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-2015 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
40struct _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
53XArray* 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
81XArray* 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
111void 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
120void 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
128inline 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
138void 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
156static 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
190Word 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
206Word 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
226void 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
234Bool 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
272Bool 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. */
284Word VG_(sizeXA) ( const XArray* xa )
285{
286   vg_assert(xa);
287   return xa->usedsizeE;
288}
289
290void 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
298void 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
318void 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
331void 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
351void 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
362static void add_char_to_XA ( HChar c, void* opaque )
363{
364   XArray* dst = (XArray*)opaque;
365   (void) VG_(addBytesToXA)( dst, &c, 1 );
366}
367
368void 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
376
377/*--------------------------------------------------------------------*/
378/*--- end                                               m_xarray.c ---*/
379/*--------------------------------------------------------------------*/
380