Home | History | Annotate | Download | only in include
      1 
      2 /*--------------------------------------------------------------------*/
      3 /*--- An expandable array implementation.        pub_tool_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 (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 #ifndef __PUB_TOOL_XARRAY_H
     32 #define __PUB_TOOL_XARRAY_H
     33 
     34 //--------------------------------------------------------------------
     35 // PURPOSE: Provides a simple but useful structure, which is an array
     36 // in which elements can be added at the end.  The array is expanded
     37 // as needed by multiplying its size by a constant factor (usually 2).
     38 // This gives amortised O(1) insertion cost, and, following sorting,
     39 // the usual O(log N) binary search cost.  Arbitrary element sizes
     40 // are allowed; the comparison function for sort/lookup can be changed
     41 // at any time, and duplicates (modulo the comparison function) are
     42 // allowed.
     43 //--------------------------------------------------------------------
     44 
     45 
     46 /* It's an abstract type.  Bwaha. */
     47 typedef  struct _XArray  XArray;
     48 
     49 /* Create new XArray, using given allocation and free function, and
     50    for elements of the specified size.  Alloc fn must not fail (that
     51    is, if it returns it must have succeeded.) */
     52 extern XArray* VG_(newXA) ( void*(*alloc_fn)(HChar*,SizeT),
     53                             HChar* cc,
     54                             void(*free_fn)(void*),
     55                             Word elemSzB );
     56 
     57 /* Free all memory associated with an XArray. */
     58 extern void VG_(deleteXA) ( XArray* );
     59 
     60 /* Set the comparison function for this XArray.  This clears an
     61    internal 'array is sorted' flag, which means you must call sortXA
     62    before making further queries with lookupXA. */
     63 extern void VG_(setCmpFnXA) ( XArray*, Int (*compar)(void*,void*) );
     64 
     65 /* Add an element to an XArray.  Element is copied into the XArray.
     66    Index at which it was added is returned.  Note this will be
     67    invalidated if the array is later sortXA'd. */
     68 extern Word VG_(addToXA) ( XArray*, void* elem );
     69 
     70 /* Add a sequence of bytes to an XArray of bytes.  Asserts if nbytes
     71    is negative or the array's element size is not 1.  Returns the
     72    index at which the first byte was added. */
     73 extern Word VG_(addBytesToXA) ( XArray* xao, void* bytesV, Word nbytes );
     74 
     75 /* Sort an XArray using its comparison function, if set; else bomb.
     76    Probably not a stable sort w.r.t. equal elements module cmpFn. */
     77 extern void VG_(sortXA) ( XArray* );
     78 
     79 /* Lookup (by binary search) 'key' in the array.  Set *first to be the
     80    index of the first, and *last to be the index of the last matching
     81    value found.  If any values are found, return True, else return
     82    False, and don't change *first or *last.  first and/or last may be
     83    NULL.  Bomb if the array is not sorted. */
     84 extern Bool VG_(lookupXA) ( XArray*, void* key,
     85                             /*OUT*/Word* first, /*OUT*/Word* last );
     86 
     87 /* A version of VG_(lookupXA) in which you can specify your own
     88    comparison function.  This is unsafe in the sense that if the array
     89    is not totally ordered as defined by your comparison function, then
     90    this function may loop indefinitely, so it is up to you to ensure
     91    that the array is suitably ordered.  This is in comparison to
     92    VG_(lookupXA), which refuses to do anything (asserts) unless the
     93    array has first been sorted using the same comparison function as
     94    is being used for the lookup. */
     95 extern Bool VG_(lookupXA_UNSAFE) ( XArray* xao, void* key,
     96                                    /*OUT*/Word* first, /*OUT*/Word* last,
     97                                    Int(*cmpFn)(void*,void*) );
     98 
     99 /* How elements are there in this XArray now? */
    100 extern Word VG_(sizeXA) ( XArray* );
    101 
    102 /* Index into the XArray.  Checks bounds and bombs if the index is
    103    invalid.  What this returns is the address of the specified element
    104    in the array, not (of course) the element itself.  Note that the
    105    element may get moved by subsequent addToXAs/sortXAs, so you should
    106    copy it out immediately and not regard its address as unchanging.
    107    Note also that indexXA will of course not return NULL if it
    108    succeeds. */
    109 extern void* VG_(indexXA) ( XArray*, Word );
    110 
    111 /* Drop the last n elements of an XArray.  Bombs if there are less
    112    than n elements in the array.  This is an O(1) operation. */
    113 extern void VG_(dropTailXA) ( XArray*, Word );
    114 
    115 /* Drop the first n elements of an XArray.  Bombs if there are less
    116    than n elements in the array.  This is an O(N) operation, where N
    117    is the number of elements remaining in the XArray. */
    118 extern void VG_(dropHeadXA) ( XArray*, Word );
    119 
    120 /* Remove the specified element of an XArray, and slide all elements
    121    beyond it back one place.  This is an O(N) operation, where N is
    122    the number of elements after the specified element, in the
    123    array. */
    124 extern void VG_(removeIndexXA)( XArray*, Word );
    125 
    126 /* Make a new, completely independent copy of the given XArray, using
    127    the existing allocation function to allocate the new space.
    128    Returns NULL if the allocation function didn't manage to allocate
    129    space (but did return NULL rather than merely abort.)  Space for
    130    the clone (and all additions to it) is billed to 'cc' unless that
    131    is NULL, in which case the parent's cost-center is used. */
    132 extern XArray* VG_(cloneXA)( HChar* cc, XArray* xa );
    133 
    134 /* Get the raw array and size so callers can index it really fast.
    135    This is dangerous in the sense that there's no range or
    136    anything-else checking.  It's also dangerous in that if
    137    VG_(addToXA) is used, the contents may be re-located without
    138    warning, hence making the contents address returned here
    139    invalid. */
    140 extern void VG_(getContentsXA_UNSAFE)( XArray* sr,
    141                                        /*OUT*/void** ctsP,
    142                                        /*OUT*/Word*  usedP );
    143 
    144 /* Convenience function: printf into an XArray of HChar, adding stuff
    145    at the end.  This is very convenient for concocting arbitrary
    146    length printf output in an XArray.  Note that the resulting string
    147    is NOT zero-terminated. */
    148 extern void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
    149                          PRINTF_CHECK(2, 3);
    150 
    151 #endif   // __PUB_TOOL_XARRAY_H
    152 
    153 /*--------------------------------------------------------------------*/
    154 /*--- end                                        pub_tool_xarray.h ---*/
    155 /*--------------------------------------------------------------------*/
    156