blob: ea6c5f3475803368aea29c112e6419bf67b752b4 [file] [log] [blame]
Jeff Browned07e002011-02-03 17:46:23 -08001
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 Cheng663860b2013-01-31 15:38:14 -080012 Copyright (C) 2007-2012 Julian Seward
Jeff Browned07e002011-02-03 17:46:23 -080013 jseward@acm.org
14
15 This code is based on previous work by Nicholas Nethercote
16 (coregrind/m_oset.c) which is
17
Ben Cheng663860b2013-01-31 15:38:14 -080018 Copyright (C) 2005-2012 Nicholas Nethercote
Jeff Browned07e002011-02-03 17:46:23 -080019 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
70typedef 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. */
79WordFM* 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. */
86void 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. */
92Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v );
93
94// Delete key from fm, returning associated key and val if found
95Bool 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
99Bool 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.
118Bool 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.
128UWord 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
136void 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.
142void 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.
146Bool VG_(nextIterFM) ( WordFM* fm,
147 /*OUT*/UWord* pKey, /*OUT*/UWord* pVal );
148
149// clear the I'm iterating flag
150void 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.
158WordFM* VG_(dopyFM) ( WordFM* fm,
159 UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) );
160
161// admin: what's the 'common' allocation size (for tree nodes?)
162SizeT VG_(getNodeSizeFM)( void );
163
164//------------------------------------------------------------------//
165//--- end WordFM ---//
166//--- Public interface ---//
167//------------------------------------------------------------------//
168
169//------------------------------------------------------------------//
170//--- WordBag (unboxed words only) ---//
171//--- Public interface ---//
172//------------------------------------------------------------------//
173
174typedef struct _WordBag WordBag; /* opaque */
175
176/* Allocate and initialise a WordBag */
177WordBag* VG_(newBag) ( void* (*alloc_nofail)( HChar* cc, SizeT ),
178 HChar* cc,
179 void (*dealloc)(void*) );
180
181/* Free up the Bag. */
182void VG_(deleteBag) ( WordBag* );
183
184/* Add a word. */
185void VG_(addToBag)( WordBag*, UWord );
186
187/* Find out how many times the given word exists in the bag. */
188UWord VG_(elemBag) ( WordBag*, UWord );
189
190/* Delete a word from the bag. */
191Bool VG_(delFromBag)( WordBag*, UWord );
192
193/* Is the bag empty? */
194Bool VG_(isEmptyBag)( WordBag* );
195
196/* Does the bag have exactly one element? */
197Bool VG_(isSingletonTotalBag)( WordBag* );
198
199/* Return an arbitrary element from the bag. */
200UWord VG_(anyElementOfBag)( WordBag* );
201
202/* How many different / total elements are in the bag? */
203UWord VG_(sizeUniqueBag)( WordBag* ); /* fast */
204UWord VG_(sizeTotalBag)( WordBag* ); /* warning: slow */
205
206/* Iterating over the elements of a bag. */
207void VG_(initIterBag)( WordBag* );
208Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount );
209void 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/*--------------------------------------------------------------------*/