From 0c2371837b4837ae8289f7ff91b607880690d59b Mon Sep 17 00:00:00 2001
From: Julian Seward <jseward@acm.org>
Date: Wed, 23 Feb 2011 13:22:24 +0000
Subject: [PATCH] Add a new constructor for empty XArrays, VG_(newSizedXA). 
 This is identical to VG_(newXA) but allows passing in a size hint.  In the
 case where the likely final size of the XArray is known at creation time,
 this allows avoiding the repeated (implicit) resizing and copying of the
 array as elements are added, which can save a vast amount of dynamic memory
 allocation turnover.

git-svn-id: svn://svn.valgrind.org/valgrind/trunk@11568
---
 coregrind/m_xarray.c      | 23 +++++++++++++++++++++--
 include/pub_tool_xarray.h | 11 +++++++++++
 2 files changed, 32 insertions(+), 2 deletions(-)

diff --git a/coregrind/m_xarray.c b/coregrind/m_xarray.c
index cdcf978615..4dc8ebdb73 100644
--- a/coregrind/m_xarray.c
+++ b/coregrind/m_xarray.c
@@ -44,6 +44,7 @@ struct _XArray {
    Int   (*cmpFn) ( void*, void* ); /* cmp fn (may be NULL) */
    Word  elemSzB;   /* element size in bytes */
    void* arr;       /* pointer to elements */
+   Word  initsizeE; /* HINT only: initial size, 0 if no hint */
    Word  usedsizeE; /* # used elements in arr */
    Word  totsizeE;  /* max size of arr, in elements */
    Bool  sorted;    /* is it sorted? */
@@ -72,6 +73,7 @@ XArray* VG_(newXA) ( void*(*alloc_fn)(HChar*,SizeT),
    xa->free      = free_fn;
    xa->cmpFn     = NULL;
    xa->elemSzB   = elemSzB;
+   xa->initsizeE = 0;
    xa->usedsizeE = 0;
    xa->totsizeE  = 0;
    xa->sorted    = False;
@@ -79,6 +81,19 @@ XArray* VG_(newXA) ( void*(*alloc_fn)(HChar*,SizeT),
    return xa;
 }
 
+XArray* VG_(newSizedXA) ( void*(*alloc_fn)(HChar*,SizeT), 
+                          HChar* cc,
+                          void(*free_fn)(void*),
+                          Word elemSzB,
+                          Word nInitialElems )
+{
+   XArray* xa;
+   tl_assert(nInitialElems >= 0);
+   xa = VG_(newXA)( alloc_fn, cc, free_fn, elemSzB );
+   xa->initsizeE = nInitialElems;
+   return xa;
+}
+
 XArray* VG_(cloneXA)( HChar* cc, XArray* xao )
 {
    struct _XArray* xa = (struct _XArray*)xao;
@@ -145,7 +160,7 @@ inline void* VG_(indexXA) ( XArray* xao, Word n )
 
 static inline void ensureSpaceXA ( struct _XArray* xa )
 {
-   if (xa->usedsizeE == xa->totsizeE) {
+   if (UNLIKELY(xa->usedsizeE == xa->totsizeE)) {
       void* tmp;
       Word  newsz;
       if (xa->totsizeE == 0)
@@ -158,7 +173,11 @@ static inline void ensureSpaceXA ( struct _XArray* xa )
             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;
+         /* Also, if there's a hinted initial size, use that instead of
+            the logic in the preceding comment. */
+         tl_assert(xa->initsizeE >= 0);
+         if (xa->initsizeE > 0) newsz = xa->initsizeE;
+         else if (xa->elemSzB == 1) newsz = 8;
          else if (xa->elemSzB == 2) newsz = 4;
          else newsz = 2;
       } else {
diff --git a/include/pub_tool_xarray.h b/include/pub_tool_xarray.h
index cd1b02e43b..ff8dfb3449 100644
--- a/include/pub_tool_xarray.h
+++ b/include/pub_tool_xarray.h
@@ -54,6 +54,17 @@ extern XArray* VG_(newXA) ( void*(*alloc_fn)(HChar*,SizeT),
                             void(*free_fn)(void*),
                             Word elemSzB );
 
+/* Same as VG_(newXA), except allows specification of an initial
+   number of elements for the array, so as to avoid a potentially
+   large wasted cost of repeatedly resizing the array when the caller
+   knows something about what the expected final size is going to
+   be. */
+extern XArray* VG_(newSizedXA) ( void*(*alloc_fn)(HChar*,SizeT), 
+                                 HChar* cc,
+                                 void(*free_fn)(void*),
+                                 Word elemSzB,
+                                 Word nInitialElems );
+
 /* Free all memory associated with an XArray. */
 extern void VG_(deleteXA) ( XArray* );
 
-- 
2.47.2