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