1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
/*--------------------------------------------------------------------*/
/*--- An expandable array implementation. pub_tool_xarray.h ---*/
/*--------------------------------------------------------------------*/
/*
This file is part of Valgrind, a dynamic binary instrumentation
framework.
Copyright (C) 2007-2009 OpenWorks LLP
info@open-works.co.uk
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307, USA.
The GNU General Public License is contained in the file COPYING.
*/
#ifndef __PUB_TOOL_XARRAY_H
#define __PUB_TOOL_XARRAY_H
//--------------------------------------------------------------------
// PURPOSE: Provides a simple but useful structure, which is an array
// in which elements can be added at the end. The array is expanded
// as needed by multiplying its size by a constant factor (usually 2).
// This gives amortised O(1) insertion cost, and, following sorting,
// the usual O(log N) binary search cost. Arbitrary element sizes
// are allowed; the comparison function for sort/lookup can be changed
// at any time, and duplicates (modulo the comparison function) are
// allowed.
//--------------------------------------------------------------------
/* It's an abstract type. Bwaha. */
typedef struct _XArray XArray;
/* Create new XArray, using given allocation and free function, and
for elements of the specified size. Alloc fn must not fail (that
is, if it returns it must have succeeded.) */
extern XArray* VG_(newXA) ( void*(*alloc_fn)(HChar*,SizeT),
HChar* cc,
void(*free_fn)(void*),
Word elemSzB );
/* Free all memory associated with an XArray. */
extern void VG_(deleteXA) ( XArray* );
/* Set the comparison function for this XArray. This clears an
internal 'array is sorted' flag, which means you must call sortXA
before making further queries with lookupXA. */
extern void VG_(setCmpFnXA) ( XArray*, Int (*compar)(void*,void*) );
/* Add an element to an XArray. Element is copied into the XArray.
Index at which it was added is returned. Note this will be
invalidated if the array is later sortXA'd. */
extern Word VG_(addToXA) ( XArray*, void* elem );
/* Add a sequence of bytes to an XArray of bytes. Asserts if nbytes
is negative or the array's element size is not 1. Returns the
index at which the first byte was added. */
extern Word VG_(addBytesToXA) ( XArray* xao, void* bytesV, Word nbytes );
/* Sort an XArray using its comparison function, if set; else bomb.
Probably not a stable sort w.r.t. equal elements module cmpFn. */
extern void VG_(sortXA) ( XArray* );
/* Lookup (by binary search) 'key' in the array. Set *first to be the
index of the first, and *last to be the index of the last matching
value found. If any values are found, return True, else return
False, and don't change *first or *last. Bomb if the array is not
sorted. */
extern Bool VG_(lookupXA) ( XArray*, void* key,
/*OUT*/Word* first, /*OUT*/Word* last );
/* How elements are there in this XArray now? */
extern Word VG_(sizeXA) ( XArray* );
/* Index into the XArray. Checks bounds and bombs if the index is
invalid. What this returns is the address of the specified element
in the array, not (of course) the element itself. Note that the
element may get moved by subsequent addToXAs/sortXAs, so you should
copy it out immediately and not regard its address as unchanging.
Note also that indexXA will of course not return NULL if it
succeeds. */
extern void* VG_(indexXA) ( XArray*, Word );
/* Drop the last n elements of an XArray. Bombs if there are less
than n elements in the array. */
extern void VG_(dropTailXA) ( XArray*, Word );
/* Make a new, completely independent copy of the given XArray, using
the existing allocation function to allocate the new space.
Returns NULL if the allocation function didn't manage to allocate
space (but did return NULL rather than merely abort.) Space for
the clone (and all additions to it) is billed to 'cc' unless that
is NULL, in which case the parent's cost-center is used. */
extern XArray* VG_(cloneXA)( HChar* cc, XArray* xa );
#endif // __PUB_TOOL_XARRAY_H
/*--------------------------------------------------------------------*/
/*--- end pub_tool_xarray.h ---*/
/*--------------------------------------------------------------------*/
|
