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-2013 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-2013 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 #include "pub_tool_basics.h"    // Word
56 
57 //------------------------------------------------------------------//
58 //---                           WordFM                           ---//
59 //---                      Public interface                      ---//
60 //------------------------------------------------------------------//
61 
62 /* As of r7409 (15 Feb 08), all these word-based abstractions (WordFM,
63    WordSet, WordBag) now operate on unsigned words (UWord), whereas
64    they previously operated on signed words (Word).  This became a
65    problem, when using unboxed comparisons (when kCmp == NULL), with
66    the introduction of VG_(initIterAtFM), which allows iteration over
67    parts of mappings.  Iterating over a mapping in increasing order of
68    signed Word keys is not what callers expect when iterating through
69    maps whose keys represent addresses (Addr) since Addr is unsigned,
70    and causes logical problems and assertion failures. */
71 
72 typedef  struct _WordFM  WordFM; /* opaque */
73 
74 /* Allocate and initialise a WordFM.  If kCmp is non-NULL, elements in
75    the set are ordered according to the ordering specified by kCmp,
76    which becomes obvious if you use VG_(initIterFM),
77    VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over
78    sections of the map, or the whole thing.  If kCmp is NULL then the
79    ordering used is unsigned word ordering (UWord) on the key
80    values.
81    The function never returns NULL. */
82 WordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
83                      const HChar* cc,
84                      void  (*dealloc)(void*),
85                      Word  (*kCmp)(UWord,UWord) );
86 
87 /* Free up the FM.  If kFin is non-NULL, it is applied to keys
88    before the FM is deleted; ditto with vFin for vals. */
89 void VG_(deleteFM) ( WordFM*, void(*kFin)(UWord), void(*vFin)(UWord) );
90 
91 /* Add (k,v) to fm.  If a binding for k already exists, it is updated
92    to map to this new v.  In that case we should really return the
93    previous v so that caller can finalise it.  Oh well.  Returns
94    True if a binding for k already exists. */
95 Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v );
96 
97 // Delete key from fm, returning associated key and val if found
98 Bool VG_(delFromFM) ( WordFM* fm,
99                       /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key );
100 
101 // Look up in fm, assigning found key & val at spec'd addresses
102 Bool VG_(lookupFM) ( const WordFM* fm,
103                      /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key );
104 
105 // Find the closest key values bracketing the given key, assuming the
106 // given key is not present in the map.  minKey and maxKey are the
107 // minimum and maximum possible key values.  The resulting bracket
108 // values are returned in *kMinP and *kMaxP.  It follows that if fm is
109 // empty then the returned values are simply minKey and maxKey.
110 //
111 // For convenience the associated value fields are also returned
112 // through *vMinP and *vMaxP.  To make that possible in the general
113 // case, the caller must supply via minVal and maxVal, the value
114 // fields associated with minKey and maxKey.
115 //
116 // If the operation was successful (that is, the given key is not
117 // present), True is returned.  If the given key is in fact present,
118 // False is returned, and *kMinP, *vMinP, *kMaxP and *vMaxP are
119 // undefined.  Any of kMinP, vMinP, kMaxP and vMaxP may be safely
120 // supplied as NULL.
121 Bool VG_(findBoundsFM)( const WordFM* fm,
122                         /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP,
123                         /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP,
124                         UWord minKey, UWord minVal,
125                         UWord maxKey, UWord maxVal,
126                         UWord key );
127 
128 // How many elements are there in fm?  NOTE: dangerous in the
129 // sense that this is not an O(1) operation but rather O(N),
130 // since it involves walking the whole tree.
131 UWord VG_(sizeFM) ( const WordFM* fm );
132 
133 // set up FM for iteration
134 void VG_(initIterFM) ( WordFM* fm );
135 
136 // set up FM for iteration so that the first key subsequently produced
137 // by VG_(nextIterFM) is the smallest key in the map >= start_at.
138 // Naturally ">=" is defined by the comparison function supplied to
139 // VG_(newFM), as documented above.
140 void VG_(initIterAtFM) ( WordFM* fm, UWord start_at );
141 
142 // get next key/val pair.  Will assert if fm has been modified
143 // or looked up in since initIterFM/initIterWithStartFM was called.
144 Bool VG_(nextIterFM) ( WordFM* fm,
145                        /*OUT*/UWord* pKey, /*OUT*/UWord* pVal );
146 
147 // Finish an FM iteration
148 void VG_(doneIterFM) ( WordFM* fm );
149 
150 // Deep copy a FM.  If dopyK is NULL, keys are copied verbatim.
151 // If non-null, dopyK is applied to each key to generate the
152 // version in the new copy.  dopyK may be called with a NULL argument
153 // in which case it should return NULL. For all other argument values
154 // dopyK must not return NULL. Ditto with dopyV for values.
155 // VG_(dopyFM) never returns NULL.
156 WordFM* VG_(dopyFM) ( WordFM* fm,
157                       UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) );
158 
159 //------------------------------------------------------------------//
160 //---                         end WordFM                         ---//
161 //---                      Public interface                      ---//
162 //------------------------------------------------------------------//
163 
164 //------------------------------------------------------------------//
165 //---                WordBag (unboxed words only)                ---//
166 //---                      Public interface                      ---//
167 //------------------------------------------------------------------//
168 
169 typedef  struct _WordBag  WordBag; /* opaque */
170 
171 /* Allocate and initialise a WordBag. Never returns NULL. */
172 WordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
173                        const HChar* cc,
174                        void  (*dealloc)(void*) );
175 
176 /* Free up the Bag. */
177 void VG_(deleteBag) ( WordBag* );
178 
179 /* Add a word. */
180 void VG_(addToBag)( WordBag*, UWord );
181 
182 /* Find out how many times the given word exists in the bag. */
183 UWord VG_(elemBag) ( const WordBag*, UWord );
184 
185 /* Delete a word from the bag. */
186 Bool VG_(delFromBag)( WordBag*, UWord );
187 
188 /* Is the bag empty? */
189 Bool VG_(isEmptyBag)( const WordBag* );
190 
191 /* Does the bag have exactly one element? */
192 Bool VG_(isSingletonTotalBag)( const WordBag* );
193 
194 /* Return an arbitrary element from the bag. */
195 UWord VG_(anyElementOfBag)( const WordBag* );
196 
197 /* How many different / total elements are in the bag? */
198 UWord VG_(sizeUniqueBag)( const WordBag* ); /* fast */
199 UWord VG_(sizeTotalBag)( const WordBag* );  /* warning: slow */
200 
201 /* Iterating over the elements of a bag. */
202 void VG_(initIterBag)( WordBag* );
203 Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount );
204 void VG_(doneIterBag)( WordBag* );
205 
206 //------------------------------------------------------------------//
207 //---             end WordBag (unboxed words only)               ---//
208 //---                      Public interface                      ---//
209 //------------------------------------------------------------------//
210 
211 #endif /* ! __PUB_TOOL_WORDFM_H */
212 
213 /*--------------------------------------------------------------------*/
214 /*--- end                                        pub_tool_wordfm.h ---*/
215 /*--------------------------------------------------------------------*/
216