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);
67 #define HashTableImpl(Name, _Key, _Val, hash_function, equals) \
68 HashTable ## Name * allocHashTable ## Name(unsigned int initialcapacity, double factor) { \
69 HashTable ## Name * tab = (HashTable ## Name *)ourmalloc(sizeof(HashTable ## Name)); \
70 tab->table = (struct hashlistnode ## Name *)ourcalloc(initialcapacity, sizeof(struct hashlistnode ## Name)); \
72 tab->loadfactor = factor; \
73 tab->capacity = initialcapacity; \
74 tab->capacitymask = initialcapacity - 1; \
76 tab->threshold = (unsigned int)(initialcapacity * factor); \
81 void deleteHashTable ## Name(HashTable ## Name * tab) { \
82 ourfree(tab->table); \
88 void reset ## Name(HashTable ## Name * tab) { \
89 memset(tab->table, 0, tab->capacity * sizeof(struct hashlistnode ## Name)); \
97 void resetandfree ## Name(HashTable ## Name * tab) { \
98 for(unsigned int i=0;i<tab->capacity;i++) { \
99 struct hashlistnode ## Name *bin = &tab->table[i]; \
100 if (bin->key != NULL) { \
102 if (bin->val != NULL) { \
109 if (tab->zero->val != NULL) \
110 ourfree(tab->zero->val); \
111 ourfree(tab->zero); \
117 void put ## Name(HashTable ## Name * tab, _Key key, _Val val) { \
120 tab->zero=(struct hashlistnode ## Name *)ourmalloc(sizeof(struct hashlistnode ## Name)); \
123 tab->zero->key=key; \
124 tab->zero->val=val; \
128 if (tab->size > tab->threshold) \
129 resize ## Name (tab, tab->capacity << 1); \
131 struct hashlistnode ## Name *search; \
133 unsigned int index = hash_function(key); \
135 index &= tab->capacitymask; \
136 search = &tab->table[index]; \
137 if (!search->key) { \
140 if (equals(search->key, key)) { \
152 _Val get ## Name(const HashTable ## Name * tab, _Key key) { \
153 struct hashlistnode ## Name *search; \
157 return tab->zero->val; \
162 unsigned int oindex = hash_function(key) & tab->capacitymask; \
163 unsigned int index=oindex; \
165 search = &tab->table[index]; \
166 if (!search->key) { \
170 if (equals(search->key, key)) \
171 return search->val; \
173 index &= tab->capacitymask; \
180 _Val remove ## Name(HashTable ## Name * tab, _Key key) { \
181 struct hashlistnode ## Name *search; \
187 _Val v=tab->zero->val; \
188 ourfree(tab->zero); \
195 unsigned int index = hash_function(key); \
197 index &= tab->capacitymask; \
198 search = &tab->table[index]; \
199 if (!search->key) { \
203 if (equals(search->key, key)) { \
204 _Val v=search->val; \
205 search->val=(_Val) 1; \
215 unsigned int getSizeTable ## Name(const HashTable ## Name * tab) { \
220 bool contains ## Name(const HashTable ## Name * tab, _Key key) { \
221 struct hashlistnode ## Name *search; \
223 return tab->zero!=NULL; \
225 unsigned int index = hash_function(key); \
227 index &= tab->capacitymask; \
228 search = &tab->table[index]; \
229 if (!search->key) { \
233 if (equals(search->key, key)) \
240 void resize ## Name(HashTable ## Name * tab, unsigned int newsize) { \
241 struct hashlistnode ## Name *oldtable = tab->table; \
242 struct hashlistnode ## Name *newtable; \
243 unsigned int oldcapacity = tab->capacity; \
245 if ((newtable = (struct hashlistnode ## Name *)ourcalloc(newsize, sizeof(struct hashlistnode ## Name))) == NULL) { \
246 model_print("calloc error %s %d\n", __FILE__, __LINE__); \
247 exit(EXIT_FAILURE); \
250 tab->table = newtable; \
251 tab->capacity = newsize; \
252 tab->capacitymask = newsize - 1; \
254 tab->threshold = (unsigned int)(newsize * tab->loadfactor); \
256 struct hashlistnode ## Name *bin = &oldtable[0]; \
257 struct hashlistnode ## Name *lastbin = &oldtable[oldcapacity]; \
258 for (;bin < lastbin;bin++) { \
259 _Key key = bin->key; \
261 struct hashlistnode ## Name *search; \
265 unsigned int index = hash_function(key); \
267 index &= tab->capacitymask; \
268 search = &tab->table[index]; \
270 } while (search->key); \
273 search->val = bin->val; \
278 double getLoadFactor ## Name(HashTable ## Name * tab) {return tab->loadfactor;} \
279 unsigned int getCapacity ## Name(HashTable ## Name * tab) {return tab->capacity;}
284 #endif/* __HASHTABLE_H__ */