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-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#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) ( HChar*, SizeT ); /* alloc fn (nofail) */
42   HChar* cc;                       /* cost centre for alloc */
43   void  (*free) ( void* );         /* free fn */
44   Int   (*cmpFn) ( void*, 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)(HChar*,SizeT),
54                     HChar* cc,
55                     void(*free_fn)(void*),
56                     Word elemSzB )
57{
58   struct _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   vg_assert(xa);
70   xa->alloc     = alloc_fn;
71   xa->cc        = cc;
72   xa->free      = free_fn;
73   xa->cmpFn     = NULL;
74   xa->elemSzB   = elemSzB;
75   xa->usedsizeE = 0;
76   xa->totsizeE  = 0;
77   xa->sorted    = False;
78   xa->arr       = NULL;
79   return xa;
80}
81
82XArray* VG_(cloneXA)( HChar* cc, XArray* xao )
83{
84   struct _XArray* xa = (struct _XArray*)xao;
85   struct _XArray* nyu;
86   HChar* nyu_cc;
87   vg_assert(xa);
88   vg_assert(xa->alloc);
89   vg_assert(xa->free);
90   vg_assert(xa->elemSzB >= 1);
91   nyu_cc = cc ? cc : xa->cc;
92   nyu = xa->alloc( nyu_cc, sizeof(struct _XArray) );
93   if (!nyu)
94      return NULL;
95   /* Copy everything verbatim ... */
96   *nyu = *xa;
97   nyu->cc = nyu_cc;
98   /* ... except we have to clone the contents-array */
99   if (nyu->arr) {
100      /* Restrict the total size of the new array to its current
101         actual size.  That means we don't waste space copying the
102         unused tail of the original.  The tradeoff is that it
103         guarantees we will have to resize the child if even one more
104         element is later added to it, unfortunately. */
105      nyu->totsizeE = nyu->usedsizeE;
106      /* and allocate .. */
107      nyu->arr = nyu->alloc( nyu->cc, nyu->totsizeE * nyu->elemSzB );
108      if (!nyu->arr) {
109         nyu->free(nyu);
110         return NULL;
111      }
112      VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB );
113   }
114   /* We're done! */
115   return nyu;
116}
117
118void VG_(deleteXA) ( XArray* xao )
119{
120   struct _XArray* xa = (struct _XArray*)xao;
121   vg_assert(xa);
122   vg_assert(xa->free);
123   if (xa->arr)
124      xa->free(xa->arr);
125   xa->free(xa);
126}
127
128void VG_(setCmpFnXA) ( XArray* xao, Int (*compar)(void*,void*) )
129{
130   struct _XArray* xa = (struct _XArray*)xao;
131   vg_assert(xa);
132   vg_assert(compar);
133   xa->cmpFn  = compar;
134   xa->sorted = False;
135}
136
137inline void* VG_(indexXA) ( XArray* xao, Word n )
138{
139   struct _XArray* xa = (struct _XArray*)xao;
140   vg_assert(xa);
141   vg_assert(n >= 0);
142   vg_assert(n < xa->usedsizeE);
143   return ((char*)xa->arr) + n * xa->elemSzB;
144}
145
146static inline void ensureSpaceXA ( struct _XArray* xa )
147{
148   if (xa->usedsizeE == xa->totsizeE) {
149      void* tmp;
150      Word  newsz;
151      if (xa->totsizeE == 0)
152         vg_assert(!xa->arr);
153      if (xa->totsizeE > 0)
154         vg_assert(xa->arr);
155      if (xa->totsizeE == 0) {
156         /* No point in having tiny (eg) 2-byte allocations for the
157            element array, since all allocs are rounded up to 8 anyway.
158            Hence increase the initial array size for tiny elements in
159            an attempt to avoid reallocations of size 2, 4, 8 if the
160            array does start to fill up. */
161         if (xa->elemSzB == 1) newsz = 8;
162         else if (xa->elemSzB == 2) newsz = 4;
163         else newsz = 2;
164      } else {
165         newsz = 2 + (3 * xa->totsizeE) / 2;  /* 2 * xa->totsizeE; */
166      }
167      if (0 && xa->totsizeE >= 10000)
168         VG_(printf)("addToXA: increasing from %ld to %ld\n",
169                     xa->totsizeE, newsz);
170      tmp = xa->alloc(xa->cc, newsz * xa->elemSzB);
171      vg_assert(tmp);
172      if (xa->usedsizeE > 0)
173         VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB);
174      if (xa->arr)
175         xa->free(xa->arr);
176      xa->arr = tmp;
177      xa->totsizeE = newsz;
178   }
179}
180
181Word VG_(addToXA) ( XArray* xao, void* elem )
182{
183   struct _XArray* xa = (struct _XArray*)xao;
184   vg_assert(xa);
185   vg_assert(elem);
186   vg_assert(xa->totsizeE >= 0);
187   vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
188   ensureSpaceXA( xa );
189   vg_assert(xa->usedsizeE < xa->totsizeE);
190   vg_assert(xa->arr);
191   VG_(memcpy)( ((UChar*)xa->arr) + xa->usedsizeE * xa->elemSzB,
192                elem, xa->elemSzB );
193   xa->usedsizeE++;
194   xa->sorted = False;
195   return xa->usedsizeE-1;
196}
197
198Word VG_(addBytesToXA) ( XArray* xao, void* bytesV, Word nbytes )
199{
200   Word r, i;
201   struct _XArray* xa = (struct _XArray*)xao;
202   vg_assert(xa);
203   vg_assert(xa->elemSzB == 1);
204   vg_assert(nbytes >= 0);
205   vg_assert(xa->totsizeE >= 0);
206   vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
207   r = xa->usedsizeE;
208   for (i = 0; i < nbytes; i++) {
209      ensureSpaceXA( xa );
210      vg_assert(xa->usedsizeE < xa->totsizeE);
211      vg_assert(xa->arr);
212      * (((UChar*)xa->arr) + xa->usedsizeE) = ((UChar*)bytesV)[i];
213      xa->usedsizeE++;
214   }
215   xa->sorted = False;
216   return r;
217}
218
219void VG_(sortXA) ( XArray* xao )
220{
221   struct _XArray* xa = (struct _XArray*)xao;
222   vg_assert(xa);
223   vg_assert(xa->cmpFn);
224   VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn );
225   xa->sorted = True;
226}
227
228Bool VG_(lookupXA_UNSAFE) ( XArray* xao, void* key,
229                            /*OUT*/Word* first, /*OUT*/Word* last,
230                            Int(*cmpFn)(void*,void*) )
231{
232   Word  lo, mid, hi, cres;
233   void* midv;
234   struct _XArray* xa = (struct _XArray*)xao;
235   vg_assert(xa);
236   lo = 0;
237   hi = xa->usedsizeE-1;
238   while (True) {
239      /* current unsearched space is from lo to hi, inclusive. */
240      if (lo > hi) return False; /* not found */
241      mid  = (lo + hi) / 2;
242      midv = VG_(indexXA)( xa, mid );
243      cres = cmpFn( key, midv );
244      if (cres < 0)  { hi = mid-1; continue; }
245      if (cres > 0)  { lo = mid+1; continue; }
246      /* Found it, at mid.  See how far we can expand this. */
247      vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
248      vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
249      if (first) {
250         *first = mid;
251         while (*first > 0
252                && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) {
253            (*first)--;
254         }
255      }
256      if (last) {
257         *last = mid;
258         while (*last < xa->usedsizeE-1
259                && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) {
260            (*last)++;
261         }
262      }
263      return True;
264   }
265}
266
267Bool VG_(lookupXA) ( XArray* xao, void* key,
268                     /*OUT*/Word* first, /*OUT*/Word* last )
269{
270   struct _XArray* xa = (struct _XArray*)xao;
271   vg_assert(xa);
272   vg_assert(xa->cmpFn);
273   vg_assert(xa->sorted);
274   return VG_(lookupXA_UNSAFE)(xao, key, first, last, xa->cmpFn);
275}
276
277Word VG_(sizeXA) ( XArray* xao )
278{
279   struct _XArray* xa = (struct _XArray*)xao;
280   vg_assert(xa);
281   return xa->usedsizeE;
282}
283
284void VG_(dropTailXA) ( XArray* xao, Word n )
285{
286   struct _XArray* xa = (struct _XArray*)xao;
287   vg_assert(xa);
288   vg_assert(n >= 0);
289   vg_assert(n <= xa->usedsizeE);
290   xa->usedsizeE -= n;
291}
292
293void VG_(dropHeadXA) ( XArray* xao, Word n )
294{
295   struct _XArray* xa = (struct _XArray*)xao;
296   vg_assert(xa);
297   vg_assert(n >= 0);
298   vg_assert(n <= xa->usedsizeE);
299   if (n == 0) {
300      return;
301   }
302   if (n == xa->usedsizeE) {
303      xa->usedsizeE = 0;
304      return;
305   }
306   vg_assert(n > 0);
307   vg_assert(xa->usedsizeE - n > 0);
308   VG_(memcpy)( (char*)xa->arr,
309                ((char*)xa->arr) + n * xa->elemSzB,
310                (xa->usedsizeE - n) * xa->elemSzB );
311   xa->usedsizeE -= n;
312}
313
314void VG_(getContentsXA_UNSAFE)( XArray* xao,
315                                /*OUT*/void** ctsP,
316                                /*OUT*/Word* usedP )
317{
318   struct _XArray* xa = (struct _XArray*)xao;
319   vg_assert(xa);
320   *ctsP  = (void*)xa->arr;
321   *usedP = xa->usedsizeE;
322}
323
324/* --------- Printeffery --------- */
325
326static void add_char_to_XA ( HChar c, void* opaque )
327{
328   XArray* dst = (XArray*)opaque;
329   (void) VG_(addBytesToXA)( dst, &c, 1 );
330}
331
332void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
333{
334   va_list vargs;
335   va_start(vargs, format);
336   VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
337   va_end(vargs);
338}
339
340
341/*--------------------------------------------------------------------*/
342/*--- end                                               m_xarray.c ---*/
343/*--------------------------------------------------------------------*/
344