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
40struct 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
46typedef 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
51struct 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
80static unsigned long
81HashKey(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
89static unsigned long
90ReHashKey(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
98static unsigned long
99HashKey_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
107static unsigned long
108ReHashKey_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
116HAMT *
117HAMT_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
145static void
146HAMT_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
163void
164HAMT_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
185int
186HAMT_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
199const HAMTEntry *
200HAMT_first(const HAMT *hamt)
201{
202    return STAILQ_FIRST(&hamt->entries);
203}
204
205const HAMTEntry *
206HAMT_next(const HAMTEntry *prev)
207{
208    return STAILQ_NEXT(prev, next);
209}
210
211void *
212HAMTEntry_get_data(const HAMTEntry *entry)
213{
214    return entry->data;
215}
216
217/*@-temptrans -kepttrans -mustfree@*/
218void *
219HAMT_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
376void *
377HAMT_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