21 # define _HASHTABLE_H_
131 # ifndef HASHTABLE_NSTATS
147 static inline unsigned mix32(
unsigned int h)
162 # define _JOIN2(x, y) x##y
163 # define _JOIN(x, y) _JOIN2(x, y)
174 # define NAME _JOIN(ENTRY, _hashtable)
177 # define ENTRY_t _JOIN(ENTRY, _t)
178 # define KEY_t _JOIN(KEY, _t)
179 # define MATCH_t _JOIN(MATCH, _t)
180 # define KEY_hash _JOIN(KEY, _hash)
181 # define MATCH_cmp _JOIN(MATCH, _cmp)
183 # define NAME_new _JOIN(NAME, _new)
184 # define NAME_free _JOIN(NAME, _free)
185 # define NAME_stats_init _JOIN(NAME, _stats_init)
186 # define NAME_add _JOIN(NAME, _add)
187 # define NAME_find _JOIN(NAME, _find)
188 # define NAME_iter _JOIN(NAME, _iter)
189 # define NAME_next _JOIN(NAME, _next)
192 # ifdef HASHTABLE_NMIX32
193 # define _KEY_HASH(k) KEY_hash((KEY_t *)k)
195 # define _KEY_HASH(k) mix32(KEY_hash((KEY_t *)k))
201 # define _for_probe(t, k, hk, i, h) \
202 const unsigned mask = t->size - 1;\
203 unsigned hk = _KEY_HASH(k), i, s, h;\
204 if (hk == 0) hk = -1;\
205 for (i = hk & mask, s = 0; (h = t->ktable[i]); i = (i + ++s) & mask)
208 # ifndef HASHTABLE_NSTATS
209 # define _stats_inc(c) (c++)
211 # define _stats_inc(c)
227 return _hashtable_new(size);
249 # ifndef HASHTABLE_NSTATS
270 _for_probe(t, e, he, i, h);
292 _for_probe(t, m, hm, i, he) {
346 while ((*i < t->size) && !(e = t->
etable[(*i)++])) ;
361 # undef NAME_stats_init
static hashtable_t * NAME_new(int size)
Allocate and initialize a hashtable instance.
long hashcmp_count
The count of hash compares done.
long match_count
The count of matches found.
static ENTRY_t * NAME_find(hashtable_t *t, MATCH_t *m)
Find an entry in a hashtable.
static ENTRY_t * NAME_add(hashtable_t *t, ENTRY_t *e)
Add an entry to a hashtable.
static ENTRY_t * NAME_iter(hashtable_t *t, int *i)
Initialize a iteration and return the first entry.
static unsigned mix32(unsigned int h)
MurmurHash3 finalization mix function.
int size
Size of allocated hashtable.
#define MATCH_t
The match type.
static ENTRY_t * NAME_next(hashtable_t *t, int *i)
Get the next entry from a hashtable iterator or NULL when finished.
long entrycmp_count
The count of entry compares done.
unsigned ktable[]
Table of hash keys.
#define ENTRY_t
The entry type.
static void NAME_free(hashtable_t *t)
Destroy and free a hashtable instance.
#define MATCH_cmp
The match cmp(m, e) method.
long find_count
The count of finds tried.
struct hashtable hashtable_t
The hashtable type.
static void NAME_stats_init(hashtable_t *t)
Initialize hashtable stats counters.
void ** etable
Table of pointers to entries.
int count
Number of entries in hashtable.