Elegant 'realloc'?

Elegant 'realloc'?

[Lutz Donnerhacke]

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?

   declare
      procedure Free is new Unchecked_Deallocation(T_Array, T_Array_Access);
      oldp : constant T_Array_Access := current.field;
   begin
      current.field := new T_Array'(oldp(oldp'First .. current.last));
      Free(oldp);
   end;

Re: Elegant 'realloc'?

[Matthew Heaney]

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?
> 
>    declare
>       procedure Free is new Unchecked_Deallocation(T_Array, T_Array_Access);
>       oldp : constant T_Array_Access := current.field;
>    begin
>       current.field := new T_Array'(oldp(oldp'First .. current.last));
>       Free(oldp);
>    end;

I don't know how to implement a realloc in Ada, unless you write your own
storage pool.

You can try using the vector container in Charles, which hides all the
allocate, copy, and free calls.

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.

To increase the size of a vector, you can just call Resize.

To decrease the size of a vector, you use the swap trick:

procedure Decrease_Size (V : in out Vector_Subtype) is
   V2 : Vector_Subtype := V;
begin
   Swap (V, V2);
end;

Charles makes a guarantee that the new vector V2 has the minimum size
necessary to contain all the elements in source vector V.  (Presumably the
size of V is much larger than its length, which is why we want to shrink
it.)

When you swap, the new vector V2 gets the (large) internal array of V, and V
gets the (small) internal array of V2.  V2 is immediately finalized, which
free's the internal array (and which originally belonged to V).

When you Clear a vector, like this:

Clear (V);

all this does is set the count of the number of active elements (the length)
to 0.  It leaves the internal array untouched, which means the size doesn't
change.

If you want to remove all the elements in a vector, and set the size of the
vector to 0, then you can use the swap trick:

procedure Clear_And_Decrease_Size (V : in out Vector_Subtype) is
   V2 : Vector_Subtype;  --Length and Size are both 0
begin
   Swap (V, V2);
end;

Charles makes a guarantee that there is no cost for simply declaring a
vector, in the sense that no internal memory is allocated during elaboration
of the vector object.

The Charles library is available from my home page.

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

Look for a new release of Charles early next week.

Re: Elegant 'realloc'?

[Lutz Donnerhacke]

* 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?

> 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 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.

Re: Elegant 'realloc'?

[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/

Re: Elegant 'realloc'?

[Nick Roberts]

"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?

Nope.

>    declare
>       procedure Free is new Unchecked_Deallocation(T_Array,
T_Array_Access);
>       oldp : constant T_Array_Access := current.field;
>    begin
>       current.field := new T_Array'(oldp(oldp'First .. current.last));
>       Free(oldp);
>    end;

The above isn't quite right.

Supposing we have the declarations:

   type Location_Descriptor is ...
   Unknown_Location: constant Location_Descriptor;
   type Location_Array is array (Integer range <>) of Location_Descriptor;
   type Location_History is access Location_Array;
   Track: Location_History;
   procedure Free is new Unchecked_Deallocation( Location_Array,
Location_History );

At a point where we wanted to change the range of Track to, let's say,
New_First..New_Last, we could write:

   declare
      subtype NI is Nonpositive_Integer; -- convenient renaming
      Mid_First: constant NI := NI'Max( Track'First, New_First );
      Mid_Last:  constant NI := NI'Min( Track'Last,  New_Last );
      Temp: constant Location_History := new Location_Array( New_First ..
New_Last );
   begin
      Temp( Mid_First   .. Mid_Last    ) := Track( Mid_First .. Mid_Last );
      Free( Track );
      Temp( New_First   .. Mid_First-1 ) := (others => Unknown_Location);
      Temp( Mid_Last+1 .. New_Last    ) := (others => Unknown_Location);
      Track := Temp;
   end;

I haven't tested this, but I think it's right.

--
Nick Roberts
Jabber: debater@charente.de [ICQ: 159718630]

Re: Elegant 'realloc'?

[Robert I. Eachus]

Lutz Donnerhacke wrote:
> 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?
> 
>    declare
>       procedure Free is new Unchecked_Deallocation(T_Array, T_Array_Access);
>       oldp : constant T_Array_Access := current.field;
>    begin
>       current.field := new T_Array'(oldp(oldp'First .. current.last));
>       Free(oldp);
>    end;

I would just write:

   declare
     Current: T_Array(1..Whatever);
   begin
     -- process Current
   end;

The array Current gets put on the stack.  If you really need the array 
to be extensible, containing the old value, you can either use 
recursion, the heap, or Ada.Strings.Unbounded. ;-)

-- 
"As far as I'm concerned, war always means failure." -- Jacques Chirac, 
President of France
"As far as France is concerned, you're right." -- Rush Limbaugh