mirror of
https://github.com/ioacademy-jikim/debugging
synced 2025-06-08 00:16:11 +00:00
318 lines
15 KiB
C
318 lines
15 KiB
C
|
|
/*--------------------------------------------------------------------*/
|
|
/*--- OSet: a fast data structure with no dups. pub_tool_oset.h ---*/
|
|
/*--------------------------------------------------------------------*/
|
|
|
|
/*
|
|
This file is part of Valgrind, a dynamic binary instrumentation
|
|
framework.
|
|
|
|
Copyright (C) 2005-2015 Nicholas Nethercote
|
|
njn@valgrind.org
|
|
|
|
This program is free software; you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License as
|
|
published by the Free Software Foundation; either version 2 of the
|
|
License, or (at your option) any later version.
|
|
|
|
This program is distributed in the hope that it will be useful, but
|
|
WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with this program; if not, write to the Free Software
|
|
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
|
|
02111-1307, USA.
|
|
|
|
The GNU General Public License is contained in the file COPYING.
|
|
*/
|
|
|
|
#ifndef __PUB_TOOL_OSET_H
|
|
#define __PUB_TOOL_OSET_H
|
|
|
|
#include "pub_tool_basics.h" // Word
|
|
|
|
// This module implements an ordered set, a data structure with fast
|
|
// (eg. amortised log(n) or better) insertion, lookup and deletion of
|
|
// elements. It does not allow duplicates, and will assert if you insert a
|
|
// duplicate to an OSet.
|
|
//
|
|
// It has two interfaces.
|
|
//
|
|
// - The "OSetWord_" interface provides an easier-to-use interface for the
|
|
// case where you just want to store UWord-sized values. The user
|
|
// provides the allocation and deallocation functions, and possibly a
|
|
// comparison function.
|
|
//
|
|
// - The "OSetGen_" interface provides a totally generic interface, which
|
|
// allows any kind of structure to be put into the set. The user provides
|
|
// the allocation and deallocation functions. Also, each element has a
|
|
// key, which the lookup is done with. The key may be the whole element
|
|
// (eg. in an OSet of integers, each integer serves both as an element and
|
|
// a key), or it may be only part of it (eg. if the key is a single field
|
|
// in a struct). The user can provide a function that compares an element
|
|
// with a key; this is very flexible, and with the right comparison
|
|
// function even a (non-overlapping) interval list can be created. But
|
|
// the cost of calling a function for every comparison can be high during
|
|
// lookup. If no comparison function is provided, we assume that keys are
|
|
// unsigned words, and that the key is the first word in each
|
|
// element. This fast comparison is suitable for an OSet containing
|
|
// structs where the first element is an Addr, for example.
|
|
// Do not assume fast comparison works properly with signed words.
|
|
// A.o. iterating over the values will not return them in the correct
|
|
// order.
|
|
//
|
|
// Each OSet interface also has an iterator, which makes it simple to
|
|
// traverse all the nodes in order. Note that the iterator maintains state
|
|
// and so is non-reentrant.
|
|
//
|
|
// Note that once you insert an element into an OSet, if you modify any part
|
|
// of it looked at by your cmp() function, this may cause incorrect
|
|
// behaviour as the sorted order maintained will be wrong.
|
|
|
|
/*--------------------------------------------------------------------*/
|
|
/*--- Types ---*/
|
|
/*--------------------------------------------------------------------*/
|
|
|
|
typedef struct _OSet OSet;
|
|
|
|
// - Cmp: returns -1, 0 or 1 if key is <, == or > elem.
|
|
// - Alloc: allocates a chunk of memory.
|
|
// - Free: frees a chunk of memory allocated with Alloc.
|
|
|
|
typedef Word (*OSetCmp_t) ( const void* key, const void* elem );
|
|
typedef void* (*OSetAlloc_t) ( const HChar* cc, SizeT szB );
|
|
typedef void (*OSetFree_t) ( void* p );
|
|
|
|
/*--------------------------------------------------------------------*/
|
|
/*--- Creating and destroying OSets (UWord) ---*/
|
|
/*--------------------------------------------------------------------*/
|
|
|
|
// * Create: allocates and initialises the OSet. Never returns NULL.
|
|
// Parameters:
|
|
// - alloc_fn The allocation function used internally for allocating the
|
|
// OSet and all its nodes. It must not return NULL (that is,
|
|
// if it returns it must have succeeded.)
|
|
// - cc Cost centre string used by 'alloc'.
|
|
// - free_fn The deallocation function used internally for freeing nodes
|
|
// called by VG_(OSetWord_Destroy)().
|
|
//
|
|
// * Destroy: frees all nodes in the table, plus the memory used by
|
|
// the table itself. The passed-in function is called on each node first
|
|
// to allow the destruction of any attached resources; if NULL it is not
|
|
// called.
|
|
|
|
extern OSet* VG_(OSetWord_Create) ( OSetAlloc_t alloc_fn, const HChar* cc,
|
|
OSetFree_t free_fn );
|
|
extern void VG_(OSetWord_Destroy) ( OSet* os );
|
|
|
|
/*--------------------------------------------------------------------*/
|
|
/*--- Operations on OSets (UWord) ---*/
|
|
/*--------------------------------------------------------------------*/
|
|
|
|
// In everything that follows, the parameter 'key' is always the *address*
|
|
// of the key, and 'elem' is *address* of the elem, as are the return values
|
|
// of the functions that return elems.
|
|
//
|
|
// * Size: The number of elements in the set.
|
|
//
|
|
// * Contains: Determines if the value is in the set.
|
|
//
|
|
// * Insert: Inserts a new element into the set. Duplicates are forbidden,
|
|
// and will cause assertion failures.
|
|
//
|
|
// * Remove: Removes the value from the set, if present. Returns a Bool
|
|
// indicating if the value was removed.
|
|
//
|
|
// * ResetIter: Each OSet has an iterator. This resets it to point to the
|
|
// first element in the OSet.
|
|
//
|
|
// * Next: Copies the next value according to the OSet's iterator into &val,
|
|
// advances the iterator by one, and returns True; the elements are
|
|
// visited in increasing order of unsigned words (UWord). Or, returns
|
|
// False if the iterator has reached the set's end.
|
|
//
|
|
// You can thus iterate in order through a set like this:
|
|
//
|
|
// Word val;
|
|
// VG_(OSetWord_ResetIter)(oset);
|
|
// while ( VG_(OSetWord_Next)(oset, &val) ) {
|
|
// ... do stuff with 'val' ...
|
|
// }
|
|
//
|
|
// Note that iterators are cleared any time an element is inserted or
|
|
// removed from the OSet, to avoid possible mayhem caused by the iterator
|
|
// getting out of sync with the OSet's contents. "Cleared" means that
|
|
// they will return False if VG_(OSetWord_Next)() is called without an
|
|
// intervening call to VG_(OSetWord_ResetIter)().
|
|
|
|
extern Word VG_(OSetWord_Size) ( const OSet* os );
|
|
extern void VG_(OSetWord_Insert) ( OSet* os, UWord val );
|
|
extern Bool VG_(OSetWord_Contains) ( const OSet* os, UWord val );
|
|
extern Bool VG_(OSetWord_Remove) ( OSet* os, UWord val );
|
|
extern void VG_(OSetWord_ResetIter) ( OSet* os );
|
|
extern Bool VG_(OSetWord_Next) ( OSet* os, /*OUT*/UWord* val );
|
|
|
|
|
|
/*--------------------------------------------------------------------*/
|
|
/*--- Creating and destroying OSets and OSet members (Gen) ---*/
|
|
/*--------------------------------------------------------------------*/
|
|
|
|
// * Create: allocates and initialises the OSet. Never returns NULL.
|
|
// Parameters:
|
|
// - keyOff The offset of the key within the element.
|
|
// - cmp The comparison function between keys and elements, or NULL
|
|
// if the OSet should use fast comparisons.
|
|
// - alloc_fn The allocation function used for allocating the OSet itself;
|
|
// It must not return NULL (that is, if it returns it must
|
|
// have succeeded.)
|
|
// If a pool allocator is used, it's called to allocate pool of
|
|
// nodes.
|
|
// If no pool allocator is used, it's called for each
|
|
// invocation of VG_(OSetGen_AllocNode)().
|
|
// - cc Cost centre string used by 'alloc'.
|
|
// - free_fn If no pool allocator is used, this is the deallocation
|
|
// function used by VG_(OSetGen_FreeNode)() and
|
|
// VG_(OSetGen_Destroy)().
|
|
// If a pool allocator is used, the memory used by the nodes is
|
|
// deallocated when the pool is deleted.
|
|
// (for more details about pool allocators, see pub_tool_poolalloc.h).
|
|
//
|
|
//
|
|
// If cmp is NULL, keyOff must be zero. This is checked.
|
|
//
|
|
// * Destroy: frees all nodes in the table, plus the memory used by
|
|
// the table itself. The passed-in function is called on each node first
|
|
// to allow the destruction of any attached resources; if NULL it is not
|
|
// called.
|
|
//
|
|
// * AllocNode: Allocate and zero memory for a node to go into the OSet.
|
|
// If a pool allocator is used, it uses the pool allocator to allocate a node.
|
|
// Otherwise, uses the alloc function given to VG_(OSetGen_Create)() to
|
|
// allocate a node which is big enough for both an element and the OSet
|
|
// metadata.
|
|
// Not all elements in one OSet have to be the same size.
|
|
// However, if a pool allocator is used, elements will all have a size equal
|
|
// to the max user data size given at creation + the node meta data size.
|
|
//
|
|
// Note that the element allocated will be at most word-aligned, which may
|
|
// be less aligned than the element type would normally be.
|
|
//
|
|
// * FreeNode: Deallocate a node allocated with OSetGen_AllocNode(). Using
|
|
// a deallocation function (such as VG_(free)()) directly will likely
|
|
// lead to assertions in Valgrind's allocator.
|
|
|
|
extern OSet* VG_(OSetGen_Create) ( PtrdiffT keyOff, OSetCmp_t cmp,
|
|
OSetAlloc_t alloc_fn, const HChar* cc,
|
|
OSetFree_t free_fn);
|
|
|
|
|
|
extern OSet* VG_(OSetGen_Create_With_Pool) ( PtrdiffT keyOff, OSetCmp_t cmp,
|
|
OSetAlloc_t alloc_fn,
|
|
const HChar* cc,
|
|
OSetFree_t free_fn,
|
|
SizeT poolSize,
|
|
SizeT maxEltSize);
|
|
// Same as VG_(OSetGen_Create) but created OSet will use a pool allocator to
|
|
// allocate the nodes.
|
|
// The node size is the sum of a fixed small meta data size needed for OSet
|
|
// + the size of the user data element.
|
|
// The maximum size for the user data element is specified by maxEltSize.
|
|
// (if poolSize is 0, maxEltSize is not relevant for the OSet).
|
|
// It is interesting to use a pool allocator when an OSet has many elements,
|
|
// and these elements have a small fixed size, or have a variable size, but
|
|
// always <= than a (small) maximum value.
|
|
// In such a case, allocating the nodes in pools reduces significantly
|
|
// the memory overhead needed by each node.
|
|
// When a node is freed (i.e. OSetGen_Freenode is called), the node is
|
|
// put back in the pool allocator free list (for sub-sequent re-use by
|
|
// OSetGen_AllocNode). Note that the pool memory is only released when
|
|
// the pool is destroyed : calls to VG_(OSetGen_Free) do not cause
|
|
// any calls to OSetFree_t _free function.
|
|
// If there are several OSet managing similar such elements, it might be
|
|
// interesting to use a shared pool for these OSet.
|
|
// To have multiple OSets sharing a pool allocator, create the first OSet
|
|
// with VG_(OSetGen_Create_With_Pool). Create subsequent OSet with
|
|
// VG_(OSetGen_EmptyClone).
|
|
|
|
extern void VG_(OSetGen_Destroy) ( OSet* os );
|
|
extern void* VG_(OSetGen_AllocNode) ( const OSet* os, SizeT elemSize );
|
|
extern void VG_(OSetGen_FreeNode) ( const OSet* os, void* elem );
|
|
|
|
extern OSet* VG_(OSetGen_EmptyClone) (const OSet* os);
|
|
// Creates a new empty OSet.
|
|
// The new OSet will have the same characteristics as os.
|
|
// If os uses a pool allocator, this pool allocator will be shared with
|
|
// the new OSet. A shared pool allocator is only deleted (and its memory is
|
|
// released) when the last OSet using the shared pool is destroyed.
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
/*--- Operations on OSets (Gen) ---*/
|
|
/*--------------------------------------------------------------------*/
|
|
|
|
// In everything that follows, the parameter 'key' is always the *address*
|
|
// of the key, and 'elem' is *address* of the elem, as are the return values
|
|
// of the functions that return elems.
|
|
//
|
|
// * Size: The number of elements in the set.
|
|
//
|
|
// * Insert: Inserts a new element into the set. Note that 'elem' must
|
|
// have been allocated using VG_(OSetGen_AllocNode)(), otherwise you will
|
|
// get assertion failures about "bad magic". Duplicates are forbidden,
|
|
// and will also cause assertion failures.
|
|
//
|
|
// * Contains: Determines if any element in the OSet matches the key.
|
|
//
|
|
// * Lookup: Returns a pointer to the element matching the key, if there is
|
|
// one, otherwise returns NULL.
|
|
//
|
|
// * LookupWithCmp: Like Lookup, but you specify the comparison function,
|
|
// which overrides the OSet's normal one.
|
|
//
|
|
// * Remove: Removes the element matching the key, if there is one. Returns
|
|
// NULL if no element matches the key.
|
|
//
|
|
// * ResetIter: Each OSet has an iterator. This resets it to point to the
|
|
// first element in the OSet.
|
|
//
|
|
// * ResetIterAt: Like ResetIter, but instead of resetting the iterator to the
|
|
// smallest element, it resets the iterator to point to the smallest element
|
|
// in the set whose key is greater-than-or-equal to the given key. (In many
|
|
// cases this will be the element whose key equals that of the given key.)
|
|
//
|
|
// * Next: Returns a pointer to the element pointed to by the OSet's
|
|
// iterator, and advances the iterator by one; the elements are visited
|
|
// in order. Or, returns NULL if the iterator has reached the OSet's end.
|
|
//
|
|
// You can thus iterate in order through a set like this:
|
|
//
|
|
// VG_(OSetGen_ResetIter)(oset);
|
|
// while ( (elem = VG_(OSetGen_Next)(oset)) ) {
|
|
// ... do stuff with 'elem' ...
|
|
// }
|
|
//
|
|
// Note that iterators are cleared any time an element is inserted or
|
|
// removed from the OSet, to avoid possible mayhem caused by the iterator
|
|
// getting out of sync with the OSet's contents. "Cleared" means that
|
|
// they will return NULL if VG_(OSetGen_Next)() is called without an
|
|
// intervening call to VG_(OSetGen_ResetIter)().
|
|
|
|
extern UInt VG_(OSetGen_Size) ( const OSet* os );
|
|
extern void VG_(OSetGen_Insert) ( OSet* os, void* elem );
|
|
extern Bool VG_(OSetGen_Contains) ( const OSet* os, const void* key );
|
|
extern void* VG_(OSetGen_Lookup) ( const OSet* os, const void* key );
|
|
extern void* VG_(OSetGen_LookupWithCmp)( OSet* os,
|
|
const void* key, OSetCmp_t cmp );
|
|
extern void* VG_(OSetGen_Remove) ( OSet* os, const void* key );
|
|
extern void VG_(OSetGen_ResetIter) ( OSet* os );
|
|
extern void VG_(OSetGen_ResetIterAt) ( OSet* os, const void* key );
|
|
extern void* VG_(OSetGen_Next) ( OSet* os );
|
|
|
|
|
|
#endif // __PUB_TOOL_OSET_H
|
|
|
|
/*--------------------------------------------------------------------*/
|
|
/*--- end ---*/
|
|
/*--------------------------------------------------------------------*/
|