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-2013 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) ( const HChar*, SizeT ); /* alloc fn (nofail) */
     42    const HChar* cc;                 /* cost centre for alloc */
     43    void  (*free) ( 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    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)( const HChar* cc, XArray* xao )
     83 {
     84    struct _XArray* xa = (struct _XArray*)xao;
     85    struct _XArray* nyu;
     86    const 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, XACmpFn_t compar )
    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, const 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, const 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) = ((const 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, const void* key,
    229                             /*OUT*/Word* first, /*OUT*/Word* last,
    230                             Int(*cmpFn)(const void*, const 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, const 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_(insertIndexXA)( XArray* xao, Word n, const void* elem )
    329 {
    330    struct _XArray* xa = (struct _XArray*)xao;
    331    vg_assert(xa);
    332    vg_assert(n >= 0);
    333    vg_assert(n <= xa->usedsizeE);
    334    vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
    335    ensureSpaceXA( xa );
    336    vg_assert(xa->usedsizeE < xa->totsizeE);
    337    vg_assert(xa->arr);
    338    if (n < xa->usedsizeE) {
    339       VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB,
    340                      ((char*)xa->arr) + (n+0) * xa->elemSzB,
    341                      (xa->usedsizeE - n) * xa->elemSzB );
    342    }
    343    VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB,
    344                 elem, xa->elemSzB );
    345    xa->usedsizeE++;
    346    xa->sorted = False;
    347 }
    348 
    349 void VG_(getContentsXA_UNSAFE)( XArray* xao,
    350                                 /*OUT*/void** ctsP,
    351                                 /*OUT*/Word* usedP )
    352 {
    353    struct _XArray* xa = (struct _XArray*)xao;
    354    vg_assert(xa);
    355    *ctsP  = (void*)xa->arr;
    356    *usedP = xa->usedsizeE;
    357 }
    358 
    359 /* --------- Printeffery --------- */
    360 
    361 static void add_char_to_XA ( HChar c, void* opaque )
    362 {
    363    XArray* dst = (XArray*)opaque;
    364    (void) VG_(addBytesToXA)( dst, &c, 1 );
    365 }
    366 
    367 void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
    368 {
    369    va_list vargs;
    370    va_start(vargs, format);
    371    VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
    372    va_end(vargs);
    373 }
    374 
    375 
    376 /*--------------------------------------------------------------------*/
    377 /*--- end                                               m_xarray.c ---*/
    378 /*--------------------------------------------------------------------*/
    379