2 * @brief Hashtable. Standard chained bucket variety.
14 * Hashtable linked node class, for chained storage of hash table conflicts. By
15 * default it is snapshotting, but you can pass in your own allocation
18 * @tparam _Key Type name for the key
19 * @tparam _Val Type name for the values to be stored
20 * @tparam _malloc Provide your own 'malloc' for the table, or default to
22 * @tparam _calloc Provide your own 'calloc' for the table, or default to
24 * @tparam _free Provide your own 'free' for the table, or default to
27 template<typename _Key, typename _Val>
35 * Hashtable class. By default it is snapshotting, but you can pass in your own
36 * allocation functions.
38 * @tparam _Key Type name for the key
39 * @tparam _Val Type name for the values to be stored
40 * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key
41 * manipulation and storage.
42 * @tparam _Shift Logical shift to apply to all keys. Default 0.
43 * @tparam _malloc Provide your own 'malloc' for the table, or default to
45 * @tparam _calloc Provide your own 'calloc' for the table, or default to
47 * @tparam _free Provide your own 'free' for the table, or default to
50 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>
55 * @param initialcapacity Sets the initial capacity of the hash table.
57 * @param factor Sets the percentage full before the hashtable is
58 * resized. Default ratio 0.5.
60 HashTable(unsigned int initialcapacity=1024, double factor=0.5) {
61 // Allocate space for the hash table
62 table = (struct hashlistnode<_Key,_Val> *) _calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val>));
64 capacity = initialcapacity;
65 capacitymask = initialcapacity - 1;
67 threshold = (unsigned int) (initialcapacity*loadfactor);
68 size = 0; // Initial number of elements in the hash
76 /** Override: new operator */
77 void * operator new(size_t size) {
81 /** Override: delete operator */
82 void operator delete(void *p, size_t size) {
86 /** Override: new[] operator */
87 void * operator new[](size_t size) {
91 /** Override: delete[] operator */
92 void operator delete[](void *p, size_t size) {
96 /** Reset the table to its initial state. */
98 memset(table, 0, capacity*sizeof(struct hashlistnode<_Key, _Val>));
102 /** Put a key value pair into the table. */
103 void put(_Key key, _Val val) {
104 if (size > threshold)
105 resize(capacity << 1);
107 struct hashlistnode<_Key,_Val> *search;
109 unsigned int index=((_KeyInt)key)>>_Shift;
111 index=index&capacitymask;
112 search = &table[index];
113 if (search->key==key) {
118 } while(search->key);
125 /** Lookup the corresponding value for the given key. */
127 struct hashlistnode<_Key,_Val> *search;
129 unsigned int index=((_KeyInt)key)>>_Shift;
131 index=index&capacitymask;
132 search = &table[index];
133 if (search->key==key) {
137 } while(search->key);
141 /** Check whether the table contains a value for the given key. */
142 bool contains(_Key key) {
143 struct hashlistnode<_Key,_Val> *search;
145 unsigned int index=((_KeyInt)key)>>_Shift;
147 index=index&capacitymask;
148 search = &table[index];
149 if (search->key==key) {
153 } while(search->key);
157 /** Resize the table. */
158 void resize(unsigned int newsize) {
159 struct hashlistnode<_Key,_Val> * oldtable = table;
160 struct hashlistnode<_Key,_Val> * newtable;
161 unsigned int oldcapacity = capacity;
163 if((newtable = (struct hashlistnode<_Key,_Val> *) _calloc(newsize, sizeof(struct hashlistnode<_Key,_Val>))) == NULL) {
164 printf("Calloc error %s %d\n", __FILE__, __LINE__);
168 table = newtable; //Update the global hashtable upon resize()
170 capacitymask = newsize - 1;
172 threshold = (unsigned int) (newsize * loadfactor);
174 struct hashlistnode<_Key, _Val> * bin = &oldtable[0];
175 struct hashlistnode<_Key, _Val> * lastbin = &oldtable[oldcapacity];
176 for(; bin < lastbin; bin++) {
179 struct hashlistnode<_Key,_Val> *search;
181 unsigned int index=((_KeyInt)key)>>_Shift;
183 index=index&capacitymask;
184 search = &table[index];
186 } while(search->key);
189 search->val=bin->val;
192 _free(oldtable); //Free the memory of the old hash table
196 struct hashlistnode<_Key,_Val> *table;
197 unsigned int capacity;
199 unsigned int capacitymask;
200 unsigned int threshold;