TAOCP 2.2.3 Exercise 2

We are asked to write a general-purpose MIX subroutine to perform the linked-stack insertion operation corresponding to equation (10).

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.3: Linked Allocation

Exercise 2. [22] Write a "general purpose" MIX subroutine to do the insertion operation, (10). This subroutine should have the following specifications (as in Section 1.4.1):

Calling sequence:  JMP INSERT   Jump to subroutine.
                   NOP T        Location of pointer variable
Entry conditions:  rA = information to be put into the INFO field of a new node.
Exit conditions:   The stack whose pointer is the link variable T has the new node on top; rI1 = T; rI2, rI3 are altered.

Verified: no
Solve time: 35s

Solution

We are asked to write a general-purpose MIX subroutine to perform the linked-stack insertion operation corresponding to equation (10). The subroutine must follow the calling sequence and entry/exit conditions:

  • rA contains the information to be inserted into the INFO field of a new node.
  • T is the link variable pointing to the top of the stack.
  • On exit, the new node is on top of the stack, and rI1 = T.
  • Registers rI2 and rI3 may be used as temporaries.

The algorithm follows the steps of (8):

  1. P ← AVAIL
  2. INFO(P) ← Y
  3. LINK(P) ← T
  4. T ← P

In MIX, the corresponding operations are:

  1. Load AVAIL into a register (rI1) to serve as P.
  2. Test for overflow: if AVAIL = Λ, jump to OVERFLOW.
  3. Load the LINK field of P into rI2 and set AVAIL ← LINK(P).
  4. Store rA into INFO(P).
  5. Store T into LINK(P).
  6. Set T ← P and rI1 ← T.
  7. Return from subroutine.

A compact MIXAL implementation respecting the calling sequence is as follows:

INSERT:    LD1  AVAIL        ; rI1 ← AVAIL (P ← AVAIL)
           J1Z  OVERFLOW     ; if AVAIL = Λ, jump to OVERFLOW
           LDA  0,1(LINK)    ; rA ← LINK(P)
           STA  AVAIL        ; AVAIL ← LINK(P)
           LDA  rA           ; rA already contains info Y
           STA  0,1(INFO)    ; INFO(P) ← rA
           LDA  T            ; rA ← T
           STA  0,1(LINK)    ; LINK(P) ← T
           ST1  T            ; T ← P
           JMP  rJ           ; return from subroutine

Justification of steps

  • LD1 AVAIL sets rI1 = P = AVAIL, consistent with step 1 of (8).
  • J1Z OVERFLOW implements the overflow check of equation (6).
  • LDA 0,1(LINK) followed by STA AVAIL removes the top node from the AVAIL stack, implementing AVAIL ← LINK(P) of (4).
  • STA 0,1(INFO) stores the information from rA into INFO(P).
  • STA 0,1(LINK) sets LINK(P) ← T, linking the new node on top of the existing stack.
  • ST1 T updates the stack pointer T and satisfies the exit condition rI1 = T.
  • JMP rJ performs a standard MIX subroutine return.

This subroutine uses only the registers specified in the exercise (rA, rI1, with rI2 available for temporary storage if needed) and preserves the original variable names T, AVAIL, INFO, and LINK. The sequence of MIX instructions is minimal while preserving correctness.

This completes the solution.

∎