| /* |
| * Hash Array Mapped Trie (HAMT) implementation |
| * |
| * Copyright (C) 2001 Peter Johnson |
| * |
| * Based on the paper "Ideal Hash Tries" by Phil Bagwell [2000]. |
| * One algorithmic change from that described in the paper: we use the LSB's |
| * of the key to index the root table and move upward in the key rather than |
| * use the MSBs as described in the paper. The LSBs have more entropy. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND OTHER CONTRIBUTORS ``AS IS'' |
| * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR OTHER CONTRIBUTORS BE |
| * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| * POSSIBILITY OF SUCH DAMAGE. |
| */ |
| #define YASM_LIB_INTERNAL |
| #include "util.h" |
| /*@unused@*/ RCSID("$Id$"); |
| |
| #include "coretype.h" |
| #include "hamt.h" |
| |
| typedef struct HAMTEntry { |
| SLIST_ENTRY(HAMTEntry) next; /* next hash table entry */ |
| /*@dependent@*/ const char *str; /* string being hashed */ |
| /*@owned@*/ void *data; /* data pointer being stored */ |
| } HAMTEntry; |
| |
| typedef struct HAMTNode { |
| unsigned long BitMapKey; /* 32 bits, bitmap or hash key */ |
| void *BaseValue; /* Base of HAMTNode list or value */ |
| } HAMTNode; |
| |
| struct HAMT { |
| SLIST_HEAD(HAMTEntryHead, HAMTEntry) entries; |
| HAMTNode *root; |
| /*@exits@*/ void (*error_func) (const char *file, unsigned int line, |
| const char *message); |
| }; |
| |
| /* XXX make a portable version of this. This depends on the pointer being |
| * 4 or 2-byte aligned (as it uses the LSB of the pointer variable to store |
| * the subtrie flag! |
| */ |
| #define IsSubTrie(n) ((unsigned long)((n)->BaseValue) & 1) |
| #define SetSubTrie(h, n, v) do { \ |
| if ((unsigned long)(v) & 1) \ |
| h->error_func(__FILE__, __LINE__, \ |
| N_("Subtrie is seen as subtrie before flag is set (misaligned?)")); \ |
| (n)->BaseValue = (void *)((unsigned long)(v) | 1); \ |
| } while (0) |
| #define GetSubTrie(n) (HAMTNode *)((unsigned long)((n)->BaseValue)&~1UL) |
| |
| static unsigned long |
| HashKey(const char *key) |
| { |
| unsigned long a=31415, b=27183, vHash; |
| for (vHash=0; *key; key++, a*=b) |
| vHash = a*vHash + *key; |
| return vHash; |
| } |
| |
| static unsigned long |
| ReHashKey(const char *key, int Level) |
| { |
| unsigned long a=31415, b=27183, vHash; |
| for (vHash=0; *key; key++, a*=b) |
| vHash = a*vHash*(unsigned long)Level + *key; |
| return vHash; |
| } |
| |
| HAMT * |
| HAMT_create(/*@exits@*/ void (*error_func) |
| (const char *file, unsigned int line, const char *message)) |
| { |
| /*@out@*/ HAMT *hamt = yasm_xmalloc(sizeof(HAMT)); |
| int i; |
| |
| SLIST_INIT(&hamt->entries); |
| hamt->root = yasm_xmalloc(32*sizeof(HAMTNode)); |
| |
| for (i=0; i<32; i++) { |
| hamt->root[i].BitMapKey = 0; |
| hamt->root[i].BaseValue = NULL; |
| } |
| |
| hamt->error_func = error_func; |
| |
| return hamt; |
| } |
| |
| static void |
| HAMT_delete_trie(HAMTNode *node) |
| { |
| if (IsSubTrie(node)) { |
| unsigned long i, Size; |
| |
| /* Count total number of bits in bitmap to determine size */ |
| BitCount(Size, node->BitMapKey); |
| Size &= 0x1F; /* Clamp to <32 */ |
| |
| for (i=0; i<Size; i++) |
| HAMT_delete_trie(&(GetSubTrie(node))[i]); |
| yasm_xfree(GetSubTrie(node)); |
| } |
| } |
| |
| void |
| HAMT_destroy(HAMT *hamt, void (*deletefunc) (/*@only@*/ void *data)) |
| { |
| int i; |
| |
| /* delete entries */ |
| while (!SLIST_EMPTY(&hamt->entries)) { |
| HAMTEntry *entry; |
| entry = SLIST_FIRST(&hamt->entries); |
| SLIST_REMOVE_HEAD(&hamt->entries, next); |
| deletefunc(entry->data); |
| yasm_xfree(entry); |
| } |
| |
| /* delete trie */ |
| for (i=0; i<32; i++) |
| HAMT_delete_trie(&hamt->root[i]); |
| |
| yasm_xfree(hamt->root); |
| yasm_xfree(hamt); |
| } |
| |
| int |
| HAMT_traverse(HAMT *hamt, void *d, |
| int (*func) (/*@dependent@*/ /*@null@*/ void *node, |
| /*@null@*/ void *d)) |
| { |
| HAMTEntry *entry; |
| SLIST_FOREACH(entry, &hamt->entries, next) |
| if (func(entry->data, d) == 0) |
| return 0; |
| return 1; |
| } |
| |
| /*@-temptrans -kepttrans -mustfree@*/ |
| void * |
| HAMT_insert(HAMT *hamt, const char *str, void *data, int *replace, |
| void (*deletefunc) (/*@only@*/ void *data)) |
| { |
| HAMTNode *node, *newnodes; |
| HAMTEntry *entry; |
| unsigned long key, keypart, Map; |
| int keypartbits = 0; |
| int level = 0; |
| |
| key = HashKey(str); |
| keypart = key & 0x1F; |
| node = &hamt->root[keypart]; |
| |
| if (!node->BaseValue) { |
| node->BitMapKey = key; |
| entry = yasm_xmalloc(sizeof(HAMTEntry)); |
| entry->str = str; |
| entry->data = data; |
| SLIST_INSERT_HEAD(&hamt->entries, entry, next); |
| node->BaseValue = entry; |
| if (IsSubTrie(node)) |
| hamt->error_func(__FILE__, __LINE__, |
| N_("Data is seen as subtrie (misaligned?)")); |
| *replace = 1; |
| return data; |
| } |
| |
| for (;;) { |
| if (!(IsSubTrie(node))) { |
| if (node->BitMapKey == key) { |
| /*@-branchstate@*/ |
| if (*replace) { |
| deletefunc(((HAMTEntry *)(node->BaseValue))->data); |
| ((HAMTEntry *)(node->BaseValue))->str = str; |
| ((HAMTEntry *)(node->BaseValue))->data = data; |
| } else |
| deletefunc(data); |
| /*@=branchstate@*/ |
| return ((HAMTEntry *)(node->BaseValue))->data; |
| } else { |
| unsigned long key2 = node->BitMapKey; |
| /* build tree downward until keys differ */ |
| for (;;) { |
| unsigned long keypart2; |
| |
| /* replace node with subtrie */ |
| keypartbits += 5; |
| if (keypartbits > 30) { |
| /* Exceeded 32 bits: rehash */ |
| key = ReHashKey(str, level); |
| key2 = ReHashKey(((HAMTEntry *)(node->BaseValue))->str, |
| level); |
| keypartbits = 0; |
| } |
| keypart = (key >> keypartbits) & 0x1F; |
| keypart2 = (key2 >> keypartbits) & 0x1F; |
| |
| if (keypart == keypart2) { |
| /* Still equal, build one-node subtrie and continue |
| * downward. |
| */ |
| newnodes = yasm_xmalloc(sizeof(HAMTNode)); |
| newnodes[0] = *node; /* structure copy */ |
| node->BitMapKey = 1<<keypart; |
| SetSubTrie(hamt, node, newnodes); |
| node = &newnodes[0]; |
| level++; |
| } else { |
| /* partitioned: allocate two-node subtrie */ |
| newnodes = yasm_xmalloc(2*sizeof(HAMTNode)); |
| |
| entry = yasm_xmalloc(sizeof(HAMTEntry)); |
| entry->str = str; |
| entry->data = data; |
| SLIST_INSERT_HEAD(&hamt->entries, entry, next); |
| |
| /* Copy nodes into subtrie based on order */ |
| if (keypart2 < keypart) { |
| newnodes[0] = *node; /* structure copy */ |
| newnodes[1].BitMapKey = key; |
| newnodes[1].BaseValue = entry; |
| } else { |
| newnodes[0].BitMapKey = key; |
| newnodes[0].BaseValue = entry; |
| newnodes[1] = *node; /* structure copy */ |
| } |
| |
| /* Set bits in bitmap corresponding to keys */ |
| node->BitMapKey = (1UL<<keypart) | (1UL<<keypart2); |
| SetSubTrie(hamt, node, newnodes); |
| *replace = 1; |
| return data; |
| } |
| } |
| } |
| } |
| |
| /* Subtrie: look up in bitmap */ |
| keypartbits += 5; |
| if (keypartbits > 30) { |
| /* Exceeded 32 bits of current key: rehash */ |
| key = ReHashKey(str, level); |
| keypartbits = 0; |
| } |
| keypart = (key >> keypartbits) & 0x1F; |
| if (!(node->BitMapKey & (1<<keypart))) { |
| /* bit is 0 in bitmap -> add node to table */ |
| unsigned long Size; |
| |
| /* set bit to 1 */ |
| node->BitMapKey |= 1<<keypart; |
| |
| /* Count total number of bits in bitmap to determine new size */ |
| BitCount(Size, node->BitMapKey); |
| Size &= 0x1F; /* Clamp to <=32 */ |
| if (Size == 0) |
| Size = 32; |
| newnodes = yasm_xmalloc(Size*sizeof(HAMTNode)); |
| |
| /* Count bits below to find where to insert new node at */ |
| BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart)); |
| Map &= 0x1F; /* Clamp to <32 */ |
| /* Copy existing nodes leaving gap for new node */ |
| memcpy(newnodes, GetSubTrie(node), Map*sizeof(HAMTNode)); |
| memcpy(&newnodes[Map+1], &(GetSubTrie(node))[Map], |
| (Size-Map-1)*sizeof(HAMTNode)); |
| /* Delete old subtrie */ |
| yasm_xfree(GetSubTrie(node)); |
| /* Set up new node */ |
| newnodes[Map].BitMapKey = key; |
| entry = yasm_xmalloc(sizeof(HAMTEntry)); |
| entry->str = str; |
| entry->data = data; |
| SLIST_INSERT_HEAD(&hamt->entries, entry, next); |
| newnodes[Map].BaseValue = entry; |
| SetSubTrie(hamt, node, newnodes); |
| |
| *replace = 1; |
| return data; |
| } |
| |
| /* Count bits below */ |
| BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart)); |
| Map &= 0x1F; /* Clamp to <32 */ |
| |
| /* Go down a level */ |
| level++; |
| node = &(GetSubTrie(node))[Map]; |
| } |
| } |
| /*@=temptrans =kepttrans =mustfree@*/ |
| |
| void * |
| HAMT_search(HAMT *hamt, const char *str) |
| { |
| HAMTNode *node; |
| unsigned long key, keypart, Map; |
| int keypartbits = 0; |
| int level = 0; |
| |
| key = HashKey(str); |
| keypart = key & 0x1F; |
| node = &hamt->root[keypart]; |
| |
| if (!node->BaseValue) |
| return NULL; |
| |
| for (;;) { |
| if (!(IsSubTrie(node))) { |
| if (node->BitMapKey == key) |
| return ((HAMTEntry *)(node->BaseValue))->data; |
| else |
| return NULL; |
| } |
| |
| /* Subtree: look up in bitmap */ |
| keypartbits += 5; |
| if (keypartbits > 30) { |
| /* Exceeded 32 bits of current key: rehash */ |
| key = ReHashKey(str, level); |
| keypartbits = 0; |
| } |
| keypart = (key >> keypartbits) & 0x1F; |
| if (!(node->BitMapKey & (1<<keypart))) |
| return NULL; /* bit is 0 in bitmap -> no match */ |
| |
| /* Count bits below */ |
| BitCount(Map, node->BitMapKey & ~((~0UL)<<keypart)); |
| Map &= 0x1F; /* Clamp to <32 */ |
| |
| /* Go down a level */ |
| level++; |
| node = &(GetSubTrie(node))[Map]; |
| } |
| } |
| |