htable: first implementation
[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, max;
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->max = (1 << ht->bits) * 3 / 4;
66                 /* This guarantees we enter update_common first add. */
67                 ht->common_mask = -1;
68                 ht->common_bits = 0;
69                 ht->table = calloc(1 << ht->bits, sizeof(uintptr_t));
70                 if (!ht->table) {
71                         free(ht);
72                         ht = NULL;
73                 }
74         }
75         return ht;
76 }
77
78 void htable_free(const struct htable *ht)
79 {
80         free((void *)ht->table);
81         free((void *)ht);
82 }
83
84 static size_t hash_bucket(const struct htable *ht, size_t h)
85 {
86         return h & ((1 << ht->bits)-1);
87 }
88
89 static void *htable_val(const struct htable *ht,
90                         struct htable_iter *i, size_t hash)
91 {
92         uintptr_t h2 = get_hash_ptr_bits(ht, hash);
93
94         while (ht->table[i->off]) {
95                 if (ht->table[i->off] != HTABLE_DELETED) {
96                         if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2)
97                                 return get_raw_ptr(ht, ht->table[i->off]);
98                 }
99                 i->off = (i->off + 1) & ((1 << ht->bits)-1);
100         }
101         return NULL;
102 }
103
104 void *htable_firstval(const struct htable *ht,
105                       struct htable_iter *i, size_t hash)
106 {
107         i->off = hash_bucket(ht, hash);
108         return htable_val(ht, i, hash);
109 }
110
111 void *htable_nextval(const struct htable *ht,
112                      struct htable_iter *i, size_t hash)
113 {
114         i->off = (i->off + 1) & ((1 << ht->bits)-1);
115         return htable_val(ht, i, hash);
116 }
117
118 void *htable_first(const struct htable *ht, struct htable_iter *i)
119 {
120         for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) {
121                 if (entry_is_valid(ht->table[i->off]))
122                         return get_raw_ptr(ht, ht->table[i->off]);
123         }
124         return NULL;
125 }
126
127 void *htable_next(const struct htable *ht, struct htable_iter *i)
128 {
129         for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) {
130                 if (entry_is_valid(ht->table[i->off]))
131                         return get_raw_ptr(ht, ht->table[i->off]);
132         }
133         return NULL;
134 }
135
136 /* This does not expand the hash table, that's up to caller. */
137 static void ht_add(struct htable *ht, const void *new, size_t h)
138 {
139         size_t i;
140
141         i = hash_bucket(ht, h);
142
143         while (entry_is_valid(ht->table[i]))
144                 i = (i + 1) & ((1 << ht->bits)-1);
145
146         ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h));
147 }
148
149 static COLD_ATTRIBUTE bool double_table(struct htable *ht)
150 {
151         unsigned int i;
152         size_t oldnum = (size_t)1 << ht->bits;
153         size_t *oldtable, e;
154
155         oldtable = ht->table;
156         ht->table = calloc(1 << (ht->bits+1), sizeof(size_t));
157         if (!ht->table) {
158                 ht->table = oldtable;
159                 return false;
160         }
161         ht->bits++;
162         ht->max *= 2;
163
164         for (i = 0; i < oldnum; i++) {
165                 if (entry_is_valid(e = oldtable[i])) {
166                         void *p = get_raw_ptr(ht, e);
167                         ht_add(ht, p, ht->rehash(p, ht->priv));
168                 }
169         }
170         free(oldtable);
171         return true;
172 }
173
174 /* We stole some bits, now we need to put them back... */
175 static COLD_ATTRIBUTE void update_common(struct htable *ht, const void *p)
176 {
177         unsigned int i;
178         uintptr_t maskdiff, bitsdiff;
179
180         if (ht->elems == 0) {
181                 ht->common_mask = -1;
182                 ht->common_bits = (uintptr_t)p;
183                 return;
184         }
185
186         /* Find bits which are unequal to old common set. */
187         maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask);
188
189         /* These are the bits which go there in existing entries. */
190         bitsdiff = ht->common_bits & maskdiff;
191
192         for (i = 0; i < (size_t)1 << ht->bits; i++) {
193                 if (!entry_is_valid(ht->table[i]))
194                         continue;
195                 /* Clear the bits no longer in the mask, set them as
196                  * expected. */
197                 ht->table[i] &= ~maskdiff;
198                 ht->table[i] |= bitsdiff;
199         }
200
201         /* Take away those bits from our mask and set. */
202         ht->common_mask &= ~maskdiff;
203         ht->common_bits &= ~maskdiff;
204 }
205
206 bool htable_add(struct htable *ht, size_t hash, const void *p)
207 {
208         if (ht->elems+1 > ht->max && !double_table(ht))
209                 return false;
210         assert(p);
211         if (((uintptr_t)p & ht->common_mask) != ht->common_bits)
212                 update_common(ht, p);
213
214         ht_add(ht, p, hash);
215         ht->elems++;
216         return true;
217 }
218
219 /* If every one of the following buckets are DELETED (up to the next unused
220    one), we can actually mark them all unused. */
221 static void delete_run(struct htable *ht, unsigned int num)
222 {
223         unsigned int i, last = num + 1;
224         size_t mask = (((size_t)1 << ht->bits)-1);
225
226         while (ht->table[last & mask]) {
227                 if (entry_is_valid(ht->table[last & mask]))
228                         return;
229                 last++;
230         }
231
232         /* Now see if we can step backwards to find previous deleted ones. */
233         for (i = num-1; ht->table[i & mask] == HTABLE_DELETED; i--);
234
235         for (i++; i < last; i++)
236                 ht->table[i & ((1 << ht->bits)-1)] = 0;
237 }
238
239 bool htable_del(struct htable *ht, size_t h, const void *p)
240 {
241         struct htable_iter i;
242         void *c;
243
244         for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
245                 if (c == p) {
246                         htable_delval(ht, &i);
247                         return true;
248                 }
249         }
250         return false;
251 }
252
253 void htable_delval(struct htable *ht, struct htable_iter *i)
254 {
255         assert(i->off < (size_t)1 << ht->bits);
256         assert(entry_is_valid(ht->table[i->off]));
257
258         ht->elems--;
259         ht->table[i->off] = HTABLE_DELETED;
260         delete_run(ht, i->off);
261 }