sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 1 | |
| 2 | /*--------------------------------------------------------------------*/ |
| 3 | /*--- An AVL tree based finite map for word keys and word values. ---*/ |
| 4 | /*--- Inspired by Haskell's "FiniteMap" library. ---*/ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 5 | /*--- pub_tool_wordfm.h ---*/ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 6 | /*--------------------------------------------------------------------*/ |
| 7 | |
| 8 | /* |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 9 | This file is part of Valgrind, a dynamic binary instrumentation |
| 10 | framework. |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 11 | |
sewardj | 4d474d0 | 2008-02-11 11:34:59 +0000 | [diff] [blame] | 12 | Copyright (C) 2007-2008 Julian Seward |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [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 | |
sewardj | 4d474d0 | 2008-02-11 11:34:59 +0000 | [diff] [blame] | 18 | Copyright (C) 2005-2008 Nicholas Nethercote |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [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 | |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 52 | #ifndef __PUB_TOOL_WORDFM_H |
| 53 | #define __PUB_TOOL_WORDFM_H |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 54 | |
| 55 | //------------------------------------------------------------------// |
| 56 | //--- WordFM ---// |
| 57 | //--- Public interface ---// |
| 58 | //------------------------------------------------------------------// |
| 59 | |
sewardj | fc4b63a | 2008-02-17 11:46:58 +0000 | [diff] [blame] | 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 |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 64 | the introduction of VG_(initIterAtFM), which allows iteration over |
sewardj | fc4b63a | 2008-02-17 11:46:58 +0000 | [diff] [blame] | 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 | |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 70 | typedef struct _WordFM WordFM; /* opaque */ |
| 71 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 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 |
sewardj | fc4b63a | 2008-02-17 11:46:58 +0000 | [diff] [blame] | 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. */ |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 79 | WordFM* VG_(newFM) ( void* (*alloc_nofail)( HChar* cc, SizeT ), |
| 80 | HChar* cc, |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 81 | void (*dealloc)(void*), |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 82 | Word (*kCmp)(UWord,UWord) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 86 | void VG_(deleteFM) ( WordFM*, void(*kFin)(UWord), void(*vFin)(UWord) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 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 ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 93 | |
| 94 | // Delete key from fm, returning associated key and val if found |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 95 | Bool VG_(delFromFM) ( WordFM* fm, |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 96 | /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 97 | |
| 98 | // Look up in fm, assigning found key & val at spec'd addresses |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 99 | Bool VG_(lookupFM) ( WordFM* fm, |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 100 | /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 101 | |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 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 | // |
sewardj | 9520845 | 2008-10-18 19:55:31 +0000 | [diff] [blame] | 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 | // |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 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, |
sewardj | 9520845 | 2008-10-18 19:55:31 +0000 | [diff] [blame] | 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. |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 118 | Bool VG_(findBoundsFM)( WordFM* fm, |
sewardj | 9520845 | 2008-10-18 19:55:31 +0000 | [diff] [blame] | 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 ); |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 124 | |
sewardj | 0b5f9fc | 2008-11-13 13:17:06 +0000 | [diff] [blame^] | 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. |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 128 | UWord VG_(sizeFM) ( WordFM* fm ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 129 | |
sewardj | 0b5f9fc | 2008-11-13 13:17:06 +0000 | [diff] [blame^] | 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 | |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 135 | // set up FM for iteration |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 136 | void VG_(initIterFM) ( WordFM* fm ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 137 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 138 | // set up FM for iteration so that the first key subsequently produced |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 139 | // by VG_(nextIterFM) is the smallest key in the map >= start_at. |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 140 | // Naturally ">=" is defined by the comparison function supplied to |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 141 | // VG_(newFM), as documented above. |
| 142 | void VG_(initIterAtFM) ( WordFM* fm, UWord start_at ); |
sewardj | ae5137e | 2008-01-17 23:19:54 +0000 | [diff] [blame] | 143 | |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 144 | // get next key/val pair. Will assert if fm has been modified |
sewardj | ae5137e | 2008-01-17 23:19:54 +0000 | [diff] [blame] | 145 | // or looked up in since initIterFM/initIterWithStartFM was called. |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 146 | Bool VG_(nextIterFM) ( WordFM* fm, |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 147 | /*OUT*/UWord* pKey, /*OUT*/UWord* pVal ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 148 | |
| 149 | // clear the I'm iterating flag |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 150 | void VG_(doneIterFM) ( WordFM* fm ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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. |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 158 | WordFM* VG_(dopyFM) ( WordFM* fm, |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 159 | UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 160 | |
| 161 | //------------------------------------------------------------------// |
| 162 | //--- end WordFM ---// |
| 163 | //--- Public interface ---// |
| 164 | //------------------------------------------------------------------// |
| 165 | |
| 166 | //------------------------------------------------------------------// |
| 167 | //--- WordBag (unboxed words only) ---// |
| 168 | //--- Public interface ---// |
| 169 | //------------------------------------------------------------------// |
| 170 | |
| 171 | typedef struct _WordBag WordBag; /* opaque */ |
| 172 | |
| 173 | /* Allocate and initialise a WordBag */ |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 174 | WordBag* VG_(newBag) ( void* (*alloc_nofail)( HChar* cc, SizeT ), |
| 175 | HChar* cc, |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 176 | void (*dealloc)(void*) ); |
| 177 | |
| 178 | /* Free up the Bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 179 | void VG_(deleteBag) ( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 180 | |
| 181 | /* Add a word. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 182 | void VG_(addToBag)( WordBag*, UWord ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 183 | |
| 184 | /* Find out how many times the given word exists in the bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 185 | UWord VG_(elemBag) ( WordBag*, UWord ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 186 | |
| 187 | /* Delete a word from the bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 188 | Bool VG_(delFromBag)( WordBag*, UWord ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 189 | |
| 190 | /* Is the bag empty? */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 191 | Bool VG_(isEmptyBag)( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 192 | |
| 193 | /* Does the bag have exactly one element? */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 194 | Bool VG_(isSingletonTotalBag)( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 195 | |
| 196 | /* Return an arbitrary element from the bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 197 | UWord VG_(anyElementOfBag)( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 198 | |
| 199 | /* How many different / total elements are in the bag? */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 200 | UWord VG_(sizeUniqueBag)( WordBag* ); /* fast */ |
| 201 | UWord VG_(sizeTotalBag)( WordBag* ); /* warning: slow */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 202 | |
| 203 | /* Iterating over the elements of a bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 204 | void VG_(initIterBag)( WordBag* ); |
| 205 | Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount ); |
| 206 | void VG_(doneIterBag)( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 207 | |
| 208 | //------------------------------------------------------------------// |
| 209 | //--- end WordBag (unboxed words only) ---// |
| 210 | //--- Public interface ---// |
| 211 | //------------------------------------------------------------------// |
| 212 | |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 213 | #endif /* ! __PUB_TOOL_WORDFM_H */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 214 | |
| 215 | /*--------------------------------------------------------------------*/ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 216 | /*--- end pub_tool_wordfm.h ---*/ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 217 | /*--------------------------------------------------------------------*/ |