include/valgrind/pub_tool_hashtable.h

0001
0002 /*--------------------------------------------------------------------*/
0003 /*--- A hash table implementation.            pub_tool_hashtable.h ---*/
0004 /*--------------------------------------------------------------------*/
0005
0006 /*
0007    This file is part of Valgrind, a dynamic binary instrumentation
0008    framework.
0009
0010    Copyright (C) 2005-2017 Nicholas Nethercote
0011       njn@valgrind.org
0012
0013    This program is free software; you can redistribute it and/or
0014    modify it under the terms of the GNU General Public License as
0015    published by the Free Software Foundation; either version 2 of the
0016    License, or (at your option) any later version.
0017
0018    This program is distributed in the hope that it will be useful, but
0019    WITHOUT ANY WARRANTY; without even the implied warranty of
0020    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0021    General Public License for more details.
0022
0023    You should have received a copy of the GNU General Public License
0024    along with this program; if not, see <http://www.gnu.org/licenses/>.
0025
0026    The GNU General Public License is contained in the file COPYING.
0027 */
0028
0029 #ifndef __PUB_TOOL_HASHTABLE_H
0030 #define __PUB_TOOL_HASHTABLE_H
0031
0032 #include "pub_tool_basics.h"   // VG_ macro
0033
0034 /* Generic type for a separately-chained hash table.  Via a kind of dodgy
0035    C-as-C++ style inheritance, tools can extend the VgHashNode type, so long
0036    as the first two fields match the sizes of these two fields.  Requires
0037    a bit of casting by the tool. */
0038
0039 // Problems with this data structure:
0040 // - Separate chaining gives bad cache behaviour.  Hash tables with linear
0041 //   probing give better cache behaviour.
0042
0043 typedef
0044    struct _VgHashNode {
0045       struct _VgHashNode * next;
0046       UWord              key;
0047    }
0048    VgHashNode;
0049
0050 typedef struct _VgHashTable VgHashTable;
0051
0052 /* Make a new table.  Allocates the memory with VG_(calloc)(), so can
0053    be freed with VG_(free)().  The table starts small but will
0054    periodically be expanded.  This is transparent to the users of this
0055    module. The function never returns NULL. */
0056 extern VgHashTable *VG_(HT_construct) ( const HChar* name );
0057
0058 /* Count the number of nodes in a table. */
0059 extern UInt VG_(HT_count_nodes) ( const VgHashTable *table );
0060
0061 /* Add a node to the table.  Duplicate keys are permitted. */
0062 extern void VG_(HT_add_node) ( VgHashTable *t, void* node );
0063
0064 /* Looks up a VgHashNode by key in the table.
0065  * Returns NULL if not found.  If entries
0066  * with duplicate keys are present, the most recently-added of the dups will
0067  * be returned, but it's probably better to avoid dups altogether. */
0068 extern void* VG_(HT_lookup) ( const VgHashTable *table, UWord key );
0069
0070 /* Removes a VgHashNode by key from the table.  Returns NULL if not found. */
0071 extern void* VG_(HT_remove) ( VgHashTable *table, UWord key );
0072
0073 typedef Word  (*HT_Cmp_t) ( const void* node1, const void* node2 );
0074
0075 /* Same as VG_(HT_lookup) and VG_(HT_remove), but allowing a part of or
0076    the full element to be compared for equality, not only the key.
0077    The typical use for the below function is to store a hash value of the
0078    element in the key, and have the comparison function checking for equality
0079    of the full element data.
0080    Attention about the comparison function:
0081     * It must *not* compare the 'next' pointer.
0082     * when comparing the rest of the node, if the node data contains holes
0083       between components, either the node memory should be fully initialised
0084       (e.g. allocated using VG_(calloc)) or each component should be compared
0085        individually.
0086    Note that the cmp function is only called for elements that already
0087    have keys that are equal. So, it is not needed for cmp to check for
0088    key equality. */
0089 extern void* VG_(HT_gen_lookup) ( const VgHashTable *table, const void* node,
0090                                   HT_Cmp_t cmp );
0091 extern void* VG_(HT_gen_remove) ( VgHashTable *table, const void* node,
0092                                   HT_Cmp_t cmp );
0093
0094 /* Output detailed usage/collision statistics.
0095    cmp will be used to verify if 2 elements with the same key are equal.
0096    Use NULL cmp if the hash table elements are only to be compared by key. */
0097 extern void VG_(HT_print_stats) ( const VgHashTable *table, HT_Cmp_t cmp );
0098
0099 /* Allocates a suitably-sized array, copies pointers to all the hashtable
0100    elements into it, then returns both the array and the size of it.  The
0101    array must be freed with VG_(free). If the hashtable is empty, the
0102    function returns NULL and assigns *nelems = 0. */
0103 extern VgHashNode** VG_(HT_to_array) ( const VgHashTable *table,
0104                                        /*OUT*/ UInt* n_elems );
0105
0106 /* Reset the table's iterator to point to the first element. */
0107 extern void VG_(HT_ResetIter) ( VgHashTable *table );
0108
0109 /* Return the element pointed to by the iterator and move on to the
0110    next one.  Returns NULL if the last one has been passed, or if
0111    HT_ResetIter() has not been called previously.  Asserts if the
0112    table has been modified (HT_add_node, HT_remove) since
0113    HT_ResetIter.  This guarantees that callers cannot screw up by
0114    modifying the table whilst iterating over it (and is necessary to
0115    make the implementation safe; specifically we must guarantee that
0116    the table will not get resized whilst iteration is happening.
0117    Since resizing only happens as a result of calling HT_add_node,
0118    disallowing HT_add_node during iteration should give the required
0119    assurance. */
0120 extern void* VG_(HT_Next) ( VgHashTable *table );
0121
0122 /* Remove the element pointed to by the iterator and leave the iterator
0123    in a state where VG_(HT_Next) will return the element just after the removed
0124    node.
0125    This allows removing elements from the table whilst iterating over it.
0126    Note that removing an entry does not resize the hash table, making this
0127    safe. */
0128 extern void VG_(HT_remove_at_Iter)( VgHashTable *table );
0129
0130 /* Destroy a table and deallocates the memory used by the nodes using
0131    freenode_fn.*/
0132 extern void VG_(HT_destruct) ( VgHashTable *table, void(*freenode_fn)(void*) );
0133
0134
0135 #endif   // __PUB_TOOL_HASHTABLE_H
0136
0137 /*--------------------------------------------------------------------*/
0138 /*--- end                                                          ---*/
0139 /*--------------------------------------------------------------------*/