Jeff Brown | ed07e00 | 2011-02-03 17:46:23 -0800 | [diff] [blame] | 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 | |
Ben Cheng | 663860b | 2013-01-31 15:38:14 -0800 | [diff] [blame^] | 12 | Copyright (C) 2007-2012 Julian Seward |
Jeff Brown | ed07e00 | 2011-02-03 17:46:23 -0800 | [diff] [blame] | 13 | jseward@acm.org |
| 14 | |
| 15 | This code is based on previous work by Nicholas Nethercote |
| 16 | (coregrind/m_oset.c) which is |
| 17 | |
Ben Cheng | 663860b | 2013-01-31 15:38:14 -0800 | [diff] [blame^] | 18 | Copyright (C) 2005-2012 Nicholas Nethercote |
Jeff Brown | ed07e00 | 2011-02-03 17:46:23 -0800 | [diff] [blame] | 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 | /*--------------------------------------------------------------------*/ |