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