hashtbl.c

   1 /*
   2  * hashtbl.c
   3  *
   4  * Efficient dictionary hash table class.
   5  */
   6
   7 #include "compiler.h"
   8
   9 #include <inttypes.h>
  10 #include <string.h>
  11 #include "nasm.h"
  12 #include "hashtbl.h"
  13
  14 #define HASH_MAX_LOAD           2 /* Higher = more memory-efficient, slower */
  15
  16 static struct hash_tbl_node *alloc_table(size_t newsize)
  17 {
  18     size_t bytes = newsize*sizeof(struct hash_tbl_node);
  19     struct hash_tbl_node *newtbl = nasm_zalloc(bytes);
  20
  21     return newtbl;
  22 }
  23
  24 void hash_init(struct hash_table *head, size_t size)
  25 {
  26     head->table    = alloc_table(size);
  27     head->load     = 0;
  28     head->size     = size;
  29     head->max_load = size*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
  30 }
  31
  32 /*
  33  * Find an entry in a hash table.
  34  *
  35  * On failure, if "insert" is non-NULL, store data in that structure
  36  * which can be used to insert that node using hash_add().
  37  *
  38  * WARNING: this data is only valid until the very next call of
  39  * hash_add(); it cannot be "saved" to a later date.
  40  *
  41  * On success, return a pointer to the "data" element of the hash
  42  * structure.
  43  */
  44 void **hash_find(struct hash_table *head, const char *key,
  45                 struct hash_insert *insert)
  46 {
  47     struct hash_tbl_node *np;
  48     uint64_t hash = crc64(CRC64_INIT, key);
  49     struct hash_tbl_node *tbl = head->table;
  50     size_t mask = head->size-1;
  51     size_t pos  = hash & mask;
  52     size_t inc  = ((hash >> 32) & mask) | 1;    /* Always odd */
  53
  54     while ((np = &tbl[pos])->key) {
  55         if (hash == np->hash && !strcmp(key, np->key))
  56             return &np->data;
  57         pos = (pos+inc) & mask;
  58     }
  59
  60     /* Not found.  Store info for insert if requested. */
  61     if (insert) {
  62         insert->head  = head;
  63         insert->hash  = hash;
  64         insert->where = np;
  65     }
  66     return NULL;
  67 }
  68
  69 /*
  70  * Same as hash_find, but for case-insensitive hashing.
  71  */
  72 void **hash_findi(struct hash_table *head, const char *key,
  73                   struct hash_insert *insert)
  74 {
  75     struct hash_tbl_node *np;
  76     uint64_t hash = crc64i(CRC64_INIT, key);
  77     struct hash_tbl_node *tbl = head->table;
  78     size_t mask = head->size-1;
  79     size_t pos  = hash & mask;
  80     size_t inc  = ((hash >> 32) & mask) | 1;    /* Always odd */
  81
  82     while ((np = &tbl[pos])->key) {
  83         if (hash == np->hash && !nasm_stricmp(key, np->key))
  84             return &np->data;
  85         pos = (pos+inc) & mask;
  86     }
  87
  88     /* Not found.  Store info for insert if requested. */
  89     if (insert) {
  90         insert->head  = head;
  91         insert->hash  = hash;
  92         insert->where = np;
  93     }
  94     return NULL;
  95 }
  96
  97 /*
  98  * Insert node.  Return a pointer to the "data" element of the newly
  99  * created hash node.
 100  */
 101 void **hash_add(struct hash_insert *insert, const char *key, void *data)
 102 {
 103     struct hash_table *head  = insert->head;
 104     struct hash_tbl_node *np = insert->where;
 105
 106     /* Insert node.  We can always do this, even if we need to
 107        rebalance immediately after. */
 108     np->hash = insert->hash;
 109     np->key  = key;
 110     np->data = data;
 111
 112     if (++head->load > head->max_load) {
 113         /* Need to expand the table */
 114         size_t newsize = head->size << 1;
 115         struct hash_tbl_node *newtbl = alloc_table(newsize);
 116         size_t mask = newsize-1;
 117
 118         if (head->table) {
 119             struct hash_tbl_node *op, *xp;
 120             size_t i;
 121
 122             /* Rebalance all the entries */
 123             for (i = 0, op = head->table; i < head->size; i++, op++) {
 124                 if (op->key) {
 125                     size_t pos = op->hash & mask;
 126                     size_t inc = ((op->hash >> 32) & mask) | 1;
 127
 128                     while ((xp = &newtbl[pos])->key)
 129                         pos = (pos+inc) & mask;
 130
 131                     *xp = *op;
 132                     if (op == np)
 133                         np = xp;
 134                 }
 135             }
 136             nasm_free(head->table);
 137         }
 138
 139         head->table    = newtbl;
 140         head->size     = newsize;
 141         head->max_load = newsize*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
 142     }
 143
 144     return &np->data;
 145 }
 146
 147 /*
 148  * Iterate over all members of a hash set.  For the first call,
 149  * iterator should be initialized to NULL.  Returns the data pointer,
 150  * or NULL on failure.
 151  */
 152 void *hash_iterate(const struct hash_table *head,
 153                    struct hash_tbl_node **iterator,
 154                    const char **key)
 155 {
 156     struct hash_tbl_node *np = *iterator;
 157     struct hash_tbl_node *ep = head->table + head->size;
 158
 159     if (!np)
 160         np = head->table;
 161
 162     while (np < ep) {
 163         if (np->key) {
 164             *iterator = np+1;
 165             if (key)
 166                 *key = np->key;
 167             return np->data;
 168         }
 169         np++;
 170     }
 171
 172     *iterator = NULL;
 173     if (key)
 174         *key = NULL;
 175     return NULL;
 176 }
 177
 178 /*
 179  * Free the hash itself.  Doesn't free the data elements; use
 180  * hash_iterate() to do that first, if needed.
 181  */
 182 void hash_free(struct hash_table *head)
 183 {
 184     void *p = head->table;
 185     head->table = NULL;
 186     nasm_free(p);
 187 }