hashtbl.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2009 The NASM Authors - All Rights Reserved
   4  *   See the file AUTHORS included with the NASM distribution for
   5  *   the specific copyright holders.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following
   9  *   conditions are met:
  10  *
  11  *   * Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  *   * Redistributions in binary form must reproduce the above
  14  *     copyright notice, this list of conditions and the following
  15  *     disclaimer in the documentation and/or other materials provided
  16  *     with the distribution.
  17  *
  18  *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  19  *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21  *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28  *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  29  *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  30  *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  *
  32  * ----------------------------------------------------------------------- */
  33
  34 /*
  35  * hashtbl.c
  36  *
  37  * Efficient dictionary hash table class.
  38  */
  39
  40 #include "compiler.h"
  41
  42 #include <inttypes.h>
  43 #include <string.h>
  44 #include "nasm.h"
  45 #include "hashtbl.h"
  46
  47 #define HASH_MAX_LOAD           2 /* Higher = more memory-efficient, slower */
  48
  49 static struct hash_tbl_node *alloc_table(size_t newsize)
  50 {
  51     size_t bytes = newsize*sizeof(struct hash_tbl_node);
  52     struct hash_tbl_node *newtbl = nasm_zalloc(bytes);
  53
  54     return newtbl;
  55 }
  56
  57 void hash_init(struct hash_table *head, size_t size)
  58 {
  59     head->table    = alloc_table(size);
  60     head->load     = 0;
  61     head->size     = size;
  62     head->max_load = size*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
  63 }
  64
  65 /*
  66  * Find an entry in a hash table.
  67  *
  68  * On failure, if "insert" is non-NULL, store data in that structure
  69  * which can be used to insert that node using hash_add().
  70  *
  71  * WARNING: this data is only valid until the very next call of
  72  * hash_add(); it cannot be "saved" to a later date.
  73  *
  74  * On success, return a pointer to the "data" element of the hash
  75  * structure.
  76  */
  77 void **hash_find(struct hash_table *head, const char *key,
  78                 struct hash_insert *insert)
  79 {
  80     struct hash_tbl_node *np;
  81     uint64_t hash = crc64(CRC64_INIT, key);
  82     struct hash_tbl_node *tbl = head->table;
  83     size_t mask = head->size-1;
  84     size_t pos  = hash & mask;
  85     size_t inc  = ((hash >> 32) & mask) | 1;    /* Always odd */
  86
  87     while ((np = &tbl[pos])->key) {
  88         if (hash == np->hash && !strcmp(key, np->key))
  89             return &np->data;
  90         pos = (pos+inc) & mask;
  91     }
  92
  93     /* Not found.  Store info for insert if requested. */
  94     if (insert) {
  95         insert->head  = head;
  96         insert->hash  = hash;
  97         insert->where = np;
  98     }
  99     return NULL;
 100 }
 101
 102 /*
 103  * Same as hash_find, but for case-insensitive hashing.
 104  */
 105 void **hash_findi(struct hash_table *head, const char *key,
 106                   struct hash_insert *insert)
 107 {
 108     struct hash_tbl_node *np;
 109     uint64_t hash = crc64i(CRC64_INIT, key);
 110     struct hash_tbl_node *tbl = head->table;
 111     size_t mask = head->size-1;
 112     size_t pos  = hash & mask;
 113     size_t inc  = ((hash >> 32) & mask) | 1;    /* Always odd */
 114
 115     while ((np = &tbl[pos])->key) {
 116         if (hash == np->hash && !nasm_stricmp(key, np->key))
 117             return &np->data;
 118         pos = (pos+inc) & mask;
 119     }
 120
 121     /* Not found.  Store info for insert if requested. */
 122     if (insert) {
 123         insert->head  = head;
 124         insert->hash  = hash;
 125         insert->where = np;
 126     }
 127     return NULL;
 128 }
 129
 130 /*
 131  * Insert node.  Return a pointer to the "data" element of the newly
 132  * created hash node.
 133  */
 134 void **hash_add(struct hash_insert *insert, const char *key, void *data)
 135 {
 136     struct hash_table *head  = insert->head;
 137     struct hash_tbl_node *np = insert->where;
 138
 139     /* Insert node.  We can always do this, even if we need to
 140        rebalance immediately after. */
 141     np->hash = insert->hash;
 142     np->key  = key;
 143     np->data = data;
 144
 145     if (++head->load > head->max_load) {
 146         /* Need to expand the table */
 147         size_t newsize = head->size << 1;
 148         struct hash_tbl_node *newtbl = alloc_table(newsize);
 149         size_t mask = newsize-1;
 150
 151         if (head->table) {
 152             struct hash_tbl_node *op, *xp;
 153             size_t i;
 154
 155             /* Rebalance all the entries */
 156             for (i = 0, op = head->table; i < head->size; i++, op++) {
 157                 if (op->key) {
 158                     size_t pos = op->hash & mask;
 159                     size_t inc = ((op->hash >> 32) & mask) | 1;
 160
 161                     while ((xp = &newtbl[pos])->key)
 162                         pos = (pos+inc) & mask;
 163
 164                     *xp = *op;
 165                     if (op == np)
 166                         np = xp;
 167                 }
 168             }
 169             nasm_free(head->table);
 170         }
 171
 172         head->table    = newtbl;
 173         head->size     = newsize;
 174         head->max_load = newsize*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
 175     }
 176
 177     return &np->data;
 178 }
 179
 180 /*
 181  * Iterate over all members of a hash set.  For the first call,
 182  * iterator should be initialized to NULL.  Returns the data pointer,
 183  * or NULL on failure.
 184  */
 185 void *hash_iterate(const struct hash_table *head,
 186                    struct hash_tbl_node **iterator,
 187                    const char **key)
 188 {
 189     struct hash_tbl_node *np = *iterator;
 190     struct hash_tbl_node *ep = head->table + head->size;
 191
 192     if (!np) {
 193         np = head->table;
 194         if (!np)
 195             return NULL;        /* Uninitialized table */
 196     }
 197
 198     while (np < ep) {
 199         if (np->key) {
 200             *iterator = np+1;
 201             if (key)
 202                 *key = np->key;
 203             return np->data;
 204         }
 205         np++;
 206     }
 207
 208     *iterator = NULL;
 209     if (key)
 210         *key = NULL;
 211     return NULL;
 212 }
 213
 214 /*
 215  * Free the hash itself.  Doesn't free the data elements; use
 216  * hash_iterate() to do that first, if needed.
 217  */
 218 void hash_free(struct hash_table *head)
 219 {
 220     void *p = head->table;
 221     head->table = NULL;
 222     nasm_free(p);
 223 }