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