tiny.sql.LeafPage

1pub const Leaf = struct {2    bytes: *[size]u8,34    pub fn init(bytes: *[size]u8, page_id: u64) Leaf {5        var leaf = Leaf{ .bytes = bytes };6        @memset(leaf.bytes, 0);7        @memcpy(leaf.bytes[magic_offset..][0..magic.len], magic[0..]);8        leaf.bytes[version_offset] = format_version;9        leaf.bytes[kind_offset] = leaf_kind;10        leaf.writeU16(flags_offset, 0);11        leaf.writeU64(id_offset, page_id);12        leaf.writeU64(generation_offset, 0);13        leaf.writeU16(lower_offset, header_size);14        leaf.writeU16(upper_offset, size);15        leaf.writeU16(cells_offset, 0);16        leaf.writeU16(reserved_offset, 0);17        return leaf;18    }1920    pub fn load(bytes: *[size]u8) Error!Leaf {21        const leaf = Leaf{ .bytes = bytes };22        try leaf.validate();23        return leaf;24    }2526    /// Wraps a leaf image that `load` validated, without walking its cells27    /// again. The image must be unchanged since that `load`. A reader that28    /// returns to one leaf once per cell validates it once through `load` and29    /// resumes through this.30    pub fn fromValidated(bytes: *[size]u8) Leaf {31        std.debug.assert(bytes[kind_offset] == leaf_kind);32        return .{ .bytes = bytes };33    }3435    pub fn id(self: *const Leaf) u64 {36        return self.readU64(id_offset);37    }3839    pub fn generation(self: *const Leaf) u64 {40        return self.readU64(generation_offset);41    }4243    pub fn cellCount(self: *const Leaf) usize {44        return self.readU16(cells_offset);45    }4647    pub fn firstKey(self: *const Leaf) ?[]const u8 {48        if (self.cellCount() == 0) return null;49        return self.keyAt(0);50    }5152    pub fn freeBytes(self: *const Leaf) usize {53        const lower_bound = self.lower();54        const upper_bound = self.upper();55        if (upper_bound < lower_bound) return 0;56        return upper_bound - lower_bound;57    }5859    pub fn usedBytes(self: *const Leaf) usize {60        return size - self.freeBytes();61    }6263    pub fn get(self: *const Leaf, key: []const u8) ?[]const u8 {64        const phase = trace.scope("page.leaf.get");65        defer phase.end();66        const index = self.lowerBound(key);67        if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), key)) return self.valueAt(index);68        return null;69    }7071    pub fn put(self: *Leaf, key: []const u8, value: []const u8) Error!void {72        const phase = trace.scope("page.leaf.put");73        defer phase.end();74        try checkLengths(key, value);75        const next_generation = try self.nextGeneration();7677        const existing_index = self.lowerBound(key);78        if (existing_index == self.cellCount() or79            !std.mem.eql(u8, self.keyAt(existing_index), key))80        {81            try self.cells().insert(existing_index, key, value);82            self.writeU64(generation_offset, next_generation);83            trace.progress("page.leaf.put.insert.complete");84            return;85        }86        const slot = self.slotAt(existing_index);87        if (value.len == slot.value_len) {88            const value_offset: usize = slot.offset + slot.key_len;89            @memcpy(self.bytes[value_offset..][0..value.len], value);90            self.writeU64(generation_offset, next_generation);91            trace.progress("page.leaf.put.inplace.complete");92            return;93        }9495        var scratch: [size]u8 = undefined;96        var rebuilt = Leaf.init(&scratch, self.id());97        rebuilt.writeU64(generation_offset, next_generation);9899        var inserted = false;100        var index: usize = 0;101        while (index < self.cellCount()) : (index += 1) {102            const entry = self.entryAt(index);103            switch (simd.order(Bytes, entry.key, key)) {104                .lt => try rebuilt.appendEntry(entry.key, entry.value),105                .eq => {106                    if (!inserted) {107                        try rebuilt.appendEntry(key, value);108                        inserted = true;109                    }110                },111                .gt => {112                    if (!inserted) {113                        try rebuilt.appendEntry(key, value);114                        inserted = true;115                    }116                    try rebuilt.appendEntry(entry.key, entry.value);117                },118            }119        }120        if (!inserted) try rebuilt.appendEntry(key, value);121122        self.bytes.* = scratch;123        trace.progress("page.leaf.put.complete");124    }125126    pub fn delete(self: *Leaf, key: []const u8) Error!void {127        const phase = trace.scope("page.leaf.delete");128        defer phase.end();129        const next_generation = try self.nextGeneration();130        const index = self.lowerBound(key);131        if (index == self.cellCount() or !std.mem.eql(u8, self.keyAt(index), key)) {132            return error.KeyNotFound;133        }134        self.cells().remove(index);135        self.writeU64(generation_offset, next_generation);136        trace.progress("page.leaf.delete.complete");137    }138139    pub fn range(self: *const Leaf, start: ?[]const u8, end: ?[]const u8) Error!Range {140        if (start) |lower_key| {141            if (end) |upper_key| {142                if (simd.order(Bytes, lower_key, upper_key) == .gt) return error.InvalidRange;143            }144        }145        return .{146            .leaf = self,147            .end = end,148            .index = if (start) |key| self.lowerBound(key) else 0,149        };150    }151152    pub fn splitPut(self: *const Leaf, left: *Leaf, right: *Leaf, key: []const u8, value: []const u8) Error![]const u8 {153        const phase = trace.scope("page.leaf.split_put");154        defer phase.end();155        try checkLengths(key, value);156        const next_generation = try self.nextGeneration();157        left.writeU64(generation_offset, next_generation);158        right.writeU64(generation_offset, next_generation);159160        var replacement = false;161        var index: usize = 0;162        while (index < self.cellCount()) : (index += 1) {163            if (std.mem.eql(u8, self.keyAt(index), key)) replacement = true;164        }165166        const total = self.cellCount() + if (replacement) @as(usize, 0) else 1;167        const split_index = try splitIndexFor(self, key, value.len, total);168        var ordinal: usize = 0;169        var inserted = false;170        index = 0;171        while (index < self.cellCount()) : (index += 1) {172            const entry = self.entryAt(index);173            switch (simd.order(Bytes, entry.key, key)) {174                .lt => {175                    try appendSplitEntry(left, right, split_index, &ordinal, entry.key, entry.value);176                },177                .eq => {178                    if (!inserted) {179                        try appendSplitEntry(left, right, split_index, &ordinal, key, value);180                        inserted = true;181                    }182                },183                .gt => {184                    if (!inserted) {185                        try appendSplitEntry(left, right, split_index, &ordinal, key, value);186                        inserted = true;187                    }188                    try appendSplitEntry(left, right, split_index, &ordinal, entry.key, entry.value);189                },190            }191        }192        if (!inserted) try appendSplitEntry(left, right, split_index, &ordinal, key, value);193        return right.firstKey() orelse error.InvalidPage;194    }195196    pub fn copyTo(self: *const Leaf, target: *Leaf) Error!void {197        target.writeU64(generation_offset, self.generation());198        var index: usize = 0;199        while (index < self.cellCount()) : (index += 1) {200            const entry = self.entryAt(index);201            try target.appendEntry(entry.key, entry.value);202        }203    }204205    fn validate(self: *const Leaf) Error!void {206        if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage;207        if (self.bytes[version_offset] != format_version) return error.InvalidPage;208        if (self.bytes[kind_offset] != leaf_kind) return error.InvalidPage;209        if (self.readU16(flags_offset) != 0) return error.InvalidPage;210        if (self.readU16(reserved_offset) != 0) return error.InvalidPage;211        const count = self.cellCount();212        if (count > (size - header_size) / slot_size) return error.InvalidPage;213        const lower_bound = self.lower();214        const upper_bound = self.upper();215        if (lower_bound != header_size + count * slot_size) return error.InvalidPage;216        if (upper_bound < lower_bound or upper_bound > size) return error.InvalidPage;217218        var index: usize = 0;219        while (index < count) : (index += 1) {220            const slot = self.slotAt(index);221            const offset: usize = slot.offset;222            const payload_end = offset + @as(usize, slot.key_len) + @as(usize, slot.value_len);223            if (offset < upper_bound or payload_end > size) return error.InvalidPage;224            if (slot.flags != 0) return error.InvalidPage;225            if (index > 0 and simd.order(Bytes, self.keyAt(index - 1), self.keyAt(index)) != .lt) return error.InvalidPage;226        }227    }228229    fn appendEntry(self: *Leaf, key: []const u8, value: []const u8) Error!void {230        try self.cells().insert(self.cellCount(), key, value);231    }232233    fn cells(self: *Leaf) Cells {234        return .{ .bytes = self.bytes };235    }236237    fn lowerBound(self: *const Leaf, key: []const u8) usize {238        var low: usize = 0;239        var high = self.cellCount();240        while (low < high) {241            const mid = low + (high - low) / 2;242            switch (simd.order(Bytes, self.keyAt(mid), key)) {243                .lt => low = mid + 1,244                .eq, .gt => high = mid,245            }246        }247        return low;248    }249250    fn nextGeneration(self: *const Leaf) Error!u64 {251        const current = self.generation();252        if (current == std.math.maxInt(u64)) return error.GenerationOverflow;253        return current + 1;254    }255256    pub fn lastKey(self: *const Leaf) ?[]const u8 {257        const count = self.cellCount();258        if (count == 0) return null;259        return self.keyAt(count - 1);260    }261262    fn entryAt(self: *const Leaf, index: usize) Entry {263        return .{ .key = self.keyAt(index), .value = self.valueAt(index) };264    }265266    fn keyAt(self: *const Leaf, index: usize) []const u8 {267        const slot = self.slotAt(index);268        const start: usize = slot.offset;269        return self.bytes[start..][0..slot.key_len];270    }271272    fn valueAt(self: *const Leaf, index: usize) []const u8 {273        const slot = self.slotAt(index);274        const start: usize = slot.offset + slot.key_len;275        return self.bytes[start..][0..slot.value_len];276    }277278    fn slotAt(self: *const Leaf, index: usize) Slot {279        const offset = header_size + index * slot_size;280        return .{281            .offset = self.readU16(offset),282            .key_len = self.readU16(offset + 2),283            .value_len = self.readU16(offset + 4),284            .flags = self.readU16(offset + 6),285        };286    }287288    fn lower(self: *const Leaf) usize {289        return self.readU16(lower_offset);290    }291292    fn upper(self: *const Leaf) usize {293        return self.readU16(upper_offset);294    }295296    fn readU16(self: *const Leaf, offset: usize) u16 {297        return std.mem.readInt(u16, self.bytes[offset..][0..2], .big);298    }299300    fn readU64(self: *const Leaf, offset: usize) u64 {301        return std.mem.readInt(u64, self.bytes[offset..][0..8], .big);302    }303304    fn writeU16(self: *Leaf, offset: usize, value: u16) void {305        std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big);306    }307308    fn writeU64(self: *Leaf, offset: usize, value: u64) void {309        std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big);310    }311};

1pub const LeafPage = page.Leaf;