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 /*--------------------------------------------------------------------*/ 216