coregrind/m_xarray.c

   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-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, see <http://www.gnu.org/licenses/>.
  25
  26    The GNU General Public License is contained in the file COPYING.
  27 */
  28
  29 #include "pub_core_basics.h"
  30 #include "pub_core_libcbase.h"
  31 #include "pub_core_libcassert.h"
  32 #include "pub_core_libcprint.h"
  33 #include "pub_core_xarray.h"    /* self */
  34
  35
  36 /* See pub_tool_xarray.h for details of what this is all about. */
  37
  38 struct _XArray {
  39    Alloc_Fn_t alloc_fn;                /* alloc fn (nofail) */
  40    const HChar* cc;                    /* cost centre for alloc */
  41    Free_Fn_t free_fn;                  /* free fn */
  42    Int   (*cmpFn) ( const void*, const void* ); /* cmp fn (may be NULL) */
  43    Word  elemSzB;   /* element size in bytes */
  44    void* arr;       /* pointer to elements */
  45    Word  usedsizeE; /* # used elements in arr */
  46    Word  totsizeE;  /* max size of arr, in elements */
  47    Bool  sorted;    /* is it sorted? */
  48 };
  49
  50
  51 XArray* VG_(newXA) ( Alloc_Fn_t alloc_fn,
  52                      const HChar* cc,
  53                      Free_Fn_t free_fn,
  54                      Word elemSzB )
  55 {
  56    XArray* xa;
  57    /* Implementation relies on Word being signed and (possibly)
  58       on SizeT being unsigned. */
  59    vg_assert( sizeof(Word) == sizeof(void*) );
  60    vg_assert( ((Word)(-1)) < ((Word)(0)) );
  61    vg_assert( ((SizeT)(-1)) > ((SizeT)(0)) );
  62    /* check user-supplied info .. */
  63    vg_assert(alloc_fn);
  64    vg_assert(free_fn);
  65    vg_assert(elemSzB > 0);
  66    xa = alloc_fn( cc, sizeof(struct _XArray) );
  67    xa->alloc_fn  = alloc_fn;
  68    xa->cc        = cc;
  69    xa->free_fn   = free_fn;
  70    xa->cmpFn     = NULL;
  71    xa->elemSzB   = elemSzB;
  72    xa->usedsizeE = 0;
  73    xa->totsizeE  = 0;
  74    xa->sorted    = False;
  75    xa->arr       = NULL;
  76    return xa;
  77 }
  78
  79 XArray* VG_(cloneXA)( const HChar* cc, const XArray* xa )
  80 {
  81    XArray* nyu;
  82    const HChar* nyu_cc;
  83    vg_assert(xa);
  84    vg_assert(xa->alloc_fn);
  85    vg_assert(xa->free_fn);
  86    vg_assert(xa->elemSzB >= 1);
  87    nyu_cc = cc ? cc : xa->cc;
  88    nyu = xa->alloc_fn( nyu_cc, sizeof(struct _XArray) );
  89
  90    /* Copy everything verbatim ... */
  91    *nyu = *xa;
  92    nyu->cc = nyu_cc;
  93    /* ... except we have to clone the contents-array */
  94    if (nyu->arr) {
  95       /* Restrict the total size of the new array to its current
  96          actual size.  That means we don't waste space copying the
  97          unused tail of the original.  The tradeoff is that it
  98          guarantees we will have to resize the child if even one more
  99          element is later added to it, unfortunately. */
 100       nyu->totsizeE = nyu->usedsizeE;
 101       /* and allocate .. */
 102       nyu->arr = nyu->alloc_fn( nyu->cc, nyu->totsizeE * nyu->elemSzB );
 103       VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB );
 104    }
 105    /* We're done! */
 106    return nyu;
 107 }
 108
 109 void VG_(deleteXA) ( XArray* xa )
 110 {
 111    vg_assert(xa);
 112    vg_assert(xa->free_fn);
 113    if (xa->arr)
 114       xa->free_fn(xa->arr);
 115    xa->free_fn(xa);
 116 }
 117
 118 void VG_(setCmpFnXA) ( XArray* xa, XACmpFn_t compar )
 119 {
 120    vg_assert(xa);
 121    vg_assert(compar);
 122    xa->cmpFn  = compar;
 123    xa->sorted = False;
 124 }
 125
 126 inline void* VG_(indexXA) ( const XArray* xa, Word n )
 127 {
 128    vg_assert(xa);
 129    /* vg_assert(n >= 0); If n negative, the UWord conversion will make
 130       it bigger than usedsizeE, which is verified to be non negative when
 131       xa is modified. */
 132    vg_assert((UWord)n < (UWord)xa->usedsizeE);
 133    return ((char*)xa->arr) + n * xa->elemSzB;
 134 }
 135
 136 void VG_(hintSizeXA) ( XArray* xa, Word n)
 137 {
 138    /* Currently, we support giving a size hint only just after the
 139       call to VG_(newXA). So, we could instead have done
 140       a function VG_(newXA_with_SizeHint). The separate VG_(hintSizeXA)
 141       function is however chosen as we might one day accept to
 142       give a size hint after having added elements. That could be useful
 143       for reducing the size of an xarray to just the size currently needed
 144       or to give a size hint when it is known that a lot more elements
 145       are needed or when the final nr of elements is known. */
 146    vg_assert(xa);
 147    vg_assert(xa->usedsizeE == 0);
 148    vg_assert(xa->totsizeE == 0);
 149    vg_assert(!xa->arr);
 150    if (n > 0) {
 151       xa->arr = xa->alloc_fn(xa->cc, n * xa->elemSzB);
 152       xa->totsizeE = n;
 153    }
 154 }
 155
 156 static inline void ensureSpaceXA ( XArray* xa )
 157 {
 158    if (xa->usedsizeE == xa->totsizeE) {
 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);
 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. */
 171          if (xa->elemSzB == 1) newsz = 8;
 172          else if (xa->elemSzB == 2) newsz = 4;
 173          else newsz = 2;
 174       } else {
 175          newsz = 2 + (3 * xa->totsizeE) / 2;  /* 2 * xa->totsizeE; */
 176       }
 177       if (0 && xa->totsizeE >= 10000)
 178          VG_(printf)("addToXA: increasing from %ld to %ld\n",
 179                      xa->totsizeE, newsz);
 180       tmp = xa->alloc_fn(xa->cc, newsz * xa->elemSzB);
 181       if (xa->usedsizeE > 0)
 182          VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB);
 183       if (xa->arr)
 184          xa->free_fn(xa->arr);
 185       xa->arr = tmp;
 186       xa->totsizeE = newsz;
 187    }
 188 }
 189
 190 Word VG_(addToXA) ( XArray* xa, const void* elem )
 191 {
 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 );
 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;
 203    return xa->usedsizeE-1;
 204 }
 205
 206 Word VG_(addBytesToXA) ( XArray* xa, const void* bytesV, Word nbytes )
 207 {
 208    Word r, i;
 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);
 219       * (((UChar*)xa->arr) + xa->usedsizeE) = ((const UChar*)bytesV)[i];
 220       xa->usedsizeE++;
 221    }
 222    xa->sorted = False;
 223    return r;
 224 }
 225
 226 void VG_(sortXA) ( XArray* xa )
 227 {
 228    vg_assert(xa);
 229    vg_assert(xa->cmpFn);
 230    VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn );
 231    xa->sorted = True;
 232 }
 233
 234 Bool VG_(lookupXA_UNSAFE) ( const XArray* xa, const void* key,
 235                             /*OUT*/Word* first, /*OUT*/Word* last,
 236                             Int(*cmpFn)(const void*, const void*) )
 237 {
 238    Word  lo, mid, hi, cres;
 239    void* midv;
 240    vg_assert(xa);
 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 );
 248       cres = cmpFn( key, midv );
 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. */
 252       vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
 253       vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
 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       }
 268       return True;
 269    }
 270 }
 271
 272 Bool VG_(lookupXA) ( const XArray* xa, const void* key,
 273                      /*OUT*/Word* first, /*OUT*/Word* last )
 274 {
 275    vg_assert(xa);
 276    vg_assert(xa->cmpFn);
 277    vg_assert(xa->sorted);
 278    return VG_(lookupXA_UNSAFE)(xa, key, first, last, xa->cmpFn);
 279 }
 280
 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. */
 284 Word VG_(sizeXA) ( const XArray* xa )
 285 {
 286    vg_assert(xa);
 287    return xa->usedsizeE;
 288 }
 289
 290 void VG_(dropTailXA) ( XArray* xa, Word n )
 291 {
 292    vg_assert(xa);
 293    vg_assert(n >= 0);
 294    vg_assert(n <= xa->usedsizeE);
 295    xa->usedsizeE -= n;
 296 }
 297
 298 void VG_(dropHeadXA) ( XArray* xa, Word n )
 299 {
 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
 318 void VG_(removeIndexXA)( XArray* xa, Word n )
 319 {
 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
 331 void VG_(insertIndexXA)( XArray* xa, Word n, const void* elem )
 332 {
 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
 351 void VG_(replaceIndexXA)( XArray* xa, Word n, const void* elem )
 352 {
 353    vg_assert(xa);
 354    vg_assert(n >= 0);
 355    vg_assert(n < xa->usedsizeE);
 356    vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
 357    VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB,
 358                 elem, xa->elemSzB );
 359    xa->sorted = False;
 360 }
 361
 362 void VG_(getContentsXA_UNSAFE)( XArray* xa,
 363                                 /*OUT*/void** ctsP,
 364                                 /*OUT*/Word* usedP )
 365 {
 366    vg_assert(xa);
 367    *ctsP  = (void*)xa->arr;
 368    *usedP = xa->usedsizeE;
 369 }
 370
 371 /* --------- Printeffery --------- */
 372
 373 static void add_char_to_XA ( HChar c, void* opaque )
 374 {
 375    XArray* dst = (XArray*)opaque;
 376    (void) VG_(addBytesToXA)( dst, &c, 1 );
 377 }
 378
 379 void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
 380 {
 381    va_list vargs;
 382    va_start(vargs, format);
 383    VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
 384    va_end(vargs);
 385 }
 386
 387 Bool VG_(strIsMemberXA)(const XArray* xa, const HChar* str )
 388 {
 389    Word i;
 390    HChar** members = (HChar**)xa->arr;
 391
 392    for (i = 0; i < xa->usedsizeE; i++)
 393       if (VG_(strcmp)(str, members[i]) == 0)
 394          return True;
 395    return False;
 396 }
 397
 398 /*--------------------------------------------------------------------*/
 399 /*--- end                                               m_xarray.c ---*/
 400 /*--------------------------------------------------------------------*/