Logo Search packages:      
Sourcecode: yasm version File versions  Download package

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: hamt.c 1137 2004-09-04 01:24:57Z peter $");

#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 *
00089 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
00125 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
00147 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 *
00160 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 *
00313 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];
    }
}


Generated by  Doxygen 1.6.0   Back to index