mirror of
https://github.com/ioacademy-jikim/debugging
synced 2025-06-08 00:16:11 +00:00
216 lines
9.1 KiB
C
216 lines
9.1 KiB
C
|
|
/*--------------------------------------------------------------------*/
|
|
/*--- An AVL tree based finite map for word keys and word values. ---*/
|
|
/*--- Inspired by Haskell's "FiniteMap" library. ---*/
|
|
/*--- pub_tool_wordfm.h ---*/
|
|
/*--------------------------------------------------------------------*/
|
|
|
|
/*
|
|
This file is part of Valgrind, a dynamic binary instrumentation
|
|
framework.
|
|
|
|
Copyright (C) 2007-2015 Julian Seward
|
|
jseward@acm.org
|
|
|
|
This code is based on previous work by Nicholas Nethercote
|
|
(coregrind/m_oset.c) which is
|
|
|
|
Copyright (C) 2005-2015 Nicholas Nethercote
|
|
njn@valgrind.org
|
|
|
|
which in turn was derived partially from:
|
|
|
|
AVL C library
|
|
Copyright (C) 2000,2002 Daniel Nagy
|
|
|
|
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.
|
|
[...]
|
|
|
|
(taken from libavl-0.4/debian/copyright)
|
|
|
|
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_WORDFM_H
|
|
#define __PUB_TOOL_WORDFM_H
|
|
|
|
#include "pub_tool_basics.h" // Word
|
|
|
|
//------------------------------------------------------------------//
|
|
//--- WordFM ---//
|
|
//--- Public interface ---//
|
|
//------------------------------------------------------------------//
|
|
|
|
/* As of r7409 (15 Feb 08), all these word-based abstractions (WordFM,
|
|
WordSet, WordBag) now operate on unsigned words (UWord), whereas
|
|
they previously operated on signed words (Word). This became a
|
|
problem, when using unboxed comparisons (when kCmp == NULL), with
|
|
the introduction of VG_(initIterAtFM), which allows iteration over
|
|
parts of mappings. Iterating over a mapping in increasing order of
|
|
signed Word keys is not what callers expect when iterating through
|
|
maps whose keys represent addresses (Addr) since Addr is unsigned,
|
|
and causes logical problems and assertion failures. */
|
|
|
|
typedef struct _WordFM WordFM; /* opaque */
|
|
|
|
/* Allocate and initialise a WordFM. If kCmp is non-NULL, elements in
|
|
the set are ordered according to the ordering specified by kCmp,
|
|
which becomes obvious if you use VG_(initIterFM),
|
|
VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over
|
|
sections of the map, or the whole thing. If kCmp is NULL then the
|
|
ordering used is unsigned word ordering (UWord) on the key
|
|
values.
|
|
The function never returns NULL. */
|
|
WordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
|
|
const HChar* cc,
|
|
void (*dealloc)(void*),
|
|
Word (*kCmp)(UWord,UWord) );
|
|
|
|
/* Free up the FM. If kFin is non-NULL, it is applied to keys
|
|
before the FM is deleted; ditto with vFin for vals. */
|
|
void VG_(deleteFM) ( WordFM*, void(*kFin)(UWord), void(*vFin)(UWord) );
|
|
|
|
/* Add (k,v) to fm. If a binding for k already exists, it is updated
|
|
to map to this new v. In that case we should really return the
|
|
previous v so that caller can finalise it. Oh well. Returns
|
|
True if a binding for k already exists. */
|
|
Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v );
|
|
|
|
// Delete key from fm, returning associated key and val if found
|
|
Bool VG_(delFromFM) ( WordFM* fm,
|
|
/*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key );
|
|
|
|
// Look up in fm, assigning found key & val at spec'd addresses
|
|
Bool VG_(lookupFM) ( const WordFM* fm,
|
|
/*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key );
|
|
|
|
// Find the closest key values bracketing the given key, assuming the
|
|
// given key is not present in the map. minKey and maxKey are the
|
|
// minimum and maximum possible key values. The resulting bracket
|
|
// values are returned in *kMinP and *kMaxP. It follows that if fm is
|
|
// empty then the returned values are simply minKey and maxKey.
|
|
//
|
|
// For convenience the associated value fields are also returned
|
|
// through *vMinP and *vMaxP. To make that possible in the general
|
|
// case, the caller must supply via minVal and maxVal, the value
|
|
// fields associated with minKey and maxKey.
|
|
//
|
|
// If the operation was successful (that is, the given key is not
|
|
// present), True is returned. If the given key is in fact present,
|
|
// False is returned, and *kMinP, *vMinP, *kMaxP and *vMaxP are
|
|
// undefined. Any of kMinP, vMinP, kMaxP and vMaxP may be safely
|
|
// supplied as NULL.
|
|
Bool VG_(findBoundsFM)( const WordFM* fm,
|
|
/*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP,
|
|
/*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP,
|
|
UWord minKey, UWord minVal,
|
|
UWord maxKey, UWord maxVal,
|
|
UWord key );
|
|
|
|
// How many elements are there in fm? NOTE: dangerous in the
|
|
// sense that this is not an O(1) operation but rather O(N),
|
|
// since it involves walking the whole tree.
|
|
UWord VG_(sizeFM) ( const WordFM* fm );
|
|
|
|
// set up FM for iteration
|
|
void VG_(initIterFM) ( WordFM* fm );
|
|
|
|
// set up FM for iteration so that the first key subsequently produced
|
|
// by VG_(nextIterFM) is the smallest key in the map >= start_at.
|
|
// Naturally ">=" is defined by the comparison function supplied to
|
|
// VG_(newFM), as documented above.
|
|
void VG_(initIterAtFM) ( WordFM* fm, UWord start_at );
|
|
|
|
// get next key/val pair. Will assert if fm has been modified
|
|
// or looked up in since initIterFM/initIterWithStartFM was called.
|
|
Bool VG_(nextIterFM) ( WordFM* fm,
|
|
/*OUT*/UWord* pKey, /*OUT*/UWord* pVal );
|
|
|
|
// Finish an FM iteration
|
|
void VG_(doneIterFM) ( WordFM* fm );
|
|
|
|
// Deep copy a FM. If dopyK is NULL, keys are copied verbatim.
|
|
// If non-null, dopyK is applied to each key to generate the
|
|
// version in the new copy. dopyK may be called with a NULL argument
|
|
// in which case it should return NULL. For all other argument values
|
|
// dopyK must not return NULL. Ditto with dopyV for values.
|
|
// VG_(dopyFM) never returns NULL.
|
|
WordFM* VG_(dopyFM) ( WordFM* fm,
|
|
UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) );
|
|
|
|
//------------------------------------------------------------------//
|
|
//--- end WordFM ---//
|
|
//--- Public interface ---//
|
|
//------------------------------------------------------------------//
|
|
|
|
//------------------------------------------------------------------//
|
|
//--- WordBag (unboxed words only) ---//
|
|
//--- Public interface ---//
|
|
//------------------------------------------------------------------//
|
|
|
|
typedef struct _WordBag WordBag; /* opaque */
|
|
|
|
/* Allocate and initialise a WordBag. Never returns NULL. */
|
|
WordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar* cc, SizeT ),
|
|
const HChar* cc,
|
|
void (*dealloc)(void*) );
|
|
|
|
/* Free up the Bag. */
|
|
void VG_(deleteBag) ( WordBag* );
|
|
|
|
/* Add a word. */
|
|
void VG_(addToBag)( WordBag*, UWord );
|
|
|
|
/* Find out how many times the given word exists in the bag. */
|
|
UWord VG_(elemBag) ( const WordBag*, UWord );
|
|
|
|
/* Delete a word from the bag. */
|
|
Bool VG_(delFromBag)( WordBag*, UWord );
|
|
|
|
/* Is the bag empty? */
|
|
Bool VG_(isEmptyBag)( const WordBag* );
|
|
|
|
/* Does the bag have exactly one element? */
|
|
Bool VG_(isSingletonTotalBag)( const WordBag* );
|
|
|
|
/* Return an arbitrary element from the bag. */
|
|
UWord VG_(anyElementOfBag)( const WordBag* );
|
|
|
|
/* How many different / total elements are in the bag? */
|
|
UWord VG_(sizeUniqueBag)( const WordBag* ); /* fast */
|
|
UWord VG_(sizeTotalBag)( const WordBag* ); /* warning: slow */
|
|
|
|
/* Iterating over the elements of a bag. */
|
|
void VG_(initIterBag)( WordBag* );
|
|
Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount );
|
|
void VG_(doneIterBag)( WordBag* );
|
|
|
|
//------------------------------------------------------------------//
|
|
//--- end WordBag (unboxed words only) ---//
|
|
//--- Public interface ---//
|
|
//------------------------------------------------------------------//
|
|
|
|
#endif /* ! __PUB_TOOL_WORDFM_H */
|
|
|
|
/*--------------------------------------------------------------------*/
|
|
/*--- end pub_tool_wordfm.h ---*/
|
|
/*--------------------------------------------------------------------*/
|