Base Commit
[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 HashTable node
25  *
26  * @tparam _Key    Type name for the key
27  * @tparam _Val    Type name for the values to be stored
28  */
29 template<typename _Key, typename _Val>
30 struct hashlistnode {
31         _Key key;
32         _Val val;
33 };
34
35 template<typename _Key, int _Shift, typename _KeyInt>
36 inline unsigned int default_hash_function(_Key hash) {
37         return (unsigned int)(((_KeyInt)hash) >> _Shift);
38 }
39
40 template<typename _Key>
41 inline bool default_equals(_Key key1, _Key key2) {
42         return key1 == key2;
43 }
44
45 /**
46  * @brief A simple, custom hash table
47  *
48  * By default it is model_malloc, but you can pass in your own allocation
49  * functions. Note that this table does not support the value 0 (NULL) used as
50  * a key and is designed primarily with pointer-based keys in mind. Other
51  * primitive key types are supported only for non-zero values.
52  *
53  * @tparam _Key    Type name for the key
54  * @tparam _Val    Type name for the values to be stored
55  * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
56  *                 manipulation and storage.
57  * @tparam _Shift  Logical shift to apply to all keys. Default 0.
58  * @tparam _malloc Provide your own 'malloc' for the table, or default to
59  *                 model_malloc.
60  * @tparam _calloc Provide your own 'calloc' for the table, or default to
61  *                 model_malloc.
62  * @tparam _free   Provide your own 'free' for the table, or default to
63  *                 model_malloc.
64  */
65 template<typename _Key, typename _Val, typename _KeyInt, int _Shift = 0, void * (* _malloc)(size_t) = model_malloc, void * (* _calloc)(size_t, size_t) = model_calloc, void (*_free)(void *) = model_free, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
66 class HashTable {
67 public:
68         /**
69          * @brief Hash table constructor
70          * @param initialcapacity Sets the initial capacity of the hash table.
71          * Default size 1024.
72          * @param factor Sets the percentage full before the hashtable is
73          * resized. Default ratio 0.5.
74          */
75         HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
76                 // Allocate space for the hash table
77                 table = (struct hashlistnode<_Key, _Val> *)_calloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
78                 zero = NULL;
79                 loadfactor = factor;
80                 capacity = initialcapacity;
81                 capacitymask = initialcapacity - 1;
82
83                 threshold = (unsigned int)(initialcapacity * loadfactor);
84                 size = 0;                                                                                                                                                                                                                                                                               // Initial number of elements in the hash
85         }
86
87         /** @brief Hash table destructor */
88         ~HashTable() {
89                 _free(table);
90                 if (zero)
91                         _free(zero);
92         }
93
94         /** Override: new operator */
95         void * operator new(size_t size) {
96                 return _malloc(size);
97         }
98
99         /** Override: delete operator */
100         void operator delete(void *p, size_t size) {
101                 _free(p);
102         }
103
104         /** Override: new[] operator */
105         void * operator new[](size_t size) {
106                 return _malloc(size);
107         }
108
109         /** Override: delete[] operator */
110         void operator delete[](void *p, size_t size) {
111                 _free(p);
112         }
113
114         /** @brief Reset the table to its initial state. */
115         void reset() {
116                 memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
117                 if (zero) {
118                         _free(zero);
119                         zero = NULL;
120                 }
121                 size = 0;
122         }
123
124         void resetanddelete() {
125                 for(unsigned int i=0;i<capacity;i++) {
126                         struct hashlistnode<_Key, _Val> *bin = &table[i];
127                         if (bin->key != NULL) {
128                                 bin->key = NULL;
129                                 if (bin->val != NULL) {
130                                         delete bin->val;
131                                         bin->val = NULL;
132                                 }
133                         }
134                 }
135                 if (zero) {
136                         if (zero->val != NULL)
137                                 delete zero->val;
138                         _free(zero);
139                         zero = NULL;
140                 }
141                 size = 0;
142         }
143
144         void resetandfree() {
145                 for(unsigned int i=0;i<capacity;i++) {
146                         struct hashlistnode<_Key, _Val> *bin = &table[i];
147                         if (bin->key != NULL) {
148                                 bin->key = NULL;
149                                 if (bin->val != NULL) {
150                                         _free(bin->val);
151                                         bin->val = NULL;
152                                 }
153                         }
154                 }
155                 if (zero) {
156                         if (zero->val != NULL)
157                                 _free(zero->val);
158                         _free(zero);
159                         zero = NULL;
160                 }
161                 size = 0;
162         }
163
164         /**
165          * @brief Put a key/value pair into the table
166          * @param key The key for the new value; must not be 0 or NULL
167          * @param val The value to store in the table
168          */
169         void put(_Key key, _Val val) {
170                 /* HashTable cannot handle 0 as a key */
171                 if (!key) {
172                         if (!zero) {
173                                 zero=(struct hashlistnode<_Key, _Val> *)_malloc(sizeof(struct hashlistnode<_Key, _Val>));
174                                 size++;
175                         }
176                         zero->key=key;
177                         zero->val=val;
178                         return;
179                 }
180
181                 if (size > threshold)
182                         resize(capacity << 1);
183
184                 struct hashlistnode<_Key, _Val> *search;
185
186                 unsigned int index = hash_function(key);
187                 do {
188                         index &= capacitymask;
189                         search = &table[index];
190                         if (!search->key) {
191                                 //key is null, probably done
192                                 break;
193                         }
194                         if (equals(search->key, key)) {
195                                 search->val = val;
196                                 return;
197                         }
198                         index++;
199                 } while (true);
200
201                 search->key = key;
202                 search->val = val;
203                 size++;
204         }
205
206         /**
207          * @brief Lookup the corresponding value for the given key
208          * @param key The key for finding the value; must not be 0 or NULL
209          * @return The value in the table, if the key is found; otherwise 0
210          */
211         _Val get(_Key key) const {
212                 struct hashlistnode<_Key, _Val> *search;
213
214                 /* HashTable cannot handle 0 as a key */
215                 if (!key) {
216                         if (zero)
217                                 return zero->val;
218                         else
219                                 return (_Val) 0;
220                 }
221
222                 unsigned int oindex = hash_function(key) & capacitymask;
223                 unsigned int index=oindex;
224                 do {
225                         search = &table[index];
226                         if (!search->key) {
227                                 if (!search->val)
228                                         break;
229                         } else
230                         if (equals(search->key, key))
231                                 return search->val;
232                         index++;
233                         index &= capacitymask;
234                         if (index==oindex)
235                                 break;
236                 } while (true);
237                 return (_Val)0;
238         }
239
240         /**
241          * @brief Remove the given key and return the corresponding value
242          * @param key The key for finding the value; must not be 0 or NULL
243          * @return The value in the table, if the key is found; otherwise 0
244          */
245         _Val remove(_Key key) {
246                 struct hashlistnode<_Key, _Val> *search;
247
248                 /* HashTable cannot handle 0 as a key */
249                 if (!key) {
250                         if (!zero) {
251                                 return (_Val)0;
252                         } else {
253                                 _Val v=zero->val;
254                                 _free(zero);
255                                 zero=NULL;
256                                 size--;
257                                 return v;
258                         }
259                 }
260
261
262                 unsigned int index = hash_function(key);
263                 do {
264                         index &= capacitymask;
265                         search = &table[index];
266                         if (!search->key) {
267                                 if (!search->val)
268                                         break;
269                         } else
270                         if (equals(search->key, key)) {
271                                 _Val v=search->val;
272                                 //empty out this bin
273                                 search->val=(_Val) 1;
274                                 search->key=0;
275                                 size--;
276                                 return v;
277                         }
278                         index++;
279                 } while (true);
280                 return (_Val)0;
281         }
282
283         unsigned int getSize() const {
284                 return size;
285         }
286
287
288         /**
289          * @brief Check whether the table contains a value for the given key
290          * @param key The key for finding the value; must not be 0 or NULL
291          * @return True, if the key is found; false otherwise
292          */
293         bool contains(_Key key) const {
294                 struct hashlistnode<_Key, _Val> *search;
295
296                 /* HashTable cannot handle 0 as a key */
297                 if (!key) {
298                         return zero!=NULL;
299                 }
300
301                 unsigned int index = hash_function(key);
302                 do {
303                         index &= capacitymask;
304                         search = &table[index];
305                         if (!search->key) {
306                                 if (!search->val)
307                                         break;
308                         } else
309                         if (equals(search->key, key))
310                                 return true;
311                         index++;
312                 } while (true);
313                 return false;
314         }
315
316         /**
317          * @brief Resize the table
318          * @param newsize The new size of the table
319          */
320         void resize(unsigned int newsize) {
321                 struct hashlistnode<_Key, _Val> *oldtable = table;
322                 struct hashlistnode<_Key, _Val> *newtable;
323                 unsigned int oldcapacity = capacity;
324
325                 if ((newtable = (struct hashlistnode<_Key, _Val> *)_calloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
326                         model_print("calloc error %s %d\n", __FILE__, __LINE__);
327                         exit(EXIT_FAILURE);
328                 }
329
330                 table = newtable;                                                                                                                                                                                                                                                                                                                                                                                                               // Update the global hashtable upon resize()
331                 capacity = newsize;
332                 capacitymask = newsize - 1;
333
334                 threshold = (unsigned int)(newsize * loadfactor);
335
336                 struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
337                 struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
338                 for (;bin < lastbin;bin++) {
339                         _Key key = bin->key;
340
341                         struct hashlistnode<_Key, _Val> *search;
342                         if (!key)
343                                 continue;
344
345                         unsigned int index = hash_function(key);
346                         do {
347                                 index &= capacitymask;
348                                 search = &table[index];
349                                 index++;
350                         } while (search->key);
351
352                         search->key = key;
353                         search->val = bin->val;
354                 }
355
356                 _free(oldtable);                                                                                                                                                                                                                                                                                                                                                                                                                                                // Free the memory of the old hash table
357         }
358         double getLoadFactor() {return loadfactor;}
359         unsigned int getCapacity() {return capacity;}
360         struct hashlistnode<_Key, _Val> *table;
361         struct hashlistnode<_Key, _Val> *zero;
362         unsigned int capacity;
363         unsigned int size;
364 private:
365         unsigned int capacitymask;
366         unsigned int threshold;
367         double loadfactor;
368 };
369
370 #endif/* __HASHTABLE_H__ */