l4/pkg/valgrind/src/valgrind-3.6.0-svn/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-2010 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    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 /*--------------------------------------------------------------------*/