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=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) {
 128                 struct hashlistnode<_Key,_Val> *search;
 129
 130                 unsigned int index=((_KeyInt)key)>>_Shift;
 131                 do {
 132                         index=index&capacitymask;
 133                         search = &table[index];
 134                         if (search->key==key) {
 135                                 return search->val;
 136                         }
 137                         index++;
 138                 } while(search->key);
 139                 return (_Val) 0;
 140         }
 141
 142         /** Check whether the table contains a value for the given key. */
 143         bool contains(_Key key) {
 144                 struct hashlistnode<_Key,_Val> *search;
 145
 146                 unsigned int index=((_KeyInt)key)>>_Shift;
 147                 do {
 148                         index=index&capacitymask;
 149                         search = &table[index];
 150                         if (search->key==key) {
 151                                 return true;
 152                         }
 153                         index++;
 154                 } while(search->key);
 155                 return false;
 156         }
 157
 158         /** Resize the table. */
 159         void resize(unsigned int newsize) {
 160                 struct hashlistnode<_Key,_Val> * oldtable = table;
 161                 struct hashlistnode<_Key,_Val> * newtable;
 162                 unsigned int oldcapacity = capacity;
 163
 164                 if((newtable = (struct hashlistnode<_Key,_Val> *) _calloc(newsize, sizeof(struct hashlistnode<_Key,_Val>))) == NULL) {
 165                         model_print("Calloc error %s %d\n", __FILE__, __LINE__);
 166                         exit(-1);
 167                 }
 168
 169                 table = newtable;          //Update the global hashtable upon resize()
 170                 capacity = newsize;
 171                 capacitymask = newsize - 1;
 172
 173                 threshold = (unsigned int) (newsize * loadfactor);
 174
 175                 struct hashlistnode<_Key, _Val> * bin = &oldtable[0];
 176                 struct hashlistnode<_Key, _Val> * lastbin = &oldtable[oldcapacity];
 177                 for(; bin < lastbin; bin++) {
 178                         _Key key=bin->key;
 179
 180                         struct hashlistnode<_Key,_Val> *search;
 181
 182                         unsigned int index=((_KeyInt)key)>>_Shift;
 183                         do {
 184                                 index=index&capacitymask;
 185                                 search = &table[index];
 186                                 index++;
 187                         } while(search->key);
 188
 189                         search->key=key;
 190                         search->val=bin->val;
 191                 }
 192
 193                 _free(oldtable);            //Free the memory of the old hash table
 194         }
 195
 196  private:
 197         struct hashlistnode<_Key,_Val> *table;
 198         unsigned int capacity;
 199         unsigned int size;
 200         unsigned int capacitymask;
 201         unsigned int threshold;
 202         double loadfactor;
 203 };
 204 #endif