sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 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 | |
sewardj | 0f157dd | 2013-10-18 14:27:36 +0000 | [diff] [blame] | 10 | Copyright (C) 2007-2013 OpenWorks LLP |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 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 | |
florian | 535fb1b | 2013-09-15 13:54:34 +0000 | [diff] [blame] | 34 | #include "pub_tool_basics.h" // Word |
| 35 | |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 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. */ |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 49 | typedef struct _XArray XArray; |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 50 | |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 51 | typedef Int (*XACmpFn_t)(const void *, const void *); |
| 52 | |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 53 | /* Create new XArray, using given allocation and free function, and |
| 54 | for elements of the specified size. Alloc fn must not fail (that |
| 55 | is, if it returns it must have succeeded.) */ |
florian | 54fe202 | 2012-10-27 23:07:42 +0000 | [diff] [blame] | 56 | extern XArray* VG_(newXA) ( void*(*alloc_fn)(const HChar*,SizeT), |
| 57 | const HChar* cc, |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 58 | void(*free_fn)(void*), |
| 59 | Word elemSzB ); |
| 60 | |
| 61 | /* Free all memory associated with an XArray. */ |
| 62 | extern void VG_(deleteXA) ( XArray* ); |
| 63 | |
| 64 | /* Set the comparison function for this XArray. This clears an |
| 65 | internal 'array is sorted' flag, which means you must call sortXA |
| 66 | before making further queries with lookupXA. */ |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 67 | extern void VG_(setCmpFnXA) ( XArray*, XACmpFn_t); |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 68 | |
sewardj | 0f63148 | 2007-02-27 16:40:53 +0000 | [diff] [blame] | 69 | /* Add an element to an XArray. Element is copied into the XArray. |
| 70 | Index at which it was added is returned. Note this will be |
| 71 | invalidated if the array is later sortXA'd. */ |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 72 | extern Word VG_(addToXA) ( XArray*, const void* elem ); |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 73 | |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 74 | /* Add a sequence of bytes to an XArray of bytes. Asserts if nbytes |
| 75 | is negative or the array's element size is not 1. Returns the |
| 76 | index at which the first byte was added. */ |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 77 | extern Word VG_(addBytesToXA) ( XArray* xao, const void* bytesV, Word nbytes ); |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 78 | |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 79 | /* Sort an XArray using its comparison function, if set; else bomb. |
| 80 | Probably not a stable sort w.r.t. equal elements module cmpFn. */ |
| 81 | extern void VG_(sortXA) ( XArray* ); |
| 82 | |
| 83 | /* Lookup (by binary search) 'key' in the array. Set *first to be the |
| 84 | index of the first, and *last to be the index of the last matching |
| 85 | value found. If any values are found, return True, else return |
sewardj | ffce815 | 2011-06-24 10:09:41 +0000 | [diff] [blame] | 86 | False, and don't change *first or *last. first and/or last may be |
| 87 | NULL. Bomb if the array is not sorted. */ |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 88 | extern Bool VG_(lookupXA) ( XArray*, const void* key, |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 89 | /*OUT*/Word* first, /*OUT*/Word* last ); |
| 90 | |
sewardj | daa5da5 | 2009-07-24 08:42:07 +0000 | [diff] [blame] | 91 | /* A version of VG_(lookupXA) in which you can specify your own |
| 92 | comparison function. This is unsafe in the sense that if the array |
| 93 | is not totally ordered as defined by your comparison function, then |
| 94 | this function may loop indefinitely, so it is up to you to ensure |
| 95 | that the array is suitably ordered. This is in comparison to |
| 96 | VG_(lookupXA), which refuses to do anything (asserts) unless the |
| 97 | array has first been sorted using the same comparison function as |
| 98 | is being used for the lookup. */ |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 99 | extern Bool VG_(lookupXA_UNSAFE) ( XArray* xao, const void* key, |
sewardj | daa5da5 | 2009-07-24 08:42:07 +0000 | [diff] [blame] | 100 | /*OUT*/Word* first, /*OUT*/Word* last, |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 101 | XACmpFn_t cmpFn ); |
sewardj | daa5da5 | 2009-07-24 08:42:07 +0000 | [diff] [blame] | 102 | |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 103 | /* How elements are there in this XArray now? */ |
| 104 | extern Word VG_(sizeXA) ( XArray* ); |
| 105 | |
| 106 | /* Index into the XArray. Checks bounds and bombs if the index is |
| 107 | invalid. What this returns is the address of the specified element |
| 108 | in the array, not (of course) the element itself. Note that the |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 109 | element may get moved by subsequent calls to addToXA / sortXA / |
| 110 | insertIndexXA, so you should copy it out immediately and not regard |
| 111 | its address as unchanging. Note also that indexXA will of course |
| 112 | not return NULL if it succeeds. */ |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 113 | extern void* VG_(indexXA) ( XArray*, Word ); |
| 114 | |
| 115 | /* Drop the last n elements of an XArray. Bombs if there are less |
sewardj | daa5da5 | 2009-07-24 08:42:07 +0000 | [diff] [blame] | 116 | than n elements in the array. This is an O(1) operation. */ |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 117 | extern void VG_(dropTailXA) ( XArray*, Word ); |
| 118 | |
sewardj | daa5da5 | 2009-07-24 08:42:07 +0000 | [diff] [blame] | 119 | /* Drop the first n elements of an XArray. Bombs if there are less |
| 120 | than n elements in the array. This is an O(N) operation, where N |
| 121 | is the number of elements remaining in the XArray. */ |
| 122 | extern void VG_(dropHeadXA) ( XArray*, Word ); |
| 123 | |
sewardj | 291849f | 2012-04-20 23:58:55 +0000 | [diff] [blame] | 124 | /* Remove the specified element of an XArray, and slide all elements |
| 125 | beyond it back one place. This is an O(N) operation, where N is |
| 126 | the number of elements after the specified element, in the |
| 127 | array. */ |
| 128 | extern void VG_(removeIndexXA)( XArray*, Word ); |
| 129 | |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 130 | /* Insert an element into an XArray at the given index. The existing |
| 131 | element at the index and all above it are slid upwards one slot so |
| 132 | as to make space. Element is copied into the XArray. This is an |
| 133 | O(N) operation, when N is the number of elements after the |
| 134 | specified element, in the array. */ |
| 135 | extern void VG_(insertIndexXA)( XArray*, Word, const void* elem ); |
| 136 | |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 137 | /* Make a new, completely independent copy of the given XArray, using |
| 138 | the existing allocation function to allocate the new space. |
| 139 | Returns NULL if the allocation function didn't manage to allocate |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 140 | space (but did return NULL rather than merely abort.) Space for |
| 141 | the clone (and all additions to it) is billed to 'cc' unless that |
| 142 | is NULL, in which case the parent's cost-center is used. */ |
florian | 54fe202 | 2012-10-27 23:07:42 +0000 | [diff] [blame] | 143 | extern XArray* VG_(cloneXA)( const HChar* cc, XArray* xa ); |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 144 | |
sewardj | 8f8fa17 | 2010-05-05 09:23:41 +0000 | [diff] [blame] | 145 | /* Get the raw array and size so callers can index it really fast. |
| 146 | This is dangerous in the sense that there's no range or |
| 147 | anything-else checking. It's also dangerous in that if |
| 148 | VG_(addToXA) is used, the contents may be re-located without |
| 149 | warning, hence making the contents address returned here |
| 150 | invalid. */ |
| 151 | extern void VG_(getContentsXA_UNSAFE)( XArray* sr, |
| 152 | /*OUT*/void** ctsP, |
| 153 | /*OUT*/Word* usedP ); |
| 154 | |
sewardj | 588adef | 2009-08-15 22:41:51 +0000 | [diff] [blame] | 155 | /* Convenience function: printf into an XArray of HChar, adding stuff |
| 156 | at the end. This is very convenient for concocting arbitrary |
| 157 | length printf output in an XArray. Note that the resulting string |
bart | b3af9cf | 2011-10-06 19:08:37 +0000 | [diff] [blame] | 158 | is NOT zero-terminated. */ |
sewardj | 588adef | 2009-08-15 22:41:51 +0000 | [diff] [blame] | 159 | extern void VG_(xaprintf)( XArray* dst, const HChar* format, ... ) |
| 160 | PRINTF_CHECK(2, 3); |
| 161 | |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 162 | #endif // __PUB_TOOL_XARRAY_H |
| 163 | |
| 164 | /*--------------------------------------------------------------------*/ |
| 165 | /*--- end pub_tool_xarray.h ---*/ |
| 166 | /*--------------------------------------------------------------------*/ |