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
  11 template<typename _Key, typename _Val, void * (* _malloc)(size_t), void * (* _calloc)(size_t, size_t), void (*_free)(void *)>
  12         struct hashlistnode {
  13                 _Key key;
  14                 _Val val;
  15                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *next;
  16
  17         void * operator new(size_t size) {
  18                 return _malloc(size);
  19         }
  20
  21         void operator delete(void *p, size_t size) {
  22                 _free(p);
  23         }
  24
  25         void * operator new[](size_t size) {
  26                 return _malloc(size);
  27         }
  28
  29         void operator delete[](void *p, size_t size) {
  30                 _free(p);
  31         }
  32         };
  33
  34 /** Hashtable class.  By default it is snapshotting, but you can pass
  35                 in your own allocation functions. */
  36
  37 template<typename _Key, typename _Val, typename _KeyInt, int _Shift=0, void * (* _malloc)(size_t)=malloc, void * (* _calloc)(size_t, size_t)=calloc, void (*_free)(void *)=free>
  38         class HashTable {
  39  public:
  40         HashTable(unsigned int initialcapacity=1024, double factor=0.5) {
  41                 // Allocate space for the hash table
  42                 table = (struct hashlistnode<_Key,_Val, _malloc, _calloc,_free> **) _calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *));
  43                 loadfactor = factor;
  44                 capacity = initialcapacity;
  45                 threshold = (unsigned int) (initialcapacity*loadfactor);
  46                 mask = (capacity << _Shift)-1;
  47                 size = 0; // Initial number of elements in the hash
  48         }
  49
  50         ~HashTable() {
  51                 for(unsigned int i=0;i<capacity;i++) {
  52                         struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> * bin = table[i];
  53                         while(bin!=NULL) {
  54                                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> * next=bin->next;
  55                                 delete bin;
  56                                 bin=next;
  57                         }
  58                 }
  59                 _free(table);
  60         }
  61
  62         void * operator new(size_t size) {
  63                 return _malloc(size);
  64         }
  65
  66         void operator delete(void *p, size_t size) {
  67                 _free(p);
  68         }
  69
  70         void * operator new[](size_t size) {
  71                 return _malloc(size);
  72         }
  73
  74         void operator delete[](void *p, size_t size) {
  75                 _free(p);
  76         }
  77
  78         /** Reset the table to its initial state. */
  79         void reset() {
  80                 for(int i=0;i<capacity;i++) {
  81                         struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> * bin = table[i];
  82                         while(bin!=NULL) {
  83                                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> * next=bin->next;
  84                                 delete bin;
  85                                 bin=next;
  86                         }
  87                 }
  88                 memset(table, 0, capacity*sizeof(struct hashlistnode<_Key, _Val, _malloc, _calloc, _free> *));
  89                 size=0;
  90         }
  91
  92         /** Put a key value pair into the table. */
  93         void put(_Key key, _Val val) {
  94                 if(size > threshold) {
  95                         //Resize
  96                         unsigned int newsize = capacity << 1;
  97                         resize(newsize);
  98                 }
  99
 100                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *ptr = table[(((_KeyInt)key) & mask)>>_Shift];
 101                 size++;
 102                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *search = ptr;
 103
 104                 while(search!=NULL) {
 105                         if (search->key==key) {
 106                                 search->val=val;
 107                                 return;
 108                         }
 109                         search=search->next;
 110                 }
 111
 112                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *newptr=(struct hashlistnode<_Key,_Val,_malloc,_calloc,_free> *)new struct hashlistnode<_Key,_Val, _malloc, _calloc, _free>;
 113                 newptr->key=key;
 114                 newptr->val=val;
 115                 newptr->next=ptr;
 116                 table[(((_KeyInt)key)&mask)>>_Shift]=newptr;
 117         }
 118
 119         /** Put a key entry into the table. */
 120         _Val * ensureptr(_Key key) {
 121                 if(size > threshold) {
 122                         //Resize
 123                   unsigned int newsize = capacity << 1;
 124                   resize(newsize);
 125           }
 126
 127           struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *ptr = table[(((_KeyInt)key) & mask)>>_Shift];
 128                 size++;
 129                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *search = ptr;
 130
 131                 while(search!=NULL) {
 132                         if (search->key==key) {
 133                                 return &search->val;
 134                         }
 135                         search=search->next;
 136                 }
 137
 138                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *newptr=(struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *)new struct hashlistnode<_Key,_Val, _malloc, _calloc, _free>;
 139                 newptr->key=key;
 140                 newptr->next=ptr;
 141                 table[(((_KeyInt)key)&mask)>>_Shift]=newptr;
 142                 return &newptr->val;
 143         }
 144
 145         /** Lookup the corresponding value for the given key. */
 146         _Val get(_Key key) {
 147                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *search = table[(((_KeyInt)key) & mask)>>_Shift];
 148
 149                 while(search!=NULL) {
 150                         if (search->key==key) {
 151                                 return search->val;
 152                         }
 153                         search=search->next;
 154                 }
 155                 return (_Val)0;
 156         }
 157
 158         /** Lookup the corresponding value for the given key. */
 159         _Val * getptr(_Key key) {
 160                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *search = table[(((_KeyInt)key) & mask)>>_Shift];
 161
 162                 while(search!=NULL) {
 163                         if (search->key==key) {
 164                                 return & search->val;
 165                         }
 166                         search=search->next;
 167                 }
 168                 return (_Val *) NULL;
 169         }
 170
 171         /** Check whether the table contains a value for the given key. */
 172         bool contains(_Key key) {
 173                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *search = table[(((_KeyInt)key) & mask)>>_Shift];
 174
 175                 while(search!=NULL) {
 176                         if (search->key==key) {
 177                                 return true;
 178                         }
 179                         search=search->next;
 180                 }
 181                 return false;
 182         }
 183
 184         /** Resize the table. */
 185         void resize(unsigned int newsize) {
 186                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> ** oldtable = table;
 187                 struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> ** newtable;
 188                 unsigned int oldcapacity = capacity;
 189
 190                 if((newtable = (struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> **) _calloc(newsize, sizeof(struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> *))) == NULL) {
 191                         printf("Calloc error %s %d\n", __FILE__, __LINE__);
 192                         exit(-1);
 193                 }
 194
 195                 table = newtable;          //Update the global hashtable upon resize()
 196                 capacity = newsize;
 197                 threshold = (unsigned int) (newsize * loadfactor);
 198                 mask = (newsize << _Shift)-1;
 199
 200                 for(unsigned int i = 0; i < oldcapacity; i++) {
 201                         struct hashlistnode<_Key, _Val, _malloc, _calloc, _free> * bin = oldtable[i];
 202
 203                         while(bin!=NULL) {
 204                                 _Key key=bin->key;
 205                                 struct hashlistnode<_Key, _Val, _malloc, _calloc, _free> * next=bin->next;
 206
 207                                 unsigned int index = (((_KeyInt)key) & mask) >>_Shift;
 208                                 struct hashlistnode<_Key, _Val, _malloc, _calloc, _free> * tmp=newtable[index];
 209                                 bin->next=tmp;
 210                                 newtable[index]=bin;
 211                                 bin = next;
 212                         }
 213                 }
 214
 215                 _free(oldtable);            //Free the memory of the old hash table
 216         }
 217
 218  private:
 219         struct hashlistnode<_Key,_Val, _malloc, _calloc, _free> **table;
 220         unsigned int capacity;
 221         _KeyInt mask;
 222         unsigned int size;
 223         unsigned int threshold;
 224         double loadfactor;
 225 };
 226 #endif