Previous | Table of Contents | Next |
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.
Previous | Table of Contents | Next |