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