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
40struct _XArray {
41   void* (*alloc) ( const HChar*, SizeT ); /* alloc fn (nofail) */
42   const HChar* cc;                 /* cost centre for alloc */
43   void  (*free) ( 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   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)( const HChar* cc, XArray* xao )
83{
84   struct _XArray* xa = (struct _XArray*)xao;
85   struct _XArray* nyu;
86   const 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, XACmpFn_t compar )
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, const 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, const 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) = ((const 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, const void* key,
229                            /*OUT*/Word* first, /*OUT*/Word* last,
230                            Int(*cmpFn)(const void*, const 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, const 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_(removeIndexXA)( XArray* xao, Word n )
315{
316   struct _XArray* xa = (struct _XArray*)xao;
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
328void VG_(insertIndexXA)( XArray* xao, Word n, const void* elem )
329{
330   struct _XArray* xa = (struct _XArray*)xao;
331   vg_assert(xa);
332   vg_assert(n >= 0);
333   vg_assert(n <= xa->usedsizeE);
334   vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
335   ensureSpaceXA( xa );
336   vg_assert(xa->usedsizeE < xa->totsizeE);
337   vg_assert(xa->arr);
338   if (n < xa->usedsizeE) {
339      VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB,
340                     ((char*)xa->arr) + (n+0) * xa->elemSzB,
341                     (xa->usedsizeE - n) * xa->elemSzB );
342   }
343   VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB,
344                elem, xa->elemSzB );
345   xa->usedsizeE++;
346   xa->sorted = False;
347}
348
349void VG_(getContentsXA_UNSAFE)( XArray* xao,
350                                /*OUT*/void** ctsP,
351                                /*OUT*/Word* usedP )
352{
353   struct _XArray* xa = (struct _XArray*)xao;
354   vg_assert(xa);
355   *ctsP  = (void*)xa->arr;
356   *usedP = xa->usedsizeE;
357}
358
359/* --------- Printeffery --------- */
360
361static void add_char_to_XA ( HChar c, void* opaque )
362{
363   XArray* dst = (XArray*)opaque;
364   (void) VG_(addBytesToXA)( dst, &c, 1 );
365}
366
367void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
368{
369   va_list vargs;
370   va_start(vargs, format);
371   VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
372   va_end(vargs);
373}
374
375
376/*--------------------------------------------------------------------*/
377/*--- end                                               m_xarray.c ---*/
378/*--------------------------------------------------------------------*/
379