blob: 95ffefa530e5e191294446aaa756eaa96f431e40 [file] [log] [blame]
/*--------------------------------------------------------------------*/
/*--- 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) 2000-2005 Julian Seward
jseward@acm.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
// 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.
//
// The structure is totally generic. 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 (signed or unsigned) words, and that
// the key is the first word in each element. This fast comparison is
// suitable for an OSet of Words, or an OSet containing structs where the
// first element is an Addr, for example.
//
// Each OSet 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;
typedef struct _OSetNode OSetNode;
typedef Word (*OSetCmp_t) ( void* key, void* elem );
typedef void* (*OSetAlloc_t) ( SizeT szB );
typedef void (*OSetFree_t) ( void* p );
typedef void (*OSetNodeDestroy_t) ( void* elem );
/*--------------------------------------------------------------------*/
/*--- Creating and destroying OSets and OSet members ---*/
/*--------------------------------------------------------------------*/
// * Create: allocates and initialises the OSet. Arguments:
// - 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 The allocation function used for allocating the OSet itself;
// it's also called for each invocation of VG_(OSet_AllocNode)().
// - free The deallocation function used by VG_(OSet_FreeNode)() and
// VG_(OSet_Destroy)().
//
// 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.
// Uses the alloc function given to VG_(OSet_Create)() to allocated 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.
//
// 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 OSet_AllocNode(). Using
// a deallocation function (such as VG_(free)()) directly will likely
// lead to assertions in Valgrind's allocator.
extern OSet* VG_(OSet_Create) ( OffT keyOff, OSetCmp_t cmp,
OSetAlloc_t alloc, OSetFree_t free );
extern void VG_(OSet_Destroy) ( OSet* os, OSetNodeDestroy_t destroyNode );
extern void* VG_(OSet_AllocNode) ( OSet* os, SizeT elemSize );
extern void VG_(OSet_FreeNode) ( OSet* os, void* elem );
/*--------------------------------------------------------------------*/
/*--- Operations on OSets ---*/
/*--------------------------------------------------------------------*/
// 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 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.
//
// * Insert: Inserts a new element into the list. Note that 'elem' must
// have been allocated using VG_(OSet_AllocNode)(), otherwise you will get
// assertion failures about "bad magic". Duplicates are forbidden, and
// will also cause assertion failures.
//
// * 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.
//
// * 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 an OSet like this:
//
// VG_(OSet_ResetIter)(oset);
// while ( (elem = VG_(OSet_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_(OSet_Next)() is called without an
// intervening call to VG_(OSet_ResetIter)().
extern Int VG_(OSet_Size) ( OSet* os );
extern void VG_(OSet_Insert) ( OSet* os, void* elem );
extern Bool VG_(OSet_Contains) ( OSet* os, void* key );
extern void* VG_(OSet_Lookup) ( OSet* os, void* key );
extern void* VG_(OSet_LookupWithCmp)( OSet* os, void* key, OSetCmp_t cmp );
extern void* VG_(OSet_Remove) ( OSet* os, void* key );
extern void VG_(OSet_ResetIter) ( OSet* os );
extern void* VG_(OSet_Next) ( OSet* os );
#endif // __PUB_TOOL_OSET_H
/*--------------------------------------------------------------------*/
/*--- end ---*/
/*--------------------------------------------------------------------*/