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