1 2 /*--------------------------------------------------------------------*/ 3 /*--- An expandable array implementation. pub_tool_xarray.h ---*/ 4 /*--------------------------------------------------------------------*/ 5 6 /* 7 This file is part of Valgrind, a dynamic binary instrumentation 8 framework. 9 10 Copyright (C) 2007-2011 OpenWorks LLP 11 info (at) open-works.co.uk 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_XARRAY_H 32 #define __PUB_TOOL_XARRAY_H 33 34 //-------------------------------------------------------------------- 35 // PURPOSE: Provides a simple but useful structure, which is an array 36 // in which elements can be added at the end. The array is expanded 37 // as needed by multiplying its size by a constant factor (usually 2). 38 // This gives amortised O(1) insertion cost, and, following sorting, 39 // the usual O(log N) binary search cost. Arbitrary element sizes 40 // are allowed; the comparison function for sort/lookup can be changed 41 // at any time, and duplicates (modulo the comparison function) are 42 // allowed. 43 //-------------------------------------------------------------------- 44 45 46 /* It's an abstract type. Bwaha. */ 47 typedef struct _XArray XArray; 48 49 /* Create new XArray, using given allocation and free function, and 50 for elements of the specified size. Alloc fn must not fail (that 51 is, if it returns it must have succeeded.) */ 52 extern XArray* VG_(newXA) ( void*(*alloc_fn)(HChar*,SizeT), 53 HChar* cc, 54 void(*free_fn)(void*), 55 Word elemSzB ); 56 57 /* Free all memory associated with an XArray. */ 58 extern void VG_(deleteXA) ( XArray* ); 59 60 /* Set the comparison function for this XArray. This clears an 61 internal 'array is sorted' flag, which means you must call sortXA 62 before making further queries with lookupXA. */ 63 extern void VG_(setCmpFnXA) ( XArray*, Int (*compar)(void*,void*) ); 64 65 /* Add an element to an XArray. Element is copied into the XArray. 66 Index at which it was added is returned. Note this will be 67 invalidated if the array is later sortXA'd. */ 68 extern Word VG_(addToXA) ( XArray*, void* elem ); 69 70 /* Add a sequence of bytes to an XArray of bytes. Asserts if nbytes 71 is negative or the array's element size is not 1. Returns the 72 index at which the first byte was added. */ 73 extern Word VG_(addBytesToXA) ( XArray* xao, void* bytesV, Word nbytes ); 74 75 /* Sort an XArray using its comparison function, if set; else bomb. 76 Probably not a stable sort w.r.t. equal elements module cmpFn. */ 77 extern void VG_(sortXA) ( XArray* ); 78 79 /* Lookup (by binary search) 'key' in the array. Set *first to be the 80 index of the first, and *last to be the index of the last matching 81 value found. If any values are found, return True, else return 82 False, and don't change *first or *last. first and/or last may be 83 NULL. Bomb if the array is not sorted. */ 84 extern Bool VG_(lookupXA) ( XArray*, void* key, 85 /*OUT*/Word* first, /*OUT*/Word* last ); 86 87 /* A version of VG_(lookupXA) in which you can specify your own 88 comparison function. This is unsafe in the sense that if the array 89 is not totally ordered as defined by your comparison function, then 90 this function may loop indefinitely, so it is up to you to ensure 91 that the array is suitably ordered. This is in comparison to 92 VG_(lookupXA), which refuses to do anything (asserts) unless the 93 array has first been sorted using the same comparison function as 94 is being used for the lookup. */ 95 extern Bool VG_(lookupXA_UNSAFE) ( XArray* xao, void* key, 96 /*OUT*/Word* first, /*OUT*/Word* last, 97 Int(*cmpFn)(void*,void*) ); 98 99 /* How elements are there in this XArray now? */ 100 extern Word VG_(sizeXA) ( XArray* ); 101 102 /* Index into the XArray. Checks bounds and bombs if the index is 103 invalid. What this returns is the address of the specified element 104 in the array, not (of course) the element itself. Note that the 105 element may get moved by subsequent addToXAs/sortXAs, so you should 106 copy it out immediately and not regard its address as unchanging. 107 Note also that indexXA will of course not return NULL if it 108 succeeds. */ 109 extern void* VG_(indexXA) ( XArray*, Word ); 110 111 /* Drop the last n elements of an XArray. Bombs if there are less 112 than n elements in the array. This is an O(1) operation. */ 113 extern void VG_(dropTailXA) ( XArray*, Word ); 114 115 /* Drop the first n elements of an XArray. Bombs if there are less 116 than n elements in the array. This is an O(N) operation, where N 117 is the number of elements remaining in the XArray. */ 118 extern void VG_(dropHeadXA) ( XArray*, Word ); 119 120 /* Make a new, completely independent copy of the given XArray, using 121 the existing allocation function to allocate the new space. 122 Returns NULL if the allocation function didn't manage to allocate 123 space (but did return NULL rather than merely abort.) Space for 124 the clone (and all additions to it) is billed to 'cc' unless that 125 is NULL, in which case the parent's cost-center is used. */ 126 extern XArray* VG_(cloneXA)( HChar* cc, XArray* xa ); 127 128 /* Get the raw array and size so callers can index it really fast. 129 This is dangerous in the sense that there's no range or 130 anything-else checking. It's also dangerous in that if 131 VG_(addToXA) is used, the contents may be re-located without 132 warning, hence making the contents address returned here 133 invalid. */ 134 extern void VG_(getContentsXA_UNSAFE)( XArray* sr, 135 /*OUT*/void** ctsP, 136 /*OUT*/Word* usedP ); 137 138 /* Convenience function: printf into an XArray of HChar, adding stuff 139 at the end. This is very convenient for concocting arbitrary 140 length printf output in an XArray. Note that the resulting string 141 is NOT zero-terminated. */ 142 extern void VG_(xaprintf)( XArray* dst, const HChar* format, ... ) 143 PRINTF_CHECK(2, 3); 144 145 #endif // __PUB_TOOL_XARRAY_H 146 147 /*--------------------------------------------------------------------*/ 148 /*--- end pub_tool_xarray.h ---*/ 149 /*--------------------------------------------------------------------*/ 150
