Reputation:
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?
Upvotes: 1
Views: 277
Reputation: 2602
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, n
th, 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.
Upvotes: 2