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, write to the Free Software
  46    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  47    02111-1307, USA.
  48
  49    The GNU General Public License is contained in the file COPYING.
  50 */
  51
  52 #ifndef __PUB_TOOL_WORDFM_H
  53 #define __PUB_TOOL_WORDFM_H
  54
  55 #include "pub_tool_basics.h"    // Word
  56
  57 //------------------------------------------------------------------//
  58 //---                           WordFM                           ---//
  59 //---                      Public interface                      ---//
  60 //------------------------------------------------------------------//
  61
  62 /* As of r7409 (15 Feb 08), all these word-based abstractions (WordFM,
  63    WordSet, WordBag) now operate on unsigned words (UWord), whereas
  64    they previously operated on signed words (Word).  This became a
  65    problem, when using unboxed comparisons (when kCmp == NULL), with
  66    the introduction of VG_(initIterAtFM), which allows iteration over
  67    parts of mappings.  Iterating over a mapping in increasing order of
  68    signed Word keys is not what callers expect when iterating through
  69    maps whose keys represent addresses (Addr) since Addr is unsigned,
  70    and causes logical problems and assertion failures. */
  71
  72 typedef  struct _WordFM  WordFM; /* opaque */
  73
  74 /* Allocate and initialise a WordFM.  If kCmp is non-NULL, elements in
  75    the set are ordered according to the ordering specified by kCmp,
  76    which becomes obvious if you use VG_(initIterFM),
  77    VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over
  78    sections of the map, or the whole thing.  If kCmp is NULL then the
  79    ordering used is unsigned word ordering (UWord) on the key
  80    values.
  81    The function never returns NULL. */
  82 WordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
  83                      const HChar* cc,
  84                      void  (*dealloc)(void*),
  85                      Word  (*kCmp)(UWord,UWord) );
  86
  87 /* Free up the FM.  If kFin is non-NULL, it is applied to keys
  88    before the FM is deleted; ditto with vFin for vals. */
  89 void VG_(deleteFM) ( WordFM*, void(*kFin)(UWord), void(*vFin)(UWord) );
  90
  91 /* Add (k,v) to fm.  If a binding for k already exists, it is updated
  92    to map to this new v.  In that case we should really return the
  93    previous v so that caller can finalise it.  Oh well.  Returns
  94    True if a binding for k already exists. */
  95 Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v );
  96
  97 // Delete key from fm, returning associated key and val if found
  98 Bool VG_(delFromFM) ( WordFM* fm,
  99                       /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key );
 100
 101 // Look up in fm, assigning found key & val at spec'd addresses
 102 Bool VG_(lookupFM) ( const WordFM* fm,
 103                      /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key );
 104
 105 // Find the closest key values bracketing the given key, assuming the
 106 // given key is not present in the map.  minKey and maxKey are the
 107 // minimum and maximum possible key values.  The resulting bracket
 108 // values are returned in *kMinP and *kMaxP.  It follows that if fm is
 109 // empty then the returned values are simply minKey and maxKey.
 110 //
 111 // For convenience the associated value fields are also returned
 112 // through *vMinP and *vMaxP.  To make that possible in the general
 113 // case, the caller must supply via minVal and maxVal, the value
 114 // fields associated with minKey and maxKey.
 115 //
 116 // If the operation was successful (that is, the given key is not
 117 // present), True is returned.  If the given key is in fact present,
 118 // False is returned, and *kMinP, *vMinP, *kMaxP and *vMaxP are
 119 // undefined.  Any of kMinP, vMinP, kMaxP and vMaxP may be safely
 120 // supplied as NULL.
 121 Bool VG_(findBoundsFM)( const WordFM* fm,
 122                         /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP,
 123                         /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP,
 124                         UWord minKey, UWord minVal,
 125                         UWord maxKey, UWord maxVal,
 126                         UWord key );
 127
 128 // How many elements are there in fm?  NOTE: dangerous in the
 129 // sense that this is not an O(1) operation but rather O(N),
 130 // since it involves walking the whole tree.
 131 UWord VG_(sizeFM) ( const WordFM* fm );
 132
 133 // set up FM for iteration
 134 void VG_(initIterFM) ( WordFM* fm );
 135
 136 // set up FM for iteration so that the first key subsequently produced
 137 // by VG_(nextIterFM) is the smallest key in the map >= start_at.
 138 // Naturally ">=" is defined by the comparison function supplied to
 139 // VG_(newFM), as documented above.
 140 void VG_(initIterAtFM) ( WordFM* fm, UWord start_at );
 141
 142 // get next key/val pair.  Will assert if fm has been modified
 143 // or looked up in since initIterFM/initIterWithStartFM was called.
 144 Bool VG_(nextIterFM) ( WordFM* fm,
 145                        /*OUT*/UWord* pKey, /*OUT*/UWord* pVal );
 146
 147 // Finish an FM iteration
 148 void VG_(doneIterFM) ( WordFM* fm );
 149
 150 // Deep copy a FM.  If dopyK is NULL, keys are copied verbatim.
 151 // If non-null, dopyK is applied to each key to generate the
 152 // version in the new copy.  dopyK may be called with a NULL argument
 153 // in which case it should return NULL. For all other argument values
 154 // dopyK must not return NULL. Ditto with dopyV for values.
 155 // VG_(dopyFM) never returns NULL.
 156 WordFM* VG_(dopyFM) ( WordFM* fm,
 157                       UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) );
 158
 159 //------------------------------------------------------------------//
 160 //---                         end WordFM                         ---//
 161 //---                      Public interface                      ---//
 162 //------------------------------------------------------------------//
 163
 164 //------------------------------------------------------------------//
 165 //---                WordBag (unboxed words only)                ---//
 166 //---                      Public interface                      ---//
 167 //------------------------------------------------------------------//
 168
 169 typedef  struct _WordBag  WordBag; /* opaque */
 170
 171 /* Allocate and initialise a WordBag. Never returns NULL. */
 172 WordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
 173                        const HChar* cc,
 174                        void  (*dealloc)(void*) );
 175
 176 /* Free up the Bag. */
 177 void VG_(deleteBag) ( WordBag* );
 178
 179 /* Add a word. */
 180 void VG_(addToBag)( WordBag*, UWord );
 181
 182 /* Find out how many times the given word exists in the bag. */
 183 UWord VG_(elemBag) ( const WordBag*, UWord );
 184
 185 /* Delete a word from the bag. */
 186 Bool VG_(delFromBag)( WordBag*, UWord );
 187
 188 /* Is the bag empty? */
 189 Bool VG_(isEmptyBag)( const WordBag* );
 190
 191 /* Does the bag have exactly one element? */
 192 Bool VG_(isSingletonTotalBag)( const WordBag* );
 193
 194 /* Return an arbitrary element from the bag. */
 195 UWord VG_(anyElementOfBag)( const WordBag* );
 196
 197 /* How many different / total elements are in the bag? */
 198 UWord VG_(sizeUniqueBag)( const WordBag* ); /* fast */
 199 UWord VG_(sizeTotalBag)( const WordBag* );  /* warning: slow */
 200
 201 /* Iterating over the elements of a bag. */
 202 void VG_(initIterBag)( WordBag* );
 203 Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount );
 204 void VG_(doneIterBag)( WordBag* );
 205
 206 //------------------------------------------------------------------//
 207 //---             end WordBag (unboxed words only)               ---//
 208 //---                      Public interface                      ---//
 209 //------------------------------------------------------------------//
 210
 211 #endif /* ! __PUB_TOOL_WORDFM_H */
 212
 213 /*--------------------------------------------------------------------*/
 214 /*--- end                                        pub_tool_wordfm.h ---*/
 215 /*--------------------------------------------------------------------*/