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-2012 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    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    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, 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_(getContentsXA_UNSAFE)( XArray* xao,
 329                                 /*OUT*/void** ctsP,
 330                                 /*OUT*/Word* usedP )
 331 {
 332    struct _XArray* xa = (struct _XArray*)xao;
 333    vg_assert(xa);
 334    *ctsP  = (void*)xa->arr;
 335    *usedP = xa->usedsizeE;
 336 }
 337
 338 /* --------- Printeffery --------- */
 339
 340 static void add_char_to_XA ( HChar c, void* opaque )
 341 {
 342    XArray* dst = (XArray*)opaque;
 343    (void) VG_(addBytesToXA)( dst, &c, 1 );
 344 }
 345
 346 void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
 347 {
 348    va_list vargs;
 349    va_start(vargs, format);
 350    VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
 351    va_end(vargs);
 352 }
 353
 354
 355 /*--------------------------------------------------------------------*/
 356 /*--- end                                               m_xarray.c ---*/
 357 /*--------------------------------------------------------------------*/