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