Module | TatungBytes

Introduction

Every variable so far was declared before the program ran, and there were exactly as many as were declared. But some things grow as you go. Every move the worker makes in Warehouse must be remembered, so that it can be undone, and nobody knows beforehand how many moves there will be. For that, a program needs to make new variables as it runs - and let go of them when they are no longer wanted.

New, And Pointers

type
  MoveP = ^Move;
  Move = record
    Dir: Char;
    Next: MoveP;
  end;
var
  P: MoveP;

^Move means "a pointer to a Move". A pointer is not a Move itself; it is the machine's note of where one is. MoveP is declared before Move: a pointer type may name a type that is only declared after it.

New(P) makes a new, nameless Move somewhere in memory and sets P to point at it. P^ - the pointer with a ^ after it - is the Move it points at, and its fields are reached as usual: P^.Dir := 'U'.

On the Einstein, ^ is the UP arrow key, and the screen draws it as an up arrow (S3).

The special value nil points at nothing. A pointer that is nil is how a list says "this is the end".

A List

Each Move has a Next field, a pointer to another Move. That lets moves be chained together, each pointing at the one before, with a pointer called Top at the newest:

procedure Push(D: Char);
var
  P: MoveP;
begin
  New(P);
  P^.Dir := D;
  P^.Next := Top;
  Top := P;
end;

Each new move is linked in front of the old top and becomes the top. Walking the list means following the pointers until one is nil:

P := Top;
while P <> nil do
begin
  Write(P^.Dir);
  P := P^.Next;
end;

and the moves come out newest first - exactly the order undo needs.

Giving Memory Back

The memory for these variables comes from a store called the heap, and the heap is not endless. MemAvail says how many bytes are free in it. When a variable is finished with, Dispose(P) gives its memory back, and the next New can use it again:

P := Top;
Top := Top^.Next;
Dispose(P);

Forget the Dispose, and the memory is lost to the program for as long as it runs. Keep that up in a long game, and the heap fills: the New that finds no room stops the program with

Run-time error FF

Turbo has a second way to give memory back: Mark(P) notes where the heap has got to, and Release(P) frees everything made since, all at once. Borland's manual warns that a program should use either Dispose or Mark and Release, not both. This course uses Dispose.

The Code

program Undo;
type
  MoveP = ^Move;
  Move = record
    Dir: Char;
    Next: MoveP;
  end;
var
  Top: MoveP;

procedure Push(D: Char);
var
  P: MoveP;
begin
  New(P);
  P^.Dir := D;
  P^.Next := Top;
  Top := P;
end;

procedure Pop;
var
  P: MoveP;
begin
  if Top <> nil then
  begin
    Write('undo ', Top^.Dir, ' ');
    P := Top;
    Top := Top^.Next;
    Dispose(P);
  end;
end;

begin
  Top := nil;
  Writeln('Free: ', MemAvail);
  Push('U'); Push('R');
  Push('R'); Push('D');
  Writeln('Free: ', MemAvail);
  Pop; Pop;
  Writeln;
  Writeln('Free: ', MemAvail);
end.

Four moves - up, right, right, down - are remembered, and then the last two are undone.

Starting from

Turbo freshly started, Y, a new work file called UNDO.

What you should see

Free: 25645
Free: 25629
undo D undo R
Free: 25637

The free figures will depend on your program exactly as typed; what matters is that four moves take 16 bytes, and undoing two gives 8 back. The undos come out in reverse order: the last move first.

Change One Thing

Delete the line Dispose(P);. What happens to the last Free figure?
Change Pop; Pop; to six Pops. How many undos are printed, and why does the program not go wrong when the list runs out?
Print MemAvail after the first two Pushes as well. How much does each move cost?

Exercises

22.1 Push each letter of the word WAREHOUSE, then pop until the list is empty. What comes out?

22.2 Write a function Count that walks the list and returns how many moves it holds. Push three, print the count, pop one, print it again.

22.3 Use Mark and Release to make fifty moves and free them all at once, printing MemAvail before, during and after.

Worked solutions are in Appendix II.

When It Goes Wrong

Symptom	Cause
`Run-time error FF` at a `New`	The heap is full - perhaps because memory is never given back with `Dispose`.
Free memory keeps falling as the program runs	Variables made with `New` and never `Dispose`d.
A list walk never ends, or prints rubbish	The last `Next` was never set to `nil`, or `Top` was never set to `nil` at the start.
`^` looks like an arrow	That is how the Einstein draws it; it is typed with UP.

Summary

^T is a pointer to a T. New(P) makes a new T, and P^ is it. nil points at nothing and marks the end of a list. Records that point to each other make a list that grows and shrinks as the program runs. Dispose gives a variable's memory back for the next New; MemAvail says how much is free.

S23, Where Text Goes - clearing the screen and putting text exactly where you want it: the first step to drawing a warehouse.

← Previous Next →

Pointers