How to properly clean up an extended, generic structure?

How to properly clean up an extended, generic structure?

[Peter C. Chapin]

Hello! I'm working on improving my Ada skills by assigning myself little 
programming exercises and then solving them in Ada. I come from a C++ 
background so I tend to see the world in C++ terms. I realize that isn't 
necessarily helpful.

Right now I'm working on a generic package that implements splay trees. 
My generic parameters look like:

generic
    type Item_Type is private;
    with function "<"(L : Item_Type; R : Item_Type) return Boolean;
package Splay_Tree is ...


I've created a procedure Destroy_Tree that uses an instance of 
Ada.Unchecked_Deallocation to remove all the nodes in a given tree. 
Destroy_Tree is meant to be used when a tree is no longer needed and it 
serves the role of a destructor (using C++ terminology). It occurs to 
me, though, that Item_Type might have its own clean up needs. I assume 
that Unchecked_Deallocation knows nothing about that. Thus my code 
currently might be improperly cleaning up the Item_Types in each tree 
node. In C++ this is not a problem because deleting a node invokes the 
node's destructor (if there is one) so the issue is handled 
automatically. My question is how do I best deal with this in Ada?

I could pass a clean up procedure for Item_Types as another generic 
parameter. However, in cases where no such procedure is necessary (for 
example, when Item_Type is just Integer), such a solution seems awkward. 
Is there a nicer solution?

Peter

Re: How to properly clean up an extended, generic structure?

[jimmaureenrogers]

Peter C. Chapin wrote:
> I've created a procedure Destroy_Tree that uses an instance of
> Ada.Unchecked_Deallocation to remove all the nodes in a given tree.
> Destroy_Tree is meant to be used when a tree is no longer needed and it
> serves the role of a destructor (using C++ terminology). It occurs to
> me, though, that Item_Type might have its own clean up needs. I assume
> that Unchecked_Deallocation knows nothing about that. Thus my code
> currently might be improperly cleaning up the Item_Types in each tree
> node. In C++ this is not a problem because deleting a node invokes the
> node's destructor (if there is one) so the issue is handled
> automatically. My question is how do I best deal with this in Ada?
>
> I could pass a clean up procedure for Item_Types as another generic
> parameter. However, in cases where no such procedure is necessary (for
> example, when Item_Type is just Integer), such a solution seems awkward.
> Is there a nicer solution?

You should read up on Ada controlled types. The tree itself can be a
controlled type. The tree elements may or may not be controlled types.

Ada controlled types allow you to specify actions to be taken upon
initialization, adjustment, and finalization of a data element. These
actions effectively mimic many of the characteristics of C++
constructors and destructors.

Jim Rogers

Re: How to properly clean up an extended, generic structure?

[Ludovic Brenta]

Peter C. Chapin writes:
> Right now I'm working on a generic package that implements splay
> trees. My generic parameters look like:
>
> generic
>    type Item_Type is private;
>    with function "<"(L : Item_Type; R : Item_Type) return Boolean;
> package Splay_Tree is ...
>
>
> I've created a procedure Destroy_Tree that uses an instance of
> Ada.Unchecked_Deallocation to remove all the nodes in a given
> tree. Destroy_Tree is meant to be used when a tree is no longer needed
> and it serves the role of a destructor (using C++ terminology). It
> occurs to me, though, that Item_Type might have its own clean up
> needs. I assume that Unchecked_Deallocation knows nothing about
> that. Thus my code currently might be improperly cleaning up the
> Item_Types in each tree node. In C++ this is not a problem because
> deleting a node invokes the node's destructor (if there is one) so the
> issue is handled automatically. My question is how do I best deal with
> this in Ada?
>
> I could pass a clean up procedure for Item_Types as another generic
> parameter. However, in cases where no such procedure is necessary (for
> example, when Item_Type is just Integer), such a solution seems
> awkward. Is there a nicer solution?

You do not need to change anything to your Splay_Tree; instead, just
pass a controlled type as the Item_Type.  A controlled type is a type
derived from Ada.Finalization.Controlled(*).  You override its
Finalize procedure to reclaim the storage for the item; that's the
equivalent of a destructor in C++.  The language guarantees (ARM
7.6(1)) that the instance of Unchecked_Deallocation will call your
Finalize, much like delete in C++ will call your destructor.

For more details, see ARM 7.6.

(*) or Limited_Controlled, but your generic does not accept limited
types, which is probably OK for a container.

HTH

-- 
Ludovic Brenta.

Re: How to properly clean up an extended, generic structure?

[Björn Persson]

Peter C. Chapin wrote:
> I've created a procedure Destroy_Tree that uses an instance of 
> Ada.Unchecked_Deallocation to remove all the nodes in a given tree. 
> Destroy_Tree is meant to be used when a tree is no longer needed and it 
> serves the role of a destructor (using C++ terminology). It occurs to 
> me, though, that Item_Type might have its own clean up needs.

You need controlled types. Derive your tree type from 
Ada.Finalization.Controlled, and instead of Destroy_Tree write a 
procedure Finalize, overriding the Finalize that's declared in 
Ada.Finalization. Finalize will then be executed automatically when the 
object is destroyed.

Item types that need cleaning up should also be controlled. Each item 
will then be finalized when its tree node is finalized.

-- 
Bj�rn Persson                              PGP key A88682FD
                    omb jor ers @sv ge.
                    r o.b n.p son eri nu

Re: How to properly clean up an extended, generic structure?

[Georg Bauhaus]

Peter C. Chapin wrote:

> It occurs to 
> me, though, that Item_Type might have its own clean up needs. I assume 
> that Unchecked_Deallocation knows nothing about that.

According to LRM 7.6.1(10), an instance of Unchecked_Deallocation
will trigger finalization of the object before its storage is reclaimed.

Perhaps you could consider the interactions of nested scopes with
finalization of objects declared in these scopes?


-- Georg

Re: How to properly clean up an extended, generic structure?

[Peter C. Chapin]

Ludovic Brenta wrote:

> You do not need to change anything to your Splay_Tree; instead, just
> pass a controlled type as the Item_Type.  A controlled type is a type
> derived from Ada.Finalization.Controlled(*).  You override its
> Finalize procedure to reclaim the storage for the item; that's the
> equivalent of a destructor in C++.  The language guarantees (ARM
> 7.6(1)) that the instance of Unchecked_Deallocation will call your
> Finalize, much like delete in C++ will call your destructor.

That sounds good... much better than what I was thinking about before. 
I'll play with it. Thank you (and others) for bringing this to my attention.

Peter

Re: How to properly clean up an extended, generic structure?

[Jeffrey R. Carter]

Peter C. Chapin wrote:
> 
> Right now I'm working on a generic package that implements splay trees. 
> My generic parameters look like:
> 
> generic
>    type Item_Type is private;
>    with function "<"(L : Item_Type; R : Item_Type) return Boolean;
> package Splay_Tree is ...

Let me summarize the answers you've received, since some of them only 
address part of your concern.

Your tree should clean up after itself. You don't say if Splay_Tree 
provides ADTs or an ASM, but in either case controlled types are the way 
to achieve this (ARM 7.6). Then you don't need to have a visible Destroy 
operation, and the clients of your package aren't responsible for 
destroying a tree when it's no longer needed.

It's up to the clients of your package to arrange for finalization for 
the actual associated with Item_Type, if it's needed. Basically, if the 
actual needs finalization, then it should be a controlled type. If it's 
a controlled type, then its Finalization procedure will be called when 
an object ceases to exist, including due to deallocation.

-- 
Jeff Carter
"My mind is a raging torrent, flooded with rivulets of
thought, cascading into a waterfall of creative alternatives."
Blazing Saddles
89

Re: How to properly clean up an extended, generic structure?

[Jean-Pierre Rosen]

> Peter C. Chapin wrote:
>>
>> Right now I'm working on a generic package that implements splay 
>> trees. My generic parameters look like:
>>
>> generic
>>    type Item_Type is private;
>>    with function "<"(L : Item_Type; R : Item_Type) return Boolean;
>> package Splay_Tree is ...
> 
If you want your package to be usable with non-controlled type, you can 
also do (in Ada 2005 only):

generic
    type Item_Type is private;
    with function "<"(L : Item_Type; R : Item_Type) return Boolean;
    with procedure Clear (Item : in out Item_Type) is null;
package Splay_Tree is ...

This way, a user does not need to provide a Clear procedure unless it is 
needed.
-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr