45.8 SegIdStack

SegIdStack is the container currently used for the FSS and delta-FSS. It is also used as a temporary container when checkpoint processing retrieves the delta-FSS from the SUT and later transfers those SegIds into the FSS. The type derives publicly from std::deque<SegId>, so the SUT can iterate, sort, search, insert, erase and swap its contents as well as use the two convenience operations shown below.

struct SegIdStack : public std::deque<SegId>
{
    void Push(SegId segid)
    {
        push_back(segid);
    }

    SegId Pop()
    {
        SegId segid = front();
        pop_front();
        return segid;
    }

};

Ordering behaviour

Despite its name, SegIdStack is not a LIFO stack. Push() appends a SegId at the back of the deque, whereas Pop() removes the SegId at the front. With no intervening reordering, these operations provide FIFO behaviour. Pop() assumes that the deque is not empty; its callers perform the empty check when required.

The FSS does not rely on FIFO ordering either. When a successfully published checkpoint makes the contents of the delta-FSS reusable, SUT::AddToFss() appends those SegIds and sorts the entire FSS in ascending SegId order. Since allocation removes the front entry, the lowest available SegId is normally allocated first. Startup reconstruction produces the same order by scanning segments from the lowest SegId to the highest.

This policy helps consecutive allocations remain in nearby regions of the file and favours reuse near the beginning, making it more likely that free space accumulates at the end where eventual file truncation is possible. Ordering is therefore a policy imposed by the SUT, not an invariant provided by SegIdStack itself.

Set membership

Conceptually, the FSS contains a set of SegIds that are safe to reuse, but SegIdStack does not enforce uniqueness or provide set semantics. Correct membership is maintained by the SUT's utilisation, reservation, checkpoint and recovery rules. Diagnostic FSS validation constructs and sorts temporary SegIdStack values so that the recorded free segments can be compared with the free segments derived independently from utilisation and reservation state.

Naming

Both SegIdStack and the expansion Free Segment Stack are historical names that can mislead readers into expecting LIFO behaviour. Other Proposals proposes renaming the FSS as the Free Segment Set and using neutral container terminology in the code, while documenting lowest-SegId-first allocation as a separate policy.