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 "stl-model.h"
  12 #include "mymemory.h"
  13 #include "common.h"
  14
  15 /**
  16  * @brief HashTable node
  17  *
  18  * @tparam _Key    Type name for the key
  19  * @tparam _Val    Type name for the values to be stored
  20  */
  21 template<typename _Key, typename _Val>
  22 struct hashlistnode {
  23         _Key key;
  24         _Val val;
  25 };
  26
  27 /**
  28  * @brief A simple, custom hash table
  29  *
  30  * By default it is snapshotting, but you can pass in your own allocation
  31  * functions. Note that this table does not support the value 0 (NULL) used as
  32  * a key and is designed primarily with pointer-based keys in mind. Other
  33  * primitive key types are supported only for non-zero values.
  34  *
  35  * @tparam _Key    Type name for the key
  36  * @tparam _Val    Type name for the values to be stored
  37  * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
  38  *                 manipulation and storage.
  39  * @tparam _Shift  Logical shift to apply to all keys. Default 0.
  40  * @tparam _malloc Provide your own 'malloc' for the table, or default to
  41  *                 snapshotting.
  42  * @tparam _calloc Provide your own 'calloc' for the table, or default to
  43  *                 snapshotting.
  44  * @tparam _free   Provide your own 'free' for the table, or default to
  45  *                 snapshotting.
  46  */
  47 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>
  48 class HashTable {
  49 public:
  50         /**
  51          * @brief Hash table constructor
  52          * @param initialcapacity Sets the initial capacity of the hash table.
  53          * Default size 1024.
  54          * @param factor Sets the percentage full before the hashtable is
  55          * resized. Default ratio 0.5.
  56          */
  57         HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
  58                 // Allocate space for the hash table
  59                 table = (struct hashlistnode<_Key, _Val> *)_calloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
  60                 keyset = (_Key *)_calloc(initialcapacity, sizeof(_Key));
  61                 keyset_end = keyset;
  62                 loadfactor = factor;
  63                 capacity = initialcapacity;
  64                 capacitymask = initialcapacity - 1;
  65
  66                 threshold = (unsigned int)(initialcapacity * loadfactor);
  67                 size = 0;       // Initial number of elements in the hash
  68         }
  69
  70         /** @brief Hash table destructor */
  71         ~HashTable() {
  72                 _free(table);
  73                 _free(keyset);
  74         }
  75
  76         /** Override: new operator */
  77         void * operator new(size_t size) {
  78                 return _malloc(size);
  79         }
  80
  81         /** Override: delete operator */
  82         void operator delete(void *p, size_t size) {
  83                 _free(p);
  84         }
  85
  86         /** Override: new[] operator */
  87         void * operator new[](size_t size) {
  88                 return _malloc(size);
  89         }
  90
  91         /** Override: delete[] operator */
  92         void operator delete[](void *p, size_t size) {
  93                 _free(p);
  94         }
  95
  96         /** @brief Reset the table to its initial state. */
  97         void reset() {
  98                 memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
  99                 memset(keyset, 0, capacity * sizeof(_Key));
 100                 size = 0;
 101         }
 102
 103         /**
 104          * @brief Put a key/value pair into the table
 105          * @param key The key for the new value; must not be 0 or NULL
 106          * @param val The value to store in the table
 107          */
 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                 *keyset_end = key;
 131                 keyset_end++;
 132                 size++;
 133         }
 134
 135         /**
 136          * @brief Lookup the corresponding value for the given key
 137          * @param key The key for finding the value; must not be 0 or NULL
 138          * @return The value in the table, if the key is found; otherwise 0
 139          */
 140         _Val get(_Key key) const {
 141                 struct hashlistnode<_Key, _Val> *search;
 142
 143                 /* HashTable cannot handle 0 as a key */
 144                 ASSERT(key);
 145
 146                 unsigned int index = ((_KeyInt)key) >> _Shift;
 147                 do {
 148                         index &= capacitymask;
 149                         search = &table[index];
 150                         if (search->key == key)
 151                                 return search->val;
 152                         index++;
 153                 } while (search->key);
 154                 return (_Val)0;
 155         }
 156
 157         /**
 158          * @brief Check whether the table contains a value for the given key
 159          * @param key The key for finding the value; must not be 0 or NULL
 160          * @return True, if the key is found; false otherwise
 161          */
 162         bool contains(_Key key) const {
 163                 struct hashlistnode<_Key, _Val> *search;
 164
 165                 /* HashTable cannot handle 0 as a key */
 166                 ASSERT(key);
 167
 168                 unsigned int index = ((_KeyInt)key) >> _Shift;
 169                 do {
 170                         index &= capacitymask;
 171                         search = &table[index];
 172                         if (search->key == key)
 173                                 return true;
 174                         index++;
 175                 } while (search->key);
 176                 return false;
 177         }
 178
 179         /**
 180          * @brief Resize the table
 181          * @param newsize The new size of the table
 182          */
 183         void resize(unsigned int newsize) {
 184                 struct hashlistnode<_Key, _Val> *oldtable = table;
 185                 struct hashlistnode<_Key, _Val> *newtable;
 186                 _Key *oldkeyset = keyset;
 187                 _Key *newkeyset;
 188
 189                 unsigned int oldcapacity = capacity;
 190
 191                 if ((newtable = (struct hashlistnode<_Key, _Val> *)_calloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
 192                         model_print("calloc error %s %d\n", __FILE__, __LINE__);
 193                         exit(EXIT_FAILURE);
 194                 }
 195
 196                 if ((newkeyset = (_Key *)_calloc(newsize, sizeof(_Key))) == NULL ) {
 197                         model_print("calloc error %s %d\n", __FILE__, __LINE__);
 198                         exit(EXIT_FAILURE);
 199                 }
 200
 201                 table = newtable;       // Update the global hashtable upon resize()
 202                 keyset = newkeyset;
 203                 keyset_end = newkeyset;
 204
 205                 capacity = newsize;
 206                 capacitymask = newsize - 1;
 207
 208                 threshold = (unsigned int)(newsize * loadfactor);
 209
 210                 struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
 211                 struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
 212                 for (;bin < lastbin;bin++) {
 213                         _Key key = bin->key;
 214
 215                         struct hashlistnode<_Key, _Val> *search;
 216
 217                         unsigned int index = ((_KeyInt)key) >> _Shift;
 218                         do {
 219                                 index &= capacitymask;
 220                                 search = &table[index];
 221                                 index++;
 222                         } while (search->key);
 223
 224                         search->key = key;
 225                         search->val = bin->val;
 226                 }
 227
 228                 memcpy(keyset, oldkeyset, size * sizeof(_Key)); // copy keyset
 229                 keyset_end = keyset + size;     // pointer arithmetic
 230
 231                 _free(oldtable);        // Free the memory of the old hash table
 232                 _free(oldkeyset);
 233         }
 234
 235         _Key * getKeySet() {
 236                 return keyset;
 237         }
 238
 239         unsigned int getSize() {
 240                 return size;
 241         }
 242
 243 private:
 244         struct hashlistnode<_Key, _Val> *table;
 245         _Key *keyset;
 246         _Key *keyset_end;
 247         unsigned int capacity;
 248         unsigned int size;
 249         unsigned int capacitymask;
 250         unsigned int threshold;
 251         double loadfactor;
 252 };
 253
 254 #endif  /* __HASHTABLE_H__ */