TAOCP 2.5 Exercise 17
When there are no available blocks, the list headed by `AVAIL` must be empty.
Section 2.5: Dynamic Storage Allocation
Exercise 17. [**] [10] What should the contents of LOC(AVAIL) and LOC(AVAIL)+1 be
in (9) when there are no available blocks present?
Verified: yes
Solve time: 1m30s
When there are no available blocks, the list headed by AVAIL must be empty. In the representation used by Algorithm C, an empty doubly linked circular list is obtained by making the header point to itself in both directions.
Therefore, in equation (9) the fields immediately following AVAIL should contain the location of the header itself:
$$ \boxed{\text{LOC(AVAIL)}=\text{AVAIL}, \qquad \text{LOC(AVAIL)}+1=\text{AVAIL}.} $$
With these values, traversals of the available-space list terminate correctly, since the first successor and predecessor of the header are the header itself. This is the standard representation of an empty circular list.