taocp, sequential allocation questions

Question

hi all, i've run into few problems while working tacop 2.2.2 sequential allocations, repacking memory section at page 247.

the subject is there are n stacks sharing a common area locations L0 < L < LX, initially we set BASE[j] = TOP[j] = L0 for 1 <= j <= n

the goal is when overflow occurs while inserting or deleting elements with respect to stack i, how to repack memory. (making room for stack i by taking some away from tables that aren't yet filled).

a). find the smallest k for which i < k < n and TOP[k] < BASE[k+1], if any such k exists. move things up one notch, Set CONTENTS(L+1) -> CONTENTS(L), for TOP[k] >= L > BASE[i+1] finally, Set BASE[j] -> BASE[j] + 1, TOP[j] -> TOP[j] + 1, for i < j < k

here's my questions:

how do they find the stack that aren't yet to be filled? stack k? and why chose the smallest k?

Answer 1

To find the stack that isn't yet filled, the basic idea used is the fact:

Stack k is not full <==> TOP[k] < BASE[k+1]

The loop in the first step of the algorithm runs k from i+1 to n to find the first k that satisfies this condition.

Also note that initially all space is given to the last, nth, stack by setting BASE[n] = TOP[n] = L0 and BASE[n+1]=LInfty. So unless all "higher" stacks have been filled, we will find such a k.

Your second question (Why choose the smallest such k?) is more easily answered: The algorithm on Page 247 is just one way of repacking and a simple one at that. As Knuth mentions in the paragraph just above the text of the algorithm:

Several ways to do the repacking suggest themselves; ... We will start by giving the simplest of the methods, and will then consider some of the alternatives.

Later, Knuth describes a repacking approach that takes into account the earlier repacking, making the process somewhat adaptive.