Home | History | Annotate | Download | only in coregrind
      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-2015 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_fn) ( const HChar*, SizeT ); /* alloc fn (nofail) */
     42    const HChar* cc;                    /* cost centre for alloc */
     43    void  (*free_fn) ( void* );         /* 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) ( void*(*alloc_fn)(const HChar*,SizeT),
     54                      const HChar* cc,
     55                      void(*free_fn)(void*),
     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    xa->arr = xa->alloc_fn(xa->cc, n * xa->elemSzB);
    153    xa->totsizeE = n;
    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_(getContentsXA_UNSAFE)( XArray* xa,
    352                                 /*OUT*/void** ctsP,
    353                                 /*OUT*/Word* usedP )
    354 {
    355    vg_assert(xa);
    356    *ctsP  = (void*)xa->arr;
    357    *usedP = xa->usedsizeE;
    358 }
    359 
    360 /* --------- Printeffery --------- */
    361 
    362 static void add_char_to_XA ( HChar c, void* opaque )
    363 {
    364    XArray* dst = (XArray*)opaque;
    365    (void) VG_(addBytesToXA)( dst, &c, 1 );
    366 }
    367 
    368 void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
    369 {
    370    va_list vargs;
    371    va_start(vargs, format);
    372    VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
    373    va_end(vargs);
    374 }
    375 
    376 
    377 /*--------------------------------------------------------------------*/
    378 /*--- end                                               m_xarray.c ---*/
    379 /*--------------------------------------------------------------------*/
    380