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 "mymemory.h"
  11
  12 /**
  13  * Hashtable linked node class, for chained storage of hash table conflicts. By
  14  * default it is snapshotting, but you can pass in your own allocation
  15  * functions.
  16  *
  17  * @tparam _Key    Type name for the key
  18  * @tparam _Val    Type name for the values to be stored
  19  * @tparam _malloc Provide your own 'malloc' for the table, or default to
  20  *                 snapshotting.
  21  * @tparam _calloc Provide your own 'calloc' for the table, or default to
  22  *                 snapshotting.
  23  * @tparam _free   Provide your own 'free' for the table, or default to
  24  *                 snapshotting.
  25  */
  26 template<typename _Key, typename _Val>
  27
  28 struct hashlistnode {
  29         _Key key;
  30         _Val val;
  31 };
  32
  33 /**
  34  * Hashtable class. By default it is snapshotting, but you can pass in your own
  35  * allocation functions.
  36  *
  37  * @tparam _Key    Type name for the key
  38  * @tparam _Val    Type name for the values to be stored
  39  * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
  40  *                 manipulation and storage.
  41  * @tparam _Shift  Logical shift to apply to all keys. Default 0.
  42  * @tparam _malloc Provide your own 'malloc' for the table, or default to
  43  *                 snapshotting.
  44  * @tparam _calloc Provide your own 'calloc' for the table, or default to
  45  *                 snapshotting.
  46  * @tparam _free   Provide your own 'free' for the table, or default to
  47  *                 snapshotting.
  48  */
  49 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>
  50         class HashTable {
  51  public:
  52         /**
  53          * Constructor
  54          * @param initialcapacity Sets the initial capacity of the hash table.
  55          * Default size 1024.
  56          * @param factor Sets the percentage full before the hashtable is
  57          * resized. Default ratio 0.5.
  58          */
  59         HashTable(unsigned int initialcapacity=1024, double factor=0.5) {
  60                 // Allocate space for the hash table
  61                 table = (struct hashlistnode<_Key,_Val> *) _calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val>));
  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         /** Destructor */
  71         ~HashTable() {
  72                 _free(table);
  73         }
  74
  75         /** Override: new operator */
  76         void * operator new(size_t size) {
  77                 return _malloc(size);
  78         }
  79
  80         /** Override: delete operator */
  81         void operator delete(void *p, size_t size) {
  82                 _free(p);
  83         }
  84
  85         /** Override: new[] operator */
  86         void * operator new[](size_t size) {
  87                 return _malloc(size);
  88         }
  89
  90         /** Override: delete[] operator */
  91         void operator delete[](void *p, size_t size) {
  92                 _free(p);
  93         }
  94
  95         /** Reset the table to its initial state. */
  96         void reset() {
  97                 memset(table, 0, capacity*sizeof(struct hashlistnode<_Key, _Val>));
  98                 size=0;
  99         }
 100
 101         /** Put a key value pair into the table. */
 102         void put(_Key key, _Val val) {
 103                 if (size > threshold)
 104                         resize(capacity << 1);
 105
 106                 struct hashlistnode<_Key,_Val> *search;
 107
 108                 unsigned int index=((_KeyInt)key)>>_Shift;
 109                 do {
 110                         index=index&capacitymask;
 111                         search = &table[index];
 112                         if (search->key==key) {
 113                                 search->val=val;
 114                                 return;
 115                         }
 116                         index++;
 117                 } while(search->key);
 118
 119                 search->key=key;
 120                 search->val=val;
 121                 size++;
 122         }
 123
 124         /** Lookup the corresponding value for the given key. */
 125         _Val get(_Key key) {
 126                 struct hashlistnode<_Key,_Val> *search;
 127
 128                 unsigned int index=((_KeyInt)key)>>_Shift;
 129                 do {
 130                         index=index&capacitymask;
 131                         search = &table[index];
 132                         if (search->key==key) {
 133                                 return search->val;
 134                         }
 135                         index++;
 136                 } while(search->key);
 137                 return (_Val) 0;
 138         }
 139
 140         /** Check whether the table contains a value for the given key. */
 141         bool contains(_Key key) {
 142                 struct hashlistnode<_Key,_Val> *search;
 143
 144                 unsigned int index=((_KeyInt)key)>>_Shift;
 145                 do {
 146                         index=index&capacitymask;
 147                         search = &table[index];
 148                         if (search->key==key) {
 149                                 return true;
 150                         }
 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                         printf("Calloc error %s %d\n", __FILE__, __LINE__);
 164                         exit(-1);
 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=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