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, 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    Alloc_Fn_t alloc_fn;                /* alloc fn (nofail) */
  42    const HChar* cc;                    /* cost centre for alloc */
  43    Free_Fn_t free_fn;                  /* 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) ( Alloc_Fn_t alloc_fn,
  54                      const HChar* cc,
  55                      Free_Fn_t free_fn,
  56                      Word elemSzB )
  57 {
  58    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    xa->alloc_fn  = alloc_fn;
  70    xa->cc        = cc;
  71    xa->free_fn   = free_fn;
  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
  81 XArray* VG_(cloneXA)( const HChar* cc, const XArray* xa )
  82 {
  83    XArray* nyu;
  84    const HChar* nyu_cc;
  85    vg_assert(xa);
  86    vg_assert(xa->alloc_fn);
  87    vg_assert(xa->free_fn);
  88    vg_assert(xa->elemSzB >= 1);
  89    nyu_cc = cc ? cc : xa->cc;
  90    nyu = xa->alloc_fn( nyu_cc, sizeof(struct _XArray) );
  91
  92    /* Copy everything verbatim ... */
  93    *nyu = *xa;
  94    nyu->cc = nyu_cc;
  95    /* ... except we have to clone the contents-array */
  96    if (nyu->arr) {
  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 .. */
 104       nyu->arr = nyu->alloc_fn( nyu->cc, nyu->totsizeE * nyu->elemSzB );
 105       VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB );
 106    }
 107    /* We're done! */
 108    return nyu;
 109 }
 110
 111 void VG_(deleteXA) ( XArray* xa )
 112 {
 113    vg_assert(xa);
 114    vg_assert(xa->free_fn);
 115    if (xa->arr)
 116       xa->free_fn(xa->arr);
 117    xa->free_fn(xa);
 118 }
 119
 120 void VG_(setCmpFnXA) ( XArray* xa, XACmpFn_t compar )
 121 {
 122    vg_assert(xa);
 123    vg_assert(compar);
 124    xa->cmpFn  = compar;
 125    xa->sorted = False;
 126 }
 127
 128 inline void* VG_(indexXA) ( const XArray* xa, Word n )
 129 {
 130    vg_assert(xa);
 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);
 135    return ((char*)xa->arr) + n * xa->elemSzB;
 136 }
 137
 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    if (n > 0) {
 153       xa->arr = xa->alloc_fn(xa->cc, n * xa->elemSzB);
 154       xa->totsizeE = n;
 155    }
 156 }
 157
 158 static inline void ensureSpaceXA ( XArray* xa )
 159 {
 160    if (xa->usedsizeE == xa->totsizeE) {
 161       void* tmp;
 162       Word  newsz;
 163       if (xa->totsizeE == 0)
 164          vg_assert(!xa->arr);
 165       if (xa->totsizeE > 0)
 166          vg_assert(xa->arr);
 167       if (xa->totsizeE == 0) {
 168          /* No point in having tiny (eg) 2-byte allocations for the
 169             element array, since all allocs are rounded up to 8 anyway.
 170             Hence increase the initial array size for tiny elements in
 171             an attempt to avoid reallocations of size 2, 4, 8 if the
 172             array does start to fill up. */
 173          if (xa->elemSzB == 1) newsz = 8;
 174          else if (xa->elemSzB == 2) newsz = 4;
 175          else newsz = 2;
 176       } else {
 177          newsz = 2 + (3 * xa->totsizeE) / 2;  /* 2 * xa->totsizeE; */
 178       }
 179       if (0 && xa->totsizeE >= 10000)
 180          VG_(printf)("addToXA: increasing from %ld to %ld\n",
 181                      xa->totsizeE, newsz);
 182       tmp = xa->alloc_fn(xa->cc, newsz * xa->elemSzB);
 183       if (xa->usedsizeE > 0)
 184          VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB);
 185       if (xa->arr)
 186          xa->free_fn(xa->arr);
 187       xa->arr = tmp;
 188       xa->totsizeE = newsz;
 189    }
 190 }
 191
 192 Word VG_(addToXA) ( XArray* xa, const void* elem )
 193 {
 194    vg_assert(xa);
 195    vg_assert(elem);
 196    vg_assert(xa->totsizeE >= 0);
 197    vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
 198    ensureSpaceXA( xa );
 199    vg_assert(xa->usedsizeE < xa->totsizeE);
 200    vg_assert(xa->arr);
 201    VG_(memcpy)( ((UChar*)xa->arr) + xa->usedsizeE * xa->elemSzB,
 202                 elem, xa->elemSzB );
 203    xa->usedsizeE++;
 204    xa->sorted = False;
 205    return xa->usedsizeE-1;
 206 }
 207
 208 Word VG_(addBytesToXA) ( XArray* xa, const void* bytesV, Word nbytes )
 209 {
 210    Word r, i;
 211    vg_assert(xa);
 212    vg_assert(xa->elemSzB == 1);
 213    vg_assert(nbytes >= 0);
 214    vg_assert(xa->totsizeE >= 0);
 215    vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
 216    r = xa->usedsizeE;
 217    for (i = 0; i < nbytes; i++) {
 218       ensureSpaceXA( xa );
 219       vg_assert(xa->usedsizeE < xa->totsizeE);
 220       vg_assert(xa->arr);
 221       * (((UChar*)xa->arr) + xa->usedsizeE) = ((const UChar*)bytesV)[i];
 222       xa->usedsizeE++;
 223    }
 224    xa->sorted = False;
 225    return r;
 226 }
 227
 228 void VG_(sortXA) ( XArray* xa )
 229 {
 230    vg_assert(xa);
 231    vg_assert(xa->cmpFn);
 232    VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn );
 233    xa->sorted = True;
 234 }
 235
 236 Bool VG_(lookupXA_UNSAFE) ( const XArray* xa, const void* key,
 237                             /*OUT*/Word* first, /*OUT*/Word* last,
 238                             Int(*cmpFn)(const void*, const void*) )
 239 {
 240    Word  lo, mid, hi, cres;
 241    void* midv;
 242    vg_assert(xa);
 243    lo = 0;
 244    hi = xa->usedsizeE-1;
 245    while (True) {
 246       /* current unsearched space is from lo to hi, inclusive. */
 247       if (lo > hi) return False; /* not found */
 248       mid  = (lo + hi) / 2;
 249       midv = VG_(indexXA)( xa, mid );
 250       cres = cmpFn( key, midv );
 251       if (cres < 0)  { hi = mid-1; continue; }
 252       if (cres > 0)  { lo = mid+1; continue; }
 253       /* Found it, at mid.  See how far we can expand this. */
 254       vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
 255       vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
 256       if (first) {
 257          *first = mid;
 258          while (*first > 0
 259                 && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) {
 260             (*first)--;
 261          }
 262       }
 263       if (last) {
 264          *last = mid;
 265          while (*last < xa->usedsizeE-1
 266                 && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) {
 267             (*last)++;
 268          }
 269       }
 270       return True;
 271    }
 272 }
 273
 274 Bool VG_(lookupXA) ( const XArray* xa, const void* key,
 275                      /*OUT*/Word* first, /*OUT*/Word* last )
 276 {
 277    vg_assert(xa);
 278    vg_assert(xa->cmpFn);
 279    vg_assert(xa->sorted);
 280    return VG_(lookupXA_UNSAFE)(xa, key, first, last, xa->cmpFn);
 281 }
 282
 283 /* FIXME: This function should return an unsigned value because the number
 284    of elements cannot be negative. Unfortunately, making the change causes
 285    a lot of ripple. */
 286 Word VG_(sizeXA) ( const XArray* xa )
 287 {
 288    vg_assert(xa);
 289    return xa->usedsizeE;
 290 }
 291
 292 void VG_(dropTailXA) ( XArray* xa, Word n )
 293 {
 294    vg_assert(xa);
 295    vg_assert(n >= 0);
 296    vg_assert(n <= xa->usedsizeE);
 297    xa->usedsizeE -= n;
 298 }
 299
 300 void VG_(dropHeadXA) ( XArray* xa, Word n )
 301 {
 302    vg_assert(xa);
 303    vg_assert(n >= 0);
 304    vg_assert(n <= xa->usedsizeE);
 305    if (n == 0) {
 306       return;
 307    }
 308    if (n == xa->usedsizeE) {
 309       xa->usedsizeE = 0;
 310       return;
 311    }
 312    vg_assert(n > 0);
 313    vg_assert(xa->usedsizeE - n > 0);
 314    VG_(memcpy)( (char*)xa->arr,
 315                 ((char*)xa->arr) + n * xa->elemSzB,
 316                 (xa->usedsizeE - n) * xa->elemSzB );
 317    xa->usedsizeE -= n;
 318 }
 319
 320 void VG_(removeIndexXA)( XArray* xa, Word n )
 321 {
 322    vg_assert(xa);
 323    vg_assert(n >= 0);
 324    vg_assert(n < xa->usedsizeE);
 325    if (n+1 < xa->usedsizeE) {
 326       VG_(memmove)( ((char*)xa->arr) + (n+0) * xa->elemSzB,
 327                     ((char*)xa->arr) + (n+1) * xa->elemSzB,
 328                     (xa->usedsizeE - n - 1) * xa->elemSzB );
 329    }
 330    xa->usedsizeE--;
 331 }
 332
 333 void VG_(insertIndexXA)( XArray* xa, Word n, const void* elem )
 334 {
 335    vg_assert(xa);
 336    vg_assert(n >= 0);
 337    vg_assert(n <= xa->usedsizeE);
 338    vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
 339    ensureSpaceXA( xa );
 340    vg_assert(xa->usedsizeE < xa->totsizeE);
 341    vg_assert(xa->arr);
 342    if (n < xa->usedsizeE) {
 343       VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB,
 344                      ((char*)xa->arr) + (n+0) * xa->elemSzB,
 345                      (xa->usedsizeE - n) * xa->elemSzB );
 346    }
 347    VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB,
 348                 elem, xa->elemSzB );
 349    xa->usedsizeE++;
 350    xa->sorted = False;
 351 }
 352
 353 void VG_(getContentsXA_UNSAFE)( XArray* xa,
 354                                 /*OUT*/void** ctsP,
 355                                 /*OUT*/Word* usedP )
 356 {
 357    vg_assert(xa);
 358    *ctsP  = (void*)xa->arr;
 359    *usedP = xa->usedsizeE;
 360 }
 361
 362 /* --------- Printeffery --------- */
 363
 364 static void add_char_to_XA ( HChar c, void* opaque )
 365 {
 366    XArray* dst = (XArray*)opaque;
 367    (void) VG_(addBytesToXA)( dst, &c, 1 );
 368 }
 369
 370 void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
 371 {
 372    va_list vargs;
 373    va_start(vargs, format);
 374    VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
 375    va_end(vargs);
 376 }
 377
 378 Bool VG_(strIsMemberXA)(const XArray* xa, const HChar* str )
 379 {
 380    Word i;
 381    HChar** members = (HChar**)xa->arr;
 382
 383    for (i = 0; i < xa->usedsizeE; i++)
 384       if (VG_(strcmp)(str, members[i]) == 0)
 385          return True;
 386    return False;
 387 }
 388
 389 /*--------------------------------------------------------------------*/
 390 /*--- end                                               m_xarray.c ---*/
 391 /*--------------------------------------------------------------------*/