1 /* Copyright (c) 2015 Regents of the University of California
3 * Author: Brian Demsky <bdemsky@uci.edu>
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.
11 * @brief Hashtable. Standard chained bucket variety.
14 #ifndef __HASHTABLE_H__
15 #define __HASHTABLE_H__
23 #define HT_DEFAULT_FACTOR 0.75
24 #define HT_INITIAL_CAPACITY 16
27 * @brief A simple, custom hash table
29 * By default it is model_malloc, but you can pass in your own allocation
30 * functions. Note that This table does not support the value 0 (NULL) used as
31 * a key and is designed primarily with pointer-based keys in mind. Other
32 * primitive key types are supported only for non-zero values.
34 * @tparam _Key Type name for the key
35 * @tparam _Val Type name for the values to be stored
37 #define HashTableDef(Name, _Key, _Val)\
38 struct hashlistnode ## Name { \
43 struct HashTable ## Name { \
44 struct hashlistnode ## Name *table; \
45 struct hashlistnode ## Name *zero; \
46 unsigned int capacity; \
48 unsigned int capacitymask; \
49 unsigned int threshold; \
53 typedef struct HashTable ## Name HashTable ## Name; \
54 HashTable ## Name * allocHashTable ## Name(unsigned int initialcapacity, double factor); \
55 void deleteHashTable ## Name(HashTable ## Name * tab); \
56 void reset ## Name(HashTable ## Name * tab); \
57 void resetandfree ## Name(HashTable ## Name * tab); \
58 void put ## Name(HashTable ## Name * tab, _Key key, _Val val); \
59 _Val get ## Name(const HashTable ## Name * tab, _Key key); \
60 _Val remove ## Name(HashTable ## Name * tab, _Key key); \
61 unsigned int getSizeTable ## Name(const HashTable ## Name * tab); \
62 bool contains ## Name(const HashTable ## Name * tab, _Key key); \
63 void resize ## Name(HashTable ## Name * tab, unsigned int newsize); \
64 double getLoadFactor ## Name(HashTable ## Name * tab); \
65 unsigned int getCapacity ## Name(HashTable ## Name * tab); \
66 void resetAndDeleteHashTable ## Name(HashTable ## Name * tab);
68 #define HashTableImpl(Name, _Key, _Val, hash_function, equals, freefunction) \
69 HashTable ## Name * allocHashTable ## Name(unsigned int initialcapacity, double factor) { \
70 HashTable ## Name * tab = (HashTable ## Name *)ourmalloc(sizeof(HashTable ## Name)); \
71 tab->table = (struct hashlistnode ## Name *)ourcalloc(initialcapacity, sizeof(struct hashlistnode ## Name)); \
73 tab->loadfactor = factor; \
74 tab->capacity = initialcapacity; \
75 tab->capacitymask = initialcapacity - 1; \
77 tab->threshold = (unsigned int)(initialcapacity * factor); \
82 void deleteHashTable ## Name(HashTable ## Name * tab) { \
83 ourfree(tab->table); \
89 void resetAndDeleteHashTable ## Name(HashTable ## Name * tab) { \
90 for (uint i = 0; i < tab->capacity; i++) { \
91 struct hashlistnode ## Name *bin = &tab->table[i]; \
92 if (bin->key != NULL) { \
94 if (bin->val != NULL) { \
95 freefunction(bin->val); \
101 if (tab->zero->val != NULL) \
102 freefunction(tab->zero->val); \
103 ourfree(tab->zero); \
109 void reset ## Name(HashTable ## Name * tab) { \
110 memset(tab->table, 0, tab->capacity * sizeof(struct hashlistnode ## Name)); \
112 ourfree(tab->zero); \
118 void resetandfree ## Name(HashTable ## Name * tab) { \
119 for (unsigned int i = 0; i < tab->capacity; i++) { \
120 struct hashlistnode ## Name *bin = &tab->table[i]; \
121 if (bin->key != NULL) { \
123 if (bin->val != NULL) { \
130 if (tab->zero->val != NULL) \
131 ourfree(tab->zero->val); \
132 ourfree(tab->zero); \
138 void put ## Name(HashTable ## Name * tab, _Key key, _Val val) { \
141 tab->zero = (struct hashlistnode ## Name *)ourmalloc(sizeof(struct hashlistnode ## Name)); \
144 tab->zero->key = key; \
145 tab->zero->val = val; \
149 if (tab->size > tab->threshold) \
150 resize ## Name (tab, tab->capacity << 1); \
152 struct hashlistnode ## Name *search; \
154 unsigned int index = hash_function(key); \
156 index &= tab->capacitymask; \
157 search = &tab->table[index]; \
158 if (!search->key) { \
161 if (equals(search->key, key)) { \
173 _Val get ## Name(const HashTable ## Name * tab, _Key key) { \
174 struct hashlistnode ## Name *search; \
178 return tab->zero->val; \
183 unsigned int oindex = hash_function(key) & tab->capacitymask; \
184 unsigned int index = oindex; \
186 search = &tab->table[index]; \
187 if (!search->key) { \
191 if (equals(search->key, key)) \
192 return search->val; \
194 index &= tab->capacitymask; \
195 if (index == oindex) \
201 _Val remove ## Name(HashTable ## Name * tab, _Key key) { \
202 struct hashlistnode ## Name *search; \
208 _Val v = tab->zero->val; \
209 ourfree(tab->zero); \
216 unsigned int index = hash_function(key); \
218 index &= tab->capacitymask; \
219 search = &tab->table[index]; \
220 if (!search->key) { \
224 if (equals(search->key, key)) { \
225 _Val v = search->val; \
226 search->val = (_Val) 1; \
236 unsigned int getSizeTable ## Name(const HashTable ## Name * tab) { \
241 bool contains ## Name(const HashTable ## Name * tab, _Key key) { \
242 struct hashlistnode ## Name *search; \
244 return tab->zero != NULL; \
246 unsigned int index = hash_function(key); \
248 index &= tab->capacitymask; \
249 search = &tab->table[index]; \
250 if (!search->key) { \
254 if (equals(search->key, key)) \
261 void resize ## Name(HashTable ## Name * tab, unsigned int newsize) { \
262 struct hashlistnode ## Name *oldtable = tab->table; \
263 struct hashlistnode ## Name *newtable; \
264 unsigned int oldcapacity = tab->capacity; \
266 if ((newtable = (struct hashlistnode ## Name *)ourcalloc(newsize, sizeof(struct hashlistnode ## Name))) == NULL) { \
267 model_print("calloc error %s %d\n", __FILE__, __LINE__); \
268 exit(EXIT_FAILURE); \
271 tab->table = newtable; \
272 tab->capacity = newsize; \
273 tab->capacitymask = newsize - 1; \
275 tab->threshold = (unsigned int)(newsize * tab->loadfactor); \
277 struct hashlistnode ## Name *bin = &oldtable[0]; \
278 struct hashlistnode ## Name *lastbin = &oldtable[oldcapacity]; \
279 for (; bin < lastbin; bin++) { \
280 _Key key = bin->key; \
282 struct hashlistnode ## Name *search; \
286 unsigned int index = hash_function(key); \
288 index &= tab->capacitymask; \
289 search = &tab->table[index]; \
291 } while (search->key); \
294 search->val = bin->val; \
299 double getLoadFactor ## Name(HashTable ## Name * tab) {return tab->loadfactor;} \
300 unsigned int getCapacity ## Name(HashTable ## Name * tab) {return tab->capacity;}
305 #endif/* __HASHTABLE_H__ */