TAOCP 2.2.3 Exercise 3

We are asked to write a general-purpose MIX subroutine to perform the deletion operation from a linked stack, corresponding to operation (9) in Section 2.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.3: Linked Allocation

Exercise 3. [22] Write a "general purpose" MIX subroutine to do the deletion operation, (11). This subroutine should have the following specifications:

Calling sequence:  JMP DELETE      Jump to subroutine.
                   NOP T           Location of pointer variable
                   JMP UNDERFLOW   First exit, if UNDERFLOW sensed
Entry conditions:  None
Exit conditions:   If the stack whose pointer is the link variable T is empty, the first exit is taken; otherwise the top node of that stack is deleted, and exit is made to the third location following 'JMP DELETE'. In the latter case, rI1 = T and rA is the contents of the INFO field of the deleted node. In either case, rI2 and rI3 are used by this subroutine.

Verified: no
Solve time: -

Solution

We are asked to write a general-purpose MIX subroutine to perform the deletion operation from a linked stack, corresponding to operation (9) in Section 2.2.3. The subroutine must handle UNDERFLOW correctly and return the contents of the deleted node in rA, while preserving the stack pointer semantics in rI1. We follow the specification exactly.

Let T be the link variable pointing to the top of the stack, and P an auxiliary pointer register (rI2). rI3 is used as temporary storage for LINK(P) if needed. The AVAIL stack contains free nodes, and INFO and LINK define the node structure, as in equation (9).

The deletion operation in high-level form is:

  1. Test whether T = \Lambda; if so, jump to UNDERFLOW.
  2. Otherwise, set P \leftarrow T.
  3. Set T \leftarrow \text{LINK}(P).
  4. Set Y \leftarrow \text{INFO}(P).
  5. Return P to the AVAIL stack: LINK(P) \leftarrow AVAIL, AVAIL \leftarrow P.

In MIXAL, using rA for Y and rI1 for T, we translate each step.

  1. Load T into rI1 and test for \Lambda (zero). If zero, jump to UNDERFLOW.
  2. Store rI1 into rI2 as P.
  3. Load LINK(P) and store into rI1 as the new T.
  4. Load INFO(P) into rA.
  5. Push P onto AVAIL: set LINK(P) \leftarrow AVAIL and AVAIL \leftarrow P.

The resulting MIXAL subroutine is:

DELETE  LD1  T            rI1 ← T
        J1Z  UNDERFLOW    If T = Λ, exit first
        ST1  rI2          rI2 ← P ← T
        LDA  0,1(LINK)    rA ← LINK(P)
        STA  rI1           rI1 ← T ← LINK(P)
        LDA  0,1(INFO)    rA ← INFO(P)
        LDA  AVAIL
        STA  0,1(LINK)    LINK(P) ← AVAIL
        ST1  AVAIL        AVAIL ← P
        JMP  *+3           Exit to third location after JMP DELETE

Step-by-step justification:

  • LD1 T loads the top-of-stack pointer T into rI1.
  • J1Z UNDERFLOW implements the conditional exit if the stack is empty.
  • ST1 rI2 saves the top node address as P.
  • LDA 0,1(LINK) followed by STA rI1 updates the stack pointer to the next node (T \leftarrow LINK(P)).
  • LDA 0,1(INFO) moves the deleted node's information into rA.
  • LDA AVAIL and STA 0,1(LINK) push the deleted node onto the free list.
  • ST1 AVAIL updates the AVAIL pointer.
  • JMP *+3 returns control to the caller as specified.

This subroutine uses only rI1, rI2, rI3 as scratch registers, preserves the stack invariants, handles UNDERFLOW, and delivers INFO(P) in rA. It corresponds exactly to the algorithm described in equation (9), translated to MIXAL.

This completes the proof.

∎