1
2 /*--------------------------------------------------------------------*/
3 /*--- A separately-chained hash table. m_hashtable.c ---*/
4 /*--------------------------------------------------------------------*/
5
6 /*
7 This file is part of Valgrind, a dynamic binary instrumentation
8 framework.
9
10 Copyright (C) 2005-2013 Nicholas Nethercote
11 njn@valgrind.org
12
13 This program is free software; you can redistribute it and/or
14 modify it under the terms of the GNU General Public License as
15 published by the Free Software Foundation; either version 2 of the
16 License, or (at your option) any later version.
17
18 This program is distributed in the hope that it will be useful, but
19 WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 General Public License for more details.
22
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
26 02111-1307, USA.
27
28 The GNU General Public License is contained in the file COPYING.
29 */
30
31 #include "pub_core_basics.h"
32 #include "pub_core_debuglog.h"
33 #include "pub_core_hashtable.h"
34 #include "pub_core_libcassert.h"
35 #include "pub_core_mallocfree.h"
36
37 /*--------------------------------------------------------------------*/
38 /*--- Declarations ---*/
39 /*--------------------------------------------------------------------*/
40
41 #define CHAIN_NO(key,tbl) (((UWord)(key)) % tbl->n_chains)
42
43 struct _VgHashTable {
44 UInt n_chains; // should be prime
45 UInt n_elements;
46 VgHashNode* iterNode; // current iterator node
47 UInt iterChain; // next chain to be traversed by the iterator
48 VgHashNode** chains; // expanding array of hash chains
49 Bool iterOK; // table safe to iterate over?
50 const HChar* name; // name of table (for debugging only)
51 };
52
53 #define N_HASH_PRIMES 20
54
55 static SizeT primes[N_HASH_PRIMES] = {
56 769UL, 1543UL, 3079UL, 6151UL,
57 12289UL, 24593UL, 49157UL, 98317UL,
58 196613UL, 393241UL, 786433UL, 1572869UL,
59 3145739UL, 6291469UL, 12582917UL, 25165843UL,
60 50331653UL, 100663319UL, 201326611UL, 402653189UL
61 };
62
63 /*--------------------------------------------------------------------*/
64 /*--- Functions ---*/
65 /*--------------------------------------------------------------------*/
66
VG_(HT_construct)67 VgHashTable VG_(HT_construct) ( const HChar* name )
68 {
69 /* Initialises to zero, ie. all entries NULL */
70 SizeT n_chains = primes[0];
71 SizeT sz = n_chains * sizeof(VgHashNode*);
72 VgHashTable table = VG_(calloc)("hashtable.Hc.1",
73 1, sizeof(struct _VgHashTable));
74 table->chains = VG_(calloc)("hashtable.Hc.2", 1, sz);
75 table->n_chains = n_chains;
76 table->n_elements = 0;
77 table->iterOK = True;
78 table->name = name;
79 vg_assert(name);
80 return table;
81 }
82
VG_(HT_count_nodes)83 Int VG_(HT_count_nodes) ( VgHashTable table )
84 {
85 return table->n_elements;
86 }
87
resize(VgHashTable table)88 static void resize ( VgHashTable table )
89 {
90 Int i;
91 SizeT sz;
92 SizeT old_chains = table->n_chains;
93 SizeT new_chains = old_chains + 1;
94 VgHashNode** chains;
95 VgHashNode * node;
96
97 /* If we've run out of primes, do nothing. */
98 if (old_chains == primes[N_HASH_PRIMES-1])
99 return;
100
101 vg_assert(old_chains >= primes[0]
102 && old_chains < primes[N_HASH_PRIMES-1]);
103
104 for (i = 0; i < N_HASH_PRIMES; i++) {
105 if (primes[i] > new_chains) {
106 new_chains = primes[i];
107 break;
108 }
109 }
110
111 vg_assert(new_chains > old_chains);
112 vg_assert(new_chains > primes[0]
113 && new_chains <= primes[N_HASH_PRIMES-1]);
114
115 VG_(debugLog)(
116 1, "hashtable",
117 "resizing table `%s' from %lu to %lu (total elems %lu)\n",
118 table->name, (UWord)old_chains, (UWord)new_chains,
119 (UWord)table->n_elements );
120
121 table->n_chains = new_chains;
122 sz = new_chains * sizeof(VgHashNode*);
123 chains = VG_(calloc)("hashtable.resize.1", 1, sz);
124
125 for (i = 0; i < old_chains; i++) {
126 node = table->chains[i];
127 while (node != NULL) {
128 VgHashNode* next = node->next;
129 UWord chain = CHAIN_NO(node->key, table);
130 node->next = chains[chain];
131 chains[chain] = node;
132 node = next;
133 }
134 }
135
136 VG_(free)(table->chains);
137 table->chains = chains;
138 }
139
140 /* Puts a new, heap allocated VgHashNode, into the VgHashTable. Prepends
141 the node to the appropriate chain. No duplicate key detection is done. */
VG_(HT_add_node)142 void VG_(HT_add_node) ( VgHashTable table, void* vnode )
143 {
144 VgHashNode* node = (VgHashNode*)vnode;
145 UWord chain = CHAIN_NO(node->key, table);
146 node->next = table->chains[chain];
147 table->chains[chain] = node;
148 table->n_elements++;
149 if ( (1 * (ULong)table->n_elements) > (1 * (ULong)table->n_chains) ) {
150 resize(table);
151 }
152
153 /* Table has been modified; hence HT_Next should assert. */
154 table->iterOK = False;
155 }
156
157 /* Looks up a VgHashNode in the table. Returns NULL if not found. */
VG_(HT_lookup)158 void* VG_(HT_lookup) ( VgHashTable table, UWord key )
159 {
160 VgHashNode* curr = table->chains[ CHAIN_NO(key, table) ];
161
162 while (curr) {
163 if (key == curr->key) {
164 return curr;
165 }
166 curr = curr->next;
167 }
168 return NULL;
169 }
170
171 /* Removes a VgHashNode from the table. Returns NULL if not found. */
VG_(HT_remove)172 void* VG_(HT_remove) ( VgHashTable table, UWord key )
173 {
174 UWord chain = CHAIN_NO(key, table);
175 VgHashNode* curr = table->chains[chain];
176 VgHashNode** prev_next_ptr = &(table->chains[chain]);
177
178 /* Table has been modified; hence HT_Next should assert. */
179 table->iterOK = False;
180
181 while (curr) {
182 if (key == curr->key) {
183 *prev_next_ptr = curr->next;
184 table->n_elements--;
185 return curr;
186 }
187 prev_next_ptr = &(curr->next);
188 curr = curr->next;
189 }
190 return NULL;
191 }
192
193 /* Allocates a suitably-sized array, copies pointers to all the hashtable
194 elements into it, then returns both the array and the size of it. The
195 array must be freed with VG_(free).
196 */
VG_(HT_to_array)197 VgHashNode** VG_(HT_to_array) ( VgHashTable table, /*OUT*/ UInt* n_elems )
198 {
199 UInt i, j;
200 VgHashNode** arr;
201 VgHashNode* node;
202
203 *n_elems = table->n_elements;
204 if (*n_elems == 0)
205 return NULL;
206
207 arr = VG_(malloc)( "hashtable.Hta.1", *n_elems * sizeof(VgHashNode*) );
208
209 j = 0;
210 for (i = 0; i < table->n_chains; i++) {
211 for (node = table->chains[i]; node != NULL; node = node->next) {
212 arr[j++] = node;
213 }
214 }
215 vg_assert(j == *n_elems);
216
217 return arr;
218 }
219
VG_(HT_ResetIter)220 void VG_(HT_ResetIter)(VgHashTable table)
221 {
222 vg_assert(table);
223 table->iterNode = NULL;
224 table->iterChain = 0;
225 table->iterOK = True;
226 }
227
VG_(HT_Next)228 void* VG_(HT_Next)(VgHashTable table)
229 {
230 Int i;
231 vg_assert(table);
232 /* See long comment on HT_Next prototype in pub_tool_hashtable.h.
233 In short if this fails, it means the caller tried to modify the
234 table whilst iterating over it, which is a bug. */
235 vg_assert(table->iterOK);
236
237 if (table->iterNode && table->iterNode->next) {
238 table->iterNode = table->iterNode->next;
239 return table->iterNode;
240 }
241
242 for (i = table->iterChain; i < table->n_chains; i++) {
243 if (table->chains[i]) {
244 table->iterNode = table->chains[i];
245 table->iterChain = i + 1; // Next chain to be traversed
246 return table->iterNode;
247 }
248 }
249 return NULL;
250 }
251
VG_(HT_destruct)252 void VG_(HT_destruct)(VgHashTable table, void(*freenode_fn)(void*))
253 {
254 UInt i;
255 VgHashNode *node, *node_next;
256
257 for (i = 0; i < table->n_chains; i++) {
258 for (node = table->chains[i]; node != NULL; node = node_next) {
259 node_next = node->next;
260 freenode_fn(node);
261 }
262 }
263 VG_(free)(table->chains);
264 VG_(free)(table);
265 }
266
267 /*--------------------------------------------------------------------*/
268 /*--- end ---*/
269 /*--------------------------------------------------------------------*/
270