htable: start empty.
[ccan] / ccan / htable / htable.c
1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #include <ccan/htable/htable.h>
3 #include <ccan/compiler/compiler.h>
4 #include <stdint.h>
5 #include <stdlib.h>
6 #include <limits.h>
7 #include <stdbool.h>
8 #include <assert.h>
9
10 /* We use 0x1 as deleted marker. */
11 #define HTABLE_DELETED (0x1)
12
13 struct htable {
14         size_t (*rehash)(const void *elem, void *priv);
15         void *priv;
16         unsigned int bits;
17         size_t elems, deleted, max, max_with_deleted;
18         /* These are the bits which are the same in all pointers. */
19         uintptr_t common_mask, common_bits;
20         uintptr_t perfect_bit;
21         uintptr_t *table;
22 };
23
24 /* We clear out the bits which are always the same, and put metadata there. */
25 static inline uintptr_t get_extra_ptr_bits(const struct htable *ht,
26                                            uintptr_t e)
27 {
28         return e & ht->common_mask;
29 }
30
31 static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e)
32 {
33         return (void *)((e & ~ht->common_mask) | ht->common_bits);
34 }
35
36 static inline uintptr_t make_hval(const struct htable *ht,
37                                   const void *p, uintptr_t bits)
38 {
39         return ((uintptr_t)p & ~ht->common_mask) | bits;
40 }
41
42 static inline bool entry_is_valid(uintptr_t e)
43 {
44         return e > HTABLE_DELETED;
45 }
46
47 static inline uintptr_t get_hash_ptr_bits(const struct htable *ht,
48                                           size_t hash)
49 {
50         /* Shuffling the extra bits (as specified in mask) down the
51          * end is quite expensive.  But the lower bits are redundant, so
52          * we fold the value first. */
53         return (hash ^ (hash >> ht->bits))
54                 & ht->common_mask & ~ht->perfect_bit;
55 }
56
57 struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
58                           void *priv)
59 {
60         struct htable *ht = malloc(sizeof(struct htable));
61         if (ht) {
62                 ht->bits = 0;
63                 ht->rehash = rehash;
64                 ht->priv = priv;
65                 ht->elems = 0;
66                 ht->deleted = 0;
67                 ht->max = 0;
68                 ht->max_with_deleted = 0;
69                 /* This guarantees we enter update_common first add. */
70                 ht->common_mask = -1;
71                 ht->common_bits = 0;
72                 ht->perfect_bit = 0;
73                 /* Dummy table until first insert. */
74                 ht->table = &ht->perfect_bit;
75         }
76         return ht;
77 }
78
79 void htable_free(const struct htable *ht)
80 {
81         if (ht->table != &ht->perfect_bit)
82                 free((void *)ht->table);
83         free((void *)ht);
84 }
85
86 static size_t hash_bucket(const struct htable *ht, size_t h)
87 {
88         return h & ((1 << ht->bits)-1);
89 }
90
91 static void *htable_val(const struct htable *ht,
92                         struct htable_iter *i, size_t hash, uintptr_t perfect)
93 {
94         uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect;
95
96         while (ht->table[i->off]) {
97                 if (ht->table[i->off] != HTABLE_DELETED) {
98                         if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2)
99                                 return get_raw_ptr(ht, ht->table[i->off]);
100                 }
101                 i->off = (i->off + 1) & ((1 << ht->bits)-1);
102                 h2 &= ~perfect;
103         }
104         return NULL;
105 }
106
107 void *htable_firstval(const struct htable *ht,
108                       struct htable_iter *i, size_t hash)
109 {
110         i->off = hash_bucket(ht, hash);
111         return htable_val(ht, i, hash, ht->perfect_bit);
112 }
113
114 void *htable_nextval(const struct htable *ht,
115                      struct htable_iter *i, size_t hash)
116 {
117         i->off = (i->off + 1) & ((1 << ht->bits)-1);
118         return htable_val(ht, i, hash, 0);
119 }
120
121 void *htable_first(const struct htable *ht, struct htable_iter *i)
122 {
123         for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) {
124                 if (entry_is_valid(ht->table[i->off]))
125                         return get_raw_ptr(ht, ht->table[i->off]);
126         }
127         return NULL;
128 }
129
130 void *htable_next(const struct htable *ht, struct htable_iter *i)
131 {
132         for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) {
133                 if (entry_is_valid(ht->table[i->off]))
134                         return get_raw_ptr(ht, ht->table[i->off]);
135         }
136         return NULL;
137 }
138
139 /* This does not expand the hash table, that's up to caller. */
140 static void ht_add(struct htable *ht, const void *new, size_t h)
141 {
142         size_t i;
143         uintptr_t perfect = ht->perfect_bit;
144
145         i = hash_bucket(ht, h);
146
147         while (entry_is_valid(ht->table[i])) {
148                 perfect = 0;
149                 i = (i + 1) & ((1 << ht->bits)-1);
150         }
151         ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect);
152 }
153
154 static COLD bool double_table(struct htable *ht)
155 {
156         unsigned int i;
157         size_t oldnum = (size_t)1 << ht->bits;
158         uintptr_t *oldtable, e;
159
160         oldtable = ht->table;
161         ht->table = calloc(1 << (ht->bits+1), sizeof(size_t));
162         if (!ht->table) {
163                 ht->table = oldtable;
164                 return false;
165         }
166         ht->bits++;
167         ht->max = ((size_t)3 << ht->bits) / 4;
168         ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
169
170         /* If we lost our "perfect bit", get it back now. */
171         if (!ht->perfect_bit && ht->common_mask) {
172                 for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) {
173                         if (ht->common_mask & ((size_t)1 << i)) {
174                                 ht->perfect_bit = (size_t)1 << i;
175                                 break;
176                         }
177                 }
178         }
179
180         if (oldtable != &ht->perfect_bit) {
181                 for (i = 0; i < oldnum; i++) {
182                         if (entry_is_valid(e = oldtable[i])) {
183                                 void *p = get_raw_ptr(ht, e);
184                                 ht_add(ht, p, ht->rehash(p, ht->priv));
185                         }
186                 }
187                 free(oldtable);
188         }
189         ht->deleted = 0;
190         return true;
191 }
192
193 static COLD void rehash_table(struct htable *ht)
194 {
195         size_t start, i;
196         uintptr_t e;
197
198         /* Beware wrap cases: we need to start from first empty bucket. */
199         for (start = 0; ht->table[start]; start++);
200
201         for (i = 0; i < (size_t)1 << ht->bits; i++) {
202                 size_t h = (i + start) & ((1 << ht->bits)-1);
203                 e = ht->table[h];
204                 if (!e)
205                         continue;
206                 if (e == HTABLE_DELETED)
207                         ht->table[h] = 0;
208                 else if (!(e & ht->perfect_bit)) {
209                         void *p = get_raw_ptr(ht, e);
210                         ht->table[h] = 0;
211                         ht_add(ht, p, ht->rehash(p, ht->priv));
212                 }
213         }
214         ht->deleted = 0;
215 }
216
217 /* We stole some bits, now we need to put them back... */
218 static COLD void update_common(struct htable *ht, const void *p)
219 {
220         unsigned int i;
221         uintptr_t maskdiff, bitsdiff;
222
223         if (ht->elems == 0) {
224                 ht->common_mask = -1;
225                 ht->common_bits = (uintptr_t)p;
226                 ht->perfect_bit = 1;
227                 return;
228         }
229
230         /* Find bits which are unequal to old common set. */
231         maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask);
232
233         /* These are the bits which go there in existing entries. */
234         bitsdiff = ht->common_bits & maskdiff;
235
236         for (i = 0; i < (size_t)1 << ht->bits; i++) {
237                 if (!entry_is_valid(ht->table[i]))
238                         continue;
239                 /* Clear the bits no longer in the mask, set them as
240                  * expected. */
241                 ht->table[i] &= ~maskdiff;
242                 ht->table[i] |= bitsdiff;
243         }
244
245         /* Take away those bits from our mask, bits and perfect bit. */
246         ht->common_mask &= ~maskdiff;
247         ht->common_bits &= ~maskdiff;
248         ht->perfect_bit &= ~maskdiff;
249 }
250
251 bool htable_add(struct htable *ht, size_t hash, const void *p)
252 {
253         if (ht->elems+1 > ht->max && !double_table(ht))
254                 return false;
255         if (ht->elems+1 + ht->deleted > ht->max_with_deleted)
256                 rehash_table(ht);
257         assert(p);
258         if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
259                 update_common(ht, p);
260
261         ht_add(ht, p, hash);
262         ht->elems++;
263         return true;
264 }
265
266 bool htable_del(struct htable *ht, size_t h, const void *p)
267 {
268         struct htable_iter i;
269         void *c;
270
271         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
272                 if (c == p) {
273                         htable_delval(ht, &i);
274                         return true;
275                 }
276         }
277         return false;
278 }
279
280 void htable_delval(struct htable *ht, struct htable_iter *i)
281 {
282         assert(i->off < (size_t)1 << ht->bits);
283         assert(entry_is_valid(ht->table[i->off]));
284
285         ht->elems--;
286         ht->table[i->off] = HTABLE_DELETED;
287         ht->deleted++;
288 }