2 * @brief Hashtable. Standard chained bucket variety.
15 * @brief HashTable linked node class, for chained storage of hash table conflicts
17 * By default it is snapshotting, but you can pass in your own allocation
20 * @tparam _Key Type name for the key
21 * @tparam _Val Type name for the values to be stored
22 * @tparam _malloc Provide your own 'malloc' for the table, or default to
24 * @tparam _calloc Provide your own 'calloc' for the table, or default to
26 * @tparam _free Provide your own 'free' for the table, or default to
29 template<typename _Key, typename _Val>
37 * @brief A simple, custom hash table
39 * By default it is snapshotting, but you can pass in your own allocation
40 * functions. Note that this table does not support 0 (NULL) keys and is
41 * designed primarily with pointer-based keys in mind.
43 * @tparam _Key Type name for the key
44 * @tparam _Val Type name for the values to be stored
45 * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
46 * manipulation and storage.
47 * @tparam _Shift Logical shift to apply to all keys. Default 0.
48 * @tparam _malloc Provide your own 'malloc' for the table, or default to
50 * @tparam _calloc Provide your own 'calloc' for the table, or default to
52 * @tparam _free Provide your own 'free' for the table, or default to
55 template<typename _Key, typename _Val, typename _KeyInt, int _Shift = 0, void * (* _malloc)(size_t) = snapshot_malloc, void * (* _calloc)(size_t, size_t) = snapshot_calloc, void (*_free)(void *) = snapshot_free>
60 * @param initialcapacity Sets the initial capacity of the hash table.
62 * @param factor Sets the percentage full before the hashtable is
63 * resized. Default ratio 0.5.
65 HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
66 // Allocate space for the hash table
67 table = (struct hashlistnode<_Key, _Val> *)_calloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
69 capacity = initialcapacity;
70 capacitymask = initialcapacity - 1;
72 threshold = (unsigned int)(initialcapacity * loadfactor);
73 size = 0; // Initial number of elements in the hash
81 /** Override: new operator */
82 void * operator new(size_t size) {
86 /** Override: delete operator */
87 void operator delete(void *p, size_t size) {
91 /** Override: new[] operator */
92 void * operator new[](size_t size) {
96 /** Override: delete[] operator */
97 void operator delete[](void *p, size_t size) {
101 /** Reset the table to its initial state. */
103 memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
107 /** Put a key value pair into the table. */
108 void put(_Key key, _Val val) {
109 /* HashTable cannot handle 0 as a key */
112 if (size > threshold)
113 resize(capacity << 1);
115 struct hashlistnode<_Key, _Val> *search;
117 unsigned int index = ((_KeyInt)key) >> _Shift;
119 index &= capacitymask;
120 search = &table[index];
121 if (search->key == key) {
126 } while (search->key);
133 /** Lookup the corresponding value for the given key. */
134 _Val get(_Key key) const {
135 struct hashlistnode<_Key, _Val> *search;
137 /* HashTable cannot handle 0 as a key */
140 unsigned int index = ((_KeyInt)key) >> _Shift;
142 index &= capacitymask;
143 search = &table[index];
144 if (search->key == key)
147 } while (search->key);
151 /** Check whether the table contains a value for the given key. */
152 bool contains(_Key key) const {
153 struct hashlistnode<_Key, _Val> *search;
155 /* HashTable cannot handle 0 as a key */
158 unsigned int index = ((_KeyInt)key) >> _Shift;
160 index &= capacitymask;
161 search = &table[index];
162 if (search->key == key)
165 } while (search->key);
169 /** Resize the table. */
170 void resize(unsigned int newsize) {
171 struct hashlistnode<_Key, _Val> *oldtable = table;
172 struct hashlistnode<_Key, _Val> *newtable;
173 unsigned int oldcapacity = capacity;
175 if ((newtable = (struct hashlistnode<_Key, _Val> *)_calloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
176 model_print("calloc error %s %d\n", __FILE__, __LINE__);
180 table = newtable; // Update the global hashtable upon resize()
182 capacitymask = newsize - 1;
184 threshold = (unsigned int)(newsize * loadfactor);
186 struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
187 struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
188 for (; bin < lastbin; bin++) {
191 struct hashlistnode<_Key, _Val> *search;
193 unsigned int index = ((_KeyInt)key) >> _Shift;
195 index &= capacitymask;
196 search = &table[index];
198 } while (search->key);
201 search->val = bin->val;
204 _free(oldtable); // Free the memory of the old hash table
208 struct hashlistnode<_Key, _Val> *table;
209 unsigned int capacity;
211 unsigned int capacitymask;
212 unsigned int threshold;