1 /*
2 * Hash Array Mapped Trie (HAMT) implementation
3 *
4 * Copyright (C) 2001-2007 Peter Johnson
5 *
6 * Based on the paper "Ideal Hash Tries" by Phil Bagwell [2000].
7 * One algorithmic change from that described in the paper: we use the LSB's
8 * of the key to index the root table and move upward in the key rather than
9 * use the MSBs as described in the paper. The LSBs have more entropy.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND OTHER CONTRIBUTORS ``AS IS''
21 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR OTHER CONTRIBUTORS BE
24 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 * POSSIBILITY OF SUCH DAMAGE.
31 */
32 #include "util.h"
33
34 #include <ctype.h>
35
36 #include "libyasm-stdint.h"
37 #include "coretype.h"
38 #include "hamt.h"
39
40 struct HAMTEntry {
41 STAILQ_ENTRY(HAMTEntry) next; /* next hash table entry */
42 /*@dependent@*/ const char *str; /* string being hashed */
43 /*@owned@*/ void *data; /* data pointer being stored */
44 };
45
46 typedef struct HAMTNode {
47 unsigned long BitMapKey; /* 32 bits, bitmap or hash key */
48 uintptr_t BaseValue; /* Base of HAMTNode list or value */
49 } HAMTNode;
50
51 struct HAMT {
52 STAILQ_HEAD(HAMTEntryHead, HAMTEntry) entries;
53 HAMTNode *root;
54 /*@exits@*/ void (*error_func) (const char *file, unsigned int line,
55 const char *message);
56 unsigned long (*HashKey) (const char *key);
57 unsigned long (*ReHashKey) (const char *key, int Level);
58 int (*CmpKey) (const char *s1, const char *s2);
59 };
60
61 /* XXX make a portable version of this. This depends on the pointer being
62 * 4 or 2-byte aligned (as it uses the LSB of the pointer variable to store
63 * the subtrie flag!
64 */
65 #define IsSubTrie(n) ((n)->BaseValue & 1)
66 #define SetSubTrie(h, n, v) do { \
67 if ((uintptr_t)(v) & 1) \
68 h->error_func(__FILE__, __LINE__, \
69 N_("Subtrie is seen as subtrie before flag is set (misaligned?)")); \
70 (n)->BaseValue = (uintptr_t)(v) | 1; \
71 } while (0)
72 #define SetValue(h, n, v) do { \
73 if ((uintptr_t)(v) & 1) \
74 h->error_func(__FILE__, __LINE__, \
75 N_("Value is seen as subtrie (misaligned?)")); \
76 (n)->BaseValue = (uintptr_t)(v); \
77 } while (0)
78 #define GetSubTrie(n) (HAMTNode *)(((n)->BaseValue | 1) ^ 1)
79
80 static unsigned long
HashKey(const char * key)81 HashKey(const char *key)
82 {
83 unsigned long a=31415, b=27183, vHash;
84 for (vHash=0; *key; key++, a*=b)
85 vHash = a*vHash + *key;
86 return vHash;
87 }
88
89 static unsigned long
ReHashKey(const char * key,int Level)90 ReHashKey(const char *key, int Level)
91 {
92 unsigned long a=31415, b=27183, vHash;
93 for (vHash=0; *key; key++, a*=b)
94 vHash = a*vHash*(unsigned long)Level + *key;
95 return vHash;
96 }
97
98 static unsigned long
HashKey_nocase(const char * key)99 HashKey_nocase(const char *key)
100 {
101 unsigned long a=31415, b=27183, vHash;
102 for (vHash=0; *key; key++, a*=b)
103 vHash = a*vHash + tolower(*key);
104 return vHash;
105 }
106
107 static unsigned long
ReHashKey_nocase(const char * key,int Level)108 ReHashKey_nocase(const char *key, int Level)
109 {
110 unsigned long a=31415, b=27183, vHash;
111 for (vHash=0; *key; key++, a*=b)
112 vHash = a*vHash*(unsigned long)Level + tolower(*key);
113 return vHash;
114 }
115
116 HAMT *
HAMT_create(int nocase,void (* error_func)(const char * file,unsigned int line,const char * message))117 HAMT_create(int nocase, /*@exits@*/ void (*error_func)
118 (const char *file, unsigned int line, const char *message))
119 {
120 /*@out@*/ HAMT *hamt = yasm_xmalloc(sizeof(HAMT));
121 int i;
122
123 STAILQ_INIT(&hamt->entries);
124 hamt->root = yasm_xmalloc(32*sizeof(HAMTNode));
125
126 for (i=0; i<32; i++) {
127 hamt->root[i].BitMapKey = 0;
128 hamt->root[i].BaseValue = 0;
129 }
130
131 hamt->error_func = error_func;
132 if (nocase) {
133 hamt->HashKey = HashKey_nocase;
134 hamt->ReHashKey = ReHashKey_nocase;
135 hamt->CmpKey = yasm__strcasecmp;
136 } else {
137 hamt->HashKey = HashKey;
138 hamt->ReHashKey = ReHashKey;
139 hamt->CmpKey = strcmp;
140 }
141
142 return hamt;
143 }
144
145 static void
HAMT_delete_trie(HAMTNode * node)146 HAMT_delete_trie(HAMTNode *node)
147 {
148 if (IsSubTrie(node)) {
149 unsigned long i, Size;
150
151 /* Count total number of bits in bitmap to determine size */
152 BitCount(Size, node->BitMapKey);
153 Size &= 0x1F;
154 if (Size == 0)
155 Size = 32;
156
157 for (i=0; i<Size; i++)
158 HAMT_delete_trie(&(GetSubTrie(node))[i]);
159 yasm_xfree(GetSubTrie(node));
160 }
161 }
162
163 void
HAMT_destroy(HAMT * hamt,void (* deletefunc)(void * data))164 HAMT_destroy(HAMT *hamt, void (*deletefunc) (/*@only@*/ void *data))
165 {
166 int i;
167
168 /* delete entries */
169 while (!STAILQ_EMPTY(&hamt->entries)) {
170 HAMTEntry *entry;
171 entry = STAILQ_FIRST(&hamt->entries);
172 STAILQ_REMOVE_HEAD(&hamt->entries, next);
173 deletefunc(entry->data);
174 yasm_xfree(entry);
175 }
176
177 /* delete trie */
178 for (i=0; i<32; i++)
179 HAMT_delete_trie(&hamt->root[i]);
180
181 yasm_xfree(hamt->root);
182 yasm_xfree(hamt);
183 }
184
185 int
HAMT_traverse(HAMT * hamt,void * d,int (* func)(void * node,void * d))186 HAMT_traverse(HAMT *hamt, void *d,
187 int (*func) (/*@dependent@*/ /*@null@*/ void *node,
188 /*@null@*/ void *d))
189 {
190 HAMTEntry *entry;
191 STAILQ_FOREACH(entry, &hamt->entries, next) {
192 int retval = func(entry->data, d);
193 if (retval != 0)
194 return retval;
195 }
196 return 0;
197 }
198
199 const HAMTEntry *
HAMT_first(const HAMT * hamt)200 HAMT_first(const HAMT *hamt)
201 {
202 return STAILQ_FIRST(&hamt->entries);
203 }
204
205 const HAMTEntry *
HAMT_next(const HAMTEntry * prev)206 HAMT_next(const HAMTEntry *prev)
207 {
208 return STAILQ_NEXT(prev, next);
209 }
210
211 void *
HAMTEntry_get_data(const HAMTEntry * entry)212 HAMTEntry_get_data(const HAMTEntry *entry)
213 {
214 return entry->data;
215 }
216
217 /*@-temptrans -kepttrans -mustfree@*/
218 void *
HAMT_insert(HAMT * hamt,const char * str,void * data,int * replace,void (* deletefunc)(void * data))219 HAMT_insert(HAMT *hamt, const char *str, void *data, int *replace,
220 void (*deletefunc) (/*@only@*/ void *data))
221 {
222 HAMTNode *node, *newnodes;
223 HAMTEntry *entry;
224 unsigned long key, keypart, Map;
225 int keypartbits = 0;
226 int level = 0;
227
228 key = hamt->HashKey(str);
229 keypart = key & 0x1F;
230 node = &hamt->root[keypart];
231
232 if (!node->BaseValue) {
233 node->BitMapKey = key;
234 entry = yasm_xmalloc(sizeof(HAMTEntry));
235 entry->str = str;
236 entry->data = data;
237 STAILQ_INSERT_TAIL(&hamt->entries, entry, next);
238 SetValue(hamt, node, entry);
239 if (IsSubTrie(node))
240 hamt->error_func(__FILE__, __LINE__,
241 N_("Data is seen as subtrie (misaligned?)"));
242 *replace = 1;
243 return data;
244 }
245
246 for (;;) {
247 if (!(IsSubTrie(node))) {
248 if (node->BitMapKey == key
249 && hamt->CmpKey(((HAMTEntry *)(node->BaseValue))->str,
250 str) == 0) {
251 /*@-branchstate@*/
252 if (*replace) {
253 deletefunc(((HAMTEntry *)(node->BaseValue))->data);
254 ((HAMTEntry *)(node->BaseValue))->str = str;
255 ((HAMTEntry *)(node->BaseValue))->data = data;
256 } else
257 deletefunc(data);
258 /*@=branchstate@*/
259 return ((HAMTEntry *)(node->BaseValue))->data;
260 } else {
261 unsigned long key2 = node->BitMapKey;
262 /* build tree downward until keys differ */
263 for (;;) {
264 unsigned long keypart2;
265
266 /* replace node with subtrie */
267 keypartbits += 5;
268 if (keypartbits > 30) {
269 /* Exceeded 32 bits: rehash */
270 key = hamt->ReHashKey(str, level);
271 key2 = hamt->ReHashKey(
272 ((HAMTEntry *)(node->BaseValue))->str, level);
273 keypartbits = 0;
274 }
275 keypart = (key >> keypartbits) & 0x1F;
276 keypart2 = (key2 >> keypartbits) & 0x1F;
277
278 if (keypart == keypart2) {
279 /* Still equal, build one-node subtrie and continue
280 * downward.
281 */
282 newnodes = yasm_xmalloc(sizeof(HAMTNode));
283 newnodes[0].BitMapKey = key2;
284 newnodes[0].BaseValue = node->BaseValue;
285 node->BitMapKey = 1<<keypart;
286 SetSubTrie(hamt, node, newnodes);
287 node = &newnodes[0];
288 level++;
289 } else {
290 /* partitioned: allocate two-node subtrie */
291 newnodes = yasm_xmalloc(2*sizeof(HAMTNode));
292
293 entry = yasm_xmalloc(sizeof(HAMTEntry));
294 entry->str = str;
295 entry->data = data;
296 STAILQ_INSERT_TAIL(&hamt->entries, entry, next);
297
298 /* Copy nodes into subtrie based on order */
299 if (keypart2 < keypart) {
300 newnodes[0].BitMapKey = key2;
301 newnodes[0].BaseValue = node->BaseValue;
302 newnodes[1].BitMapKey = key;
303 SetValue(hamt, &newnodes[1], entry);
304 } else {
305 newnodes[0].BitMapKey = key;
306 SetValue(hamt, &newnodes[0], entry);
307 newnodes[1].BitMapKey = key2;
308 newnodes[1].BaseValue = node->BaseValue;
309 }
310
311 /* Set bits in bitmap corresponding to keys */
312 node->BitMapKey = (1UL<<keypart) | (1UL<<keypart2);
313 SetSubTrie(hamt, node, newnodes);
314 *replace = 1;
315 return data;
316 }
317 }
318 }
319 }
320
321 /* Subtrie: look up in bitmap */
322 keypartbits += 5;
323 if (keypartbits > 30) {
324 /* Exceeded 32 bits of current key: rehash */
325 key = hamt->ReHashKey(str, level);
326 keypartbits = 0;
327 }
328 keypart = (key >> keypartbits) & 0x1F;
329 if (!(node->BitMapKey & (1<<keypart))) {
330 /* bit is 0 in bitmap -> add node to table */
331 unsigned long Size;
332
333 /* set bit to 1 */
334 node->BitMapKey |= 1<<keypart;
335
336 /* Count total number of bits in bitmap to determine new size */
337 BitCount(Size, node->BitMapKey);
338 Size &= 0x1F;
339 if (Size == 0)
340 Size = 32;
341 newnodes = yasm_xmalloc(Size*sizeof(HAMTNode));
342
343 /* Count bits below to find where to insert new node at */
344 BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
345 Map &= 0x1F; /* Clamp to <32 */
346 /* Copy existing nodes leaving gap for new node */
347 memcpy(newnodes, GetSubTrie(node), Map*sizeof(HAMTNode));
348 memcpy(&newnodes[Map+1], &(GetSubTrie(node))[Map],
349 (Size-Map-1)*sizeof(HAMTNode));
350 /* Delete old subtrie */
351 yasm_xfree(GetSubTrie(node));
352 /* Set up new node */
353 newnodes[Map].BitMapKey = key;
354 entry = yasm_xmalloc(sizeof(HAMTEntry));
355 entry->str = str;
356 entry->data = data;
357 STAILQ_INSERT_TAIL(&hamt->entries, entry, next);
358 SetValue(hamt, &newnodes[Map], entry);
359 SetSubTrie(hamt, node, newnodes);
360
361 *replace = 1;
362 return data;
363 }
364
365 /* Count bits below */
366 BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
367 Map &= 0x1F; /* Clamp to <32 */
368
369 /* Go down a level */
370 level++;
371 node = &(GetSubTrie(node))[Map];
372 }
373 }
374 /*@=temptrans =kepttrans =mustfree@*/
375
376 void *
HAMT_search(HAMT * hamt,const char * str)377 HAMT_search(HAMT *hamt, const char *str)
378 {
379 HAMTNode *node;
380 unsigned long key, keypart, Map;
381 int keypartbits = 0;
382 int level = 0;
383
384 key = hamt->HashKey(str);
385 keypart = key & 0x1F;
386 node = &hamt->root[keypart];
387
388 if (!node->BaseValue)
389 return NULL;
390
391 for (;;) {
392 if (!(IsSubTrie(node))) {
393 if (node->BitMapKey == key
394 && hamt->CmpKey(((HAMTEntry *)(node->BaseValue))->str,
395 str) == 0)
396 return ((HAMTEntry *)(node->BaseValue))->data;
397 else
398 return NULL;
399 }
400
401 /* Subtree: look up in bitmap */
402 keypartbits += 5;
403 if (keypartbits > 30) {
404 /* Exceeded 32 bits of current key: rehash */
405 key = hamt->ReHashKey(str, level);
406 keypartbits = 0;
407 }
408 keypart = (key >> keypartbits) & 0x1F;
409 if (!(node->BitMapKey & (1<<keypart)))
410 return NULL; /* bit is 0 in bitmap -> no match */
411
412 /* Count bits below */
413 BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart));
414 Map &= 0x1F; /* Clamp to <32 */
415
416 /* Go down a level */
417 level++;
418 node = &(GetSubTrie(node))[Map];
419 }
420 }
421
422