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-2017 Nicholas Nethercote 11 njn@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 #include "pub_tool_basics.h" // Word 35 36 // This module implements an ordered set, a data structure with fast 37 // (eg. amortised log(n) or better) insertion, lookup and deletion of 38 // elements. It does not allow duplicates, and will assert if you insert a 39 // duplicate to an OSet. 40 // 41 // It has two interfaces. 42 // 43 // - The "OSetWord_" interface provides an easier-to-use interface for the 44 // case where you just want to store UWord-sized values. The user 45 // provides the allocation and deallocation functions, and possibly a 46 // comparison function. 47 // 48 // - The "OSetGen_" interface provides a totally generic interface, which 49 // allows any kind of structure to be put into the set. The user provides 50 // the allocation and deallocation functions. Also, each element has a 51 // key, which the lookup is done with. The key may be the whole element 52 // (eg. in an OSet of integers, each integer serves both as an element and 53 // a key), or it may be only part of it (eg. if the key is a single field 54 // in a struct). The user can provide a function that compares an element 55 // with a key; this is very flexible, and with the right comparison 56 // function even a (non-overlapping) interval list can be created. But 57 // the cost of calling a function for every comparison can be high during 58 // lookup. If no comparison function is provided, we assume that keys are 59 // unsigned words, and that the key is the first word in each 60 // element. This fast comparison is suitable for an OSet containing 61 // structs where the first element is an Addr, for example. 62 // Do not assume fast comparison works properly with signed words. 63 // A.o. iterating over the values will not return them in the correct 64 // order. 65 // 66 // Each OSet interface also has an iterator, which makes it simple to 67 // traverse all the nodes in order. Note that the iterator maintains state 68 // and so is non-reentrant. 69 // 70 // Note that once you insert an element into an OSet, if you modify any part 71 // of it looked at by your cmp() function, this may cause incorrect 72 // behaviour as the sorted order maintained will be wrong. 73 74 /*--------------------------------------------------------------------*/ 75 /*--- Types ---*/ 76 /*--------------------------------------------------------------------*/ 77 78 typedef struct _OSet OSet; 79 80 // - OSetCmp_t: returns -1, 0 or 1 if key is <, == or > elem. 81 typedef Word (*OSetCmp_t) ( const void* key, const void* elem ); 82 83 /*--------------------------------------------------------------------*/ 84 /*--- Creating and destroying OSets (UWord) ---*/ 85 /*--------------------------------------------------------------------*/ 86 87 // * Create: allocates and initialises the OSet. Never returns NULL. 88 // Parameters: 89 // - alloc_fn The allocation function used internally for allocating the 90 // OSet and all its nodes. It must not return NULL (that is, 91 // if it returns it must have succeeded.) 92 // - cc Cost centre string used by 'alloc'. 93 // - free_fn The deallocation function used internally for freeing nodes 94 // called by VG_(OSetWord_Destroy)(). 95 // 96 // * Destroy: frees all nodes in the table, plus the memory used by 97 // the table itself. The passed-in function is called on each node first 98 // to allow the destruction of any attached resources; if NULL it is not 99 // called. 100 101 extern OSet* VG_(OSetWord_Create) ( Alloc_Fn_t alloc_fn, const HChar* cc, 102 Free_Fn_t free_fn ); 103 extern void VG_(OSetWord_Destroy) ( OSet* os ); 104 105 /*--------------------------------------------------------------------*/ 106 /*--- Operations on OSets (UWord) ---*/ 107 /*--------------------------------------------------------------------*/ 108 109 // In everything that follows, the parameter 'key' is always the *address* 110 // of the key, and 'elem' is *address* of the elem, as are the return values 111 // of the functions that return elems. 112 // 113 // * Size: The number of elements in the set. 114 // 115 // * Contains: Determines if the value is in the set. 116 // 117 // * Insert: Inserts a new element into the set. Duplicates are forbidden, 118 // and will cause assertion failures. 119 // 120 // * Remove: Removes the value from the set, if present. Returns a Bool 121 // indicating if the value was removed. 122 // 123 // * ResetIter: Each OSet has an iterator. This resets it to point to the 124 // first element in the OSet. 125 // 126 // * Next: Copies the next value according to the OSet's iterator into &val, 127 // advances the iterator by one, and returns True; the elements are 128 // visited in increasing order of unsigned words (UWord). Or, returns 129 // False if the iterator has reached the set's end. 130 // 131 // You can thus iterate in order through a set like this: 132 // 133 // Word val; 134 // VG_(OSetWord_ResetIter)(oset); 135 // while ( VG_(OSetWord_Next)(oset, &val) ) { 136 // ... do stuff with 'val' ... 137 // } 138 // 139 // Note that iterators are cleared any time an element is inserted or 140 // removed from the OSet, to avoid possible mayhem caused by the iterator 141 // getting out of sync with the OSet's contents. "Cleared" means that 142 // they will return False if VG_(OSetWord_Next)() is called without an 143 // intervening call to VG_(OSetWord_ResetIter)(). 144 145 extern Word VG_(OSetWord_Size) ( const OSet* os ); 146 extern void VG_(OSetWord_Insert) ( OSet* os, UWord val ); 147 extern Bool VG_(OSetWord_Contains) ( const OSet* os, UWord val ); 148 extern Bool VG_(OSetWord_Remove) ( OSet* os, UWord val ); 149 extern void VG_(OSetWord_ResetIter) ( OSet* os ); 150 extern Bool VG_(OSetWord_Next) ( OSet* os, /*OUT*/UWord* val ); 151 152 153 /*--------------------------------------------------------------------*/ 154 /*--- Creating and destroying OSets and OSet members (Gen) ---*/ 155 /*--------------------------------------------------------------------*/ 156 157 // * Create: allocates and initialises the OSet. Never returns NULL. 158 // Parameters: 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_fn The allocation function used for allocating the OSet itself; 163 // It must not return NULL (that is, if it returns it must 164 // have succeeded.) 165 // If a pool allocator is used, it's called to allocate pool of 166 // nodes. 167 // If no pool allocator is used, it's called for each 168 // invocation of VG_(OSetGen_AllocNode)(). 169 // - cc Cost centre string used by 'alloc'. 170 // - free_fn If no pool allocator is used, this is the deallocation 171 // function used by VG_(OSetGen_FreeNode)() and 172 // VG_(OSetGen_Destroy)(). 173 // If a pool allocator is used, the memory used by the nodes is 174 // deallocated when the pool is deleted. 175 // (for more details about pool allocators, see pub_tool_poolalloc.h). 176 // 177 // 178 // If cmp is NULL, keyOff must be zero. This is checked. 179 // 180 // * Destroy: frees all nodes in the table, plus the memory used by 181 // the table itself. The passed-in function is called on each node first 182 // to allow the destruction of any attached resources; if NULL it is not 183 // called. 184 // 185 // * AllocNode: Allocate and zero memory for a node to go into the OSet. 186 // If a pool allocator is used, it uses the pool allocator to allocate a node. 187 // Otherwise, uses the alloc function given to VG_(OSetGen_Create)() to 188 // allocate a node which is big enough for both an element and the OSet 189 // metadata. 190 // Not all elements in one OSet have to be the same size. 191 // However, if a pool allocator is used, elements will all have a size equal 192 // to the max user data size given at creation + the node meta data size. 193 // 194 // Note that the element allocated will be at most word-aligned, which may 195 // be less aligned than the element type would normally be. 196 // 197 // * FreeNode: Deallocate a node allocated with OSetGen_AllocNode(). Using 198 // a deallocation function (such as VG_(free)()) directly will likely 199 // lead to assertions in Valgrind's allocator. 200 201 extern OSet* VG_(OSetGen_Create) ( PtrdiffT keyOff, OSetCmp_t cmp, 202 Alloc_Fn_t alloc_fn, const HChar* cc, 203 Free_Fn_t free_fn); 204 205 206 extern OSet* VG_(OSetGen_Create_With_Pool) ( PtrdiffT keyOff, OSetCmp_t cmp, 207 Alloc_Fn_t alloc_fn, 208 const HChar* cc, 209 Free_Fn_t free_fn, 210 SizeT poolSize, 211 SizeT maxEltSize); 212 // Same as VG_(OSetGen_Create) but created OSet will use a pool allocator to 213 // allocate the nodes. 214 // The node size is the sum of a fixed small meta data size needed for OSet 215 // + the size of the user data element. 216 // The maximum size for the user data element is specified by maxEltSize. 217 // (if poolSize is 0, maxEltSize is not relevant for the OSet). 218 // It is interesting to use a pool allocator when an OSet has many elements, 219 // and these elements have a small fixed size, or have a variable size, but 220 // always <= than a (small) maximum value. 221 // In such a case, allocating the nodes in pools reduces significantly 222 // the memory overhead needed by each node. 223 // When a node is freed (i.e. OSetGen_Freenode is called), the node is 224 // put back in the pool allocator free list (for sub-sequent re-use by 225 // OSetGen_AllocNode). Note that the pool memory is only released when 226 // the pool is destroyed : calls to VG_(OSetGen_Free) do not cause 227 // any calls to OSetFree_t _free function. 228 // If there are several OSet managing similar such elements, it might be 229 // interesting to use a shared pool for these OSet. 230 // To have multiple OSets sharing a pool allocator, create the first OSet 231 // with VG_(OSetGen_Create_With_Pool). Create subsequent OSet with 232 // VG_(OSetGen_EmptyClone). 233 234 extern void VG_(OSetGen_Destroy) ( OSet* os ); 235 extern void* VG_(OSetGen_AllocNode) ( const OSet* os, SizeT elemSize ); 236 extern void VG_(OSetGen_FreeNode) ( const OSet* os, void* elem ); 237 238 extern OSet* VG_(OSetGen_EmptyClone) (const OSet* os); 239 // Creates a new empty OSet. 240 // The new OSet will have the same characteristics as os. 241 // If os uses a pool allocator, this pool allocator will be shared with 242 // the new OSet. A shared pool allocator is only deleted (and its memory is 243 // released) when the last OSet using the shared pool is destroyed. 244 245 /*-------------------------------------------------------------------*/ 246 /*--- Operations on OSets (Gen) ---*/ 247 /*--------------------------------------------------------------------*/ 248 249 // In everything that follows, the parameter 'key' is always the *address* 250 // of the key, and 'elem' is *address* of the elem, as are the return values 251 // of the functions that return elems. 252 // 253 // * Size: The number of elements in the set. 254 // 255 // * Insert: Inserts a new element into the set. Note that 'elem' must 256 // have been allocated using VG_(OSetGen_AllocNode)(), otherwise you will 257 // get assertion failures about "bad magic". Duplicates are forbidden, 258 // and will also cause assertion failures. 259 // 260 // * Contains: Determines if any element in the OSet matches the key. 261 // 262 // * Lookup: Returns a pointer to the element matching the key, if there is 263 // one, otherwise returns NULL. 264 // 265 // * LookupWithCmp: Like Lookup, but you specify the comparison function, 266 // which overrides the OSet's normal one. 267 // 268 // * Remove: Removes the element matching the key, if there is one. Returns 269 // NULL if no element matches the key. 270 // 271 // * ResetIter: Each OSet has an iterator. This resets it to point to the 272 // first element in the OSet. 273 // 274 // * ResetIterAt: Like ResetIter, but instead of resetting the iterator to the 275 // smallest element, it resets the iterator to point to the smallest element 276 // in the set whose key is greater-than-or-equal to the given key. (In many 277 // cases this will be the element whose key equals that of the given key.) 278 // 279 // * Next: Returns a pointer to the element pointed to by the OSet's 280 // iterator, and advances the iterator by one; the elements are visited 281 // in order. Or, returns NULL if the iterator has reached the OSet's end. 282 // 283 // You can thus iterate in order through a set like this: 284 // 285 // VG_(OSetGen_ResetIter)(oset); 286 // while ( (elem = VG_(OSetGen_Next)(oset)) ) { 287 // ... do stuff with 'elem' ... 288 // } 289 // 290 // Note that iterators are cleared any time an element is inserted or 291 // removed from the OSet, to avoid possible mayhem caused by the iterator 292 // getting out of sync with the OSet's contents. "Cleared" means that 293 // they will return NULL if VG_(OSetGen_Next)() is called without an 294 // intervening call to VG_(OSetGen_ResetIter)(). 295 296 extern UInt VG_(OSetGen_Size) ( const OSet* os ); 297 extern void VG_(OSetGen_Insert) ( OSet* os, void* elem ); 298 extern Bool VG_(OSetGen_Contains) ( const OSet* os, const void* key ); 299 extern void* VG_(OSetGen_Lookup) ( const OSet* os, const void* key ); 300 extern void* VG_(OSetGen_LookupWithCmp)( OSet* os, 301 const void* key, OSetCmp_t cmp ); 302 extern void* VG_(OSetGen_Remove) ( OSet* os, const void* key ); 303 extern void VG_(OSetGen_ResetIter) ( OSet* os ); 304 extern void VG_(OSetGen_ResetIterAt) ( OSet* os, const void* key ); 305 extern void* VG_(OSetGen_Next) ( OSet* os ); 306 307 308 #endif // __PUB_TOOL_OSET_H 309 310 /*--------------------------------------------------------------------*/ 311 /*--- end ---*/ 312 /*--------------------------------------------------------------------*/ 313