include/pub_tool_xarray.h

   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-2017 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, see <http://www.gnu.org/licenses/>.
  25
  26    The GNU General Public License is contained in the file COPYING.
  27 */
  28
  29 #ifndef __PUB_TOOL_XARRAY_H
  30 #define __PUB_TOOL_XARRAY_H
  31
  32 #include "pub_tool_basics.h"    // Word
  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 typedef Int (*XACmpFn_t)(const void *, const void *);
  50
  51 /* Create new XArray, using given allocation and free function, and
  52    for elements of the specified size.  alloc_fn must not return NULL (that
  53    is, if it returns it must have succeeded.)
  54    This function never returns NULL. */
  55 extern XArray* VG_(newXA) ( Alloc_Fn_t alloc_fn,
  56                             const HChar* cc,
  57                             Free_Fn_t free_fn,
  58                             Word elemSzB );
  59
  60 /* Free all memory associated with an XArray. */
  61 extern void VG_(deleteXA) ( XArray* );
  62
  63 /* Set the comparison function for this XArray.  This clears an
  64    internal 'array is sorted' flag, which means you must call sortXA
  65    before making further queries with lookupXA. */
  66 extern void VG_(setCmpFnXA) ( XArray*, XACmpFn_t);
  67
  68 /* Add an element to an XArray.  Element is copied into the XArray.
  69    Index at which it was added is returned.  Note this will be
  70    invalidated if the array is later sortXA'd. */
  71 extern Word VG_(addToXA) ( XArray*, const void* elem );
  72
  73 /* Add a sequence of bytes to an XArray of bytes.  Asserts if nbytes
  74    is negative or the array's element size is not 1.  Returns the
  75    index at which the first byte was added. */
  76 extern Word VG_(addBytesToXA) ( XArray* xao, const void* bytesV, Word nbytes );
  77
  78 /* Sort an XArray using its comparison function, if set; else bomb.
  79    Probably not a stable sort w.r.t. equal elements module cmpFn. */
  80 extern void VG_(sortXA) ( XArray* );
  81
  82 /* Lookup (by binary search) 'key' in the array.  Set *first to be the
  83    index of the first, and *last to be the index of the last matching
  84    value found.  If any values are found, return True, else return
  85    False, and don't change *first or *last.  first and/or last may be
  86    NULL.  Bomb if the array is not sorted. */
  87 extern Bool VG_(lookupXA) ( const XArray*, const void* key,
  88                             /*OUT*/Word* first, /*OUT*/Word* last );
  89
  90 /* A version of VG_(lookupXA) in which you can specify your own
  91    comparison function.  This is unsafe in the sense that if the array
  92    is not totally ordered as defined by your comparison function, then
  93    this function may loop indefinitely, so it is up to you to ensure
  94    that the array is suitably ordered.  This is in comparison to
  95    VG_(lookupXA), which refuses to do anything (asserts) unless the
  96    array has first been sorted using the same comparison function as
  97    is being used for the lookup. */
  98 extern Bool VG_(lookupXA_UNSAFE) ( const XArray* xao, const void* key,
  99                                    /*OUT*/Word* first, /*OUT*/Word* last,
 100                                    XACmpFn_t cmpFn );
 101
 102 /* How elements are there in this XArray now? */
 103 extern Word VG_(sizeXA) ( const XArray* );
 104
 105 /* If you know how many elements an XArray will have, you can
 106    optimise memory usage and number of reallocation needed
 107    to insert these elements. The call to VG_(hintSizeXA) must be
 108    done just after the call to VG_(newXA), before any element
 109    has been inserted. */
 110 extern void VG_(hintSizeXA) ( XArray*, Word);
 111
 112 /* Index into the XArray.  Checks bounds and bombs if the index is
 113    invalid.  What this returns is the address of the specified element
 114    in the array, not (of course) the element itself.  Note that the
 115    element may get moved by subsequent calls to addToXA / sortXA /
 116    insertIndexXA, so you should copy it out immediately and not regard
 117    its address as unchanging.  Note also that indexXA will of course
 118    not return NULL if it succeeds. */
 119 extern void* VG_(indexXA) ( const XArray*, Word );
 120
 121 /* Drop the last n elements of an XArray.  Bombs if there are less
 122    than n elements in the array.  This is an O(1) operation. */
 123 extern void VG_(dropTailXA) ( XArray*, Word );
 124
 125 /* Drop the first n elements of an XArray.  Bombs if there are less
 126    than n elements in the array.  This is an O(N) operation, where N
 127    is the number of elements remaining in the XArray. */
 128 extern void VG_(dropHeadXA) ( XArray*, Word );
 129
 130 /* Remove the specified element of an XArray, and slide all elements
 131    beyond it back one place.  This is an O(N) operation, where N is
 132    the number of elements after the specified element, in the
 133    array. */
 134 extern void VG_(removeIndexXA)( XArray*, Word );
 135
 136 /* Insert an element into an XArray at the given index.  The existing
 137    element at the index and all above it are slid upwards one slot so
 138    as to make space.  Element is copied into the XArray.  This is an
 139    O(N) operation, when N is the number of elements after the
 140    specified element, in the array. */
 141 extern void VG_(insertIndexXA)( XArray*, Word, const void* elem );
 142
 143 /* Replace the element of an XArray at the given index with a copy
 144    of the new element.  This is an O(1) operation.
 145    Compared to the caller doing:
 146           *(T*)VG_(indexXA)(arr, index) = new_value;
 147    this function will also mark the array as unsorted.  */
 148 extern void VG_(replaceIndexXA)( XArray*, Word, const void* elem );
 149
 150
 151 /* Make a new, completely independent copy of the given XArray, using
 152    the existing allocation function to allocate the new space.
 153    Space for the clone (and all additions to it) is billed to 'cc' unless
 154    that is NULL, in which case the parent's cost-center is used.
 155    Ths function never returns NULL. */
 156 extern XArray* VG_(cloneXA)( const HChar* cc, const XArray* xa );
 157
 158 /* Get the raw array and size so callers can index it really fast.
 159    This is dangerous in the sense that there's no range or
 160    anything-else checking.  It's also dangerous in that if
 161    VG_(addToXA) is used, the contents may be re-located without
 162    warning, hence making the contents address returned here
 163    invalid. */
 164 extern void VG_(getContentsXA_UNSAFE)( XArray* sr,
 165                                        /*OUT*/void** ctsP,
 166                                        /*OUT*/Word*  usedP );
 167
 168 /* Convenience function: printf into an XArray of HChar, adding stuff
 169    at the end.  This is very convenient for concocting arbitrary
 170    length printf output in an XArray.  Note that the resulting string
 171    is NOT zero-terminated. */
 172 extern void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
 173                          PRINTF_CHECK(2, 3);
 174
 175 /* Convenience function: linear search in an XArray of HChar*. */
 176 extern Bool VG_(strIsMemberXA)(const XArray* xa, const HChar* str );
 177 #endif   // __PUB_TOOL_XARRAY_H
 178
 179 /*--------------------------------------------------------------------*/
 180 /*--- end                                        pub_tool_xarray.h ---*/
 181 /*--------------------------------------------------------------------*/