Instructor's Manual for

M.B. Feldman and E.B. Koffman, Ada 95 Problem Solving and Program Design, 3rd edition. Copyright 1999, Addison-Wesley Publishing Company. All Rights Reserved Reserved

Questions and comments to mfeldman@seas.gwu.edu

---

Chapter 15 Access Types and Dynamic Data Structures

last revised March 1999

Chapter Objectives

The student will

1. learn how to manipulate access (pointer) variables in Ada
2. learn how to construct and use linked lists
3. learn about stacks and queues

New Terms

Section 15.1

pointer	access type
designate	storage pool
linked data structure	dereference
inaccessible block	storage leak

Section 15.6

stack

queue

General Suggestions

Ada attempts to make linked-list programming safer than in other languages. Specifically.

• Access values (pointers) are automatically initialized to NULL; a "garbage" pointer is therefore less likely to occur.
• An attempt to dereference a NULL pointer results in the raising of Constraint_Error instead of the "core dump" we expect from C.

On the other hand, some problems are more fundamental to linked-list programming and cannot be solved within the language; they must be prevented by careful programming. Specifically:

• Inaccessible blocks are caused by program bugs and cannot be prevented by a language or compiler; therefore, storage-leak prevention is still the programmer's responsibility.
• Aliasing cannot be prevented either; it is up to the programmer to ensure that no attempt is made to dereference an alias to a block that was deallocated through a different pointer. Ada's "dispose" procedure is called Unchecked_Deallocation precisely because it is generally infeasible to check for aliases.

Section 15.1

This long section introduces much new terminology regarding dynamic allocation, and will require quite a bit of class time to cover. Go over the various diagrams and their relationships to the code segments. Emphasize the importance of drawing pictures, and tracing, in understanding linked structures. Be sure students understand that copying one access value (pointer) to another copies only the pointer, not the designated block. Pictures are immeasurably helpful here.

Students may ask about pointers vs. addresses. Point out that there is no requirement that a pointer have the same internal form as an address (a pointer might be simpler than a full machine address).

The notion of inaccessibility is very important; make sure it is clear and that the students understand that repeatedly creating inaccessible blocks causes storage leaks, which have a way of creeping even into industrial-strength programs.

Students will ask why these blocks are not reclaimed automatically; explain that while Ada 95 is designed to make garbage collection feasible, compilers typically do not support it because most customers of Ada 95 compilers do not want it. Developers of real-time systems, in particular, shy away from garbage collection because they perceive it to be unpredictable in its space and time requirements.

In explaining Unchecked_Deallocation, be sure to point out the aliasing problem described on p.640.

Section 15.2

It is instructive to compare the iterattive and recursive implementations of the list operations.

Section 15.3

Compare the single-pointer and two-pointer implementations of the list operations.

Section 15.4

InsertInOrder is an especially difficult algorithm to write correctly. Splitting it into the four cases given here greatly simplifies the problem.

Section 15.5

Completing the generic linked list package, then using it in some application, makes for a good student project.

Section 15.6

This section gives only a brief overview of stack and queue applications, but it is helpful to show students a real use for linked lists.

Section 15.7

If you assign a project using linked lists, spend some time going over this section to show students where the pitfalls are. Avoiding the dereferencing-null-pointer problem is an especially nice use of Ada's short-circuit evaluation of Boolean expressions.