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 10 Copyright (C) 2007-2013 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 #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 38 /* See pub_tool_xarray.h for details of what this is all about. */ 39 40 struct _XArray { 41 void* (*alloc) ( const HChar*, SizeT ); /* alloc fn (nofail) */ 42 const HChar* cc; /* cost centre for alloc */ 43 void (*free) ( void* ); /* free fn */ 44 Int (*cmpFn) ( const void*, const void* ); /* cmp fn (may be NULL) */ 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 53 XArray* VG_(newXA) ( void*(*alloc_fn)(const HChar*,SizeT), 54 const HChar* cc, 55 void(*free_fn)(void*), 56 Word elemSzB ) 57 { 58 struct _XArray* xa; 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); 68 xa = alloc_fn( cc, sizeof(struct _XArray) ); 69 vg_assert(xa); 70 xa->alloc = alloc_fn; 71 xa->cc = cc; 72 xa->free = free_fn; 73 xa->cmpFn = NULL; 74 xa->elemSzB = elemSzB; 75 xa->usedsizeE = 0; 76 xa->totsizeE = 0; 77 xa->sorted = False; 78 xa->arr = NULL; 79 return xa; 80 } 81 82 XArray* VG_(cloneXA)( const HChar* cc, XArray* xao ) 83 { 84 struct _XArray* xa = (struct _XArray*)xao; 85 struct _XArray* nyu; 86 const HChar* nyu_cc; 87 vg_assert(xa); 88 vg_assert(xa->alloc); 89 vg_assert(xa->free); 90 vg_assert(xa->elemSzB >= 1); 91 nyu_cc = cc ? cc : xa->cc; 92 nyu = xa->alloc( nyu_cc, sizeof(struct _XArray) ); 93 if (!nyu) 94 return NULL; 95 /* Copy everything verbatim ... */ 96 *nyu = *xa; 97 nyu->cc = nyu_cc; 98 /* ... except we have to clone the contents-array */ 99 if (nyu->arr) { 100 /* Restrict the total size of the new array to its current 101 actual size. That means we don't waste space copying the 102 unused tail of the original. The tradeoff is that it 103 guarantees we will have to resize the child if even one more 104 element is later added to it, unfortunately. */ 105 nyu->totsizeE = nyu->usedsizeE; 106 /* and allocate .. */ 107 nyu->arr = nyu->alloc( nyu->cc, nyu->totsizeE * nyu->elemSzB ); 108 if (!nyu->arr) { 109 nyu->free(nyu); 110 return NULL; 111 } 112 VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB ); 113 } 114 /* We're done! */ 115 return nyu; 116 } 117 118 void VG_(deleteXA) ( XArray* xao ) 119 { 120 struct _XArray* xa = (struct _XArray*)xao; 121 vg_assert(xa); 122 vg_assert(xa->free); 123 if (xa->arr) 124 xa->free(xa->arr); 125 xa->free(xa); 126 } 127 128 void VG_(setCmpFnXA) ( XArray* xao, XACmpFn_t compar ) 129 { 130 struct _XArray* xa = (struct _XArray*)xao; 131 vg_assert(xa); 132 vg_assert(compar); 133 xa->cmpFn = compar; 134 xa->sorted = False; 135 } 136 137 inline void* VG_(indexXA) ( XArray* xao, Word n ) 138 { 139 struct _XArray* xa = (struct _XArray*)xao; 140 vg_assert(xa); 141 vg_assert(n >= 0); 142 vg_assert(n < xa->usedsizeE); 143 return ((char*)xa->arr) + n * xa->elemSzB; 144 } 145 146 static inline void ensureSpaceXA ( struct _XArray* xa ) 147 { 148 if (xa->usedsizeE == xa->totsizeE) { 149 void* tmp; 150 Word newsz; 151 if (xa->totsizeE == 0) 152 vg_assert(!xa->arr); 153 if (xa->totsizeE > 0) 154 vg_assert(xa->arr); 155 if (xa->totsizeE == 0) { 156 /* No point in having tiny (eg) 2-byte allocations for the 157 element array, since all allocs are rounded up to 8 anyway. 158 Hence increase the initial array size for tiny elements in 159 an attempt to avoid reallocations of size 2, 4, 8 if the 160 array does start to fill up. */ 161 if (xa->elemSzB == 1) newsz = 8; 162 else if (xa->elemSzB == 2) newsz = 4; 163 else newsz = 2; 164 } else { 165 newsz = 2 + (3 * xa->totsizeE) / 2; /* 2 * xa->totsizeE; */ 166 } 167 if (0 && xa->totsizeE >= 10000) 168 VG_(printf)("addToXA: increasing from %ld to %ld\n", 169 xa->totsizeE, newsz); 170 tmp = xa->alloc(xa->cc, newsz * xa->elemSzB); 171 vg_assert(tmp); 172 if (xa->usedsizeE > 0) 173 VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB); 174 if (xa->arr) 175 xa->free(xa->arr); 176 xa->arr = tmp; 177 xa->totsizeE = newsz; 178 } 179 } 180 181 Word VG_(addToXA) ( XArray* xao, const void* elem ) 182 { 183 struct _XArray* xa = (struct _XArray*)xao; 184 vg_assert(xa); 185 vg_assert(elem); 186 vg_assert(xa->totsizeE >= 0); 187 vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); 188 ensureSpaceXA( xa ); 189 vg_assert(xa->usedsizeE < xa->totsizeE); 190 vg_assert(xa->arr); 191 VG_(memcpy)( ((UChar*)xa->arr) + xa->usedsizeE * xa->elemSzB, 192 elem, xa->elemSzB ); 193 xa->usedsizeE++; 194 xa->sorted = False; 195 return xa->usedsizeE-1; 196 } 197 198 Word VG_(addBytesToXA) ( XArray* xao, const void* bytesV, Word nbytes ) 199 { 200 Word r, i; 201 struct _XArray* xa = (struct _XArray*)xao; 202 vg_assert(xa); 203 vg_assert(xa->elemSzB == 1); 204 vg_assert(nbytes >= 0); 205 vg_assert(xa->totsizeE >= 0); 206 vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); 207 r = xa->usedsizeE; 208 for (i = 0; i < nbytes; i++) { 209 ensureSpaceXA( xa ); 210 vg_assert(xa->usedsizeE < xa->totsizeE); 211 vg_assert(xa->arr); 212 * (((UChar*)xa->arr) + xa->usedsizeE) = ((const UChar*)bytesV)[i]; 213 xa->usedsizeE++; 214 } 215 xa->sorted = False; 216 return r; 217 } 218 219 void VG_(sortXA) ( XArray* xao ) 220 { 221 struct _XArray* xa = (struct _XArray*)xao; 222 vg_assert(xa); 223 vg_assert(xa->cmpFn); 224 VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn ); 225 xa->sorted = True; 226 } 227 228 Bool VG_(lookupXA_UNSAFE) ( XArray* xao, const void* key, 229 /*OUT*/Word* first, /*OUT*/Word* last, 230 Int(*cmpFn)(const void*, const void*) ) 231 { 232 Word lo, mid, hi, cres; 233 void* midv; 234 struct _XArray* xa = (struct _XArray*)xao; 235 vg_assert(xa); 236 lo = 0; 237 hi = xa->usedsizeE-1; 238 while (True) { 239 /* current unsearched space is from lo to hi, inclusive. */ 240 if (lo > hi) return False; /* not found */ 241 mid = (lo + hi) / 2; 242 midv = VG_(indexXA)( xa, mid ); 243 cres = cmpFn( key, midv ); 244 if (cres < 0) { hi = mid-1; continue; } 245 if (cres > 0) { lo = mid+1; continue; } 246 /* Found it, at mid. See how far we can expand this. */ 247 vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0); 248 vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0); 249 if (first) { 250 *first = mid; 251 while (*first > 0 252 && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) { 253 (*first)--; 254 } 255 } 256 if (last) { 257 *last = mid; 258 while (*last < xa->usedsizeE-1 259 && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) { 260 (*last)++; 261 } 262 } 263 return True; 264 } 265 } 266 267 Bool VG_(lookupXA) ( XArray* xao, const void* key, 268 /*OUT*/Word* first, /*OUT*/Word* last ) 269 { 270 struct _XArray* xa = (struct _XArray*)xao; 271 vg_assert(xa); 272 vg_assert(xa->cmpFn); 273 vg_assert(xa->sorted); 274 return VG_(lookupXA_UNSAFE)(xao, key, first, last, xa->cmpFn); 275 } 276 277 Word VG_(sizeXA) ( XArray* xao ) 278 { 279 struct _XArray* xa = (struct _XArray*)xao; 280 vg_assert(xa); 281 return xa->usedsizeE; 282 } 283 284 void VG_(dropTailXA) ( XArray* xao, Word n ) 285 { 286 struct _XArray* xa = (struct _XArray*)xao; 287 vg_assert(xa); 288 vg_assert(n >= 0); 289 vg_assert(n <= xa->usedsizeE); 290 xa->usedsizeE -= n; 291 } 292 293 void VG_(dropHeadXA) ( XArray* xao, Word n ) 294 { 295 struct _XArray* xa = (struct _XArray*)xao; 296 vg_assert(xa); 297 vg_assert(n >= 0); 298 vg_assert(n <= xa->usedsizeE); 299 if (n == 0) { 300 return; 301 } 302 if (n == xa->usedsizeE) { 303 xa->usedsizeE = 0; 304 return; 305 } 306 vg_assert(n > 0); 307 vg_assert(xa->usedsizeE - n > 0); 308 VG_(memcpy)( (char*)xa->arr, 309 ((char*)xa->arr) + n * xa->elemSzB, 310 (xa->usedsizeE - n) * xa->elemSzB ); 311 xa->usedsizeE -= n; 312 } 313 314 void VG_(removeIndexXA)( XArray* xao, Word n ) 315 { 316 struct _XArray* xa = (struct _XArray*)xao; 317 vg_assert(xa); 318 vg_assert(n >= 0); 319 vg_assert(n < xa->usedsizeE); 320 if (n+1 < xa->usedsizeE) { 321 VG_(memmove)( ((char*)xa->arr) + (n+0) * xa->elemSzB, 322 ((char*)xa->arr) + (n+1) * xa->elemSzB, 323 (xa->usedsizeE - n - 1) * xa->elemSzB ); 324 } 325 xa->usedsizeE--; 326 } 327 328 void VG_(insertIndexXA)( XArray* xao, Word n, const void* elem ) 329 { 330 struct _XArray* xa = (struct _XArray*)xao; 331 vg_assert(xa); 332 vg_assert(n >= 0); 333 vg_assert(n <= xa->usedsizeE); 334 vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); 335 ensureSpaceXA( xa ); 336 vg_assert(xa->usedsizeE < xa->totsizeE); 337 vg_assert(xa->arr); 338 if (n < xa->usedsizeE) { 339 VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB, 340 ((char*)xa->arr) + (n+0) * xa->elemSzB, 341 (xa->usedsizeE - n) * xa->elemSzB ); 342 } 343 VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB, 344 elem, xa->elemSzB ); 345 xa->usedsizeE++; 346 xa->sorted = False; 347 } 348 349 void VG_(getContentsXA_UNSAFE)( XArray* xao, 350 /*OUT*/void** ctsP, 351 /*OUT*/Word* usedP ) 352 { 353 struct _XArray* xa = (struct _XArray*)xao; 354 vg_assert(xa); 355 *ctsP = (void*)xa->arr; 356 *usedP = xa->usedsizeE; 357 } 358 359 /* --------- Printeffery --------- */ 360 361 static void add_char_to_XA ( HChar c, void* opaque ) 362 { 363 XArray* dst = (XArray*)opaque; 364 (void) VG_(addBytesToXA)( dst, &c, 1 ); 365 } 366 367 void VG_(xaprintf)( XArray* dst, const HChar* format, ... ) 368 { 369 va_list vargs; 370 va_start(vargs, format); 371 VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs ); 372 va_end(vargs); 373 } 374 375 376 /*--------------------------------------------------------------------*/ 377 /*--- end m_xarray.c ---*/ 378 /*--------------------------------------------------------------------*/ 379
