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 #define hash_calc(key)          crc64(CRC64_INIT, (key))
  50 #define hash_calci(key)         crc64i(CRC64_INIT, (key))
  51 #define hash_max_load(size)     ((size) * (HASH_MAX_LOAD - 1) / HASH_MAX_LOAD)
  52 #define hash_expand(size)       ((size) << 1)
  53 #define hash_mask(size)         ((size) - 1)
  54 #define hash_pos(hash, mask)    ((hash) & (mask))
  55 #define hash_inc(hash, mask)    ((((hash) >> 32) & (mask)) | 1) /* always odd */
  56 #define hash_pos_next(pos, inc, mask) (((pos) + (inc)) & (mask))
  57
  58 static struct hash_tbl_node *alloc_table(size_t newsize)
  59 {
  60     size_t bytes = newsize * sizeof(struct hash_tbl_node);
  61     return nasm_zalloc(bytes);
  62 }
  63
  64 void hash_init(struct hash_table *head, size_t size)
  65 {
  66     nasm_assert(is_power2(size));
  67     head->table    = alloc_table(size);
  68     head->load     = 0;
  69     head->size     = size;
  70     head->max_load = hash_max_load(size);
  71 }
  72
  73 /*
  74  * Find an entry in a hash table.
  75  *
  76  * On failure, if "insert" is non-NULL, store data in that structure
  77  * which can be used to insert that node using hash_add().
  78  *
  79  * WARNING: this data is only valid until the very next call of
  80  * hash_add(); it cannot be "saved" to a later date.
  81  *
  82  * On success, return a pointer to the "data" element of the hash
  83  * structure.
  84  */
  85 void **hash_find(struct hash_table *head, const char *key,
  86                  struct hash_insert *insert)
  87 {
  88     struct hash_tbl_node *np;
  89     struct hash_tbl_node *tbl = head->table;
  90     uint64_t hash = hash_calc(key);
  91     size_t mask = hash_mask(head->size);
  92     size_t pos = hash_pos(hash, mask);
  93     size_t inc = hash_inc(hash, mask);
  94
  95     while ((np = &tbl[pos])->key) {
  96         if (hash == np->hash && !strcmp(key, np->key))
  97             return &np->data;
  98         pos = hash_pos_next(pos, inc, mask);
  99     }
 100
 101     /* Not found.  Store info for insert if requested. */
 102     if (insert) {
 103         insert->head  = head;
 104         insert->hash  = hash;
 105         insert->where = np;
 106     }
 107     return NULL;
 108 }
 109
 110 /*
 111  * Same as hash_find, but for case-insensitive hashing.
 112  */
 113 void **hash_findi(struct hash_table *head, const char *key,
 114                   struct hash_insert *insert)
 115 {
 116     struct hash_tbl_node *np;
 117     struct hash_tbl_node *tbl = head->table;
 118     uint64_t hash = hash_calci(key);
 119     size_t mask = hash_mask(head->size);
 120     size_t pos = hash_pos(hash, mask);
 121     size_t inc = hash_inc(hash, mask);
 122
 123     while ((np = &tbl[pos])->key) {
 124         if (hash == np->hash && !nasm_stricmp(key, np->key))
 125             return &np->data;
 126         pos = hash_pos_next(pos, inc, mask);
 127     }
 128
 129     /* Not found.  Store info for insert if requested. */
 130     if (insert) {
 131         insert->head  = head;
 132         insert->hash  = hash;
 133         insert->where = np;
 134     }
 135     return NULL;
 136 }
 137
 138 /*
 139  * Insert node.  Return a pointer to the "data" element of the newly
 140  * created hash node.
 141  */
 142 void **hash_add(struct hash_insert *insert, const char *key, void *data)
 143 {
 144     struct hash_table *head  = insert->head;
 145     struct hash_tbl_node *np = insert->where;
 146
 147     /*
 148      * Insert node.  We can always do this, even if we need to
 149      * rebalance immediately after.
 150      */
 151     np->hash = insert->hash;
 152     np->key  = key;
 153     np->data = data;
 154
 155     if (++head->load > head->max_load) {
 156         /* Need to expand the table */
 157         size_t newsize                  = hash_expand(head->size);
 158         struct hash_tbl_node *newtbl    = alloc_table(newsize);
 159         size_t mask                     = hash_mask(newsize);
 160
 161         if (head->table) {
 162             struct hash_tbl_node *op, *xp;
 163             size_t i;
 164
 165             /* Rebalance all the entries */
 166             for (i = 0, op = head->table; i < head->size; i++, op++) {
 167                 if (op->key) {
 168                     size_t pos = hash_pos(op->hash, mask);
 169                     size_t inc = hash_inc(op->hash, mask);
 170
 171                     while ((xp = &newtbl[pos])->key)
 172                         pos = hash_pos_next(pos, inc, mask);
 173
 174                     *xp = *op;
 175                     if (op == np)
 176                         np = xp;
 177                 }
 178             }
 179             nasm_free(head->table);
 180         }
 181
 182         head->table    = newtbl;
 183         head->size     = newsize;
 184         head->max_load = hash_max_load(newsize);
 185     }
 186
 187     return &np->data;
 188 }
 189
 190 /*
 191  * Iterate over all members of a hash set.  For the first call,
 192  * iterator should be initialized to NULL.  Returns the data pointer,
 193  * or NULL on failure.
 194  */
 195 void *hash_iterate(const struct hash_table *head,
 196                    struct hash_tbl_node **iterator,
 197                    const char **key)
 198 {
 199     struct hash_tbl_node *np = *iterator;
 200     struct hash_tbl_node *ep = head->table + head->size;
 201
 202     if (!np) {
 203         np = head->table;
 204         if (!np)
 205             return NULL;        /* Uninitialized table */
 206     }
 207
 208     while (np < ep) {
 209         if (np->key) {
 210             *iterator = np + 1;
 211             if (key)
 212                 *key = np->key;
 213             return np->data;
 214         }
 215         np++;
 216     }
 217
 218     *iterator = NULL;
 219     if (key)
 220         *key = NULL;
 221     return NULL;
 222 }
 223
 224 /*
 225  * Free the hash itself.  Doesn't free the data elements; use
 226  * hash_iterate() to do that first, if needed.
 227  */
 228 void hash_free(struct hash_table *head)
 229 {
 230     void *p = head->table;
 231     head->table = NULL;
 232     nasm_free(p);
 233 }