Deallocation, Storage Pools & Linked Structures
Build linked lists and trees with incomplete type declarations, free memory with Ada.Unchecked_Deallocation, understand dangling pointers and leaks, 'Storage_Size and storage pools (subpools), and when to prefer containers or controlled types over manual memory management.
Ada has no mandatory garbage collector. Memory allocated with new is released either when its access type goes out of scope (for types declared in a subprogram, with GNAT), through a storage pool, or explicitly with an instance of Ada.Unchecked_Deallocation. The word 'Unchecked' is a warning: freeing memory is the one operation the language cannot check, so manual deallocation should be encapsulated inside abstractions.
Recursive Types
A node that points to other nodes needs an incomplete type declaration: 'type Node; type Node_Ptr is access Node; type Node is record Value : Integer; Next : Node_Ptr; end record;'. The incomplete declaration introduces the name so the access type can refer to it before its full definition. Trees follow the same pattern with Left and Right pointers. Recursive subprograms (Insert, In_Order, Height) mirror the recursive structure.
• type Node; — incomplete declaration. • type Node_Ptr is access Node; then the full record. • Recursive algorithms follow recursive data.
Unchecked_Deallocation
'procedure Free is new Ada.Unchecked_Deallocation (Object => Node, Name => Node_Ptr);' instantiates a deallocator. Free (P) releases the object and sets P to null. Any other access value that designated the same object is now dangling; using it is erroneous (undefined). Freeing null is a no-op. Controlled objects are finalized before their memory is released. Common patterns: pop and free in a stack, post-order Destroy for a tree.
• Instantiate Ada.Unchecked_Deallocation (Object, Name). • Free (P) releases and sets P := null; copies of P dangle. • Freeing null does nothing.
Storage Pools and Alternatives
Every access type has a storage pool that manages its allocations. 'for Node_Ptr'Storage_Size use 10_000;' bounds the pool (exceeding it raises Storage_Error). You can supply your own pool by deriving from System.Storage_Pools.Root_Storage_Pool (e.g. an arena freed all at once), and Ada 2012 subpools allow freeing groups of objects together. In practice, the safest option is to avoid manual memory management: use Ada.Containers (vectors, lists, maps, trees via Multiway_Trees) or wrap pointers in controlled types that free in Finalize.
• Each access type has a storage pool; 'Storage_Size limits it. • Custom pools: System.Storage_Pools; subpools for group deallocation. • Prefer Ada.Containers or controlled wrappers.
Code Examples
The stack pushes 10, 20, 30, 40 and pops in reverse, freeing each node. The BST prints keys in sorted order and has height 3; Destroy frees it in post-order. The final lines show the danger: Old is not nulled by freeing another variable, so it is now a dangling pointer (it must never be dereferenced). Output: Popped: 40 30 20 10 Live nodes after popping all: 0 In-order: 20 30 40 50 60 70 80 Height: 3 Root is null after Destroy? TRUE Popped 1; Old still points to freed memory: dangling! Old = null? FALSE (only the freed copy was nulled) Free (Top); Top:= Top.Next;
Old := Top; Top := Top.Next; Free (Old);
After Free, Top is null; read what you need before freeing.
Destroy (T) freeing the root before its children Destroy (T.Left); Destroy (T.Right); Free_Node (T);
Free children first (post-order), or you lose the pointers to them.
-- raw access types spread throughout an application -- encapsulate in a package, or use Ada.Containers / controlled types
Manual memory management is unchecked; keep it inside small, tested abstractions.
What does Free (P) do to P? A. Nothing B. Sets it to null C. Points it to the next node D. Raises an exception
B. Sets it to null (other copies remain dangling).
Why is 'type Node;' needed before 'type Node_Ptr is access Node;'? A. Performance B. To declare the name before its full definition (incomplete type) C. For generics D. It isn't
In which order must a tree be freed? A. Pre-order B. Post-order (children first) C. Any D. Level order only
What is usually the best alternative to manual linked lists? A. Ada.Containers.Doubly_Linked_Lists B. Arrays of addresses C. Unchecked_Conversion D. Global variables Trace the linked-structure example.
Real output: Popped: 40 30 20 10 Live nodes after popping all: 0 In-order: 20 30 40 50 60 70 80 Height: 3 Root is null after Destroy? TRUE Popped 1; Old still points to freed memory: dangling! Old = null? FALSE (only the freed copy was nulled)
Write a function Length (L : Node_Ptr) return Natural for the linked list.
function Length (L : Node_Ptr) return Natural is N : Natural := 0; P : Node_Ptr := L; begin while P /= null loop N := N + 1; P := P.Next; end loop; return N; end Length;
Walk the list with a cursor pointer until null.
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Unchecked_Deallocation;
procedure L32_Linked is
-- ---------- A linked stack ----------
type Node; -- incomplete type declaration
type Node_Ptr is access Node;
type Node is record
Value : Integer;
Next : Node_Ptr;
end record;
procedure Free is new Ada.Unchecked_Deallocation (Object => Node, Name => Node_Ptr);
Top : Node_Ptr; -- null = empty stack
Live_Nodes : Natural := 0;
procedure Push (V : Integer) is
begin
Top := new Node'(Value => V, Next => Top);
Live_Nodes := Live_Nodes + 1;
end Push;
function Pop return Integer is
Old : Node_Ptr := Top;
V : constant Integer := Top.Value;
begin
Top := Top.Next;
Free (Old); -- releases memory and sets Old to null
Live_Nodes := Live_Nodes - 1;
return V;
end Pop;
-- ---------- A binary search tree ----------
type Tree_Node;
type Tree is access Tree_Node;
type Tree_Node is record
Key : Integer;
Left, Right : Tree;
end record;
procedure Free_Node is new Ada.Unchecked_Deallocat
…