Contiguous Extent Allocator for a Storage Volume, Then O(log n)

A virtual-disk service carves a volume of blocks fixed-size blocks into extents (contiguous runs) for files. Implement:

class Volume:
    def __init__(self, blocks: int): ...       # blocks 0..blocks-1, all free
    def reserve(self, n: int) -> int: ...      # start of a free run of n blocks, or -1
    def release(self, start: int) -> None: ... # give back the extent that reserve returned

Rules:

• reserve(n) with n <= 0 raises ValueError.
• release on an address that is not the start of a live extent (never reserved, or already released) raises KeyError.
• Free space must coalesce: after a release, adjacent free runs merge, so a later large request can use them.

Part 1: Simple version

Keep the free runs in a Python list sorted by start and use first fit (lowest address that fits). Explain the cost of each operation.

Part 2: Logarithmic version

Make both reserve and release run in O(log F) time, where F is the number of free runs. Use best fit (smallest free run that fits; break ties by lowest address). Standard library only, so if you need an ordered structure, build a small one.

Example

v = Volume(100)
v.reserve(30) -> 0
v.reserve(20) -> 30
v.reserve(40) -> 50
v.reserve(20) -> -1        # only 10 blocks free
v.release(30)
v.reserve(15) -> 30
v.release(0); v.release(30)
v.reserve(50) -> 0         # 0..29, 30..44 and 45..49 coalesced

Policy difference:

v = Volume(100)
reserve 30, 10, 10, 50     -> 0, 30, 40, 50
release(0); release(40)    # free runs: [0,30) and [40,50)
v.reserve(10)              -> first fit: 0    best fit: 40

Constraints

• blocks up to 10^12 (so no per-block arrays), up to 10^6 operations.