include/pub_tool_wordfm.h

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- An AVL tree based finite map for word keys and word values.  ---*/
   4 /*--- Inspired by Haskell's "FiniteMap" library.                   ---*/
   5 /*---                                            pub_tool_wordfm.h ---*/
   6 /*--------------------------------------------------------------------*/
   7
   8 /*
   9    This file is part of Valgrind, a dynamic binary instrumentation
  10    framework.
  11
  12    Copyright (C) 2007-2017 Julian Seward
  13       jseward@acm.org
  14
  15    This code is based on previous work by Nicholas Nethercote
  16    (coregrind/m_oset.c) which is
  17
  18    Copyright (C) 2005-2017 Nicholas Nethercote
  19        njn@valgrind.org
  20
  21    which in turn was derived partially from:
  22
  23       AVL C library
  24       Copyright (C) 2000,2002  Daniel Nagy
  25
  26       This program is free software; you can redistribute it and/or
  27       modify it under the terms of the GNU General Public License as
  28       published by the Free Software Foundation; either version 2 of
  29       the License, or (at your option) any later version.
  30       [...]
  31
  32       (taken from libavl-0.4/debian/copyright)
  33
  34    This program is free software; you can redistribute it and/or
  35    modify it under the terms of the GNU General Public License as
  36    published by the Free Software Foundation; either version 2 of the
  37    License, or (at your option) any later version.
  38
  39    This program is distributed in the hope that it will be useful, but
  40    WITHOUT ANY WARRANTY; without even the implied warranty of
  41    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  42    General Public License for more details.
  43
  44    You should have received a copy of the GNU General Public License
  45    along with this program; if not, see <http://www.gnu.org/licenses/>.
  46
  47    The GNU General Public License is contained in the file COPYING.
  48 */
  49
  50 #ifndef __PUB_TOOL_WORDFM_H
  51 #define __PUB_TOOL_WORDFM_H
  52
  53 #include "pub_tool_basics.h"    // Word
  54
  55 //------------------------------------------------------------------//
  56 //---                           WordFM                           ---//
  57 //---                      Public interface                      ---//
  58 //------------------------------------------------------------------//
  59
  60 /* As of r7409 (15 Feb 08), all these word-based abstractions (WordFM,
  61    WordSet, WordBag) now operate on unsigned words (UWord), whereas
  62    they previously operated on signed words (Word).  This became a
  63    problem, when using unboxed comparisons (when kCmp == NULL), with
  64    the introduction of VG_(initIterAtFM), which allows iteration over
  65    parts of mappings.  Iterating over a mapping in increasing order of
  66    signed Word keys is not what callers expect when iterating through
  67    maps whose keys represent addresses (Addr) since Addr is unsigned,
  68    and causes logical problems and assertion failures. */
  69
  70 typedef  struct _WordFM  WordFM; /* opaque */
  71
  72 /* Allocate and initialise a WordFM.  If kCmp is non-NULL, elements in
  73    the set are ordered according to the ordering specified by kCmp,
  74    which becomes obvious if you use VG_(initIterFM),
  75    VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over
  76    sections of the map, or the whole thing.  If kCmp is NULL then the
  77    ordering used is unsigned word ordering (UWord) on the key
  78    values.
  79    The function never returns NULL. */
  80 WordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
  81                      const HChar* cc,
  82                      void  (*dealloc)(void*),
  83                      Word  (*kCmp)(UWord,UWord) );
  84
  85 /* Free up the FM.  If kFin is non-NULL, it is applied to keys
  86    before the FM is deleted; ditto with vFin for vals. */
  87 void VG_(deleteFM) ( WordFM*, void(*kFin)(UWord), void(*vFin)(UWord) );
  88
  89 /* Add (k,v) to fm.  If a binding for k already exists, it is updated
  90    to map to this new v.  In that case we should really return the
  91    previous v so that caller can finalise it.  Oh well.  Returns
  92    True if a binding for k already exists. */
  93 Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v );
  94
  95 // Delete key from fm, returning associated key and val if found
  96 Bool VG_(delFromFM) ( WordFM* fm,
  97                       /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key );
  98
  99 // Look up in fm, assigning found key & val at spec'd addresses
 100 Bool VG_(lookupFM) ( const WordFM* fm,
 101                      /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key );
 102
 103 // Find the closest key values bracketing the given key, assuming the
 104 // given key is not present in the map.  minKey and maxKey are the
 105 // minimum and maximum possible key values.  The resulting bracket
 106 // values are returned in *kMinP and *kMaxP.  It follows that if fm is
 107 // empty then the returned values are simply minKey and maxKey.
 108 //
 109 // For convenience the associated value fields are also returned
 110 // through *vMinP and *vMaxP.  To make that possible in the general
 111 // case, the caller must supply via minVal and maxVal, the value
 112 // fields associated with minKey and maxKey.
 113 //
 114 // If the operation was successful (that is, the given key is not
 115 // present), True is returned.  If the given key is in fact present,
 116 // False is returned, and *kMinP, *vMinP, *kMaxP and *vMaxP are
 117 // undefined.  Any of kMinP, vMinP, kMaxP and vMaxP may be safely
 118 // supplied as NULL.
 119 Bool VG_(findBoundsFM)( const WordFM* fm,
 120                         /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP,
 121                         /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP,
 122                         UWord minKey, UWord minVal,
 123                         UWord maxKey, UWord maxVal,
 124                         UWord key );
 125
 126 // How many elements are there in fm?  NOTE: dangerous in the
 127 // sense that this is not an O(1) operation but rather O(N),
 128 // since it involves walking the whole tree.
 129 UWord VG_(sizeFM) ( const WordFM* fm );
 130
 131 // set up FM for iteration
 132 void VG_(initIterFM) ( WordFM* fm );
 133
 134 // set up FM for iteration so that the first key subsequently produced
 135 // by VG_(nextIterFM) is the smallest key in the map >= start_at.
 136 // Naturally ">=" is defined by the comparison function supplied to
 137 // VG_(newFM), as documented above.
 138 void VG_(initIterAtFM) ( WordFM* fm, UWord start_at );
 139
 140 // get next key/val pair.  Will assert if fm has been modified
 141 // or looked up in since initIterFM/initIterWithStartFM was called.
 142 Bool VG_(nextIterFM) ( WordFM* fm,
 143                        /*OUT*/UWord* pKey, /*OUT*/UWord* pVal );
 144
 145 // Finish an FM iteration
 146 void VG_(doneIterFM) ( WordFM* fm );
 147
 148 // Deep copy a FM.  If dopyK is NULL, keys are copied verbatim.
 149 // If non-null, dopyK is applied to each key to generate the
 150 // version in the new copy.  dopyK may be called with a NULL argument
 151 // in which case it should return NULL. For all other argument values
 152 // dopyK must not return NULL. Ditto with dopyV for values.
 153 // VG_(dopyFM) never returns NULL.
 154 WordFM* VG_(dopyFM) ( WordFM* fm,
 155                       UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) );
 156
 157 //------------------------------------------------------------------//
 158 //---                         end WordFM                         ---//
 159 //---                      Public interface                      ---//
 160 //------------------------------------------------------------------//
 161
 162 //------------------------------------------------------------------//
 163 //---                WordBag (unboxed words only)                ---//
 164 //---                      Public interface                      ---//
 165 //------------------------------------------------------------------//
 166
 167 typedef  struct _WordBag  WordBag; /* opaque */
 168
 169 /* Allocate and initialise a WordBag. Never returns NULL. */
 170 WordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
 171                        const HChar* cc,
 172                        void  (*dealloc)(void*) );
 173
 174 /* Free up the Bag. */
 175 void VG_(deleteBag) ( WordBag* );
 176
 177 /* Add a word. */
 178 void VG_(addToBag)( WordBag*, UWord );
 179
 180 /* Find out how many times the given word exists in the bag. */
 181 UWord VG_(elemBag) ( const WordBag*, UWord );
 182
 183 /* Delete a word from the bag. */
 184 Bool VG_(delFromBag)( WordBag*, UWord );
 185
 186 /* Is the bag empty? */
 187 Bool VG_(isEmptyBag)( const WordBag* );
 188
 189 /* Does the bag have exactly one element? */
 190 Bool VG_(isSingletonTotalBag)( const WordBag* );
 191
 192 /* Return an arbitrary element from the bag. */
 193 UWord VG_(anyElementOfBag)( const WordBag* );
 194
 195 /* How many different / total elements are in the bag? */
 196 UWord VG_(sizeUniqueBag)( const WordBag* ); /* fast */
 197 UWord VG_(sizeTotalBag)( const WordBag* );  /* warning: slow */
 198
 199 /* Iterating over the elements of a bag. */
 200 void VG_(initIterBag)( WordBag* );
 201 Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount );
 202 void VG_(doneIterBag)( WordBag* );
 203
 204 //------------------------------------------------------------------//
 205 //---             end WordBag (unboxed words only)               ---//
 206 //---                      Public interface                      ---//
 207 //------------------------------------------------------------------//
 208
 209 #endif /* ! __PUB_TOOL_WORDFM_H */
 210
 211 /*--------------------------------------------------------------------*/
 212 /*--- end                                        pub_tool_wordfm.h ---*/
 213 /*--------------------------------------------------------------------*/