Finish rewriting Set/Table/Vector
[satune.git] / src / hashtable.h
1 /*      Copyright (c) 2015 Regents of the University of California
2  *
3  *      Author: Brian Demsky <bdemsky@uci.edu>
4  *
5  *      This program is free software; you can redistribute it and/or
6  *      modify it under the terms of the GNU General Public License
7  *      version 2 as published by the Free Software Foundation.
8  */
9
10 /** @file hashtable.h
11  *  @brief Hashtable.  Standard chained bucket variety.
12  */
13
14 #ifndef __HASHTABLE_H__
15 #define __HASHTABLE_H__
16
17 #include <stdlib.h>
18 #include <stdio.h>
19 #include <string.h>
20 #include "mymemory.h"
21 #include "common.h"
22
23 /**
24  * @brief A simple, custom hash table
25  *
26  * By default it is model_malloc, but you can pass in your own allocation
27  * functions. Note that this table does not support the value 0 (NULL) used as
28  * a key and is designed primarily with pointer-based keys in mind. Other
29  * primitive key types are supported only for non-zero values.
30  *
31  * @tparam _Key    Type name for the key
32  * @tparam _Val    Type name for the values to be stored
33  */
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 freeHashTable ## 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 freeHashTable ## 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__ */