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>
  12         struct hashlistnode {
  13                 _Key key;
  14                 _Val val;
  15                 struct hashlistnode<_Key,_Val> *next;
  16         };
  17
  18 template<typename _Key, typename _Val, typename _KeyInt, int _Shift>
  19         class HashTable {
  20  public:
  21         HashTable(unsigned int initialcapacity=1024, double factor=0.5) {
  22                 // Allocate space for the hash table
  23                 table = (struct hashlistnode<_Key,_Val> **) calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val> *));
  24                 loadfactor = factor;
  25                 capacity = initialcapacity;
  26                 threshold = (unsigned int) (initialcapacity*loadfactor);
  27                 mask = (capacity << _Shift)-1;
  28                 size = 0; // Initial number of elements in the hash
  29         }
  30
  31         ~HashTable() {
  32                 for(unsigned int i=0;i<capacity;i++) {
  33                         struct hashlistnode<_Key,_Val> * bin = table[i];
  34                         while(bin!=NULL) {
  35                                 struct hashlistnode<_Key,_Val> * next=bin->next;
  36                                 free(bin);
  37                                 bin=next;
  38                         }
  39                 }
  40                 free(table);
  41         }
  42
  43         /** Reset the table to its initial state. */
  44         void reset() {
  45                 for(int i=0;i<capacity;i++) {
  46                         struct hashlistnode<_Key,_Val> * bin = table[i];
  47                         while(bin!=NULL) {
  48                                 struct hashlistnode<_Key,_Val> * next=bin->next;
  49                                 free(bin);
  50                                 bin=next;
  51                         }
  52                 }
  53                 memset(table, 0, capacity*sizeof(struct hashlistnode<_Key, _Val> *));
  54                 size=0;
  55         }
  56
  57         /** Put a key value pair into the table. */
  58         void put(_Key key, _Val val) {
  59                 if(size > threshold) {
  60                         //Resize
  61                         unsigned int newsize = capacity << 1;
  62                         resize(newsize);
  63                 }
  64
  65                 struct hashlistnode<_Key,_Val> *ptr = table[(((_KeyInt)key) & mask)>>_Shift];
  66                 size++;
  67                 struct hashlistnode<_Key,_Val> *search = ptr;
  68
  69                 while(search!=NULL) {
  70                         if (search->key==key) {
  71                                 search->val=val;
  72                                 return;
  73                         }
  74                         search=search->next;
  75                 }
  76
  77                 struct hashlistnode<_Key,_Val> *newptr=(struct hashlistnode<_Key,_Val> *)malloc(sizeof(struct hashlistnode<_Key,_Val>));
  78                 newptr->key=key;
  79                 newptr->val=val;
  80                 newptr->next=ptr;
  81                 table[(((_KeyInt)key)&mask)>>_Shift]=newptr;
  82         }
  83
  84         /** Lookup the corresponding value for the given key. */
  85         _Val get(_Key key) {
  86                 struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift];
  87
  88                 while(search!=NULL) {
  89                         if (search->key==key) {
  90                                 return search->val;
  91                         }
  92                         search=search->next;
  93                 }
  94                 return (_Val)0;
  95         }
  96
  97         /** Check whether the table contains a value for the given key. */
  98         bool contains(_Key key) {
  99                 struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift];
 100
 101                 while(search!=NULL) {
 102                         if (search->key==key) {
 103                                 return true;
 104                         }
 105                         search=search->next;
 106                 }
 107                 return false;
 108         }
 109
 110         /** Resize the table. */
 111         void resize(unsigned int newsize) {
 112                 struct hashlistnode<_Key,_Val> ** oldtable = table;
 113                 struct hashlistnode<_Key,_Val> ** newtable;
 114                 unsigned int oldcapacity = capacity;
 115
 116                 if((newtable = (struct hashlistnode<_Key,_Val> **) calloc(newsize, sizeof(struct hashlistnode<_Key,_Val> *))) == NULL) {
 117                         printf("Calloc error %s %d\n", __FILE__, __LINE__);
 118                         exit(-1);
 119                 }
 120
 121                 table = newtable;          //Update the global hashtable upon resize()
 122                 capacity = newsize;
 123                 threshold = (unsigned int) (newsize * loadfactor);
 124                 mask = (newsize << _Shift)-1;
 125
 126                 for(unsigned int i = 0; i < oldcapacity; i++) {
 127                         struct hashlistnode<_Key, _Val> * bin = oldtable[i];
 128
 129                         while(bin!=NULL) {
 130                                 _Key key=bin->key;
 131                                 struct hashlistnode<_Key, _Val> * next=bin->next;
 132
 133                                 unsigned int index = (((_KeyInt)key) & mask) >>_Shift;
 134                                 struct hashlistnode<_Key, _Val> * tmp=newtable[index];
 135                                 bin->next=tmp;
 136                                 newtable[index]=bin;
 137                                 bin = next;
 138                         }
 139                 }
 140
 141                 free(oldtable);            //Free the memory of the old hash table
 142         }
 143
 144  private:
 145         struct hashlistnode<_Key,_Val> **table;
 146         unsigned int capacity;
 147         _KeyInt mask;
 148         unsigned int size;
 149         unsigned int threshold;
 150         double loadfactor;
 151 };
 152 #endif