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-2010 Nicholas Nethercote 11 njn (at) 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 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 67 VgHashTable VG_(HT_construct) ( 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 83 Int VG_(HT_count_nodes) ( VgHashTable table ) 84 { 85 return table->n_elements; 86 } 87 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. */ 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. */ 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. */ 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 */ 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 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 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 252 void VG_(HT_destruct)(VgHashTable table) 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 VG_(free)(node); 261 } 262 } 263 VG_(free)(table->chains); 264 VG_(free)(table); 265 } 266 267 /*--------------------------------------------------------------------*/ 268 /*--- end ---*/ 269 /*--------------------------------------------------------------------*/ 270
