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-2010 Nicholas Nethercote 11 njn (at) 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 // This module implements an ordered set, a data structure with fast 35 // (eg. amortised log(n) or better) insertion, lookup and deletion of 36 // elements. It does not allow duplicates, and will assert if you insert a 37 // duplicate to an OSet. 38 // 39 // It has two interfaces. 40 // 41 // - The "OSetWord_" interface provides an easier-to-use interface for the 42 // case where you just want to store UWord-sized values. The user 43 // provides the allocation and deallocation functions, and possibly a 44 // comparison function. 45 // 46 // - The "OSetGen_" interface provides a totally generic interface, which 47 // allows any kind of structure to be put into the set. The user provides 48 // the allocation and deallocation functions. Also, each element has a 49 // key, which the lookup is done with. The key may be the whole element 50 // (eg. in an OSet of integers, each integer serves both as an element and 51 // a key), or it may be only part of it (eg. if the key is a single field 52 // in a struct). The user can provide a function that compares an element 53 // with a key; this is very flexible, and with the right comparison 54 // function even a (non-overlapping) interval list can be created. But 55 // the cost of calling a function for every comparison can be high during 56 // lookup. If no comparison function is provided, we assume that keys are 57 // (signed or unsigned) words, and that the key is the first word in each 58 // element. This fast comparison is suitable for an OSet containing 59 // structs where the first element is an Addr, for example. 60 // 61 // Each OSet interface also has an iterator, which makes it simple to 62 // traverse all the nodes in order. Note that the iterator maintains state 63 // and so is non-reentrant. 64 // 65 // Note that once you insert an element into an OSet, if you modify any part 66 // of it looked at by your cmp() function, this may cause incorrect 67 // behaviour as the sorted order maintained will be wrong. 68 69 /*--------------------------------------------------------------------*/ 70 /*--- Types ---*/ 71 /*--------------------------------------------------------------------*/ 72 73 typedef struct _OSet OSet; 74 75 // - Cmp: returns -1, 0 or 1 if key is <, == or > elem. 76 // - Alloc: allocates a chunk of memory. 77 // - Free: frees a chunk of memory allocated with Alloc. 78 79 typedef Word (*OSetCmp_t) ( const void* key, const void* elem ); 80 typedef void* (*OSetAlloc_t) ( HChar* cc, SizeT szB ); 81 typedef void (*OSetFree_t) ( void* p ); 82 83 /*--------------------------------------------------------------------*/ 84 /*--- Creating and destroying OSets (UWord) ---*/ 85 /*--------------------------------------------------------------------*/ 86 87 // * Create: allocates and initialises the OSet. Arguments: 88 // - alloc The allocation function used internally for allocating the 89 // OSet and all its nodes. 90 // - cc Cost centre string used by 'alloc'. 91 // - free The deallocation function used internally for freeing nodes 92 // called by VG_(OSetWord_Destroy)(). 93 // 94 // * CreateWithCmp: like Create, but you specify your own comparison 95 // function. 96 // 97 // * Destroy: frees all nodes in the table, plus the memory used by 98 // the table itself. The passed-in function is called on each node first 99 // to allow the destruction of any attached resources; if NULL it is not 100 // called. 101 102 extern OSet* VG_(OSetWord_Create) ( OSetAlloc_t alloc, HChar* cc, 103 OSetFree_t _free ); 104 extern void VG_(OSetWord_Destroy) ( OSet* os ); 105 106 /*--------------------------------------------------------------------*/ 107 /*--- Operations on OSets (UWord) ---*/ 108 /*--------------------------------------------------------------------*/ 109 110 // In everything that follows, the parameter 'key' is always the *address* 111 // of the key, and 'elem' is *address* of the elem, as are the return values 112 // of the functions that return elems. 113 // 114 // * Size: The number of elements in the set. 115 // 116 // * Contains: Determines if the value is in the set. 117 // 118 // * Insert: Inserts a new element into the set. Duplicates are forbidden, 119 // and will cause assertion failures. 120 // 121 // * Remove: Removes the value from the set, if present. Returns a Bool 122 // indicating if the value was removed. 123 // 124 // * ResetIter: Each OSet has an iterator. This resets it to point to the 125 // first element in the OSet. 126 // 127 // * Next: Copies the next value according to the OSet's iterator into &val, 128 // advances the iterator by one, and returns True; the elements are 129 // visited in increasing order of unsigned words (UWord). Or, returns 130 // False if the iterator has reached the set's end. 131 // 132 // You can thus iterate in order through a set like this: 133 // 134 // Word val; 135 // VG_(OSetWord_ResetIter)(oset); 136 // while ( VG_(OSetWord_Next)(oset, &val) ) { 137 // ... do stuff with 'val' ... 138 // } 139 // 140 // Note that iterators are cleared any time an element is inserted or 141 // removed from the OSet, to avoid possible mayhem caused by the iterator 142 // getting out of sync with the OSet's contents. "Cleared" means that 143 // they will return False if VG_(OSetWord_Next)() is called without an 144 // intervening call to VG_(OSetWord_ResetIter)(). 145 146 extern Word VG_(OSetWord_Size) ( OSet* os ); 147 extern void VG_(OSetWord_Insert) ( OSet* os, UWord val ); 148 extern Bool VG_(OSetWord_Contains) ( OSet* os, UWord val ); 149 extern Bool VG_(OSetWord_Remove) ( OSet* os, UWord val ); 150 extern void VG_(OSetWord_ResetIter) ( OSet* os ); 151 extern Bool VG_(OSetWord_Next) ( OSet* os, /*OUT*/UWord* val ); 152 153 154 /*--------------------------------------------------------------------*/ 155 /*--- Creating and destroying OSets and OSet members (Gen) ---*/ 156 /*--------------------------------------------------------------------*/ 157 158 // * Create: allocates and initialises the OSet. Arguments: 159 // - keyOff The offset of the key within the element. 160 // - cmp The comparison function between keys and elements, or NULL 161 // if the OSet should use fast comparisons. 162 // - alloc The allocation function used for allocating the OSet itself; 163 // it's also called for each invocation of 164 // VG_(OSetGen_AllocNode)(). 165 // - cc Cost centre string used by 'alloc'. 166 // - free The deallocation function used by VG_(OSetGen_FreeNode)() and 167 // VG_(OSetGen_Destroy)(). 168 // 169 // If cmp is NULL, keyOff must be zero. This is checked. 170 // 171 // * Destroy: frees all nodes in the table, plus the memory used by 172 // the table itself. The passed-in function is called on each node first 173 // to allow the destruction of any attached resources; if NULL it is not 174 // called. 175 // 176 // * AllocNode: Allocate and zero memory for a node to go into the OSet. 177 // Uses the alloc function given to VG_(OSetGen_Create)() to allocated a 178 // node which is big enough for both an element and the OSet metadata. 179 // Not all elements in one OSet have to be the same size. 180 // 181 // Note that the element allocated will be at most word-aligned, which may 182 // be less aligned than the element type would normally be. 183 // 184 // * FreeNode: Deallocate a node allocated with OSetGen_AllocNode(). Using 185 // a deallocation function (such as VG_(free)()) directly will likely 186 // lead to assertions in Valgrind's allocator. 187 188 extern OSet* VG_(OSetGen_Create) ( PtrdiffT keyOff, OSetCmp_t cmp, 189 OSetAlloc_t alloc, HChar* cc, 190 OSetFree_t _free ); 191 extern void VG_(OSetGen_Destroy) ( OSet* os ); 192 extern void* VG_(OSetGen_AllocNode) ( OSet* os, SizeT elemSize ); 193 extern void VG_(OSetGen_FreeNode) ( OSet* os, void* elem ); 194 195 /*--------------------------------------------------------------------*/ 196 /*--- Operations on OSets (Gen) ---*/ 197 /*--------------------------------------------------------------------*/ 198 199 // In everything that follows, the parameter 'key' is always the *address* 200 // of the key, and 'elem' is *address* of the elem, as are the return values 201 // of the functions that return elems. 202 // 203 // * Size: The number of elements in the set. 204 // 205 // * Insert: Inserts a new element into the set. Note that 'elem' must 206 // have been allocated using VG_(OSetGen_AllocNode)(), otherwise you will 207 // get assertion failures about "bad magic". Duplicates are forbidden, 208 // and will also cause assertion failures. 209 // 210 // * Contains: Determines if any element in the OSet matches the key. 211 // 212 // * Lookup: Returns a pointer to the element matching the key, if there is 213 // one, otherwise returns NULL. 214 // 215 // * LookupWithCmp: Like Lookup, but you specify the comparison function, 216 // which overrides the OSet's normal one. 217 // 218 // * Remove: Removes the element matching the key, if there is one. Returns 219 // NULL if no element matches the key. 220 // 221 // * ResetIter: Each OSet has an iterator. This resets it to point to the 222 // first element in the OSet. 223 // 224 // * ResetIterAt: Like ResetIter, but instead of resetting the iterator to the 225 // smallest element, it resets the iterator to point to the smallest element 226 // in the set whose key is greater-than-or-equal to the given key. (In many 227 // cases this will be the element whose key equals that of the given key.) 228 // 229 // * Next: Returns a pointer to the element pointed to by the OSet's 230 // iterator, and advances the iterator by one; the elements are visited 231 // in order. Or, returns NULL if the iterator has reached the OSet's end. 232 // 233 // You can thus iterate in order through a set like this: 234 // 235 // VG_(OSetGen_ResetIter)(oset); 236 // while ( (elem = VG_(OSetGen_Next)(oset)) ) { 237 // ... do stuff with 'elem' ... 238 // } 239 // 240 // Note that iterators are cleared any time an element is inserted or 241 // removed from the OSet, to avoid possible mayhem caused by the iterator 242 // getting out of sync with the OSet's contents. "Cleared" means that 243 // they will return NULL if VG_(OSetGen_Next)() is called without an 244 // intervening call to VG_(OSetGen_ResetIter)(). 245 246 extern Word VG_(OSetGen_Size) ( const OSet* os ); 247 extern void VG_(OSetGen_Insert) ( OSet* os, void* elem ); 248 extern Bool VG_(OSetGen_Contains) ( const OSet* os, const void* key ); 249 extern void* VG_(OSetGen_Lookup) ( const OSet* os, const void* key ); 250 extern void* VG_(OSetGen_LookupWithCmp)( OSet* os, 251 const void* key, OSetCmp_t cmp ); 252 extern void* VG_(OSetGen_Remove) ( OSet* os, const void* key ); 253 extern void VG_(OSetGen_ResetIter) ( OSet* os ); 254 extern void VG_(OSetGen_ResetIterAt) ( OSet* os, const void* key ); 255 extern void* VG_(OSetGen_Next) ( OSet* os ); 256 257 258 #endif // __PUB_TOOL_OSET_H 259 260 /*--------------------------------------------------------------------*/ 261 /*--- end ---*/ 262 /*--------------------------------------------------------------------*/ 263
