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
#define ENTRY_t
The entry type.
static void NAME_stats_init(hashtable_t *t)
Initialize hashtable stats counters.
static ENTRY_t * NAME_next(hashtable_t *t, int *i)
Get the next entry from a hashtable iterator or NULL when finished.
static ENTRY_t * NAME_add(hashtable_t *t, ENTRY_t *e)
Add an entry to a hashtable.
#define MATCH_cmp
The match cmp(m, e) method.
struct hashtable hashtable_t
The hashtable type.
#define MATCH_t
The match type.
static void NAME_free(hashtable_t *t)
Destroy and free a hashtable instance.
static ENTRY_t * NAME_iter(hashtable_t *t, int *i)
Initialize a iteration and return the first entry.
static ENTRY_t * NAME_find(hashtable_t *t, MATCH_t *m)
Find an entry in a hashtable.
static unsigned mix32(unsigned h)
MurmurHash3 finalization mix function.
static unsigned nozero(unsigned h)
Ensure hash's are never zero.
static hashtable_t * NAME_new(int size)
Allocate and initialize a hashtable instance.
long find_count
The count of finds tried.
unsigned ktable[]
Table of hash keys.
long match_count
The count of matches found.
int count
Number of entries in hashtable.
unsigned char * kbloom
Bloom filter of hash keys with k=1.
long entrycmp_count
The count of entry compares done.
int size
Size of allocated hashtable.
unsigned tmask
Mask to get the hashtable index.
void ** etable
Table of pointers to entries.
long hashcmp_count
The count of hash compares done.
unsigned bshift
Shift to get the bloomfilter index.