Hello,
Reading Ada 2012 and other resources online I cannot figure out how allocation and deallocation are supposed to work in Ada further than new|malloc and Unchecked_Deallocation|free.
For example, if I want to implement a binary tree data structure, how should it be done so that memory is freed when I am finished with it?
I understand that I could do Unchecked_Deallocation for every new, but from what I have read it seems like storage pools can make it work like arenas that are freed all at once. Hence, the preferred way would be for the entire tree to be deallocated in an equivalent way to arena_free.
Furthermore, any advice on another, (better?) approach that I cannot devise is also appreciated.
Thanks in advance.
– zen
I have never used pools myself, but here is how I would go about it.
I assume that you want to allocate very many times, grow the tree, and then, once you are done with it, nuke it out of existence. If that is the case, arenas seem pretty good for that.
I would declare a Pool and then create an access with a pool aspect pointing to that pool. The tree would then use that access type as part of its declaration/data structure. All the new operations will be automatically routed to the Pools specific allocator. Once you are done with the tree, you can nuke/empty the Pool in one go with Deallocate_Subpool.
I hope this helps. Best regards,
Fer
Btw,
if you are going to be deallocating a lot of data in one go (not just the tree in question), you may want to create a set of subpools within a larger pool. Then, instead of having to deallocate several subpools sequentially, you can just deallocate the parent pool, which will clean everything else.
This could be useful for example in a videogame where one may allocate a lot of data everyframe and once the frame is computed, the entire thing can be cleaned off in one go and start anew in the next frame.
Best regards,
Fer
In order to implement arena in Ada you can use:
- A subpool (ARM 13.11.4)
- A mark and release pool (LIFO, Unchecked_Deallocation releases all up to the pointer, e.g. the node allocated first)
The second option is more flexible because you can have a fine control over the allocation strategy (LIFO, chunking etc). Note that a custom pool can take memory from another pool, e.g. the standard pool. So you need not to implement some sophisticated memory management algorithm. You can also use a plain array to back it, e.g. if you have an embedded target and what to limit the total memory amount.
For obvious reasons you should be careful with controlled types or any types requiring finalization.
You can take a look at Simple Components implementation of such memory pools.
Note also that Ada’s pools and pool-specific access types provide a very powerful mechanism. You can implement a tree that has only data and keeps all link structure in the pool fully transparent to the nodes. As an example see implementation of graphs and doubly-linked lists in Simple Components.
Sounds like controlled types might be helpful for what you want, from package Ada.Finalization. These allow you to automatically manage resource allocation/deallocation when the object is initialized, assigned, or finalized (e.g. when the object goes out of scope), similar to C++ destructors.
Some resources you might find useful to learn more about controlled types and finalization:
Before going down this route, watch Memory Management with Ada 2012.
Note how scope is used to control memory: Once a type leaves scope, there can no longer be any accesses to that type, and therefore the compiler can free all accesses to that type. This method works even without any accesses; example:
Declare
-- Here we allocate the memory for the result of GET_LINE.
Answer : String renames Ada.Text_IO.Get_Line;
Begin
if Answer = "QUIT" then Do_Exit;
elsif Answer = "LIST" then Do_Listing;
else Ada.Text_IO.Put_Line( "Invalid COmmand." );
end if;
End;
-- …and here Answer's memory is freed.
The second method is by deriving from Ada.Finalization.Controlled or Ada.Finalization.Limited_Controlled, which (using tagged-types) hooks to the initialization and finalization of objects, allowing you to use Unchecked_Deallocation on anything you allocated for the object. — One “dirty trick” is to use a not null access within your object, then (in finalize) overlay it with an access (of the same type) which is not not null and call the Unchecked_Deallocation on that: approaching things this way (where appropriate) keeps you from the null trip-hazard during “normal operation”, only having to work around that restriction during the cleanup (that is, violating the constraint of not null).
Ada 83 did not have Get_Line as a function. I remember a quite impressive implementation of a function that used recursive calls. I leave that for you as an exercise.
But no, there is no recursive types in Ada, so you cannot do that for trees.
?
While I know that implementation, here, but that has nothing to do with the point: he was asking about managing memory and I used a simple example to show memory management w/o an access type. — You absolutely can use this for trees, provided that your entire definition and use are within the same declarative region (esp. as you can flatten a balanced binary tree into an array), you could (as example) constrain an entire AST into the declarative region of a function that takes the token-stream and produces an IR.
You can also specify the Storage_Size aspect for the access type; RM 13.11(18/6).
type Ac_T is access T with Storage_Size => whatever;
An implementation-defined storage pool will then be used. If the access type goes out of scope, the storage is reclaimed.
Note: This is not true if Storage_Size is not specified.
This is the simplest method.
You cannot spell a tree type without access types. q.e.d.
Ok, thanks everyone for the responses, I think I am getting somewhere.
Do you know some practical example that does something similar, so that I can see how they do it?
Cheers
– zen
Here is an Ada 2022 expression parser. The abstract syntax tree is allocated in the arena. The following generates a Graphviz output of the tree:
with Ada.Exceptions; use Ada.Exceptions;
with Ada.Text_IO; use Ada.Text_IO;
with Parsers.String_Source; use Parsers.String_Source;
with Parsers.Generic_Ada_Parser.Generic_Dot;
procedure Parsing_Tree_Example is
package Ada_Parsers is
new Parsers.Generic_Ada_Parser (Parsers.String_Source.Code);
package Dot is new Ada_Parsers.Generic_Dot;
Text : aliased String := "A + B + C * D + E / 1.2";
Input : aliased Source (Text'Access);
Parser : Ada_Parsers.Ada_Expression;
Result : Ada_Parsers.Tokens.Argument_Token;
Stub : Ada_Parsers.Node_Ptr;
begin
Stub := new Ada_Parsers.Mark; -- Mark the stack
Ada_Parsers.Lexers.Parse (Parser, Input, Result);
Dot.Put (Result, "tree.dot", False);
Ada_Parsers.Free (Stub); -- Release the tree on the stack
exception
when Error : others =>
Put ("Error :");
Put_Line (Exception_Information (Error));
end Parsing_Tree_Example;
Yes, you can.
- Flattening into an array can be achieved by noting that:
- Parent of node at index
i: → i / 2.
- Left child of node at index
i: → 2*i
- Right child of node at index
i: → 2*i + 1
- Using
Ada.Containers.Multiway_tree.
As I said, you can’t use technique #1 in all places, but you can use it. And technique #2 is arguably using accesses, though it is arguable since those mechanisms aren’t “on full display”.
(The array technique is best for constant or semi-constant data, mapping decently well onto where unconstrained arrays are useful. A good example of constant data would be in the grammar for a language, since it’s not going to be changing.)
This is not a legal Ada code.
GNAT implementation of:
type Tree_Node_Type is record
Parent : Tree_Node_Access;
Prev : Tree_Node_Access;
Next : Tree_Node_Access;
Children : Children_Type;
Element : aliased Element_Type;
end record;
No, it is not arguable. The question was specifically about an implementation. The answer is: it is not possible to implement trees without access types (or an equivalent).
What is possible is an implementation that would allocate the tree strictly on the stack. One can use a pool backed by an array. Upon Adjust one would walk the tree and fix access types by adding an offset (ARM 13.7.1-2).
P.S. It is interesting to note that PL/1 had support for such stuff. It has pointers and offsets.
What? You want a full implementation?
Declare
-- Array_Tree needs to have a FIRST of 1 for the indexing to map.
Type Array_Tree is Array( Positive range <> ) of Integer;
Type Cursor(Max_Index : Natural) is record
Current : Natural;
end record;
Function Create( Object : Array_Tree ) return Cursor is
( (Max_Index => Object'Last, others => 1) );
Procedure Parent( Object : in out Cursor ) is
Begin
Object.Current:= @ / 2;
End Parent;
Procedure Left( Object : in out Cursor ) is
Begin
Object.Current:= @*2;
if Object.Current > Object.Max_Index then
Object.Current := 0;
end if;
End Left;
Procedure Right( Object : in out Cursor ) is
Begin
Object.Current:= Positive'Succ(@*2);
if Object.Current > Object.Max_Index then
Object.Current := 0;
end if;
End Right;
Tree : Constant Array_Tree:=
( 1 => 45,
-- / \
-- / \
2 => 18, 3 => 56,
-- / \ / \
4 => 8, 5 => 23, 6 => 108, 7 => 256
);
Begin
Null; -- Whatever processing you need.
End;
Obviously I could have bound the Cursor to the array via discriminant, but I get the feeling you would cite that as violating my claim that it can be done without accesses.
How Cursor is different from an access type?
BTW, this is how we programmed in FORTRAN which had no pointers. I remember a linear algebra library that allocated vectors and matrices this way.
Ideologically, it’s not; it serves pretty much the same purpose, but I did it to bundle/map the indexing logic to the record.
Then, if you knew of the technique, did you object to citation of it?
Because it is not what was asked. It is semantically a pointer and it is not a tree type. You presented two types:
- One is an equivalent of a memory pool
- Another is an equivalent of access type to the pool.
None of them is a tree. This is why it does not qualify, forgetting that it is utterly atrocious. Even C could better that early FORTRAN.
There is no solution.
BTW, for singleton trees one could use generics:
generic
type Left_Type is private;
type Right_Type is private;
package Balanced_Node is
type Node is record
Left : Left_Type;
Right : Right_Type;
end record;
end Balanced_Node;
generic
type Left_Type is private;
package Left_Node is
type Node is record
Left : Left_Type;
end record;
end Left_Node;
generic
type Right_Type is private;
package Right_Node is
type Node is record
Right : Right_Type;
end record;
end Left_Node;
package T1 is new Left_Node (Integer);
package T2 is new Balanced_Node (Integer, T1.Node);
package T3 is new Balanced_Node (T1.Node, T2.Node);
and so on. It is a cool way to break the compiler. I wonder the point when GNAT would give up. 
Hi, I think now I partly understand. If I understood correctly, you roll out your own Stack_Storage, which uses an unbounded array and serves as the pool of memory. Thus this is equivalent to an Arena.
On another side, I also see the use of new and Free in the following:
-- stack_storage.ads
procedure Free is new Ada.Unchecked_Deallocation (Block, Block_Ptr);
procedure New_Block
( Stack : in out Pool;
Size : Storage_Count
) is
Ptr : Block_Ptr;
begin
if Stack.Block_Size < Size * 2 then
Stack.Block_Size := Size * Storage_Count (Stack.Items_Number);
end if;
Ptr := new Block (Stack.Block_Size);
Put (Stack.Blocks, Stack.Current + 1, Ptr);
Stack.Current := Stack.Current + 1;
Stack.Last := Stack.Last + 1;
Stack.Total_Size := Stack.Total_Size + Stack.Block_Size;
exception
when others =>
Free (Ptr);
raise;
end New_Block;
But under normal circumstances it seems to me like the Block is not freed. The access type was declared inside a static package, so the storage would not be reclaimed. What is it that I am not seeing here?
Nice, I will save this for the future 
. Funnily enough, it is for allocating videogame graphic elements that I am looking for this.