10.4.3.10. Implementing the Linked List Package

Now I examine the body of HB.Lists_Generic, which, given the preceding discussion, is mostly straightforward.

    1 with Ada.Unchecked_Deallocation;
    2 package body HB.Lists_Generic is
    3
    4   procedure Display(L: in List) is
    5     Current: ListPtr := L.Head;
    6   begin
    7     while Current /= Null loop
    8       DisplayElement(Current.Element);
    9       Current := Current.Next;
   10     end loop;
   11   end Display;
   12
   13   procedure AddToEnd
   14     (L: in out List; Element: in ElementType) is
   15   begin
   16     if L.Tail = Null then
   17       L.Tail := new ListNode’(Element, Null);
   18       L.Head := L.Tail;
   19     else
   20       L.Tail.Next := new ListNode’(Element, Null);
   21       L.Tail := L.Tail.Next;
   22     end if;
   23   end AddToEnd;
   24
   25   function “=”(L1, L2: List) return Boolean is
   26     Current1: ListPtr := L1.Head;
   27     Current2: ListPtr := L2.Head;
   28   begin
   29     while Current1 /= Null and Current2 /= Null loop
   30       if Current1.Element /= Current2.Element then
   31         return False;
   32       end if;
   33       Current1 := Current1.Next;
   34       Current2 := Current2.Next;
   35     end loop;
   36     return (Current1 = Null and Current2 = Null);
   37   end “=”;
   38
   39   procedure Adjust (L: in out List) is
   40     TempList: List;
   41     Current: ListPtr;
   42   begin
   43     Current := L.Head;
   44     while Current /= Null loop
   45       AddToEnd (TempList, Current.Element);
   46       Current := Current.Next;
   47     end loop;
   48     L.Head := TempList.Head;
   49     L.Tail := TempList.Tail;
   50     TempList.Head := Null;
   51     TempList.Tail := Null;
   52   end Adjust;
   53
   54   procedure Dispose is
   55     new Ada.Unchecked_Deallocation
   56       (Object => ListNode, Name => ListPtr);
   57
   58   procedure Finalize (L: in out List) is
   59     Current: ListPtr := L.Head;
   60     Leading: ListPtr;
   61   begin
   62     while Current /= Null loop
   63       Leading := Current.Next;
   64       Dispose(Current);
   65       Current := Leading;
   66     end loop;
   67     L.Head := Null;
   68     L.Tail := Null;
   69   end Finalize;
   70
   71   procedure MakeEmpty (L: in out List) is
   72   begin
   73     Finalize(L);
   74   end MakeEmpty;
   75
   76   procedure Initialize (L: in out List) is
   77   begin
   78     Finalize (L);
   79   end Initialize;
   80
   81 end HB.Lists_Generic;

Refer again to the linked list:

The context clause in line 1 mentions Ada.Unchecked_Deallocation. I explain this shortly. Now given a list like the preceding one, it is easy to see that the procedure in lines 4-11 declares a temporary pointer Current, initialized to the first node in the list. The while loop, in traditional linked-list programming style, walks down the list, calling DisplayElement to display each element in turn.

In AddToEnd (lines 13-23), I allocate a new node, store the element in it, and connect it to the list. If the list is initially empty, the new node is the first and only one, and

   L.Tail := new ListNode’(Element, Null);

stores in L.Tail a pointer to a new (heap-allocated) node with Element and Null in the corresponding fields. (Strictly speaking, the Null could have been omitted because that field is already Null; I include it for emphasis.) If the list already contains some nodes, then I connect the new node to the end of the list and change the Tail pointer accordingly (lines 20-21).

The overloaded (“=”) operator (lines 25-37) simply moves two temporary pointers down the two lists in parallel, returning False to the calling program if, at a given point in both lists, their elements disagree. The loop iterates until the end of one or both lists is reached. The two lists are equal (line 36) if and only both ends are reached at the same time.

Lines 39-52 give the implementation of the overriding Adjust procedure. Because Adjust has only one parameter, L, I make Adjust work as a deep copy operation by copying L into a temporary list, TempList, using AddToEnd in a straightforward while loop, and then I copy the head and tail pointers of TempList back into L. In this manner I return in L a list that is distinct from the one received in L. Now suppose a client program executes

   L1 := L2;

Because List is a controlled type, L1 is first finalized. Then the header block (head and tail pointers) of L2 are copied into L1. At this point, the Adjust is called. The client now has, in L1, a complete but distinct copy of L2, as desired.