hamt.c

/*
 * 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"
#include "_stdint.h"			/* for uintptr_t */

typedef struct HAMTEntry {
    STAILQ_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 {
    STAILQ_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)		((uintptr_t)((n)->BaseValue) & 1)
#define SetSubTrie(h, n, v)	do {				\
	if ((uintptr_t)(v) & 1)				\
	    h->error_func(__FILE__, __LINE__,			\
			  N_("Subtrie is seen as subtrie before flag is set (misaligned?)"));	\
	(n)->BaseValue = (void *)((uintptr_t)(v) | 1);	\
    } while (0)
#define GetSubTrie(n)		(HAMTNode *)((uintptr_t)((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;

    STAILQ_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;
	if (Size == 0)
	    Size = 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 (!STAILQ_EMPTY(&hamt->entries)) {
	HAMTEntry *entry;
	entry = STAILQ_FIRST(&hamt->entries);
	STAILQ_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;
    STAILQ_FOREACH(entry, &hamt->entries, next) {
	int retval = func(entry->data, d);
	if (retval != 0)
	    return retval;
    }
    return 0;
}

/*@-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;
	STAILQ_INSERT_TAIL(&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
		&& strcmp(((HAMTEntry *)(node->BaseValue))->str, str) == 0) {
		/*@-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;
			STAILQ_INSERT_TAIL(&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;
	    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;
	    STAILQ_INSERT_TAIL(&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];
    }
}