hashtable.h

   1 /** @file hashtable.h
   2  *  @brief Hashtable.  Standard chained bucket variety.
   3  */
   4
   5 #ifndef HASHTABLE_H
   6 #define HASHTABLE_H
   7
   8 #include <stdlib.h>
   9 #include <stdio.h>
  10 #include <string.h>
  11 #include "mymemory.h"
  12 #include "common.h"
  13
  14 /**
  15  * @brief HashTable linked node class, for chained storage of hash table conflicts
  16  *
  17  * By default it is snapshotting, but you can pass in your own allocation
  18  * functions.
  19  *
  20  * @tparam _Key    Type name for the key
  21  * @tparam _Val    Type name for the values to be stored
  22  * @tparam _malloc Provide your own 'malloc' for the table, or default to
  23  *                 snapshotting.
  24  * @tparam _calloc Provide your own 'calloc' for the table, or default to
  25  *                 snapshotting.
  26  * @tparam _free   Provide your own 'free' for the table, or default to
  27  *                 snapshotting.
  28  */
  29 template<typename _Key, typename _Val>
  30
  31 struct hashlistnode {
  32         _Key key;
  33         _Val val;
  34 };
  35
  36 /**
  37  * @brief A simple, custom hash table
  38  *
  39  * By default it is snapshotting, but you can pass in your own allocation
  40  * functions. Note that this table does not support 0 (NULL) keys and is
  41  * designed primarily with pointer-based keys in mind.
  42  *
  43  * @tparam _Key    Type name for the key
  44  * @tparam _Val    Type name for the values to be stored
  45  * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
  46  *                 manipulation and storage.
  47  * @tparam _Shift  Logical shift to apply to all keys. Default 0.
  48  * @tparam _malloc Provide your own 'malloc' for the table, or default to
  49  *                 snapshotting.
  50  * @tparam _calloc Provide your own 'calloc' for the table, or default to
  51  *                 snapshotting.
  52  * @tparam _free   Provide your own 'free' for the table, or default to
  53  *                 snapshotting.
  54  */
  55 template<typename _Key, typename _Val, typename _KeyInt, int _Shift = 0, void * (* _malloc)(size_t) = snapshot_malloc, void * (* _calloc)(size_t, size_t) = snapshot_calloc, void (*_free)(void *) = snapshot_free>
  56         class HashTable {
  57  public:
  58         /**
  59          * Constructor
  60          * @param initialcapacity Sets the initial capacity of the hash table.
  61          * Default size 1024.
  62          * @param factor Sets the percentage full before the hashtable is
  63          * resized. Default ratio 0.5.
  64          */
  65         HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
  66                 // Allocate space for the hash table
  67                 table = (struct hashlistnode<_Key, _Val> *)_calloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
  68                 loadfactor = factor;
  69                 capacity = initialcapacity;
  70                 capacitymask = initialcapacity - 1;
  71
  72                 threshold = (unsigned int)(initialcapacity * loadfactor);
  73                 size = 0; // Initial number of elements in the hash
  74         }
  75
  76         /** Destructor */
  77         ~HashTable() {
  78                 _free(table);
  79         }
  80
  81         /** Override: new operator */
  82         void * operator new(size_t size) {
  83                 return _malloc(size);
  84         }
  85
  86         /** Override: delete operator */
  87         void operator delete(void *p, size_t size) {
  88                 _free(p);
  89         }
  90
  91         /** Override: new[] operator */
  92         void * operator new[](size_t size) {
  93                 return _malloc(size);
  94         }
  95
  96         /** Override: delete[] operator */
  97         void operator delete[](void *p, size_t size) {
  98                 _free(p);
  99         }
 100
 101         /** Reset the table to its initial state. */
 102         void reset() {
 103                 memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
 104                 size = 0;
 105         }
 106
 107         /** Put a key value pair into the table. */
 108         void put(_Key key, _Val val) {
 109                 /* HashTable cannot handle 0 as a key */
 110                 ASSERT(key);
 111
 112                 if (size > threshold)
 113                         resize(capacity << 1);
 114
 115                 struct hashlistnode<_Key, _Val> *search;
 116
 117                 unsigned int index = ((_KeyInt)key) >> _Shift;
 118                 do {
 119                         index &= capacitymask;
 120                         search = &table[index];
 121                         if (search->key == key) {
 122                                 search->val = val;
 123                                 return;
 124                         }
 125                         index++;
 126                 } while (search->key);
 127
 128                 search->key = key;
 129                 search->val = val;
 130                 size++;
 131         }
 132
 133         /** Lookup the corresponding value for the given key. */
 134         _Val get(_Key key) const {
 135                 struct hashlistnode<_Key, _Val> *search;
 136
 137                 /* HashTable cannot handle 0 as a key */
 138                 ASSERT(key);
 139
 140                 unsigned int index = ((_KeyInt)key) >> _Shift;
 141                 do {
 142                         index &= capacitymask;
 143                         search = &table[index];
 144                         if (search->key == key)
 145                                 return search->val;
 146                         index++;
 147                 } while (search->key);
 148                 return (_Val)0;
 149         }
 150
 151         /** Check whether the table contains a value for the given key. */
 152         bool contains(_Key key) const {
 153                 struct hashlistnode<_Key, _Val> *search;
 154
 155                 /* HashTable cannot handle 0 as a key */
 156                 ASSERT(key);
 157
 158                 unsigned int index = ((_KeyInt)key) >> _Shift;
 159                 do {
 160                         index &= capacitymask;
 161                         search = &table[index];
 162                         if (search->key == key)
 163                                 return true;
 164                         index++;
 165                 } while (search->key);
 166                 return false;
 167         }
 168
 169         /** Resize the table. */
 170         void resize(unsigned int newsize) {
 171                 struct hashlistnode<_Key, _Val> *oldtable = table;
 172                 struct hashlistnode<_Key, _Val> *newtable;
 173                 unsigned int oldcapacity = capacity;
 174
 175                 if ((newtable = (struct hashlistnode<_Key, _Val> *)_calloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
 176                         model_print("calloc error %s %d\n", __FILE__, __LINE__);
 177                         exit(EXIT_FAILURE);
 178                 }
 179
 180                 table = newtable;          // Update the global hashtable upon resize()
 181                 capacity = newsize;
 182                 capacitymask = newsize - 1;
 183
 184                 threshold = (unsigned int)(newsize * loadfactor);
 185
 186                 struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
 187                 struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
 188                 for (; bin < lastbin; bin++) {
 189                         _Key key = bin->key;
 190
 191                         struct hashlistnode<_Key, _Val> *search;
 192
 193                         unsigned int index = ((_KeyInt)key) >> _Shift;
 194                         do {
 195                                 index &= capacitymask;
 196                                 search = &table[index];
 197                                 index++;
 198                         } while (search->key);
 199
 200                         search->key = key;
 201                         search->val = bin->val;
 202                 }
 203
 204                 _free(oldtable);            // Free the memory of the old hash table
 205         }
 206
 207  private:
 208         struct hashlistnode<_Key, _Val> *table;
 209         unsigned int capacity;
 210         unsigned int size;
 211         unsigned int capacitymask;
 212         unsigned int threshold;
 213         double loadfactor;
 214 };
 215 #endif