1 /* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
2
3 #include "hashtable.h"
4 #include <stdlib.h>
5 #include <stdio.h>
6 #include <string.h>
7 #include <math.h>
8 #include <stdint.h>
9 #include <stdarg.h>
10 #include "talloc.h"
11
12 struct entry
13 {
14 const void *k;
15 void *v;
16 unsigned int h;
17 struct entry *next;
18 };
19
20 struct hashtable {
21 unsigned int tablelength;
22 unsigned int flags;
23 struct entry **table;
24 unsigned int entrycount;
25 unsigned int loadlimit;
26 unsigned int primeindex;
27 unsigned int (*hashfn) (const void *k);
28 int (*eqfn) (const void *k1, const void *k2);
29 };
30
31 /*
32 * Credit for primes table: Aaron Krowne
33 * https://planetmath.org/goodhashtableprimes
34 */
35 static const unsigned int primes[] = {
36 11, 23, 53, 97, 193, 389,
37 769, 1543, 3079, 6151,
38 12289, 24593, 49157, 98317,
39 196613, 393241, 786433, 1572869,
40 3145739, 6291469, 12582917, 25165843,
41 50331653, 100663319, 201326611, 402653189,
42 805306457, 1610612741
43 };
44
45 #define PRIME_TABLE_LEN ARRAY_SIZE(primes)
46 #define MAX_LOAD_PERCENT 65
47
indexFor(unsigned int tablelength,unsigned int hashvalue)48 static inline unsigned int indexFor(unsigned int tablelength,
49 unsigned int hashvalue)
50 {
51 return (hashvalue % tablelength);
52 }
53
loadlimit(unsigned int pindex)54 static unsigned int loadlimit(unsigned int pindex)
55 {
56 return ((uint64_t)primes[pindex] * MAX_LOAD_PERCENT) / 100;
57 }
58
create_hashtable(const void * ctx,const char * name,unsigned int (* hashf)(const void *),int (* eqf)(const void *,const void *),unsigned int flags)59 struct hashtable *create_hashtable(const void *ctx, const char *name,
60 unsigned int (*hashf) (const void *),
61 int (*eqf) (const void *, const void *),
62 unsigned int flags)
63 {
64 struct hashtable *h;
65
66 h = talloc_zero(ctx, struct hashtable);
67 if (NULL == h)
68 goto err0;
69 talloc_set_name_const(h, name);
70 h->table = talloc_zero_array(h, struct entry *, primes[0]);
71 if (NULL == h->table)
72 goto err1;
73
74 h->primeindex = 0;
75 h->tablelength = primes[h->primeindex];
76 h->flags = flags;
77 h->entrycount = 0;
78 h->hashfn = hashf;
79 h->eqfn = eqf;
80 h->loadlimit = loadlimit(h->primeindex);
81 return h;
82
83 err1:
84 talloc_free(h);
85 err0:
86 return NULL;
87 }
88
hash(const struct hashtable * h,const void * k)89 static unsigned int hash(const struct hashtable *h, const void *k)
90 {
91 /* Aim to protect against poor hash functions by adding logic here
92 * - logic taken from java 1.4 hashtable source */
93 unsigned int i = h->hashfn(k);
94 i += ~(i << 9);
95 i ^= ((i >> 14) | (i << 18)); /* >>> */
96 i += (i << 4);
97 i ^= ((i >> 10) | (i << 22)); /* >>> */
98 return i;
99 }
100
hashtable_expand(struct hashtable * h)101 static int hashtable_expand(struct hashtable *h)
102 {
103 /* Double the size of the table to accomodate more entries */
104 struct entry **newtable;
105 struct entry *e;
106 struct entry **pE;
107 unsigned int newsize, i, index;
108 /* Check we're not hitting max capacity */
109 if (h->primeindex == (PRIME_TABLE_LEN - 1))
110 return ENOSPC;
111 newsize = primes[++(h->primeindex)];
112
113 newtable = talloc_realloc(h, h->table, struct entry *, newsize);
114 if (!newtable)
115 {
116 h->primeindex--;
117 return ENOMEM;
118 }
119
120 h->table = newtable;
121 memset(newtable + h->tablelength, 0,
122 (newsize - h->tablelength) * sizeof(*newtable));
123 for (i = 0; i < h->tablelength; i++) {
124 for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
125 index = indexFor(newsize, e->h);
126 if (index == i)
127 {
128 pE = &(e->next);
129 }
130 else
131 {
132 *pE = e->next;
133 e->next = newtable[index];
134 newtable[index] = e;
135 }
136 }
137 }
138
139 h->tablelength = newsize;
140 h->loadlimit = loadlimit(h->primeindex);
141 return 0;
142 }
143
hashtable_search_entry(const struct hashtable * h,const void * k)144 static struct entry *hashtable_search_entry(const struct hashtable *h,
145 const void *k)
146 {
147 struct entry *e;
148 unsigned int hashvalue, index;
149
150 hashvalue = hash(h, k);
151 index = indexFor(h->tablelength, hashvalue);
152 e = h->table[index];
153
154 for (e = h->table[index]; e; e = e->next)
155 {
156 /* Check hash value to short circuit heavier comparison */
157 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
158 return e;
159 }
160
161 return NULL;
162 }
163
hashtable_add(struct hashtable * h,const void * k,void * v)164 int hashtable_add(struct hashtable *h, const void *k, void *v)
165 {
166 unsigned int index;
167 struct entry *e;
168
169 if (hashtable_search_entry(h, k))
170 return EEXIST;
171
172 if (++(h->entrycount) > h->loadlimit)
173 {
174 /* Ignore the return value. If expand fails, we should
175 * still try cramming just this value into the existing table
176 * -- we may not have memory for a larger table, but one more
177 * element may be ok. Next time we insert, we'll try expanding again.*/
178 hashtable_expand(h);
179 }
180 e = talloc_zero(h, struct entry);
181 if (NULL == e)
182 {
183 --h->entrycount;
184 return ENOMEM;
185 }
186 e->h = hash(h,k);
187 index = indexFor(h->tablelength,e->h);
188 e->k = k;
189 if (h->flags & HASHTABLE_FREE_KEY)
190 talloc_steal(e, k);
191 e->v = v;
192 if (h->flags & HASHTABLE_FREE_VALUE)
193 talloc_steal(e, v);
194 e->next = h->table[index];
195 h->table[index] = e;
196 return 0;
197 }
198
hashtable_search(const struct hashtable * h,const void * k)199 void *hashtable_search(const struct hashtable *h, const void *k)
200 {
201 struct entry *e;
202
203 e = hashtable_search_entry(h, k);
204
205 return e ? e->v : NULL;
206 }
207
hashtable_replace(struct hashtable * h,const void * k,void * v)208 int hashtable_replace(struct hashtable *h, const void *k, void *v)
209 {
210 struct entry *e;
211
212 e = hashtable_search_entry(h, k);
213 if (!e)
214 return ENOENT;
215
216 if (h->flags & HASHTABLE_FREE_VALUE)
217 {
218 talloc_free(e->v);
219 talloc_steal(e, v);
220 }
221
222 e->v = v;
223
224 return 0;
225 }
226
227 void
hashtable_remove(struct hashtable * h,const void * k)228 hashtable_remove(struct hashtable *h, const void *k)
229 {
230 /* TODO: consider compacting the table when the load factor drops enough,
231 * or provide a 'compact' method. */
232
233 struct entry *e;
234 struct entry **pE;
235 unsigned int hashvalue, index;
236
237 hashvalue = hash(h,k);
238 index = indexFor(h->tablelength,hash(h,k));
239 pE = &(h->table[index]);
240 e = *pE;
241 while (NULL != e)
242 {
243 /* Check hash value to short circuit heavier comparison */
244 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
245 {
246 *pE = e->next;
247 h->entrycount--;
248 talloc_free(e);
249 return;
250 }
251 pE = &(e->next);
252 e = e->next;
253 }
254 }
255
hashtable_iterate(struct hashtable * h,int (* func)(const void * k,void * v,void * arg),void * arg)256 int hashtable_iterate(struct hashtable *h,
257 int (*func)(const void *k, void *v, void *arg), void *arg)
258 {
259 int ret;
260 unsigned int i;
261 struct entry *e, *f;
262 struct entry **table = h->table;
263
264 for (i = 0; i < h->tablelength; i++)
265 {
266 e = table[i];
267 while (e)
268 {
269 f = e;
270 e = e->next;
271 ret = func(f->k, f->v, arg);
272 if (ret)
273 return ret;
274 }
275 }
276
277 return 0;
278 }
279
hashtable_destroy(struct hashtable * h)280 void hashtable_destroy(struct hashtable *h)
281 {
282 talloc_free(h);
283 }
284
285 /*
286 * Copyright (c) 2002, Christopher Clark
287 * All rights reserved.
288 *
289 * Redistribution and use in source and binary forms, with or without
290 * modification, are permitted provided that the following conditions
291 * are met:
292 *
293 * * Redistributions of source code must retain the above copyright
294 * notice, this list of conditions and the following disclaimer.
295 *
296 * * Redistributions in binary form must reproduce the above copyright
297 * notice, this list of conditions and the following disclaimer in the
298 * documentation and/or other materials provided with the distribution.
299 *
300 * * Neither the name of the original author; nor the names of any contributors
301 * may be used to endorse or promote products derived from this software
302 * without specific prior written permission.
303 *
304 *
305 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
306 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
307 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
308 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
309 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
310 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
311 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
312 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
313 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
314 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
315 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
316 */
317