src/Collections/hashtable.h

   1 /*      Copyright (c) 2015 Regents of the University of California
   2  *
   3  *      Author: Brian Demsky <bdemsky@uci.edu>
   4  *
   5  *      This program is free software; you can redistribute it and/or
   6  *      modify it under the terms of the GNU General Public License
   7  *      version 2 as published by the Free Software Foundation.
   8  */
   9
  10 /** @file hashtable.h
  11  *  @brief Hashtable.  Standard chained bucket variety.
  12  */
  13
  14 #ifndef __HASHTABLE_H__
  15 #define __HASHTABLE_H__
  16
  17 #include <stdlib.h>
  18 #include <stdio.h>
  19 #include <string.h>
  20 #include "mymemory.h"
  21 #include "common.h"
  22
  23 /**
  24  * @brief HashTable node
  25  *
  26  * @tparam _Key    Type name for the key
  27  * @tparam _Val    Type name for the values to be stored
  28  */
  29 template<typename _Key, typename _Val>
  30 struct hashlistnode {
  31         _Key key;
  32         _Val val;
  33 };
  34
  35 template<typename _Key, int _Shift, typename _KeyInt>
  36 inline unsigned int default_hash_function(_Key hash) {
  37         return (unsigned int)(((_KeyInt)hash) >> _Shift);
  38 }
  39
  40 template<typename _Key>
  41 inline bool default_equals(_Key key1, _Key key2) {
  42         return key1 == key2;
  43 }
  44
  45 /**
  46  * @brief A simple, custom hash table
  47  *
  48  * By default it is snapshotting, but you can pass in your own allocation
  49  * functions. Note that this table does not support the value 0 (NULL) used as
  50  * a key and is designed primarily with pointer-based keys in mind. Other
  51  * primitive key types are supported only for non-zero values.
  52  *
  53  * @tparam _Key    Type name for the key
  54  * @tparam _Val    Type name for the values to be stored
  55  * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
  56  *                 manipulation and storage.
  57  * @tparam _Shift  Logical shift to apply to all keys. Default 0.
  58  */
  59 template<typename _Key, typename _Val, typename _KeyInt, int _Shift = 0, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
  60 class HashTable {
  61 public:
  62         /**
  63          * @brief Hash table constructor
  64          * @param initialcapacity Sets the initial capacity of the hash table.
  65          * Default size 1024.
  66          * @param factor Sets the percentage full before the hashtable is
  67          * resized. Default ratio 0.5.
  68          */
  69         HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
  70                 // Allocate space for the hash table
  71                 table = (struct hashlistnode<_Key, _Val> *)ourcalloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
  72                 zero = NULL;
  73                 loadfactor = factor;
  74                 capacity = initialcapacity;
  75                 capacitymask = initialcapacity - 1;
  76
  77                 threshold = (unsigned int)(initialcapacity * loadfactor);
  78                 size = 0;                                                       // Initial number of elements in the hash
  79         }
  80
  81         /** @brief Hash table destructor */
  82         ~HashTable() {
  83                 ourfree(table);
  84                 if (zero)
  85                         ourfree(zero);
  86         }
  87
  88         /** Override: new operator */
  89         void * operator new(size_t size) {
  90                 return ourmalloc(size);
  91         }
  92
  93         /** Override: delete operator */
  94         void operator delete(void *p, size_t size) {
  95                 ourfree(p);
  96         }
  97
  98         /** Override: new[] operator */
  99         void * operator new[](size_t size) {
 100                 return ourmalloc(size);
 101         }
 102
 103         /** Override: delete[] operator */
 104         void operator delete[](void *p, size_t size) {
 105                 ourfree(p);
 106         }
 107
 108         /** @brief Reset the table to its initial state. */
 109         void reset() {
 110                 memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
 111                 if (zero) {
 112                         ourfree(zero);
 113                         zero = NULL;
 114                 }
 115                 size = 0;
 116         }
 117
 118         void resetanddelete() {
 119                 for(unsigned int i=0;i<capacity;i++) {
 120                         struct hashlistnode<_Key, _Val> *bin = &table[i];
 121                         if (bin->key != NULL) {
 122                                 bin->key = NULL;
 123                                 if (bin->val != NULL) {
 124                                         delete bin->val;
 125                                         bin->val = NULL;
 126                                 }
 127                         }
 128                 }
 129                 if (zero) {
 130                         if (zero->val != NULL)
 131                                 delete zero->val;
 132                         ourfree(zero);
 133                         zero = NULL;
 134                 }
 135                 size = 0;
 136         }
 137
 138         void resetandfree() {
 139                 for(unsigned int i=0;i<capacity;i++) {
 140                         struct hashlistnode<_Key, _Val> *bin = &table[i];
 141                         if (bin->key != NULL) {
 142                                 bin->key = NULL;
 143                                 if (bin->val != NULL) {
 144                                         ourfree(bin->val);
 145                                         bin->val = NULL;
 146                                 }
 147                         }
 148                 }
 149                 if (zero) {
 150                         if (zero->val != NULL)
 151                                 ourfree(zero->val);
 152                         ourfree(zero);
 153                         zero = NULL;
 154                 }
 155                 size = 0;
 156         }
 157
 158         /**
 159          * @brief Put a key/value pair into the table
 160          * @param key The key for the new value; must not be 0 or NULL
 161          * @param val The value to store in the table
 162          */
 163         void put(_Key key, _Val val) {
 164                 /* HashTable cannot handle 0 as a key */
 165                 if (!key) {
 166                         if (!zero) {
 167                                 zero=(struct hashlistnode<_Key, _Val> *)ourmalloc(sizeof(struct hashlistnode<_Key, _Val>));
 168                                 size++;
 169                         }
 170                         zero->key=key;
 171                         zero->val=val;
 172                         return;
 173                 }
 174
 175                 if (size > threshold)
 176                         resize(capacity << 1);
 177
 178                 struct hashlistnode<_Key, _Val> *search;
 179
 180                 unsigned int index = hash_function(key);
 181                 do {
 182                         index &= capacitymask;
 183                         search = &table[index];
 184                         if (!search->key) {
 185                                 //key is null, probably done
 186                                 break;
 187                         }
 188                         if (equals(search->key, key)) {
 189                                 search->val = val;
 190                                 return;
 191                         }
 192                         index++;
 193                 } while (true);
 194
 195                 search->key = key;
 196                 search->val = val;
 197                 size++;
 198         }
 199
 200         /**
 201          * @brief Lookup the corresponding value for the given key
 202          * @param key The key for finding the value; must not be 0 or NULL
 203          * @return The value in the table, if the key is found; otherwise 0
 204          */
 205         _Val get(_Key key) const {
 206                 struct hashlistnode<_Key, _Val> *search;
 207
 208                 /* HashTable cannot handle 0 as a key */
 209                 if (!key) {
 210                         if (zero)
 211                                 return zero->val;
 212                         else
 213                                 return (_Val) 0;
 214                 }
 215
 216                 unsigned int oindex = hash_function(key) & capacitymask;
 217                 unsigned int index=oindex;
 218                 do {
 219                         search = &table[index];
 220                         if (!search->key) {
 221                                 if (!search->val)
 222                                         break;
 223                         } else
 224                         if (equals(search->key, key))
 225                                 return search->val;
 226                         index++;
 227                         index &= capacitymask;
 228                         if (index==oindex)
 229                                 break;
 230                 } while (true);
 231                 return (_Val)0;
 232         }
 233
 234         /**
 235          * @brief Remove the given key and return the corresponding value
 236          * @param key The key for finding the value; must not be 0 or NULL
 237          * @return The value in the table, if the key is found; otherwise 0
 238          */
 239         _Val remove(_Key key) {
 240                 struct hashlistnode<_Key, _Val> *search;
 241
 242                 /* HashTable cannot handle 0 as a key */
 243                 if (!key) {
 244                         if (!zero) {
 245                                 return (_Val)0;
 246                         } else {
 247                                 _Val v=zero->val;
 248                                 ourfree(zero);
 249                                 zero=NULL;
 250                                 size--;
 251                                 return v;
 252                         }
 253                 }
 254
 255
 256                 unsigned int index = hash_function(key);
 257                 do {
 258                         index &= capacitymask;
 259                         search = &table[index];
 260                         if (!search->key) {
 261                                 if (!search->val)
 262                                         break;
 263                         } else
 264                         if (equals(search->key, key)) {
 265                                 _Val v=search->val;
 266                                 //empty out this bin
 267                                 search->val=(_Val) 1;
 268                                 search->key=0;
 269                                 size--;
 270                                 return v;
 271                         }
 272                         index++;
 273                 } while (true);
 274                 return (_Val)0;
 275         }
 276
 277         unsigned int getSize() const {
 278                 return size;
 279         }
 280
 281
 282         /**
 283          * @brief Check whether the table contains a value for the given key
 284          * @param key The key for finding the value; must not be 0 or NULL
 285          * @return True, if the key is found; false otherwise
 286          */
 287         bool contains(_Key key) const {
 288                 struct hashlistnode<_Key, _Val> *search;
 289
 290                 /* HashTable cannot handle 0 as a key */
 291                 if (!key) {
 292                         return zero!=NULL;
 293                 }
 294
 295                 unsigned int index = hash_function(key);
 296                 do {
 297                         index &= capacitymask;
 298                         search = &table[index];
 299                         if (!search->key) {
 300                                 if (!search->val)
 301                                         break;
 302                         } else
 303                         if (equals(search->key, key))
 304                                 return true;
 305                         index++;
 306                 } while (true);
 307                 return false;
 308         }
 309
 310         /**
 311          * @brief Resize the table
 312          * @param newsize The new size of the table
 313          */
 314         void resize(unsigned int newsize) {
 315                 struct hashlistnode<_Key, _Val> *oldtable = table;
 316                 struct hashlistnode<_Key, _Val> *newtable;
 317                 unsigned int oldcapacity = capacity;
 318
 319                 if ((newtable = (struct hashlistnode<_Key, _Val> *)ourcalloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
 320                         model_print("calloc error %s %d\n", __FILE__, __LINE__);
 321                         exit(EXIT_FAILURE);
 322                 }
 323
 324                 table = newtable;                                                                                       // Update the global hashtable upon resize()
 325                 capacity = newsize;
 326                 capacitymask = newsize - 1;
 327
 328                 threshold = (unsigned int)(newsize * loadfactor);
 329
 330                 struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
 331                 struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
 332                 for (;bin < lastbin;bin++) {
 333                         _Key key = bin->key;
 334
 335                         struct hashlistnode<_Key, _Val> *search;
 336                         if (!key)
 337                                 continue;
 338
 339                         unsigned int index = hash_function(key);
 340                         do {
 341                                 index &= capacitymask;
 342                                 search = &table[index];
 343                                 index++;
 344                         } while (search->key);
 345
 346                         search->key = key;
 347                         search->val = bin->val;
 348                 }
 349
 350                 ourfree(oldtable);                                                                                              // Free the memory of the old hash table
 351         }
 352         double getLoadFactor() {return loadfactor;}
 353         unsigned int getCapacity() {return capacity;}
 354         struct hashlistnode<_Key, _Val> *table;
 355         struct hashlistnode<_Key, _Val> *zero;
 356         unsigned int capacity;
 357         unsigned int size;
 358 private:
 359         unsigned int capacitymask;
 360         unsigned int threshold;
 361         double loadfactor;
 362 };
 363
 364 #endif/* __HASHTABLE_H__ */