include/valgrind/pub_tool_xarray.h

0001
0002 /*--------------------------------------------------------------------*/
0003 /*--- An expandable array implementation.        pub_tool_xarray.h ---*/
0004 /*--------------------------------------------------------------------*/
0005
0006 /*
0007    This file is part of Valgrind, a dynamic binary instrumentation
0008    framework.
0009
0010    Copyright (C) 2007-2017 OpenWorks LLP
0011       info@open-works.co.uk
0012
0013    This program is free software; you can redistribute it and/or
0014    modify it under the terms of the GNU General Public License as
0015    published by the Free Software Foundation; either version 2 of the
0016    License, or (at your option) any later version.
0017
0018    This program is distributed in the hope that it will be useful, but
0019    WITHOUT ANY WARRANTY; without even the implied warranty of
0020    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0021    General Public License for more details.
0022
0023    You should have received a copy of the GNU General Public License
0024    along with this program; if not, see <http://www.gnu.org/licenses/>.
0025
0026    The GNU General Public License is contained in the file COPYING.
0027 */
0028
0029 #ifndef __PUB_TOOL_XARRAY_H
0030 #define __PUB_TOOL_XARRAY_H
0031
0032 #include "pub_tool_basics.h"    // Word
0033
0034 //--------------------------------------------------------------------
0035 // PURPOSE: Provides a simple but useful structure, which is an array
0036 // in which elements can be added at the end.  The array is expanded
0037 // as needed by multiplying its size by a constant factor (usually 2).
0038 // This gives amortised O(1) insertion cost, and, following sorting,
0039 // the usual O(log N) binary search cost.  Arbitrary element sizes
0040 // are allowed; the comparison function for sort/lookup can be changed
0041 // at any time, and duplicates (modulo the comparison function) are
0042 // allowed.
0043 //--------------------------------------------------------------------
0044
0045
0046 /* It's an abstract type.  Bwaha. */
0047 typedef  struct _XArray  XArray;
0048
0049 typedef Int (*XACmpFn_t)(const void *, const void *);
0050
0051 /* Create new XArray, using given allocation and free function, and
0052    for elements of the specified size.  alloc_fn must not return NULL (that
0053    is, if it returns it must have succeeded.)
0054    This function never returns NULL. */
0055 extern XArray* VG_(newXA) ( Alloc_Fn_t alloc_fn,
0056                             const HChar* cc,
0057                             Free_Fn_t free_fn,
0058                             Word elemSzB );
0059
0060 /* Free all memory associated with an XArray. */
0061 extern void VG_(deleteXA) ( XArray* );
0062
0063 /* Set the comparison function for this XArray.  This clears an
0064    internal 'array is sorted' flag, which means you must call sortXA
0065    before making further queries with lookupXA. */
0066 extern void VG_(setCmpFnXA) ( XArray*, XACmpFn_t);
0067
0068 /* Add an element to an XArray.  Element is copied into the XArray.
0069    Index at which it was added is returned.  Note this will be
0070    invalidated if the array is later sortXA'd. */
0071 extern Word VG_(addToXA) ( XArray*, const void* elem );
0072
0073 /* Add a sequence of bytes to an XArray of bytes.  Asserts if nbytes
0074    is negative or the array's element size is not 1.  Returns the
0075    index at which the first byte was added. */
0076 extern Word VG_(addBytesToXA) ( XArray* xao, const void* bytesV, Word nbytes );
0077
0078 /* Sort an XArray using its comparison function, if set; else bomb.
0079    Probably not a stable sort w.r.t. equal elements module cmpFn. */
0080 extern void VG_(sortXA) ( XArray* );
0081
0082 /* Lookup (by binary search) 'key' in the array.  Set *first to be the
0083    index of the first, and *last to be the index of the last matching
0084    value found.  If any values are found, return True, else return
0085    False, and don't change *first or *last.  first and/or last may be
0086    NULL.  Bomb if the array is not sorted. */
0087 extern Bool VG_(lookupXA) ( const XArray*, const void* key,
0088                             /*OUT*/Word* first, /*OUT*/Word* last );
0089
0090 /* A version of VG_(lookupXA) in which you can specify your own
0091    comparison function.  This is unsafe in the sense that if the array
0092    is not totally ordered as defined by your comparison function, then
0093    this function may loop indefinitely, so it is up to you to ensure
0094    that the array is suitably ordered.  This is in comparison to
0095    VG_(lookupXA), which refuses to do anything (asserts) unless the
0096    array has first been sorted using the same comparison function as
0097    is being used for the lookup. */
0098 extern Bool VG_(lookupXA_UNSAFE) ( const XArray* xao, const void* key,
0099                                    /*OUT*/Word* first, /*OUT*/Word* last,
0100                                    XACmpFn_t cmpFn );
0101
0102 /* How elements are there in this XArray now? */
0103 extern Word VG_(sizeXA) ( const XArray* );
0104
0105 /* If you know how many elements an XArray will have, you can
0106    optimise memory usage and number of reallocation needed
0107    to insert these elements. The call to VG_(hintSizeXA) must be
0108    done just after the call to VG_(newXA), before any element
0109    has been inserted. */
0110 extern void VG_(hintSizeXA) ( XArray*, Word);
0111
0112 /* Index into the XArray.  Checks bounds and bombs if the index is
0113    invalid.  What this returns is the address of the specified element
0114    in the array, not (of course) the element itself.  Note that the
0115    element may get moved by subsequent calls to addToXA / sortXA /
0116    insertIndexXA, so you should copy it out immediately and not regard
0117    its address as unchanging.  Note also that indexXA will of course
0118    not return NULL if it succeeds. */
0119 extern void* VG_(indexXA) ( const XArray*, Word );
0120
0121 /* Drop the last n elements of an XArray.  Bombs if there are less
0122    than n elements in the array.  This is an O(1) operation. */
0123 extern void VG_(dropTailXA) ( XArray*, Word );
0124
0125 /* Drop the first n elements of an XArray.  Bombs if there are less
0126    than n elements in the array.  This is an O(N) operation, where N
0127    is the number of elements remaining in the XArray. */
0128 extern void VG_(dropHeadXA) ( XArray*, Word );
0129
0130 /* Remove the specified element of an XArray, and slide all elements
0131    beyond it back one place.  This is an O(N) operation, where N is
0132    the number of elements after the specified element, in the
0133    array. */
0134 extern void VG_(removeIndexXA)( XArray*, Word );
0135
0136 /* Insert an element into an XArray at the given index.  The existing
0137    element at the index and all above it are slid upwards one slot so
0138    as to make space.  Element is copied into the XArray.  This is an
0139    O(N) operation, when N is the number of elements after the
0140    specified element, in the array. */
0141 extern void VG_(insertIndexXA)( XArray*, Word, const void* elem );
0142
0143 /* Replace the element of an XArray at the given index with a copy
0144    of the new element.  This is an O(1) operation.
0145    Compared to the caller doing:
0146           *(T*)VG_(indexXA)(arr, index) = new_value;
0147    this function will also mark the array as unsorted.  */
0148 extern void VG_(replaceIndexXA)( XArray*, Word, const void* elem );
0149
0150
0151 /* Make a new, completely independent copy of the given XArray, using
0152    the existing allocation function to allocate the new space.
0153    Space for the clone (and all additions to it) is billed to 'cc' unless
0154    that is NULL, in which case the parent's cost-center is used.
0155    Ths function never returns NULL. */
0156 extern XArray* VG_(cloneXA)( const HChar* cc, const XArray* xa );
0157
0158 /* Get the raw array and size so callers can index it really fast.
0159    This is dangerous in the sense that there's no range or
0160    anything-else checking.  It's also dangerous in that if
0161    VG_(addToXA) is used, the contents may be re-located without
0162    warning, hence making the contents address returned here
0163    invalid. */
0164 extern void VG_(getContentsXA_UNSAFE)( XArray* sr,
0165                                        /*OUT*/void** ctsP,
0166                                        /*OUT*/Word*  usedP );
0167
0168 /* Convenience function: printf into an XArray of HChar, adding stuff
0169    at the end.  This is very convenient for concocting arbitrary
0170    length printf output in an XArray.  Note that the resulting string
0171    is NOT zero-terminated. */
0172 extern void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
0173                          PRINTF_CHECK(2, 3);
0174
0175 /* Convenience function: linear search in an XArray of HChar*. */
0176 extern Bool VG_(strIsMemberXA)(const XArray* xa, const HChar* str );
0177 #endif   // __PUB_TOOL_XARRAY_H
0178
0179 /*--------------------------------------------------------------------*/
0180 /*--- end                                        pub_tool_xarray.h ---*/
0181 /*--------------------------------------------------------------------*/