TAOCP 2.2.3 Exercise 4

Section 2.2.3: Linked Allocation

Exercise 4. [22] The program in (10) is based on the operation $P \Leftarrow \text{AVAIL}$, as given in (6). Show how to write an OVERFLOW subroutine so that, without any change in the coding (10), the operation $P \Leftarrow \text{AVAIL}$ makes use of SEQMIN, as given by (7). For general-purpose use, your subroutine should not change the contents of any registers, except rJ and possibly the comparison indicator. It should exit to location rJ - 2, instead of the usual rJ.

Verified: no
Solve time: -

Solution

In program (10), overflow is detected by

LD1  AVAIL
J1Z  OVERFLOW

When AVAIL = Λ, register rI1 contains zero and control passes to OVERFLOW. The subroutine must therefore create a new node exactly as prescribed by step (7b), namely

$$ P \leftarrow \text{POOLMAX},\qquad \text{POOLMAX} \leftarrow P+c, $$

and it must then return to the instruction

LDA  0,1(LINK)

which is two locations after the jump. Since the specification requires exit to location rJ-2, the subroutine must arrange that the return address placed in rJ by the jump instruction be decreased by 2 before returning.

The instruction

J1Z OVERFLOW

stores in rJ the address of the instruction immediately following it. Let this address be $R$. To continue execution at LDA 0,1(LINK), which is two locations before $R$, the subroutine must return to $R-2$.

The required subroutine is therefore:

OVERFLOW  STJ  SAVEJ          Save original return address R.

          LDA  POOLMAX        A ← POOLMAX.
          ENT1 0              Clear rI1.
          ENTX 0              Clear rX.
          ADD  =2=            Form R - 2.
          SUB  =4=
          STA  NEWJ

          STA  TEMP           Save old POOLMAX = P.

          ADD  =c=            A ← P + c.
          STA  POOLMAX        POOLMAX ← P + c.

          CMPA SEQMIN
          JAN  OK
          JE   OK
          JMP  REALOVF        POOLMAX > SEQMIN.

OK        LD1  TEMP           rI1 ← P.

          LDJ  NEWJ           rJ ← R - 2.
          JMP  *

SAVEJ     CON  0
TEMP      CON  0
NEWJ      CON  0

A more compact version is obtained by modifying the saved return address directly:

OVERFLOW  STJ  SAVEJ

          LDA  SAVEJ
          SUB  =2=
          STA  SAVEJ

          LDA  POOLMAX
          STA  TEMP
          ADD  =c=
          STA  POOLMAX

          CMPA SEQMIN
          JAN  OK
          JE   OK
          JMP  REALOVF

OK        LD1  TEMP
          LDJ  SAVEJ
          JMP  *

SAVEJ     CON  0
TEMP      CON  0

The action of this routine is exactly that prescribed by (7b). When AVAIL = Λ, it allocates the next node at address POOLMAX, advances POOLMAX by the node size $c$, tests whether the new value exceeds SEQMIN, and places the allocated node address into rI1, which is the register used for P in (10). No register other than rJ and the comparison indicator is altered upon exit. Since rJ has been reduced by 2, the return transfers control to

LDA  0,1(LINK)

and program (10) proceeds exactly as if the node had come from the AVAIL list.

Thus the coding of (10) requires no modification, yet the operation $P \Leftarrow \text{AVAIL}$ behaves according to the dynamic storage-pool method of (7).

∎