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
72typedef  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. */
81WordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
82                     const HChar* cc,
83                     void  (*dealloc)(void*),
84                     Word  (*kCmp)(UWord,UWord) );
85
86/* Free up the FM.  If kFin is non-NULL, it is applied to keys
87   before the FM is deleted; ditto with vFin for vals. */
88void VG_(deleteFM) ( WordFM*, void(*kFin)(UWord), void(*vFin)(UWord) );
89
90/* Add (k,v) to fm.  If a binding for k already exists, it is updated
91   to map to this new v.  In that case we should really return the
92   previous v so that caller can finalise it.  Oh well.  Returns
93   True if a binding for k already exists. */
94Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v );
95
96// Delete key from fm, returning associated key and val if found
97Bool VG_(delFromFM) ( WordFM* fm,
98                      /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key );
99
100// Look up in fm, assigning found key & val at spec'd addresses
101Bool VG_(lookupFM) ( WordFM* fm,
102                     /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key );
103
104// Find the closest key values bracketing the given key, assuming the
105// given key is not present in the map.  minKey and maxKey are the
106// minimum and maximum possible key values.  The resulting bracket
107// values are returned in *kMinP and *kMaxP.  It follows that if fm is
108// empty then the returned values are simply minKey and maxKey.
109//
110// For convenience the associated value fields are also returned
111// through *vMinP and *vMaxP.  To make that possible in the general
112// case, the caller must supply via minVal and maxVal, the value
113// fields associated with minKey and maxKey.
114//
115// If the operation was successful (that is, the given key is not
116// present), True is returned.  If the given key is in fact present,
117// False is returned, and *kMinP, *vMinP, *kMaxP and *vMaxP are
118// undefined.  Any of kMinP, vMinP, kMaxP and vMaxP may be safely
119// supplied as NULL.
120Bool VG_(findBoundsFM)( WordFM* fm,
121                        /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP,
122                        /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP,
123                        UWord minKey, UWord minVal,
124                        UWord maxKey, UWord maxVal,
125                        UWord key );
126
127// How many elements are there in fm?  NOTE: dangerous in the
128// sense that this is not an O(1) operation but rather O(N),
129// since it involves walking the whole tree.
130UWord VG_(sizeFM) ( WordFM* fm );
131
132// Is fm empty?  This at least is an O(1) operation.
133// Code is present in m_wordfm.c but commented out due to no
134// current usage.  Un-comment (and TEST IT) if required.
135//Bool VG_(isEmptyFM)( WordFM* fm );
136
137// set up FM for iteration
138void VG_(initIterFM) ( WordFM* fm );
139
140// set up FM for iteration so that the first key subsequently produced
141// by VG_(nextIterFM) is the smallest key in the map >= start_at.
142// Naturally ">=" is defined by the comparison function supplied to
143// VG_(newFM), as documented above.
144void VG_(initIterAtFM) ( WordFM* fm, UWord start_at );
145
146// get next key/val pair.  Will assert if fm has been modified
147// or looked up in since initIterFM/initIterWithStartFM was called.
148Bool VG_(nextIterFM) ( WordFM* fm,
149                       /*OUT*/UWord* pKey, /*OUT*/UWord* pVal );
150
151// clear the I'm iterating flag
152void VG_(doneIterFM) ( WordFM* fm );
153
154// Deep copy a FM.  If dopyK is NULL, keys are copied verbatim.
155// If non-null, dopyK is applied to each key to generate the
156// version in the new copy.  In that case, if the argument to dopyK
157// is non-NULL but the result is NULL, it is assumed that dopyK
158// could not allocate memory, in which case the copy is abandoned
159// and NULL is returned.  Ditto with dopyV for values.
160WordFM* VG_(dopyFM) ( WordFM* fm,
161                      UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) );
162
163// admin: what's the 'common' allocation size (for tree nodes?)
164SizeT VG_(getNodeSizeFM)( void );
165
166//------------------------------------------------------------------//
167//---                         end WordFM                         ---//
168//---                      Public interface                      ---//
169//------------------------------------------------------------------//
170
171//------------------------------------------------------------------//
172//---                WordBag (unboxed words only)                ---//
173//---                      Public interface                      ---//
174//------------------------------------------------------------------//
175
176typedef  struct _WordBag  WordBag; /* opaque */
177
178/* Allocate and initialise a WordBag */
179WordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
180                       const HChar* cc,
181                       void  (*dealloc)(void*) );
182
183/* Free up the Bag. */
184void VG_(deleteBag) ( WordBag* );
185
186/* Add a word. */
187void VG_(addToBag)( WordBag*, UWord );
188
189/* Find out how many times the given word exists in the bag. */
190UWord VG_(elemBag) ( WordBag*, UWord );
191
192/* Delete a word from the bag. */
193Bool VG_(delFromBag)( WordBag*, UWord );
194
195/* Is the bag empty? */
196Bool VG_(isEmptyBag)( WordBag* );
197
198/* Does the bag have exactly one element? */
199Bool VG_(isSingletonTotalBag)( WordBag* );
200
201/* Return an arbitrary element from the bag. */
202UWord VG_(anyElementOfBag)( WordBag* );
203
204/* How many different / total elements are in the bag? */
205UWord VG_(sizeUniqueBag)( WordBag* ); /* fast */
206UWord VG_(sizeTotalBag)( WordBag* );  /* warning: slow */
207
208/* Iterating over the elements of a bag. */
209void VG_(initIterBag)( WordBag* );
210Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount );
211void VG_(doneIterBag)( WordBag* );
212
213//------------------------------------------------------------------//
214//---             end WordBag (unboxed words only)               ---//
215//---                      Public interface                      ---//
216//------------------------------------------------------------------//
217
218#endif /* ! __PUB_TOOL_WORDFM_H */
219
220/*--------------------------------------------------------------------*/
221/*--- end                                        pub_tool_wordfm.h ---*/
222/*--------------------------------------------------------------------*/
223