1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #include <ccan/htable/htable.h>
3 #include <ccan/likely/likely.h>
4 #include <ccan/compiler/compiler.h>
12 /* We use 0x1 as deleted marker. */
13 #define HTABLE_DELETED (0x1)
15 /* perfect_bitnum 63 means there's no perfect bitnum */
16 #define NO_PERFECT_BIT (sizeof(uintptr_t) * CHAR_BIT - 1)
18 static void *htable_default_alloc(struct htable *ht, size_t len)
20 return calloc(len, 1);
23 static void htable_default_free(struct htable *ht, void *p)
28 static void *(*htable_alloc)(struct htable *, size_t) = htable_default_alloc;
29 static void (*htable_free)(struct htable *, void *) = htable_default_free;
31 void htable_set_allocator(void *(*alloc)(struct htable *, size_t len),
32 void (*free)(struct htable *, void *p))
35 alloc = htable_default_alloc;
37 free = htable_default_free;
42 /* We clear out the bits which are always the same, and put metadata there. */
43 static inline uintptr_t get_extra_ptr_bits(const struct htable *ht,
46 return e & ht->common_mask;
49 static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e)
51 return (void *)((e & ~ht->common_mask) | ht->common_bits);
54 static inline uintptr_t make_hval(const struct htable *ht,
55 const void *p, uintptr_t bits)
57 return ((uintptr_t)p & ~ht->common_mask) | bits;
60 static inline uintptr_t *actually_valid_pair(const struct htable *ht)
62 return ht->table + ((size_t)1 << ht->bits);
65 /* We have have two entries which look deleted, but we remember
67 static inline bool entry_actually_valid(const struct htable *ht, size_t off)
69 const uintptr_t *valid = actually_valid_pair(ht);
70 /* In the empty case, these are "common_mask" and "rehash"
71 * which cannot be 0 */
72 return valid[0] == off || valid[1] == off;
75 /* Initialize the "actually valid" pair. */
76 static inline void init_actually_valid(struct htable *ht)
78 uintptr_t *valid = actually_valid_pair(ht);
79 valid[0] = valid[1] = ((size_t)1 << ht->bits);
82 /* Add to the "actually valid" pair: there can only ever be two! */
83 static COLD void add_actually_valid(struct htable *ht, size_t off)
85 uintptr_t *valid = actually_valid_pair(ht);
86 if (valid[0] == ((size_t)1 << ht->bits))
89 assert(valid[1] == ((size_t)1 << ht->bits));
94 static COLD void del_actually_valid(struct htable *ht, size_t off)
96 uintptr_t *validpair = actually_valid_pair(ht);
97 if (validpair[0] == off)
98 validpair[0] = ((size_t)1 << ht->bits);
100 assert(validpair[1] == off);
101 validpair[1] = ((size_t)1 << ht->bits);
105 /* If this entry looks invalid, check entry_actually_valid! */
106 static inline bool entry_looks_invalid(const struct htable *ht, size_t off)
108 return ht->table[off] <= HTABLE_DELETED;
111 static inline bool entry_is_valid(const struct htable *ht, size_t off)
113 if (!entry_looks_invalid(ht, off))
115 return entry_actually_valid(ht, off);
118 static inline uintptr_t ht_perfect_mask(const struct htable *ht)
120 return (uintptr_t)2 << ht->perfect_bitnum;
123 static inline uintptr_t get_hash_ptr_bits(const struct htable *ht,
126 /* Shuffling the extra bits (as specified in mask) down the
127 * end is quite expensive. But the lower bits are redundant, so
128 * we fold the value first. */
129 return (hash ^ (hash >> ht->bits))
130 & ht->common_mask & ~ht_perfect_mask(ht);
133 void htable_init(struct htable *ht,
134 size_t (*rehash)(const void *elem, void *priv), void *priv)
136 struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL);
140 ht->table = &ht->common_bits;
143 static inline size_t ht_max(const struct htable *ht)
145 return ((size_t)3 << ht->bits) / 4;
148 static inline size_t ht_max_with_deleted(const struct htable *ht)
150 return ((size_t)9 << ht->bits) / 10;
153 /* Includes the two trailing "not-deleted" entries */
154 static size_t htable_alloc_size(size_t bits)
156 return (sizeof(size_t) << bits) + 2 * sizeof(size_t);
159 bool htable_init_sized(struct htable *ht,
160 size_t (*rehash)(const void *, void *),
161 void *priv, size_t expect)
163 htable_init(ht, rehash, priv);
165 /* Don't go insane with sizing. */
166 for (ht->bits = 1; ((size_t)3 << ht->bits) / 4 < expect; ht->bits++) {
171 ht->table = htable_alloc(ht, htable_alloc_size(ht->bits));
173 ht->table = &ht->common_bits;
176 init_actually_valid(ht);
177 (void)htable_debug(ht, HTABLE_LOC);
181 void htable_clear(struct htable *ht)
183 if (ht->table != &ht->common_bits)
184 htable_free(ht, (void *)ht->table);
185 htable_init(ht, ht->rehash, ht->priv);
188 bool htable_copy_(struct htable *dst, const struct htable *src)
190 uintptr_t *htable = htable_alloc(dst, htable_alloc_size(src->bits));
197 memcpy(dst->table, src->table, htable_alloc_size(src->bits));
201 static size_t hash_bucket(const struct htable *ht, size_t h)
203 return h & ((1 << ht->bits)-1);
206 static void *htable_val(const struct htable *ht,
207 struct htable_iter *i, size_t hash, uintptr_t perfect)
209 uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect;
210 const uintptr_t *valid = actually_valid_pair(ht);
212 while (ht->table[i->off] || valid[0] == i->off || valid[1] == i->off) {
213 uintptr_t e = ht->table[i->off];
214 if (e != HTABLE_DELETED || valid[0] == i->off || valid[1] == i->off) {
215 if (get_extra_ptr_bits(ht, e) == h2) {
216 return get_raw_ptr(ht, e);
219 i->off = (i->off + 1) & ((1 << ht->bits)-1);
225 void *htable_firstval_(const struct htable *ht,
226 struct htable_iter *i, size_t hash)
228 i->off = hash_bucket(ht, hash);
229 return htable_val(ht, i, hash, ht_perfect_mask(ht));
232 void *htable_nextval_(const struct htable *ht,
233 struct htable_iter *i, size_t hash)
235 i->off = (i->off + 1) & ((1 << ht->bits)-1);
236 return htable_val(ht, i, hash, 0);
239 void *htable_first_(const struct htable *ht, struct htable_iter *i)
241 for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) {
242 if (entry_is_valid(ht, i->off))
243 return get_raw_ptr(ht, ht->table[i->off]);
248 void *htable_next_(const struct htable *ht, struct htable_iter *i)
250 for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) {
251 if (entry_is_valid(ht, i->off))
252 return get_raw_ptr(ht, ht->table[i->off]);
257 void *htable_prev_(const struct htable *ht, struct htable_iter *i)
263 if (entry_is_valid(ht, i->off))
264 return get_raw_ptr(ht, ht->table[i->off]);
268 /* This does not expand the hash table, that's up to caller. */
269 static void ht_add(struct htable *ht, const void *new, size_t h)
272 uintptr_t perfect = ht_perfect_mask(ht);
274 i = hash_bucket(ht, h);
276 while (entry_is_valid(ht, i)) {
278 i = (i + 1) & ((1 << ht->bits)-1);
280 ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);
282 /* If it looks invalid, add it to exceptions */
283 if (ht->table[i] <= HTABLE_DELETED)
284 add_actually_valid(ht, i);
287 static COLD bool double_table(struct htable *ht)
290 struct htable oldht = *ht;
292 ht->table = htable_alloc(ht, htable_alloc_size(ht->bits+1));
294 ht->table = oldht.table;
298 init_actually_valid(ht);
300 /* If we lost our "perfect bit", get it back now. */
301 if (ht->perfect_bitnum == NO_PERFECT_BIT && ht->common_mask) {
302 for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) {
303 if (ht->common_mask & ((size_t)2 << i)) {
304 ht->perfect_bitnum = i;
310 if (oldht.table != &ht->common_bits) {
311 for (i = 0; i < (size_t)1 << oldht.bits; i++) {
312 if (entry_is_valid(&oldht, i)) {
313 void *p = get_raw_ptr(&oldht, oldht.table[i]);
314 ht_add(ht, p, ht->rehash(p, ht->priv));
317 /* Pass ht here to callback: oldht is an internal figment */
318 htable_free(ht, oldht.table);
322 (void)htable_debug(ht, HTABLE_LOC);
326 static COLD void rehash_table(struct htable *ht)
329 uintptr_t e, perfect = ht_perfect_mask(ht);
330 uintptr_t *validpair = actually_valid_pair(ht);
332 /* Beware wrap cases: we need to start from first empty bucket. */
333 for (start = 0; ht->table[start]; start++);
335 for (i = 0; i < (size_t)1 << ht->bits; i++) {
336 size_t h = (i + start) & ((1 << ht->bits)-1);
337 uintptr_t *actually = NULL;
339 if (e <= HTABLE_DELETED) {
340 /* If it's actually valid, remember in case we move it! */
341 if (validpair[0] == h) {
342 actually = &validpair[0];
343 } else if (validpair[1] == h) {
344 actually = &validpair[1];
351 if (!(e & perfect)) {
352 void *p = get_raw_ptr(ht, e);
354 /* Clear actuallyvalid, let ht_add refill */
356 *actually = ((size_t)1 << ht->bits);
357 ht_add(ht, p, ht->rehash(p, ht->priv));
361 (void)htable_debug(ht, HTABLE_LOC);
364 /* We stole some bits, now we need to put them back... */
365 static COLD void update_common(struct htable *ht, const void *p)
368 uintptr_t maskdiff, bitsdiff;
370 if (ht->elems == 0) {
371 ht->common_mask = -1;
372 ht->common_bits = ((uintptr_t)p & ht->common_mask);
373 ht->perfect_bitnum = 0;
374 (void)htable_debug(ht, HTABLE_LOC);
378 /* Find bits which are unequal to old common set. */
379 maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask);
381 /* These are the bits which go there in existing entries. */
382 bitsdiff = ht->common_bits & maskdiff;
384 for (i = 0; i < (size_t)1 << ht->bits; i++) {
385 if (!entry_is_valid(ht, i))
387 /* Clear the bits no longer in the mask, set them as
389 ht->table[i] &= ~maskdiff;
390 ht->table[i] |= bitsdiff;
392 /* Make sure it's not newly falsely invalid */
393 if (ht->table[i] <= HTABLE_DELETED && !entry_actually_valid(ht, i))
394 add_actually_valid(ht, i);
397 /* Take away those bits from our mask, bits and perfect bit. */
398 ht->common_mask &= ~maskdiff;
399 ht->common_bits &= ~maskdiff;
400 if (ht_perfect_mask(ht) & maskdiff)
401 ht->perfect_bitnum = NO_PERFECT_BIT;
402 (void)htable_debug(ht, HTABLE_LOC);
405 bool htable_add_(struct htable *ht, size_t hash, const void *p)
407 if (ht->elems+1 > ht_max(ht) && !double_table(ht))
409 if (ht->elems+1 + ht->deleted > ht_max_with_deleted(ht))
412 if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
413 update_common(ht, p);
420 bool htable_del_(struct htable *ht, size_t h, const void *p)
422 struct htable_iter i;
425 for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
427 htable_delval(ht, &i);
434 void htable_delval_(struct htable *ht, struct htable_iter *i)
436 assert(i->off < (size_t)1 << ht->bits);
438 if (entry_looks_invalid(ht, i->off))
439 del_actually_valid(ht, i->off);
442 ht->table[i->off] = HTABLE_DELETED;
446 void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i)
449 struct htable_iter unwanted;
453 i->off = seed % ((size_t)1 << ht->bits);
454 e = htable_next(ht, i);
456 e = htable_first(ht, i);
460 struct htable *htable_check(const struct htable *ht, const char *abortstr)
463 struct htable_iter i;
465 const uintptr_t *validpair = actually_valid_pair(ht);
467 /* Use non-DEBUG versions here, to avoid infinite recursion with
468 * CCAN_HTABLE_DEBUG! */
469 for (p = htable_first_(ht, &i); p; p = htable_next_(ht, &i)) {
470 struct htable_iter i2;
472 size_t h = ht->rehash(p, ht->priv);
477 /* Open-code htable_get to avoid CCAN_HTABLE_DEBUG */
478 for (c = htable_firstval_(ht, &i2, h);
480 c = htable_nextval_(ht, &i2, h)) {
490 "%s: element %p in position %zu"
491 " cannot find itself\n",
498 if (n != ht->elems) {
501 "%s: found %zu elems, expected %zu\n",
502 abortstr, n, ht->elems);
508 /* Check validpair does actually override invalid-looking entries! */
509 if (ht->table != &ht->common_bits) {
511 for (i = 0; i < 2; i++) {
512 if (validpair[i] == ((size_t)1 << ht->bits))
514 if (validpair[i] > ((size_t)1 << ht->bits)) {
517 "%s: validpair[%zu] points at %zu"
518 " which is out of bounds\n",
519 abortstr, i, validpair[i]);
524 if (entry_looks_invalid(ht, validpair[i]))
529 "%s: validpair[%zu] points at %zu"
530 " which seems valid\n",
531 abortstr, i, validpair[i]);
538 return (struct htable *)ht;