From b09ffd9fb9ef41436d48c954a8de84826021ed78 Mon Sep 17 00:00:00 2001 From: Philippe Waroquiers Date: Wed, 20 May 2015 15:08:09 +0000 Subject: [PATCH] Have the hash table 'gen' functions comparing the key instead of the cmp function. Document this in the cmp function comment in pub_tool_hashtable.h git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15263 --- coregrind/m_deduppoolalloc.c | 13 ++++++++----- coregrind/m_hashtable.c | 4 ++-- include/pub_tool_hashtable.h | 5 ++++- 3 files changed, 14 insertions(+), 8 deletions(-) diff --git a/coregrind/m_deduppoolalloc.c b/coregrind/m_deduppoolalloc.c index bf6d1e3c88..51a58cb063 100644 --- a/coregrind/m_deduppoolalloc.c +++ b/coregrind/m_deduppoolalloc.c @@ -177,16 +177,19 @@ static void ddpa_add_new_pool_or_grow ( DedupPoolAlloc* ddpa ) } } +/* Compare function for 'gen' hash table. No need to compare the key + in this function, as the hash table already does it for us, + and that in any case, if the data is equal, the keys must also be + equal. */ static Word cmp_pool_elt (const void* node1, const void* node2 ) { const ht_node* hnode1 = node1; const ht_node* hnode2 = node2; - if (hnode1->key < hnode2->key) - return -1; - else if (hnode1->key > hnode2->key) - return 1; - else if (hnode1->eltSzB == hnode2->eltSzB) + /* As this function is called by hashtable, that has already checked + for key equality, it is likely that it is the 'good' element. + So, we handle the equal case first. */ + if (hnode1->eltSzB == hnode2->eltSzB) return VG_(memcmp) (hnode1->elt, hnode2->elt, hnode1->eltSzB); else if (hnode1->eltSzB < hnode2->eltSzB) return -1; diff --git a/coregrind/m_hashtable.c b/coregrind/m_hashtable.c index 3b6c72d13d..7b28e0a63d 100644 --- a/coregrind/m_hashtable.c +++ b/coregrind/m_hashtable.c @@ -179,7 +179,7 @@ void* VG_(HT_gen_lookup) ( const VgHashTable *table, const void* node, VgHashNode* curr = table->chains[ CHAIN_NO(hnode->key, table) ]; // GEN!!! while (curr) { - if (cmp (hnode, curr) == 0) { // GEN!!! + if (hnode->key == curr->key && cmp (hnode, curr) == 0) { // GEN!!! return curr; } curr = curr->next; @@ -222,7 +222,7 @@ void* VG_(HT_gen_remove) ( VgHashTable *table, const void* node, HT_Cmp_t cmp ) table->iterOK = False; while (curr) { - if (cmp(hnode, curr) == 0) { // GEN!!! + if (hnode->key == curr->key && cmp(hnode, curr) == 0) { // GEN!!! *prev_next_ptr = curr->next; table->n_elements--; return curr; diff --git a/include/pub_tool_hashtable.h b/include/pub_tool_hashtable.h index b105ac4043..6fc6822b46 100644 --- a/include/pub_tool_hashtable.h +++ b/include/pub_tool_hashtable.h @@ -84,7 +84,10 @@ typedef Word (*HT_Cmp_t) ( const void* node1, const void* node2 ); * when comparing the rest of the node, if the node data contains holes between components, either the node memory should be fully initialised (e.g. allocated using VG_(calloc)) or each component should be compared - individually. */ + individually. + Note that the cmp function is only called for elements that already + have keys that are equal. So, it is not needed for cmp to check for + key equality. */ extern void* VG_(HT_gen_lookup) ( const VgHashTable *table, const void* node, HT_Cmp_t cmp ); extern void* VG_(HT_gen_remove) ( VgHashTable *table, const void* node, -- 2.47.3