htable: rehash to clear delete markers
[ccan] / ccan / htable / htable.c
1 #include <ccan/htable/htable.h>
2 #include <ccan/compiler/compiler.h>
3 #include <stdint.h>
4 #include <stdlib.h>
5 #include <stdbool.h>
6 #include <assert.h>
7
8 /* This means a struct htable takes at least 512 bytes / 1k (32/64 bits). */
9 #define HTABLE_BASE_BITS 7
10
11 /* We use 0x1 as deleted marker. */
12 #define HTABLE_DELETED (0x1)
13
14 struct htable {
15         size_t (*rehash)(const void *elem, void *priv);
16         void *priv;
17         unsigned int bits;
18         size_t elems, deleted, max, max_with_deleted;
19         /* These are the bits which are the same in all pointers. */
20         uintptr_t common_mask, common_bits;
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)) & ht->common_mask;
54 }
55
56 struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
57                           void *priv)
58 {
59         struct htable *ht = malloc(sizeof(struct htable));
60         if (ht) {
61                 ht->bits = HTABLE_BASE_BITS;
62                 ht->rehash = rehash;
63                 ht->priv = priv;
64                 ht->elems = 0;
65                 ht->deleted = 0;
66                 ht->max = (1 << ht->bits) * 2 / 3;
67                 ht->max_with_deleted = (1 << ht->bits) * 4 / 5;
68                 /* This guarantees we enter update_common first add. */
69                 ht->common_mask = -1;
70                 ht->common_bits = 0;
71                 ht->table = calloc(1 << ht->bits, sizeof(uintptr_t));
72                 if (!ht->table) {
73                         free(ht);
74                         ht = NULL;
75                 }
76         }
77         return ht;
78 }
79
80 void htable_free(const struct htable *ht)
81 {
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)
93 {
94         uintptr_t h2 = get_hash_ptr_bits(ht, hash);
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         }
103         return NULL;
104 }
105
106 void *htable_firstval(const struct htable *ht,
107                       struct htable_iter *i, size_t hash)
108 {
109         i->off = hash_bucket(ht, hash);
110         return htable_val(ht, i, hash);
111 }
112
113 void *htable_nextval(const struct htable *ht,
114                      struct htable_iter *i, size_t hash)
115 {
116         i->off = (i->off + 1) & ((1 << ht->bits)-1);
117         return htable_val(ht, i, hash);
118 }
119
120 void *htable_first(const struct htable *ht, struct htable_iter *i)
121 {
122         for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) {
123                 if (entry_is_valid(ht->table[i->off]))
124                         return get_raw_ptr(ht, ht->table[i->off]);
125         }
126         return NULL;
127 }
128
129 void *htable_next(const struct htable *ht, struct htable_iter *i)
130 {
131         for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) {
132                 if (entry_is_valid(ht->table[i->off]))
133                         return get_raw_ptr(ht, ht->table[i->off]);
134         }
135         return NULL;
136 }
137
138 /* This does not expand the hash table, that's up to caller. */
139 static void ht_add(struct htable *ht, const void *new, size_t h)
140 {
141         size_t i;
142
143         i = hash_bucket(ht, h);
144
145         while (entry_is_valid(ht->table[i]))
146                 i = (i + 1) & ((1 << ht->bits)-1);
147
148         ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h));
149 }
150
151 static COLD_ATTRIBUTE bool double_table(struct htable *ht)
152 {
153         unsigned int i;
154         size_t oldnum = (size_t)1 << ht->bits;
155         uintptr_t *oldtable, e;
156
157         oldtable = ht->table;
158         ht->table = calloc(1 << (ht->bits+1), sizeof(size_t));
159         if (!ht->table) {
160                 ht->table = oldtable;
161                 return false;
162         }
163         ht->bits++;
164         ht->max *= 2;
165         ht->max_with_deleted *= 2;
166
167         for (i = 0; i < oldnum; i++) {
168                 if (entry_is_valid(e = oldtable[i])) {
169                         void *p = get_raw_ptr(ht, e);
170                         ht_add(ht, p, ht->rehash(p, ht->priv));
171                 }
172         }
173         ht->deleted = 0;
174         free(oldtable);
175         return true;
176 }
177
178 static COLD_ATTRIBUTE void rehash_table(struct htable *ht)
179 {
180         size_t start, i;
181         uintptr_t e;
182
183         /* Beware wrap cases: we need to start from first empty bucket. */
184         for (start = 0; ht->table[start]; start++);
185
186         for (i = 0; i < (size_t)1 << ht->bits; i++) {
187                 size_t h = (i + start) & ((1 << ht->bits)-1);
188                 e = ht->table[h];
189                 if (!e)
190                         continue;
191                 ht->table[h] = 0;
192                 if (e != HTABLE_DELETED) {
193                         void *p = get_raw_ptr(ht, e);
194                         ht_add(ht, p, ht->rehash(p, ht->priv));
195                 }
196         }
197         ht->deleted = 0;
198 }
199
200 /* We stole some bits, now we need to put them back... */
201 static COLD_ATTRIBUTE void update_common(struct htable *ht, const void *p)
202 {
203         unsigned int i;
204         uintptr_t maskdiff, bitsdiff;
205
206         if (ht->elems == 0) {
207                 ht->common_mask = -1;
208                 ht->common_bits = (uintptr_t)p;
209                 return;
210         }
211
212         /* Find bits which are unequal to old common set. */
213         maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask);
214
215         /* These are the bits which go there in existing entries. */
216         bitsdiff = ht->common_bits & maskdiff;
217
218         for (i = 0; i < (size_t)1 << ht->bits; i++) {
219                 if (!entry_is_valid(ht->table[i]))
220                         continue;
221                 /* Clear the bits no longer in the mask, set them as
222                  * expected. */
223                 ht->table[i] &= ~maskdiff;
224                 ht->table[i] |= bitsdiff;
225         }
226
227         /* Take away those bits from our mask and set. */
228         ht->common_mask &= ~maskdiff;
229         ht->common_bits &= ~maskdiff;
230 }
231
232 bool htable_add(struct htable *ht, size_t hash, const void *p)
233 {
234         if (ht->elems+1 > ht->max && !double_table(ht))
235                 return false;
236         if (ht->elems+1 + ht->deleted > ht->max_with_deleted)
237                 rehash_table(ht);
238         assert(p);
239         if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
240                 update_common(ht, p);
241
242         ht_add(ht, p, hash);
243         ht->elems++;
244         return true;
245 }
246
247 bool htable_del(struct htable *ht, size_t h, const void *p)
248 {
249         struct htable_iter i;
250         void *c;
251
252         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
253                 if (c == p) {
254                         htable_delval(ht, &i);
255                         return true;
256                 }
257         }
258         return false;
259 }
260
261 void htable_delval(struct htable *ht, struct htable_iter *i)
262 {
263         assert(i->off < (size_t)1 << ht->bits);
264         assert(entry_is_valid(ht->table[i->off]));
265
266         ht->elems--;
267         ht->table[i->off] = HTABLE_DELETED;
268         ht->deleted++;
269 }