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-2017 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 Alloc_Fn_t alloc_fn; /* alloc fn (nofail) */
42 const HChar* cc; /* cost centre for alloc */
43 Free_Fn_t free_fn; /* 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) ( Alloc_Fn_t alloc_fn,
54 const HChar* cc,
55 Free_Fn_t free_fn,
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
281 /* FIXME: This function should return an unsigned value because the number
282 of elements cannot be negative. Unfortunately, making the change causes
283 a lot of ripple. */
VG_(sizeXA)284 Word VG_(sizeXA) ( const XArray* xa )
285 {
286 vg_assert(xa);
287 return xa->usedsizeE;
288 }
289
VG_(dropTailXA)290 void VG_(dropTailXA) ( XArray* xa, Word n )
291 {
292 vg_assert(xa);
293 vg_assert(n >= 0);
294 vg_assert(n <= xa->usedsizeE);
295 xa->usedsizeE -= n;
296 }
297
VG_(dropHeadXA)298 void VG_(dropHeadXA) ( XArray* xa, Word n )
299 {
300 vg_assert(xa);
301 vg_assert(n >= 0);
302 vg_assert(n <= xa->usedsizeE);
303 if (n == 0) {
304 return;
305 }
306 if (n == xa->usedsizeE) {
307 xa->usedsizeE = 0;
308 return;
309 }
310 vg_assert(n > 0);
311 vg_assert(xa->usedsizeE - n > 0);
312 VG_(memcpy)( (char*)xa->arr,
313 ((char*)xa->arr) + n * xa->elemSzB,
314 (xa->usedsizeE - n) * xa->elemSzB );
315 xa->usedsizeE -= n;
316 }
317
VG_(removeIndexXA)318 void VG_(removeIndexXA)( XArray* xa, Word n )
319 {
320 vg_assert(xa);
321 vg_assert(n >= 0);
322 vg_assert(n < xa->usedsizeE);
323 if (n+1 < xa->usedsizeE) {
324 VG_(memmove)( ((char*)xa->arr) + (n+0) * xa->elemSzB,
325 ((char*)xa->arr) + (n+1) * xa->elemSzB,
326 (xa->usedsizeE - n - 1) * xa->elemSzB );
327 }
328 xa->usedsizeE--;
329 }
330
VG_(insertIndexXA)331 void VG_(insertIndexXA)( XArray* xa, Word n, const void* elem )
332 {
333 vg_assert(xa);
334 vg_assert(n >= 0);
335 vg_assert(n <= xa->usedsizeE);
336 vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
337 ensureSpaceXA( xa );
338 vg_assert(xa->usedsizeE < xa->totsizeE);
339 vg_assert(xa->arr);
340 if (n < xa->usedsizeE) {
341 VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB,
342 ((char*)xa->arr) + (n+0) * xa->elemSzB,
343 (xa->usedsizeE - n) * xa->elemSzB );
344 }
345 VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB,
346 elem, xa->elemSzB );
347 xa->usedsizeE++;
348 xa->sorted = False;
349 }
350
VG_(getContentsXA_UNSAFE)351 void VG_(getContentsXA_UNSAFE)( XArray* xa,
352 /*OUT*/void** ctsP,
353 /*OUT*/Word* usedP )
354 {
355 vg_assert(xa);
356 *ctsP = (void*)xa->arr;
357 *usedP = xa->usedsizeE;
358 }
359
360 /* --------- Printeffery --------- */
361
add_char_to_XA(HChar c,void * opaque)362 static void add_char_to_XA ( HChar c, void* opaque )
363 {
364 XArray* dst = (XArray*)opaque;
365 (void) VG_(addBytesToXA)( dst, &c, 1 );
366 }
367
VG_(xaprintf)368 void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
369 {
370 va_list vargs;
371 va_start(vargs, format);
372 VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
373 va_end(vargs);
374 }
375
VG_(strIsMemberXA)376 Bool VG_(strIsMemberXA)(const XArray* xa, const HChar* str )
377 {
378 Word i;
379 HChar** members = (HChar**)xa->arr;
380
381 for (i = 0; i < xa->usedsizeE; i++)
382 if (VG_(strcmp)(str, members[i]) == 0)
383 return True;
384 return False;
385 }
386
387 /*--------------------------------------------------------------------*/
388 /*--- end m_xarray.c ---*/
389 /*--------------------------------------------------------------------*/
390