tiny.sql.page
Defined in tiny.sql.
API (30)
Actions
Public operations.
Identity.entriesIdentity.initIdentity.keyBytesIdentity.loadIdentity.setEntriesIdentity.setKeyBytesIdentity.setStateIdentity.setValueBytesIdentity.stateIdentity.valueBytesRange.nextcellBytes: Returns the page bytes a cell with a key and value of these lengths takes.kind
Types and contracts
Public types and contracts.
Values and defaults
Public values and defaults.
Identity.state_sizecell_bytes_max: A put of a cell no larger than this, counting its key, value and slot bytes, succeeds on any page whose cells are no larger: a split that balances bytes leaves both halves within one page.child_size: Branch cells hold their child page number in this many bytes.header_sizemeta_chain_page_entriesoverflow_capacitysize
Source
Source: lib/sql/src/page.zig:4
zig
const std = @import("std");const simd = @import("simd");const lattice = @import("lattice.zig");const trace = @import("trace.zig");const Bytes = simd.ScalableTag(u8);pub const size: usize = 4096;pub const header_size: usize = 32;pub const Error = error{ FreeListFull, GenerationOverflow, InvalidPage, InvalidPageId, InvalidRange, KeyNotFound, KeyTooLarge, PageFull, ValueTooLarge,};pub const Entry = struct { key: []const u8, value: []const u8,};pub const BranchEntry = struct { lower: []const u8, child: u32,};pub const Kind = enum { leaf, branch, meta, overflow, identity,};pub fn kind(bytes: *const [size]u8) Error!Kind { if (!std.mem.eql(u8, bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage; if (bytes[version_offset] != format_version) return error.InvalidPage; return switch (bytes[kind_offset]) { leaf_kind => .leaf, branch_kind => .branch, meta_kind => .meta, overflow_kind => .overflow, identity_kind => .identity, else => error.InvalidPage, };}const magic = [_]u8{ 't', 's', 'q', 'l' };const format_version: u8 = 1;const leaf_kind: u8 = 1;const branch_kind: u8 = 2;const meta_kind: u8 = 3;const overflow_kind: u8 = 4;const identity_kind: u8 = 5;const identity_entries_offset: usize = header_size;const identity_key_bytes_offset: usize = header_size + 8;const identity_value_bytes_offset: usize = header_size + 16;const identity_state_offset: usize = header_size + 24;const slot_size: usize = 8;/// Branch cells hold their child page number in this many bytes.pub const child_size: usize = 4;/// A put of a cell no larger than this, counting its key, value and slot/// bytes, succeeds on any page whose cells are no larger: a split that/// balances bytes leaves both halves within one page.pub const cell_bytes_max: usize = (size - header_size) / 2;const magic_offset: usize = 0;const version_offset: usize = 4;const kind_offset: usize = 5;const flags_offset: usize = 6;const id_offset: usize = 8;const generation_offset: usize = 16;const lower_offset: usize = 24;const upper_offset: usize = 26;const cells_offset: usize = 28;const reserved_offset: usize = 30;const meta_highest_offset: usize = 24;const meta_free_count_offset: usize = 28;const meta_reserved_offset: usize = 30;const meta_entry_size: usize = 4;const meta_chained_flag: u16 = 1;const meta_chain_offset: usize = 32;const meta_chained_entries_offset: usize = meta_chain_offset + meta_entry_size;pub const meta_chain_page_entries: usize = (size - meta_chained_entries_offset) / meta_entry_size;const overflow_next_offset: usize = 24;const overflow_used_offset: usize = 28;const overflow_reserved_offset: usize = 30;pub const overflow_capacity: usize = size - header_size;const Slot = struct { offset: u16, key_len: u16, value_len: u16, flags: u16 = 0,};pub const Leaf = struct { bytes: *[size]u8, pub fn init(bytes: *[size]u8, page_id: u64) Leaf { var leaf = Leaf{ .bytes = bytes }; @memset(leaf.bytes, 0); @memcpy(leaf.bytes[magic_offset..][0..magic.len], magic[0..]); leaf.bytes[version_offset] = format_version; leaf.bytes[kind_offset] = leaf_kind; leaf.writeU16(flags_offset, 0); leaf.writeU64(id_offset, page_id); leaf.writeU64(generation_offset, 0); leaf.writeU16(lower_offset, header_size); leaf.writeU16(upper_offset, size); leaf.writeU16(cells_offset, 0); leaf.writeU16(reserved_offset, 0); return leaf; } pub fn load(bytes: *[size]u8) Error!Leaf { const leaf = Leaf{ .bytes = bytes }; try leaf.validate(); return leaf; } /// Wraps a leaf image that `load` validated, without walking its cells /// again. The image must be unchanged since that `load`. A reader that /// returns to one leaf once per cell validates it once through `load` and /// resumes through this. pub fn fromValidated(bytes: *[size]u8) Leaf { std.debug.assert(bytes[kind_offset] == leaf_kind); return .{ .bytes = bytes }; } pub fn id(self: *const Leaf) u64 { return self.readU64(id_offset); } pub fn generation(self: *const Leaf) u64 { return self.readU64(generation_offset); } pub fn cellCount(self: *const Leaf) usize { return self.readU16(cells_offset); } pub fn firstKey(self: *const Leaf) ?[]const u8 { if (self.cellCount() == 0) return null; return self.keyAt(0); } pub fn freeBytes(self: *const Leaf) usize { const lower_bound = self.lower(); const upper_bound = self.upper(); if (upper_bound < lower_bound) return 0; return upper_bound - lower_bound; } pub fn usedBytes(self: *const Leaf) usize { return size - self.freeBytes(); } pub fn get(self: *const Leaf, key: []const u8) ?[]const u8 { const phase = trace.scope("page.leaf.get"); defer phase.end(); const index = self.lowerBound(key); if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), key)) return self.valueAt(index); return null; } pub fn put(self: *Leaf, key: []const u8, value: []const u8) Error!void { const phase = trace.scope("page.leaf.put"); defer phase.end(); try checkLengths(key, value); const next_generation = try self.nextGeneration(); const existing_index = self.lowerBound(key); if (existing_index == self.cellCount() or !std.mem.eql(u8, self.keyAt(existing_index), key)) { try self.cells().insert(existing_index, key, value); self.writeU64(generation_offset, next_generation); trace.progress("page.leaf.put.insert.complete"); return; } const slot = self.slotAt(existing_index); if (value.len == slot.value_len) { const value_offset: usize = slot.offset + slot.key_len; @memcpy(self.bytes[value_offset..][0..value.len], value); self.writeU64(generation_offset, next_generation); trace.progress("page.leaf.put.inplace.complete"); return; } var scratch: [size]u8 = undefined; var rebuilt = Leaf.init(&scratch, self.id()); rebuilt.writeU64(generation_offset, next_generation); var inserted = false; var index: usize = 0; while (index < self.cellCount()) : (index += 1) { const entry = self.entryAt(index); switch (simd.order(Bytes, entry.key, key)) { .lt => try rebuilt.appendEntry(entry.key, entry.value), .eq => { if (!inserted) { try rebuilt.appendEntry(key, value); inserted = true; } }, .gt => { if (!inserted) { try rebuilt.appendEntry(key, value); inserted = true; } try rebuilt.appendEntry(entry.key, entry.value); }, } } if (!inserted) try rebuilt.appendEntry(key, value); self.bytes.* = scratch; trace.progress("page.leaf.put.complete"); } pub fn delete(self: *Leaf, key: []const u8) Error!void { const phase = trace.scope("page.leaf.delete"); defer phase.end(); const next_generation = try self.nextGeneration(); const index = self.lowerBound(key); if (index == self.cellCount() or !std.mem.eql(u8, self.keyAt(index), key)) { return error.KeyNotFound; } self.cells().remove(index); self.writeU64(generation_offset, next_generation); trace.progress("page.leaf.delete.complete"); } pub fn range(self: *const Leaf, start: ?[]const u8, end: ?[]const u8) Error!Range { if (start) |lower_key| { if (end) |upper_key| { if (simd.order(Bytes, lower_key, upper_key) == .gt) return error.InvalidRange; } } return .{ .leaf = self, .end = end, .index = if (start) |key| self.lowerBound(key) else 0, }; } pub fn splitPut(self: *const Leaf, left: *Leaf, right: *Leaf, key: []const u8, value: []const u8) Error![]const u8 { const phase = trace.scope("page.leaf.split_put"); defer phase.end(); try checkLengths(key, value); const next_generation = try self.nextGeneration(); left.writeU64(generation_offset, next_generation); right.writeU64(generation_offset, next_generation); var replacement = false; var index: usize = 0; while (index < self.cellCount()) : (index += 1) { if (std.mem.eql(u8, self.keyAt(index), key)) replacement = true; } const total = self.cellCount() + if (replacement) @as(usize, 0) else 1; const split_index = try splitIndexFor(self, key, value.len, total); var ordinal: usize = 0; var inserted = false; index = 0; while (index < self.cellCount()) : (index += 1) { const entry = self.entryAt(index); switch (simd.order(Bytes, entry.key, key)) { .lt => { try appendSplitEntry(left, right, split_index, &ordinal, entry.key, entry.value); }, .eq => { if (!inserted) { try appendSplitEntry(left, right, split_index, &ordinal, key, value); inserted = true; } }, .gt => { if (!inserted) { try appendSplitEntry(left, right, split_index, &ordinal, key, value); inserted = true; } try appendSplitEntry(left, right, split_index, &ordinal, entry.key, entry.value); }, } } if (!inserted) try appendSplitEntry(left, right, split_index, &ordinal, key, value); return right.firstKey() orelse error.InvalidPage; } pub fn copyTo(self: *const Leaf, target: *Leaf) Error!void { target.writeU64(generation_offset, self.generation()); var index: usize = 0; while (index < self.cellCount()) : (index += 1) { const entry = self.entryAt(index); try target.appendEntry(entry.key, entry.value); } } fn validate(self: *const Leaf) Error!void { if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage; if (self.bytes[version_offset] != format_version) return error.InvalidPage; if (self.bytes[kind_offset] != leaf_kind) return error.InvalidPage; if (self.readU16(flags_offset) != 0) return error.InvalidPage; if (self.readU16(reserved_offset) != 0) return error.InvalidPage; const count = self.cellCount(); if (count > (size - header_size) / slot_size) return error.InvalidPage; const lower_bound = self.lower(); const upper_bound = self.upper(); if (lower_bound != header_size + count * slot_size) return error.InvalidPage; if (upper_bound < lower_bound or upper_bound > size) return error.InvalidPage; var index: usize = 0; while (index < count) : (index += 1) { const slot = self.slotAt(index); const offset: usize = slot.offset; const payload_end = offset + @as(usize, slot.key_len) + @as(usize, slot.value_len); if (offset < upper_bound or payload_end > size) return error.InvalidPage; if (slot.flags != 0) return error.InvalidPage; if (index > 0 and simd.order(Bytes, self.keyAt(index - 1), self.keyAt(index)) != .lt) return error.InvalidPage; } } fn appendEntry(self: *Leaf, key: []const u8, value: []const u8) Error!void { try self.cells().insert(self.cellCount(), key, value); } fn cells(self: *Leaf) Cells { return .{ .bytes = self.bytes }; } fn lowerBound(self: *const Leaf, key: []const u8) usize { var low: usize = 0; var high = self.cellCount(); while (low < high) { const mid = low + (high - low) / 2; switch (simd.order(Bytes, self.keyAt(mid), key)) { .lt => low = mid + 1, .eq, .gt => high = mid, } } return low; } fn nextGeneration(self: *const Leaf) Error!u64 { const current = self.generation(); if (current == std.math.maxInt(u64)) return error.GenerationOverflow; return current + 1; } pub fn lastKey(self: *const Leaf) ?[]const u8 { const count = self.cellCount(); if (count == 0) return null; return self.keyAt(count - 1); } fn entryAt(self: *const Leaf, index: usize) Entry { return .{ .key = self.keyAt(index), .value = self.valueAt(index) }; } fn keyAt(self: *const Leaf, index: usize) []const u8 { const slot = self.slotAt(index); const start: usize = slot.offset; return self.bytes[start..][0..slot.key_len]; } fn valueAt(self: *const Leaf, index: usize) []const u8 { const slot = self.slotAt(index); const start: usize = slot.offset + slot.key_len; return self.bytes[start..][0..slot.value_len]; } fn slotAt(self: *const Leaf, index: usize) Slot { const offset = header_size + index * slot_size; return .{ .offset = self.readU16(offset), .key_len = self.readU16(offset + 2), .value_len = self.readU16(offset + 4), .flags = self.readU16(offset + 6), }; } fn lower(self: *const Leaf) usize { return self.readU16(lower_offset); } fn upper(self: *const Leaf) usize { return self.readU16(upper_offset); } fn readU16(self: *const Leaf, offset: usize) u16 { return std.mem.readInt(u16, self.bytes[offset..][0..2], .big); } fn readU64(self: *const Leaf, offset: usize) u64 { return std.mem.readInt(u64, self.bytes[offset..][0..8], .big); } fn writeU16(self: *Leaf, offset: usize, value: u16) void { std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big); } fn writeU64(self: *Leaf, offset: usize, value: u64) void { std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big); }};pub const Branch = struct { bytes: *[size]u8, pub fn init(bytes: *[size]u8, page_id: u64) Branch { var branch = Branch{ .bytes = bytes }; @memset(branch.bytes, 0); @memcpy(branch.bytes[magic_offset..][0..magic.len], magic[0..]); branch.bytes[version_offset] = format_version; branch.bytes[kind_offset] = branch_kind; branch.writeU16(flags_offset, 0); branch.writeU64(id_offset, page_id); branch.writeU64(generation_offset, 0); branch.writeU16(lower_offset, header_size); branch.writeU16(upper_offset, size); branch.writeU16(cells_offset, 0); branch.writeU16(reserved_offset, 0); return branch; } pub fn load(bytes: *[size]u8) Error!Branch { const branch = Branch{ .bytes = bytes }; try branch.validate(); return branch; } /// Wraps a branch image that `load` validated, without walking its cells /// again. The image must be unchanged since that `load`. pub fn fromValidated(bytes: *[size]u8) Branch { std.debug.assert(bytes[kind_offset] == branch_kind); return .{ .bytes = bytes }; } pub fn id(self: *const Branch) u64 { return self.readU64(id_offset); } pub fn generation(self: *const Branch) u64 { return self.readU64(generation_offset); } pub fn cellCount(self: *const Branch) usize { return self.readU16(cells_offset); } pub fn childAt(self: *const Branch, index: usize) u32 { return self.childPayloadAt(index); } pub fn lowerAt(self: *const Branch, index: usize) []const u8 { return self.keyAt(index); } pub fn firstLower(self: *const Branch) ?[]const u8 { if (self.cellCount() == 0) return null; return self.keyAt(0); } pub fn childIndexFor(self: *const Branch, key: []const u8) usize { const index = self.lowerBound(key); if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), key)) return index; if (index == 0) return 0; return index - 1; } pub fn childFor(self: *const Branch, key: []const u8) u32 { return self.childAt(self.childIndexFor(key)); } pub fn put(self: *Branch, lower_key: []const u8, child: u32) Error!void { if (child == 0) return error.InvalidPage; const child_bytes = childBytes(child); try checkLengths(lower_key, child_bytes[0..]); const next_generation = try self.nextGeneration(); const index = self.lowerBound(lower_key); if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), lower_key)) { const slot = self.slotAt(index); const child_offset: usize = slot.offset + slot.key_len; self.bytes[child_offset..][0..child_bytes.len].* = child_bytes; } else { try self.cells().insert(index, lower_key, child_bytes[0..]); } self.writeU64(generation_offset, next_generation); } pub fn splitPut(self: *const Branch, left: *Branch, right: *Branch, lower_key: []const u8, child: u32) Error![]const u8 { if (child == 0) return error.InvalidPage; const child_bytes = childBytes(child); try checkLengths(lower_key, child_bytes[0..]); const next_generation = try self.nextGeneration(); left.writeU64(generation_offset, next_generation); right.writeU64(generation_offset, next_generation); var replacement = false; var index: usize = 0; while (index < self.cellCount()) : (index += 1) { if (std.mem.eql(u8, self.keyAt(index), lower_key)) replacement = true; } const total = self.cellCount() + if (replacement) @as(usize, 0) else 1; const split_index = try splitIndexFor(self, lower_key, child_bytes.len, total); var ordinal: usize = 0; var inserted = false; index = 0; while (index < self.cellCount()) : (index += 1) { const entry = self.entryAt(index); switch (simd.order(Bytes, entry.lower, lower_key)) { .lt => try appendSplitBranchEntry(left, right, split_index, &ordinal, entry.lower, entry.child), .eq => { if (!inserted) { try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child); inserted = true; } }, .gt => { if (!inserted) { try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child); inserted = true; } try appendSplitBranchEntry(left, right, split_index, &ordinal, entry.lower, entry.child); }, } } if (!inserted) try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child); return right.firstLower() orelse error.InvalidPage; } pub fn replace(self: *Branch, index: usize, lower_key: []const u8, child: u32) Error!void { if (index >= self.cellCount()) return error.InvalidPage; if (child == 0) return error.InvalidPage; const child_bytes = childBytes(child); try checkLengths(lower_key, child_bytes[0..]); const next_generation = try self.nextGeneration(); var scratch: [size]u8 = undefined; var rebuilt = Branch.init(&scratch, self.id()); rebuilt.writeU64(generation_offset, next_generation); var cursor: usize = 0; while (cursor < self.cellCount()) : (cursor += 1) { if (cursor == index) { try rebuilt.appendEntry(lower_key, child); } else { const entry = self.entryAt(cursor); try rebuilt.appendEntry(entry.lower, entry.child); } } self.bytes.* = scratch; } pub fn remove(self: *Branch, index: usize) Error!void { if (index >= self.cellCount()) return error.InvalidPage; const next_generation = try self.nextGeneration(); self.cells().remove(index); self.writeU64(generation_offset, next_generation); } pub fn copyTo(self: *const Branch, target: *Branch) Error!void { target.writeU64(generation_offset, self.generation()); var index: usize = 0; while (index < self.cellCount()) : (index += 1) { const entry = self.entryAt(index); try target.appendEntry(entry.lower, entry.child); } } fn validate(self: *const Branch) Error!void { if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage; if (self.bytes[version_offset] != format_version) return error.InvalidPage; if (self.bytes[kind_offset] != branch_kind) return error.InvalidPage; if (self.readU16(flags_offset) != 0) return error.InvalidPage; if (self.readU16(reserved_offset) != 0) return error.InvalidPage; const count = self.cellCount(); if (count > (size - header_size) / slot_size) return error.InvalidPage; const lower_bound = self.lower(); const upper_bound = self.upper(); if (lower_bound != header_size + count * slot_size) return error.InvalidPage; if (upper_bound < lower_bound or upper_bound > size) return error.InvalidPage; if (count == 0) return error.InvalidPage; var index: usize = 0; while (index < count) : (index += 1) { const slot = self.slotAt(index); const offset: usize = slot.offset; const payload_end = offset + @as(usize, slot.key_len) + @as(usize, slot.value_len); if (offset < upper_bound or payload_end > size) return error.InvalidPage; if (slot.flags != 0) return error.InvalidPage; if (slot.value_len != 4) return error.InvalidPage; if (self.childPayloadAt(index) == 0) return error.InvalidPage; if (index > 0 and simd.order(Bytes, self.keyAt(index - 1), self.keyAt(index)) != .lt) return error.InvalidPage; } } fn appendEntry(self: *Branch, lower_key: []const u8, child: u32) Error!void { const child_bytes = childBytes(child); try self.cells().insert(self.cellCount(), lower_key, child_bytes[0..]); } fn cells(self: *Branch) Cells { return .{ .bytes = self.bytes }; } fn entryAt(self: *const Branch, index: usize) BranchEntry { return .{ .lower = self.keyAt(index), .child = self.childPayloadAt(index) }; } fn lowerBound(self: *const Branch, key: []const u8) usize { var low: usize = 0; var high = self.cellCount(); while (low < high) { const mid = low + (high - low) / 2; switch (simd.order(Bytes, self.keyAt(mid), key)) { .lt => low = mid + 1, .eq, .gt => high = mid, } } return low; } fn nextGeneration(self: *const Branch) Error!u64 { const current = self.generation(); if (current == std.math.maxInt(u64)) return error.GenerationOverflow; return current + 1; } fn keyAt(self: *const Branch, index: usize) []const u8 { const slot = self.slotAt(index); const start: usize = slot.offset; return self.bytes[start..][0..slot.key_len]; } fn childPayloadAt(self: *const Branch, index: usize) u32 { const slot = self.slotAt(index); const start: usize = slot.offset + slot.key_len; return std.mem.readInt(u32, self.bytes[start..][0..4], .big); } fn slotAt(self: *const Branch, index: usize) Slot { const offset = header_size + index * slot_size; return .{ .offset = self.readU16(offset), .key_len = self.readU16(offset + 2), .value_len = self.readU16(offset + 4), .flags = self.readU16(offset + 6), }; } fn lower(self: *const Branch) usize { return self.readU16(lower_offset); } fn upper(self: *const Branch) usize { return self.readU16(upper_offset); } fn readU16(self: *const Branch, offset: usize) u16 { return std.mem.readInt(u16, self.bytes[offset..][0..2], .big); } fn readU64(self: *const Branch, offset: usize) u64 { return std.mem.readInt(u64, self.bytes[offset..][0..8], .big); } fn writeU16(self: *Branch, offset: usize, value: u16) void { std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big); } fn writeU64(self: *Branch, offset: usize, value: u64) void { std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big); }};pub const Identity = struct { bytes: *[size]u8, pub const state_size = lattice.encoded_size; pub fn init(bytes: *[size]u8, page_id: u64) Identity { var identity = Identity{ .bytes = bytes }; @memset(identity.bytes, 0); @memcpy(identity.bytes[magic_offset..][0..magic.len], magic[0..]); identity.bytes[version_offset] = format_version; identity.bytes[kind_offset] = identity_kind; std.mem.writeInt(u16, identity.bytes[flags_offset..][0..2], 0, .big); std.mem.writeInt(u64, identity.bytes[id_offset..][0..8], page_id, .big); std.mem.writeInt(u64, identity.bytes[generation_offset..][0..8], 0, .big); return identity; } pub fn load(bytes: *[size]u8) Error!Identity { if (try kind(bytes) != .identity) return error.InvalidPage; return .{ .bytes = bytes }; } pub fn entries(self: *const Identity) u64 { return std.mem.readInt(u64, self.bytes[identity_entries_offset..][0..8], .big); } pub fn setEntries(self: *Identity, value: u64) void { std.mem.writeInt(u64, self.bytes[identity_entries_offset..][0..8], value, .big); } pub fn keyBytes(self: *const Identity) u64 { return std.mem.readInt(u64, self.bytes[identity_key_bytes_offset..][0..8], .big); } pub fn setKeyBytes(self: *Identity, value: u64) void { std.mem.writeInt(u64, self.bytes[identity_key_bytes_offset..][0..8], value, .big); } pub fn valueBytes(self: *const Identity) u64 { return std.mem.readInt(u64, self.bytes[identity_value_bytes_offset..][0..8], .big); } pub fn setValueBytes(self: *Identity, value: u64) void { std.mem.writeInt(u64, self.bytes[identity_value_bytes_offset..][0..8], value, .big); } pub fn state(self: *const Identity) lattice.State { return lattice.State.decode(self.bytes[identity_state_offset..][0..state_size]); } pub fn setState(self: *Identity, value: *const lattice.State) void { value.encode(self.bytes[identity_state_offset..][0..state_size]); }};pub const Meta = struct { bytes: *[size]u8, pub fn init(bytes: *[size]u8, page_id: u64, highest_page: u32) Meta { var meta = Meta{ .bytes = bytes }; @memset(meta.bytes, 0); @memcpy(meta.bytes[magic_offset..][0..magic.len], magic[0..]); meta.bytes[version_offset] = format_version; meta.bytes[kind_offset] = meta_kind; meta.writeU16(flags_offset, 0); meta.writeU64(id_offset, page_id); meta.writeU64(generation_offset, 0); meta.writeU32(meta_highest_offset, highest_page); meta.writeU16(meta_free_count_offset, 0); meta.writeU16(meta_reserved_offset, 0); return meta; } pub fn load(bytes: *[size]u8) Error!Meta { const meta = Meta{ .bytes = bytes }; try meta.validate(); return meta; } pub fn id(self: *const Meta) u64 { return self.readU64(id_offset); } pub fn generation(self: *const Meta) u64 { return self.readU64(generation_offset); } pub fn highestPage(self: *const Meta) u32 { return self.readU32(meta_highest_offset); } pub fn freeCount(self: *const Meta) usize { return self.readU16(meta_free_count_offset); } pub fn isChained(self: *const Meta) bool { return self.readU16(flags_offset) & meta_chained_flag != 0; } pub fn chainHead(self: *const Meta) u32 { if (!self.isChained()) return 0; return self.readU32(meta_chain_offset); } pub fn freeCapacity(self: *const Meta) usize { return (size - self.entriesOffset()) / meta_entry_size; } fn entriesOffset(self: *const Meta) usize { return if (self.isChained()) meta_chained_entries_offset else header_size; } pub fn allocate(self: *Meta) Error!u32 { const next_generation = try self.nextGeneration(); const count = self.freeCount(); if (count > 0) { const page_id = self.freeAt(count - 1); self.writeU16(meta_free_count_offset, @intCast(count - 1)); self.writeU64(generation_offset, next_generation); return page_id; } const highest = self.highestPage(); if (highest == std.math.maxInt(u32)) return error.InvalidPageId; const page_id = highest + 1; self.writeU32(meta_highest_offset, page_id); self.writeU64(generation_offset, next_generation); return page_id; } pub fn reserveThrough(self: *Meta, page_id: u32) Error!bool { if (page_id == 0) return error.InvalidPageId; if (page_id <= self.highestPage()) return false; const next_generation = try self.nextGeneration(); self.writeU32(meta_highest_offset, page_id); self.writeU64(generation_offset, next_generation); return true; } pub fn release(self: *Meta, page_id: u32) Error!void { if (page_id == 0 or @as(u64, page_id) == self.id() or page_id > self.highestPage()) return error.InvalidPageId; if (self.contains(page_id)) return error.InvalidPage; if (page_id == self.highestPage()) return self.releaseHighest(); const count = self.freeCount(); if (count >= self.freeCapacity()) return error.FreeListFull; const next_generation = try self.nextGeneration(); self.writeFree(count, page_id); self.writeU16(meta_free_count_offset, @intCast(count + 1)); self.writeU64(generation_offset, next_generation); } pub fn spillEntries(self: *Meta, buffer: []u32) Error!usize { const count = self.freeCount(); if (count == 0 or count > buffer.len) return error.InvalidPage; const next_generation = try self.nextGeneration(); var index: usize = 0; while (index < count) : (index += 1) buffer[index] = self.freeAt(index); self.writeU16(meta_free_count_offset, 0); self.writeU64(generation_offset, next_generation); return count; } pub fn adoptChain(self: *Meta, head: u32) Error!void { if (head == 0 or @as(u64, head) == self.id() or head > self.highestPage()) return error.InvalidPageId; if (self.freeCount() != 0) return error.InvalidPage; const next_generation = try self.nextGeneration(); self.writeU16(flags_offset, meta_chained_flag); self.writeU32(meta_chain_offset, head); self.writeU64(generation_offset, next_generation); } pub fn refillFromChain(self: *Meta, next_head: u32, entries: []const u32) Error!void { if (!self.isChained()) return error.InvalidPage; if (self.freeCount() != 0) return error.InvalidPage; if (next_head != 0 and (@as(u64, next_head) == self.id() or next_head > self.highestPage())) return error.InvalidPageId; for (entries) |entry| { if (entry == 0 or @as(u64, entry) == self.id() or entry > self.highestPage()) return error.InvalidPage; } const target_entries_offset: usize = if (next_head == 0) header_size else meta_chained_entries_offset; if (entries.len > (size - target_entries_offset) / meta_entry_size) return error.InvalidPage; const next_generation = try self.nextGeneration(); if (next_head == 0) { self.writeU16(flags_offset, 0); self.writeU32(meta_chain_offset, 0); } else { self.writeU32(meta_chain_offset, next_head); } for (entries, 0..) |entry, index| self.writeFree(index, entry); self.writeU16(meta_free_count_offset, @intCast(entries.len)); self.writeU64(generation_offset, next_generation); } pub fn freeAt(self: *const Meta, index: usize) u32 { return self.readU32(self.entriesOffset() + index * meta_entry_size); } fn validate(self: *const Meta) Error!void { if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage; if (self.bytes[version_offset] != format_version) return error.InvalidPage; if (self.bytes[kind_offset] != meta_kind) return error.InvalidPage; const flags = self.readU16(flags_offset); if (flags & ~meta_chained_flag != 0) return error.InvalidPage; if (self.readU16(meta_reserved_offset) != 0) return error.InvalidPage; if (flags & meta_chained_flag != 0) { const head = self.readU32(meta_chain_offset); if (head == 0 or @as(u64, head) == self.id() or head > self.highestPage()) return error.InvalidPage; } const count = self.freeCount(); if (count > self.freeCapacity()) return error.InvalidPage; if (self.highestPage() == 0) return error.InvalidPage; var index: usize = 0; while (index < count) : (index += 1) { const page_id = self.freeAt(index); if (page_id == 0 or @as(u64, page_id) == self.id() or page_id > self.highestPage()) return error.InvalidPage; var compare: usize = index + 1; while (compare < count) : (compare += 1) { if (page_id == self.freeAt(compare)) return error.InvalidPage; } } } fn contains(self: *const Meta, page_id: u32) bool { var index: usize = 0; while (index < self.freeCount()) : (index += 1) { if (self.freeAt(index) == page_id) return true; } return false; } fn releaseHighest(self: *Meta) Error!void { const next_generation = try self.nextGeneration(); var highest = self.highestPage() - 1; var count = self.freeCount(); while (count > 0) { const index = self.freeIndex(highest, count) orelse break; count -= 1; if (index != count) self.writeFree(index, self.freeAt(count)); highest -= 1; } self.writeU32(meta_highest_offset, highest); self.writeU16(meta_free_count_offset, @intCast(count)); self.writeU64(generation_offset, next_generation); } fn freeIndex(self: *const Meta, page_id: u32, count: usize) ?usize { var index: usize = 0; while (index < count) : (index += 1) { if (self.freeAt(index) == page_id) return index; } return null; } fn nextGeneration(self: *const Meta) Error!u64 { const current = self.generation(); if (current == std.math.maxInt(u64)) return error.GenerationOverflow; return current + 1; } fn writeFree(self: *Meta, index: usize, page_id: u32) void { self.writeU32(self.entriesOffset() + index * meta_entry_size, page_id); } fn readU16(self: *const Meta, offset: usize) u16 { return std.mem.readInt(u16, self.bytes[offset..][0..2], .big); } fn readU32(self: *const Meta, offset: usize) u32 { return std.mem.readInt(u32, self.bytes[offset..][0..4], .big); } fn readU64(self: *const Meta, offset: usize) u64 { return std.mem.readInt(u64, self.bytes[offset..][0..8], .big); } fn writeU16(self: *Meta, offset: usize, value: u16) void { std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big); } fn writeU32(self: *Meta, offset: usize, value: u32) void { std.mem.writeInt(u32, self.bytes[offset..][0..4], value, .big); } fn writeU64(self: *Meta, offset: usize, value: u64) void { std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big); }};pub const Overflow = struct { bytes: *[size]u8, pub fn init(bytes: *[size]u8, page_id: u64, next_page: u32, fragment: []const u8) Error!Overflow { if (fragment.len == 0 or fragment.len > overflow_capacity) return error.ValueTooLarge; if (next_page != 0 and @as(u64, next_page) == page_id) return error.InvalidPageId; var overflow = Overflow{ .bytes = bytes }; @memset(overflow.bytes, 0); @memcpy(overflow.bytes[magic_offset..][0..magic.len], magic[0..]); overflow.bytes[version_offset] = format_version; overflow.bytes[kind_offset] = overflow_kind; overflow.writeU16(flags_offset, 0); overflow.writeU64(id_offset, page_id); overflow.writeU64(generation_offset, 0); overflow.writeU32(overflow_next_offset, next_page); overflow.writeU16(overflow_used_offset, @intCast(fragment.len)); overflow.writeU16(overflow_reserved_offset, 0); @memcpy(overflow.bytes[header_size..][0..fragment.len], fragment); return overflow; } pub fn load(bytes: *[size]u8) Error!Overflow { const overflow = Overflow{ .bytes = bytes }; try overflow.validate(); return overflow; } pub fn id(self: *const Overflow) u64 { return self.readU64(id_offset); } pub fn next(self: *const Overflow) u32 { return self.readU32(overflow_next_offset); } pub fn used(self: *const Overflow) usize { return self.readU16(overflow_used_offset); } pub fn content(self: *const Overflow) []const u8 { return self.bytes[header_size..][0..self.used()]; } fn validate(self: *const Overflow) Error!void { if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage; if (self.bytes[version_offset] != format_version) return error.InvalidPage; if (self.bytes[kind_offset] != overflow_kind) return error.InvalidPage; if (self.readU16(flags_offset) != 0) return error.InvalidPage; if (self.readU16(overflow_reserved_offset) != 0) return error.InvalidPage; if (self.used() == 0 or self.used() > overflow_capacity) return error.InvalidPage; if (self.next() != 0 and @as(u64, self.next()) == self.id()) return error.InvalidPage; } fn readU16(self: *const Overflow, offset: usize) u16 { return std.mem.readInt(u16, self.bytes[offset..][0..2], .big); } fn readU32(self: *const Overflow, offset: usize) u32 { return std.mem.readInt(u32, self.bytes[offset..][0..4], .big); } fn readU64(self: *const Overflow, offset: usize) u64 { return std.mem.readInt(u64, self.bytes[offset..][0..8], .big); } fn writeU16(self: *Overflow, offset: usize, value: u16) void { std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big); } fn writeU32(self: *Overflow, offset: usize, value: u32) void { std.mem.writeInt(u32, self.bytes[offset..][0..4], value, .big); } fn writeU64(self: *Overflow, offset: usize, value: u64) void { std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big); }};pub const Range = struct { leaf: *const Leaf, end: ?[]const u8, index: usize, pub fn next(self: *Range) ?Entry { const phase = trace.scope("page.range.next"); defer phase.end(); if (self.index >= self.leaf.cellCount()) return null; const entry = self.leaf.entryAt(self.index); if (self.end) |upper| { if (simd.order(Bytes, entry.key, upper) != .lt) return null; } self.index += 1; return entry; }};fn checkLengths(key: []const u8, value: []const u8) Error!void { if (key.len > std.math.maxInt(u16)) return error.KeyTooLarge; if (value.len > std.math.maxInt(u16)) return error.ValueTooLarge; if (key.len + value.len > std.math.maxInt(u16)) return error.PageFull;}/// The cell layout leaf and branch pages share. Slots grow up from the/// header in key order, cells grow down from the end of the page, and the/// free bytes between them read as zero.const Cells = struct { bytes: *[size]u8, /// Writes a cell holding `key` and then `value` below the lowest cell /// and opens slot `index` for it, moving the slots from `index` up by /// one. A page without room for the cell and its slot stays unchanged. fn insert(self: Cells, index: usize, key: []const u8, value: []const u8) Error!void { try checkLengths(key, value); const count = self.read(cells_offset); const lower_bound = self.read(lower_offset); const upper_bound = self.read(upper_offset); std.debug.assert(index <= count); std.debug.assert(lower_bound == header_size + count * slot_size); if (upper_bound < lower_bound) return error.PageFull; const payload_len = key.len + value.len; if (payload_len + slot_size > upper_bound - lower_bound) return error.PageFull; const cell = upper_bound - payload_len; @memcpy(self.bytes[cell..][0..key.len], key); @memcpy(self.bytes[cell + key.len ..][0..value.len], value); const slot = header_size + index * slot_size; if (index < count) { const moved_slots = self.bytes[slot..lower_bound]; @memmove(self.bytes[slot + slot_size ..][0..moved_slots.len], moved_slots); } self.write(slot, cell); self.write(slot + 2, key.len); self.write(slot + 4, value.len); self.write(slot + 6, 0); self.write(cells_offset, count + 1); self.write(lower_offset, lower_bound + slot_size); self.write(upper_offset, cell); } /// Removes slot `index` and its cell. The cells below it move up by its /// length and the later slots move down by one, so the free bytes stay /// one zeroed gap. fn remove(self: Cells, index: usize) void { const count = self.read(cells_offset); const lower_bound = self.read(lower_offset); const upper_bound = self.read(upper_offset); std.debug.assert(index < count); std.debug.assert(lower_bound == header_size + count * slot_size); const slot = header_size + index * slot_size; const cell = self.read(slot); const cell_len = self.read(slot + 2) + self.read(slot + 4); std.debug.assert(cell >= upper_bound); std.debug.assert(cell + cell_len <= size); const moved_cells = self.bytes[upper_bound..cell]; @memmove(self.bytes[upper_bound + cell_len ..][0..moved_cells.len], moved_cells); @memset(self.bytes[upper_bound..][0..cell_len], 0); const last_slot = lower_bound - slot_size; @memmove(self.bytes[slot..last_slot], self.bytes[slot + slot_size .. lower_bound]); @memset(self.bytes[last_slot..lower_bound], 0); var moved: usize = header_size; while (moved < last_slot) : (moved += slot_size) { const offset = self.read(moved); if (offset < cell) self.write(moved, offset + cell_len); } self.write(cells_offset, count - 1); self.write(lower_offset, last_slot); self.write(upper_offset, upper_bound + cell_len); } fn read(self: Cells, offset: usize) usize { return std.mem.readInt(u16, self.bytes[offset..][0..2], .big); } fn write(self: Cells, offset: usize, value: usize) void { std.mem.writeInt(u16, self.bytes[offset..][0..2], @intCast(value), .big); }};fn appendSplitEntry(left: *Leaf, right: *Leaf, split_index: usize, ordinal: *usize, key: []const u8, value: []const u8) Error!void { if (ordinal.* < split_index) { try left.appendEntry(key, value); } else { try right.appendEntry(key, value); } ordinal.* += 1;}/// Returns the page bytes a cell with a key and value of these lengths takes.pub fn cellBytes(key_len: usize, value_len: usize) usize { return key_len + value_len + slot_size;}fn storedCellBytes(source: anytype, index: usize) usize { const slot = source.slotAt(index); return cellBytes(slot.key_len, slot.value_len);}/// Returns the split point that balances bytes between the halves of a leaf/// or branch merged with one put of `key`. A cell with that key is replaced.fn splitIndexFor(source: anytype, key: []const u8, value_len: usize, total: usize) Error!usize { const put_bytes = cellBytes(key.len, value_len); var search = SplitSearch{ .total = total, .total_bytes = mergedBytes(source, key, put_bytes), }; var inserted = false; var index: usize = 0; while (index < source.cellCount()) : (index += 1) { switch (simd.order(Bytes, source.keyAt(index), key)) { .lt => search.add(storedCellBytes(source, index)), .eq => { if (!inserted) { search.add(put_bytes); inserted = true; } }, .gt => { if (!inserted) { search.add(put_bytes); inserted = true; } search.add(storedCellBytes(source, index)); }, } } if (!inserted) search.add(put_bytes); if (search.best_index == 0) return error.PageFull; return search.best_index;}fn mergedBytes(source: anytype, key: []const u8, put_bytes: usize) usize { var bytes = put_bytes; var index: usize = 0; while (index < source.cellCount()) : (index += 1) { if (!std.mem.eql(u8, source.keyAt(index), key)) bytes += storedCellBytes(source, index); } return bytes;}/// Walks the cells of a split in key order and keeps the split point whose/// larger half is smallest among the points where both halves fit a page.const SplitSearch = struct { total: usize, total_bytes: usize, ordinal: usize = 0, left_bytes: usize = 0, best_index: usize = 0, best_score: usize = std.math.maxInt(usize), fn add(search: *SplitSearch, bytes: usize) void { search.ordinal += 1; search.left_bytes += bytes; if (search.ordinal >= search.total) return; const right_bytes = search.total_bytes - search.left_bytes; const capacity = size - header_size; if (search.left_bytes > capacity or right_bytes > capacity) return; const score = @max(search.left_bytes, right_bytes); if (score < search.best_score) { search.best_score = score; search.best_index = search.ordinal; } }};fn appendSplitBranchEntry(left: *Branch, right: *Branch, split_index: usize, ordinal: *usize, lower_key: []const u8, child: u32) Error!void { if (ordinal.* < split_index) { try left.appendEntry(lower_key, child); } else { try right.appendEntry(lower_key, child); } ordinal.* += 1;}fn childBytes(child: u32) [child_size]u8 { var bytes: [child_size]u8 = undefined; std.mem.writeInt(u32, &bytes, child, .big); return bytes;}test "leaf page initializes a stable header" { var bytes: [size]u8 = undefined; const leaf = Leaf.init(&bytes, 42); try std.testing.expectEqualStrings("tsql", bytes[0..4]); try std.testing.expectEqual(@as(u8, 1), bytes[version_offset]); try std.testing.expectEqual(@as(u8, leaf_kind), bytes[kind_offset]); try std.testing.expectEqual(@as(u64, 42), leaf.id()); try std.testing.expectEqual(@as(u64, 0), leaf.generation()); try std.testing.expectEqual(@as(usize, 0), leaf.cellCount()); try std.testing.expectEqual(@as(usize, size - header_size), leaf.freeBytes()); _ = try Leaf.load(&bytes);}test "leaf page stores byte keys in sorted order" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 7); try leaf.put("c", "three"); try leaf.put("a", "one"); try leaf.put("b", "two"); try std.testing.expectEqual(@as(usize, 3), leaf.cellCount()); try std.testing.expectEqualStrings("one", leaf.get("a").?); try std.testing.expectEqualStrings("two", leaf.get("b").?); try std.testing.expectEqualStrings("three", leaf.get("c").?); try std.testing.expect(leaf.get("d") == null); const loaded = try Leaf.load(&bytes); var range = try loaded.range(null, null); const first = range.next().?; const second = range.next().?; const third = range.next().?; try std.testing.expectEqualStrings("a", first.key); try std.testing.expectEqualStrings("b", second.key); try std.testing.expectEqualStrings("c", third.key); try std.testing.expect(range.next() == null);}test "leaf page replacement and deletion compact payload bytes" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 9); try leaf.put("k", "v1"); const used_after_insert = leaf.usedBytes(); try leaf.put("k", "replacement"); try std.testing.expectEqualStrings("replacement", leaf.get("k").?); try std.testing.expect(leaf.usedBytes() > used_after_insert); try std.testing.expectEqual(@as(u64, 2), leaf.generation()); try leaf.delete("k"); try std.testing.expectEqual(@as(usize, 0), leaf.cellCount()); try std.testing.expectEqual(@as(usize, size - header_size), leaf.freeBytes()); try std.testing.expect(leaf.get("k") == null); try std.testing.expectEqual(@as(u64, 3), leaf.generation());}test "leaf page same size replacement updates cell in place" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 10); try leaf.put("k", "v1"); const used_after_insert = leaf.usedBytes(); const slot_after_insert = leaf.slotAt(0); try leaf.put("k", "v2"); try std.testing.expectEqualStrings("v2", leaf.get("k").?); try std.testing.expectEqual(@as(u64, 2), leaf.generation()); try std.testing.expectEqual(used_after_insert, leaf.usedBytes()); try std.testing.expectEqual(slot_after_insert.offset, leaf.slotAt(0).offset); try std.testing.expectEqual(slot_after_insert.key_len, leaf.slotAt(0).key_len); try std.testing.expectEqual(slot_after_insert.value_len, leaf.slotAt(0).value_len); _ = try Leaf.load(&bytes);}test "leaf page range scans honor half open bounds" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 11); try leaf.put("a", "1"); try leaf.put("b", "2"); try leaf.put("c", "3"); try leaf.put("d", "4"); var range = try leaf.range("b", "d"); const first = range.next().?; const second = range.next().?; try std.testing.expectEqualStrings("b", first.key); try std.testing.expectEqualStrings("c", second.key); try std.testing.expect(range.next() == null); try std.testing.expectError(error.InvalidRange, leaf.range("d", "b"));}test "leaf page failed writes leave existing bytes intact" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 13); try leaf.put("a", "1"); const before = bytes; var large_value: [size]u8 = undefined; @memset(&large_value, 'x'); try std.testing.expectError(error.PageFull, leaf.put("b", &large_value)); try std.testing.expectEqualSlices(u8, before[0..], bytes[0..]); try std.testing.expectEqualStrings("1", leaf.get("a").?);}test "leaf page inserts between cells without moving them" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 14); try leaf.put("a", "one"); try leaf.put("c", "three"); const first = leaf.slotAt(0); const last = leaf.slotAt(1); try leaf.put("b", "two"); try std.testing.expectEqual(@as(usize, 3), leaf.cellCount()); try std.testing.expectEqual(first, leaf.slotAt(0)); try std.testing.expectEqual(last, leaf.slotAt(2)); try std.testing.expectEqualStrings("two", leaf.get("b").?); try std.testing.expectEqual(@as(u64, 3), leaf.generation()); try expectCompactCells(&bytes); _ = try Leaf.load(&bytes);}test "leaf page deletion closes the gap and zeroes the freed bytes" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 15); try leaf.put("a", "one"); try leaf.put("b", "two"); try leaf.put("c", "three"); try leaf.put("d", "four"); try leaf.delete("b"); try std.testing.expectError(error.KeyNotFound, leaf.delete("b")); var fresh_bytes: [size]u8 = undefined; var fresh = Leaf.init(&fresh_bytes, 15); try fresh.put("a", "one"); try fresh.put("c", "three"); try fresh.put("d", "four"); try std.testing.expectEqual(fresh.freeBytes(), leaf.freeBytes()); try std.testing.expect(leaf.get("b") == null); try std.testing.expectEqualStrings("one", leaf.get("a").?); try std.testing.expectEqualStrings("three", leaf.get("c").?); try std.testing.expectEqualStrings("four", leaf.get("d").?); try std.testing.expectEqual(@as(u64, 5), leaf.generation()); try expectCompactCells(&bytes); _ = try Leaf.load(&bytes);}test "leaf page insert into a full page leaves it unchanged" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 16); const value: [200]u8 = @splat('v'); var key = [_]u8{ 'k', 0 }; while (true) : (key[1] += 2) { leaf.put(&key, &value) catch |err| switch (err) { error.PageFull => break, else => return err, }; } const before = bytes; key[1] = 1; try std.testing.expectError(error.PageFull, leaf.put(&key, &value)); try std.testing.expectEqualSlices(u8, before[0..], bytes[0..]);}test "leaf page split balances uneven value sizes" { var bytes: [size]u8 = undefined; var leaf = Leaf.init(&bytes, 14); var large: [430]u8 = undefined; @memset(&large, 'x'); for (0..9) |index| { const key_bytes = [_]u8{ 'a', @intCast('0' + index / 10), @intCast('0' + index % 10) }; try leaf.put(key_bytes[0..], "s"); } for (0..8) |index| { const key_bytes = [_]u8{ 'z', @intCast('0' + index / 10), @intCast('0' + index % 10) }; try leaf.put(key_bytes[0..], large[0..]); } var left_bytes: [size]u8 = undefined; var right_bytes: [size]u8 = undefined; var left = Leaf.init(&left_bytes, 15); var right = Leaf.init(&right_bytes, 16); const new_key = [_]u8{ 'z', '0', '8' }; const separator = try leaf.splitPut(&left, &right, new_key[0..], large[0..]); _ = try Leaf.load(&left_bytes); _ = try Leaf.load(&right_bytes); try std.testing.expect(left.cellCount() > 0); try std.testing.expect(right.cellCount() > 0); try std.testing.expect(right.get(new_key[0..]) != null); try std.testing.expectEqualStrings(right.firstKey().?, separator);}test "branch page stores lower bounds and routes children" { var bytes: [size]u8 = undefined; var branch = Branch.init(&bytes, 21); try std.testing.expectEqual(Kind.branch, try kind(&bytes)); try std.testing.expectError(error.InvalidPage, Branch.load(&bytes)); try branch.put("m", 3); try branch.put(&.{}, 2); try branch.put("t", 4); const loaded = try Branch.load(&bytes); try std.testing.expectEqual(@as(u64, 21), loaded.id()); try std.testing.expectEqual(@as(u64, 3), loaded.generation()); try std.testing.expectEqual(@as(usize, 3), loaded.cellCount()); try std.testing.expectEqualStrings("", loaded.lowerAt(0)); try std.testing.expectEqualStrings("m", loaded.lowerAt(1)); try std.testing.expectEqualStrings("t", loaded.lowerAt(2)); try std.testing.expectEqual(@as(u32, 2), loaded.childFor("a")); try std.testing.expectEqual(@as(u32, 3), loaded.childFor("m")); try std.testing.expectEqual(@as(u32, 3), loaded.childFor("s")); try std.testing.expectEqual(@as(u32, 4), loaded.childFor("t")); try std.testing.expectEqual(@as(u32, 4), loaded.childFor("z"));}test "branch page replacement preserves lower bound order" { var bytes: [size]u8 = undefined; var branch = Branch.init(&bytes, 22); try branch.put(&.{}, 2); try branch.put("m", 3); try branch.put("t", 4); try branch.put("m", 5); const loaded = try Branch.load(&bytes); try std.testing.expectEqual(@as(u64, 4), loaded.generation()); try std.testing.expectEqual(@as(usize, 3), loaded.cellCount()); try std.testing.expectEqual(@as(u32, 2), loaded.childAt(0)); try std.testing.expectEqual(@as(u32, 5), loaded.childAt(1)); try std.testing.expectEqual(@as(u32, 4), loaded.childAt(2)); try std.testing.expectEqual(@as(u32, 5), loaded.childFor("q"));}test "branch page rejects zero child identifiers" { var bytes: [size]u8 = undefined; var branch = Branch.init(&bytes, 23); try std.testing.expectError(error.InvalidPage, branch.put(&.{}, 0)); try std.testing.expectError(error.InvalidPage, Branch.load(&bytes));}test "branch page split returns the first lower bound of the right page" { var bytes: [size]u8 = undefined; var branch = Branch.init(&bytes, 24); try branch.put(&.{}, 2); try branch.put("c", 3); try branch.put("f", 4); try branch.put("j", 5); try branch.put("n", 6); var left_bytes: [size]u8 = undefined; var right_bytes: [size]u8 = undefined; var left = Branch.init(&left_bytes, 25); var right = Branch.init(&right_bytes, 26); const separator = try branch.splitPut(&left, &right, "h", 7); try std.testing.expectEqualStrings("h", separator); const loaded_left = try Branch.load(&left_bytes); const loaded_right = try Branch.load(&right_bytes); try std.testing.expectEqualStrings("", loaded_left.lowerAt(0)); try std.testing.expectEqualStrings("h", loaded_right.lowerAt(0)); try std.testing.expectEqual(@as(u32, 4), loaded_left.childFor("g")); try std.testing.expectEqual(@as(u32, 7), loaded_right.childFor("h")); try std.testing.expectEqual(@as(u32, 6), loaded_right.childFor("z"));}test "branch page split balances uneven lower bound sizes" { var bytes: [size]u8 = undefined; var branch = Branch.init(&bytes, 28); try branch.put(&.{}, 2); for (0..12) |index| { const short = [_]u8{ 'a', @intCast('0' + index / 10), @intCast('0' + index % 10) }; try branch.put(short[0..], @intCast(3 + index)); } var long: [279]u8 = @splat('x'); long[0] = 'z'; for (0..13) |index| { long[1] = @intCast('0' + index / 10); long[2] = @intCast('0' + index % 10); try branch.put(long[0..], @intCast(20 + index)); } long[1] = '1'; long[2] = '3'; try std.testing.expectError(error.PageFull, branch.put(long[0..], 40)); var left_bytes: [size]u8 = undefined; var right_bytes: [size]u8 = undefined; var left = Branch.init(&left_bytes, 29); var right = Branch.init(&right_bytes, 30); const separator = try branch.splitPut(&left, &right, long[0..], 40); const loaded_left = try Branch.load(&left_bytes); const loaded_right = try Branch.load(&right_bytes); try std.testing.expect(loaded_left.cellCount() > 13); try std.testing.expectEqual(@as(usize, 27), loaded_left.cellCount() + loaded_right.cellCount()); try std.testing.expectEqualStrings(loaded_right.firstLower().?, separator); try std.testing.expectEqual(@as(u32, 40), loaded_right.childFor(long[0..]));}test "branch page replaces and removes child entries by index" { var bytes: [size]u8 = undefined; var branch = Branch.init(&bytes, 27); try branch.put(&.{}, 2); try branch.put("m", 3); try branch.put("t", 4); try branch.replace(1, "n", 5); var loaded = try Branch.load(&bytes); try std.testing.expectEqual(@as(usize, 3), loaded.cellCount()); try std.testing.expectEqualStrings("n", loaded.lowerAt(1)); try std.testing.expectEqual(@as(u32, 5), loaded.childFor("s")); try branch.remove(0); loaded = try Branch.load(&bytes); try std.testing.expectEqual(@as(usize, 2), loaded.cellCount()); try std.testing.expectEqualStrings("n", loaded.lowerAt(0)); try std.testing.expectEqual(@as(u32, 5), loaded.childFor("a"));}test "branch page inserts replaces children and removes cells in place" { var bytes: [size]u8 = undefined; var branch = Branch.init(&bytes, 28); try branch.put(&.{}, 2); try branch.put("t", 4); const last = branch.slotAt(1); try branch.put("m", 3); try std.testing.expectEqual(last, branch.slotAt(2)); try std.testing.expectEqual(@as(u32, 3), branch.childFor("p")); try branch.put("m", 5); try std.testing.expectEqual(@as(usize, 3), branch.cellCount()); try std.testing.expectEqual(@as(u32, 5), branch.childFor("p")); try branch.remove(1); try std.testing.expectEqual(@as(usize, 2), branch.cellCount()); try std.testing.expectEqual(@as(u32, 2), branch.childFor("p")); try std.testing.expectEqual(@as(u32, 4), branch.childFor("u")); try std.testing.expectEqual(@as(u64, 5), branch.generation()); try expectCompactCells(&bytes); _ = try Branch.load(&bytes);}/// Checks that the cells of a leaf or branch image fill the end of the/// page without gaps and that its free bytes read as zero.fn expectCompactCells(bytes: *[size]u8) !void { const cells = Cells{ .bytes = bytes }; const count = cells.read(cells_offset); const lower_bound = cells.read(lower_offset); const upper_bound = cells.read(upper_offset); var payload: usize = 0; var index: usize = 0; while (index < count) : (index += 1) { const slot = header_size + index * slot_size; payload += cells.read(slot + 2) + cells.read(slot + 4); } try std.testing.expectEqual(size - upper_bound, payload); try std.testing.expect(std.mem.allEqual(u8, bytes[lower_bound..upper_bound], 0));}test "pages copy entries into a new page identity" { var leaf_bytes: [size]u8 = undefined; var copied_leaf_bytes: [size]u8 = undefined; var leaf = Leaf.init(&leaf_bytes, 31); try leaf.put("a", "1"); try leaf.put("b", "2"); var copied_leaf = Leaf.init(&copied_leaf_bytes, 32); try leaf.copyTo(&copied_leaf); const loaded_leaf = try Leaf.load(&copied_leaf_bytes); try std.testing.expectEqual(@as(u64, 32), loaded_leaf.id()); try std.testing.expectEqualStrings("1", loaded_leaf.get("a").?); try std.testing.expectEqualStrings("2", loaded_leaf.get("b").?); var branch_bytes: [size]u8 = undefined; var copied_branch_bytes: [size]u8 = undefined; var branch = Branch.init(&branch_bytes, 33); try branch.put(&.{}, 2); try branch.put("m", 3); var copied_branch = Branch.init(&copied_branch_bytes, 34); try branch.copyTo(&copied_branch); const loaded_branch = try Branch.load(&copied_branch_bytes); try std.testing.expectEqual(@as(u64, 34), loaded_branch.id()); try std.testing.expectEqual(@as(u32, 2), loaded_branch.childFor("a")); try std.testing.expectEqual(@as(u32, 3), loaded_branch.childFor("z"));}test "meta page allocates appends and reuses released pages" { var bytes: [size]u8 = undefined; var meta = Meta.init(&bytes, 1, 4); try std.testing.expectEqual(Kind.meta, try kind(&bytes)); try std.testing.expectEqual(@as(u64, 1), meta.id()); try std.testing.expectEqual(@as(u32, 4), meta.highestPage()); try std.testing.expectEqual(@as(usize, 0), meta.freeCount()); try std.testing.expectEqual(@as(u32, 5), try meta.allocate()); try std.testing.expectEqual(@as(u32, 5), meta.highestPage()); try std.testing.expectEqual(@as(u64, 1), meta.generation()); try meta.release(3); try meta.release(4); try std.testing.expectEqual(@as(usize, 2), meta.freeCount()); try std.testing.expectEqual(@as(u32, 4), try meta.allocate()); try std.testing.expectEqual(@as(u32, 3), try meta.allocate()); try std.testing.expectEqual(@as(u32, 6), try meta.allocate()); const loaded = try Meta.load(&bytes); try std.testing.expectEqual(@as(u32, 6), loaded.highestPage()); try std.testing.expectEqual(@as(usize, 0), loaded.freeCount());}test "meta page truncates descending high-page releases" { var bytes: [size]u8 = undefined; var meta = Meta.init(&bytes, 1, 6000); var page_id: u32 = 6000; while (page_id >= 2000) : (page_id -= 1) try meta.release(page_id); try std.testing.expectEqual(@as(u32, 1999), meta.highestPage()); try std.testing.expectEqual(@as(usize, 0), meta.freeCount()); try std.testing.expectEqual(@as(u32, 2000), try meta.allocate());}test "meta reserves explicit root pages before allocation" { var bytes: [size]u8 = undefined; var meta = Meta.init(&bytes, 1, 2); try std.testing.expect(try meta.reserveThrough(4)); try std.testing.expectEqual(@as(u32, 4), meta.highestPage()); try std.testing.expect(!(try meta.reserveThrough(3))); try std.testing.expectEqual(@as(u32, 5), try meta.allocate());}test "meta page rejects invalid free-list entries" { var bytes: [size]u8 = undefined; var meta = Meta.init(&bytes, 1, 3); try std.testing.expectError(error.InvalidPageId, meta.release(0)); try std.testing.expectError(error.InvalidPageId, meta.release(1)); try std.testing.expectError(error.InvalidPageId, meta.release(4)); try meta.release(2); try std.testing.expectError(error.InvalidPage, meta.release(2)); _ = try Meta.load(&bytes);}test "meta page spills and refills a chained free list" { var bytes: [size]u8 = undefined; var meta = Meta.init(&bytes, 1, 100_000); const inline_capacity = meta.freeCapacity(); var page_id: u32 = 2; while (meta.freeCount() < inline_capacity) : (page_id += 2) try meta.release(page_id); try std.testing.expectError(error.FreeListFull, meta.release(page_id)); const chain_page = try meta.allocate(); var spilled: [meta_chain_page_entries + 1]u32 = undefined; const count = try meta.spillEntries(&spilled); try std.testing.expectEqual(inline_capacity - 1, count); try std.testing.expectEqual(@as(usize, 0), meta.freeCount()); try meta.adoptChain(chain_page); try std.testing.expect(meta.isChained()); try std.testing.expectEqual(chain_page, meta.chainHead()); try std.testing.expectEqual(meta_chain_page_entries, meta.freeCapacity()); _ = try Meta.load(&bytes); try meta.release(page_id); try std.testing.expectEqual(@as(usize, 1), meta.freeCount()); try std.testing.expectEqual(page_id, try meta.allocate()); try meta.refillFromChain(0, spilled[0..count]); try std.testing.expect(!meta.isChained()); try std.testing.expectEqual(@as(u32, 0), meta.chainHead()); try std.testing.expectEqual(count, meta.freeCount()); try std.testing.expectEqual(spilled[count - 1], try meta.allocate()); const loaded = try Meta.load(&bytes); try std.testing.expectEqual(count - 1, loaded.freeCount());}test "meta page rejects malformed chain transitions" { var bytes: [size]u8 = undefined; var meta = Meta.init(&bytes, 1, 50); var buffer: [4]u32 = undefined; try std.testing.expectError(error.InvalidPage, meta.spillEntries(&buffer)); try std.testing.expectError(error.InvalidPageId, meta.adoptChain(0)); try std.testing.expectError(error.InvalidPageId, meta.adoptChain(1)); try std.testing.expectError(error.InvalidPageId, meta.adoptChain(51)); try std.testing.expectError(error.InvalidPage, meta.refillFromChain(0, &.{2})); try meta.release(2); try std.testing.expectError(error.InvalidPage, meta.adoptChain(3)); _ = try meta.allocate(); try meta.adoptChain(3); try std.testing.expectError(error.InvalidPage, meta.refillFromChain(0, &.{0})); try std.testing.expectError(error.InvalidPage, meta.refillFromChain(0, &.{1})); try std.testing.expectError(error.InvalidPage, meta.refillFromChain(0, &.{51})); try std.testing.expectError(error.InvalidPageId, meta.refillFromChain(1, &.{4})); try std.testing.expectError(error.InvalidPageId, meta.refillFromChain(51, &.{4})); try meta.refillFromChain(5, &.{4}); try std.testing.expect(meta.isChained()); try std.testing.expectEqual(@as(u32, 5), meta.chainHead()); try std.testing.expectEqual(@as(usize, 1), meta.freeCount()); _ = try Meta.load(&bytes);}test "overflow page stores a linked content fragment" { var bytes: [size]u8 = undefined; const overflow = try Overflow.init(&bytes, 40, 41, "fragment"); try std.testing.expectEqual(Kind.overflow, try kind(&bytes)); try std.testing.expectEqual(@as(u64, 40), overflow.id()); try std.testing.expectEqual(@as(u32, 41), overflow.next()); try std.testing.expectEqualStrings("fragment", overflow.content()); const loaded = try Overflow.load(&bytes); try std.testing.expectEqual(@as(u32, 41), loaded.next()); try std.testing.expectEqualStrings("fragment", loaded.content());}test "overflow page rejects empty oversized and self-linked fragments" { var bytes: [size]u8 = undefined; var oversized: [overflow_capacity + 1]u8 = undefined; @memset(&oversized, 'x'); try std.testing.expectError(error.ValueTooLarge, Overflow.init(&bytes, 50, 0, &.{})); try std.testing.expectError(error.ValueTooLarge, Overflow.init(&bytes, 50, 0, &oversized)); try std.testing.expectError(error.InvalidPageId, Overflow.init(&bytes, 50, 50, "fragment"));}Source: lib/sql/src/root.zig:20
zig
pub const page = @import("page.zig");Complete caller list for page.kind
16 direct callers.
tiny.sql.page.Identity.load[function] atlib/sql/src/page.zig:702lib.sql.src.page.test_branch_page_stores_lower_bounds_and_routes_children[function] — test source atlib/sql/src/page.zig:1450in nearest public ownertiny.sql.pagelib.sql.src.page.test_meta_page_allocates_appends_and_reuses_released_pages[function] — test source atlib/sql/src/page.zig:1648in nearest public ownertiny.sql.pagelib.sql.src.page.test_overflow_page_stores_a_linked_content_fragment[function] — test source atlib/sql/src/page.zig:1769in nearest public ownertiny.sql.pagelib.sql.src.tree.RootBuild.appendNode[method] — private source atlib/sql/src/tree.zig:1804in nearest public ownertiny.sql.treelib.sql.src.tree.Tree.collectReleasedPages[method] — private source atlib/sql/src/tree.zig:1495in nearest public ownertiny.sql.treelib.sql.src.tree.Tree.compactRoot[method] — private source atlib/sql/src/tree.zig:1436in nearest public ownertiny.sql.treelib.sql.src.tree.copyRootPage[function] — private source atlib/sql/src/tree.zig:2202in nearest public ownertiny.sql.treelib.sql.src.tree.loadTreePage[function] — private source atlib/sql/src/tree.zig:1998in nearest public ownertiny.sql.treelib.sql.src.tree.summarizePage[function] — private source atlib/sql/src/tree.zig:2043in nearest public ownertiny.sql.treelib.sql.src.tree.test_tree_delete_compacts_recursive_branches_back_to_a_root_leaf[function] — test source atlib/sql/src/tree.zig:2914in nearest public ownertiny.sql.treelib.sql.src.tree.test_tree_delete_removes_empty_child_and_collapses_root_branch[function] — test source atlib/sql/src/tree.zig:2807in nearest public ownertiny.sql.treelib.sql.src.tree.test_tree_recursively_splits_branch_pages[function] — test source atlib/sql/src/tree.zig:2499in nearest public ownertiny.sql.treelib.sql.src.tree.test_tree_root_split_creates_a_branch_over_leaf_children[function] — test source atlib/sql/src/tree.zig:2288in nearest public ownertiny.sql.treelib.sql.src.tree.trustedTreePage[function] — private source atlib/sql/src/tree.zig:2008in nearest public ownertiny.sql.treelib.sql.src.tree.validTreePage[function] — private source atlib/sql/src/tree.zig:2018in nearest public ownertiny.sql.tree
Audit
| Definitions | 25 |
|---|---|
| Public names | 27 |
| Members | 15 |
| Version | 26.7.0 |
| Revision | daab053ee433 |