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-2013 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 #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. */ 58 extern VgHashTable VG_(HT_construct) ( const HChar* name ); 59 60 /* Count the number of nodes in a table. */ 61 extern Int VG_(HT_count_nodes) ( 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 in the table. Returns NULL if not found. If entries 67 * with duplicate keys are present, the most recently-added of the dups will 68 * be returned, but it's probably better to avoid dups altogether. */ 69 extern void* VG_(HT_lookup) ( VgHashTable table, UWord key ); 70 71 /* Removes a VgHashNode from the table. Returns NULL if not found. */ 72 extern void* VG_(HT_remove) ( VgHashTable table, UWord key ); 73 74 /* Allocates a suitably-sized array, copies pointers to all the hashtable 75 elements into it, then returns both the array and the size of it. The 76 array must be freed with VG_(free). */ 77 extern VgHashNode** VG_(HT_to_array) ( VgHashTable t, /*OUT*/ UInt* n_elems ); 78 79 /* Reset the table's iterator to point to the first element. */ 80 extern void VG_(HT_ResetIter) ( VgHashTable table ); 81 82 /* Return the element pointed to by the iterator and move on to the 83 next one. Returns NULL if the last one has been passed, or if 84 HT_ResetIter() has not been called previously. Asserts if the 85 table has been modified (HT_add_node, HT_remove) since 86 HT_ResetIter. This guarantees that callers cannot screw up by 87 modifying the table whilst iterating over it (and is necessary to 88 make the implementation safe; specifically we must guarantee that 89 the table will not get resized whilst iteration is happening. 90 Since resizing only happens as a result of calling HT_add_node, 91 disallowing HT_add_node during iteration should give the required 92 assurance. */ 93 extern void* VG_(HT_Next) ( VgHashTable table ); 94 95 /* Destroy a table and deallocates the memory used by the nodes using 96 freenode_fn.*/ 97 extern void VG_(HT_destruct) ( VgHashTable t, void(*freenode_fn)(void*) ); 98 99 100 #endif // __PUB_TOOL_HASHTABLE_H 101 102 /*--------------------------------------------------------------------*/ 103 /*--- end ---*/ 104 /*--------------------------------------------------------------------*/ 105
