pub_tool_xarray.h revision b32f58018498ea2225959b0ba11c18f0c433deef 
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-2011 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//--------------------------------------------------------------------
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. */
47typedef  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.) */
52extern 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. */
58extern 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. */
63extern 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. */
68extern 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. */
73extern 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. */
77extern 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. */
84extern 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. */
95extern 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? */
100extern 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. */
109extern 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. */
113extern 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. */
118extern void VG_(dropHeadXA) ( XArray*, Word );
119
120/* Make a new, completely independent copy of the given XArray, using
121   the existing allocation function to allocate the new space.
122   Returns NULL if the allocation function didn't manage to allocate
123   space (but did return NULL rather than merely abort.)  Space for
124   the clone (and all additions to it) is billed to 'cc' unless that
125   is NULL, in which case the parent's cost-center is used. */
126extern XArray* VG_(cloneXA)( HChar* cc, XArray* xa );
127
128/* Get the raw array and size so callers can index it really fast.
129   This is dangerous in the sense that there's no range or
130   anything-else checking.  It's also dangerous in that if
131   VG_(addToXA) is used, the contents may be re-located without
132   warning, hence making the contents address returned here
133   invalid. */
134extern void VG_(getContentsXA_UNSAFE)( XArray* sr,
135                                       /*OUT*/void** ctsP,
136                                       /*OUT*/Word*  usedP );
137
138/* Convenience function: printf into an XArray of HChar, adding stuff
139   at the end.  This is very convenient for concocting arbitrary
140   length printf output in an XArray.  Note that the resulting string
141   is NOT zero-terminated. */
142extern void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
143                         PRINTF_CHECK(2, 3);
144
145#endif   // __PUB_TOOL_XARRAY_H
146
147/*--------------------------------------------------------------------*/
148/*--- end                                        pub_tool_xarray.h ---*/
149/*--------------------------------------------------------------------*/
150