Previous Table of Contents Next


10.4.3.8. Dynamic Data Structures

The dashboard example made use of a generic linked list package, HB.Lists_Generic, detailed discussion of which was deferred until this point. Here is the interface of Lists_Generic.

    1 with Ada.Finalization;
    2 generic
    3   type ElementType is private;
    4   with procedure DisplayElement (Item: in ElementType);
    5 package HB.Lists_Generic is
    6
    7   type List is private;
    8
    9   procedure MakeEmpty (L : in out List);
   10   procedure AddToEnd
   11     (L: in out List; Element: in ElementType);
   12   function “=”(L1, L2: List) return Boolean;
   13   procedure Display (L: in List);
   14
   15 private
   16
   17   type ListNode;
   18   type ListPtr is access ListNode;
   19   type ListNode is record
   20     Element: ElementType;
   21     Next: ListPtr;
   22   end record;
   23
   24   type List is new Ada.Finalization.Controlled
   25   with record
   26     Head: ListPtr;
   27     Tail: ListPtr;
   28   end record;
   29
   30   procedure Initialize (L : in out List);
   31   procedure Finalize (L: in out List);
   32   procedure Adjust (L : in out List);
   33
   34 end HB.Lists_Generic;

Like most modern linked-structure systems, this package depends on the language support for dynamic storage allocation. Ada provides for such allocation; the term storage pool is used to refero the “heap” from which blocks of memory are dynamically drawn. Ada also provides for deallocation of individual blocks; a deallocated block is returned to the storage pool.

The Ada standard allows, but does not require, automatic deallocation, sometimes called “garbage collection.” In simple terms, garbage collection is not required because developers of real-time systems feel strongly that this would lead to unpredictable runtime overhead and therefore prefer that programmers control their own storage reclamation. As you shall see shortly, Ada does provide useful mechanisms to make it easier for programmers to do this reliably.

I return shortly to the meaning of the context clause in line 1. Mean-while, lines 3 and 4 give, as usual, the generic formal parameters, actuals for which an instantiating client is required to supply. The first parameter is ElementType, which describes the kind of object to be contained in each node. Recall from the earlier matrices discussion that in this context, private indicates that any type, including a private one, but not including a limited or tagged one, can be supplied to “match” ElementType (the dashboard example used HB.Instruments.Aux.InstrumentPointer). The second parameter is DisplayElement, which describes how to display an object of type ElementType (the dashboard case used HB.Instruments.Aux.Display).

Now the public part of the interface provides a private type List and four operations, just enough to be illustrative. Additional operations would be straightforward linked-list manipulations; I choose here to omit them for brevity’s sake.

MakeEmpty removes all the nodes in a list and returns them explicitly to the storage pool. In the absence of garbage collection, one cannot simply disconnect a linked list from its header; all the lists’s nodes would remain allocated but inaccessible.

AddToEnd is straightforward; given an element, this operation just adds a node containing the element to the tail of the list. Display is equally straightforward; it iterates through the list, calling DisplayElement at each node.

Before discussing “=”, I examine the data structures in the private section of the interface. First, lines 19-22 describe the node type as a record with an element and a forward link to the next node. This link is of type NextPtr. Because Ada requires types to be declared before they are used, line 18

   type ListPtr is access ListNode;

declares the pointer type. Now ListNode seems to be used before it is declared. I therefore declare it as an incomplete (“forward”) declaration in line 17. This three-part declaration is the conventional Ada idiom for declaring linked structures.

Now lines 24-28 declare the list structure itself as a header block, a pair of pointers designating the first and last nodes, respectively, of the list (I explain shortly why it is an extension of a tagged type Ada.Finalization.Controlled).

The overloaded operator (“=”) is interesting. Given lists L1 and L2, this is a “deep” equality test that returns True if and only if the contents of the lists are equal, that is, if the element in each node of L1 is equal to the element in the corresponding node of L2. Recall from the Rationals discussion that equality-test (and inequality test) are predefined for private types, so this “=” overrides the predefined one.

All I can expect of predefined equality is that it will compare these header blocks. If the two header blocks are equal, they are pointing to the same list. If they are unequal, predefined equality will return False, of course, but the two lists might still be equal in the “deep” sense I require. I need my own “=” operator to provide this deep testing.


Previous Table of Contents Next