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
42 * @tparam _Key Type name for the key
43 * @tparam _Val Type name for the values to be stored
44 * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
45 * manipulation and storage.
46 * @tparam _Shift Logical shift to apply to all keys. Default 0.
47 * @tparam _malloc Provide your own 'malloc' for the table, or default to
49 * @tparam _calloc Provide your own 'calloc' for the table, or default to
51 * @tparam _free Provide your own 'free' for the table, or default to
54 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>
59 * @param initialcapacity Sets the initial capacity of the hash table.
61 * @param factor Sets the percentage full before the hashtable is
62 * resized. Default ratio 0.5.
64 HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) {
65 // Allocate space for the hash table
66 table = (struct hashlistnode<_Key, _Val> *)_calloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>));
68 capacity = initialcapacity;
69 capacitymask = initialcapacity - 1;
71 threshold = (unsigned int)(initialcapacity * loadfactor);
72 size = 0; // Initial number of elements in the hash
80 /** Override: new operator */
81 void * operator new(size_t size) {
85 /** Override: delete operator */
86 void operator delete(void *p, size_t size) {
90 /** Override: new[] operator */
91 void * operator new[](size_t size) {
95 /** Override: delete[] operator */
96 void operator delete[](void *p, size_t size) {
100 /** Reset the table to its initial state. */
102 memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>));
106 /** Put a key value pair into the table. */
107 void put(_Key key, _Val val) {
108 if (size > threshold)
109 resize(capacity << 1);
111 struct hashlistnode<_Key, _Val> *search;
113 unsigned int index = ((_KeyInt)key) >> _Shift;
115 index &= capacitymask;
116 search = &table[index];
117 if (search->key == key) {
122 } while (search->key);
129 /** Lookup the corresponding value for the given key. */
130 _Val get(_Key key) const {
131 struct hashlistnode<_Key, _Val> *search;
133 unsigned int index = ((_KeyInt)key) >> _Shift;
135 index &= capacitymask;
136 search = &table[index];
137 if (search->key == key)
140 } while (search->key);
144 /** Check whether the table contains a value for the given key. */
145 bool contains(_Key key) const {
146 struct hashlistnode<_Key, _Val> *search;
148 unsigned int index = ((_KeyInt)key) >> _Shift;
150 index &= capacitymask;
151 search = &table[index];
152 if (search->key == key)
155 } while (search->key);
159 /** Resize the table. */
160 void resize(unsigned int newsize) {
161 struct hashlistnode<_Key, _Val> *oldtable = table;
162 struct hashlistnode<_Key, _Val> *newtable;
163 unsigned int oldcapacity = capacity;
165 if ((newtable = (struct hashlistnode<_Key, _Val> *)_calloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) {
166 model_print("calloc error %s %d\n", __FILE__, __LINE__);
170 table = newtable; // Update the global hashtable upon resize()
172 capacitymask = newsize - 1;
174 threshold = (unsigned int)(newsize * loadfactor);
176 struct hashlistnode<_Key, _Val> *bin = &oldtable[0];
177 struct hashlistnode<_Key, _Val> *lastbin = &oldtable[oldcapacity];
178 for (; bin < lastbin; bin++) {
181 struct hashlistnode<_Key, _Val> *search;
183 unsigned int index = ((_KeyInt)key) >> _Shift;
185 index &= capacitymask;
186 search = &table[index];
188 } while (search->key);
191 search->val = bin->val;
194 _free(oldtable); // Free the memory of the old hash table
198 struct hashlistnode<_Key, _Val> *table;
199 unsigned int capacity;
201 unsigned int capacitymask;
202 unsigned int threshold;