21 # define _HASHTABLE_H_ 134 # ifndef HASHTABLE_NBLOOM 137 # ifndef HASHTABLE_NSTATS 144 # ifndef HASHTABLE_NBLOOM 155 # ifndef HASHTABLE_NBLOOM 156 static inline void hashtable_setbloom(
hashtable_t *t,
unsigned const h)
159 unsigned const i = h >> t->
bshift;
160 t->
kbloom[i / 8] |= (
unsigned char)(1 << (i % 8));
163 static inline bool hashtable_getbloom(
hashtable_t *t,
unsigned const h)
166 unsigned const i = h >> t->
bshift;
167 return (t->
kbloom[i / 8] >> (i % 8)) & 1;
172 static inline unsigned mix32(
unsigned h)
183 static inline unsigned nozero(
unsigned h)
185 return h ? h : (unsigned)-1;
193 # define _JOIN2(x, y) x##y 194 # define _JOIN(x, y) _JOIN2(x, y) 205 # define NAME _JOIN(ENTRY, _hashtable) 208 # define ENTRY_t _JOIN(ENTRY, _t) 209 # define KEY_t _JOIN(KEY, _t) 210 # define MATCH_t _JOIN(MATCH, _t) 211 # define KEY_hash _JOIN(KEY, _hash) 212 # define MATCH_cmp _JOIN(MATCH, _cmp) 214 # define NAME_new _JOIN(NAME, _new) 215 # define NAME_free _JOIN(NAME, _free) 216 # define NAME_stats_init _JOIN(NAME, _stats_init) 217 # define NAME_add _JOIN(NAME, _add) 218 # define NAME_find _JOIN(NAME, _find) 219 # define NAME_iter _JOIN(NAME, _iter) 220 # define NAME_next _JOIN(NAME, _next) 223 # ifdef HASHTABLE_NMIX32 224 # define _KEY_HASH(k) nozero(KEY_hash((KEY_t *)k)) 226 # define _KEY_HASH(k) nozero(mix32(KEY_hash((KEY_t *)k))) 231 # define _for_probe(t, hk, i, h) \ 232 unsigned const *const ktable = t->ktable;\ 233 unsigned const tmask = t->tmask;\ 235 for (i = hk & tmask, s = 0; (h = ktable[i]); i = (i + ++s) & tmask) 238 # ifndef HASHTABLE_NSTATS 239 # define _stats_inc(c) (c++) 241 # define _stats_inc(c) 257 return _hashtable_new(size);
279 # ifndef HASHTABLE_NSTATS 297 unsigned he = _KEY_HASH(e);
302 # ifndef HASHTABLE_NBLOOM 303 hashtable_setbloom(t, he);
305 _for_probe(t, he, i, h);
324 unsigned hm = _KEY_HASH(m);
328 # ifndef HASHTABLE_NBLOOM 329 if (!hashtable_getbloom(t, hm))
332 _for_probe(t, hm, i, he) {
388 while ((*i < t->size) && !(e = t->
etable[(*i)++])) ;
403 # undef NAME_stats_init unsigned char * kbloom
Bloom filter of hash keys with k=1.
static hashtable_t * NAME_new(int size)
Allocate and initialize a hashtable instance.
unsigned tmask
Mask to get the hashtable index.
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 unsigned nozero(unsigned h)
Ensure hash's are never zero.
static ENTRY_t * NAME_iter(hashtable_t *t, int *i)
Initialize a iteration and return the first entry.
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.
static unsigned mix32(unsigned h)
MurmurHash3 finalization mix function.
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.
unsigned bshift
Shift to get the bloomfilter index.
#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.