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