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