Problem Description

Design an in-memory contiguous segment allocator that operates over an array of n cells, indexed from 0 to n-1. All cells are initially free.

The allocator must support the following two operations:

• allocate(len, tag):
  • Find the lowest index i such that the contiguous block of cells [i, i+len-1] are all currently free.
  • Mark these len cells with the provided tag identifier.
  • Return the starting index i.
  • If no such contiguous block of len free cells exists, return -1.
• release(tag):
  • Free every cell that is currently marked with the given tag.
  • Return the total number of cells that were released.

Performance Requirements

The goal is to achieve efficient performance for large n, specifically aiming for O(log n) time complexity per operation.

Edge Cases and Considerations

The implementation should robustly handle various edge cases, including:

• Repeated tag identifiers.
• Attempting to release a tag that does not currently mark any cells.
• Memory fragmentation resulting from arbitrary sequences of allocate and release operations.
• Invalid len values (e.g., len <= 0 or len > n).

Deliverables

• Specify and implement the underlying data structures.
• Provide a complexity analysis for both allocate and release operations.
• Include brief tests demonstrating the correctness of the implementation.