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 | // |
| 108 | // If the operation was successful (that is, the given key is not |
| 109 | // present), True is returned. If the given key is in fact present, |
| 110 | // False is returned, and *kMinP and *kMaxP are undefined. |
| 111 | Bool VG_(findBoundsFM)( WordFM* fm, |
| 112 | /*OUT*/UWord* kMinP, /*OUT*/UWord* kMaxP, |
| 113 | UWord minKey, UWord maxKey, UWord key ); |
| 114 | |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 115 | // How many elements are there in fm? |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 116 | UWord VG_(sizeFM) ( WordFM* fm ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 117 | |
| 118 | // set up FM for iteration |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 119 | void VG_(initIterFM) ( WordFM* fm ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 120 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 121 | // set up FM for iteration so that the first key subsequently produced |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 122 | // by VG_(nextIterFM) is the smallest key in the map >= start_at. |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 123 | // Naturally ">=" is defined by the comparison function supplied to |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 124 | // VG_(newFM), as documented above. |
| 125 | void VG_(initIterAtFM) ( WordFM* fm, UWord start_at ); |
sewardj | ae5137e | 2008-01-17 23:19:54 +0000 | [diff] [blame] | 126 | |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 127 | // get next key/val pair. Will assert if fm has been modified |
sewardj | ae5137e | 2008-01-17 23:19:54 +0000 | [diff] [blame] | 128 | // or looked up in since initIterFM/initIterWithStartFM was called. |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 129 | Bool VG_(nextIterFM) ( WordFM* fm, |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 130 | /*OUT*/UWord* pKey, /*OUT*/UWord* pVal ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 131 | |
| 132 | // clear the I'm iterating flag |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 133 | void VG_(doneIterFM) ( WordFM* fm ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 134 | |
| 135 | // Deep copy a FM. If dopyK is NULL, keys are copied verbatim. |
| 136 | // If non-null, dopyK is applied to each key to generate the |
| 137 | // version in the new copy. In that case, if the argument to dopyK |
| 138 | // is non-NULL but the result is NULL, it is assumed that dopyK |
| 139 | // could not allocate memory, in which case the copy is abandoned |
| 140 | // and NULL is returned. Ditto with dopyV for values. |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 141 | WordFM* VG_(dopyFM) ( WordFM* fm, |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 142 | UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 143 | |
| 144 | //------------------------------------------------------------------// |
| 145 | //--- end WordFM ---// |
| 146 | //--- Public interface ---// |
| 147 | //------------------------------------------------------------------// |
| 148 | |
| 149 | //------------------------------------------------------------------// |
| 150 | //--- WordBag (unboxed words only) ---// |
| 151 | //--- Public interface ---// |
| 152 | //------------------------------------------------------------------// |
| 153 | |
| 154 | typedef struct _WordBag WordBag; /* opaque */ |
| 155 | |
| 156 | /* Allocate and initialise a WordBag */ |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame^] | 157 | WordBag* VG_(newBag) ( void* (*alloc_nofail)( HChar* cc, SizeT ), |
| 158 | HChar* cc, |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 159 | void (*dealloc)(void*) ); |
| 160 | |
| 161 | /* Free up the Bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 162 | void VG_(deleteBag) ( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 163 | |
| 164 | /* Add a word. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 165 | void VG_(addToBag)( WordBag*, UWord ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 166 | |
| 167 | /* Find out how many times the given word exists in the bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 168 | UWord VG_(elemBag) ( WordBag*, UWord ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 169 | |
| 170 | /* Delete a word from the bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 171 | Bool VG_(delFromBag)( WordBag*, UWord ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 172 | |
| 173 | /* Is the bag empty? */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 174 | Bool VG_(isEmptyBag)( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 175 | |
| 176 | /* Does the bag have exactly one element? */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 177 | Bool VG_(isSingletonTotalBag)( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 178 | |
| 179 | /* Return an arbitrary element from the bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 180 | UWord VG_(anyElementOfBag)( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 181 | |
| 182 | /* How many different / total elements are in the bag? */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 183 | UWord VG_(sizeUniqueBag)( WordBag* ); /* fast */ |
| 184 | UWord VG_(sizeTotalBag)( WordBag* ); /* warning: slow */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 185 | |
| 186 | /* Iterating over the elements of a bag. */ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 187 | void VG_(initIterBag)( WordBag* ); |
| 188 | Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount ); |
| 189 | void VG_(doneIterBag)( WordBag* ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 190 | |
| 191 | //------------------------------------------------------------------// |
| 192 | //--- end WordBag (unboxed words only) ---// |
| 193 | //--- Public interface ---// |
| 194 | //------------------------------------------------------------------// |
| 195 | |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 196 | #endif /* ! __PUB_TOOL_WORDFM_H */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 197 | |
| 198 | /*--------------------------------------------------------------------*/ |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 199 | /*--- end pub_tool_wordfm.h ---*/ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 200 | /*--------------------------------------------------------------------*/ |