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 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 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 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 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 * 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 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 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 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 * 200 HAMT_first(const HAMT *hamt) 201 { 202 return STAILQ_FIRST(&hamt->entries); 203 } 204 205 const HAMTEntry * 206 HAMT_next(const HAMTEntry *prev) 207 { 208 return STAILQ_NEXT(prev, next); 209 } 210 211 void * 212 HAMTEntry_get_data(const HAMTEntry *entry) 213 { 214 return entry->data; 215 } 216 217 /*@-temptrans -kepttrans -mustfree@*/ 218 void * 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 * 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
