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. ---*/ |
| 5 | /*--- hg_wordfm.h ---*/ |
| 6 | /*--------------------------------------------------------------------*/ |
| 7 | |
| 8 | /* |
| 9 | This file is part of Helgrind, a Valgrind tool for detecting errors |
| 10 | in threaded programs. |
| 11 | |
| 12 | Copyright (C) 2007-2007 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-2007 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 __HG_WORDFM_H |
| 53 | #define __HG_WORDFM_H |
| 54 | |
| 55 | //------------------------------------------------------------------// |
| 56 | //--- WordFM ---// |
| 57 | //--- Public interface ---// |
| 58 | //------------------------------------------------------------------// |
| 59 | |
| 60 | typedef struct _WordFM WordFM; /* opaque */ |
| 61 | |
| 62 | /* Allocate and initialise a WordFM */ |
| 63 | WordFM* HG_(newFM) ( void* (*alloc_nofail)( SizeT ), |
| 64 | void (*dealloc)(void*), |
| 65 | Word (*kCmp)(Word,Word) ); |
| 66 | |
| 67 | /* Free up the FM. If kFin is non-NULL, it is applied to keys |
| 68 | before the FM is deleted; ditto with vFin for vals. */ |
| 69 | void HG_(deleteFM) ( WordFM*, void(*kFin)(Word), void(*vFin)(Word) ); |
| 70 | |
| 71 | /* Add (k,v) to fm. If a binding for k already exists, it is updated |
| 72 | to map to this new v. In that case we should really return the |
| 73 | previous v so that caller can finalise it. Oh well. */ |
| 74 | void HG_(addToFM) ( WordFM* fm, Word k, Word v ); |
| 75 | |
| 76 | // Delete key from fm, returning associated key and val if found |
| 77 | Bool HG_(delFromFM) ( WordFM* fm, |
| 78 | /*OUT*/Word* oldK, /*OUT*/Word* oldV, Word key ); |
| 79 | |
| 80 | // Look up in fm, assigning found key & val at spec'd addresses |
| 81 | Bool HG_(lookupFM) ( WordFM* fm, |
| 82 | /*OUT*/Word* keyP, /*OUT*/Word* valP, Word key ); |
| 83 | |
| 84 | // How many elements are there in fm? |
| 85 | Word HG_(sizeFM) ( WordFM* fm ); |
| 86 | |
| 87 | // set up FM for iteration |
| 88 | void HG_(initIterFM) ( WordFM* fm ); |
| 89 | |
| 90 | // get next key/val pair. Will assert if fm has been modified |
| 91 | // or looked up in since initIterFM was called. |
| 92 | Bool HG_(nextIterFM) ( WordFM* fm, |
| 93 | /*OUT*/Word* pKey, /*OUT*/Word* pVal ); |
| 94 | |
| 95 | // clear the I'm iterating flag |
| 96 | void HG_(doneIterFM) ( WordFM* fm ); |
| 97 | |
| 98 | // Deep copy a FM. If dopyK is NULL, keys are copied verbatim. |
| 99 | // If non-null, dopyK is applied to each key to generate the |
| 100 | // version in the new copy. In that case, if the argument to dopyK |
| 101 | // is non-NULL but the result is NULL, it is assumed that dopyK |
| 102 | // could not allocate memory, in which case the copy is abandoned |
| 103 | // and NULL is returned. Ditto with dopyV for values. |
| 104 | WordFM* HG_(dopyFM) ( WordFM* fm, |
| 105 | Word(*dopyK)(Word), Word(*dopyV)(Word) ); |
| 106 | |
| 107 | //------------------------------------------------------------------// |
| 108 | //--- end WordFM ---// |
| 109 | //--- Public interface ---// |
| 110 | //------------------------------------------------------------------// |
| 111 | |
| 112 | //------------------------------------------------------------------// |
| 113 | //--- WordBag (unboxed words only) ---// |
| 114 | //--- Public interface ---// |
| 115 | //------------------------------------------------------------------// |
| 116 | |
| 117 | typedef struct _WordBag WordBag; /* opaque */ |
| 118 | |
| 119 | /* Allocate and initialise a WordBag */ |
| 120 | WordBag* HG_(newBag) ( void* (*alloc_nofail)( SizeT ), |
| 121 | void (*dealloc)(void*) ); |
| 122 | |
| 123 | /* Free up the Bag. */ |
| 124 | void HG_(deleteBag) ( WordBag* ); |
| 125 | |
| 126 | /* Add a word. */ |
| 127 | void HG_(addToBag)( WordBag*, Word ); |
| 128 | |
| 129 | /* Find out how many times the given word exists in the bag. */ |
| 130 | Word HG_(elemBag) ( WordBag*, Word ); |
| 131 | |
| 132 | /* Delete a word from the bag. */ |
| 133 | Bool HG_(delFromBag)( WordBag*, Word ); |
| 134 | |
| 135 | /* Is the bag empty? */ |
| 136 | Bool HG_(isEmptyBag)( WordBag* ); |
| 137 | |
| 138 | /* Does the bag have exactly one element? */ |
| 139 | Bool HG_(isSingletonTotalBag)( WordBag* ); |
| 140 | |
| 141 | /* Return an arbitrary element from the bag. */ |
| 142 | Word HG_(anyElementOfBag)( WordBag* ); |
| 143 | |
| 144 | /* How many different / total elements are in the bag? */ |
| 145 | Word HG_(sizeUniqueBag)( WordBag* ); /* fast */ |
| 146 | Word HG_(sizeTotalBag)( WordBag* ); /* warning: slow */ |
| 147 | |
| 148 | /* Iterating over the elements of a bag. */ |
| 149 | void HG_(initIterBag)( WordBag* ); |
| 150 | Bool HG_(nextIterBag)( WordBag*, /*OUT*/Word* pVal, /*OUT*/Word* pCount ); |
| 151 | void HG_(doneIterBag)( WordBag* ); |
| 152 | |
| 153 | //------------------------------------------------------------------// |
| 154 | //--- end WordBag (unboxed words only) ---// |
| 155 | //--- Public interface ---// |
| 156 | //------------------------------------------------------------------// |
| 157 | |
| 158 | #endif /* ! __HG_WORDFM_H */ |
| 159 | |
| 160 | /*--------------------------------------------------------------------*/ |
| 161 | /*--- end hg_wordfm.h ---*/ |
| 162 | /*--------------------------------------------------------------------*/ |