Slotted Page

Implement a slotted page that stores variable-length records in a fixed-size byte array.

Types

type SlottedPage struct {
    // internal fields
}

func NewSlottedPage(size int) *SlottedPage
func (p *SlottedPage) Insert(record []byte) (slot int, ok bool)
func (p *SlottedPage) Get(slot int) ([]byte, bool)
func (p *SlottedPage) Delete(slot int) bool
func (p *SlottedPage) Compact()
func (p *SlottedPage) FreeSpace() int

Layout

• Data grows from the front.
• Slot directory grows from the back.
• Each slot entry is 4 bytes: offset (uint16) + length (uint16).
• Encode both descriptor fields little-endian. Slot s starts at size - 4*(s+1). Free-space metadata lives outside the page bytes.

Rules

• If there is not enough space for record + a slot entry, Insert must return ok=false.
• Each successful insertion appends a new slot ID; deleted slots are not reused.
• Failed insertion leaves the page unchanged. It does not compact automatically.
• Delete marks the slot as empty (length=0). It does not remove the slot.
• Compact repacks live records to eliminate gaps and updates offsets.
• Visit live records in slot-ID order during compaction; retain all slot IDs, including deleted descriptors. Repeated compaction preserves the result.
• Get returns a copy of the record.
• Invalid/deleted slots return false from Get and Delete.

Notes

• FreeSpace returns the contiguous free space between data and slot directory.
• Inputs use page sizes from 8 through 256 and nonempty records. A zero length is reserved for deleted slots.