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