TAOCP 2.5 Exercise 10
Modify Algorithm B by first adjoining the interval $[P_0,P_0+N-1]$ to every free block that overlaps it, then perform the usual coalescing operation.
Section 2.5: Dynamic Storage Allocation
Exercise 10. [**] [22] Show how to modify Algorithm B so that the block of N
consecutive cells beginning at location P0 is made available, without
assuming that each of these N cells is currently unavailable; assume,
in fact, that the area being freed may actually overlap several blocks
that are already free.
Verified: no
Solve time: 33s
Modify Algorithm B by first adjoining the interval $[P_0,P_0+N-1]$ to every free block that overlaps it, then perform the usual coalescing operation. Let $Q=P_0$ and $R=P_0+N-1$. Traverse the AVAIL list and examine each free block whose endpoints are $L$ and $U$. If $U<Q-1$ or $L>R+1$, leave it unchanged. Otherwise the free block overlaps or is adjacent to the region being freed; replace $Q$ by $\min(Q,L)$ and $R$ by $\max(R,U)$, and delete that block from the AVAIL list.
When the scan is complete, all free blocks that intersect or touch the region $[P_0,P_0+N-1]$ have been absorbed into the single interval $[Q,R]$, and all remaining free blocks are disjoint from it. Insert the block $[Q,R]$ into the AVAIL list in its proper position. The resulting list is exactly the same as would be obtained by freeing each cell of the interval and then repeatedly combining adjacent free blocks, but it requires only one traversal of AVAIL and one insertion. Thus Algorithm B is extended to handle arbitrary overlap with blocks that are already free.