coregrind/m_xarray.c - platform/external/valgrind - Git at Google


 /*--------------------------------------------------------------------*/
 /*--- An expandable array implementation.               m_xarray.h ---*/
 /*--------------------------------------------------------------------*/

 /*
    This file is part of Valgrind, a dynamic binary instrumentation
    framework.

    Copyright (C) 2007-2013 OpenWorks LLP
       info@open-works.co.uk

    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License as
    published by the Free Software Foundation; either version 2 of the
    License, or (at your option) any later version.

    This program is distributed in the hope that it will be useful, but
    WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307, USA.

    The GNU General Public License is contained in the file COPYING.
 */

 #include "pub_core_basics.h"
 #include "pub_core_libcbase.h"
 #include "pub_core_libcassert.h"
 #include "pub_core_libcprint.h"
 #include "pub_core_xarray.h"    /* self */


 /* See pub_tool_xarray.h for details of what this is all about. */

 struct _XArray {
    void* (*alloc_fn) ( const HChar*, SizeT ); /* alloc fn (nofail) */
    const HChar* cc;                    /* cost centre for alloc */
    void  (*free_fn) ( void* );         /* free fn */
    Int   (*cmpFn) ( const void*, const void* ); /* cmp fn (may be NULL) */
    Word  elemSzB;   /* element size in bytes */
    void* arr;       /* pointer to elements */
    Word  usedsizeE; /* # used elements in arr */
    Word  totsizeE;  /* max size of arr, in elements */
    Bool  sorted;    /* is it sorted? */
 };


 XArray* VG_(newXA) ( void*(*alloc_fn)(const HChar*,SizeT),
                      const HChar* cc,
                      void(*free_fn)(void*),
                      Word elemSzB )
 {
    XArray* xa;
    /* Implementation relies on Word being signed and (possibly)
       on SizeT being unsigned. */
    vg_assert( sizeof(Word) == sizeof(void*) );
    vg_assert( ((Word)(-1)) < ((Word)(0)) );
    vg_assert( ((SizeT)(-1)) > ((SizeT)(0)) );
    /* check user-supplied info .. */
    vg_assert(alloc_fn);
    vg_assert(free_fn);
    vg_assert(elemSzB > 0);
    xa = alloc_fn( cc, sizeof(struct _XArray) );
    xa->alloc_fn  = alloc_fn;
    xa->cc        = cc;
    xa->free_fn   = free_fn;
    xa->cmpFn     = NULL;
    xa->elemSzB   = elemSzB;
    xa->usedsizeE = 0;
    xa->totsizeE  = 0;
    xa->sorted    = False;
    xa->arr       = NULL;
    return xa;
 }

 XArray* VG_(cloneXA)( const HChar* cc, const XArray* xa )
 {
    XArray* nyu;
    const HChar* nyu_cc;
    vg_assert(xa);
    vg_assert(xa->alloc_fn);
    vg_assert(xa->free_fn);
    vg_assert(xa->elemSzB >= 1);
    nyu_cc = cc ? cc : xa->cc;
    nyu = xa->alloc_fn( nyu_cc, sizeof(struct _XArray) );

    /* Copy everything verbatim ... */
    *nyu = *xa;
    nyu->cc = nyu_cc;
    /* ... except we have to clone the contents-array */
    if (nyu->arr) {
       /* Restrict the total size of the new array to its current
          actual size.  That means we don't waste space copying the
          unused tail of the original.  The tradeoff is that it
          guarantees we will have to resize the child if even one more
          element is later added to it, unfortunately. */
       nyu->totsizeE = nyu->usedsizeE;
       /* and allocate .. */
       nyu->arr = nyu->alloc_fn( nyu->cc, nyu->totsizeE * nyu->elemSzB );
       VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB );
    }
    /* We're done! */
    return nyu;
 }

 void VG_(deleteXA) ( XArray* xa )
 {
    vg_assert(xa);
    vg_assert(xa->free_fn);
    if (xa->arr)
       xa->free_fn(xa->arr);
    xa->free_fn(xa);
 }

 void VG_(setCmpFnXA) ( XArray* xa, XACmpFn_t compar )
 {
    vg_assert(xa);
    vg_assert(compar);
    xa->cmpFn  = compar;
    xa->sorted = False;
 }

 inline void* VG_(indexXA) ( const XArray* xa, Word n )
 {
    vg_assert(xa);
    /* vg_assert(n >= 0); If n negative, the UWord conversion will make
       it bigger than usedsizeE, which is verified to be non negative when
       xa is modified. */
    vg_assert((UWord)n < (UWord)xa->usedsizeE);
    return ((char*)xa->arr) + n * xa->elemSzB;
 }

 void VG_(hintSizeXA) ( XArray* xa, Word n)
 {
    /* Currently, we support giving a size hint only just after the
       call to VG_(newXA). So, we could instead have done
       a function VG_(newXA_with_SizeHint). The separate VG_(hintSizeXA)
       function is however chosen as we might one day accept to
       give a size hint after having added elements. That could be useful
       for reducing the size of an xarray to just the size currently needed
       or to give a size hint when it is known that a lot more elements
       are needed or when the final nr of elements is known. */
    vg_assert(xa);
    vg_assert(xa->usedsizeE == 0);
    vg_assert(xa->totsizeE == 0);
    vg_assert(!xa->arr);
    xa->arr = xa->alloc_fn(xa->cc, n * xa->elemSzB);
    xa->totsizeE = n;
 }

 static inline void ensureSpaceXA ( XArray* xa )
 {
    if (xa->usedsizeE == xa->totsizeE) {
       void* tmp;
       Word  newsz;
       if (xa->totsizeE == 0)
          vg_assert(!xa->arr);
       if (xa->totsizeE > 0)
          vg_assert(xa->arr);
       if (xa->totsizeE == 0) {
          /* No point in having tiny (eg) 2-byte allocations for the
             element array, since all allocs are rounded up to 8 anyway.
             Hence increase the initial array size for tiny elements in
             an attempt to avoid reallocations of size 2, 4, 8 if the
             array does start to fill up. */
          if (xa->elemSzB == 1) newsz = 8;
          else if (xa->elemSzB == 2) newsz = 4;
          else newsz = 2;
       } else {
          newsz = 2 + (3 * xa->totsizeE) / 2;  /* 2 * xa->totsizeE; */
       }
       if (0 && xa->totsizeE >= 10000)
          VG_(printf)("addToXA: increasing from %ld to %ld\n",
                      xa->totsizeE, newsz);
       tmp = xa->alloc_fn(xa->cc, newsz * xa->elemSzB);
       if (xa->usedsizeE > 0)
          VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB);
       if (xa->arr)
          xa->free_fn(xa->arr);
       xa->arr = tmp;
       xa->totsizeE = newsz;
    }
 }

 Word VG_(addToXA) ( XArray* xa, const void* elem )
 {
    vg_assert(xa);
    vg_assert(elem);
    vg_assert(xa->totsizeE >= 0);
    vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
    ensureSpaceXA( xa );
    vg_assert(xa->usedsizeE < xa->totsizeE);
    vg_assert(xa->arr);
    VG_(memcpy)( ((UChar*)xa->arr) + xa->usedsizeE * xa->elemSzB,
                 elem, xa->elemSzB );
    xa->usedsizeE++;
    xa->sorted = False;
    return xa->usedsizeE-1;
 }

 Word VG_(addBytesToXA) ( XArray* xa, const void* bytesV, Word nbytes )
 {
    Word r, i;
    vg_assert(xa);
    vg_assert(xa->elemSzB == 1);
    vg_assert(nbytes >= 0);
    vg_assert(xa->totsizeE >= 0);
    vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
    r = xa->usedsizeE;
    for (i = 0; i < nbytes; i++) {
       ensureSpaceXA( xa );
       vg_assert(xa->usedsizeE < xa->totsizeE);
       vg_assert(xa->arr);
       * (((UChar*)xa->arr) + xa->usedsizeE) = ((const UChar*)bytesV)[i];
       xa->usedsizeE++;
    }
    xa->sorted = False;
    return r;
 }

 void VG_(sortXA) ( XArray* xa )
 {
    vg_assert(xa);
    vg_assert(xa->cmpFn);
    VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn );
    xa->sorted = True;
 }

 Bool VG_(lookupXA_UNSAFE) ( const XArray* xa, const void* key,
                             /*OUT*/Word* first, /*OUT*/Word* last,
                             Int(*cmpFn)(const void*, const void*) )
 {
    Word  lo, mid, hi, cres;
    void* midv;
    vg_assert(xa);
    lo = 0;
    hi = xa->usedsizeE-1;
    while (True) {
       /* current unsearched space is from lo to hi, inclusive. */
       if (lo > hi) return False; /* not found */
       mid  = (lo + hi) / 2;
       midv = VG_(indexXA)( xa, mid );
       cres = cmpFn( key, midv );
       if (cres < 0)  { hi = mid-1; continue; }
       if (cres > 0)  { lo = mid+1; continue; }
       /* Found it, at mid.  See how far we can expand this. */
       vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
       vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
       if (first) {
          *first = mid;
          while (*first > 0
                 && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) {
             (*first)--;
          }
       }
       if (last) {
          *last = mid;
          while (*last < xa->usedsizeE-1
                 && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) {
             (*last)++;
          }
       }
       return True;
    }
 }

 Bool VG_(lookupXA) ( const XArray* xa, const void* key,
                      /*OUT*/Word* first, /*OUT*/Word* last )
 {
    vg_assert(xa);
    vg_assert(xa->cmpFn);
    vg_assert(xa->sorted);
    return VG_(lookupXA_UNSAFE)(xa, key, first, last, xa->cmpFn);
 }

 Word VG_(sizeXA) ( const XArray* xa )
 {
    vg_assert(xa);
    return xa->usedsizeE;
 }

 void VG_(dropTailXA) ( XArray* xa, Word n )
 {
    vg_assert(xa);
    vg_assert(n >= 0);
    vg_assert(n <= xa->usedsizeE);
    xa->usedsizeE -= n;
 }

 void VG_(dropHeadXA) ( XArray* xa, Word n )
 {
    vg_assert(xa);
    vg_assert(n >= 0);
    vg_assert(n <= xa->usedsizeE);
    if (n == 0) {
       return;
    }
    if (n == xa->usedsizeE) {
       xa->usedsizeE = 0;
       return;
    }
    vg_assert(n > 0);
    vg_assert(xa->usedsizeE - n > 0);
    VG_(memcpy)( (char*)xa->arr,
                 ((char*)xa->arr) + n * xa->elemSzB,
                 (xa->usedsizeE - n) * xa->elemSzB );
    xa->usedsizeE -= n;
 }

 void VG_(removeIndexXA)( XArray* xa, Word n )
 {
    vg_assert(xa);
    vg_assert(n >= 0);
    vg_assert(n < xa->usedsizeE);
    if (n+1 < xa->usedsizeE) {
       VG_(memmove)( ((char*)xa->arr) + (n+0) * xa->elemSzB,
                     ((char*)xa->arr) + (n+1) * xa->elemSzB,
                     (xa->usedsizeE - n - 1) * xa->elemSzB );
    }
    xa->usedsizeE--;
 }

 void VG_(insertIndexXA)( XArray* xa, Word n, const void* elem )
 {
    vg_assert(xa);
    vg_assert(n >= 0);
    vg_assert(n <= xa->usedsizeE);
    vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
    ensureSpaceXA( xa );
    vg_assert(xa->usedsizeE < xa->totsizeE);
    vg_assert(xa->arr);
    if (n < xa->usedsizeE) {
       VG_(memmove) ( ((char*)xa->arr) + (n+1) * xa->elemSzB,
                      ((char*)xa->arr) + (n+0) * xa->elemSzB,
                      (xa->usedsizeE - n) * xa->elemSzB );
    }
    VG_(memcpy)( ((UChar*)xa->arr) + n * xa->elemSzB,
                 elem, xa->elemSzB );
    xa->usedsizeE++;
    xa->sorted = False;
 }

 void VG_(getContentsXA_UNSAFE)( XArray* xa,
                                 /*OUT*/void** ctsP,
                                 /*OUT*/Word* usedP )
 {
    vg_assert(xa);
    *ctsP  = (void*)xa->arr;
    *usedP = xa->usedsizeE;
 }

 /* --------- Printeffery --------- */

 static void add_char_to_XA ( HChar c, void* opaque )
 {
    XArray* dst = (XArray*)opaque;
    (void) VG_(addBytesToXA)( dst, &c, 1 );
 }

 void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
 {
    va_list vargs;
    va_start(vargs, format);
    VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
    va_end(vargs);
 }


 /*--------------------------------------------------------------------*/
 /*--- end                                               m_xarray.c ---*/
 /*--------------------------------------------------------------------*/

	/--------------------------------------------------------------------/
	/--- An expandable array implementation. m_xarray.h ---/
	/--------------------------------------------------------------------/

	/*
	This file is part of Valgrind, a dynamic binary instrumentation
	framework.

	Copyright (C) 2007-2013 OpenWorks LLP
	info@open-works.co.uk

	This program is free software; you can redistribute it and/or
	modify it under the terms of the GNU General Public License as
	published by the Free Software Foundation; either version 2 of the
	License, or (at your option) any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
	02111-1307, USA.

	The GNU General Public License is contained in the file COPYING.
	*/

	#include "pub_core_basics.h"
	#include "pub_core_libcbase.h"
	#include "pub_core_libcassert.h"
	#include "pub_core_libcprint.h"
	#include "pub_core_xarray.h" /* self */


	/* See pub_tool_xarray.h for details of what this is all about. */

	struct _XArray {
	void* (alloc_fn) ( const HChar, SizeT ); /* alloc fn (nofail) */
	const HChar* cc; /* cost centre for alloc */
	void (free_fn) ( void ); /* free fn */
	Int (cmpFn) ( const void, const void* ); /* cmp fn (may be NULL) */
	Word elemSzB; /* element size in bytes */
	void* arr; /* pointer to elements */
	Word usedsizeE; /* # used elements in arr */
	Word totsizeE; /* max size of arr, in elements */
	Bool sorted; /* is it sorted? */
	};


	XArray* VG_(newXA) ( void(alloc_fn)(const HChar*,SizeT),
	const HChar* cc,
	void(free_fn)(void),
	Word elemSzB )
	{
	XArray* xa;
	/* Implementation relies on Word being signed and (possibly)
	on SizeT being unsigned. */
	vg_assert( sizeof(Word) == sizeof(void*) );
	vg_assert( ((Word)(-1)) < ((Word)(0)) );
	vg_assert( ((SizeT)(-1)) > ((SizeT)(0)) );
	/* check user-supplied info .. */
	vg_assert(alloc_fn);
	vg_assert(free_fn);
	vg_assert(elemSzB > 0);
	xa = alloc_fn( cc, sizeof(struct _XArray) );
	xa->alloc_fn = alloc_fn;
	xa->cc = cc;
	xa->free_fn = free_fn;
	xa->cmpFn = NULL;
	xa->elemSzB = elemSzB;
	xa->usedsizeE = 0;
	xa->totsizeE = 0;
	xa->sorted = False;
	xa->arr = NULL;
	return xa;
	}

	XArray* VG_(cloneXA)( const HChar* cc, const XArray* xa )
	{
	XArray* nyu;
	const HChar* nyu_cc;
	vg_assert(xa);
	vg_assert(xa->alloc_fn);
	vg_assert(xa->free_fn);
	vg_assert(xa->elemSzB >= 1);
	nyu_cc = cc ? cc : xa->cc;
	nyu = xa->alloc_fn( nyu_cc, sizeof(struct _XArray) );

	/* Copy everything verbatim ... */
	nyu = xa;
	nyu->cc = nyu_cc;
	/* ... except we have to clone the contents-array */
	if (nyu->arr) {
	/* Restrict the total size of the new array to its current
	actual size. That means we don't waste space copying the
	unused tail of the original. The tradeoff is that it
	guarantees we will have to resize the child if even one more
	element is later added to it, unfortunately. */
	nyu->totsizeE = nyu->usedsizeE;
	/* and allocate .. */
	nyu->arr = nyu->alloc_fn( nyu->cc, nyu->totsizeE * nyu->elemSzB );
	VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB );
	}
	/* We're done! */
	return nyu;
	}

	void VG_(deleteXA) ( XArray* xa )
	{
	vg_assert(xa);
	vg_assert(xa->free_fn);
	if (xa->arr)
	xa->free_fn(xa->arr);
	xa->free_fn(xa);
	}

	void VG_(setCmpFnXA) ( XArray* xa, XACmpFn_t compar )
	{
	vg_assert(xa);
	vg_assert(compar);
	xa->cmpFn = compar;
	xa->sorted = False;
	}

	inline void* VG_(indexXA) ( const XArray* xa, Word n )
	{
	vg_assert(xa);
	/* vg_assert(n >= 0); If n negative, the UWord conversion will make
	it bigger than usedsizeE, which is verified to be non negative when
	xa is modified. */
	vg_assert((UWord)n < (UWord)xa->usedsizeE);
	return ((char)xa->arr) + n xa->elemSzB;
	}

	void VG_(hintSizeXA) ( XArray* xa, Word n)
	{
	/* Currently, we support giving a size hint only just after the
	call to VG_(newXA). So, we could instead have done
	a function VG_(newXA_with_SizeHint). The separate VG_(hintSizeXA)
	function is however chosen as we might one day accept to
	give a size hint after having added elements. That could be useful
	for reducing the size of an xarray to just the size currently needed
	or to give a size hint when it is known that a lot more elements
	are needed or when the final nr of elements is known. */
	vg_assert(xa);
	vg_assert(xa->usedsizeE == 0);
	vg_assert(xa->totsizeE == 0);
	vg_assert(!xa->arr);
	xa->arr = xa->alloc_fn(xa->cc, n * xa->elemSzB);
	xa->totsizeE = n;
	}

	static inline void ensureSpaceXA ( XArray* xa )
	{
	if (xa->usedsizeE == xa->totsizeE) {
	void* tmp;
	Word newsz;
	if (xa->totsizeE == 0)
	vg_assert(!xa->arr);
	if (xa->totsizeE > 0)
	vg_assert(xa->arr);
	if (xa->totsizeE == 0) {
	/* No point in having tiny (eg) 2-byte allocations for the
	element array, since all allocs are rounded up to 8 anyway.
	Hence increase the initial array size for tiny elements in
	an attempt to avoid reallocations of size 2, 4, 8 if the
	array does start to fill up. */
	if (xa->elemSzB == 1) newsz = 8;
	else if (xa->elemSzB == 2) newsz = 4;
	else newsz = 2;
	} else {
	newsz = 2 + (3 * xa->totsizeE) / 2; /* 2 * xa->totsizeE; */
	}
	if (0 && xa->totsizeE >= 10000)
	VG_(printf)("addToXA: increasing from %ld to %ld\n",
	xa->totsizeE, newsz);
	tmp = xa->alloc_fn(xa->cc, newsz * xa->elemSzB);
	if (xa->usedsizeE > 0)
	VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB);
	if (xa->arr)
	xa->free_fn(xa->arr);
	xa->arr = tmp;
	xa->totsizeE = newsz;
	}
	}

	Word VG_(addToXA) ( XArray* xa, const void* elem )
	{
	vg_assert(xa);
	vg_assert(elem);
	vg_assert(xa->totsizeE >= 0);
	vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
	ensureSpaceXA( xa );
	vg_assert(xa->usedsizeE < xa->totsizeE);
	vg_assert(xa->arr);
	VG_(memcpy)( ((UChar)xa->arr) + xa->usedsizeE xa->elemSzB,
	elem, xa->elemSzB );
	xa->usedsizeE++;
	xa->sorted = False;
	return xa->usedsizeE-1;
	}

	Word VG_(addBytesToXA) ( XArray* xa, const void* bytesV, Word nbytes )
	{
	Word r, i;
	vg_assert(xa);
	vg_assert(xa->elemSzB == 1);
	vg_assert(nbytes >= 0);
	vg_assert(xa->totsizeE >= 0);
	vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
	r = xa->usedsizeE;
	for (i = 0; i < nbytes; i++) {
	ensureSpaceXA( xa );
	vg_assert(xa->usedsizeE < xa->totsizeE);
	vg_assert(xa->arr);
	* (((UChar)xa->arr) + xa->usedsizeE) = ((const UChar)bytesV)[i];
	xa->usedsizeE++;
	}
	xa->sorted = False;
	return r;
	}

	void VG_(sortXA) ( XArray* xa )
	{
	vg_assert(xa);
	vg_assert(xa->cmpFn);
	VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn );
	xa->sorted = True;
	}

	Bool VG_(lookupXA_UNSAFE) ( const XArray* xa, const void* key,
	/OUT/Word* first, /OUT/Word* last,
	Int(cmpFn)(const void, const void*) )
	{
	Word lo, mid, hi, cres;
	void* midv;
	vg_assert(xa);
	lo = 0;
	hi = xa->usedsizeE-1;
	while (True) {
	/* current unsearched space is from lo to hi, inclusive. */
	if (lo > hi) return False; /* not found */
	mid = (lo + hi) / 2;
	midv = VG_(indexXA)( xa, mid );
	cres = cmpFn( key, midv );
	if (cres < 0) { hi = mid-1; continue; }
	if (cres > 0) { lo = mid+1; continue; }
	/* Found it, at mid. See how far we can expand this. */
	vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
	vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
	if (first) {
	*first = mid;
	while (*first > 0
	&& 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1))) {
	(*first)--;
	}
	}
	if (last) {
	*last = mid;
	while (*last < xa->usedsizeE-1
	&& 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1))) {
	(*last)++;
	}
	}
	return True;
	}
	}

	Bool VG_(lookupXA) ( const XArray* xa, const void* key,
	/OUT/Word* first, /OUT/Word* last )
	{
	vg_assert(xa);
	vg_assert(xa->cmpFn);
	vg_assert(xa->sorted);
	return VG_(lookupXA_UNSAFE)(xa, key, first, last, xa->cmpFn);
	}

	Word VG_(sizeXA) ( const XArray* xa )
	{
	vg_assert(xa);
	return xa->usedsizeE;
	}

	void VG_(dropTailXA) ( XArray* xa, Word n )
	{
	vg_assert(xa);
	vg_assert(n >= 0);
	vg_assert(n <= xa->usedsizeE);
	xa->usedsizeE -= n;
	}

	void VG_(dropHeadXA) ( XArray* xa, Word n )
	{
	vg_assert(xa);
	vg_assert(n >= 0);
	vg_assert(n <= xa->usedsizeE);
	if (n == 0) {
	return;
	}
	if (n == xa->usedsizeE) {
	xa->usedsizeE = 0;
	return;
	}
	vg_assert(n > 0);
	vg_assert(xa->usedsizeE - n > 0);
	VG_(memcpy)( (char*)xa->arr,
	((char)xa->arr) + n xa->elemSzB,
	(xa->usedsizeE - n) * xa->elemSzB );
	xa->usedsizeE -= n;
	}

	void VG_(removeIndexXA)( XArray* xa, Word n )
	{
	vg_assert(xa);
	vg_assert(n >= 0);
	vg_assert(n < xa->usedsizeE);
	if (n+1 < xa->usedsizeE) {
	VG_(memmove)( ((char)xa->arr) + (n+0) xa->elemSzB,
	((char)xa->arr) + (n+1) xa->elemSzB,
	(xa->usedsizeE - n - 1) * xa->elemSzB );
	}
	xa->usedsizeE--;
	}

	void VG_(insertIndexXA)( XArray* xa, Word n, const void* elem )
	{
	vg_assert(xa);
	vg_assert(n >= 0);
	vg_assert(n <= xa->usedsizeE);
	vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
	ensureSpaceXA( xa );
	vg_assert(xa->usedsizeE < xa->totsizeE);
	vg_assert(xa->arr);
	if (n < xa->usedsizeE) {
	VG_(memmove) ( ((char)xa->arr) + (n+1) xa->elemSzB,
	((char)xa->arr) + (n+0) xa->elemSzB,
	(xa->usedsizeE - n) * xa->elemSzB );
	}
	VG_(memcpy)( ((UChar)xa->arr) + n xa->elemSzB,
	elem, xa->elemSzB );
	xa->usedsizeE++;
	xa->sorted = False;
	}

	void VG_(getContentsXA_UNSAFE)( XArray* xa,
	/OUT/void** ctsP,
	/OUT/Word* usedP )
	{
	vg_assert(xa);
	ctsP = (void)xa->arr;
	*usedP = xa->usedsizeE;
	}

	/* --------- Printeffery --------- */

	static void add_char_to_XA ( HChar c, void* opaque )
	{
	XArray* dst = (XArray*)opaque;
	(void) VG_(addBytesToXA)( dst, &c, 1 );
	}

	void VG_(xaprintf)( XArray* dst, const HChar* format, ... )
	{
	va_list vargs;
	va_start(vargs, format);
	VG_(vcbprintf)( add_char_to_XA, (void*)dst, format, vargs );
	va_end(vargs);
	}


	/--------------------------------------------------------------------/
	/--- end m_xarray.c ---/
	/--------------------------------------------------------------------/