1 2 /*--------------------------------------------------------------------*/ 3 /*--- A hash table implementation. pub_tool_hashtable.h ---*/ 4 /*--------------------------------------------------------------------*/ 5 6 /* 7 This file is part of Valgrind, a dynamic binary instrumentation 8 framework. 9 10 Copyright (C) 2005-2017 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 #ifndef __PUB_TOOL_HASHTABLE_H 32 #define __PUB_TOOL_HASHTABLE_H 33 34 #include "pub_tool_basics.h" // VG_ macro 35 36 /* Generic type for a separately-chained hash table. Via a kind of dodgy 37 C-as-C++ style inheritance, tools can extend the VgHashNode type, so long 38 as the first two fields match the sizes of these two fields. Requires 39 a bit of casting by the tool. */ 40 41 // Problems with this data structure: 42 // - Separate chaining gives bad cache behaviour. Hash tables with linear 43 // probing give better cache behaviour. 44 45 typedef 46 struct _VgHashNode { 47 struct _VgHashNode * next; 48 UWord key; 49 } 50 VgHashNode; 51 52 typedef struct _VgHashTable VgHashTable; 53 54 /* Make a new table. Allocates the memory with VG_(calloc)(), so can 55 be freed with VG_(free)(). The table starts small but will 56 periodically be expanded. This is transparent to the users of this 57 module. The function never returns NULL. */ 58 extern VgHashTable *VG_(HT_construct) ( const HChar* name ); 59 60 /* Count the number of nodes in a table. */ 61 extern UInt VG_(HT_count_nodes) ( const VgHashTable *table ); 62 63 /* Add a node to the table. Duplicate keys are permitted. */ 64 extern void VG_(HT_add_node) ( VgHashTable *t, void* node ); 65 66 /* Looks up a VgHashNode by key in the table. 67 * Returns NULL if not found. If entries 68 * with duplicate keys are present, the most recently-added of the dups will 69 * be returned, but it's probably better to avoid dups altogether. */ 70 extern void* VG_(HT_lookup) ( const VgHashTable *table, UWord key ); 71 72 /* Removes a VgHashNode by key from the table. Returns NULL if not found. */ 73 extern void* VG_(HT_remove) ( VgHashTable *table, UWord key ); 74 75 typedef Word (*HT_Cmp_t) ( const void* node1, const void* node2 ); 76 77 /* Same as VG_(HT_lookup) and VG_(HT_remove), but allowing a part of or 78 the full element to be compared for equality, not only the key. 79 The typical use for the below function is to store a hash value of the 80 element in the key, and have the comparison function checking for equality 81 of the full element data. 82 Attention about the comparison function: 83 * It must *not* compare the 'next' pointer. 84 * when comparing the rest of the node, if the node data contains holes 85 between components, either the node memory should be fully initialised 86 (e.g. allocated using VG_(calloc)) or each component should be compared 87 individually. 88 Note that the cmp function is only called for elements that already 89 have keys that are equal. So, it is not needed for cmp to check for 90 key equality. */ 91 extern void* VG_(HT_gen_lookup) ( const VgHashTable *table, const void* node, 92 HT_Cmp_t cmp ); 93 extern void* VG_(HT_gen_remove) ( VgHashTable *table, const void* node, 94 HT_Cmp_t cmp ); 95 96 /* Output detailed usage/collision statistics. 97 cmp will be used to verify if 2 elements with the same key are equal. 98 Use NULL cmp if the hash table elements are only to be compared by key. */ 99 extern void VG_(HT_print_stats) ( const VgHashTable *table, HT_Cmp_t cmp ); 100 101 /* Allocates a suitably-sized array, copies pointers to all the hashtable 102 elements into it, then returns both the array and the size of it. The 103 array must be freed with VG_(free). If the hashtable is empty, the 104 function returns NULL and assigns *nelems = 0. */ 105 extern VgHashNode** VG_(HT_to_array) ( const VgHashTable *table, 106 /*OUT*/ UInt* n_elems ); 107 108 /* Reset the table's iterator to point to the first element. */ 109 extern void VG_(HT_ResetIter) ( VgHashTable *table ); 110 111 /* Return the element pointed to by the iterator and move on to the 112 next one. Returns NULL if the last one has been passed, or if 113 HT_ResetIter() has not been called previously. Asserts if the 114 table has been modified (HT_add_node, HT_remove) since 115 HT_ResetIter. This guarantees that callers cannot screw up by 116 modifying the table whilst iterating over it (and is necessary to 117 make the implementation safe; specifically we must guarantee that 118 the table will not get resized whilst iteration is happening. 119 Since resizing only happens as a result of calling HT_add_node, 120 disallowing HT_add_node during iteration should give the required 121 assurance. */ 122 extern void* VG_(HT_Next) ( VgHashTable *table ); 123 124 /* Remove the element pointed to by the iterator and leave the iterator 125 in a state where VG_(HT_Next) will return the element just after the removed 126 node. 127 This allows removing elements from the table whilst iterating over it. 128 Note that removing an entry does not resize the hash table, making this 129 safe. */ 130 extern void VG_(HT_remove_at_Iter)( VgHashTable *table ); 131 132 /* Destroy a table and deallocates the memory used by the nodes using 133 freenode_fn.*/ 134 extern void VG_(HT_destruct) ( VgHashTable *table, void(*freenode_fn)(void*) ); 135 136 137 #endif // __PUB_TOOL_HASHTABLE_H 138 139 /*--------------------------------------------------------------------*/ 140 /*--- end ---*/ 141 /*--------------------------------------------------------------------*/ 142