| |
| /*--------------------------------------------------------------------*/ |
| /*--- A separately-chained hash table. m_hashtable.c ---*/ |
| /*--------------------------------------------------------------------*/ |
| |
| /* |
| This file is part of Valgrind, a dynamic binary instrumentation |
| framework. |
| |
| Copyright (C) 2005-2012 Nicholas Nethercote |
| njn@valgrind.org |
| |
| This program is free software; you can redistribute it and/or |
| modify it under the terms of the GNU General Public License as |
| published by the Free Software Foundation; either version 2 of the |
| License, or (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program; if not, write to the Free Software |
| Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 02111-1307, USA. |
| |
| The GNU General Public License is contained in the file COPYING. |
| */ |
| |
| #include "pub_core_basics.h" |
| #include "pub_core_debuglog.h" |
| #include "pub_core_hashtable.h" |
| #include "pub_core_libcassert.h" |
| #include "pub_core_mallocfree.h" |
| |
| /*--------------------------------------------------------------------*/ |
| /*--- Declarations ---*/ |
| /*--------------------------------------------------------------------*/ |
| |
| #define CHAIN_NO(key,tbl) (((UWord)(key)) % tbl->n_chains) |
| |
| struct _VgHashTable { |
| UInt n_chains; // should be prime |
| UInt n_elements; |
| VgHashNode* iterNode; // current iterator node |
| UInt iterChain; // next chain to be traversed by the iterator |
| VgHashNode** chains; // expanding array of hash chains |
| Bool iterOK; // table safe to iterate over? |
| HChar* name; // name of table (for debugging only) |
| }; |
| |
| #define N_HASH_PRIMES 20 |
| |
| static SizeT primes[N_HASH_PRIMES] = { |
| 769UL, 1543UL, 3079UL, 6151UL, |
| 12289UL, 24593UL, 49157UL, 98317UL, |
| 196613UL, 393241UL, 786433UL, 1572869UL, |
| 3145739UL, 6291469UL, 12582917UL, 25165843UL, |
| 50331653UL, 100663319UL, 201326611UL, 402653189UL |
| }; |
| |
| /*--------------------------------------------------------------------*/ |
| /*--- Functions ---*/ |
| /*--------------------------------------------------------------------*/ |
| |
| VgHashTable VG_(HT_construct) ( HChar* name ) |
| { |
| /* Initialises to zero, ie. all entries NULL */ |
| SizeT n_chains = primes[0]; |
| SizeT sz = n_chains * sizeof(VgHashNode*); |
| VgHashTable table = VG_(calloc)("hashtable.Hc.1", |
| 1, sizeof(struct _VgHashTable)); |
| table->chains = VG_(calloc)("hashtable.Hc.2", 1, sz); |
| table->n_chains = n_chains; |
| table->n_elements = 0; |
| table->iterOK = True; |
| table->name = name; |
| vg_assert(name); |
| return table; |
| } |
| |
| Int VG_(HT_count_nodes) ( VgHashTable table ) |
| { |
| return table->n_elements; |
| } |
| |
| static void resize ( VgHashTable table ) |
| { |
| Int i; |
| SizeT sz; |
| SizeT old_chains = table->n_chains; |
| SizeT new_chains = old_chains + 1; |
| VgHashNode** chains; |
| VgHashNode * node; |
| |
| /* If we've run out of primes, do nothing. */ |
| if (old_chains == primes[N_HASH_PRIMES-1]) |
| return; |
| |
| vg_assert(old_chains >= primes[0] |
| && old_chains < primes[N_HASH_PRIMES-1]); |
| |
| for (i = 0; i < N_HASH_PRIMES; i++) { |
| if (primes[i] > new_chains) { |
| new_chains = primes[i]; |
| break; |
| } |
| } |
| |
| vg_assert(new_chains > old_chains); |
| vg_assert(new_chains > primes[0] |
| && new_chains <= primes[N_HASH_PRIMES-1]); |
| |
| VG_(debugLog)( |
| 1, "hashtable", |
| "resizing table `%s' from %lu to %lu (total elems %lu)\n", |
| table->name, (UWord)old_chains, (UWord)new_chains, |
| (UWord)table->n_elements ); |
| |
| table->n_chains = new_chains; |
| sz = new_chains * sizeof(VgHashNode*); |
| chains = VG_(calloc)("hashtable.resize.1", 1, sz); |
| |
| for (i = 0; i < old_chains; i++) { |
| node = table->chains[i]; |
| while (node != NULL) { |
| VgHashNode* next = node->next; |
| UWord chain = CHAIN_NO(node->key, table); |
| node->next = chains[chain]; |
| chains[chain] = node; |
| node = next; |
| } |
| } |
| |
| VG_(free)(table->chains); |
| table->chains = chains; |
| } |
| |
| /* Puts a new, heap allocated VgHashNode, into the VgHashTable. Prepends |
| the node to the appropriate chain. No duplicate key detection is done. */ |
| void VG_(HT_add_node) ( VgHashTable table, void* vnode ) |
| { |
| VgHashNode* node = (VgHashNode*)vnode; |
| UWord chain = CHAIN_NO(node->key, table); |
| node->next = table->chains[chain]; |
| table->chains[chain] = node; |
| table->n_elements++; |
| if ( (1 * (ULong)table->n_elements) > (1 * (ULong)table->n_chains) ) { |
| resize(table); |
| } |
| |
| /* Table has been modified; hence HT_Next should assert. */ |
| table->iterOK = False; |
| } |
| |
| /* Looks up a VgHashNode in the table. Returns NULL if not found. */ |
| void* VG_(HT_lookup) ( VgHashTable table, UWord key ) |
| { |
| VgHashNode* curr = table->chains[ CHAIN_NO(key, table) ]; |
| |
| while (curr) { |
| if (key == curr->key) { |
| return curr; |
| } |
| curr = curr->next; |
| } |
| return NULL; |
| } |
| |
| /* Removes a VgHashNode from the table. Returns NULL if not found. */ |
| void* VG_(HT_remove) ( VgHashTable table, UWord key ) |
| { |
| UWord chain = CHAIN_NO(key, table); |
| VgHashNode* curr = table->chains[chain]; |
| VgHashNode** prev_next_ptr = &(table->chains[chain]); |
| |
| /* Table has been modified; hence HT_Next should assert. */ |
| table->iterOK = False; |
| |
| while (curr) { |
| if (key == curr->key) { |
| *prev_next_ptr = curr->next; |
| table->n_elements--; |
| return curr; |
| } |
| prev_next_ptr = &(curr->next); |
| curr = curr->next; |
| } |
| return NULL; |
| } |
| |
| /* Allocates a suitably-sized array, copies pointers to all the hashtable |
| elements into it, then returns both the array and the size of it. The |
| array must be freed with VG_(free). |
| */ |
| VgHashNode** VG_(HT_to_array) ( VgHashTable table, /*OUT*/ UInt* n_elems ) |
| { |
| UInt i, j; |
| VgHashNode** arr; |
| VgHashNode* node; |
| |
| *n_elems = table->n_elements; |
| if (*n_elems == 0) |
| return NULL; |
| |
| arr = VG_(malloc)( "hashtable.Hta.1", *n_elems * sizeof(VgHashNode*) ); |
| |
| j = 0; |
| for (i = 0; i < table->n_chains; i++) { |
| for (node = table->chains[i]; node != NULL; node = node->next) { |
| arr[j++] = node; |
| } |
| } |
| vg_assert(j == *n_elems); |
| |
| return arr; |
| } |
| |
| void VG_(HT_ResetIter)(VgHashTable table) |
| { |
| vg_assert(table); |
| table->iterNode = NULL; |
| table->iterChain = 0; |
| table->iterOK = True; |
| } |
| |
| void* VG_(HT_Next)(VgHashTable table) |
| { |
| Int i; |
| vg_assert(table); |
| /* See long comment on HT_Next prototype in pub_tool_hashtable.h. |
| In short if this fails, it means the caller tried to modify the |
| table whilst iterating over it, which is a bug. */ |
| vg_assert(table->iterOK); |
| |
| if (table->iterNode && table->iterNode->next) { |
| table->iterNode = table->iterNode->next; |
| return table->iterNode; |
| } |
| |
| for (i = table->iterChain; i < table->n_chains; i++) { |
| if (table->chains[i]) { |
| table->iterNode = table->chains[i]; |
| table->iterChain = i + 1; // Next chain to be traversed |
| return table->iterNode; |
| } |
| } |
| return NULL; |
| } |
| |
| void VG_(HT_destruct)(VgHashTable table, void(*freenode_fn)(void*)) |
| { |
| UInt i; |
| VgHashNode *node, *node_next; |
| |
| for (i = 0; i < table->n_chains; i++) { |
| for (node = table->chains[i]; node != NULL; node = node_next) { |
| node_next = node->next; |
| freenode_fn(node); |
| } |
| } |
| VG_(free)(table->chains); |
| VG_(free)(table); |
| } |
| |
| /*--------------------------------------------------------------------*/ |
| /*--- end ---*/ |
| /*--------------------------------------------------------------------*/ |