edits
[satune.git] / 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__ */