src/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 model_malloc, 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  * @tparam _malloc Provide your own 'malloc' for the table, or default to
  59  *                 model_malloc.
  60  * @tparam _calloc Provide your own 'calloc' for the table, or default to
  61  *                 model_malloc.
  62  * @tparam _free   Provide your own 'free' for the table, or default to
  63  *                 model_malloc.
  64  */
  65 template<typename _Key, typename _Val, typename _KeyInt, int _Shift = 0, void * (* _malloc)(size_t) = model_malloc, void * (* _calloc)(size_t, size_t) = model_calloc, void (*_free)(void *) = model_free, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
  66 class HashTable {
  67 public:
  68         /**
  69          * @brief Hash table constructor
  70          * @param initialcapacity Sets the initial capacity of the hash table.
  71          * Default size 1024.
  72          * @param factor Sets the percentage full before the hashtable is
  73          * resized. Default ratio 0.5.
  74          */
  75         HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
  76                 // Allocate space for the hash table
  77                 table = (struct hashlistnode<_Key, _Val> *)_calloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
  78                 zero = NULL;
  79                 loadfactor = factor;
  80                 capacity = initialcapacity;
  81                 capacitymask = initialcapacity - 1;
  82
  83                 threshold = (unsigned int)(initialcapacity * loadfactor);
  84                 // Initial number of elements in the hash
  85                 size = 0;
  86         }
  87
  88         /** @brief Hash table destructor */
  89         ~HashTable() {
  90                 _free(table);
  91                 if (zero)
  92                         _free(zero);
  93         }
  94
  95         /** Override: new operator */
  96         void * operator new(size_t size) {
  97                 return _malloc(size);
  98         }
  99
 100         /** Override: delete operator */
 101         void operator delete(void *p, size_t size) {
 102                 _free(p);
 103         }
 104
 105         /** Override: new[] operator */
 106         void * operator new[](size_t size) {
 107                 return _malloc(size);
 108         }
 109
 110         /** Override: delete[] operator */
 111         void operator delete[](void *p, size_t size) {
 112                 _free(p);
 113         }
 114
 115         /** @brief Reset the table to its initial state. */
 116         void reset() {
 117                 memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
 118                 if (zero) {
 119                         _free(zero);
 120                         zero = NULL;
 121                 }
 122                 size = 0;
 123         }
 124
 125         void resetanddelete() {
 126                 for(unsigned int i=0;i<capacity;i++) {
 127                         struct hashlistnode<_Key, _Val> *bin = &table[i];
 128                         if (bin->key != NULL) {
 129                                 bin->key = NULL;
 130                                 if (bin->val != NULL) {
 131                                         delete bin->val;
 132                                         bin->val = NULL;
 133                                 }
 134                         }
 135                 }
 136                 if (zero) {
 137                         if (zero->val != NULL)
 138                                 delete zero->val;
 139                         _free(zero);
 140                         zero = NULL;
 141                 }
 142                 size = 0;
 143         }
 144
 145         void resetandfree() {
 146                 for(unsigned int i=0;i<capacity;i++) {
 147                         struct hashlistnode<_Key, _Val> *bin = &table[i];
 148                         if (bin->key != NULL) {
 149                                 bin->key = NULL;
 150                                 if (bin->val != NULL) {
 151                                         _free(bin->val);
 152                                         bin->val = NULL;
 153                                 }
 154                         }
 155                 }
 156                 if (zero) {
 157                         if (zero->val != NULL)
 158                                 _free(zero->val);
 159                         _free(zero);
 160                         zero = NULL;
 161                 }
 162                 size = 0;
 163         }
 164
 165         /**
 166          * @brief Put a key/value pair into the table
 167          * @param key The key for the new value; must not be 0 or NULL
 168          * @param val The value to store in the table
 169          */
 170         void put(_Key key, _Val val) {
 171                 /* HashTable cannot handle 0 as a key */
 172                 if (!key) {
 173                         if (!zero) {
 174                                 zero=(struct hashlistnode<_Key, _Val> *)_malloc(sizeof(struct hashlistnode<_Key, _Val>));
 175                                 size++;
 176                         }
 177                         zero->key=key;
 178                         zero->val=val;
 179                         return;
 180                 }
 181
 182                 if (size > threshold)
 183                         resize(capacity << 1);
 184
 185                 struct hashlistnode<_Key, _Val> *search;
 186
 187                 unsigned int index = hash_function(key);
 188                 do {
 189                         index &= capacitymask;
 190                         search = &table[index];
 191                         if (!search->key) {
 192                                 //key is null, probably done
 193                                 break;
 194                         }
 195                         if (equals(search->key, key)) {
 196                                 search->val = val;
 197                                 return;
 198                         }
 199                         index++;
 200                 } while (true);
 201
 202                 search->key = key;
 203                 search->val = val;
 204                 size++;
 205         }
 206
 207         /**
 208          * @brief Lookup the corresponding value for the given key
 209          * @param key The key for finding the value; must not be 0 or NULL
 210          * @return The value in the table, if the key is found; otherwise 0
 211          */
 212         _Val get(_Key key) const {
 213                 struct hashlistnode<_Key, _Val> *search;
 214
 215                 /* HashTable cannot handle 0 as a key */
 216                 if (!key) {
 217                         if (zero)
 218                                 return zero->val;
 219                         else
 220                                 return (_Val) 0;
 221                 }
 222
 223                 unsigned int oindex = hash_function(key) & capacitymask;
 224                 unsigned int index=oindex;
 225                 do {
 226                         search = &table[index];
 227                         if (!search->key) {
 228                                 if (!search->val)
 229                                         break;
 230                         } else
 231                         if (equals(search->key, key))
 232                                 return search->val;
 233                         index++;
 234                         index &= capacitymask;
 235                         if (index==oindex)
 236                                 break;
 237                 } while (true);
 238                 return (_Val)0;
 239         }
 240
 241         /**
 242          * @brief Remove the given key and return the corresponding value
 243          * @param key The key for finding the value; must not be 0 or NULL
 244          * @return The value in the table, if the key is found; otherwise 0
 245          */
 246         _Val remove(_Key key) {
 247                 struct hashlistnode<_Key, _Val> *search;
 248
 249                 /* HashTable cannot handle 0 as a key */
 250                 if (!key) {
 251                         if (!zero) {
 252                                 return (_Val)0;
 253                         } else {
 254                                 _Val v=zero->val;
 255                                 _free(zero);
 256                                 zero=NULL;
 257                                 size--;
 258                                 return v;
 259                         }
 260                 }
 261
 262
 263                 unsigned int index = hash_function(key);
 264                 do {
 265                         index &= capacitymask;
 266                         search = &table[index];
 267                         if (!search->key) {
 268                                 if (!search->val)
 269                                         break;
 270                         } else
 271                         if (equals(search->key, key)) {
 272                                 _Val v=search->val;
 273                                 //empty out this bin
 274                                 search->val=(_Val) 1;
 275                                 search->key=0;
 276                                 size--;
 277                                 return v;
 278                         }
 279                         index++;
 280                 } while (true);
 281                 return (_Val)0;
 282         }
 283
 284         unsigned int getSize() const {
 285                 return size;
 286         }
 287
 288
 289         /**
 290          * @brief Check whether the table contains a value for the given key
 291          * @param key The key for finding the value; must not be 0 or NULL
 292          * @return True, if the key is found; false otherwise
 293          */
 294         bool contains(_Key key) const {
 295                 struct hashlistnode<_Key, _Val> *search;
 296
 297                 /* HashTable cannot handle 0 as a key */
 298                 if (!key) {
 299                         return zero!=NULL;
 300                 }
 301
 302                 unsigned int index = hash_function(key);
 303                 do {
 304                         index &= capacitymask;
 305                         search = &table[index];
 306                         if (!search->key) {
 307                                 if (!search->val)
 308                                         break;
 309                         } else
 310                         if (equals(search->key, key))
 311                                 return true;
 312                         index++;
 313                 } while (true);
 314                 return false;
 315         }
 316
 317         /**
 318          * @brief Resize the table
 319          * @param newsize The new size of the table
 320          */
 321         void resize(unsigned int newsize) {
 322                 struct hashlistnode<_Key, _Val> *oldtable = table;
 323                 struct hashlistnode<_Key, _Val> *newtable;
 324                 unsigned int oldcapacity = capacity;
 325
 326                 if ((newtable = (struct hashlistnode<_Key, _Val> *)_calloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
 327                         model_print("calloc error %s %d\n", __FILE__, __LINE__);
 328                         exit(EXIT_FAILURE);
 329                 }
 330
 331                 table = newtable;
 332                 // Update the global hashtable upon resize()
 333                 capacity = newsize;
 334                 capacitymask = newsize - 1;
 335
 336                 threshold = (unsigned int)(newsize * loadfactor);
 337
 338                 struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
 339                 struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
 340                 for (;bin < lastbin;bin++) {
 341                         _Key key = bin->key;
 342
 343                         struct hashlistnode<_Key, _Val> *search;
 344                         if (!key)
 345                                 continue;
 346
 347                         unsigned int index = hash_function(key);
 348                         do {
 349                                 index &= capacitymask;
 350                                 search = &table[index];
 351                                 index++;
 352                         } while (search->key);
 353
 354                         search->key = key;
 355                         search->val = bin->val;
 356                 }
 357
 358                 _free(oldtable);
 359                 // Free the memory of the old hash table
 360         }
 361         double getLoadFactor() {return loadfactor;}
 362         unsigned int getCapacity() {return capacity;}
 363         struct hashlistnode<_Key, _Val> *table;
 364         struct hashlistnode<_Key, _Val> *zero;
 365         unsigned int capacity;
 366         unsigned int size;
 367 private:
 368         unsigned int capacitymask;
 369         unsigned int threshold;
 370         double loadfactor;
 371 };
 372
 373 #endif/* __HASHTABLE_H__ */