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__
24 * @brief A simple, custom hash table
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.
31 * @tparam _Key Type name for the key
32 * @tparam _Val Type name for the values to be stored
34 #define HashTableDef(Name, _Key, _Val, hash_function, equals)\
35 struct hashlistnode ## Name { \
40 struct HashTable ## Name { \
41 struct hashlistnode ## Name *table; \
42 struct hashlistnode ## Name *zero; \
43 unsigned int capacity; \
45 unsigned int capacitymask; \
46 unsigned int threshold; \
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);
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)); \
69 tab->loadfactor = factor; \
70 tab->capacity = initialcapacity; \
71 tab->capacitymask = initialcapacity - 1; \
73 tab->threshold = (unsigned int)(initialcapacity * factor); \
78 void deleteHashTable ## Name(HashTable ## Name * tab) { \
79 ourfree(tab->table); \
85 void reset ## Name(HashTable ## Name * tab) { \
86 memset(tab->table, 0, tab->capacity * sizeof(struct hashlistnode ## Name)); \
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) { \
99 if (bin->val != NULL) { \
106 if (tab->zero->val != NULL) \
107 ourfree(tab->zero->val); \
108 ourfree(tab->zero); \
114 void put ## Name(HashTable ## Name * tab, _Key key, _Val val) { \
117 tab->zero=(struct hashlistnode ## Name *)ourmalloc(sizeof(struct hashlistnode ## Name)); \
120 tab->zero->key=key; \
121 tab->zero->val=val; \
125 if (tab->size > tab->threshold) \
126 resize ## Name (tab, tab->capacity << 1); \
128 struct hashlistnode ## Name *search; \
130 unsigned int index = hash_function(key); \
132 index &= tab->capacitymask; \
133 search = &tab->table[index]; \
134 if (!search->key) { \
137 if (equals(search->key, key)) { \
149 _Val get ## Name(const HashTable ## Name * tab, _Key key) { \
150 struct hashlistnode ## Name *search; \
154 return tab->zero->val; \
159 unsigned int oindex = hash_function(key) & tab->capacitymask; \
160 unsigned int index=oindex; \
162 search = &tab->table[index]; \
163 if (!search->key) { \
167 if (equals(search->key, key)) \
168 return search->val; \
170 index &= tab->capacitymask; \
177 _Val remove ## Name(HashTable ## Name * tab, _Key key) { \
178 struct hashlistnode ## Name *search; \
184 _Val v=tab->zero->val; \
185 ourfree(tab->zero); \
192 unsigned int index = hash_function(key); \
194 index &= tab->capacitymask; \
195 search = &tab->table[index]; \
196 if (!search->key) { \
200 if (equals(search->key, key)) { \
201 _Val v=search->val; \
202 search->val=(_Val) 1; \
212 unsigned int getSizeTable ## Name(const HashTable ## Name * tab) { \
217 bool contains ## Name(const HashTable ## Name * tab, _Key key) { \
218 struct hashlistnode ## Name *search; \
220 return tab->zero!=NULL; \
222 unsigned int index = hash_function(key); \
224 index &= tab->capacitymask; \
225 search = &tab->table[index]; \
226 if (!search->key) { \
230 if (equals(search->key, key)) \
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; \
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); \
247 tab->table = newtable; \
248 tab->capacity = newsize; \
249 tab->capacitymask = newsize - 1; \
251 tab->threshold = (unsigned int)(newsize * tab->loadfactor); \
253 struct hashlistnode ## Name *bin = &oldtable[0]; \
254 struct hashlistnode ## Name *lastbin = &oldtable[oldcapacity]; \
255 for (;bin < lastbin;bin++) { \
256 _Key key = bin->key; \
258 struct hashlistnode ## Name *search; \
262 unsigned int index = hash_function(key); \
264 index &= tab->capacitymask; \
265 search = &tab->table[index]; \
267 } while (search->key); \
270 search->val = bin->val; \
275 double getLoadFactor ## Name(HashTable ## Name * tab) {return tab->loadfactor;} \
276 unsigned int getCapacity ## Name(HashTable ## Name * tab) {return tab->capacity;}
281 #endif/* __HASHTABLE_H__ */