main.cpp

#include <cerrno>
#include <fcntl.h>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sys/stat.h>
#include <unistd.h>

#include <string>
#include <array>
#include <memory>
#include <iostream>

// ─────────────────────────────────────────────
//  Constants
// ─────────────────────────────────────────────

static constexpr uint32_t COLUMN_USERNAME_SIZE = 32;
static constexpr uint32_t COLUMN_EMAIL_SIZE    = 255;
static constexpr uint32_t PAGE_SIZE            = 4096;
static constexpr uint32_t TABLE_MAX_PAGES      = 400;
static constexpr uint32_t INVALID_PAGE_NUM     = UINT32_MAX;

// ─────────────────────────────────────────────
//  Enums
// ─────────────────────────────────────────────

enum class ExecuteResult      { SUCCESS, DUPLICATE_KEY };
enum class MetaCommandResult  { SUCCESS, UNRECOGNIZED_COMMAND };
enum class PrepareResult      { SUCCESS, NEGATIVE_ID, STRING_TOO_LONG,
                                SYNTAX_ERROR, UNRECOGNIZED_STATEMENT };
enum class StatementType      { INSERT, SELECT };
enum class NodeType           { INTERNAL, LEAF };

// ─────────────────────────────────────────────
//  Row
// ─────────────────────────────────────────────

struct Row {
    uint32_t id{};
    char username[COLUMN_USERNAME_SIZE + 1]{};
    char email[COLUMN_EMAIL_SIZE    + 1]{};
};

// ─────────────────────────────────────────────
//  Row layout (serialisation offsets)
// ─────────────────────────────────────────────

static constexpr uint32_t ID_SIZE       = sizeof(Row::id);
static constexpr uint32_t USERNAME_SIZE = sizeof(Row::username);
static constexpr uint32_t EMAIL_SIZE    = sizeof(Row::email);
static constexpr uint32_t ID_OFFSET       = 0;
static constexpr uint32_t USERNAME_OFFSET = ID_OFFSET + ID_SIZE;
static constexpr uint32_t EMAIL_OFFSET    = USERNAME_OFFSET + USERNAME_SIZE;
static constexpr uint32_t ROW_SIZE        = ID_SIZE + USERNAME_SIZE + EMAIL_SIZE;

// ─────────────────────────────────────────────
//  Node header layout
// ─────────────────────────────────────────────

static constexpr uint32_t NODE_TYPE_SIZE        = sizeof(uint8_t);
static constexpr uint32_t NODE_TYPE_OFFSET      = 0;
static constexpr uint32_t IS_ROOT_SIZE          = sizeof(uint8_t);
static constexpr uint32_t IS_ROOT_OFFSET        = NODE_TYPE_SIZE;
static constexpr uint32_t PARENT_POINTER_SIZE   = sizeof(uint32_t);
static constexpr uint32_t PARENT_POINTER_OFFSET = IS_ROOT_OFFSET + IS_ROOT_SIZE;
static constexpr uint32_t COMMON_NODE_HEADER_SIZE =
    NODE_TYPE_SIZE + IS_ROOT_SIZE + PARENT_POINTER_SIZE;

// Internal node header
static constexpr uint32_t INTERNAL_NODE_NUM_KEYS_SIZE     = sizeof(uint32_t);
static constexpr uint32_t INTERNAL_NODE_NUM_KEYS_OFFSET   = COMMON_NODE_HEADER_SIZE;
static constexpr uint32_t INTERNAL_NODE_RIGHT_CHILD_SIZE  = sizeof(uint32_t);
static constexpr uint32_t INTERNAL_NODE_RIGHT_CHILD_OFFSET =
    INTERNAL_NODE_NUM_KEYS_OFFSET + INTERNAL_NODE_NUM_KEYS_SIZE;
static constexpr uint32_t INTERNAL_NODE_HEADER_SIZE =
    COMMON_NODE_HEADER_SIZE + INTERNAL_NODE_NUM_KEYS_SIZE + INTERNAL_NODE_RIGHT_CHILD_SIZE;

// Internal node body
static constexpr uint32_t INTERNAL_NODE_KEY_SIZE   = sizeof(uint32_t);
static constexpr uint32_t INTERNAL_NODE_CHILD_SIZE = sizeof(uint32_t);
static constexpr uint32_t INTERNAL_NODE_CELL_SIZE  = INTERNAL_NODE_CHILD_SIZE + INTERNAL_NODE_KEY_SIZE;
static constexpr uint32_t INTERNAL_NODE_MAX_KEYS   = 3; // kept small for testing

// Leaf node header
static constexpr uint32_t LEAF_NODE_NUM_CELLS_SIZE   = sizeof(uint32_t);
static constexpr uint32_t LEAF_NODE_NUM_CELLS_OFFSET = COMMON_NODE_HEADER_SIZE;
static constexpr uint32_t LEAF_NODE_NEXT_LEAF_SIZE   = sizeof(uint32_t);
static constexpr uint32_t LEAF_NODE_NEXT_LEAF_OFFSET =
    LEAF_NODE_NUM_CELLS_OFFSET + LEAF_NODE_NUM_CELLS_SIZE;
static constexpr uint32_t LEAF_NODE_HEADER_SIZE =
    COMMON_NODE_HEADER_SIZE + LEAF_NODE_NUM_CELLS_SIZE + LEAF_NODE_NEXT_LEAF_SIZE;

// Leaf node body
static constexpr uint32_t LEAF_NODE_KEY_SIZE        = sizeof(uint32_t);
static constexpr uint32_t LEAF_NODE_KEY_OFFSET      = 0;
static constexpr uint32_t LEAF_NODE_VALUE_SIZE      = ROW_SIZE;
static constexpr uint32_t LEAF_NODE_VALUE_OFFSET    = LEAF_NODE_KEY_OFFSET + LEAF_NODE_KEY_SIZE;
static constexpr uint32_t LEAF_NODE_CELL_SIZE       = LEAF_NODE_KEY_SIZE + LEAF_NODE_VALUE_SIZE;
static constexpr uint32_t LEAF_NODE_SPACE_FOR_CELLS = PAGE_SIZE - LEAF_NODE_HEADER_SIZE;
static constexpr uint32_t LEAF_NODE_MAX_CELLS       = LEAF_NODE_SPACE_FOR_CELLS / LEAF_NODE_CELL_SIZE;
static constexpr uint32_t LEAF_NODE_RIGHT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) / 2;
static constexpr uint32_t LEAF_NODE_LEFT_SPLIT_COUNT  =
    (LEAF_NODE_MAX_CELLS + 1) - LEAF_NODE_RIGHT_SPLIT_COUNT;

// ─────────────────────────────────────────────
//  InputBuffer
// ─────────────────────────────────────────────

struct InputBuffer {
    std::string buffer;

    void read() {
        if (!std::getline(std::cin, buffer)) {
            if (buffer.empty()) {
                std::cerr << "Error reading input\n";
                std::exit(EXIT_FAILURE);
            }
        }
    }
};

// ─────────────────────────────────────────────
//  Pager
// ─────────────────────────────────────────────

struct Pager {
    int      file_descriptor{-1};
    uint32_t file_length{0};
    uint32_t num_pages{0};
    std::array<void*, TABLE_MAX_PAGES> pages{};

    Pager() { pages.fill(nullptr); }
    ~Pager() {
        for (auto* p : pages) free(p);
    }

    // Non-copyable
    Pager(const Pager&)            = delete;
    Pager& operator=(const Pager&) = delete;
};

// ─────────────────────────────────────────────
//  Table / Cursor (forward declarations)
// ─────────────────────────────────────────────

struct Table;

struct Cursor {
    Table*   table{nullptr};
    uint32_t page_num{0};
    uint32_t cell_num{0};
    bool     end_of_table{false};
};

struct Table {
    Pager*   pager{nullptr};
    uint32_t root_page_num{0};
};

// ─────────────────────────────────────────────
//  Statement
// ─────────────────────────────────────────────

struct Statement {
    StatementType type{StatementType::SELECT};
    Row           row_to_insert{};
};

// ─────────────────────────────────────────────
//  Node accessor helpers
// ─────────────────────────────────────────────

inline NodeType get_node_type(void* node) {
    return static_cast<NodeType>(*reinterpret_cast<uint8_t*>(
        static_cast<char*>(node) + NODE_TYPE_OFFSET));
}
inline void set_node_type(void* node, NodeType type) {
    *reinterpret_cast<uint8_t*>(static_cast<char*>(node) + NODE_TYPE_OFFSET) =
        static_cast<uint8_t>(type);
}
inline bool is_node_root(void* node) {
    return static_cast<bool>(*reinterpret_cast<uint8_t*>(
        static_cast<char*>(node) + IS_ROOT_OFFSET));
}
inline void set_node_root(void* node, bool is_root) {
    *reinterpret_cast<uint8_t*>(static_cast<char*>(node) + IS_ROOT_OFFSET) =
        static_cast<uint8_t>(is_root);
}
inline uint32_t* node_parent(void* node) {
    return reinterpret_cast<uint32_t*>(static_cast<char*>(node) + PARENT_POINTER_OFFSET);
}

// Internal node
inline uint32_t* internal_node_num_keys(void* node) {
    return reinterpret_cast<uint32_t*>(static_cast<char*>(node) + INTERNAL_NODE_NUM_KEYS_OFFSET);
}
inline uint32_t* internal_node_right_child(void* node) {
    return reinterpret_cast<uint32_t*>(static_cast<char*>(node) + INTERNAL_NODE_RIGHT_CHILD_OFFSET);
}
inline uint32_t* internal_node_cell(void* node, uint32_t cell_num) {
    return reinterpret_cast<uint32_t*>(
        static_cast<char*>(node) + INTERNAL_NODE_HEADER_SIZE + cell_num * INTERNAL_NODE_CELL_SIZE);
}
inline uint32_t* internal_node_key(void* node, uint32_t key_num) {
    return reinterpret_cast<uint32_t*>(
        reinterpret_cast<char*>(internal_node_cell(node, key_num)) + INTERNAL_NODE_CHILD_SIZE);
}

// Leaf node
inline uint32_t* leaf_node_num_cells(void* node) {
    return reinterpret_cast<uint32_t*>(static_cast<char*>(node) + LEAF_NODE_NUM_CELLS_OFFSET);
}
inline uint32_t* leaf_node_next_leaf(void* node) {
    return reinterpret_cast<uint32_t*>(static_cast<char*>(node) + LEAF_NODE_NEXT_LEAF_OFFSET);
}
inline void* leaf_node_cell(void* node, uint32_t cell_num) {
    return static_cast<char*>(node) + LEAF_NODE_HEADER_SIZE + cell_num * LEAF_NODE_CELL_SIZE;
}
inline uint32_t* leaf_node_key(void* node, uint32_t cell_num) {
    return reinterpret_cast<uint32_t*>(leaf_node_cell(node, cell_num));
}
inline void* leaf_node_value(void* node, uint32_t cell_num) {
    return static_cast<char*>(leaf_node_cell(node, cell_num)) + LEAF_NODE_KEY_SIZE;
}

// ─────────────────────────────────────────────
//  Pager / Table open & close
// ─────────────────────────────────────────────

void* get_page(Pager* pager, uint32_t page_num);  // forward declaration

uint32_t get_node_max_key(Pager* pager, void* node) {
    if (get_node_type(node) == NodeType::LEAF)
        return *leaf_node_key(node, *leaf_node_num_cells(node) - 1);
    void* right_child = get_page(pager, *internal_node_right_child(node));
    return get_node_max_key(pager, right_child);
}

void* get_page(Pager* pager, uint32_t page_num) {
    if (page_num > TABLE_MAX_PAGES) {
        std::fprintf(stderr, "Tried to fetch page number out of bounds. %u > %u\n",
                     page_num, TABLE_MAX_PAGES);
        std::exit(EXIT_FAILURE);
    }

    if (pager->pages[page_num] == nullptr) {
        void* page = std::malloc(PAGE_SIZE);
        uint32_t num_pages = pager->file_length / PAGE_SIZE;
        if (pager->file_length % PAGE_SIZE) ++num_pages;

        if (page_num <= num_pages) {
            lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);
            ssize_t bytes_read = read(pager->file_descriptor, page, PAGE_SIZE);
            if (bytes_read == -1) {
                std::fprintf(stderr, "Error reading file: %d\n", errno);
                std::exit(EXIT_FAILURE);
            }
        }

        pager->pages[page_num] = page;
        if (page_num >= pager->num_pages)
            pager->num_pages = page_num + 1;
    }

    return pager->pages[page_num];
}

uint32_t* internal_node_child(void* node, uint32_t child_num) {
    uint32_t num_keys = *internal_node_num_keys(node);
    if (child_num > num_keys) {
        std::fprintf(stderr, "Tried to access child_num %u > num_keys %u\n",
                     child_num, num_keys);
        std::exit(EXIT_FAILURE);
    }
    if (child_num == num_keys) {
        uint32_t* right_child = internal_node_right_child(node);
        if (*right_child == INVALID_PAGE_NUM) {
            std::fprintf(stderr, "Tried to access right child of node, but was invalid page\n");
            std::exit(EXIT_FAILURE);
        }
        return right_child;
    }
    uint32_t* child = internal_node_cell(node, child_num);
    if (*child == INVALID_PAGE_NUM) {
        std::fprintf(stderr, "Tried to access child %u of node, but was invalid page\n", child_num);
        std::exit(EXIT_FAILURE);
    }
    return child;
}

Pager* pager_open(const std::string& filename) {
    int fd = open(filename.c_str(),
                  O_RDWR | O_CREAT,
                  S_IWUSR | S_IRUSR);
    if (fd == -1) {
        std::fprintf(stderr, "Unable to open file\n");
        std::exit(EXIT_FAILURE);
    }

    off_t file_length = lseek(fd, 0, SEEK_END);

    Pager* pager         = new Pager();
    pager->file_descriptor = fd;
    pager->file_length     = static_cast<uint32_t>(file_length);
    pager->num_pages       = static_cast<uint32_t>(file_length / PAGE_SIZE);

    if (file_length % PAGE_SIZE != 0) {
        std::fprintf(stderr, "Db file is not a whole number of pages. Corrupt file.\n");
        std::exit(EXIT_FAILURE);
    }

    return pager;
}

void initialize_leaf_node(void* node) {
    set_node_type(node, NodeType::LEAF);
    set_node_root(node, false);
    *leaf_node_num_cells(node) = 0;
    *leaf_node_next_leaf(node) = 0;
}

void initialize_internal_node(void* node) {
    set_node_type(node, NodeType::INTERNAL);
    set_node_root(node, false);
    *internal_node_num_keys(node)    = 0;
    *internal_node_right_child(node) = INVALID_PAGE_NUM;
}

Table* db_open(const std::string& filename) {
    Pager* pager = pager_open(filename);

    Table* table        = new Table();
    table->pager        = pager;
    table->root_page_num = 0;

    if (pager->num_pages == 0) {
        void* root_node = get_page(pager, 0);
        initialize_leaf_node(root_node);
        set_node_root(root_node, true);
    }

    return table;
}

void pager_flush(Pager* pager, uint32_t page_num) {
    if (pager->pages[page_num] == nullptr) {
        std::fprintf(stderr, "Tried to flush null page\n");
        std::exit(EXIT_FAILURE);
    }

    off_t offset = lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);
    if (offset == -1) {
        std::fprintf(stderr, "Error seeking: %d\n", errno);
        std::exit(EXIT_FAILURE);
    }

    ssize_t bytes_written =
        write(pager->file_descriptor, pager->pages[page_num], PAGE_SIZE);
    if (bytes_written == -1) {
        std::fprintf(stderr, "Error writing: %d\n", errno);
        std::exit(EXIT_FAILURE);
    }
}

void db_close(Table* table) {
    Pager* pager = table->pager;

    for (uint32_t i = 0; i < pager->num_pages; i++) {
        if (pager->pages[i] == nullptr) continue;
        pager_flush(pager, i);
        std::free(pager->pages[i]);
        pager->pages[i] = nullptr;
    }

    if (close(pager->file_descriptor) == -1) {
        std::fprintf(stderr, "Error closing db file.\n");
        std::exit(EXIT_FAILURE);
    }

    delete pager;
    delete table;
}

// ─────────────────────────────────────────────
//  Row serialisation
// ─────────────────────────────────────────────

void serialize_row(const Row* source, void* destination) {
    std::memcpy(static_cast<char*>(destination) + ID_OFFSET,       &source->id,       ID_SIZE);
    std::memcpy(static_cast<char*>(destination) + USERNAME_OFFSET, &source->username, USERNAME_SIZE);
    std::memcpy(static_cast<char*>(destination) + EMAIL_OFFSET,    &source->email,    EMAIL_SIZE);
}

void deserialize_row(const void* source, Row* destination) {
    std::memcpy(&destination->id,       static_cast<const char*>(source) + ID_OFFSET,       ID_SIZE);
    std::memcpy(&destination->username, static_cast<const char*>(source) + USERNAME_OFFSET, USERNAME_SIZE);
    std::memcpy(&destination->email,    static_cast<const char*>(source) + EMAIL_OFFSET,    EMAIL_SIZE);
}

void print_row(const Row* row) {
    std::printf("(%u, %s, %s)\n", row->id, row->username, row->email);
}

// ─────────────────────────────────────────────
//  Cursor helpers
// ─────────────────────────────────────────────

void* cursor_value(Cursor* cursor) {
    void* page = get_page(cursor->table->pager, cursor->page_num);
    return leaf_node_value(page, cursor->cell_num);
}

void cursor_advance(Cursor* cursor) {
    void* node = get_page(cursor->table->pager, cursor->page_num);
    cursor->cell_num++;
    if (cursor->cell_num >= *leaf_node_num_cells(node)) {
        uint32_t next_page_num = *leaf_node_next_leaf(node);
        if (next_page_num == 0) {
            cursor->end_of_table = true;
        } else {
            cursor->page_num = next_page_num;
            cursor->cell_num = 0;
        }
    }
}

// ─────────────────────────────────────────────
//  Tree search
// ─────────────────────────────────────────────

Cursor* leaf_node_find(Table* table, uint32_t page_num, uint32_t key) {
    void*    node      = get_page(table->pager, page_num);
    uint32_t num_cells = *leaf_node_num_cells(node);

    Cursor* cursor       = new Cursor();
    cursor->table        = table;
    cursor->page_num     = page_num;
    cursor->end_of_table = false;

    uint32_t min_index        = 0;
    uint32_t one_past_max_index = num_cells;
    while (one_past_max_index != min_index) {
        uint32_t index        = (min_index + one_past_max_index) / 2;
        uint32_t key_at_index = *leaf_node_key(node, index);
        if (key == key_at_index) { cursor->cell_num = index; return cursor; }
        if (key < key_at_index)  one_past_max_index = index;
        else                     min_index = index + 1;
    }

    cursor->cell_num = min_index;
    return cursor;
}

uint32_t internal_node_find_child(void* node, uint32_t key) {
    uint32_t num_keys  = *internal_node_num_keys(node);
    uint32_t min_index = 0;
    uint32_t max_index = num_keys;

    while (min_index != max_index) {
        uint32_t index        = (min_index + max_index) / 2;
        uint32_t key_to_right = *internal_node_key(node, index);
        if (key_to_right >= key) max_index = index;
        else                     min_index = index + 1;
    }
    return min_index;
}

Cursor* internal_node_find(Table* table, uint32_t page_num, uint32_t key);

Cursor* table_find(Table* table, uint32_t key) {
    void* root_node = get_page(table->pager, table->root_page_num);
    if (get_node_type(root_node) == NodeType::LEAF)
        return leaf_node_find(table, table->root_page_num, key);
    return internal_node_find(table, table->root_page_num, key);
}

Cursor* internal_node_find(Table* table, uint32_t page_num, uint32_t key) {
    void*    node        = get_page(table->pager, page_num);
    uint32_t child_index = internal_node_find_child(node, key);
    uint32_t child_num   = *internal_node_child(node, child_index);
    void*    child       = get_page(table->pager, child_num);

    if (get_node_type(child) == NodeType::LEAF)
        return leaf_node_find(table, child_num, key);
    return internal_node_find(table, child_num, key);
}

Cursor* table_start(Table* table) {
    Cursor*  cursor    = table_find(table, 0);
    void*    node      = get_page(table->pager, cursor->page_num);
    uint32_t num_cells = *leaf_node_num_cells(node);
    cursor->end_of_table = (num_cells == 0);
    return cursor;
}

// ─────────────────────────────────────────────
//  Tree mutation
// ─────────────────────────────────────────────

void internal_node_split_and_insert(Table* table, uint32_t parent_page_num,
                                    uint32_t child_page_num); // forward decl

void create_new_root(Table* table, uint32_t right_child_page_num) {
    void*    root              = get_page(table->pager, table->root_page_num);
    void*    right_child       = get_page(table->pager, right_child_page_num);
    uint32_t left_child_page_num = table->pager->num_pages; // get_unused_page_num
    void*    left_child        = get_page(table->pager, left_child_page_num);

    if (get_node_type(root) == NodeType::INTERNAL) {
        initialize_internal_node(right_child);
        initialize_internal_node(left_child);
    }

    std::memcpy(left_child, root, PAGE_SIZE);
    set_node_root(left_child, false);

    if (get_node_type(left_child) == NodeType::INTERNAL) {
        for (int i = 0; i < static_cast<int>(*internal_node_num_keys(left_child)); i++) {
            void* child = get_page(table->pager, *internal_node_child(left_child, i));
            *node_parent(child) = left_child_page_num;
        }
        void* child = get_page(table->pager, *internal_node_right_child(left_child));
        *node_parent(child) = left_child_page_num;
    }

    initialize_internal_node(root);
    set_node_root(root, true);
    *internal_node_num_keys(root)    = 1;
    *internal_node_child(root, 0)    = left_child_page_num;
    uint32_t left_child_max_key      = get_node_max_key(table->pager, left_child);
    *internal_node_key(root, 0)      = left_child_max_key;
    *internal_node_right_child(root) = right_child_page_num;
    *node_parent(left_child)         = table->root_page_num;
    *node_parent(right_child)        = table->root_page_num;
}

void internal_node_insert(Table* table, uint32_t parent_page_num,
                          uint32_t child_page_num) {
    void*    parent        = get_page(table->pager, parent_page_num);
    void*    child         = get_page(table->pager, child_page_num);
    uint32_t child_max_key = get_node_max_key(table->pager, child);
    uint32_t index         = internal_node_find_child(parent, child_max_key);
    uint32_t original_num_keys = *internal_node_num_keys(parent);

    if (original_num_keys >= INTERNAL_NODE_MAX_KEYS) {
        internal_node_split_and_insert(table, parent_page_num, child_page_num);
        return;
    }

    uint32_t right_child_page_num = *internal_node_right_child(parent);
    if (right_child_page_num == INVALID_PAGE_NUM) {
        *internal_node_right_child(parent) = child_page_num;
        return;
    }

    void* right_child = get_page(table->pager, right_child_page_num);
    *internal_node_num_keys(parent) = original_num_keys + 1;

    if (child_max_key > get_node_max_key(table->pager, right_child)) {
        *internal_node_child(parent, original_num_keys) = right_child_page_num;
        *internal_node_key(parent, original_num_keys)   =
            get_node_max_key(table->pager, right_child);
        *internal_node_right_child(parent) = child_page_num;
    } else {
        for (uint32_t i = original_num_keys; i > index; i--) {
            std::memcpy(internal_node_cell(parent, i),
                        internal_node_cell(parent, i - 1),
                        INTERNAL_NODE_CELL_SIZE);
        }
        *internal_node_child(parent, index) = child_page_num;
        *internal_node_key(parent, index)   = child_max_key;
    }
}

void update_internal_node_key(void* node, uint32_t old_key, uint32_t new_key) {
    uint32_t old_child_index = internal_node_find_child(node, old_key);
    *internal_node_key(node, old_child_index) = new_key;
}

void internal_node_split_and_insert(Table* table, uint32_t parent_page_num,
                                    uint32_t child_page_num) {
    uint32_t old_page_num = parent_page_num;
    void*    old_node     = get_page(table->pager, parent_page_num);
    uint32_t old_max      = get_node_max_key(table->pager, old_node);

    void*    child        = get_page(table->pager, child_page_num);
    uint32_t child_max    = get_node_max_key(table->pager, child);

    uint32_t new_page_num = table->pager->num_pages; // get_unused_page_num
    bool splitting_root   = is_node_root(old_node);

    void* parent   = nullptr;
    void* new_node = nullptr;

    if (splitting_root) {
        create_new_root(table, new_page_num);
        parent      = get_page(table->pager, table->root_page_num);
        old_page_num = *internal_node_child(parent, 0);
        old_node    = get_page(table->pager, old_page_num);
    } else {
        parent   = get_page(table->pager, *node_parent(old_node));
        new_node = get_page(table->pager, new_page_num);
        initialize_internal_node(new_node);
    }

    uint32_t* old_num_keys   = internal_node_num_keys(old_node);
    uint32_t  cur_page_num   = *internal_node_right_child(old_node);
    void*     cur            = get_page(table->pager, cur_page_num);

    internal_node_insert(table, new_page_num, cur_page_num);
    *node_parent(cur) = new_page_num;
    *internal_node_right_child(old_node) = INVALID_PAGE_NUM;

    for (int i = static_cast<int>(INTERNAL_NODE_MAX_KEYS) - 1;
         i > static_cast<int>(INTERNAL_NODE_MAX_KEYS / 2); i--) {
        cur_page_num = *internal_node_child(old_node, static_cast<uint32_t>(i));
        cur          = get_page(table->pager, cur_page_num);

        internal_node_insert(table, new_page_num, cur_page_num);
        *node_parent(cur) = new_page_num;
        (*old_num_keys)--;
    }

    *internal_node_right_child(old_node) =
        *internal_node_child(old_node, *old_num_keys - 1);
    (*old_num_keys)--;

    uint32_t max_after_split      = get_node_max_key(table->pager, old_node);
    uint32_t destination_page_num =
        (child_max < max_after_split) ? old_page_num : new_page_num;

    internal_node_insert(table, destination_page_num, child_page_num);
    *node_parent(child) = destination_page_num;

    update_internal_node_key(parent, old_max,
                             get_node_max_key(table->pager, old_node));

    if (!splitting_root) {
        internal_node_insert(table, *node_parent(old_node), new_page_num);
        *node_parent(new_node) = *node_parent(old_node);
    }
}

void leaf_node_split_and_insert(Cursor* cursor, uint32_t key, Row* value) {
    void*    old_node    = get_page(cursor->table->pager, cursor->page_num);
    uint32_t old_max     = get_node_max_key(cursor->table->pager, old_node);
    uint32_t new_page_num = cursor->table->pager->num_pages;
    void*    new_node    = get_page(cursor->table->pager, new_page_num);

    initialize_leaf_node(new_node);
    *node_parent(new_node)          = *node_parent(old_node);
    *leaf_node_next_leaf(new_node)  = *leaf_node_next_leaf(old_node);
    *leaf_node_next_leaf(old_node)  = new_page_num;

    for (int32_t i = static_cast<int32_t>(LEAF_NODE_MAX_CELLS); i >= 0; i--) {
        void*    destination_node;
        if (static_cast<uint32_t>(i) >= LEAF_NODE_LEFT_SPLIT_COUNT)
            destination_node = new_node;
        else
            destination_node = old_node;

        uint32_t index_within_node = static_cast<uint32_t>(i) % LEAF_NODE_LEFT_SPLIT_COUNT;
        void*    destination       = leaf_node_cell(destination_node, index_within_node);

        if (static_cast<uint32_t>(i) == cursor->cell_num) {
            serialize_row(value, leaf_node_value(destination_node, index_within_node));
            *leaf_node_key(destination_node, index_within_node) = key;
        } else if (static_cast<uint32_t>(i) > cursor->cell_num) {
            std::memcpy(destination,
                        leaf_node_cell(old_node, static_cast<uint32_t>(i) - 1),
                        LEAF_NODE_CELL_SIZE);
        } else {
            std::memcpy(destination,
                        leaf_node_cell(old_node, static_cast<uint32_t>(i)),
                        LEAF_NODE_CELL_SIZE);
        }
    }

    *leaf_node_num_cells(old_node) = LEAF_NODE_LEFT_SPLIT_COUNT;
    *leaf_node_num_cells(new_node) = LEAF_NODE_RIGHT_SPLIT_COUNT;

    if (is_node_root(old_node)) {
        create_new_root(cursor->table, new_page_num);
    } else {
        uint32_t parent_page_num = *node_parent(old_node);
        uint32_t new_max         = get_node_max_key(cursor->table->pager, old_node);
        void*    parent          = get_page(cursor->table->pager, parent_page_num);

        update_internal_node_key(parent, old_max, new_max);
        internal_node_insert(cursor->table, parent_page_num, new_page_num);
    }
}

void leaf_node_insert(Cursor* cursor, uint32_t key, Row* value) {
    void*    node      = get_page(cursor->table->pager, cursor->page_num);
    uint32_t num_cells = *leaf_node_num_cells(node);

    if (num_cells >= LEAF_NODE_MAX_CELLS) {
        leaf_node_split_and_insert(cursor, key, value);
        return;
    }

    if (cursor->cell_num < num_cells) {
        for (uint32_t i = num_cells; i > cursor->cell_num; i--)
            std::memcpy(leaf_node_cell(node, i),
                        leaf_node_cell(node, i - 1),
                        LEAF_NODE_CELL_SIZE);
    }

    *leaf_node_num_cells(node) += 1;
    *leaf_node_key(node, cursor->cell_num) = key;
    serialize_row(value, leaf_node_value(node, cursor->cell_num));
}

// ─────────────────────────────────────────────
//  Debug helpers
// ─────────────────────────────────────────────

void print_constants() {
    std::printf("ROW_SIZE: %u\n",                 ROW_SIZE);
    std::printf("COMMON_NODE_HEADER_SIZE: %u\n",  COMMON_NODE_HEADER_SIZE);
    std::printf("LEAF_NODE_HEADER_SIZE: %u\n",    LEAF_NODE_HEADER_SIZE);
    std::printf("LEAF_NODE_CELL_SIZE: %u\n",      LEAF_NODE_CELL_SIZE);
    std::printf("LEAF_NODE_SPACE_FOR_CELLS: %u\n",LEAF_NODE_SPACE_FOR_CELLS);
    std::printf("LEAF_NODE_MAX_CELLS: %u\n",      LEAF_NODE_MAX_CELLS);
}

void indent(uint32_t level) {
    for (uint32_t i = 0; i < level; i++) std::printf("  ");
}

void print_tree(Pager* pager, uint32_t page_num, uint32_t indentation_level) {
    void*    node     = get_page(pager, page_num);
    uint32_t num_keys, child;

    switch (get_node_type(node)) {
        case NodeType::LEAF:
            num_keys = *leaf_node_num_cells(node);
            indent(indentation_level);
            std::printf("- leaf (size %u)\n", num_keys);
            for (uint32_t i = 0; i < num_keys; i++) {
                indent(indentation_level + 1);
                std::printf("- %u\n", *leaf_node_key(node, i));
            }
            break;
        case NodeType::INTERNAL:
            num_keys = *internal_node_num_keys(node);
            indent(indentation_level);
            std::printf("- internal (size %u)\n", num_keys);
            if (num_keys > 0) {
                for (uint32_t i = 0; i < num_keys; i++) {
                    child = *internal_node_child(node, i);
                    print_tree(pager, child, indentation_level + 1);
                    indent(indentation_level + 1);
                    std::printf("- key %u\n", *internal_node_key(node, i));
                }
                child = *internal_node_right_child(node);
                print_tree(pager, child, indentation_level + 1);
            }
            break;
    }
}

// ─────────────────────────────────────────────
//  Statement preparation & execution
// ─────────────────────────────────────────────

MetaCommandResult do_meta_command(InputBuffer& input_buffer, Table* table) {
    if (input_buffer.buffer == ".exit") {
        db_close(table);
        std::exit(EXIT_SUCCESS);
    } else if (input_buffer.buffer == ".btree") {
        std::printf("Tree:\n");
        print_tree(table->pager, 0, 0);
        return MetaCommandResult::SUCCESS;
    } else if (input_buffer.buffer == ".constants") {
        std::printf("Constants:\n");
        print_constants();
        return MetaCommandResult::SUCCESS;
    }
    return MetaCommandResult::UNRECOGNIZED_COMMAND;
}

PrepareResult prepare_insert(InputBuffer& input_buffer, Statement& statement) {
    statement.type = StatementType::INSERT;

    // Tokenise a mutable copy
    std::string buf = input_buffer.buffer;
    char* token = std::strtok(buf.data(), " "); // keyword "insert"
    char* id_string = std::strtok(nullptr, " ");
    char* username  = std::strtok(nullptr, " ");
    char* email     = std::strtok(nullptr, " ");

    if (!id_string || !username || !email)
        return PrepareResult::SYNTAX_ERROR;

    int id = std::atoi(id_string);
    if (id < 0)                                     return PrepareResult::NEGATIVE_ID;
    if (std::strlen(username) > COLUMN_USERNAME_SIZE) return PrepareResult::STRING_TOO_LONG;
    if (std::strlen(email)    > COLUMN_EMAIL_SIZE)    return PrepareResult::STRING_TOO_LONG;

    statement.row_to_insert.id = static_cast<uint32_t>(id);
    std::strcpy(statement.row_to_insert.username, username);
    std::strcpy(statement.row_to_insert.email,    email);

    return PrepareResult::SUCCESS;
}

PrepareResult prepare_statement(InputBuffer& input_buffer, Statement& statement) {
    if (input_buffer.buffer.substr(0, 6) == "insert")
        return prepare_insert(input_buffer, statement);
    if (input_buffer.buffer == "select") {
        statement.type = StatementType::SELECT;
        return PrepareResult::SUCCESS;
    }
    return PrepareResult::UNRECOGNIZED_STATEMENT;
}

ExecuteResult execute_insert(Statement& statement, Table* table) {
    Row*     row_to_insert = &statement.row_to_insert;
    uint32_t key_to_insert = row_to_insert->id;
    Cursor*  cursor        = table_find(table, key_to_insert);

    void*    node      = get_page(table->pager, cursor->page_num);
    uint32_t num_cells = *leaf_node_num_cells(node);

    if (cursor->cell_num < num_cells) {
        if (*leaf_node_key(node, cursor->cell_num) == key_to_insert) {
            delete cursor;
            return ExecuteResult::DUPLICATE_KEY;
        }
    }

    leaf_node_insert(cursor, row_to_insert->id, row_to_insert);
    delete cursor;
    return ExecuteResult::SUCCESS;
}

ExecuteResult execute_select(Statement& /*statement*/, Table* table) {
    Cursor* cursor = table_start(table);
    Row row;
    while (!cursor->end_of_table) {
        deserialize_row(cursor_value(cursor), &row);
        print_row(&row);
        cursor_advance(cursor);
    }
    delete cursor;
    return ExecuteResult::SUCCESS;
}

ExecuteResult execute_statement(Statement& statement, Table* table) {
    switch (statement.type) {
        case StatementType::INSERT: return execute_insert(statement, table);
        case StatementType::SELECT: return execute_select(statement, table);
    }
    return ExecuteResult::SUCCESS;
}

// ─────────────────────────────────────────────
//  main
// ─────────────────────────────────────────────

int main(int argc, char* argv[]) {
    if (argc < 2) {
        std::fprintf(stderr, "Must supply a database filename.\n");
        return EXIT_FAILURE;
    }

    Table* table = db_open(argv[1]);
    InputBuffer input_buffer;

    while (true) {
        std::printf("devdb > ");
        input_buffer.read();

        if (input_buffer.buffer.empty()) continue;

        if (input_buffer.buffer[0] == '.') {
            switch (do_meta_command(input_buffer, table)) {
                case MetaCommandResult::SUCCESS:
                    continue;
                case MetaCommandResult::UNRECOGNIZED_COMMAND:
                    std::printf("Unrecognized command '%s'\n",
                                input_buffer.buffer.c_str());
                    continue;
            }
        }

        Statement statement;
        switch (prepare_statement(input_buffer, statement)) {
            case PrepareResult::SUCCESS:              break;
            case PrepareResult::NEGATIVE_ID:
                std::printf("ID must be positive.\n"); continue;
            case PrepareResult::STRING_TOO_LONG:
                std::printf("String is too long.\n");  continue;
            case PrepareResult::SYNTAX_ERROR:
                std::printf("Syntax error. Could not parse statement.\n"); continue;
            case PrepareResult::UNRECOGNIZED_STATEMENT:
                std::printf("Unrecognized keyword at start of '%s'.\n",
                            input_buffer.buffer.c_str()); continue;
        }

        switch (execute_statement(statement, table)) {
            case ExecuteResult::SUCCESS:
                std::printf("Executed.\n"); break;
            case ExecuteResult::DUPLICATE_KEY:
                std::printf("Error: Duplicate key.\n"); break;
        }
    }
}