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-2012 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 /* Generic type for a separately-chained hash table. Via a kind of dodgy 35 C-as-C++ style inheritance, tools can extend the VgHashNode type, so long 36 as the first two fields match the sizes of these two fields. Requires 37 a bit of casting by the tool. */ 38 39 // Problems with this data structure: 40 // - Separate chaining gives bad cache behaviour. Hash tables with linear 41 // probing give better cache behaviour. 42 43 typedef 44 struct _VgHashNode { 45 struct _VgHashNode * next; 46 UWord key; 47 } 48 VgHashNode; 49 50 typedef struct _VgHashTable * VgHashTable; 51 52 /* Make a new table. Allocates the memory with VG_(calloc)(), so can 53 be freed with VG_(free)(). The table starts small but will 54 periodically be expanded. This is transparent to the users of this 55 module. */ 56 extern VgHashTable VG_(HT_construct) ( HChar* name ); 57 58 /* Count the number of nodes in a table. */ 59 extern Int VG_(HT_count_nodes) ( VgHashTable table ); 60 61 /* Add a node to the table. Duplicate keys are permitted. */ 62 extern void VG_(HT_add_node) ( VgHashTable t, void* node ); 63 64 /* Looks up a VgHashNode in the table. Returns NULL if not found. If entries 65 * with duplicate keys are present, the most recently-added of the dups will 66 * be returned, but it's probably better to avoid dups altogether. */ 67 extern void* VG_(HT_lookup) ( VgHashTable table, UWord key ); 68 69 /* Removes a VgHashNode from the table. Returns NULL if not found. */ 70 extern void* VG_(HT_remove) ( VgHashTable table, UWord key ); 71 72 /* Allocates a suitably-sized array, copies pointers to all the hashtable 73 elements into it, then returns both the array and the size of it. The 74 array must be freed with VG_(free). */ 75 extern VgHashNode** VG_(HT_to_array) ( VgHashTable t, /*OUT*/ UInt* n_elems ); 76 77 /* Reset the table's iterator to point to the first element. */ 78 extern void VG_(HT_ResetIter) ( VgHashTable table ); 79 80 /* Return the element pointed to by the iterator and move on to the 81 next one. Returns NULL if the last one has been passed, or if 82 HT_ResetIter() has not been called previously. Asserts if the 83 table has been modified (HT_add_node, HT_remove) since 84 HT_ResetIter. This guarantees that callers cannot screw up by 85 modifying the table whilst iterating over it (and is necessary to 86 make the implementation safe; specifically we must guarantee that 87 the table will not get resized whilst iteration is happening. 88 Since resizing only happens as a result of calling HT_add_node, 89 disallowing HT_add_node during iteration should give the required 90 assurance. */ 91 extern void* VG_(HT_Next) ( VgHashTable table ); 92 93 /* Destroy a table and deallocates the memory used by the nodes using 94 freenode_fn.*/ 95 extern void VG_(HT_destruct) ( VgHashTable t, void(*freenode_fn)(void*) ); 96 97 98 #endif // __PUB_TOOL_HASHTABLE_H 99 100 /*--------------------------------------------------------------------*/ 101 /*--- end ---*/ 102 /*--------------------------------------------------------------------*/ 103
