tiny.sql.TreeScan

1pub const Scan = struct {2    allocator: Allocator,3    read: ?file.ReadLease,4    snapshot: file.Snapshot,5    frames: [max_height]BranchFrame = undefined,6    depth: usize = 0,7    /// Image of the branch at `frames[depth - 1]`, validated when read. Leaf8    /// advances under one parent read only the next leaf.9    parent: [page.size]u8 = undefined,10    /// Image of the current leaf, validated when read.11    leaf: [page.size]u8 = undefined,12    value: std.ArrayList(u8) = .empty,13    end_key: [page.size]u8 = undefined,14    end_len: ?usize,15    index: usize,16    projection: Projection,17    observed: ScanStats = .{},18    /// The first error `next` returned. A page that fails to read or validate19    /// can be left in `leaf` or `parent`, so the scan stops there and returns20    /// the same error from then on.21    failure: ?Error = null,2223    /// Fills `self` in place, since a scan holds three page-sized buffers24    /// that a return by value would copy through each caller.25    fn init(26        self: *Scan,27        allocator: Allocator,28        snapshot: file.Snapshot,29        root_page: u32,30        start: ?[]const u8,31        end: ?[]const u8,32        projection: Projection,33    ) Error!void {34        const retained = try snapshot.retain();35        self.* = .{36            .allocator = allocator,37            .read = retained,38            .snapshot = snapshot,39            .end_len = null,40            .index = 0,41            .projection = projection,42        };43        errdefer if (self.read) |*read| read.deinit();44        if (end) |key| {45            if (key.len > page.size) return error.KeyTooLarge;46            @memcpy(self.end_key[0..key.len], key);47            self.end_len = key.len;48        }49        const root_mark = try readRoot(snapshot, root_page, &self.leaf);50        try self.descend(root_page, root_mark, start);51        const leaf = page.Leaf.fromValidated(&self.leaf);52        const leaf_range = try leaf.range(start, self.endSlice());53        self.index = leaf_range.index;54    }5556    pub fn deinit(self: *Scan) void {57        self.value.deinit(self.allocator);58        if (self.read) |*read| read.deinit();59        self.* = undefined;60    }6162    pub fn next(self: *Scan) Error!?ScanEntry {63        if (self.failure) |failure| return failure;64        return self.nextEntry() catch |err| {65            self.failure = err;66            return err;67        };68    }6970    fn nextEntry(self: *Scan) Error!?ScanEntry {71        while (true) {72            const leaf = page.Leaf.fromValidated(&self.leaf);73            var leaf_range = page.Range{74                .leaf = &leaf,75                .end = self.endSlice(),76                .index = self.index,77            };78            if (leaf_range.next()) |entry| {79                self.index = leaf_range.index;80                self.observed.entries_returned += 1;81                return .{82                    .key = entry.key,83                    .bytes = try self.valueFor(entry.value),84                };85            }86            if (!(try self.advanceLeaf())) return null;87        }88    }8990    fn valueFor(self: *Scan, bytes: []const u8) Error![]const u8 {91        return switch (self.projection) {92            .key => "",93            .record => bytes,94            .value => value: {95                if (bytes.len == 0) return error.InvalidRecord;96                break :value switch (bytes[0]) {97                    record.inline_tag => bytes[1..],98                    record.overflow_tag => overflow_value: {99                        const overflow = try record.overflow(bytes);100                        const len = try overflowLengthAsUsize(overflow.len);101                        try self.value.resize(self.allocator, len);102                        try readOverflowValueInto(self.snapshot, overflow, self.value.items);103                        break :overflow_value self.value.items;104                    },105                    else => error.InvalidRecord,106                };107            },108        };109    }110111    pub fn stats(self: *const Scan) ScanStats {112        return self.observed;113    }114115    fn endSlice(self: *const Scan) ?[]const u8 {116        const len = self.end_len orelse return null;117        return self.end_key[0..len];118    }119120    /// Descends from the page image in `self.leaf`, which is `page_id` with121    /// mark `page_mark`, to the leaf that holds `start`, or to the leftmost122    /// leaf. Each page is read into scan storage and loaded once. The last123    /// branch passed stays in `self.parent`.124    fn descend(self: *Scan, page_id: u32, page_mark: file.PageMark, start: ?[]const u8) Error!void {125        var current_page = page_id;126        var mark = page_mark;127        while (true) {128            switch (try loadMarkedTreePage(&self.leaf, mark)) {129                .leaf => {130                    self.observed.leaf_pages_visited += 1;131                    return;132                },133                .branch => {134                    if (self.depth >= max_height) return error.TreeTooDeep;135                    self.parent = self.leaf;136                    const branch = page.Branch.fromValidated(&self.parent);137                    self.observed.branch_pages_visited += 1;138                    const index = if (start) |key| branch.childIndexFor(key) else 0;139                    self.frames[self.depth] = .{140                        .page_id = current_page,141                        .index = index,142                    };143                    self.depth += 1;144                    current_page = branch.childAt(index);145                    mark = try readMarkedPage(self.snapshot, current_page, &self.leaf);146                },147            }148        }149    }150151    /// Moves to the next leaf in key order. The branch above the current leaf152    /// is already in `self.parent`, so an advance to a sibling reads one page.153    /// Only an advance past the parent's last child rereads a higher branch.154    fn advanceLeaf(self: *Scan) Error!bool {155        while (self.depth > 0) {156            const frame = &self.frames[self.depth - 1];157            const branch = page.Branch.fromValidated(&self.parent);158            const next_index = frame.index + 1;159            if (next_index < branch.cellCount()) {160                if (!self.childStartsBeforeEnd(branch.lowerAt(next_index))) {161                    self.observed.separator_children_pruned += branch.cellCount() - next_index;162                    return false;163                }164                frame.index = next_index;165                const child = branch.childAt(next_index);166                const mark = try readMarkedPage(self.snapshot, child, &self.leaf);167                try self.descend(child, mark, null);168                self.index = 0;169                return true;170            }171            self.depth -= 1;172            if (self.depth > 0) {173                const parent_page = self.frames[self.depth - 1].page_id;174                const mark = try readMarkedPage(self.snapshot, parent_page, &self.parent);175                switch (try loadMarkedTreePage(&self.parent, mark)) {176                    .leaf => return error.InvalidPage,177                    .branch => self.observed.branch_pages_visited += 1,178                }179            }180        }181        return false;182    }183184    fn childStartsBeforeEnd(self: *const Scan, lower_key: []const u8) bool {185        const end = self.endSlice() orelse return true;186        return simd.order(Bytes, lower_key, end) == .lt;187    }188};

1pub const TreeScan = tree.Scan;