tiny.sql.MetaPage

1pub const Meta = struct {2    bytes: *[size]u8,34    pub fn init(bytes: *[size]u8, page_id: u64, highest_page: u32) Meta {5        var meta = Meta{ .bytes = bytes };6        @memset(meta.bytes, 0);7        @memcpy(meta.bytes[magic_offset..][0..magic.len], magic[0..]);8        meta.bytes[version_offset] = format_version;9        meta.bytes[kind_offset] = meta_kind;10        meta.writeU16(flags_offset, 0);11        meta.writeU64(id_offset, page_id);12        meta.writeU64(generation_offset, 0);13        meta.writeU32(meta_highest_offset, highest_page);14        meta.writeU16(meta_free_count_offset, 0);15        meta.writeU16(meta_reserved_offset, 0);16        return meta;17    }1819    pub fn load(bytes: *[size]u8) Error!Meta {20        const meta = Meta{ .bytes = bytes };21        try meta.validate();22        return meta;23    }2425    pub fn id(self: *const Meta) u64 {26        return self.readU64(id_offset);27    }2829    pub fn generation(self: *const Meta) u64 {30        return self.readU64(generation_offset);31    }3233    pub fn highestPage(self: *const Meta) u32 {34        return self.readU32(meta_highest_offset);35    }3637    pub fn freeCount(self: *const Meta) usize {38        return self.readU16(meta_free_count_offset);39    }4041    pub fn isChained(self: *const Meta) bool {42        return self.readU16(flags_offset) & meta_chained_flag != 0;43    }4445    pub fn chainHead(self: *const Meta) u32 {46        if (!self.isChained()) return 0;47        return self.readU32(meta_chain_offset);48    }4950    pub fn freeCapacity(self: *const Meta) usize {51        return (size - self.entriesOffset()) / meta_entry_size;52    }5354    fn entriesOffset(self: *const Meta) usize {55        return if (self.isChained()) meta_chained_entries_offset else header_size;56    }5758    pub fn allocate(self: *Meta) Error!u32 {59        const next_generation = try self.nextGeneration();60        const count = self.freeCount();61        if (count > 0) {62            const page_id = self.freeAt(count - 1);63            self.writeU16(meta_free_count_offset, @intCast(count - 1));64            self.writeU64(generation_offset, next_generation);65            return page_id;66        }67        const highest = self.highestPage();68        if (highest == std.math.maxInt(u32)) return error.InvalidPageId;69        const page_id = highest + 1;70        self.writeU32(meta_highest_offset, page_id);71        self.writeU64(generation_offset, next_generation);72        return page_id;73    }7475    pub fn reserveThrough(self: *Meta, page_id: u32) Error!bool {76        if (page_id == 0) return error.InvalidPageId;77        if (page_id <= self.highestPage()) return false;78        const next_generation = try self.nextGeneration();79        self.writeU32(meta_highest_offset, page_id);80        self.writeU64(generation_offset, next_generation);81        return true;82    }8384    pub fn release(self: *Meta, page_id: u32) Error!void {85        if (page_id == 0 or @as(u64, page_id) == self.id() or page_id > self.highestPage()) return error.InvalidPageId;86        if (self.contains(page_id)) return error.InvalidPage;87        if (page_id == self.highestPage()) return self.releaseHighest();88        const count = self.freeCount();89        if (count >= self.freeCapacity()) return error.FreeListFull;90        const next_generation = try self.nextGeneration();91        self.writeFree(count, page_id);92        self.writeU16(meta_free_count_offset, @intCast(count + 1));93        self.writeU64(generation_offset, next_generation);94    }9596    pub fn spillEntries(self: *Meta, buffer: []u32) Error!usize {97        const count = self.freeCount();98        if (count == 0 or count > buffer.len) return error.InvalidPage;99        const next_generation = try self.nextGeneration();100        var index: usize = 0;101        while (index < count) : (index += 1) buffer[index] = self.freeAt(index);102        self.writeU16(meta_free_count_offset, 0);103        self.writeU64(generation_offset, next_generation);104        return count;105    }106107    pub fn adoptChain(self: *Meta, head: u32) Error!void {108        if (head == 0 or @as(u64, head) == self.id() or head > self.highestPage()) return error.InvalidPageId;109        if (self.freeCount() != 0) return error.InvalidPage;110        const next_generation = try self.nextGeneration();111        self.writeU16(flags_offset, meta_chained_flag);112        self.writeU32(meta_chain_offset, head);113        self.writeU64(generation_offset, next_generation);114    }115116    pub fn refillFromChain(self: *Meta, next_head: u32, entries: []const u32) Error!void {117        if (!self.isChained()) return error.InvalidPage;118        if (self.freeCount() != 0) return error.InvalidPage;119        if (next_head != 0 and (@as(u64, next_head) == self.id() or next_head > self.highestPage())) return error.InvalidPageId;120        for (entries) |entry| {121            if (entry == 0 or @as(u64, entry) == self.id() or entry > self.highestPage()) return error.InvalidPage;122        }123        const target_entries_offset: usize = if (next_head == 0) header_size else meta_chained_entries_offset;124        if (entries.len > (size - target_entries_offset) / meta_entry_size) return error.InvalidPage;125        const next_generation = try self.nextGeneration();126        if (next_head == 0) {127            self.writeU16(flags_offset, 0);128            self.writeU32(meta_chain_offset, 0);129        } else {130            self.writeU32(meta_chain_offset, next_head);131        }132        for (entries, 0..) |entry, index| self.writeFree(index, entry);133        self.writeU16(meta_free_count_offset, @intCast(entries.len));134        self.writeU64(generation_offset, next_generation);135    }136137    pub fn freeAt(self: *const Meta, index: usize) u32 {138        return self.readU32(self.entriesOffset() + index * meta_entry_size);139    }140141    fn validate(self: *const Meta) Error!void {142        if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage;143        if (self.bytes[version_offset] != format_version) return error.InvalidPage;144        if (self.bytes[kind_offset] != meta_kind) return error.InvalidPage;145        const flags = self.readU16(flags_offset);146        if (flags & ~meta_chained_flag != 0) return error.InvalidPage;147        if (self.readU16(meta_reserved_offset) != 0) return error.InvalidPage;148        if (flags & meta_chained_flag != 0) {149            const head = self.readU32(meta_chain_offset);150            if (head == 0 or @as(u64, head) == self.id() or head > self.highestPage()) return error.InvalidPage;151        }152        const count = self.freeCount();153        if (count > self.freeCapacity()) return error.InvalidPage;154        if (self.highestPage() == 0) return error.InvalidPage;155        var index: usize = 0;156        while (index < count) : (index += 1) {157            const page_id = self.freeAt(index);158            if (page_id == 0 or @as(u64, page_id) == self.id() or page_id > self.highestPage()) return error.InvalidPage;159            var compare: usize = index + 1;160            while (compare < count) : (compare += 1) {161                if (page_id == self.freeAt(compare)) return error.InvalidPage;162            }163        }164    }165166    fn contains(self: *const Meta, page_id: u32) bool {167        var index: usize = 0;168        while (index < self.freeCount()) : (index += 1) {169            if (self.freeAt(index) == page_id) return true;170        }171        return false;172    }173174    fn releaseHighest(self: *Meta) Error!void {175        const next_generation = try self.nextGeneration();176        var highest = self.highestPage() - 1;177        var count = self.freeCount();178        while (count > 0) {179            const index = self.freeIndex(highest, count) orelse break;180            count -= 1;181            if (index != count) self.writeFree(index, self.freeAt(count));182            highest -= 1;183        }184        self.writeU32(meta_highest_offset, highest);185        self.writeU16(meta_free_count_offset, @intCast(count));186        self.writeU64(generation_offset, next_generation);187    }188189    fn freeIndex(self: *const Meta, page_id: u32, count: usize) ?usize {190        var index: usize = 0;191        while (index < count) : (index += 1) {192            if (self.freeAt(index) == page_id) return index;193        }194        return null;195    }196197    fn nextGeneration(self: *const Meta) Error!u64 {198        const current = self.generation();199        if (current == std.math.maxInt(u64)) return error.GenerationOverflow;200        return current + 1;201    }202203    fn writeFree(self: *Meta, index: usize, page_id: u32) void {204        self.writeU32(self.entriesOffset() + index * meta_entry_size, page_id);205    }206207    fn readU16(self: *const Meta, offset: usize) u16 {208        return std.mem.readInt(u16, self.bytes[offset..][0..2], .big);209    }210211    fn readU32(self: *const Meta, offset: usize) u32 {212        return std.mem.readInt(u32, self.bytes[offset..][0..4], .big);213    }214215    fn readU64(self: *const Meta, offset: usize) u64 {216        return std.mem.readInt(u64, self.bytes[offset..][0..8], .big);217    }218219    fn writeU16(self: *Meta, offset: usize, value: u16) void {220        std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big);221    }222223    fn writeU32(self: *Meta, offset: usize, value: u32) void {224        std.mem.writeInt(u32, self.bytes[offset..][0..4], value, .big);225    }226227    fn writeU64(self: *Meta, offset: usize, value: u64) void {228        std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big);229    }230};

1pub const MetaPage = page.Meta;