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-2010 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) ( HChar*, SizeT ); /* alloc fn (nofail) */ 42 HChar* cc; /* cost centre for alloc */ 43 void (*free) ( void* ); /* free fn */ 44 Int (*cmpFn) ( void*, 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)(HChar*,SizeT), 54 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)( HChar* cc, XArray* xao ) 83 { 84 struct _XArray* xa = (struct _XArray*)xao; 85 struct _XArray* nyu; 86 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, Int (*compar)(void*,void*) ) 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, 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, 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) = ((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, void* key, 229 /*OUT*/Word* first, /*OUT*/Word* last, 230 Int(*cmpFn)(void*,void*) ) 231 { 232 Word lo, mid, hi, cres; 233 void* midv; 234 struct _XArray* xa = (struct _XArray*)xao; 235 vg_assert(xa); 236 vg_assert(first); 237 vg_assert(last); 238 lo = 0; 239 hi = xa->usedsizeE-1; 240 while (True) { 241 /* current unsearched space is from lo to hi, inclusive. */ 242 if (lo > hi) return False; /* not found */ 243 mid = (lo + hi) / 2; 244 midv = VG_(indexXA)( xa, mid ); 245 cres = cmpFn( key, midv ); 246 if (cres < 0) { hi = mid-1; continue; } 247 if (cres > 0) { lo = mid+1; continue; } 248 /* Found it, at mid. See how far we can expand this. */ 249 vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0); 250 vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0); 251 *first = *last = mid; 252 while (*first > 0 253 && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) 254 (*first)--; 255 while (*last < xa->usedsizeE-1 256 && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) 257 (*last)++; 258 return True; 259 } 260 } 261 262 Bool VG_(lookupXA) ( XArray* xao, void* key, 263 /*OUT*/Word* first, /*OUT*/Word* last ) 264 { 265 struct _XArray* xa = (struct _XArray*)xao; 266 vg_assert(xa); 267 vg_assert(xa->cmpFn); 268 vg_assert(xa->sorted); 269 return VG_(lookupXA_UNSAFE)(xao, key, first, last, xa->cmpFn); 270 } 271 272 Word VG_(sizeXA) ( XArray* xao ) 273 { 274 struct _XArray* xa = (struct _XArray*)xao; 275 vg_assert(xa); 276 return xa->usedsizeE; 277 } 278 279 void VG_(dropTailXA) ( XArray* xao, Word n ) 280 { 281 struct _XArray* xa = (struct _XArray*)xao; 282 vg_assert(xa); 283 vg_assert(n >= 0); 284 vg_assert(n <= xa->usedsizeE); 285 xa->usedsizeE -= n; 286 } 287 288 void VG_(dropHeadXA) ( XArray* xao, Word n ) 289 { 290 struct _XArray* xa = (struct _XArray*)xao; 291 vg_assert(xa); 292 vg_assert(n >= 0); 293 vg_assert(n <= xa->usedsizeE); 294 if (n == 0) { 295 return; 296 } 297 if (n == xa->usedsizeE) { 298 xa->usedsizeE = 0; 299 return; 300 } 301 vg_assert(n > 0); 302 vg_assert(xa->usedsizeE - n > 0); 303 VG_(memcpy)( (char*)xa->arr, 304 ((char*)xa->arr) + n * xa->elemSzB, 305 (xa->usedsizeE - n) * xa->elemSzB ); 306 xa->usedsizeE -= n; 307 } 308 309 void VG_(getContentsXA_UNSAFE)( XArray* xao, 310 /*OUT*/void** ctsP, 311 /*OUT*/Word* usedP ) 312 { 313 struct _XArray* xa = (struct _XArray*)xao; 314 vg_assert(xa); 315 *ctsP = (void*)xa->arr; 316 *usedP = xa->usedsizeE; 317 } 318 319 /* --------- Printeffery --------- */ 320 321 static void add_char_to_XA ( HChar c, void* opaque ) 322 { 323 XArray* dst = (XArray*)opaque; 324 (void) VG_(addBytesToXA)( dst, &c, 1 ); 325 } 326 327 void VG_(xaprintf)( XArray* dst, const HChar* format, ... ) 328 { 329 va_list vargs; 330 va_start(vargs, format); 331 VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs ); 332 va_end(vargs); 333 } 334 335 /* and again .. */ 336 void VG_(xaprintf_no_f_c)( XArray* dst, const HChar* format, ... ) 337 { 338 va_list vargs; 339 va_start(vargs, format); 340 VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs ); 341 va_end(vargs); 342 } 343 344 345 /*--------------------------------------------------------------------*/ 346 /*--- end m_xarray.c ---*/ 347 /*--------------------------------------------------------------------*/ 348
