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