Re: Elegant 'realloc'?

[mheaney@on2.com (Matthew Heaney)]

Lutz Donnerhacke <lutz@iks-jena.de> wrote in message news:<slrnbiibl2.2j7.lutz@taranis.iks-jena.de>...
> * Matthew Heaney wrote:
> > Lutz Donnerhacke <lutz@iks-jena.de> wrote in message news:<slrnbihq0e.2j7.lutz@taranis.iks-jena.de>...
> >> When dealing with dynamically allocated variable length arrays, the
> >> allocated space might change. Is there a common idiom to simulate an
> >> 'realloc' (especially shrinking) other than, allocate, copy, free?
> >
> > I don't know how to implement a realloc in Ada, unless you write your own
> > storage pool.
> 
> Any hint?

A storage pool is typically implemented using a Storage_Array.  When
you allocate, you're really allocating an array that is at least as
big as the size of the allocation request.  The internal array might
be longer, so in theory you could give the caller the rest of the
array.

I haven't tried this, so I don't know whether it's even possible.  One
issue that comes to mind immediately is initialization of array
components, which is controlled by the Ada run-time.

But it's not clear whether any of this is necessary.  This does
exactly what a vector constainer does already, so why not just use a
vector?


> > You can try using the vector container in Charles, which hides all the
> > allocate, copy, and free calls.
> 
> Performance does matter in this case. So hiding necessary parts does not help.

The cost of insertion into a vector container (at least, insertion at
the back end of the vector) is amortized constant time.  You can't do
better than that, so it's not clear what your performance issue is.



> > The length of the vector refers to the number of active elements in the
> > vector.  The size of the vector refers to the length of the underlying
> > array, which is at least the number of elements.
> 
> Exactly this is the way I implement it: Trading allocated space for running
> time.

Internal reallocation during insertion into a vector container occurs
under precisely specified conditions.  Also, the size of the
newly-allocated internal array is always a function of the current
size of the internal array.  It does not depend on the number of
active elements (if it did then insertion wouldn't be amortized
constant time).

In Charles the size of the newly-allocated internal array is two times
the current size.

So internal reallocation in a vector container does exactly what
realloc would do.  Most of the time reallocation won't be necessary,
and inserting an element into the vector will simply update the
length.

If you know apriori the number of elements you intend to put in the
vector container, then you can always call Resize, which preallocates
an internal array having at least the specified size.

Charles is available at my home page.

http://home.earthlink.net/~matthewjheaney/charles/