1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
/* An implementation of hash tables:
* Copyright(C) 2000-2002 by Salvatore Sanfilippo <antirez@invece.org>
*
* This software is under the GNU GPL license
*/
#include <sys/types.h>
#include "ens.h"
#ifndef _AHT_H
#define _AHT_H
/* #define AHT_USE_SLAB */
/* ------------------------------ exit codes -------------------------------- */
#define HT_OK 0 /* Success */
#define HT_FOUND 1 /* Key found */
#define HT_NOTFOUND 2 /* Key not found */
#define HT_BUSY 3 /* Key already exist */
#define HT_NOMEM 4 /* Out of memory */
#define HT_IOVERFLOW 5 /* Index overflow */
#define HT_INVALID 6 /* Invalid argument */
#define HT_INITIAL_SIZE 256
/* ------------------ structures for the object allocator ------------------- */
#ifdef AHT_USE_SLAB
#define SLAB_ELE 256 /* cant be > of 256 */
#define SLAB_OBJSZ 8 /* need to be multiple of 4 */
#define SLAB_PTRSZ (sizeof(void*))
struct ht_cache; /* forward declaration */
struct ht_slab {
struct ht_slab *next;
struct ht_slab *prev;
struct ht_cache *parent;
u_int32_t free;
u_int8_t freelist[SLAB_ELE];
unsigned char mem[SLAB_ELE*(SLAB_OBJSZ+SLAB_PTRSZ)];
};
struct ht_cache {
struct ht_slab *head;
struct ht_slab *tail;
u_int32_t slabs;
};
#endif /* AHT_USE_SLAB */
/* ----------------------- hash table structures -----------------------------*/
struct ht_ele {
void *key;
void *data;
};
struct hashtable {
struct ht_ele **table;
unsigned int size;
unsigned int sizemask;
unsigned int used;
unsigned int collisions;
u_int32_t (*hashf)(void *key);
int (*key_compare)(void *key1, void *key2);
void (*key_destructor)(void *key);
void (*val_destructor)(void *obj);
#ifdef AHT_USE_SLAB
struct ht_cache *cache;
#endif
};
/* ----------------------------- Prototypes ----------------------------------*/
int ht_init(struct hashtable *t);
int ht_move(struct hashtable *orig, struct hashtable *dest, unsigned int index);
int ht_expand(struct hashtable *t, size_t size);
int ht_add(struct hashtable *t, void *key, void *data);
int ht_replace(struct hashtable *t, void *key, void *data);
int ht_rm(struct hashtable *t, void *key);
int ht_destroy(struct hashtable *t);
int ht_free(struct hashtable *t, unsigned int index);
int ht_search(struct hashtable *t, void *key, unsigned int *found_index);
int ht_get_byindex(struct hashtable *t, unsigned int index);
int ht_resize(struct hashtable *t);
/* provided destructors */
void ht_destructor_free(void *obj);
#define ht_no_destructor NULL
/* provided compare functions */
int ht_compare_ptr(void *key1, void *key2);
int ht_compare_string(void *key1, void *key2);
/* ------------------------ The hash functions ------------------------------ */
u_int32_t djb_hash(unsigned char *buf, size_t len);
u_int32_t djb_hashR(unsigned char *buf, size_t len);
u_int32_t trivial_hash(unsigned char *buf, size_t len);
u_int32_t trivial_hashR(unsigned char *buf, size_t len);
u_int32_t ht_strong_hash(u_int8_t *k, u_int32_t length, u_int32_t initval);
u_int32_t __ht_strong_hash(u_int8_t *k, u_int32_t length, u_int32_t initval);
/* ----------------- hash functions for common data types ------------------- */
u_int32_t ht_hash_string(void *key);
/* ----------------------------- macros --------------------------------------*/
#define ht_set_hash(t,f) ((t)->hashf = (f))
#define ht_set_key_destructor(t,f) ((t)->key_destructor = (f))
#define ht_set_val_destructor(t,f) ((t)->val_destructor = (f))
#define ht_set_key_compare(t,f) ((t)->key_compare = (f))
#define ht_collisions(t) ((t)->collisions)
#define ht_size(t) ((t)->size)
#define ht_used(t) ((t)->used)
#define ht_key(t, i) ((t)->table[(i)]->key)
#define ht_value(t, i) ((t)->table[(i)]->data)
#if AHT_DEBUG
#define dprintf(x...) do { printf(x); fflush(stdout); } while(0)
#else
#define dprintf(x...)
#endif
#endif /* _AHT_H */
|
