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
  67 #define HashTableImpl(Name, _Key, _Val, 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 * factor);          \
  77                 tab->size = 0;                                                      \
  78                 return tab;                                                         \
  79         }                                                                     \
  80                                                                         \
  81         void deleteHashTable ## Name(HashTable ## Name * tab) {                 \
  82                 ourfree(tab->table);                                                \
  83                 if (tab->zero)                                                      \
  84                         ourfree(tab->zero);                                               \
  85                 ourfree(tab);                                                       \
  86         }                                                                     \
  87                                                                         \
  88         void reset ## Name(HashTable ## Name * tab) {                         \
  89                 memset(tab->table, 0, tab->capacity * sizeof(struct hashlistnode ## Name)); \
  90                 if (tab->zero) {                                                    \
  91                         ourfree(tab->zero);                                               \
  92                         tab->zero = NULL;                                                 \
  93                 }                                                                   \
  94                 tab->size = 0;                                                      \
  95         }                                                                     \
  96                                                                         \
  97         void resetandfree ## Name(HashTable ## Name * tab) {                  \
  98                 for(unsigned int i=0;i<tab->capacity;i++) {                         \
  99                         struct hashlistnode ## Name *bin = &tab->table[i];                \
 100                         if (bin->key != NULL) {                                           \
 101                                 bin->key = NULL;                                                \
 102                                 if (bin->val != NULL) {                                         \
 103                                         ourfree(bin->val);                                            \
 104                                         bin->val = NULL;                                              \
 105                                 }                                                               \
 106                         }                                                                 \
 107                 }                                                                   \
 108                 if (tab->zero) {                                                    \
 109                         if (tab->zero->val != NULL)                                       \
 110                                 ourfree(tab->zero->val);                                        \
 111                         ourfree(tab->zero);                                               \
 112                         tab->zero = NULL;                                                 \
 113                 }                                                                   \
 114                 tab->size = 0;                                                      \
 115         }                                                                     \
 116                                                                         \
 117         void put ## Name(HashTable ## Name * tab, _Key key, _Val val) {       \
 118                 if (!key) {                                                         \
 119                         if (!tab->zero) {                                                 \
 120                                 tab->zero=(struct hashlistnode ## Name *)ourmalloc(sizeof(struct hashlistnode ## Name)); \
 121                                 tab->size++;                                                    \
 122                         }                                                                 \
 123                         tab->zero->key=key;                                               \
 124                         tab->zero->val=val;                                               \
 125                         return;                                                           \
 126                 }                                                                   \
 127                                                                         \
 128                 if (tab->size > tab->threshold)                                     \
 129                         resize ## Name (tab, tab->capacity << 1);                         \
 130                                                                         \
 131                 struct hashlistnode ## Name *search;                                \
 132                                                                         \
 133                 unsigned int index = hash_function(key);                            \
 134                 do {                                                                \
 135                         index &= tab->capacitymask;                                       \
 136                         search = &tab->table[index];                                      \
 137                         if (!search->key) {                                               \
 138                                 break;                                                          \
 139                         }                                                                 \
 140                         if (equals(search->key, key)) {                                   \
 141                                 search->val = val;                                              \
 142                                 return;                                                         \
 143                         }                                                                 \
 144                         index++;                                                          \
 145                 } while (true);                                                     \
 146                                                                         \
 147                 search->key = key;                                                  \
 148                 search->val = val;                                                  \
 149                 tab->size++;                                                        \
 150         }                                                                     \
 151                                                                         \
 152         _Val get ## Name(const HashTable ## Name * tab, _Key key) {         \
 153                 struct hashlistnode ## Name *search;                                \
 154                                                                         \
 155                 if (!key) {                                                         \
 156                         if (tab->zero)                                                    \
 157                                 return tab->zero->val;                                          \
 158                         else                                                              \
 159                                 return (_Val) 0;                                                \
 160                 }                                                                   \
 161                                                                         \
 162                 unsigned int oindex = hash_function(key) & tab->capacitymask;       \
 163                 unsigned int index=oindex;                                          \
 164                 do {                                                                \
 165                         search = &tab->table[index];                                      \
 166                         if (!search->key) {                                               \
 167                                 if (!search->val)                                               \
 168                                         break;                                                        \
 169                         } else                                                            \
 170                         if (equals(search->key, key))                                   \
 171                                 return search->val;                                           \
 172                         index++;                                                          \
 173                         index &= tab->capacitymask;                                       \
 174                         if (index==oindex)                                                \
 175                                 break;                                                          \
 176                 } while (true);                                                     \
 177                 return (_Val)0;                                                     \
 178         }                                                                     \
 179                                                                         \
 180         _Val remove ## Name(HashTable ## Name * tab, _Key key) {              \
 181                 struct hashlistnode ## Name *search;                                \
 182                                                                         \
 183                 if (!key) {                                                         \
 184                         if (!tab->zero) {                                                 \
 185                                 return (_Val)0;                                                 \
 186                         } else {                                                          \
 187                                 _Val v=tab->zero->val;                                          \
 188                                 ourfree(tab->zero);                                             \
 189                                 tab->zero=NULL;                                                 \
 190                                 tab->size--;                                                    \
 191                                 return v;                                                       \
 192                         }                                                                 \
 193                 }                                                                   \
 194                                                                         \
 195                 unsigned int index = hash_function(key);                            \
 196                 do {                                                                \
 197                         index &= tab->capacitymask;                                       \
 198                         search = &tab->table[index];                                      \
 199                         if (!search->key) {                                               \
 200                                 if (!search->val)                                               \
 201                                         break;                                                        \
 202                         } else                                                            \
 203                         if (equals(search->key, key)) {                                 \
 204                                 _Val v=search->val;                                           \
 205                                 search->val=(_Val) 1;                                         \
 206                                 search->key=0;                                                \
 207                                 tab->size--;                                                  \
 208                                 return v;                                                     \
 209                         }                                                               \
 210                         index++;                                                          \
 211                 } while (true);                                                     \
 212                 return (_Val)0;                                                     \
 213         }                                                                     \
 214                                                                         \
 215         unsigned int getSizeTable ## Name(const HashTable ## Name * tab) {    \
 216                 return tab->size;                                                   \
 217         }                                                                     \
 218                                                                         \
 219                                                                         \
 220         bool contains ## Name(const HashTable ## Name * tab, _Key key) {      \
 221                 struct hashlistnode ## Name *search;                                \
 222                 if (!key) {                                                         \
 223                         return tab->zero!=NULL;                                           \
 224                 }                                                                   \
 225                 unsigned int index = hash_function(key);                            \
 226                 do {                                                                \
 227                         index &= tab->capacitymask;                                       \
 228                         search = &tab->table[index];                                      \
 229                         if (!search->key) {                                               \
 230                                 if (!search->val)                                               \
 231                                         break;                                                        \
 232                         } else                                                            \
 233                         if (equals(search->key, key))                                   \
 234                                 return true;                                                  \
 235                         index++;                                                          \
 236                 } while (true);                                                     \
 237                 return false;                                                       \
 238         }                                                                     \
 239                                                                         \
 240         void resize ## Name(HashTable ## Name * tab, unsigned int newsize) {  \
 241                 struct hashlistnode ## Name *oldtable = tab->table;                 \
 242                 struct hashlistnode ## Name *newtable;                              \
 243                 unsigned int oldcapacity = tab->capacity;                           \
 244                                                                         \
 245                 if ((newtable = (struct hashlistnode ## Name *)ourcalloc(newsize, sizeof(struct hashlistnode ## Name))) == NULL) { \
 246                         model_print("calloc error %s %d\n", __FILE__, __LINE__);          \
 247                         exit(EXIT_FAILURE);                                               \
 248                 }                                                                   \
 249                                                                         \
 250                 tab->table = newtable;                                              \
 251                 tab->capacity = newsize;                                            \
 252                 tab->capacitymask = newsize - 1;                                    \
 253                                                                         \
 254                 tab->threshold = (unsigned int)(newsize * tab->loadfactor);         \
 255                                                                         \
 256                 struct hashlistnode ## Name *bin = &oldtable[0];                    \
 257                 struct hashlistnode ## Name *lastbin = &oldtable[oldcapacity];      \
 258                 for (;bin < lastbin;bin++) {                                        \
 259                         _Key key = bin->key;                                              \
 260                                                                         \
 261                         struct hashlistnode ## Name *search;                              \
 262                         if (!key)                                                         \
 263                                 continue;                                                       \
 264                                                                         \
 265                         unsigned int index = hash_function(key);                          \
 266                         do {                                                              \
 267                                 index &= tab->capacitymask;                                     \
 268                                 search = &tab->table[index];                                    \
 269                                 index++;                                                        \
 270                         } while (search->key);                                            \
 271                                                                         \
 272                         search->key = key;                                                \
 273                         search->val = bin->val;                                           \
 274                 }                                                                   \
 275                                                                         \
 276                 ourfree(oldtable);                                                  \
 277         }                                                                     \
 278         double getLoadFactor ## Name(HashTable ## Name * tab) {return tab->loadfactor;} \
 279         unsigned int getCapacity ## Name(HashTable ## Name * tab) {return tab->capacity;}
 280
 281
 282
 283
 284 #endif/* __HASHTABLE_H__ */