Allow for static initialisation.
[libeze] / ez-set.c
1 /* ez-set.c: Low level hash table.
2
3    Copyright (C) 2019 Michael Zucchi
4
5    This program is free software: you can redistribute it and/or
6    modify it under the terms of the GNU Lesser General Public License
7    as published by the Free Software Foundation, either version 3 of
8    the License, or (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13    GNU General Public License for more details.
14
15    You should have received a copy of the GNU Lesser General Public
16    License along with this program. If not, see
17    <http://www.gnu.org/licenses/>.
18 */
19
20 #include <stdlib.h>
21 #include <stddef.h>
22 #include <assert.h>
23
24 #include "ez-set.h"
25
26 /**
27  * Pretty much a traditional chained hash table implementation.  I've
28  * experimented with a few variations but as a general purpose table
29  * this is always competetive at worst.
30  */
31
32 static void *scan_next_chain(ez_set *h, ez_set_scan *scan, int idx) __attribute__((noinline));
33 static void set_rehash(ez_set *h, int newsize) __attribute__((noinline));
34
35 /**
36  * Lookup an entry.
37  *
38  * Find the entry and return the previous node in the bucket chain.
39  * The previous node may be en entry in table.
40  *
41  * @param key key to lookup.
42  * @param pp return for the parent pointer.  This will
43  * be a pointer to the table entry if the chain is empty.
44  * @return an entry if found.
45  */
46 static ez_node *set_lookup(ez_set *h, const ez_node *key, unsigned int hash, ez_node **pp) {
47         unsigned int idx = hash & h->mask;
48         ez_node *scan = h->table[idx];
49         ez_node *p = (ez_node *)&h->table[idx];
50
51         while (scan && !(hash == scan->u.set.hash && h->equals(key, scan))) {
52                 p = scan;
53                 scan = scan->u.set.next;
54         }
55         *pp = p;
56
57         return scan;
58 }
59
60 /**
61  * Rehash the table to a new size.
62  *
63  * This cannot fail.  If the memory allocation fails for the table it
64  * just does nothing and the set will still function mayhaps with
65  * degraded performance.
66  */
67 static void set_rehash(ez_set *h, int newsize) {
68         ez_node **table = calloc(sizeof(*table), newsize);
69         unsigned int mask = newsize - 1;
70
71         if (!table)
72                 return;
73
74         // Move all entries to the new table
75         for (int i=0;i<=h->mask;i++) {
76                 ez_node *e = h->table[i];
77
78                 while (e) {
79                         ez_node *n = e->u.set.next;
80                         unsigned int nidx = e->u.set.hash & mask;
81
82                         e->u.set.next = table[nidx];
83                         table[nidx] = e;
84
85                         e = n;
86                 }
87         }
88
89         // update table
90         free(h->table);
91         h->table = table;
92         h->mask = mask;
93 }
94
95 /**
96  * Find the next non-empty chain.
97  */
98 static void *scan_next_chain(ez_set *h, ez_set_scan *scan, int idx) {
99         ez_node *e = NULL;
100
101         while (e == NULL && idx <= h->mask)
102                 e = h->table[idx++];
103
104         scan->e = e;
105         scan->idx = idx;
106         scan->p = e ? (struct ez_node *)&h->table[idx-1] : NULL;
107
108         return e;
109 }
110
111 /* ********************************************************************** */
112 /* Main api */
113
114 void ez_set_init(ez_set *h, unsigned int (*hash)(const void *), int (*equals)(const void *, const void *), void (*efree)(void *)) {
115         h->table = NULL;
116         h->mask = 0;
117         h->count = 0;
118         h->hash = hash;
119         h->equals = equals;
120         h->free = efree;
121 }
122
123 void ez_set_clear(ez_set *h) {
124         if (h->mask) {
125                 for (int i=0;i<=h->mask;i++) {
126                         ez_node *e = h->table[i];
127
128                         while (e) {
129                                 ez_node *n = ez_node_next(e);
130                                 if (h->free)
131                                         h->free(e);
132                                 e = n;
133                         }
134                         h->table[i] = NULL;
135                 }
136                 free(h->table);
137                 h->table = NULL;
138                 h->mask = 0;
139                 h->count = 0;
140         }
141 }
142
143 int ez_set_size(ez_set *h) {
144         return h->count;
145 }
146
147 void *ez_set_put(ez_set *h, void *ep) {
148         ez_node *e = ep, *scan, *p;
149
150         if (h->mask == 0) {
151                 h->table = calloc(sizeof(*h->table), 16);
152                 if (!h->table)
153                         return ep;
154                 h->mask = 15;
155         }
156
157         // Entries are only ever hashed once, here.
158         e->u.set.hash = h->hash(e);
159         scan = set_lookup(h, e, e->u.set.hash, &p);
160
161         // insert new node, possibly unlinking old one
162         p->u.set.next = e;
163         if (scan) {
164                 // link old node tail
165                 e->u.set.next = scan->u.set.next;
166         } else {
167                 // new node added
168                 e->u.set.next = NULL;
169                 h->count += 1;
170                 if (h->count > h->mask)
171                         set_rehash(h, (h->mask+1) * 2);
172         }
173
174         return scan;
175 }
176
177 void *ez_set_get(ez_set *h, const void *ep) {
178         const struct ez_node *e = ep;
179         struct ez_node *p;
180         unsigned int hash;
181
182         if (h->mask == 0) return NULL;
183
184         hash = ez_set_node_hash(h, e);
185
186         return set_lookup(h, e, hash, &p);
187 }
188
189 void *ez_set_remove(ez_set *h, const void *ep) {
190         const ez_node *e = ep;
191         struct ez_node *scan, *p;
192         unsigned int hash;
193
194         if (h->mask == 0) return NULL;
195
196         hash = ez_set_node_hash(h, e);
197         scan = set_lookup(h, e, hash, &p);
198         if (scan) {
199                 // unlink old node
200                 p->u.set.next = scan->u.set.next;
201                 h->count -= 1;
202                 if (h->mask > 15 && h->count*2 < h->mask)
203                         set_rehash(h, (h->mask+1)>>1);
204         }
205
206         return scan;
207 }
208
209 /* ********************************************************************** */
210 /* Set iterator */
211
212 void *ez_set_scan_init(ez_set *h, ez_set_scan *scan) {
213         if (h->mask == 0) return NULL;
214
215         scan->set = h;
216         scan_next_chain(h, scan, 0);
217
218         return scan->e;
219 }
220
221 void *ez_set_scan_next(ez_set_scan *scan) {
222         if (scan->e) {
223                 // advance e and p
224                 scan->p = scan->e;
225                 scan->e = scan->e->u.set.next;
226
227                 if (!scan->e)
228                         return scan_next_chain(scan->set, scan, scan->idx);
229         }
230
231         return scan->e;
232 }
233
234 void *ez_set_scan_remove(ez_set_scan *scan) {
235         if (scan->e) {
236                 // unlink e and advance but don't change p
237                 scan->p->u.set.next = scan->e = scan->e->u.set.next;
238                 scan->set->count -= 1;
239
240                 if (!scan->e)
241                         return scan_next_chain(scan->set, scan, scan->idx);
242         }
243
244         return scan->e;
245 }
246
247 /* ********************************************************************** */
248 /* App helpers */
249
250 /*
251  * Some hash functions.
252  *
253  * It's all a bit arbitrary in my experience and almost anything
254  * reasonable works well enough so long as you avoid really poor ones
255  * like `(int32_t)(intptr_t)pointer' or sum(char[]).
256  */
257
258 // http://www.cse.yorku.ca/~oz/hash.html
259 //  djb2
260 // Use the multiplier here and let the compiler shift-ize if it that's faster.
261 unsigned int ez_hash_string(const char *s) {
262         unsigned int hash = 5381;
263
264         while (*s)
265                 //hash = (*s++) + (hash << 5) + hash;
266                 hash = hash * 33 + (*s++);
267
268         return hash;
269 }
270
271 // http://www.cse.yorku.ca/~oz/hash.html
272 //  sdbm, used in berkeley db
273 // Use the multiplier here and let the compiler shift-ize if it that's faster.
274 unsigned int ez_hash_array(const void *sp, size_t size) {
275         unsigned int hash = 0;
276         const unsigned char *s = sp;
277         const unsigned char *se = s + size;
278
279         while (s < se)
280                 //hash = (*s++) + (hash << 6) + (hash << 16) - hash;
281                 hash = hash * 65599 + (*s++);
282
283         return hash;
284 }
285
286 // https://www.burtleburtle.net/bob/hash/integer.html
287 //  'Thomas Wang's function'
288 // TBH fuck knows, an unbiased 32-bit reversible hash isn't necessarily
289 // great for a power of 2 hash table index.
290 unsigned int ez_hash_int32(uint32_t a) {
291         a += ~(a<<15);
292         a ^=  (a>>10);
293         a +=  (a<<3);
294         a ^=  (a>>6);
295         a += ~(a<<11);
296         a ^=  (a>>16);
297         return a;
298 }
299
300 unsigned int ez_hash_int64(uint64_t x) {
301         return ez_hash_int32(x ^ (x>>32));
302 }
303
304 unsigned int ez_hash_ptr(void *v) {
305         if (sizeof(v) == 8)
306                 return ez_hash_int64((intptr_t)v);
307         else
308                 return ez_hash_int32((intptr_t)v);
309 }