1
2/*--------------------------------------------------------------------*/
3/*--- OSet: a fast data structure with no dups.    pub_tool_oset.h ---*/
4/*--------------------------------------------------------------------*/
5
6/*
7   This file is part of Valgrind, a dynamic binary instrumentation
8   framework.
9
10   Copyright (C) 2005-2015 Nicholas Nethercote
11      njn@valgrind.org
12
13   This program is free software; you can redistribute it and/or
14   modify it under the terms of the GNU General Public License as
15   published by the Free Software Foundation; either version 2 of the
16   License, or (at your option) any later version.
17
18   This program is distributed in the hope that it will be useful, but
19   WITHOUT ANY WARRANTY; without even the implied warranty of
20   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21   General Public License for more details.
22
23   You should have received a copy of the GNU General Public License
24   along with this program; if not, write to the Free Software
25   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
26   02111-1307, USA.
27
28   The GNU General Public License is contained in the file COPYING.
29*/
30
31#ifndef __PUB_TOOL_OSET_H
32#define __PUB_TOOL_OSET_H
33
34#include "pub_tool_basics.h"   // Word
35
36// This module implements an ordered set, a data structure with fast
37// (eg. amortised log(n) or better) insertion, lookup and deletion of
38// elements.  It does not allow duplicates, and will assert if you insert a
39// duplicate to an OSet.
40//
41// It has two interfaces.
42//
43// - The "OSetWord_" interface provides an easier-to-use interface for the
44//   case where you just want to store UWord-sized values.  The user
45//   provides the allocation and deallocation functions, and possibly a
46//   comparison function.
47//
48// - The "OSetGen_" interface provides a totally generic interface, which
49//   allows any kind of structure to be put into the set.  The user provides
50//   the allocation and deallocation functions.  Also, each element has a
51//   key, which the lookup is done with.  The key may be the whole element
52//   (eg. in an OSet of integers, each integer serves both as an element and
53//   a key), or it may be only part of it (eg. if the key is a single field
54//   in a struct).  The user can provide a function that compares an element
55//   with a key;  this is very flexible, and with the right comparison
56//   function even a (non-overlapping) interval list can be created.  But
57//   the cost of calling a function for every comparison can be high during
58//   lookup.  If no comparison function is provided, we assume that keys are
59//   unsigned words, and that the key is the first word in each
60//   element.  This fast comparison is suitable for an OSet containing
61//   structs where the first element is an Addr, for example.
62//   Do not assume fast comparison works properly with signed words.
63//   A.o. iterating over the values will not return them in the correct
64//   order.
65//
66// Each OSet interface also has an iterator, which makes it simple to
67// traverse all the nodes in order.  Note that the iterator maintains state
68// and so is non-reentrant.
69//
70// Note that once you insert an element into an OSet, if you modify any part
71// of it looked at by your cmp() function, this may cause incorrect
72// behaviour as the sorted order maintained will be wrong.
73
74/*--------------------------------------------------------------------*/
75/*--- Types                                                        ---*/
76/*--------------------------------------------------------------------*/
77
78typedef struct _OSet     OSet;
79
80// - Cmp:   returns -1, 0 or 1 if key is <, == or > elem.
81// - Alloc: allocates a chunk of memory.
82// - Free:  frees a chunk of memory allocated with Alloc.
83
84typedef Word  (*OSetCmp_t)         ( const void* key, const void* elem );
85typedef void* (*OSetAlloc_t)       ( const HChar* cc, SizeT szB );
86typedef void  (*OSetFree_t)        ( void* p );
87
88/*--------------------------------------------------------------------*/
89/*--- Creating and destroying OSets (UWord)                        ---*/
90/*--------------------------------------------------------------------*/
91
92// * Create: allocates and initialises the OSet.  Never returns NULL.
93//   Parameters:
94//   - alloc_fn  The allocation function used internally for allocating the
95//               OSet and all its nodes. It must not return NULL (that is,
96//               if it returns it must have succeeded.)
97//   - cc        Cost centre string used by 'alloc'.
98//   - free_fn   The deallocation function used internally for freeing nodes
99//               called by VG_(OSetWord_Destroy)().
100//
101// * Destroy: frees all nodes in the table, plus the memory used by
102//   the table itself.  The passed-in function is called on each node first
103//   to allow the destruction of any attached resources;  if NULL it is not
104//   called.
105
106extern OSet* VG_(OSetWord_Create) ( OSetAlloc_t alloc_fn, const HChar* cc,
107                                    OSetFree_t free_fn );
108extern void  VG_(OSetWord_Destroy) ( OSet* os );
109
110/*--------------------------------------------------------------------*/
111/*--- Operations on OSets (UWord)                                  ---*/
112/*--------------------------------------------------------------------*/
113
114// In everything that follows, the parameter 'key' is always the *address*
115// of the key, and 'elem' is *address* of the elem, as are the return values
116// of the functions that return elems.
117//
118// * Size: The number of elements in the set.
119//
120// * Contains: Determines if the value is in the set.
121//
122// * Insert: Inserts a new element into the set.  Duplicates are forbidden,
123//   and will cause assertion failures.
124//
125// * Remove: Removes the value from the set, if present.  Returns a Bool
126//   indicating if the value was removed.
127//
128// * ResetIter: Each OSet has an iterator.  This resets it to point to the
129//   first element in the OSet.
130//
131// * Next: Copies the next value according to the OSet's iterator into &val,
132//   advances the iterator by one, and returns True;  the elements are
133//   visited in increasing order of unsigned words (UWord).  Or, returns
134//   False if the iterator has reached the set's end.
135//
136//   You can thus iterate in order through a set like this:
137//
138//     Word val;
139//     VG_(OSetWord_ResetIter)(oset);
140//     while ( VG_(OSetWord_Next)(oset, &val) ) {
141//        ... do stuff with 'val' ...
142//     }
143//
144//   Note that iterators are cleared any time an element is inserted or
145//   removed from the OSet, to avoid possible mayhem caused by the iterator
146//   getting out of sync with the OSet's contents.  "Cleared" means that
147//   they will return False if VG_(OSetWord_Next)() is called without an
148//   intervening call to VG_(OSetWord_ResetIter)().
149
150extern Word  VG_(OSetWord_Size)         ( const OSet* os );
151extern void  VG_(OSetWord_Insert)       ( OSet* os, UWord val );
152extern Bool  VG_(OSetWord_Contains)     ( const OSet* os, UWord val );
153extern Bool  VG_(OSetWord_Remove)       ( OSet* os, UWord val );
154extern void  VG_(OSetWord_ResetIter)    ( OSet* os );
155extern Bool  VG_(OSetWord_Next)         ( OSet* os, /*OUT*/UWord* val );
156
157
158/*--------------------------------------------------------------------*/
159/*--- Creating and destroying OSets and OSet members (Gen)         ---*/
160/*--------------------------------------------------------------------*/
161
162// * Create: allocates and initialises the OSet. Never returns NULL.
163//   Parameters:
164//   - keyOff    The offset of the key within the element.
165//   - cmp       The comparison function between keys and elements, or NULL
166//               if the OSet should use fast comparisons.
167//   - alloc_fn  The allocation function used for allocating the OSet itself;
168//               It must not return NULL (that is, if it returns it must
169//               have succeeded.)
170//               If a pool allocator is used, it's called to allocate pool of
171//               nodes.
172//               If no pool allocator is used, it's called for each
173//               invocation of VG_(OSetGen_AllocNode)().
174//   - cc        Cost centre string used by 'alloc'.
175//   - free_fn   If no pool allocator is used, this is the deallocation
176//               function used by VG_(OSetGen_FreeNode)() and
177//               VG_(OSetGen_Destroy)().
178//               If a pool allocator is used, the memory used by the nodes is
179//               deallocated when the pool is deleted.
180//   (for more details about pool allocators, see pub_tool_poolalloc.h).
181//
182//
183//   If cmp is NULL, keyOff must be zero.  This is checked.
184//
185// * Destroy: frees all nodes in the table, plus the memory used by
186//   the table itself.  The passed-in function is called on each node first
187//   to allow the destruction of any attached resources;  if NULL it is not
188//   called.
189//
190// * AllocNode: Allocate and zero memory for a node to go into the OSet.
191//   If a pool allocator is used, it uses the pool allocator to allocate a node.
192//   Otherwise, uses the alloc function given to VG_(OSetGen_Create)() to
193//   allocate a node which is big enough for both an element and the OSet
194//   metadata.
195//   Not all elements in one OSet have to be the same size.
196//   However, if a pool allocator is used, elements will all have a size equal
197//   to the max user data size given at creation + the node meta data size.
198//
199//   Note that the element allocated will be at most word-aligned, which may
200//   be less aligned than the element type would normally be.
201//
202// * FreeNode: Deallocate a node allocated with OSetGen_AllocNode().  Using
203//   a deallocation function (such as VG_(free)()) directly will likely
204//   lead to assertions in Valgrind's allocator.
205
206extern OSet* VG_(OSetGen_Create)    ( PtrdiffT keyOff, OSetCmp_t cmp,
207                                      OSetAlloc_t alloc_fn, const HChar* cc,
208                                      OSetFree_t free_fn);
209
210
211extern OSet* VG_(OSetGen_Create_With_Pool)    ( PtrdiffT keyOff, OSetCmp_t cmp,
212                                                OSetAlloc_t alloc_fn,
213                                                const HChar* cc,
214                                                OSetFree_t free_fn,
215                                                SizeT poolSize,
216                                                SizeT maxEltSize);
217// Same as VG_(OSetGen_Create) but created OSet will use a pool allocator to
218// allocate the nodes.
219// The node size is the sum of a fixed small meta data size needed for OSet
220// + the size of the user data element.
221// The maximum size for the user data element is specified by maxEltSize.
222// (if poolSize is 0, maxEltSize is not relevant for the OSet).
223// It is interesting to use a pool allocator when an OSet has many elements,
224// and these elements have a small fixed size, or have a variable size, but
225// always <= than a (small) maximum value.
226// In such a case, allocating the nodes in pools reduces significantly
227// the memory overhead needed by each node.
228// When a node is freed (i.e. OSetGen_Freenode is called), the node is
229// put back in the pool allocator free list (for sub-sequent re-use by
230// OSetGen_AllocNode). Note that the pool memory is only released when
231// the pool is destroyed : calls to VG_(OSetGen_Free) do not cause
232// any calls to OSetFree_t _free function.
233// If there are several OSet managing similar such elements, it might be
234// interesting to use a shared pool for these OSet.
235// To have multiple OSets sharing a pool allocator, create the first OSet
236// with VG_(OSetGen_Create_With_Pool). Create subsequent OSet with
237// VG_(OSetGen_EmptyClone).
238
239extern void  VG_(OSetGen_Destroy)   ( OSet* os );
240extern void* VG_(OSetGen_AllocNode) ( const OSet* os, SizeT elemSize );
241extern void  VG_(OSetGen_FreeNode)  ( const OSet* os, void* elem );
242
243extern OSet* VG_(OSetGen_EmptyClone) (const OSet* os);
244// Creates a new empty OSet.
245// The new OSet will have the same characteristics as os.
246// If os uses a pool allocator, this pool allocator will be shared with
247// the new OSet. A shared pool allocator is only deleted (and its memory is
248// released) when the last OSet using the shared pool is destroyed.
249
250/*-------------------------------------------------------------------*/
251/*--- Operations on OSets (Gen)                                    ---*/
252/*--------------------------------------------------------------------*/
253
254// In everything that follows, the parameter 'key' is always the *address*
255// of the key, and 'elem' is *address* of the elem, as are the return values
256// of the functions that return elems.
257//
258// * Size: The number of elements in the set.
259//
260// * Insert: Inserts a new element into the set.  Note that 'elem' must
261//   have been allocated using VG_(OSetGen_AllocNode)(), otherwise you will
262//   get assertion failures about "bad magic".  Duplicates are forbidden,
263//   and will also cause assertion failures.
264//
265// * Contains: Determines if any element in the OSet matches the key.
266//
267// * Lookup: Returns a pointer to the element matching the key, if there is
268//   one, otherwise returns NULL.
269//
270// * LookupWithCmp: Like Lookup, but you specify the comparison function,
271//   which overrides the OSet's normal one.
272//
273// * Remove: Removes the element matching the key, if there is one.  Returns
274//   NULL if no element matches the key.
275//
276// * ResetIter: Each OSet has an iterator.  This resets it to point to the
277//   first element in the OSet.
278//
279// * ResetIterAt: Like ResetIter, but instead of resetting the iterator to the
280//   smallest element, it resets the iterator to point to the smallest element
281//   in the set whose key is greater-than-or-equal to the given key.  (In many
282//   cases this will be the element whose key equals that of the given key.)
283//
284// * Next: Returns a pointer to the element pointed to by the OSet's
285//   iterator, and advances the iterator by one;  the elements are visited
286//   in order.  Or, returns NULL if the iterator has reached the OSet's end.
287//
288//   You can thus iterate in order through a set like this:
289//
290//     VG_(OSetGen_ResetIter)(oset);
291//     while ( (elem = VG_(OSetGen_Next)(oset)) ) {
292//        ... do stuff with 'elem' ...
293//     }
294//
295//   Note that iterators are cleared any time an element is inserted or
296//   removed from the OSet, to avoid possible mayhem caused by the iterator
297//   getting out of sync with the OSet's contents.  "Cleared" means that
298//   they will return NULL if VG_(OSetGen_Next)() is called without an
299//   intervening call to VG_(OSetGen_ResetIter)().
300
301extern UInt  VG_(OSetGen_Size)         ( const OSet* os );
302extern void  VG_(OSetGen_Insert)       ( OSet* os, void* elem );
303extern Bool  VG_(OSetGen_Contains)     ( const OSet* os, const void* key );
304extern void* VG_(OSetGen_Lookup)       ( const OSet* os, const void* key );
305extern void* VG_(OSetGen_LookupWithCmp)( OSet* os,
306                                         const void* key, OSetCmp_t cmp );
307extern void* VG_(OSetGen_Remove)       ( OSet* os, const void* key );
308extern void  VG_(OSetGen_ResetIter)    ( OSet* os );
309extern void  VG_(OSetGen_ResetIterAt)  ( OSet* os, const void* key );
310extern void* VG_(OSetGen_Next)         ( OSet* os );
311
312
313#endif   // __PUB_TOOL_OSET_H
314
315/*--------------------------------------------------------------------*/
316/*--- end                                                          ---*/
317/*--------------------------------------------------------------------*/
318