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