pub_tool_hashtable.h revision b32f58018498ea2225959b0ba11c18f0c433deef
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-2011 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/* 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 43typedef 44 struct _VgHashNode { 45 struct _VgHashNode * next; 46 UWord key; 47 } 48 VgHashNode; 49 50typedef 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. */ 56extern VgHashTable VG_(HT_construct) ( HChar* name ); 57 58/* Count the number of nodes in a table. */ 59extern Int VG_(HT_count_nodes) ( VgHashTable table ); 60 61/* Add a node to the table. Duplicate keys are permitted. */ 62extern 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. */ 67extern void* VG_(HT_lookup) ( VgHashTable table, UWord key ); 68 69/* Removes a VgHashNode from the table. Returns NULL if not found. */ 70extern 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). */ 75extern VgHashNode** VG_(HT_to_array) ( VgHashTable t, /*OUT*/ UInt* n_elems ); 76 77/* Reset the table's iterator to point to the first element. */ 78extern 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. */ 91extern void* VG_(HT_Next) ( VgHashTable table ); 92 93/* Destroy a table. */ 94extern void VG_(HT_destruct) ( VgHashTable t ); 95 96 97#endif // __PUB_TOOL_HASHTABLE_H 98 99/*--------------------------------------------------------------------*/ 100/*--- end ---*/ 101/*--------------------------------------------------------------------*/ 102