Simple data structures written in Ada 95

Product Family: SCORE
Target CPU: PC/Windows, SPARC/Solaris, 1750A, 80x86, PowerPC
Language: Ada, C
Host: PC/Windows, Sparc/Solaris

Ada 95 offers several language features useful for writing flexible data structures, sometimes called containers, like list, sets, stacks and so on.

The following article shows simple examples of generic packages defining such data structures using various Ada language features like type extensions, controlled types, child library units, allocators and general access types. In these examples we make use of linked structures allocated on the heap.

The Ada predefined library is hierarchical in the sense that the units are organised into a tree-structure with only 3 root units: Ada, Interfaces and System.

 

Data

Data.Stacks Data.Lists Data.Sets Data.Maps

As the system evolves, it is anticipated that there will be further levels in the hierarchy above.

In the root package, Data, there will be no externally visible declarations, but the private part contains the most basic declarations that must be used throughout the hierachy. Since we want to implement the containers using linked structures, the most basic declarations are for links themselves. We define a link as a tagged record, such that we can extend it. For example, we want to extend it to be used as a stack element in the Data.Stacks package. This will be shown later. We also need a pointer type to be used for pointing between the individual elements of the linked structures. This pointer type is declared as a pointer to the class-wide type rooted at Link, because we want it to be useable for any extension we might make of Link. We will return to that too. The basic characteristic of a link is that it contains a pointer to the next link element:

package Data is

private

   type Link;

   type Link_Ptr is access all Link'Class;

   type Link is tagged
      record
         Next : Link_Ptr;
      end record;

end Data;

Note that the declarations are all placed in the private part, because they are useful only for the child packages of Data, not for any user of the data packages.

We could have chosen to add a procedural interface for linking in and linking out, but in this case we choose to manipulate the Next component directly, as this is extremely simple. Later we will choose otherwise for doubly-linked structures, because here the link manipulations are significantly more complicated. We can thus benefit from writing the complicated link manipulation once and for all rather than in all the data structure packages using the double-link.

Already now, we have enough machinery to define the first (and simplest) data structure, namely the stack. We want one general stack package and write the stack operations once irrespective of the stack element type. Therefore, we write a generic package taking the element type as a formal type. We write this package in a couple of small steps. First we define the type without any operations. To obtain information hiding, the stack type itself is private. The full declaration is a controlled type in order to get automatic garbage collection when stacks go out of scope. Note that since Ada defines that any object of an access type is default-initialized to null, a stack object is always default-initialized to be empty.

with Ada.Finalization;

generic
   type Elem is private;
package Data.Stacks is

   type Stack is private;

private

   type Stack_Elem is new Link with
      record
         Data : Elem;
      end record;

   type Stack_Elem_Ptr is access all Stack_Elem;

   type Stack is new Ada.Finalization.Controlled with
      record
         Top_Of_Stack : Stack_Elem_Ptr;
      end record;

end Data.Stacks;

Note that the stack elements are declared as extensions to the link type declared in the parent package Data. Each stack element thus contains a pointer to the next element as well as the actual data.

Let's now add the stack operations. Externally visible are the standard operations Push, Pop, Top and Is_Empty. Hidden is the finalization procedure that will be invoked automatically to garbage collect all the stack elements allocated (and not already free'ed by the user program) when a stack goes out of scope.

with Ada.Finalization;

generic
   type Elem is private;
package Data.Stacks is

   type Stack is private;

   procedure Push
     ( S : in out Stack;
       E :        Elem );

   procedure Pop( S : in out Stack );

   function Top( S : Stack ) return Elem;

   function Is_Empty( S : Stack ) return Boolean;

private

   type Stack_Elem is new Link with
      record
         Data : Elem;
      end record;

   type Stack_Elem_Ptr is access all Stack_Elem;

   type Stack is new Ada.Finalization.Controlled with
      record
         Top_Of_Stack : Stack_Elem_Ptr;
      end record;

   procedure Finalize ( S : in out Stack );

end Data.Stacks;

It is a simple matter to write the body of this package. The Pop operation will free the heap space no longer linked into the stack. Note that the strong typing rules of Ada require type conversions when stack element pointers are to be used as link pointers and vice versa. The implementation guarantees that these conversions are always safe.

with Ada.Unchecked_Deallocation;

package body Data.Stacks is

   procedure Free is 
          new Ada.Unchecked_Deallocation
        ( Stack_Elem, Stack_Elem_Ptr );

   procedure Push
     ( S : in out Stack;
       E :        Elem ) is
   begin
      S.Top_Of_Stack := new Stack_Elem'
                        ( Next => 
                        Link_Ptr(S.Top_Of_Stack),
                        Data => E );
   end Push;

   procedure Pop( S : in out Stack ) is
      New_Top : constant 
                Stack_Elem_Ptr := Stack_Elem_Ptr
                          (S.Top_Of_Stack.Next);
   begin
      Free( S.Top_Of_Stack );
      S.Top_Of_Stack := New_Top;
   end Pop;

   function Top( S : Stack ) return Elem is
   begin
      return S.Top_Of_Stack.Data;
   end Top;

   function Is_Empty( S : Stack ) return Boolean is
   begin
      return S.Top_Of_Stack = null;
   end Is_Empty;

   procedure Finalize ( S : in out Stack ) is
   begin
      while not Is_Empty( S ) loop
         Pop( S );
      end loop;
   end Finalize;

end Data.Stacks;

The Finalize procedure was easily written using the Is_Empty and Pop operations. The rules of Ada will ensure that finalize is called any time a stack goes out of scope, no matter whether this happens because of normal exit, subprogram return, an exception being raised or a task dying.

We end this article by showing one example of an instance of a stack package and a tiny use of it. This is how you create a package for integer stacks:

with Data.Stacks;
package Integer_Stacks is new Data.Stacks( Integer );

and here is a little example of uses of it:

with Integer_Stacks;   use Integer_Stacks;
with Report;

procedure Test_Integer_Stacks is
begin

   declare
      S : Stack;
   begin
   Push( S, -2 );
      Push( S, 7 );
      if Top( S ) /= 7 then
         Report.Failed( 1 );
      end if;
      if Is_Empty( S ) then
         Report.Failed( 2 );
      end if;
   end;   -- Finalize is called implicitly here

   Report.Result;

end Test_Integer_Stacks;

Note that the example program never pops the pushed elements. This will not cause memory leaks, because the Finalize operation will be invoked automatically on S immediately before exiting the block (see the comment).

This ends the first and simplest example of a data-structure package in the Data hierarchy. In a later article we will return to other more complex data-structures.