1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- An expandable array implementation. m_xarray.h ---*/ 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This file is part of Valgrind, a dynamic binary instrumentation 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown framework. 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 10436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Copyright (C) 2007-2013 OpenWorks LLP 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown info@open-works.co.uk 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is free software; you can redistribute it and/or 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown modify it under the terms of the GNU General Public License as 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown published by the Free Software Foundation; either version 2 of the 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown License, or (at your option) any later version. 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is distributed in the hope that it will be useful, but 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WITHOUT ANY WARRANTY; without even the implied warranty of 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown General Public License for more details. 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown You should have received a copy of the GNU General Public License 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown along with this program; if not, write to the Free Software 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 02111-1307, USA. 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown The GNU General Public License is contained in the file COPYING. 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_basics.h" 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcbase.h" 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcassert.h" 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcprint.h" 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_xarray.h" /* self */ 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* See pub_tool_xarray.h for details of what this is all about. */ 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstruct _XArray { 41436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov void* (*alloc) ( const HChar*, SizeT ); /* alloc fn (nofail) */ 42436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* cc; /* cost centre for alloc */ 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void (*free) ( void* ); /* free fn */ 44436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Int (*cmpFn) ( const void*, const void* ); /* cmp fn (may be NULL) */ 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word elemSzB; /* element size in bytes */ 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void* arr; /* pointer to elements */ 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word usedsizeE; /* # used elements in arr */ 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word totsizeE; /* max size of arr, in elements */ 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool sorted; /* is it sorted? */ 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown}; 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 53436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovXArray* VG_(newXA) ( void*(*alloc_fn)(const HChar*,SizeT), 54436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* cc, 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void(*free_fn)(void*), 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word elemSzB ) 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa; 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Implementation relies on Word being signed and (possibly) 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown on SizeT being unsigned. */ 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( sizeof(Word) == sizeof(void*) ); 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ((Word)(-1)) < ((Word)(0)) ); 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ((SizeT)(-1)) > ((SizeT)(0)) ); 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* check user-supplied info .. */ 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(alloc_fn); 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(free_fn); 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(elemSzB > 0); 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa = alloc_fn( cc, sizeof(struct _XArray) ); 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->alloc = alloc_fn; 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->cc = cc; 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->free = free_fn; 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->cmpFn = NULL; 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->elemSzB = elemSzB; 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->usedsizeE = 0; 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->totsizeE = 0; 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->sorted = False; 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->arr = NULL; 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return xa; 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 82436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovXArray* VG_(cloneXA)( const HChar* cc, XArray* xao ) 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* nyu; 86436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* nyu_cc; 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->alloc); 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->free); 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->elemSzB >= 1); 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu_cc = cc ? cc : xa->cc; 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu = xa->alloc( nyu_cc, sizeof(struct _XArray) ); 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!nyu) 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Copy everything verbatim ... */ 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *nyu = *xa; 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->cc = nyu_cc; 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* ... except we have to clone the contents-array */ 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (nyu->arr) { 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Restrict the total size of the new array to its current 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown actual size. That means we don't waste space copying the 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unused tail of the original. The tradeoff is that it 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown guarantees we will have to resize the child if even one more 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown element is later added to it, unfortunately. */ 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->totsizeE = nyu->usedsizeE; 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* and allocate .. */ 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->arr = nyu->alloc( nyu->cc, nyu->totsizeE * nyu->elemSzB ); 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!nyu->arr) { 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown nyu->free(nyu); 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB ); 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* We're done! */ 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return nyu; 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(deleteXA) ( XArray* xao ) 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->free); 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (xa->arr) 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->free(xa->arr); 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->free(xa); 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 128436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid VG_(setCmpFnXA) ( XArray* xao, XACmpFn_t compar ) 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(compar); 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->cmpFn = compar; 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->sorted = False; 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browninline void* VG_(indexXA) ( XArray* xao, Word n ) 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(n >= 0); 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(n < xa->usedsizeE); 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return ((char*)xa->arr) + n * xa->elemSzB; 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic inline void ensureSpaceXA ( struct _XArray* xa ) 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (xa->usedsizeE == xa->totsizeE) { 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void* tmp; 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word newsz; 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (xa->totsizeE == 0) 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(!xa->arr); 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (xa->totsizeE > 0) 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->arr); 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (xa->totsizeE == 0) { 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* No point in having tiny (eg) 2-byte allocations for the 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown element array, since all allocs are rounded up to 8 anyway. 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Hence increase the initial array size for tiny elements in 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown an attempt to avoid reallocations of size 2, 4, 8 if the 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown array does start to fill up. */ 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (xa->elemSzB == 1) newsz = 8; 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (xa->elemSzB == 2) newsz = 4; 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else newsz = 2; 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown newsz = 2 + (3 * xa->totsizeE) / 2; /* 2 * xa->totsizeE; */ 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (0 && xa->totsizeE >= 10000) 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(printf)("addToXA: increasing from %ld to %ld\n", 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->totsizeE, newsz); 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tmp = xa->alloc(xa->cc, newsz * xa->elemSzB); 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(tmp); 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (xa->usedsizeE > 0) 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB); 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (xa->arr) 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->free(xa->arr); 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->arr = tmp; 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->totsizeE = newsz; 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 181436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovWord VG_(addToXA) ( XArray* xao, const void* elem ) 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(elem); 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->totsizeE >= 0); 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ensureSpaceXA( xa ); 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->usedsizeE < xa->totsizeE); 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->arr); 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memcpy)( ((UChar*)xa->arr) + xa->usedsizeE * xa->elemSzB, 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown elem, xa->elemSzB ); 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->usedsizeE++; 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->sorted = False; 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return xa->usedsizeE-1; 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 198436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovWord VG_(addBytesToXA) ( XArray* xao, const void* bytesV, Word nbytes ) 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r, i; 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->elemSzB == 1); 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(nbytes >= 0); 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->totsizeE >= 0); 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown r = xa->usedsizeE; 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < nbytes; i++) { 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ensureSpaceXA( xa ); 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->usedsizeE < xa->totsizeE); 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->arr); 212436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * (((UChar*)xa->arr) + xa->usedsizeE) = ((const UChar*)bytesV)[i]; 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->usedsizeE++; 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->sorted = False; 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return r; 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(sortXA) ( XArray* xao ) 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->cmpFn); 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn ); 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->sorted = True; 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 228436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovBool VG_(lookupXA_UNSAFE) ( XArray* xao, const void* key, 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/Word* first, /*OUT*/Word* last, 230436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Int(*cmpFn)(const void*, const void*) ) 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word lo, mid, hi, cres; 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void* midv; 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown lo = 0; 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown hi = xa->usedsizeE-1; 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* current unsearched space is from lo to hi, inclusive. */ 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (lo > hi) return False; /* not found */ 241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown mid = (lo + hi) / 2; 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown midv = VG_(indexXA)( xa, mid ); 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cres = cmpFn( key, midv ); 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cres < 0) { hi = mid-1; continue; } 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (cres > 0) { lo = mid+1; continue; } 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Found it, at mid. See how far we can expand this. */ 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0); 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0); 249b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (first) { 250b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov *first = mid; 251b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov while (*first > 0 252b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) { 253b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov (*first)--; 254b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 255b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 256b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (last) { 257b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov *last = mid; 258b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov while (*last < xa->usedsizeE-1 259b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) { 260b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov (*last)++; 261b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 262b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return True; 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 267436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovBool VG_(lookupXA) ( XArray* xao, const void* key, 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/Word* first, /*OUT*/Word* last ) 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->cmpFn); 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->sorted); 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return VG_(lookupXA_UNSAFE)(xao, key, first, last, xa->cmpFn); 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWord VG_(sizeXA) ( XArray* xao ) 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return xa->usedsizeE; 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(dropTailXA) ( XArray* xao, Word n ) 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(n >= 0); 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(n <= xa->usedsizeE); 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->usedsizeE -= n; 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(dropHeadXA) ( XArray* xao, Word n ) 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(n >= 0); 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(n <= xa->usedsizeE); 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n == 0) { 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n == xa->usedsizeE) { 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->usedsizeE = 0; 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(n > 0); 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa->usedsizeE - n > 0); 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(memcpy)( (char*)xa->arr, 309ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((char*)xa->arr) + n * xa->elemSzB, 310ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (xa->usedsizeE - n) * xa->elemSzB ); 311ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown xa->usedsizeE -= n; 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 314663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengvoid VG_(removeIndexXA)( XArray* xao, Word n ) 315663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng{ 316663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng struct _XArray* xa = (struct _XArray*)xao; 317663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng vg_assert(xa); 318663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng vg_assert(n >= 0); 319663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng vg_assert(n < xa->usedsizeE); 320663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng if (n+1 < xa->usedsizeE) { 321663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng VG_(memmove)( ((char*)xa->arr) + (n+0) * xa->elemSzB, 322663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng ((char*)xa->arr) + (n+1) * xa->elemSzB, 323663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng (xa->usedsizeE - n - 1) * xa->elemSzB ); 324663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng } 325663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng xa->usedsizeE--; 326663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng} 327663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 328eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanovvoid VG_(insertIndexXA)( XArray* xao, Word n, const void* elem ) 329eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov{ 330eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov struct _XArray* xa = (struct _XArray*)xao; 331eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov vg_assert(xa); 332eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov vg_assert(n >= 0); 333eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov vg_assert(n <= xa->usedsizeE); 334eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE); 335eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov ensureSpaceXA( xa ); 336eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov vg_assert(xa->usedsizeE < xa->totsizeE); 337eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov vg_assert(xa->arr); 338eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (n < xa->usedsizeE) { 339eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB, 340eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov ((char*)xa->arr) + (n+0) * xa->elemSzB, 341eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov (xa->usedsizeE - n) * xa->elemSzB ); 342eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } 343eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB, 344eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov elem, xa->elemSzB ); 345eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov xa->usedsizeE++; 346eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov xa->sorted = False; 347eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov} 348eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 349ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(getContentsXA_UNSAFE)( XArray* xao, 350ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/void** ctsP, 351ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /*OUT*/Word* usedP ) 352ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 353ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown struct _XArray* xa = (struct _XArray*)xao; 354ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert(xa); 355ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *ctsP = (void*)xa->arr; 356ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *usedP = xa->usedsizeE; 357ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 358ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 359ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --------- Printeffery --------- */ 360ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 361ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void add_char_to_XA ( HChar c, void* opaque ) 362ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 363ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown XArray* dst = (XArray*)opaque; 364ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (void) VG_(addBytesToXA)( dst, &c, 1 ); 365ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 366ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 367ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(xaprintf)( XArray* dst, const HChar* format, ... ) 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown va_list vargs; 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown va_start(vargs, format); 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs ); 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown va_end(vargs); 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 374ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 375ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- end m_xarray.c ---*/ 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 379