1 #include <ccan/hashtable/hashtable.h>
6 /* This means a struct hashtable takes at least 512 bytes / 1k (32/64 bits). */
7 #define HASHTABLE_BASE_BITS 7
9 /* We use 0x1 as deleted marker. */
10 #define HASHTABLE_DELETED ((void *)0x1)
12 /* Number of redundant bits in a pointer. */
13 #define PTR_STEAL_BITS 3
15 static inline uintptr_t get_extra_ptr_bits(const void *p)
17 return (uintptr_t)p & (((uintptr_t)1 << PTR_STEAL_BITS)-1);
20 static inline void *get_raw_ptr(const void *p)
22 return (void *)((uintptr_t)p & ~(((uintptr_t)1 << PTR_STEAL_BITS)-1));
25 static inline void *make_ptr(const void *p, uintptr_t bits)
27 return (void *)((uintptr_t)p | bits);
31 unsigned long (*rehash)(const void *elem, void *priv);
34 unsigned long elems, max;
38 static inline bool ptr_is_valid(const void *e)
40 return e > HASHTABLE_DELETED;
43 struct hashtable *hashtable_new(unsigned long (*rehash)(const void *elem,
47 struct hashtable *ht = malloc(sizeof(struct hashtable));
49 ht->bits = HASHTABLE_BASE_BITS;
53 ht->max = (1 << ht->bits) * 3 / 4;
54 ht->table = calloc(1 << ht->bits, sizeof(void *));
63 void hashtable_free(struct hashtable *ht)
69 static unsigned long hash_bucket(const struct hashtable *ht,
70 unsigned long h, unsigned long *ptrbits)
72 *ptrbits = (h >> ht->bits) & (((uintptr_t)1 << PTR_STEAL_BITS)-1);
73 return h & ((1 << ht->bits)-1);
76 /* This does not expand the hash table, that's up to caller. */
77 static void ht_add(struct hashtable *ht, const void *new, unsigned long h)
81 i = hash_bucket(ht, h, &h2);
83 while (ptr_is_valid(ht->table[i])) {
84 i = (i + 1) & ((1 << ht->bits)-1);
86 ht->table[i] = make_ptr(new, h2);
89 static bool double_table(struct hashtable *ht)
92 size_t oldnum = (size_t)1 << ht->bits;
96 ht->table = calloc(1 << (ht->bits+1), sizeof(void *));
104 for (i = 0; i < oldnum; i++) {
105 if (ptr_is_valid(e = oldtable[i])) {
107 ht_add(ht, e, ht->rehash(e, ht->priv));
114 bool hashtable_add(struct hashtable *ht, unsigned long hash, const void *p)
116 if (ht->elems+1 > ht->max && !double_table(ht))
120 assert(((uintptr_t)p & (((uintptr_t)1 << PTR_STEAL_BITS)-1)) == 0);
125 /* Find bucket for an element. */
126 static size_t ht_find(struct hashtable *ht,
128 bool (*cmp)(const void *htelem, void *cmpdata),
134 i = hash_bucket(ht, hash, &h2);
136 while ((e = ht->table[i]) != NULL) {
137 if (e != HASHTABLE_DELETED
138 && h2 == get_extra_ptr_bits(e)
139 && cmp(get_raw_ptr(ht->table[i]), cmpdata))
141 i = (i + 1) & ((1 << ht->bits)-1);
147 /* If every one of the following buckets are DELETED (up to the next unused
148 one), we can actually mark them all unused. */
149 static void delete_run(struct hashtable *ht, unsigned int num)
151 unsigned int i, last = num + 1;
153 while (ht->table[last & ((1 << ht->bits)-1)]) {
154 if (ptr_is_valid(ht->table[last & ((1 << ht->bits)-1)]))
158 for (i = num; i < last; i++)
159 ht->table[i & ((1 << ht->bits)-1)] = NULL;
162 void *hashtable_find(struct hashtable *ht,
164 bool (*cmp)(const void *htelem, void *cmpdata),
167 size_t i = ht_find(ht, hash, cmp, cmpdata);
169 return get_raw_ptr(ht->table[i]);
173 static bool ptr_cmp(const void *htelem, void *cmpdata)
175 return htelem == cmpdata;
178 bool hashtable_del(struct hashtable *ht, unsigned long hash, const void *p)
180 size_t i = ht_find(ht, hash, ptr_cmp, (void *)p);
185 ht->table[i] = HASHTABLE_DELETED;
190 void _hashtable_traverse(struct hashtable *ht,
191 bool (*cb)(void *p, void *cbarg),
196 for (i = 0; i < (1 << ht->bits); i++) {
197 if (ptr_is_valid(ht->table[i]))
198 if (cb(get_raw_ptr(ht->table[i]), cbarg))