The Heap

Introduction

Pointers, NEW, ^ and NIL are as the Turbo course's S22 left them, and a linked list of records is built exactly the same way. What is missing is Dispose. HiSoft Pascal cannot give back one variable at a time. It gives back memory the other way Turbo had, and the only way here: in a block, with MARK and RELEASE.

MARK And RELEASE

The variables NEW makes are laid out one after another in memory, each straight after the last - the first of them just past the end of your program. MARK(H) notes, in a pointer H, how far along they have got. RELEASE(H) goes back to that point: everything made since the MARK is gone, and the next NEW uses that memory again.

So the pattern is: MARK before a job that needs some variables for a while, and RELEASE when the job is done - all of them at once. The pointer given to MARK is kept only for MARK and RELEASE, and never given to NEW.

No Warning When It Is Full

Turbo told you when there was no memory left: Run-time error FF, and MemAvail to see it coming. HiSoft Pascal has neither. NEW never says the memory is full. A hundred NEWs of 2,000 bytes each - far more than the whole machine has - all go through without a word, so nothing stops a program running out and carrying on regardless. Keep your lists to a sensible size, and RELEASE what you have finished with.

The ^ is typed with the UP arrow key, as it was in Turbo.

The Code

Three rounds of building a list of five numbers and printing it, giving the memory back after each:

10 PROGRAM STACK;
20 TYPE NODE=RECORD V:INTEGER; NEXT:^NODE END;
30 LINK=^NODE;
40 VAR TOP,P,HEAP:LINK; I,R:INTEGER;
50 BEGIN
60 FOR R:=1 TO 3 DO
70 BEGIN
80 MARK(HEAP);
90 TOP:=NIL;
100 FOR I:=1 TO 5 DO
110 BEGIN
120 NEW(P); P^.V:=I*R;
130 P^.NEXT:=TOP; TOP:=P
140 END;
150 P:=TOP;
160 WHILE P<>NIL DO
170 BEGIN WRITE(P^.V); P:=P^.NEXT END;
180 WRITELN('AT ',ADDR(TOP^));
190 RELEASE(HEAP)
200 END
210 END.

Each new record goes on the front of the list, so the list prints in reverse. ADDR(TOP^) is the address of the last record made.

Starting from

STACK.ASC saved from XBAS; HPEIN STACK.

What you should see

5 4 3 2 1 AT 3947
10 8 6 4 2 AT 3947
15 12 9 6 3 AT 3947

The same address each round: every round's five records use the memory the round before gave back.

Change One Thing

• Take out line 190. What happens to the addresses now, and by how much do they go up each round? What does that tell you about the size of one record?
• Put line 190 back, and change it to DISPOSE(P). Will it compile?
• Add ,MEMAVAIL before the ) in line 180. Will that?

Exercises

13.1 Read numbers from the keyboard until 0 is typed, keep them in a list, and print them in reverse order.

13.2 In Exercise 13.1, RELEASE the list and read a second one. Show, with ADDR, that the second list uses the same memory.

Worked solutions are in Appendix II.

When It Goes Wrong

Summary

NEW, ^ and NIL work as in Turbo. There is no Dispose and no MemAvail: MARK(H) notes the point reached, RELEASE(H) gives back everything since. NEW never reports that memory is full.

Next

S14, Where Text Goes - PAGE, and putting the cursor anywhere without GotoXY.