This page aims to serve as a companion to section 2.2.2 Sequential Allocation in The Art of Computer Programming. It can be easier to understand how these algorithms work by stepping through them and observing the changes made as the algorithm progresses. In some cases, more implementation details are visible than presented in the tables in the original text.

Multiple Stack Allocation

References

  • D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed. Addison-Wesley, 1997, p. 247-248.

Algorithms G, R

Reallocate sequential tables

G1. [Initialize.]

  • Set SUM = L∞ - L0, INC = 0.
  • Then do step G2 for 1 <= j <= n.
  • After this has been done, go on to step G3.

G2. [Gather statistics.]

  • Set SUM = SUM - (TOP[j] - BASE(j)).
  • If TOP[j] > OLDTOP[j], set D[j] = TOP[j] - OLDTOP[j] and INC = INC + D[j];
  • otherwise set D[j] = 0.

G3. [Is memory full?]

  • If SUM < 0, we cannot proceed.

G4. [Compute allocation factors.]

  • Set α = 0.1 * SUM/n, β = 0.9 * SUM/INC.

G5. [Computer new base addresses.]

  • Set NEWBASE[1] = BASE[1] and σ = 0;
  • then for j = 2, 3, ..., n set τ = σ + α + D[j-1]β, NEWBASE[j] = NEWBASE[j-1] + TOP[j-1] - BASE[j-1] + floor(τ) - floor(σ), and σ = τ.

G6. [Repack.]

  • Set TOP[i] = TOP[i] - 1.
  • Perform Algorithm R, and then reset TOP[i] = TOP[i] + 1.
  • Finally, set OLDTOP[j] = TOP[j] for 1 <= j <= n.

R1. [Initialize.]

  • j = 1.

R2. [Find start of shift.]

  • Increase j in steps of 1 until finding either:
    • a) NEWBASE[j] < BASE[j]: Go to R3; or
    • b) j > n: Go to R4.

R3. [Shift list down.]

  • Set δ = BASE[j]-NEWBASE[j].
  • Set CONTENTS(L-δ) = CONTENTS(L), for L = BASE[j]+1, BASE[j]+2, ..., TOP[j].
  • Set BASE[j] = NEWBASE[j], TOP[j] = TOP[j] - δ.
  • Go back to R2.

R4. [Find start of shift.]

  • Decrease j in steps of 1 until finding either:
    • a) NEWBASE[j] > BASE[j]: Go to R5; or
    • b) j == 1: The algorithm terminates.

R5. [Shift list up.]

  • Set δ = NEWBASE[j] - BASE[j].
  • Set CONTENTS[L+δ] = CONTENTS(L), for L = TOP[j], ..., BASE[j]+1.
  • Set BASE[j] = NEWBASE[j], TOP[j] = TOP[j] + δ.
  • Go back to R4.

References

  • D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed. Addison-Wesley, 1997, p. 248-250.