sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 1 | |
| 2 | /*--------------------------------------------------------------------*/ |
| 3 | /*--- An expandable array implementation. m_xarray.h ---*/ |
| 4 | /*--------------------------------------------------------------------*/ |
| 5 | |
| 6 | /* |
| 7 | This file is part of Valgrind, a dynamic binary instrumentation |
| 8 | framework. |
| 9 | |
sewardj | b3a1e4b | 2015-08-21 11:32:26 +0000 | [diff] [blame] | 10 | Copyright (C) 2007-2015 OpenWorks LLP |
sewardj | d864eb9 | 2007-02-25 11:51:13 +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 | #include "pub_core_basics.h" |
| 32 | #include "pub_core_libcbase.h" |
| 33 | #include "pub_core_libcassert.h" |
| 34 | #include "pub_core_libcprint.h" |
| 35 | #include "pub_core_xarray.h" /* self */ |
| 36 | |
| 37 | |
sewardj | 7df1515 | 2007-02-25 15:04:40 +0000 | [diff] [blame] | 38 | /* See pub_tool_xarray.h for details of what this is all about. */ |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 39 | |
| 40 | struct _XArray { |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 41 | void* (*alloc_fn) ( const HChar*, SizeT ); /* alloc fn (nofail) */ |
| 42 | const HChar* cc; /* cost centre for alloc */ |
| 43 | void (*free_fn) ( void* ); /* free fn */ |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 44 | Int (*cmpFn) ( const void*, const void* ); /* cmp fn (may be NULL) */ |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 45 | Word elemSzB; /* element size in bytes */ |
| 46 | void* arr; /* pointer to elements */ |
| 47 | Word usedsizeE; /* # used elements in arr */ |
| 48 | Word totsizeE; /* max size of arr, in elements */ |
| 49 | Bool sorted; /* is it sorted? */ |
| 50 | }; |
| 51 | |
| 52 | |
florian | 54fe202 | 2012-10-27 23:07:42 +0000 | [diff] [blame] | 53 | XArray* VG_(newXA) ( void*(*alloc_fn)(const HChar*,SizeT), |
| 54 | const HChar* cc, |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 55 | void(*free_fn)(void*), |
| 56 | Word elemSzB ) |
| 57 | { |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 58 | XArray* xa; |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 59 | /* Implementation relies on Word being signed and (possibly) |
| 60 | on SizeT being unsigned. */ |
| 61 | vg_assert( sizeof(Word) == sizeof(void*) ); |
| 62 | vg_assert( ((Word)(-1)) < ((Word)(0)) ); |
| 63 | vg_assert( ((SizeT)(-1)) > ((SizeT)(0)) ); |
| 64 | /* check user-supplied info .. */ |
| 65 | vg_assert(alloc_fn); |
| 66 | vg_assert(free_fn); |
| 67 | vg_assert(elemSzB > 0); |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 68 | xa = alloc_fn( cc, sizeof(struct _XArray) ); |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 69 | xa->alloc_fn = alloc_fn; |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 70 | xa->cc = cc; |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 71 | xa->free_fn = free_fn; |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 72 | xa->cmpFn = NULL; |
| 73 | xa->elemSzB = elemSzB; |
| 74 | xa->usedsizeE = 0; |
| 75 | xa->totsizeE = 0; |
| 76 | xa->sorted = False; |
| 77 | xa->arr = NULL; |
| 78 | return xa; |
| 79 | } |
| 80 | |
florian | 2fa8a5f | 2014-10-18 20:56:13 +0000 | [diff] [blame] | 81 | XArray* VG_(cloneXA)( const HChar* cc, const XArray* xa ) |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 82 | { |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 83 | XArray* nyu; |
florian | 54fe202 | 2012-10-27 23:07:42 +0000 | [diff] [blame] | 84 | const HChar* nyu_cc; |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 85 | vg_assert(xa); |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 86 | vg_assert(xa->alloc_fn); |
| 87 | vg_assert(xa->free_fn); |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 88 | vg_assert(xa->elemSzB >= 1); |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 89 | nyu_cc = cc ? cc : xa->cc; |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 90 | nyu = xa->alloc_fn( nyu_cc, sizeof(struct _XArray) ); |
| 91 | |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 92 | /* Copy everything verbatim ... */ |
| 93 | *nyu = *xa; |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 94 | nyu->cc = nyu_cc; |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 95 | /* ... except we have to clone the contents-array */ |
| 96 | if (nyu->arr) { |
sewardj | 7db115a | 2008-08-22 23:16:06 +0000 | [diff] [blame] | 97 | /* Restrict the total size of the new array to its current |
| 98 | actual size. That means we don't waste space copying the |
| 99 | unused tail of the original. The tradeoff is that it |
| 100 | guarantees we will have to resize the child if even one more |
| 101 | element is later added to it, unfortunately. */ |
| 102 | nyu->totsizeE = nyu->usedsizeE; |
| 103 | /* and allocate .. */ |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 104 | nyu->arr = nyu->alloc_fn( nyu->cc, nyu->totsizeE * nyu->elemSzB ); |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 105 | VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB ); |
| 106 | } |
| 107 | /* We're done! */ |
| 108 | return nyu; |
| 109 | } |
| 110 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 111 | void VG_(deleteXA) ( XArray* xa ) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 112 | { |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 113 | vg_assert(xa); |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 114 | vg_assert(xa->free_fn); |
sewardj | e783ceb | 2007-08-28 05:19:16 +0000 | [diff] [blame] | 115 | if (xa->arr) |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 116 | xa->free_fn(xa->arr); |
| 117 | xa->free_fn(xa); |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 118 | } |
| 119 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 120 | void VG_(setCmpFnXA) ( XArray* xa, XACmpFn_t compar ) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 121 | { |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 122 | vg_assert(xa); |
| 123 | vg_assert(compar); |
| 124 | xa->cmpFn = compar; |
| 125 | xa->sorted = False; |
| 126 | } |
| 127 | |
florian | 2fa8a5f | 2014-10-18 20:56:13 +0000 | [diff] [blame] | 128 | inline void* VG_(indexXA) ( const XArray* xa, Word n ) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 129 | { |
philippe | b290d61 | 2015-05-11 21:02:00 +0000 | [diff] [blame] | 130 | vg_assert(xa); |
philippe | 44d4a9c | 2015-05-14 21:26:36 +0000 | [diff] [blame] | 131 | /* vg_assert(n >= 0); If n negative, the UWord conversion will make |
| 132 | it bigger than usedsizeE, which is verified to be non negative when |
| 133 | xa is modified. */ |
| 134 | vg_assert((UWord)n < (UWord)xa->usedsizeE); |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 135 | return ((char*)xa->arr) + n * xa->elemSzB; |
| 136 | } |
| 137 | |
philippe | d4dc5fc | 2015-05-01 16:46:38 +0000 | [diff] [blame] | 138 | void VG_(hintSizeXA) ( XArray* xa, Word n) |
| 139 | { |
| 140 | /* Currently, we support giving a size hint only just after the |
| 141 | call to VG_(newXA). So, we could instead have done |
| 142 | a function VG_(newXA_with_SizeHint). The separate VG_(hintSizeXA) |
| 143 | function is however chosen as we might one day accept to |
| 144 | give a size hint after having added elements. That could be useful |
| 145 | for reducing the size of an xarray to just the size currently needed |
| 146 | or to give a size hint when it is known that a lot more elements |
| 147 | are needed or when the final nr of elements is known. */ |
| 148 | vg_assert(xa); |
| 149 | vg_assert(xa->usedsizeE == 0); |
| 150 | vg_assert(xa->totsizeE == 0); |
| 151 | vg_assert(!xa->arr); |
| 152 | xa->arr = xa->alloc_fn(xa->cc, n * xa->elemSzB); |
| 153 | xa->totsizeE = n; |
| 154 | } |
| 155 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 156 | static inline void ensureSpaceXA ( XArray* xa ) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 157 | { |
sewardj | aa5a1ea | 2011-02-27 23:53:32 +0000 | [diff] [blame] | 158 | if (xa->usedsizeE == xa->totsizeE) { |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 159 | void* tmp; |
| 160 | Word newsz; |
| 161 | if (xa->totsizeE == 0) |
| 162 | vg_assert(!xa->arr); |
| 163 | if (xa->totsizeE > 0) |
| 164 | vg_assert(xa->arr); |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 165 | if (xa->totsizeE == 0) { |
| 166 | /* No point in having tiny (eg) 2-byte allocations for the |
| 167 | element array, since all allocs are rounded up to 8 anyway. |
| 168 | Hence increase the initial array size for tiny elements in |
| 169 | an attempt to avoid reallocations of size 2, 4, 8 if the |
| 170 | array does start to fill up. */ |
sewardj | aa5a1ea | 2011-02-27 23:53:32 +0000 | [diff] [blame] | 171 | if (xa->elemSzB == 1) newsz = 8; |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 172 | else if (xa->elemSzB == 2) newsz = 4; |
| 173 | else newsz = 2; |
| 174 | } else { |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 175 | newsz = 2 + (3 * xa->totsizeE) / 2; /* 2 * xa->totsizeE; */ |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 176 | } |
sewardj | 7db115a | 2008-08-22 23:16:06 +0000 | [diff] [blame] | 177 | if (0 && xa->totsizeE >= 10000) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 178 | VG_(printf)("addToXA: increasing from %ld to %ld\n", |
| 179 | xa->totsizeE, newsz); |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 180 | tmp = xa->alloc_fn(xa->cc, newsz * xa->elemSzB); |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 181 | if (xa->usedsizeE > 0) |
| 182 | VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB); |
| 183 | if (xa->arr) |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 184 | xa->free_fn(xa->arr); |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 185 | xa->arr = tmp; |
| 186 | xa->totsizeE = newsz; |
| 187 | } |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 188 | } |
| 189 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 190 | Word VG_(addToXA) ( XArray* xa, const void* elem ) |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 191 | { |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 192 | vg_assert(xa); |
| 193 | vg_assert(elem); |
| 194 | vg_assert(xa->totsizeE >= 0); |
| 195 | vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); |
| 196 | ensureSpaceXA( xa ); |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 197 | vg_assert(xa->usedsizeE < xa->totsizeE); |
| 198 | vg_assert(xa->arr); |
| 199 | VG_(memcpy)( ((UChar*)xa->arr) + xa->usedsizeE * xa->elemSzB, |
| 200 | elem, xa->elemSzB ); |
| 201 | xa->usedsizeE++; |
| 202 | xa->sorted = False; |
sewardj | 0f63148 | 2007-02-27 16:40:53 +0000 | [diff] [blame] | 203 | return xa->usedsizeE-1; |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 204 | } |
| 205 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 206 | Word VG_(addBytesToXA) ( XArray* xa, const void* bytesV, Word nbytes ) |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 207 | { |
sewardj | bee43c1 | 2008-08-19 08:57:49 +0000 | [diff] [blame] | 208 | Word r, i; |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 209 | vg_assert(xa); |
| 210 | vg_assert(xa->elemSzB == 1); |
| 211 | vg_assert(nbytes >= 0); |
| 212 | vg_assert(xa->totsizeE >= 0); |
| 213 | vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); |
| 214 | r = xa->usedsizeE; |
| 215 | for (i = 0; i < nbytes; i++) { |
| 216 | ensureSpaceXA( xa ); |
| 217 | vg_assert(xa->usedsizeE < xa->totsizeE); |
| 218 | vg_assert(xa->arr); |
florian | 3e79863 | 2012-11-24 19:41:54 +0000 | [diff] [blame] | 219 | * (((UChar*)xa->arr) + xa->usedsizeE) = ((const UChar*)bytesV)[i]; |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 220 | xa->usedsizeE++; |
| 221 | } |
| 222 | xa->sorted = False; |
| 223 | return r; |
| 224 | } |
| 225 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 226 | void VG_(sortXA) ( XArray* xa ) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 227 | { |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 228 | vg_assert(xa); |
| 229 | vg_assert(xa->cmpFn); |
njn | b4cfa2f | 2007-03-28 01:27:05 +0000 | [diff] [blame] | 230 | VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn ); |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 231 | xa->sorted = True; |
| 232 | } |
| 233 | |
florian | 2fa8a5f | 2014-10-18 20:56:13 +0000 | [diff] [blame] | 234 | Bool VG_(lookupXA_UNSAFE) ( const XArray* xa, const void* key, |
sewardj | e2253bf | 2009-07-24 08:11:39 +0000 | [diff] [blame] | 235 | /*OUT*/Word* first, /*OUT*/Word* last, |
florian | 6bd9dc1 | 2012-11-23 16:17:43 +0000 | [diff] [blame] | 236 | Int(*cmpFn)(const void*, const void*) ) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 237 | { |
| 238 | Word lo, mid, hi, cres; |
| 239 | void* midv; |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 240 | vg_assert(xa); |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 241 | lo = 0; |
| 242 | hi = xa->usedsizeE-1; |
| 243 | while (True) { |
| 244 | /* current unsearched space is from lo to hi, inclusive. */ |
| 245 | if (lo > hi) return False; /* not found */ |
| 246 | mid = (lo + hi) / 2; |
| 247 | midv = VG_(indexXA)( xa, mid ); |
sewardj | e2253bf | 2009-07-24 08:11:39 +0000 | [diff] [blame] | 248 | cres = cmpFn( key, midv ); |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 249 | if (cres < 0) { hi = mid-1; continue; } |
| 250 | if (cres > 0) { lo = mid+1; continue; } |
| 251 | /* Found it, at mid. See how far we can expand this. */ |
sewardj | e2253bf | 2009-07-24 08:11:39 +0000 | [diff] [blame] | 252 | vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0); |
| 253 | vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0); |
sewardj | ffce815 | 2011-06-24 10:09:41 +0000 | [diff] [blame] | 254 | if (first) { |
| 255 | *first = mid; |
| 256 | while (*first > 0 |
| 257 | && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) { |
| 258 | (*first)--; |
| 259 | } |
| 260 | } |
| 261 | if (last) { |
| 262 | *last = mid; |
| 263 | while (*last < xa->usedsizeE-1 |
| 264 | && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) { |
| 265 | (*last)++; |
| 266 | } |
| 267 | } |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 268 | return True; |
| 269 | } |
| 270 | } |
| 271 | |
florian | 2fa8a5f | 2014-10-18 20:56:13 +0000 | [diff] [blame] | 272 | Bool VG_(lookupXA) ( const XArray* xa, const void* key, |
sewardj | e2253bf | 2009-07-24 08:11:39 +0000 | [diff] [blame] | 273 | /*OUT*/Word* first, /*OUT*/Word* last ) |
| 274 | { |
sewardj | e2253bf | 2009-07-24 08:11:39 +0000 | [diff] [blame] | 275 | vg_assert(xa); |
| 276 | vg_assert(xa->cmpFn); |
| 277 | vg_assert(xa->sorted); |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 278 | return VG_(lookupXA_UNSAFE)(xa, key, first, last, xa->cmpFn); |
sewardj | e2253bf | 2009-07-24 08:11:39 +0000 | [diff] [blame] | 279 | } |
| 280 | |
florian | b4d7a1a | 2015-08-05 13:25:58 +0000 | [diff] [blame] | 281 | /* FIXME: This function should return an unsigned value because the number |
| 282 | of elements cannot be negative. Unfortunately, making the change causes |
| 283 | a lot of ripple. */ |
florian | 2fa8a5f | 2014-10-18 20:56:13 +0000 | [diff] [blame] | 284 | Word VG_(sizeXA) ( const XArray* xa ) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 285 | { |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 286 | vg_assert(xa); |
| 287 | return xa->usedsizeE; |
| 288 | } |
| 289 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 290 | void VG_(dropTailXA) ( XArray* xa, Word n ) |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 291 | { |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 292 | vg_assert(xa); |
| 293 | vg_assert(n >= 0); |
| 294 | vg_assert(n <= xa->usedsizeE); |
| 295 | xa->usedsizeE -= n; |
| 296 | } |
| 297 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 298 | void VG_(dropHeadXA) ( XArray* xa, Word n ) |
sewardj | e2253bf | 2009-07-24 08:11:39 +0000 | [diff] [blame] | 299 | { |
sewardj | e2253bf | 2009-07-24 08:11:39 +0000 | [diff] [blame] | 300 | vg_assert(xa); |
| 301 | vg_assert(n >= 0); |
| 302 | vg_assert(n <= xa->usedsizeE); |
| 303 | if (n == 0) { |
| 304 | return; |
| 305 | } |
| 306 | if (n == xa->usedsizeE) { |
| 307 | xa->usedsizeE = 0; |
| 308 | return; |
| 309 | } |
| 310 | vg_assert(n > 0); |
| 311 | vg_assert(xa->usedsizeE - n > 0); |
| 312 | VG_(memcpy)( (char*)xa->arr, |
| 313 | ((char*)xa->arr) + n * xa->elemSzB, |
| 314 | (xa->usedsizeE - n) * xa->elemSzB ); |
| 315 | xa->usedsizeE -= n; |
| 316 | } |
| 317 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 318 | void VG_(removeIndexXA)( XArray* xa, Word n ) |
sewardj | 291849f | 2012-04-20 23:58:55 +0000 | [diff] [blame] | 319 | { |
sewardj | 291849f | 2012-04-20 23:58:55 +0000 | [diff] [blame] | 320 | vg_assert(xa); |
| 321 | vg_assert(n >= 0); |
| 322 | vg_assert(n < xa->usedsizeE); |
| 323 | if (n+1 < xa->usedsizeE) { |
| 324 | VG_(memmove)( ((char*)xa->arr) + (n+0) * xa->elemSzB, |
| 325 | ((char*)xa->arr) + (n+1) * xa->elemSzB, |
| 326 | (xa->usedsizeE - n - 1) * xa->elemSzB ); |
| 327 | } |
| 328 | xa->usedsizeE--; |
| 329 | } |
| 330 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 331 | void VG_(insertIndexXA)( XArray* xa, Word n, const void* elem ) |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 332 | { |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 333 | vg_assert(xa); |
| 334 | vg_assert(n >= 0); |
| 335 | vg_assert(n <= xa->usedsizeE); |
| 336 | vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); |
| 337 | ensureSpaceXA( xa ); |
| 338 | vg_assert(xa->usedsizeE < xa->totsizeE); |
| 339 | vg_assert(xa->arr); |
| 340 | if (n < xa->usedsizeE) { |
| 341 | VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB, |
| 342 | ((char*)xa->arr) + (n+0) * xa->elemSzB, |
| 343 | (xa->usedsizeE - n) * xa->elemSzB ); |
| 344 | } |
| 345 | VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB, |
| 346 | elem, xa->elemSzB ); |
| 347 | xa->usedsizeE++; |
| 348 | xa->sorted = False; |
| 349 | } |
| 350 | |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 351 | void VG_(getContentsXA_UNSAFE)( XArray* xa, |
sewardj | 8f8fa17 | 2010-05-05 09:23:41 +0000 | [diff] [blame] | 352 | /*OUT*/void** ctsP, |
| 353 | /*OUT*/Word* usedP ) |
| 354 | { |
sewardj | 8f8fa17 | 2010-05-05 09:23:41 +0000 | [diff] [blame] | 355 | vg_assert(xa); |
| 356 | *ctsP = (void*)xa->arr; |
| 357 | *usedP = xa->usedsizeE; |
| 358 | } |
| 359 | |
sewardj | 588adef | 2009-08-15 22:41:51 +0000 | [diff] [blame] | 360 | /* --------- Printeffery --------- */ |
| 361 | |
| 362 | static void add_char_to_XA ( HChar c, void* opaque ) |
| 363 | { |
| 364 | XArray* dst = (XArray*)opaque; |
| 365 | (void) VG_(addBytesToXA)( dst, &c, 1 ); |
| 366 | } |
| 367 | |
| 368 | void VG_(xaprintf)( XArray* dst, const HChar* format, ... ) |
| 369 | { |
| 370 | va_list vargs; |
| 371 | va_start(vargs, format); |
| 372 | VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs ); |
| 373 | va_end(vargs); |
| 374 | } |
| 375 | |
sewardj | d864eb9 | 2007-02-25 11:51:13 +0000 | [diff] [blame] | 376 | |
| 377 | /*--------------------------------------------------------------------*/ |
| 378 | /*--- end m_xarray.c ---*/ |
| 379 | /*--------------------------------------------------------------------*/ |