hashtbl.c

   1 /*
   2  * hashtbl.c
   3  *
   4  * Efficient dictionary hash table class.
   5  */
   6
   7 #include <inttypes.h>
   8 #include <string.h>
   9 #include "nasm.h"
  10 #include "hashtbl.h"
  11
  12 #define HASH_INITIAL_SIZE       64
  13 #define HASH_MAX_LOAD           2 /* Higher = more memory-efficient, slower */
  14
  15 static struct hash_tbl_node *alloc_table(size_t newsize)
  16 {
  17     size_t bytes = newsize*sizeof(struct hash_tbl_node);
  18     struct hash_tbl_node *newtbl = nasm_malloc(bytes);
  19
  20     memset(newtbl, 0, bytes);
  21
  22     return newtbl;
  23 }
  24
  25 struct hash_table *hash_init(void)
  26 {
  27     struct hash_table *head = nasm_malloc(sizeof(struct hash_table));
  28
  29     head->table    = alloc_table(HASH_INITIAL_SIZE);
  30     head->load     = 0;
  31     head->size     = HASH_INITIAL_SIZE;
  32     head->max_load = HASH_INITIAL_SIZE*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
  33
  34     return head;
  35 }
  36
  37 /*
  38  * Find an entry in a hash table.
  39  *
  40  * On failure, if "insert" is non-NULL, store data in that structure
  41  * which can be used to insert that node using hash_add().
  42  *
  43  * WARNING: this data is only valid until the very next call of
  44  * hash_add(); it cannot be "saved" to a later date.
  45  */
  46 void *hash_find(struct hash_table *head, const char *key,
  47                 struct hash_insert *insert)
  48 {
  49     struct hash_tbl_node *np;
  50     uint64_t hash = crc64(key);
  51     struct hash_tbl_node *tbl = head->table;
  52     size_t mask = head->size-1;
  53     size_t pos  = hash & mask;
  54     size_t inc  = ((hash >> 32) & mask) | 1;    /* Always odd */
  55
  56     while ((np = &tbl[pos])->key) {
  57         if (hash == np->hash && !strcmp(key, np->key))
  58             return np->data;
  59         pos = (pos+inc) & mask;
  60     }
  61
  62     /* Not found.  Store info for insert if requested. */
  63     if (insert) {
  64         insert->head  = head;
  65         insert->hash  = hash;
  66         insert->where = np;
  67     }
  68     return NULL;
  69 }
  70
  71 /*
  72  * Insert node.
  73  */
  74 void hash_add(struct hash_insert *insert, const char *key, void *data)
  75 {
  76     struct hash_table *head  = insert->head;
  77     struct hash_tbl_node *np = insert->where;
  78
  79     /* Insert node.  We can always do this, even if we need to
  80        rebalance immediately after. */
  81     np->hash = insert->hash;
  82     np->key  = key;
  83     np->data = data;
  84
  85     if (++head->load > head->max_load) {
  86         /* Need to expand the table */
  87         size_t newsize = head->size << 1;
  88         struct hash_tbl_node *newtbl = alloc_table(newsize);
  89         size_t mask = newsize-1;
  90
  91         if (head->table) {
  92             struct hash_tbl_node *op;
  93             size_t i;
  94
  95             /* Rebalance all the entries */
  96             for (i = 0, op = head->table; i < head->size; i++, op++) {
  97                 if (op->key) {
  98                     size_t pos = op->hash & mask;
  99                     size_t inc = ((op->hash >> 32) & mask) | 1;
 100
 101                     while ((np = &newtbl[pos])->data)
 102                         pos = (pos+inc) & mask;
 103
 104                     *np = *op;
 105                 }
 106             }
 107             nasm_free(head->table);
 108         }
 109
 110         head->table    = newtbl;
 111         head->size     = newsize;
 112         head->max_load = newsize*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
 113     }
 114 }
 115
 116 void hash_free(struct hash_table *head, void (*free_func)(char *, void *))
 117 {
 118     size_t i;
 119     struct hash_tbl_node *op;
 120
 121     for (i = 0, op = head->table; i < head->size; i++, op++) {
 122         if (op->key)
 123             free_func((char *)op->key, op->data);
 124     }
 125
 126     nasm_free(head->table);
 127     nasm_free(head);
 128 }