TAOCP 7.2.2.2 Exercise 134
Each BIMP table entry is maintained as a dynamically growing array whose capacity is always a power-of-two multiple of the initial size $4$.
Section 7.2.2.2: Satisfiability
Exercise 134. [22] The BIMP tables used by Algorithm L are sequential lists of dynamically varying size. One attractive way to implement them is to begin with every list having capacity 4 (say); then when a list needs to become larger, its capacity can be doubled.
Adapt the buddy system (Algorithm 2.5R) to this situation. (Lists that shrink when backtracking needn't free their memory, since they're likely to grow again later.)
Verified: yes
Solve time: 1m05s
Solution
Each BIMP table entry is maintained as a dynamically growing array whose capacity is always a power-of-two multiple of the initial size $4$. Thus every list $A$ has an associated capacity $\operatorname{cap}(A)=4\cdot 2^k$ for some $k\ge 0$, together with a current length $\operatorname{len}(A)\le \operatorname{cap}(A)$.
The buddy system from Algorithm 2.5R is used as the underlying allocator, but it is restricted to blocks whose sizes are exactly $4\cdot 2^k$. A free block of size $4\cdot 2^k$ is always regarded as a buddy pair of two blocks of size $4\cdot 2^{k-1}$ whenever $k>0$, exactly as in Algorithm 2.5R. No change is made to the splitting or coalescing rules of the buddy system itself.
When a list $A$ receives an insertion request that would increase its length beyond its current capacity, the algorithm proceeds as follows. Let $\operatorname{cap}(A)=4\cdot 2^k$ and suppose $\operatorname{len}(A)=\operatorname{cap}(A)$. A new block $B$ of size $4\cdot 2^{k+1}$ is requested from the buddy system. This request is satisfied by either taking an available free block of that size or by recursively splitting a larger free block down to size $4\cdot 2^{k+1}$ according to Algorithm 2.5R. The contents of $A$ are then copied into the first $\operatorname{cap}(A)$ positions of $B$, the element being inserted is placed in position $\operatorname{cap}(A)+1$, and the length is updated to $\operatorname{len}(A)\leftarrow \operatorname{len}(A)+1$. The old block previously used by $A$ is returned to the buddy system as a free block of size $4\cdot 2^k$, where it may immediately participate in coalescing with its buddy if that buddy is free.
The invariant maintained after every growth operation is that each active list occupies exactly one allocated block whose size is a power-of-two multiple of $4$, and that the list contents are stored contiguously in the first $\operatorname{len}(A)$ positions of that block.
When a list is shortened during backtracking, no memory is returned to the buddy system. Instead, only the value of $\operatorname{len}(A)$ is decreased. The block of size $\operatorname{cap}(A)$ remains allocated to $A$, since future extensions of $A$ reuse the same capacity without additional allocation cost. This ensures that backtracking operations affect only logical length fields and not physical memory structure.
Correctness follows from the fact that every extension operation replaces a full-capacity block by a strictly larger block that preserves all previously stored elements in the same order, so no data is lost. Every allocation is performed through the buddy system, so every block of size $4\cdot 2^k$ is always composed of aligned buddies, and splitting and coalescing preserve the structural invariant of Algorithm 2.5R. Since shrinking never frees memory, no active block is ever invalidated, and subsequent re-expansion of a list cannot require reinitialization of its previous contents.
This completes the adaptation of the buddy system to dynamically growing BIMP tables. ∎