132# ifndef HASHTABLE_NBLOOM
135# ifndef HASHTABLE_NSTATS
142# ifndef HASHTABLE_NBLOOM
153# ifndef HASHTABLE_NBLOOM
154static inline void hashtable_setbloom(
hashtable_t *t,
unsigned const h)
157 unsigned const i = h >> t->
bshift;
158 t->
kbloom[i / 8] |= (
unsigned char)(1 << (i % 8));
161static inline bool hashtable_getbloom(
hashtable_t *t,
unsigned const h)
164 unsigned const i = h >> t->
bshift;
165 return (t->
kbloom[i / 8] >> (i % 8)) & 1;
170static inline unsigned mix32(
unsigned h)
183 return h ? h : (unsigned)-1;
194# define _JOIN2(x, y) x##y
195# define _JOIN(x, y) _JOIN2(x, y)
206# define NAME _JOIN(ENTRY, _hashtable)
209# define ENTRY_t _JOIN(ENTRY, _t)
210# define KEY_t _JOIN(KEY, _t)
211# define MATCH_t _JOIN(MATCH, _t)
212# define KEY_hash _JOIN(KEY, _hash)
213# define MATCH_cmp _JOIN(MATCH, _cmp)
215# define NAME_new _JOIN(NAME, _new)
216# define NAME_free _JOIN(NAME, _free)
217# define NAME_stats_init _JOIN(NAME, _stats_init)
218# define NAME_add _JOIN(NAME, _add)
219# define NAME_find _JOIN(NAME, _find)
220# define NAME_iter _JOIN(NAME, _iter)
221# define NAME_next _JOIN(NAME, _next)
224# ifdef HASHTABLE_NMIX32
225# define _KEY_HASH(k) nozero(KEY_hash((KEY_t *)k))
227# define _KEY_HASH(k) nozero(mix32(KEY_hash((KEY_t *)k)))
232# define _for_probe(t, hk, i, h) \
233 unsigned const *const ktable = t->ktable;\
234 unsigned const tmask = t->tmask;\
236 for (i = hk & tmask, s = 0; (h = ktable[i]); i = (i + ++s) & tmask)
239# ifndef HASHTABLE_NSTATS
240# define _stats_inc(c) (c++)
242# define _stats_inc(c)
258 return _hashtable_new(size);
280# ifndef HASHTABLE_NSTATS
298 unsigned he = _KEY_HASH(e);
303# ifndef HASHTABLE_NBLOOM
304 hashtable_setbloom(t, he);
306 _for_probe(t, he, i, h);
325 unsigned hm = _KEY_HASH(m);
329# ifndef HASHTABLE_NBLOOM
330 if (!hashtable_getbloom(t, hm))
333 _for_probe(t, hm, i, he) {
389 while ((*i < t->size) && !(e = t->
etable[(*i)++])) ;
404# 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_find(hashtable_t *t, MATCH_t *m)
Find an entry in a hashtable.
static ENTRY_t * NAME_next(hashtable_t *t, int *i)
Get the next entry from a hashtable iterator or NULL when finished.
#define MATCH_cmp
The match cmp(m, e) method.
static ENTRY_t * NAME_iter(hashtable_t *t, int *i)
Initialize a iteration and return the first entry.
static hashtable_t * NAME_new(int size)
Allocate and initialize a hashtable instance.
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_add(hashtable_t *t, ENTRY_t *e)
Add an entry to a hashtable.
static unsigned mix32(unsigned h)
MurmurHash3 finalization mix function.
static unsigned nozero(unsigned h)
Ensure hash's are never zero.
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.