tiny.sql.BranchPage

1pub const Branch = struct {2    bytes: *[size]u8,34    pub fn init(bytes: *[size]u8, page_id: u64) Branch {5        var branch = Branch{ .bytes = bytes };6        @memset(branch.bytes, 0);7        @memcpy(branch.bytes[magic_offset..][0..magic.len], magic[0..]);8        branch.bytes[version_offset] = format_version;9        branch.bytes[kind_offset] = branch_kind;10        branch.writeU16(flags_offset, 0);11        branch.writeU64(id_offset, page_id);12        branch.writeU64(generation_offset, 0);13        branch.writeU16(lower_offset, header_size);14        branch.writeU16(upper_offset, size);15        branch.writeU16(cells_offset, 0);16        branch.writeU16(reserved_offset, 0);17        return branch;18    }1920    pub fn load(bytes: *[size]u8) Error!Branch {21        const branch = Branch{ .bytes = bytes };22        try branch.validate();23        return branch;24    }2526    /// Wraps a branch image that `load` validated, without walking its cells27    /// again. The image must be unchanged since that `load`.28    pub fn fromValidated(bytes: *[size]u8) Branch {29        std.debug.assert(bytes[kind_offset] == branch_kind);30        return .{ .bytes = bytes };31    }3233    pub fn id(self: *const Branch) u64 {34        return self.readU64(id_offset);35    }3637    pub fn generation(self: *const Branch) u64 {38        return self.readU64(generation_offset);39    }4041    pub fn cellCount(self: *const Branch) usize {42        return self.readU16(cells_offset);43    }4445    pub fn childAt(self: *const Branch, index: usize) u32 {46        return self.childPayloadAt(index);47    }4849    pub fn lowerAt(self: *const Branch, index: usize) []const u8 {50        return self.keyAt(index);51    }5253    pub fn firstLower(self: *const Branch) ?[]const u8 {54        if (self.cellCount() == 0) return null;55        return self.keyAt(0);56    }5758    pub fn childIndexFor(self: *const Branch, key: []const u8) usize {59        const index = self.lowerBound(key);60        if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), key)) return index;61        if (index == 0) return 0;62        return index - 1;63    }6465    pub fn childFor(self: *const Branch, key: []const u8) u32 {66        return self.childAt(self.childIndexFor(key));67    }6869    pub fn put(self: *Branch, lower_key: []const u8, child: u32) Error!void {70        if (child == 0) return error.InvalidPage;71        const child_bytes = childBytes(child);72        try checkLengths(lower_key, child_bytes[0..]);73        const next_generation = try self.nextGeneration();74        const index = self.lowerBound(lower_key);75        if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), lower_key)) {76            const slot = self.slotAt(index);77            const child_offset: usize = slot.offset + slot.key_len;78            self.bytes[child_offset..][0..child_bytes.len].* = child_bytes;79        } else {80            try self.cells().insert(index, lower_key, child_bytes[0..]);81        }82        self.writeU64(generation_offset, next_generation);83    }8485    pub fn splitPut(self: *const Branch, left: *Branch, right: *Branch, lower_key: []const u8, child: u32) Error![]const u8 {86        if (child == 0) return error.InvalidPage;87        const child_bytes = childBytes(child);88        try checkLengths(lower_key, child_bytes[0..]);89        const next_generation = try self.nextGeneration();90        left.writeU64(generation_offset, next_generation);91        right.writeU64(generation_offset, next_generation);9293        var replacement = false;94        var index: usize = 0;95        while (index < self.cellCount()) : (index += 1) {96            if (std.mem.eql(u8, self.keyAt(index), lower_key)) replacement = true;97        }9899        const total = self.cellCount() + if (replacement) @as(usize, 0) else 1;100        const split_index = try splitIndexFor(self, lower_key, child_bytes.len, total);101        var ordinal: usize = 0;102        var inserted = false;103        index = 0;104        while (index < self.cellCount()) : (index += 1) {105            const entry = self.entryAt(index);106            switch (simd.order(Bytes, entry.lower, lower_key)) {107                .lt => try appendSplitBranchEntry(left, right, split_index, &ordinal, entry.lower, entry.child),108                .eq => {109                    if (!inserted) {110                        try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child);111                        inserted = true;112                    }113                },114                .gt => {115                    if (!inserted) {116                        try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child);117                        inserted = true;118                    }119                    try appendSplitBranchEntry(left, right, split_index, &ordinal, entry.lower, entry.child);120                },121            }122        }123        if (!inserted) try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child);124        return right.firstLower() orelse error.InvalidPage;125    }126127    pub fn replace(self: *Branch, index: usize, lower_key: []const u8, child: u32) Error!void {128        if (index >= self.cellCount()) return error.InvalidPage;129        if (child == 0) return error.InvalidPage;130        const child_bytes = childBytes(child);131        try checkLengths(lower_key, child_bytes[0..]);132        const next_generation = try self.nextGeneration();133134        var scratch: [size]u8 = undefined;135        var rebuilt = Branch.init(&scratch, self.id());136        rebuilt.writeU64(generation_offset, next_generation);137138        var cursor: usize = 0;139        while (cursor < self.cellCount()) : (cursor += 1) {140            if (cursor == index) {141                try rebuilt.appendEntry(lower_key, child);142            } else {143                const entry = self.entryAt(cursor);144                try rebuilt.appendEntry(entry.lower, entry.child);145            }146        }147        self.bytes.* = scratch;148    }149150    pub fn remove(self: *Branch, index: usize) Error!void {151        if (index >= self.cellCount()) return error.InvalidPage;152        const next_generation = try self.nextGeneration();153        self.cells().remove(index);154        self.writeU64(generation_offset, next_generation);155    }156157    pub fn copyTo(self: *const Branch, target: *Branch) Error!void {158        target.writeU64(generation_offset, self.generation());159        var index: usize = 0;160        while (index < self.cellCount()) : (index += 1) {161            const entry = self.entryAt(index);162            try target.appendEntry(entry.lower, entry.child);163        }164    }165166    fn validate(self: *const Branch) Error!void {167        if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage;168        if (self.bytes[version_offset] != format_version) return error.InvalidPage;169        if (self.bytes[kind_offset] != branch_kind) return error.InvalidPage;170        if (self.readU16(flags_offset) != 0) return error.InvalidPage;171        if (self.readU16(reserved_offset) != 0) return error.InvalidPage;172        const count = self.cellCount();173        if (count > (size - header_size) / slot_size) return error.InvalidPage;174        const lower_bound = self.lower();175        const upper_bound = self.upper();176        if (lower_bound != header_size + count * slot_size) return error.InvalidPage;177        if (upper_bound < lower_bound or upper_bound > size) return error.InvalidPage;178        if (count == 0) return error.InvalidPage;179180        var index: usize = 0;181        while (index < count) : (index += 1) {182            const slot = self.slotAt(index);183            const offset: usize = slot.offset;184            const payload_end = offset + @as(usize, slot.key_len) + @as(usize, slot.value_len);185            if (offset < upper_bound or payload_end > size) return error.InvalidPage;186            if (slot.flags != 0) return error.InvalidPage;187            if (slot.value_len != 4) return error.InvalidPage;188            if (self.childPayloadAt(index) == 0) return error.InvalidPage;189            if (index > 0 and simd.order(Bytes, self.keyAt(index - 1), self.keyAt(index)) != .lt) return error.InvalidPage;190        }191    }192193    fn appendEntry(self: *Branch, lower_key: []const u8, child: u32) Error!void {194        const child_bytes = childBytes(child);195        try self.cells().insert(self.cellCount(), lower_key, child_bytes[0..]);196    }197198    fn cells(self: *Branch) Cells {199        return .{ .bytes = self.bytes };200    }201202    fn entryAt(self: *const Branch, index: usize) BranchEntry {203        return .{ .lower = self.keyAt(index), .child = self.childPayloadAt(index) };204    }205206    fn lowerBound(self: *const Branch, key: []const u8) usize {207        var low: usize = 0;208        var high = self.cellCount();209        while (low < high) {210            const mid = low + (high - low) / 2;211            switch (simd.order(Bytes, self.keyAt(mid), key)) {212                .lt => low = mid + 1,213                .eq, .gt => high = mid,214            }215        }216        return low;217    }218219    fn nextGeneration(self: *const Branch) Error!u64 {220        const current = self.generation();221        if (current == std.math.maxInt(u64)) return error.GenerationOverflow;222        return current + 1;223    }224225    fn keyAt(self: *const Branch, index: usize) []const u8 {226        const slot = self.slotAt(index);227        const start: usize = slot.offset;228        return self.bytes[start..][0..slot.key_len];229    }230231    fn childPayloadAt(self: *const Branch, index: usize) u32 {232        const slot = self.slotAt(index);233        const start: usize = slot.offset + slot.key_len;234        return std.mem.readInt(u32, self.bytes[start..][0..4], .big);235    }236237    fn slotAt(self: *const Branch, index: usize) Slot {238        const offset = header_size + index * slot_size;239        return .{240            .offset = self.readU16(offset),241            .key_len = self.readU16(offset + 2),242            .value_len = self.readU16(offset + 4),243            .flags = self.readU16(offset + 6),244        };245    }246247    fn lower(self: *const Branch) usize {248        return self.readU16(lower_offset);249    }250251    fn upper(self: *const Branch) usize {252        return self.readU16(upper_offset);253    }254255    fn readU16(self: *const Branch, offset: usize) u16 {256        return std.mem.readInt(u16, self.bytes[offset..][0..2], .big);257    }258259    fn readU64(self: *const Branch, offset: usize) u64 {260        return std.mem.readInt(u64, self.bytes[offset..][0..8], .big);261    }262263    fn writeU16(self: *Branch, offset: usize, value: u16) void {264        std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big);265    }266267    fn writeU64(self: *Branch, offset: usize, value: u64) void {268        std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big);269    }270};

1pub const BranchPage = page.Branch;