include/pub_tool_hashtable.h

   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-2017 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, see <http://www.gnu.org/licenses/>.
  25
  26    The GNU General Public License is contained in the file COPYING.
  27 */
  28
  29 #ifndef __PUB_TOOL_HASHTABLE_H
  30 #define __PUB_TOOL_HASHTABLE_H
  31
  32 #include "pub_tool_basics.h"   // VG_ macro
  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. The function never returns NULL. */
  56 extern VgHashTable *VG_(HT_construct) ( const HChar* name );
  57
  58 /* Count the number of nodes in a table. */
  59 extern UInt VG_(HT_count_nodes) ( const 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 by key in the table.
  65  * Returns NULL if not found.  If entries
  66  * with duplicate keys are present, the most recently-added of the dups will
  67  * be returned, but it's probably better to avoid dups altogether. */
  68 extern void* VG_(HT_lookup) ( const VgHashTable *table, UWord key );
  69
  70 /* Removes a VgHashNode by key from the table.  Returns NULL if not found. */
  71 extern void* VG_(HT_remove) ( VgHashTable *table, UWord key );
  72
  73 typedef Word  (*HT_Cmp_t) ( const void* node1, const void* node2 );
  74
  75 /* Same as VG_(HT_lookup) and VG_(HT_remove), but allowing a part of or
  76    the full element to be compared for equality, not only the key.
  77    The typical use for the below function is to store a hash value of the
  78    element in the key, and have the comparison function checking for equality
  79    of the full element data.
  80    Attention about the comparison function:
  81     * It must *not* compare the 'next' pointer.
  82     * when comparing the rest of the node, if the node data contains holes
  83       between components, either the node memory should be fully initialised
  84       (e.g. allocated using VG_(calloc)) or each component should be compared
  85        individually.
  86    Note that the cmp function is only called for elements that already
  87    have keys that are equal. So, it is not needed for cmp to check for
  88    key equality. */
  89 extern void* VG_(HT_gen_lookup) ( const VgHashTable *table, const void* node,
  90                                   HT_Cmp_t cmp );
  91 extern void* VG_(HT_gen_remove) ( VgHashTable *table, const void* node,
  92                                   HT_Cmp_t cmp );
  93
  94 /* Output detailed usage/collision statistics.
  95    cmp will be used to verify if 2 elements with the same key are equal.
  96    Use NULL cmp if the hash table elements are only to be compared by key. */
  97 extern void VG_(HT_print_stats) ( const VgHashTable *table, HT_Cmp_t cmp );
  98
  99 /* Allocates a suitably-sized array, copies pointers to all the hashtable
 100    elements into it, then returns both the array and the size of it.  The
 101    array must be freed with VG_(free). If the hashtable is empty, the
 102    function returns NULL and assigns *nelems = 0. */
 103 extern VgHashNode** VG_(HT_to_array) ( const VgHashTable *table,
 104                                        /*OUT*/ UInt* n_elems );
 105
 106 /* Reset the table's iterator to point to the first element. */
 107 extern void VG_(HT_ResetIter) ( VgHashTable *table );
 108
 109 /* Return the element pointed to by the iterator and move on to the
 110    next one.  Returns NULL if the last one has been passed, or if
 111    HT_ResetIter() has not been called previously.  Asserts if the
 112    table has been modified (HT_add_node, HT_remove) since
 113    HT_ResetIter.  This guarantees that callers cannot screw up by
 114    modifying the table whilst iterating over it (and is necessary to
 115    make the implementation safe; specifically we must guarantee that
 116    the table will not get resized whilst iteration is happening.
 117    Since resizing only happens as a result of calling HT_add_node,
 118    disallowing HT_add_node during iteration should give the required
 119    assurance. */
 120 extern void* VG_(HT_Next) ( VgHashTable *table );
 121
 122 /* Remove the element pointed to by the iterator and leave the iterator
 123    in a state where VG_(HT_Next) will return the element just after the removed
 124    node.
 125    This allows removing elements from the table whilst iterating over it.
 126    Note that removing an entry does not resize the hash table, making this
 127    safe. */
 128 extern void VG_(HT_remove_at_Iter)( VgHashTable *table );
 129
 130 /* Destroy a table and deallocates the memory used by the nodes using
 131    freenode_fn.*/
 132 extern void VG_(HT_destruct) ( VgHashTable *table, void(*freenode_fn)(void*) );
 133
 134
 135 #endif   // __PUB_TOOL_HASHTABLE_H
 136
 137 /*--------------------------------------------------------------------*/
 138 /*--- end                                                          ---*/
 139 /*--------------------------------------------------------------------*/