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