Compiler Explorer

Source code

import std;
import std.outbuffer;

/**
 * Slotted Pages architecture:
 *
 *  - Header keeps tracks of # of used slots, offset of the last used slot
 *  - Slot array maps sequential slots to positions of those tuples in the page
 *  - Growth:
 *     - Slot array: Linear order (grows from start -> end of page)
 *     - Tuples: Reverse order (grows from end -> start of page)
 *
 * Slotted page format:
 *  ---------------------------------------------------------
 *  | HEADER | ... FREE SPACE ... | ... INSERTED TUPLES ... |
 *  ---------------------------------------------------------
 *                                ^
 *                                free space pointer
 */

enum PAGE_SIZE = 4096;
enum HEADER_SIZE = (uint.sizeof) * 6;
enum TUPLE_SLOT_SIZE = (uint.sizeof) * 2;

struct TupleSlot
{
    uint offset;
    uint size;
}

struct Tuple
{
    uint size;
    ubyte[] data;
}

struct PageHeader
{
    uint logStorageNumber = 0;
    uint pageId = 0;
    uint prevPageId = 0;
    uint nextPageId = 0;
    uint freeSpacePointer = PAGE_SIZE;
    uint tupleCount = 0;
    TupleSlot[] slots;
}

struct SlottedPage
{
    PageHeader header;
    Tuple[] tuples;
    ubyte[PAGE_SIZE] buffer;
    
    void insertTuple(Tuple tuple)
    {
        tuples ~= tuple;
        header.slots ~= TupleSlot(header.freeSpacePointer, cast(uint) tuple.sizeof);
        header.tupleCount++;
        header.freeSpacePointer -= tuple.sizeof;
    }

void serialize(OutBuffer buf)
    {
        with (header)
        {
            buf.write(pageId);
            buf.write(logStorageNumber);
            buf.write(prevPageId);
            buf.write(nextPageId);
            buf.write(freeSpacePointer);
            buf.write(tupleCount);
        }

foreach (TupleSlot slot; header.slots)
        {
            buf.write(slot.offset);
            buf.write(slot.size);
        }

buf.fill0(header.freeSpacePointer);

foreach (Tuple tuple; tuples)
        {
            buf.write(tuple.size);
            buf.write(tuple.data);
        }
    }
}

void main()
{
    OutBuffer buffer = new OutBuffer();
	buffer.reserve(4096);

auto page = new SlottedPage(PageHeader());
	foreach (i; 0 .. 10)
	{
		OutBuffer buf = new OutBuffer();
		buf.write(i);
		page.insertTuple(Tuple(cast(uint) buf.data.length, buf.data));
	}

page.serialize(buffer);
    // Writes 8206
    writeln("Buffer size is: ", buffer.data.length);
}