EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 10:13:31
0001 0002 /*--------------------------------------------------------------------*/ 0003 /*--- An AVL tree based finite map for word keys and word values. ---*/ 0004 /*--- Inspired by Haskell's "FiniteMap" library. ---*/ 0005 /*--- pub_tool_wordfm.h ---*/ 0006 /*--------------------------------------------------------------------*/ 0007 0008 /* 0009 This file is part of Valgrind, a dynamic binary instrumentation 0010 framework. 0011 0012 Copyright (C) 2007-2017 Julian Seward 0013 jseward@acm.org 0014 0015 This code is based on previous work by Nicholas Nethercote 0016 (coregrind/m_oset.c) which is 0017 0018 Copyright (C) 2005-2017 Nicholas Nethercote 0019 njn@valgrind.org 0020 0021 which in turn was derived partially from: 0022 0023 AVL C library 0024 Copyright (C) 2000,2002 Daniel Nagy 0025 0026 This program is free software; you can redistribute it and/or 0027 modify it under the terms of the GNU General Public License as 0028 published by the Free Software Foundation; either version 2 of 0029 the License, or (at your option) any later version. 0030 [...] 0031 0032 (taken from libavl-0.4/debian/copyright) 0033 0034 This program is free software; you can redistribute it and/or 0035 modify it under the terms of the GNU General Public License as 0036 published by the Free Software Foundation; either version 2 of the 0037 License, or (at your option) any later version. 0038 0039 This program is distributed in the hope that it will be useful, but 0040 WITHOUT ANY WARRANTY; without even the implied warranty of 0041 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0042 General Public License for more details. 0043 0044 You should have received a copy of the GNU General Public License 0045 along with this program; if not, see <http://www.gnu.org/licenses/>. 0046 0047 The GNU General Public License is contained in the file COPYING. 0048 */ 0049 0050 #ifndef __PUB_TOOL_WORDFM_H 0051 #define __PUB_TOOL_WORDFM_H 0052 0053 #include "pub_tool_basics.h" // Word 0054 0055 //------------------------------------------------------------------// 0056 //--- WordFM ---// 0057 //--- Public interface ---// 0058 //------------------------------------------------------------------// 0059 0060 /* As of r7409 (15 Feb 08), all these word-based abstractions (WordFM, 0061 WordSet, WordBag) now operate on unsigned words (UWord), whereas 0062 they previously operated on signed words (Word). This became a 0063 problem, when using unboxed comparisons (when kCmp == NULL), with 0064 the introduction of VG_(initIterAtFM), which allows iteration over 0065 parts of mappings. Iterating over a mapping in increasing order of 0066 signed Word keys is not what callers expect when iterating through 0067 maps whose keys represent addresses (Addr) since Addr is unsigned, 0068 and causes logical problems and assertion failures. */ 0069 0070 typedef struct _WordFM WordFM; /* opaque */ 0071 0072 /* Allocate and initialise a WordFM. If kCmp is non-NULL, elements in 0073 the set are ordered according to the ordering specified by kCmp, 0074 which becomes obvious if you use VG_(initIterFM), 0075 VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over 0076 sections of the map, or the whole thing. If kCmp is NULL then the 0077 ordering used is unsigned word ordering (UWord) on the key 0078 values. 0079 The function never returns NULL. */ 0080 WordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar* cc, SizeT ), 0081 const HChar* cc, 0082 void (*dealloc)(void*), 0083 Word (*kCmp)(UWord,UWord) ); 0084 0085 /* Free up the FM. If kFin is non-NULL, it is applied to keys 0086 before the FM is deleted; ditto with vFin for vals. */ 0087 void VG_(deleteFM) ( WordFM*, void(*kFin)(UWord), void(*vFin)(UWord) ); 0088 0089 /* Add (k,v) to fm. If a binding for k already exists, it is updated 0090 to map to this new v. In that case we should really return the 0091 previous v so that caller can finalise it. Oh well. Returns 0092 True if a binding for k already exists. */ 0093 Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v ); 0094 0095 // Delete key from fm, returning associated key and val if found 0096 Bool VG_(delFromFM) ( WordFM* fm, 0097 /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key ); 0098 0099 // Look up in fm, assigning found key & val at spec'd addresses 0100 Bool VG_(lookupFM) ( const WordFM* fm, 0101 /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key ); 0102 0103 // Find the closest key values bracketing the given key, assuming the 0104 // given key is not present in the map. minKey and maxKey are the 0105 // minimum and maximum possible key values. The resulting bracket 0106 // values are returned in *kMinP and *kMaxP. It follows that if fm is 0107 // empty then the returned values are simply minKey and maxKey. 0108 // 0109 // For convenience the associated value fields are also returned 0110 // through *vMinP and *vMaxP. To make that possible in the general 0111 // case, the caller must supply via minVal and maxVal, the value 0112 // fields associated with minKey and maxKey. 0113 // 0114 // If the operation was successful (that is, the given key is not 0115 // present), True is returned. If the given key is in fact present, 0116 // False is returned, and *kMinP, *vMinP, *kMaxP and *vMaxP are 0117 // undefined. Any of kMinP, vMinP, kMaxP and vMaxP may be safely 0118 // supplied as NULL. 0119 Bool VG_(findBoundsFM)( const WordFM* fm, 0120 /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP, 0121 /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP, 0122 UWord minKey, UWord minVal, 0123 UWord maxKey, UWord maxVal, 0124 UWord key ); 0125 0126 // How many elements are there in fm? NOTE: dangerous in the 0127 // sense that this is not an O(1) operation but rather O(N), 0128 // since it involves walking the whole tree. 0129 UWord VG_(sizeFM) ( const WordFM* fm ); 0130 0131 // set up FM for iteration 0132 void VG_(initIterFM) ( WordFM* fm ); 0133 0134 // set up FM for iteration so that the first key subsequently produced 0135 // by VG_(nextIterFM) is the smallest key in the map >= start_at. 0136 // Naturally ">=" is defined by the comparison function supplied to 0137 // VG_(newFM), as documented above. 0138 void VG_(initIterAtFM) ( WordFM* fm, UWord start_at ); 0139 0140 // get next key/val pair. Will assert if fm has been modified 0141 // or looked up in since initIterFM/initIterWithStartFM was called. 0142 Bool VG_(nextIterFM) ( WordFM* fm, 0143 /*OUT*/UWord* pKey, /*OUT*/UWord* pVal ); 0144 0145 // Finish an FM iteration 0146 void VG_(doneIterFM) ( WordFM* fm ); 0147 0148 // Deep copy a FM. If dopyK is NULL, keys are copied verbatim. 0149 // If non-null, dopyK is applied to each key to generate the 0150 // version in the new copy. dopyK may be called with a NULL argument 0151 // in which case it should return NULL. For all other argument values 0152 // dopyK must not return NULL. Ditto with dopyV for values. 0153 // VG_(dopyFM) never returns NULL. 0154 WordFM* VG_(dopyFM) ( WordFM* fm, 0155 UWord(*dopyK)(UWord), UWord(*dopyV)(UWord) ); 0156 0157 //------------------------------------------------------------------// 0158 //--- end WordFM ---// 0159 //--- Public interface ---// 0160 //------------------------------------------------------------------// 0161 0162 //------------------------------------------------------------------// 0163 //--- WordBag (unboxed words only) ---// 0164 //--- Public interface ---// 0165 //------------------------------------------------------------------// 0166 0167 typedef struct _WordBag WordBag; /* opaque */ 0168 0169 /* Allocate and initialise a WordBag. Never returns NULL. */ 0170 WordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar* cc, SizeT ), 0171 const HChar* cc, 0172 void (*dealloc)(void*) ); 0173 0174 /* Free up the Bag. */ 0175 void VG_(deleteBag) ( WordBag* ); 0176 0177 /* Add a word. */ 0178 void VG_(addToBag)( WordBag*, UWord ); 0179 0180 /* Find out how many times the given word exists in the bag. */ 0181 UWord VG_(elemBag) ( const WordBag*, UWord ); 0182 0183 /* Delete a word from the bag. */ 0184 Bool VG_(delFromBag)( WordBag*, UWord ); 0185 0186 /* Is the bag empty? */ 0187 Bool VG_(isEmptyBag)( const WordBag* ); 0188 0189 /* Does the bag have exactly one element? */ 0190 Bool VG_(isSingletonTotalBag)( const WordBag* ); 0191 0192 /* Return an arbitrary element from the bag. */ 0193 UWord VG_(anyElementOfBag)( const WordBag* ); 0194 0195 /* How many different / total elements are in the bag? */ 0196 UWord VG_(sizeUniqueBag)( const WordBag* ); /* fast */ 0197 UWord VG_(sizeTotalBag)( const WordBag* ); /* warning: slow */ 0198 0199 /* Iterating over the elements of a bag. */ 0200 void VG_(initIterBag)( WordBag* ); 0201 Bool VG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount ); 0202 void VG_(doneIterBag)( WordBag* ); 0203 0204 //------------------------------------------------------------------// 0205 //--- end WordBag (unboxed words only) ---// 0206 //--- Public interface ---// 0207 //------------------------------------------------------------------// 0208 0209 #endif /* ! __PUB_TOOL_WORDFM_H */ 0210 0211 /*--------------------------------------------------------------------*/ 0212 /*--- end pub_tool_wordfm.h ---*/ 0213 /*--------------------------------------------------------------------*/
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|