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.
  41  *
  42  * @tparam _Key    Type name for the key
  43  * @tparam _Val    Type name for the values to be stored
  44  * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
  45  *                 manipulation and storage.
  46  * @tparam _Shift  Logical shift to apply to all keys. Default 0.
  47  * @tparam _malloc Provide your own 'malloc' for the table, or default to
  48  *                 snapshotting.
  49  * @tparam _calloc Provide your own 'calloc' for the table, or default to
  50  *                 snapshotting.
  51  * @tparam _free   Provide your own 'free' for the table, or default to
  52  *                 snapshotting.
  53  */
  54 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>
  55         class HashTable {
  56  public:
  57         /**
  58          * Constructor
  59          * @param initialcapacity Sets the initial capacity of the hash table.
  60          * Default size 1024.
  61          * @param factor Sets the percentage full before the hashtable is
  62          * resized. Default ratio 0.5.
  63          */
  64         HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
  65                 // Allocate space for the hash table
  66                 table = (struct hashlistnode<_Key, _Val> *)_calloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
  67                 loadfactor = factor;
  68                 capacity = initialcapacity;
  69                 capacitymask = initialcapacity - 1;
  70
  71                 threshold = (unsigned int)(initialcapacity * loadfactor);
  72                 size = 0; // Initial number of elements in the hash
  73         }
  74
  75         /** Destructor */
  76         ~HashTable() {
  77                 _free(table);
  78         }
  79
  80         /** Override: new operator */
  81         void * operator new(size_t size) {
  82                 return _malloc(size);
  83         }
  84
  85         /** Override: delete operator */
  86         void operator delete(void *p, size_t size) {
  87                 _free(p);
  88         }
  89
  90         /** Override: new[] operator */
  91         void * operator new[](size_t size) {
  92                 return _malloc(size);
  93         }
  94
  95         /** Override: delete[] operator */
  96         void operator delete[](void *p, size_t size) {
  97                 _free(p);
  98         }
  99
 100         /** Reset the table to its initial state. */
 101         void reset() {
 102                 memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
 103                 size = 0;
 104         }
 105
 106         /** Put a key value pair into the table. */
 107         void put(_Key key, _Val val) {
 108                 if (size > threshold)
 109                         resize(capacity << 1);
 110
 111                 struct hashlistnode<_Key, _Val> *search;
 112
 113                 unsigned int index = ((_KeyInt)key) >> _Shift;
 114                 do {
 115                         index &= capacitymask;
 116                         search = &table[index];
 117                         if (search->key == key) {
 118                                 search->val = val;
 119                                 return;
 120                         }
 121                         index++;
 122                 } while (search->key);
 123
 124                 search->key = key;
 125                 search->val = val;
 126                 size++;
 127         }
 128
 129         /** Lookup the corresponding value for the given key. */
 130         _Val get(_Key key) const {
 131                 struct hashlistnode<_Key, _Val> *search;
 132
 133                 unsigned int index = ((_KeyInt)key) >> _Shift;
 134                 do {
 135                         index &= capacitymask;
 136                         search = &table[index];
 137                         if (search->key == key)
 138                                 return search->val;
 139                         index++;
 140                 } while (search->key);
 141                 return (_Val)0;
 142         }
 143
 144         /** Check whether the table contains a value for the given key. */
 145         bool contains(_Key key) const {
 146                 struct hashlistnode<_Key, _Val> *search;
 147
 148                 unsigned int index = ((_KeyInt)key) >> _Shift;
 149                 do {
 150                         index &= capacitymask;
 151                         search = &table[index];
 152                         if (search->key == key)
 153                                 return true;
 154                         index++;
 155                 } while (search->key);
 156                 return false;
 157         }
 158
 159         /** Resize the table. */
 160         void resize(unsigned int newsize) {
 161                 struct hashlistnode<_Key, _Val> *oldtable = table;
 162                 struct hashlistnode<_Key, _Val> *newtable;
 163                 unsigned int oldcapacity = capacity;
 164
 165                 if ((newtable = (struct hashlistnode<_Key, _Val> *)_calloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
 166                         model_print("calloc error %s %d\n", __FILE__, __LINE__);
 167                         exit(EXIT_FAILURE);
 168                 }
 169
 170                 table = newtable;          // Update the global hashtable upon resize()
 171                 capacity = newsize;
 172                 capacitymask = newsize - 1;
 173
 174                 threshold = (unsigned int)(newsize * loadfactor);
 175
 176                 struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
 177                 struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
 178                 for (; bin < lastbin; bin++) {
 179                         _Key key = bin->key;
 180
 181                         struct hashlistnode<_Key, _Val> *search;
 182
 183                         unsigned int index = ((_KeyInt)key) >> _Shift;
 184                         do {
 185                                 index &= capacitymask;
 186                                 search = &table[index];
 187                                 index++;
 188                         } while (search->key);
 189
 190                         search->key = key;
 191                         search->val = bin->val;
 192                 }
 193
 194                 _free(oldtable);            // Free the memory of the old hash table
 195         }
 196
 197  private:
 198         struct hashlistnode<_Key, _Val> *table;
 199         unsigned int capacity;
 200         unsigned int size;
 201         unsigned int capacitymask;
 202         unsigned int threshold;
 203         double loadfactor;
 204 };
 205 #endif