1
2 /*--------------------------------------------------------------------*/
3 /*--- An expandable array implementation. m_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 #include "pub_core_basics.h"
32 #include "pub_core_libcbase.h"
33 #include "pub_core_libcassert.h"
34 #include "pub_core_libcprint.h"
35 #include "pub_core_xarray.h" /* self */
36
37
38 /* See pub_tool_xarray.h for details of what this is all about. */
39
40 struct _XArray {
41 void* (*alloc_fn) ( const HChar*, SizeT ); /* alloc fn (nofail) */
42 const HChar* cc; /* cost centre for alloc */
43 void (*free_fn) ( void* ); /* free fn */
44 Int (*cmpFn) ( const void*, const void* ); /* cmp fn (may be NULL) */
45 Word elemSzB; /* element size in bytes */
46 void* arr; /* pointer to elements */
47 Word usedsizeE; /* # used elements in arr */
48 Word totsizeE; /* max size of arr, in elements */
49 Bool sorted; /* is it sorted? */
50 };
51
52
VG_(newXA)53 XArray* VG_(newXA) ( void*(*alloc_fn)(const HChar*,SizeT),
54 const HChar* cc,
55 void(*free_fn)(void*),
56 Word elemSzB )
57 {
58 XArray* xa;
59 /* Implementation relies on Word being signed and (possibly)
60 on SizeT being unsigned. */
61 vg_assert( sizeof(Word) == sizeof(void*) );
62 vg_assert( ((Word)(-1)) < ((Word)(0)) );
63 vg_assert( ((SizeT)(-1)) > ((SizeT)(0)) );
64 /* check user-supplied info .. */
65 vg_assert(alloc_fn);
66 vg_assert(free_fn);
67 vg_assert(elemSzB > 0);
68 xa = alloc_fn( cc, sizeof(struct _XArray) );
69 xa->alloc_fn = alloc_fn;
70 xa->cc = cc;
71 xa->free_fn = free_fn;
72 xa->cmpFn = NULL;
73 xa->elemSzB = elemSzB;
74 xa->usedsizeE = 0;
75 xa->totsizeE = 0;
76 xa->sorted = False;
77 xa->arr = NULL;
78 return xa;
79 }
80
VG_(cloneXA)81 XArray* VG_(cloneXA)( const HChar* cc, const XArray* xa )
82 {
83 XArray* nyu;
84 const HChar* nyu_cc;
85 vg_assert(xa);
86 vg_assert(xa->alloc_fn);
87 vg_assert(xa->free_fn);
88 vg_assert(xa->elemSzB >= 1);
89 nyu_cc = cc ? cc : xa->cc;
90 nyu = xa->alloc_fn( nyu_cc, sizeof(struct _XArray) );
91
92 /* Copy everything verbatim ... */
93 *nyu = *xa;
94 nyu->cc = nyu_cc;
95 /* ... except we have to clone the contents-array */
96 if (nyu->arr) {
97 /* Restrict the total size of the new array to its current
98 actual size. That means we don't waste space copying the
99 unused tail of the original. The tradeoff is that it
100 guarantees we will have to resize the child if even one more
101 element is later added to it, unfortunately. */
102 nyu->totsizeE = nyu->usedsizeE;
103 /* and allocate .. */
104 nyu->arr = nyu->alloc_fn( nyu->cc, nyu->totsizeE * nyu->elemSzB );
105 VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB );
106 }
107 /* We're done! */
108 return nyu;
109 }
110
VG_(deleteXA)111 void VG_(deleteXA) ( XArray* xa )
112 {
113 vg_assert(xa);
114 vg_assert(xa->free_fn);
115 if (xa->arr)
116 xa->free_fn(xa->arr);
117 xa->free_fn(xa);
118 }
119
VG_(setCmpFnXA)120 void VG_(setCmpFnXA) ( XArray* xa, XACmpFn_t compar )
121 {
122 vg_assert(xa);
123 vg_assert(compar);
124 xa->cmpFn = compar;
125 xa->sorted = False;
126 }
127
VG_(indexXA)128 inline void* VG_(indexXA) ( const XArray* xa, Word n )
129 {
130 vg_assert(xa);
131 /* vg_assert(n >= 0); If n negative, the UWord conversion will make
132 it bigger than usedsizeE, which is verified to be non negative when
133 xa is modified. */
134 vg_assert((UWord)n < (UWord)xa->usedsizeE);
135 return ((char*)xa->arr) + n * xa->elemSzB;
136 }
137
VG_(hintSizeXA)138 void VG_(hintSizeXA) ( XArray* xa, Word n)
139 {
140 /* Currently, we support giving a size hint only just after the
141 call to VG_(newXA). So, we could instead have done
142 a function VG_(newXA_with_SizeHint). The separate VG_(hintSizeXA)
143 function is however chosen as we might one day accept to
144 give a size hint after having added elements. That could be useful
145 for reducing the size of an xarray to just the size currently needed
146 or to give a size hint when it is known that a lot more elements
147 are needed or when the final nr of elements is known. */
148 vg_assert(xa);
149 vg_assert(xa->usedsizeE == 0);
150 vg_assert(xa->totsizeE == 0);
151 vg_assert(!xa->arr);
152 xa->arr = xa->alloc_fn(xa->cc, n * xa->elemSzB);
153 xa->totsizeE = n;
154 }
155
ensureSpaceXA(XArray * xa)156 static inline void ensureSpaceXA ( XArray* xa )
157 {
158 if (xa->usedsizeE == xa->totsizeE) {
159 void* tmp;
160 Word newsz;
161 if (xa->totsizeE == 0)
162 vg_assert(!xa->arr);
163 if (xa->totsizeE > 0)
164 vg_assert(xa->arr);
165 if (xa->totsizeE == 0) {
166 /* No point in having tiny (eg) 2-byte allocations for the
167 element array, since all allocs are rounded up to 8 anyway.
168 Hence increase the initial array size for tiny elements in
169 an attempt to avoid reallocations of size 2, 4, 8 if the
170 array does start to fill up. */
171 if (xa->elemSzB == 1) newsz = 8;
172 else if (xa->elemSzB == 2) newsz = 4;
173 else newsz = 2;
174 } else {
175 newsz = 2 + (3 * xa->totsizeE) / 2; /* 2 * xa->totsizeE; */
176 }
177 if (0 && xa->totsizeE >= 10000)
178 VG_(printf)("addToXA: increasing from %ld to %ld\n",
179 xa->totsizeE, newsz);
180 tmp = xa->alloc_fn(xa->cc, newsz * xa->elemSzB);
181 if (xa->usedsizeE > 0)
182 VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB);
183 if (xa->arr)
184 xa->free_fn(xa->arr);
185 xa->arr = tmp;
186 xa->totsizeE = newsz;
187 }
188 }
189
VG_(addToXA)190 Word VG_(addToXA) ( XArray* xa, const void* elem )
191 {
192 vg_assert(xa);
193 vg_assert(elem);
194 vg_assert(xa->totsizeE >= 0);
195 vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
196 ensureSpaceXA( xa );
197 vg_assert(xa->usedsizeE < xa->totsizeE);
198 vg_assert(xa->arr);
199 VG_(memcpy)( ((UChar*)xa->arr) + xa->usedsizeE * xa->elemSzB,
200 elem, xa->elemSzB );
201 xa->usedsizeE++;
202 xa->sorted = False;
203 return xa->usedsizeE-1;
204 }
205
VG_(addBytesToXA)206 Word VG_(addBytesToXA) ( XArray* xa, const void* bytesV, Word nbytes )
207 {
208 Word r, i;
209 vg_assert(xa);
210 vg_assert(xa->elemSzB == 1);
211 vg_assert(nbytes >= 0);
212 vg_assert(xa->totsizeE >= 0);
213 vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
214 r = xa->usedsizeE;
215 for (i = 0; i < nbytes; i++) {
216 ensureSpaceXA( xa );
217 vg_assert(xa->usedsizeE < xa->totsizeE);
218 vg_assert(xa->arr);
219 * (((UChar*)xa->arr) + xa->usedsizeE) = ((const UChar*)bytesV)[i];
220 xa->usedsizeE++;
221 }
222 xa->sorted = False;
223 return r;
224 }
225
VG_(sortXA)226 void VG_(sortXA) ( XArray* xa )
227 {
228 vg_assert(xa);
229 vg_assert(xa->cmpFn);
230 VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn );
231 xa->sorted = True;
232 }
233
VG_(lookupXA_UNSAFE)234 Bool VG_(lookupXA_UNSAFE) ( const XArray* xa, const void* key,
235 /*OUT*/Word* first, /*OUT*/Word* last,
236 Int(*cmpFn)(const void*, const void*) )
237 {
238 Word lo, mid, hi, cres;
239 void* midv;
240 vg_assert(xa);
241 lo = 0;
242 hi = xa->usedsizeE-1;
243 while (True) {
244 /* current unsearched space is from lo to hi, inclusive. */
245 if (lo > hi) return False; /* not found */
246 mid = (lo + hi) / 2;
247 midv = VG_(indexXA)( xa, mid );
248 cres = cmpFn( key, midv );
249 if (cres < 0) { hi = mid-1; continue; }
250 if (cres > 0) { lo = mid+1; continue; }
251 /* Found it, at mid. See how far we can expand this. */
252 vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
253 vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
254 if (first) {
255 *first = mid;
256 while (*first > 0
257 && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) {
258 (*first)--;
259 }
260 }
261 if (last) {
262 *last = mid;
263 while (*last < xa->usedsizeE-1
264 && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) {
265 (*last)++;
266 }
267 }
268 return True;
269 }
270 }
271
VG_(lookupXA)272 Bool VG_(lookupXA) ( const XArray* xa, const void* key,
273 /*OUT*/Word* first, /*OUT*/Word* last )
274 {
275 vg_assert(xa);
276 vg_assert(xa->cmpFn);
277 vg_assert(xa->sorted);
278 return VG_(lookupXA_UNSAFE)(xa, key, first, last, xa->cmpFn);
279 }
280
VG_(sizeXA)281 Word VG_(sizeXA) ( const XArray* xa )
282 {
283 vg_assert(xa);
284 return xa->usedsizeE;
285 }
286
VG_(dropTailXA)287 void VG_(dropTailXA) ( XArray* xa, Word n )
288 {
289 vg_assert(xa);
290 vg_assert(n >= 0);
291 vg_assert(n <= xa->usedsizeE);
292 xa->usedsizeE -= n;
293 }
294
VG_(dropHeadXA)295 void VG_(dropHeadXA) ( XArray* xa, Word n )
296 {
297 vg_assert(xa);
298 vg_assert(n >= 0);
299 vg_assert(n <= xa->usedsizeE);
300 if (n == 0) {
301 return;
302 }
303 if (n == xa->usedsizeE) {
304 xa->usedsizeE = 0;
305 return;
306 }
307 vg_assert(n > 0);
308 vg_assert(xa->usedsizeE - n > 0);
309 VG_(memcpy)( (char*)xa->arr,
310 ((char*)xa->arr) + n * xa->elemSzB,
311 (xa->usedsizeE - n) * xa->elemSzB );
312 xa->usedsizeE -= n;
313 }
314
VG_(removeIndexXA)315 void VG_(removeIndexXA)( XArray* xa, Word n )
316 {
317 vg_assert(xa);
318 vg_assert(n >= 0);
319 vg_assert(n < xa->usedsizeE);
320 if (n+1 < xa->usedsizeE) {
321 VG_(memmove)( ((char*)xa->arr) + (n+0) * xa->elemSzB,
322 ((char*)xa->arr) + (n+1) * xa->elemSzB,
323 (xa->usedsizeE - n - 1) * xa->elemSzB );
324 }
325 xa->usedsizeE--;
326 }
327
VG_(insertIndexXA)328 void VG_(insertIndexXA)( XArray* xa, Word n, const void* elem )
329 {
330 vg_assert(xa);
331 vg_assert(n >= 0);
332 vg_assert(n <= xa->usedsizeE);
333 vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
334 ensureSpaceXA( xa );
335 vg_assert(xa->usedsizeE < xa->totsizeE);
336 vg_assert(xa->arr);
337 if (n < xa->usedsizeE) {
338 VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB,
339 ((char*)xa->arr) + (n+0) * xa->elemSzB,
340 (xa->usedsizeE - n) * xa->elemSzB );
341 }
342 VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB,
343 elem, xa->elemSzB );
344 xa->usedsizeE++;
345 xa->sorted = False;
346 }
347
VG_(getContentsXA_UNSAFE)348 void VG_(getContentsXA_UNSAFE)( XArray* xa,
349 /*OUT*/void** ctsP,
350 /*OUT*/Word* usedP )
351 {
352 vg_assert(xa);
353 *ctsP = (void*)xa->arr;
354 *usedP = xa->usedsizeE;
355 }
356
357 /* --------- Printeffery --------- */
358
add_char_to_XA(HChar c,void * opaque)359 static void add_char_to_XA ( HChar c, void* opaque )
360 {
361 XArray* dst = (XArray*)opaque;
362 (void) VG_(addBytesToXA)( dst, &c, 1 );
363 }
364
VG_(xaprintf)365 void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
366 {
367 va_list vargs;
368 va_start(vargs, format);
369 VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
370 va_end(vargs);
371 }
372
373
374 /*--------------------------------------------------------------------*/
375 /*--- end m_xarray.c ---*/
376 /*--------------------------------------------------------------------*/
377