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-2010 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) ( 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 /*--------------------------------------------------------------------*/
    348