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