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