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 A simple, custom hash table
  25  *
  26  * By default it is model_malloc, but you can pass in your own allocation
  27  * functions. Note that this table does not support the value 0 (NULL) used as
  28  * a key and is designed primarily with pointer-based keys in mind. Other
  29  * primitive key types are supported only for non-zero values.
  30  *
  31  * @tparam _Key    Type name for the key
  32  * @tparam _Val    Type name for the values to be stored
  33  * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
  34  *                 manipulation and storage.
  35  * @tparam _Shift  Logical shift to apply to all keys. Default 0.
  36  */
  37 #define HashTableDef(Name, _Key, _Val, _KeyInt, _Shift, hash_function, equals)\
  38         struct hashlistnode ## Name {                                                                                                                                                                   \
  39         _Key key;                                                                                                                                                                                                                                                       \
  40         _Val val;                                                                                                                                                                                                                                                       \
  41         };                                                                                                                                                                                                                                                                              \
  42                                                                                                                                                                                                                                                                                                 \
  43         struct HashTable ## Name {                                                                                                                                                                              \
  44         struct hashlistnode ## Name *table;                                                                                                                                             \
  45         struct hashlistnode ## Name  *zero;                                                                                                                                             \
  46         unsigned int capacity;                                                                                                                                                                                          \
  47         unsigned int size;                                                                                                                                                                                                              \
  48         unsigned int capacitymask;                                                                                                                                                                              \
  49         unsigned int threshold;                                                                                                                                                                                         \
  50         double loadfactor;                                                                                                                                                                                                              \
  51         };                                                                                                                                                                                                                                                                              \
  52                                                                                                                                                                                                                                                                                                 \
  53         typedef struct HashTable ## Name HashTable ## Name;                                                                             \
  54         HashTable ## Name * allocHashTable ## Name(unsigned int initialcapacity, double factor); \
  55         void freeHashTable ## Name(HashTable ## Name * tab);                                                                    \
  56         void reset ## Name(HashTable ## Name * tab);                                                                                                    \
  57         void resetandfree ## Name(HashTable ## Name * tab);                                                                             \
  58         void put ## Name(HashTable ## Name * tab, _Key key, _Val val);                          \
  59         _Val get ## Name(HashTable ## Name * tab, _Key key) const;                                              \
  60         _Val remove ## Name(HashTable ## Name * tab, _Key key);                                                         \
  61         unsigned int getSize ## Name(HashTable ## Name * tab, ) const;                          \
  62         bool contains ## Name(HashTable ## Name * tab, _Key key) const;                         \
  63         void resize ## Name(HashTable ## Name * tab, unsigned int newsize);             \
  64         double getLoadFactor ## Name(HashTable ## Name * tab);                                                          \
  65         unsigned int getCapacity ## Name(HashTable ## Name * tab);
  66
  67 #define HashTableDef(Name, _Key, _Val, _KeyInt, _Shift, hash_function, equals) \
  68         HashTable ## Name * allocHashTable ## Name(unsigned int initialcapacity, double factor) {       \
  69                 HashTable ## Name * tab = (HashTable ## Name *) ourmalloc(sizeof(HashTable ## Name));   \
  70                 tab -> table = (struct hashlistnode ## Name *) ourcalloc(initialcapacity, sizeof(struct hashlistnode ## Name)); \
  71                 tab->zero = NULL;                                                                                                                                                                                                               \
  72                 tab->loadfactor = factor;                                                                                                                                                                               \
  73                 tab->capacity = initialcapacity;                                                                                                                                                \
  74                 tab->capacitymask = initialcapacity - 1;                                                                                                                \
  75                                                                                                                                                                                                                                                                                                 \
  76                 tab->threshold = (unsigned int)(initialcapacity * loadfactor);                  \
  77                 tab->size = 0;                                                                                                                                                                                                                  \
  78         }                                                                                                                                                                                                                                                                                       \
  79                                                                                                                                                                                                                                                                                                 \
  80         void freeHashTable ## Name(HashTable ## Name * tab) {                                                                           \
  81                 ourfree(tab->table);                                                                                                                                                                                            \
  82                 if (tab->zero)                                                                                                                                                                                                                  \
  83                         ourfree(tab->zero);                                                                                                                                                                                             \
  84                 ourfree(tab);                                                                                                                                                                                                                           \
  85         }                                                                                                                                                                                                                                                                                       \
  86                                                                                                                                                                                                                                                                                                 \
  87         void reset ## Name(HashTable ## Name * tab) {                                                                                                   \
  88                 memset(tab->table, 0, capacity * sizeof(struct hashlistnode ## Name)); \
  89                 if (tab->zero) {                                                                                                                                                                                                                \
  90                         ourfree(tab->zero);                                                                                                                                                                                             \
  91                         tab->zero = NULL;                                                                                                                                                                                                       \
  92                 }                                                                                                                                                                                                                                                                               \
  93                 tab->size = 0;                                                                                                                                                                                                                  \
  94         }                                                                                                                                                                                                                                                                                       \
  95                                                                                                                                                                                                                                                                                                 \
  96         void resetandfree ## Name(HashTable ## Name * tab) {                                                                    \
  97                 for(unsigned int i=0;i<tab->capacity;i++) {                                                                                                     \
  98                         struct hashlistnode ## Name *bin = &tab->table[i];                                                              \
  99                         if (bin->key != NULL) {                                                                                                                                                                         \
 100                                 bin->key = NULL;                                                                                                                                                                                                \
 101                                 if (bin->val != NULL) {                                                                                                                                                                 \
 102                                         ourfree(bin->val);                                                                                                                                                                              \
 103                                         bin->val = NULL;                                                                                                                                                                                        \
 104                                 }                                                                                                                                                                                                                                                               \
 105                         }                                                                                                                                                                                                                                                                       \
 106                 }                                                                                                                                                                                                                                                                               \
 107                 if (tab->zero) {                                                                                                                                                                                                                \
 108                         if (tab->zero->val != NULL)                                                                                                                                                             \
 109                                 ourfree(tab->zero->val);                                                                                                                                                                \
 110                         ourfree(tab->zero);                                                                                                                                                                                             \
 111                         tab->zero = NULL;                                                                                                                                                                                                       \
 112                 }                                                                                                                                                                                                                                                                               \
 113                 tab->size = 0;                                                                                                                                                                                                                  \
 114         }                                                                                                                                                                                                                                                                                       \
 115                                                                                                                                                                                                                                                                                                 \
 116         void put ## Name(HashTable ## Name * tab, _Key key, _Val val) {                         \
 117                 if (!key) {                                                                                                                                                                                                                                     \
 118                         if (!tab->zero) {                                                                                                                                                                                                       \
 119                                 tab->zero=(struct hashlistnode ## Name *)ourmalloc(sizeof(struct hashlistnode ## Name)); \
 120                                 tab->size++;                                                                                                                                                                                                            \
 121                         }                                                                                                                                                                                                                                                                       \
 122                         tab->zero->key=key;                                                                                                                                                                                             \
 123                         tab->zero->val=val;                                                                                                                                                                                             \
 124                         return;                                                                                                                                                                                                                                         \
 125                 }                                                                                                                                                                                                                                                                               \
 126                                                                                                                                                                                                                                                                                                 \
 127                 if (tab->size > tab->threshold)                                                                                                                                                                 \
 128                         resize(tab->capacity << 1);                                                                                                                                                             \
 129                                                                                                                                                                                                                                                                                                 \
 130                 struct hashlistnode ## Name *search;                                                                                                                            \
 131                                                                                                                                                                                                                                                                                                 \
 132                 unsigned int index = hash_function(key);                                                                                                                \
 133                 do {                                                                                                                                                                                                                                                            \
 134                         index &= tab->capacitymask;                                                                                                                                                             \
 135                         search = &tab->table[index];                                                                                                                                                    \
 136                         if (!search->key) {                                                                                                                                                                                             \
 137                                 break;                                                                                                                                                                                                                                  \
 138                         }                                                                                                                                                                                                                                                                       \
 139                         if (equals(search->key, key)) {                                                                                                                                         \
 140                                 search->val = val;                                                                                                                                                                                      \
 141                                 return;                                                                                                                                                                                                                                 \
 142                         }                                                                                                                                                                                                                                                                       \
 143                         index++;                                                                                                                                                                                                                                        \
 144                 } while (true);                                                                                                                                                                                                                 \
 145                                                                                                                                                                                                                                                                                                 \
 146                 search->key = key;                                                                                                                                                                                                      \
 147                 search->val = val;                                                                                                                                                                                                      \
 148                 tab->size++;                                                                                                                                                                                                                            \
 149         }                                                                                                                                                                                                                                                                                       \
 150                                                                                                                                                                                                                                                                                                 \
 151         _Val get ## Name(HashTable ## Name * tab, _Key key) const {                                             \
 152                 struct hashlistnode ## Name *search;                                                                                                                            \
 153                                                                                                                                                                                                                                                                                                 \
 154                 if (!key) {                                                                                                                                                                                                                                     \
 155                         if (tab->zero)                                                                                                                                                                                                          \
 156                                 return tab->zero->val;                                                                                                                                                                  \
 157                         else                                                                                                                                                                                                                                                    \
 158                                 return (_Val) 0;                                                                                                                                                                                                \
 159                 }                                                                                                                                                                                                                                                                               \
 160                                                                                                                                                                                                                                                                                                 \
 161                 unsigned int oindex = hash_function(key) & tab->capacitymask;                           \
 162                 unsigned int index=oindex;                                                                                                                                                                      \
 163                 do {                                                                                                                                                                                                                                                            \
 164                         search = &tab->table[index];                                                                                                                                                    \
 165                         if (!search->key) {                                                                                                                                                                                             \
 166                                 if (!search->val)                                                                                                                                                                                               \
 167                                         break;                                                                                                                                                                                                                          \
 168                         } else                                                                                                                                                                                                                                          \
 169                                 if (equals(search->key, key))                                                                                                                                           \
 170                                         return search->val;                                                                                                                                                                             \
 171                         index++;                                                                                                                                                                                                                                        \
 172                         index &= tab->capacitymask;                                                                                                                                                             \
 173                         if (index==oindex)                                                                                                                                                                                              \
 174                                 break;                                                                                                                                                                                                                                  \
 175                 } while (true);                                                                                                                                                                                                                 \
 176                 return (_Val)0;                                                                                                                                                                                                                 \
 177         }                                                                                                                                                                                                                                                                                       \
 178                                                                                                                                                                                                                                                                                                 \
 179         _Val remove ## Name(HashTable ## Name * tab, _Key key) {                                                        \
 180                 struct hashlistnode ## Name *search;                                                                                                                            \
 181                                                                                                                                                                                                                                                                                                 \
 182                 if (!key) {                                                                                                                                                                                                                                     \
 183                         if (!tab->zero) {                                                                                                                                                                                                       \
 184                                 return (_Val)0;                                                                                                                                                                                                 \
 185                         } else {                                                                                                                                                                                                                                        \
 186                                 _Val v=tab->zero->val;                                                                                                                                                                  \
 187                                 ourfree(tab->zero);                                                                                                                                                                                     \
 188                                 tab->zero=NULL;                                                                                                                                                                                                 \
 189                                 tab->size--;                                                                                                                                                                                                            \
 190                                 return v;                                                                                                                                                                                                                               \
 191                         }                                                                                                                                                                                                                                                                       \
 192                 }                                                                                                                                                                                                                                                                               \
 193                                                                                                                                                                                                                                                                                                 \
 194                 unsigned int index = hash_function(key);                                                                                                                \
 195                 do {                                                                                                                                                                                                                                                            \
 196                         index &= tab->capacitymask;                                                                                                                                                             \
 197                         search = &tab->table[index];                                                                                                                                                    \
 198                         if (!search->key) {                                                                                                                                                                                             \
 199                                 if (!search->val)                                                                                                                                                                                               \
 200                                         break;                                                                                                                                                                                                                          \
 201                         } else                                                                                                                                                                                                                                          \
 202                                 if (equals(search->key, key)) {                                                                                                                                 \
 203                                         _Val v=search->val;                                                                                                                                                                             \
 204                                         search->val=(_Val) 1;                                                                                                                                                                   \
 205                                         search->key=0;                                                                                                                                                                                          \
 206                                         tab->size--;                                                                                                                                                                                                    \
 207                                         return v;                                                                                                                                                                                                                       \
 208                                 }                                                                                                                                                                                                                                                               \
 209                         index++;                                                                                                                                                                                                                                        \
 210                 } while (true);                                                                                                                                                                                                                 \
 211                 return (_Val)0;                                                                                                                                                                                                                 \
 212         }                                                                                                                                                                                                                                                                                       \
 213                                                                                                                                                                                                                                                                                                 \
 214         unsigned int getSize ## Name(HashTable ## Name * tab, ) const {                         \
 215                 return tab->size;                                                                                                                                                                                                               \
 216         }                                                                                                                                                                                                                                                                                       \
 217                                                                                                                                                                                                                                                                                                 \
 218                                                                                                                                                                                                                                                                                                 \
 219         bool contains ## Name(HashTable ## Name * tab, _Key key) const {                        \
 220                 struct hashlistnode ## Name *search;                                                                                                                            \
 221                 if (!key) {                                                                                                                                                                                                                                     \
 222                         return tab->zero!=NULL;                                                                                                                                                                         \
 223                 }                                                                                                                                                                                                                                                                               \
 224                 unsigned int index = hash_function(key);                                                                                                                \
 225                 do {                                                                                                                                                                                                                                                            \
 226                         index &= tab->capacitymask;                                                                                                                                                             \
 227                         search = &tab->table[index];                                                                                                                                                    \
 228                         if (!search->key) {                                                                                                                                                                                             \
 229                                 if (!search->val)                                                                                                                                                                                               \
 230                                         break;                                                                                                                                                                                                                          \
 231                         } else                                                                                                                                                                                                                                          \
 232                                 if (equals(search->key, key))                                                                                                                                           \
 233                                         return true;                                                                                                                                                                                                    \
 234                         index++;                                                                                                                                                                                                                                        \
 235                 } while (true);                                                                                                                                                                                                                 \
 236                 return false;                                                                                                                                                                                                                           \
 237         }                                                                                                                                                                                                                                                                                       \
 238                                                                                                                                                                                                                                                                                                 \
 239         void resize ## Name(HashTable ## Name * tab, unsigned int newsize) {    \
 240                 struct hashlistnode ## Name *oldtable = tab->table;                                                                     \
 241                 struct hashlistnode ## Name *newtable;                                                                                                                  \
 242                 unsigned int oldcapacity = tab->capacity;                                                                                                               \
 243                                                                                                                                                                                                                                                                                                 \
 244                 if ((newtable = (struct hashlistnode ## Name *)ourcalloc(newsize, sizeof(struct hashlistnode ## Name))) == NULL) { \
 245                         model_print("calloc error %s %d\n", __FILE__, __LINE__);                                        \
 246                         exit(EXIT_FAILURE);                                                                                                                                                                                             \
 247                 }                                                                                                                                                                                                                                                                               \
 248                                                                                                                                                                                                                                                                                                 \
 249                 tab->table = newtable;                                                                                                                                                                                  \
 250                 tab->capacity = newsize;                                                                                                                                                                                \
 251                 tab->capacitymask = newsize - 1;                                                                                                                                                \
 252                                                                                                                                                                                                                                                                                                 \
 253                 tab->threshold = (unsigned int)(newsize * loadfactor);                                                  \
 254                                                                                                                                                                                                                                                                                                 \
 255                 struct hashlistnode ## Name *bin = &oldtable[0];                                                                                \
 256                 struct hashlistnode ## Name *lastbin = &oldtable[oldcapacity];                  \
 257                 for (;bin < lastbin;bin++) {                                                                                                                                                            \
 258                         _Key key = bin->key;                                                                                                                                                                                    \
 259                                                                                                                                                                                                                                                                                                 \
 260                         struct hashlistnode ## Name *search;                                                                                                                    \
 261                         if (!key)                                                                                                                                                                                                                                       \
 262                                 continue;                                                                                                                                                                                                                               \
 263                                                                                                                                                                                                                                                                                                 \
 264                         unsigned int index = hash_function(key);                                                                                                        \
 265                         do {                                                                                                                                                                                                                                                    \
 266                                 index &= tab->capacitymask;                                                                                                                                                     \
 267                                 search = &tab->table[index];                                                                                                                                            \
 268                                 index++;                                                                                                                                                                                                                                \
 269                         } while (search->key);                                                                                                                                                                          \
 270                                                                                                                                                                                                                                                                                                 \
 271                         search->key = key;                                                                                                                                                                                              \
 272                         search->val = bin->val;                                                                                                                                                                         \
 273                 }                                                                                                                                                                                                                                                                               \
 274                                                                                                                                                                                                                                                                                                 \
 275                 ourfree(oldtable);                                                                                                                                                                                                      \
 276         }                                                                                                                                                                                                                                                                                       \
 277         double getLoadFactor ## Name(HashTable ## Name * tab) {return tab->loadfactor;} \
 278         unsigned int getCapacity ## Name(HashTable ## Name * tab) {return tab->capacity;}
 279
 280
 281
 282
 283 #endif/* __HASHTABLE_H__ */