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-2013 Julian Seward 13 jseward (at) 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-2013 Nicholas Nethercote 19 njn (at) 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 WordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar* cc, SizeT ), 82 const HChar* cc, 83 void (*dealloc)(void*), 84 Word (*kCmp)(UWord,UWord) ); 85 86 /* Free up the FM. If kFin is non-NULL, it is applied to keys 87 before the FM is deleted; ditto with vFin for vals. */ 88 void VG_(deleteFM) ( WordFM*, void(*kFin)(UWord), void(*vFin)(UWord) ); 89 90 /* Add (k,v) to fm. If a binding for k already exists, it is updated 91 to map to this new v. In that case we should really return the 92 previous v so that caller can finalise it. Oh well. Returns 93 True if a binding for k already exists. */ 94 Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v ); 95 96 // Delete key from fm, returning associated key and val if found 97 Bool VG_(delFromFM) ( WordFM* fm, 98 /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key ); 99 100 // Look up in fm, assigning found key & val at spec'd addresses 101 Bool VG_(lookupFM) ( WordFM* fm, 102 /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key ); 103 104 // Find the closest key values bracketing the given key, assuming the 105 // given key is not present in the map. minKey and maxKey are the 106 // minimum and maximum possible key values. The resulting bracket 107 // values are returned in *kMinP and *kMaxP. It follows that if fm is 108 // empty then the returned values are simply minKey and maxKey. 109 // 110 // For convenience the associated value fields are also returned 111 // through *vMinP and *vMaxP. To make that possible in the general 112 // case, the caller must supply via minVal and maxVal, the value 113 // fields associated with minKey and maxKey. 114 // 115 // If the operation was successful (that is, the given key is not 116 // present), True is returned. If the given key is in fact present, 117 // False is returned, and *kMinP, *vMinP, *kMaxP and *vMaxP are 118 // undefined. Any of kMinP, vMinP, kMaxP and vMaxP may be safely 119 // supplied as NULL. 120 Bool VG_(findBoundsFM)( WordFM* fm, 121 /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP, 122 /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP, 123 UWord minKey, UWord minVal, 124 UWord maxKey, UWord maxVal, 125 UWord key ); 126 127 // How many elements are there in fm? NOTE: dangerous in the 128 // sense that this is not an O(1) operation but rather O(N), 129 // since it involves walking the whole tree. 130 UWord VG_(sizeFM) ( WordFM* fm ); 131 132 // Is fm empty? This at least is an O(1) operation. 133 // Code is present in m_wordfm.c but commented out due to no 134 // current usage. Un-comment (and TEST IT) if required. 135 //Bool VG_(isEmptyFM)( WordFM* fm ); 136 137 // set up FM for iteration 138 void VG_(initIterFM) ( WordFM* fm ); 139 140 // set up FM for iteration so that the first key subsequently produced 141 // by VG_(nextIterFM) is the smallest key in the map >= start_at. 142 // Naturally ">=" is defined by the comparison function supplied to 143 // VG_(newFM), as documented above. 144 void VG_(initIterAtFM) ( WordFM* fm, UWord start_at ); 145 146 // get next key/val pair. Will assert if fm has been modified 147 // or looked up in since initIterFM/initIterWithStartFM was called. 148 Bool VG_(nextIterFM) ( WordFM* fm, 149 /*OUT*/UWord* pKey, /*OUT*/UWord* pVal ); 150 151 // clear the I'm iterating flag 152 void VG_(doneIterFM) ( WordFM* fm ); 153 154 // Deep copy a FM. If dopyK is NULL, keys are copied verbatim. 155 // If non-null, dopyK is applied to each key to generate the 156 // version in the new copy. In that case, if the argument to dopyK 157 // is non-NULL but the result is NULL, it is assumed that dopyK 158 // could not allocate memory, in which case the copy is abandoned 159 // and NULL is returned. Ditto with dopyV for values. 160 WordFM* VG_(dopyFM) ( WordFM* fm, 161 UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) ); 162 163 // admin: what's the 'common' allocation size (for tree nodes?) 164 SizeT VG_(getNodeSizeFM)( void ); 165 166 //------------------------------------------------------------------// 167 //--- end WordFM ---// 168 //--- Public interface ---// 169 //------------------------------------------------------------------// 170 171 //------------------------------------------------------------------// 172 //--- WordBag (unboxed words only) ---// 173 //--- Public interface ---// 174 //------------------------------------------------------------------// 175 176 typedef struct _WordBag WordBag; /* opaque */ 177 178 /* Allocate and initialise a WordBag */ 179 WordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar* cc, SizeT ), 180 const HChar* cc, 181 void (*dealloc)(void*) ); 182 183 /* Free up the Bag. */ 184 void VG_(deleteBag) ( WordBag* ); 185 186 /* Add a word. */ 187 void VG_(addToBag)( WordBag*, UWord ); 188 189 /* Find out how many times the given word exists in the bag. */ 190 UWord VG_(elemBag) ( WordBag*, UWord ); 191 192 /* Delete a word from the bag. */ 193 Bool VG_(delFromBag)( WordBag*, UWord ); 194 195 /* Is the bag empty? */ 196 Bool VG_(isEmptyBag)( WordBag* ); 197 198 /* Does the bag have exactly one element? */ 199 Bool VG_(isSingletonTotalBag)( WordBag* ); 200 201 /* Return an arbitrary element from the bag. */ 202 UWord VG_(anyElementOfBag)( WordBag* ); 203 204 /* How many different / total elements are in the bag? */ 205 UWord VG_(sizeUniqueBag)( WordBag* ); /* fast */ 206 UWord VG_(sizeTotalBag)( WordBag* ); /* warning: slow */ 207 208 /* Iterating over the elements of a bag. */ 209 void VG_(initIterBag)( WordBag* ); 210 Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount ); 211 void VG_(doneIterBag)( WordBag* ); 212 213 //------------------------------------------------------------------// 214 //--- end WordBag (unboxed words only) ---// 215 //--- Public interface ---// 216 //------------------------------------------------------------------// 217 218 #endif /* ! __PUB_TOOL_WORDFM_H */ 219 220 /*--------------------------------------------------------------------*/ 221 /*--- end pub_tool_wordfm.h ---*/ 222 /*--------------------------------------------------------------------*/ 223
