Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Free spans: first-fit allocation and adjacent coalescing

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A free-span list stores the unallocated intervals of one fixed address range. The first-fit policy scans spans in increasing start-address order and takes the first interval long enough for a request. A partial fit advances that free span's start; an exact fit removes the span. The allocated map records the size associated with each returned start address, so release does not trust a caller-supplied length. On release, the interval returns to the free list, the list is sorted, and adjacent intervals are joined. Coalescing matters: two released neighbors can satisfy one larger request only when the allocator recognizes that their union is contiguous. This is an address-management model, not an operating-system allocator; it does not move live allocations or return memory to a host process.

Operational case

A 64-unit maintenance buffer first reserves 13 units for a pump record and 19 for a valve record. Releasing both creates two adjacent intervals; coalescing turns them into one span from zero through 31. A later 24-unit service record starts at zero, leaving a free tail from 24 through 63. Total free units are 40. If the two earlier records remained separate, neither isolated interval could fit the 24-unit request despite their combined capacity. Conversely, enough total free units do not guarantee success when live allocations divide them into small nonadjacent holes. An unknown start address is rejected rather than freeing somebody else's span.

Working Python program

python
class FirstFitSpanPool:
    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.free_spans = [(0, capacity)]
        self.allocated = {}

    def allocate(self, size):
        if size < 1:
            raise ValueError("size must be positive")
        for index, (start, length) in enumerate(self.free_spans):
            if length < size:
                continue
            if length == size:
                self.free_spans.pop(index)
            else:
                self.free_spans[index] = (start + size, length - size)
            self.allocated[start] = size
            return start
        raise MemoryError("no contiguous free span fits")

    def release(self, start):
        size = self.allocated.pop(start)
        self.free_spans.append((start, size))
        self.free_spans.sort()
        merged = []
        for span_start, length in self.free_spans:
            if merged and merged[-1][0] + merged[-1][1] == span_start:
                previous_start, previous_length = merged[-1]
                merged[-1] = (previous_start, previous_length + length)
            else:
                merged.append((span_start, length))
        self.free_spans = merged

    def free_units(self):
        return sum(length for _, length in self.free_spans)


pool = FirstFitSpanPool(64)
pump = pool.allocate(13)
valve = pool.allocate(19)
pool.release(pump)
pool.release(valve)
service = pool.allocate(24)
print("service-start=", service, " free=", pool.free_units(),
      " spans=", pool.free_spans, sep="")

Output

Output
service-start=0 free=40 spans=[(24, 40)]

Time, space, and tradeoff

Let F be the number of free spans. First-fit allocation scans at most F spans and may shift a Python list when one is removed, so it costs O(F) time. Release appends, sorts, and merges F plus one spans, costing O(F log F) time and O(F) temporary list space. The allocated map gives expected O(1) ownership lookup, with O(L) records for L live allocations. Capacity accounting uses O(F) time by summing lengths. A balanced interval tree or size-indexed bins could change search costs, but each also adds metadata and different fragmentation tradeoffs. First fit does not compact occupied intervals or guarantee that a suitable contiguous block exists.

Common Mistakes

  • Do not equate total free space with the largest available contiguous span.
  • Do not merge intervals across a live allocation.
  • Do not accept a release size supplied by a caller when the allocator has the ownership record.
  • Do not claim constant-time release for this sorting implementation.

Connected lessons

Compare ownership and reuse with Checkpoint arenas: reclaim a region by lifetime, Buddy blocks: split powers of two and reunite partners, Slab slots: reuse fixed-size pages with generation checks, then run the storage audit and contract quiz.

data structures
array-data-structure-guide
Storage details