tiny.sql.Tree

1pub const Tree = struct {2    database: *file.Database,3    meta_page: u32,4    root_page: u32,5    identity_page: u32,6    reserved_page_max: u32,78    pub fn open(database: *file.Database, options: Options) Error!Tree {9        const reserved_page_max = try validateOptions(options);10        return .{11            .database = database,12            .meta_page = options.meta_page,13            .root_page = options.root_page,14            .identity_page = options.identity_page,15            .reserved_page_max = reserved_page_max,16        };17    }1819    pub fn reader(self: *const Tree, snapshot: file.Snapshot) Error!Reader {20        return .{21            .snapshot = snapshot,22            .meta_page = self.meta_page,23            .root_page = self.root_page,24            .identity_page = self.identity_page,25            .reserved_page_max = self.reserved_page_max,26        };27    }2829    pub fn identity(self: *const Tree) Error!TreeIdentity {30        var read = try self.database.beginRead();31        defer read.deinit();32        const opened = try self.reader(read.snapshot());33        return try opened.identity();34    }3536    /// Returns the digest of `identity_value`, an identity this tree read37    /// from its identity page, through its database's memo.38    pub fn digestIdentity(39        self: *const Tree,40        identity_value: *const TreeIdentity,41    ) [lattice.digest_size]u8 {42        return self.database.digest_memo.digest(43            self.identity_page,44            &identity_value.state,45            identity_value.entries,46        );47    }4849    pub fn get(self: *const Tree, allocator: Allocator, key: []const u8) Error!?[]u8 {50        var read = try self.database.beginRead();51        defer read.deinit();52        const opened = try self.reader(read.snapshot());53        return try opened.get(allocator, key);54    }5556    pub fn valueLength(self: *const Tree, key: []const u8) Error!?usize {57        var read = try self.database.beginRead();58        defer read.deinit();59        const opened = try self.reader(read.snapshot());60        return try opened.valueLength(key);61    }6263    pub fn getInto(self: *const Tree, key: []const u8, target: []u8) Error!?[]u8 {64        var read = try self.database.beginRead();65        defer read.deinit();66        const opened = try self.reader(read.snapshot());67        return try opened.getInto(key, target);68    }6970    pub fn lastKey(self: *const Tree, buffer: []u8) Error!?[]const u8 {71        var read = try self.database.beginRead();72        defer read.deinit();73        const opened = try self.reader(read.snapshot());74        return try opened.lastKey(buffer);75    }7677    pub fn put(self: *Tree, key: []const u8, value: []const u8, options: file.CommitOptions) Error!file.Commit {78        const phase = trace.scope("tree.put");79        defer phase.end();8081        var write = try Write.beginTree(self);82        defer write.deinit();83        try write.put(self, key, value);84        return try write.commit(options);85    }8687    fn putInWrite(self: *Tree, write: *Write, key: []const u8, value: []const u8) Error!void {88        var pending_storage: PendingPut = undefined;89        var pending: ?*PendingPut = null;90        if (try write.identityScratch(self)) |scratch| {91            var hasher = lattice.EntryHasher.init(key);92            hasher.update(value);93            pending_storage = .{94                .scratch = scratch,95                .fresh = hasher.finish(),96                .key_len = key.len,97                .value_len = value.len,98            };99            pending = &pending_storage;100        }101102        var inline_buffer: [inline_value_max + 1]u8 = undefined;103        var overflow_buffer: [record.overflow_size]u8 = undefined;104        const value_record = try self.writeValueRecord(write, value, &inline_buffer, &overflow_buffer);105        var root_scratch: [page.size]u8 = undefined;106        switch (try write.readRootPage(self, &root_scratch)) {107            .leaf => |leaf| try self.putRootLeaf(write, leaf, key, value_record, pending),108            .branch => |branch| try self.putRootBranch(write, branch, key, value_record, pending),109        }110    }111112    fn applyPutIdentity(self: *const Tree, write: *Write, pending: ?*PendingPut, key: []const u8, old_record: ?[]const u8) Error!void {113        const pending_put = pending orelse return;114        if (old_record) |encoded| {115            const old = try self.entryStateFromRecord(write, key, encoded);116            pending_put.scratch.state.subtract(&old.state);117            pending_put.scratch.value_bytes -= old.value_len;118        } else {119            pending_put.scratch.entries += 1;120            pending_put.scratch.key_bytes += pending_put.key_len;121        }122        pending_put.scratch.value_bytes += pending_put.value_len;123        pending_put.scratch.state.add(&pending_put.fresh);124        pending_put.scratch.dirty = true;125    }126127    fn applyDeleteIdentity(self: *const Tree, write: *Write, scratch: ?*IdentityScratch, key: []const u8, old_record: []const u8) Error!void {128        const identity_scratch = scratch orelse return;129        const old = try self.entryStateFromRecord(write, key, old_record);130        identity_scratch.state.subtract(&old.state);131        identity_scratch.entries -= 1;132        identity_scratch.key_bytes -= key.len;133        identity_scratch.value_bytes -= old.value_len;134        identity_scratch.dirty = true;135    }136137    fn entryStateFromRecord(self: *const Tree, write: *Write, key: []const u8, value_record: []const u8) Error!OldEntry {138        _ = self;139        var hasher = lattice.EntryHasher.init(key);140        var value_len: u64 = 0;141        switch (try record.kind(value_record)) {142            .inline_value => {143                const inline_value = try record.inlineValue(value_record);144                value_len = inline_value.len;145                hasher.update(inline_value);146            },147            .overflow => {148                const overflow = try record.overflow(value_record);149                value_len = overflow.len;150                var remaining = try overflowLengthAsUsize(overflow.len);151                var page_id = overflow.first_page;152                while (page_id != 0) {153                    var image: [page.size]u8 = undefined;154                    try write.readExistingPage(page_id, &image);155                    const overflow_page = try page.Overflow.load(&image);156                    const expected = @min(page.overflow_capacity, remaining);157                    if (overflow_page.content().len != expected) return error.InvalidPage;158                    hasher.update(overflow_page.content());159                    const next_page = overflow_page.next();160                    remaining -= expected;161                    if (remaining == 0 and next_page != 0) return error.InvalidPage;162                    if (remaining > 0 and next_page == 0) return error.InvalidPage;163                    page_id = next_page;164                }165                if (remaining != 0) return error.InvalidPage;166            },167        }168        return .{ .state = hasher.finish(), .value_len = value_len };169    }170171    pub fn delete(self: *Tree, key: []const u8, options: file.CommitOptions) Error!file.Commit {172        const phase = trace.scope("tree.delete");173        defer phase.end();174175        var write = try Write.beginTree(self);176        defer write.deinit();177        try write.delete(self, key);178        return try write.commit(options);179    }180181    fn deleteInWrite(self: *Tree, write: *Write, key: []const u8) Error!void {182        const scratch = try write.identityScratch(self);183        var root_scratch: [page.size]u8 = undefined;184        switch (try write.readRootPage(self, &root_scratch)) {185            .leaf => |loaded| {186                var leaf = loaded;187                const old_record = leaf.get(key) orelse return error.KeyNotFound;188                try self.applyDeleteIdentity(write, scratch, key, old_record);189                const old_overflow = try overflowRefOrNull(old_record);190                try leaf.delete(key);191                if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);192                try write.putPage(self.root_page, leaf.bytes);193            },194            .branch => |branch| try self.deleteRootBranch(write, branch, key, scratch),195        }196    }197198    pub fn clear(self: *Tree, options: file.CommitOptions) Error!file.Commit {199        const phase = trace.scope("tree.clear");200        defer phase.end();201202        var write = try Write.beginTree(self);203        defer write.deinit();204        try write.clear(self);205        return try write.commit(options);206    }207208    fn clearInWrite(self: *Tree, write: *Write) Error!void {209        var root_image: [page.size]u8 = undefined;210        try write.readRoot(self, &root_image);211        var pages: std.ArrayList(u32) = .empty;212        defer pages.deinit(write.database.allocator);213        try self.collectReleasedPages(write, &root_image, 0, &pages);214        std.mem.sort(u32, pages.items, {}, PageIdSort.desc);215        for (pages.items) |page_id| try write.releasePage(self.root_page, page_id);216        _ = page.Leaf.init(&root_image, self.root_page);217        try write.putPage(self.root_page, &root_image);218        if (try write.identityScratch(self)) |scratch| {219            scratch.state = lattice.State.empty;220            scratch.entries = 0;221            scratch.key_bytes = 0;222            scratch.value_bytes = 0;223            scratch.dirty = true;224        }225    }226227    pub fn range(228        self: *const Tree,229        target: *Range,230        allocator: Allocator,231        start: ?[]const u8,232        end: ?[]const u8,233    ) Error!void {234        var read = try self.database.beginRead();235        defer read.deinit();236        const opened = try self.reader(read.snapshot());237        try opened.range(target, allocator, start, end);238    }239240    pub fn scan(241        self: *const Tree,242        target: *Scan,243        allocator: Allocator,244        start: ?[]const u8,245        end: ?[]const u8,246        projection: Projection,247    ) Error!void {248        var read = try self.database.beginRead();249        defer read.deinit();250        const opened = try self.reader(read.snapshot());251        try opened.scan(target, allocator, start, end, projection);252    }253254    pub fn summarize(self: *const Tree) Error!Summary {255        var read = try self.database.beginRead();256        defer read.deinit();257        const opened = try self.reader(read.snapshot());258        return try opened.summarize();259    }260261    pub fn count(self: *const Tree) Error!usize {262        var read = try self.database.beginRead();263        defer read.deinit();264        const opened = try self.reader(read.snapshot());265        return try opened.count();266    }267268    pub fn summarizeIn(self: *const Tree, write: *const Write) Error!Summary {269        const phase = trace.scope("tree.summarize_in");270        defer phase.end();271272        try write.ensureTree(self);273        var root_image: [page.size]u8 = undefined;274        try write.readRoot(self, &root_image);275        var summary = Summary{};276        try summarizePage(write, &root_image, 0, &summary);277        return summary;278    }279280    pub fn root(self: *const Tree, allocator: Allocator) Error!Root {281        const phase = trace.scope("tree.root");282        defer phase.end();283284        var read = try self.database.beginRead();285        defer read.deinit();286        const snapshot = read.snapshot();287        if (self.database.tree_roots.find(self.root_page, snapshot.view.base_generation, snapshot.view.end_mark)) |cached| {288            return try cached.clone(allocator);289        }290        var root_image: [page.size]u8 = undefined;291        _ = try readRoot(snapshot, self.root_page, &root_image);292        var build = RootBuild.init(allocator);293        errdefer build.deinit();294        _ = try build.appendNode(snapshot, &root_image, &.{}, null, 0);295        const built = try build.finish();296        self.database.tree_roots.store(297            self.database.allocator,298            self.root_page,299            snapshot.view.base_generation,300            snapshot.view.end_mark,301            &built,302        ) catch {};303        return built;304    }305306    fn putRootLeaf(307        self: *Tree,308        write: *Write,309        loaded: page.Leaf,310        key: []const u8,311        value_record: []const u8,312        pending: ?*PendingPut,313    ) Error!void {314        var leaf = loaded;315        const root_image = leaf.bytes;316        const old_record = leaf.get(key);317        try self.applyPutIdentity(write, pending, key, old_record);318        const old_overflow = try overflowRefOrNull(old_record);319        leaf.put(key, value_record) catch |err| switch (err) {320            error.PageFull => {321                const first_child = try write.allocatePage();322                const second_child = try write.allocatePage();323                var left_image: [page.size]u8 = undefined;324                var right_image: [page.size]u8 = undefined;325                var left = page.Leaf.init(&left_image, first_child);326                var right = page.Leaf.init(&right_image, second_child);327                const separator = leaf.splitPut(&left, &right, key, value_record) catch |split_err| switch (split_err) {328                    error.PageFull => return error.KeyTooLarge,329                    else => return split_err,330                };331                var branch = page.Branch.init(root_image, self.root_page);332                try branch.put(&.{}, first_child);333                try branch.put(separator, second_child);334                if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);335                try write.putPage(self.root_page, root_image);336                try write.putPage(first_child, &left_image);337                try write.putPage(second_child, &right_image);338                return;339            },340            else => return err,341        };342        if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);343        try write.putPage(self.root_page, root_image);344    }345346    fn putRootBranch(347        self: *Tree,348        write: *Write,349        loaded: page.Branch,350        key: []const u8,351        value_record: []const u8,352        pending: ?*PendingPut,353    ) Error!void {354        var branch = loaded;355        const root_image = branch.bytes;356        const child_id = branch.childFor(key);357        const split = (try self.putNonRoot(write, child_id, key, value_record, 1, pending)) orelse return;358        branch.put(split.key(), split.child) catch |err| switch (err) {359            error.PageFull => {360                const left_child = try write.allocatePage();361                const right_child = try write.allocatePage();362                var left_image: [page.size]u8 = undefined;363                var right_image: [page.size]u8 = undefined;364                var left = page.Branch.init(&left_image, left_child);365                var right = page.Branch.init(&right_image, right_child);366                const separator = branch.splitPut(&left, &right, split.key(), split.child) catch |split_err| switch (split_err) {367                    error.PageFull => return error.KeyTooLarge,368                    else => return split_err,369                };370                const left_lower = left.firstLower() orelse return error.InvalidPage;371                var new_root = page.Branch.init(root_image, self.root_page);372                try new_root.put(left_lower, left_child);373                try new_root.put(separator, right_child);374                try write.putPage(self.root_page, root_image);375                try write.putPage(left_child, &left_image);376                try write.putPage(right_child, &right_image);377                return;378            },379            else => return err,380        };381        try write.putPage(self.root_page, root_image);382    }383384    fn putNonRoot(self: *Tree, write: *Write, page_id: u32, key: []const u8, value_record: []const u8, depth: usize, pending: ?*PendingPut) Error!?Separator {385        if (depth >= max_height) return error.TreeTooDeep;386        var scratch: [page.size]u8 = undefined;387        return switch (try write.readTreePage(page_id, &scratch)) {388            .leaf => |leaf| try self.putLeaf(write, leaf, page_id, key, value_record, pending),389            .branch => |branch| try self.putBranch(390                write,391                branch,392                page_id,393                key,394                value_record,395                depth,396                pending,397            ),398        };399    }400401    fn putLeaf(402        self: *Tree,403        write: *Write,404        loaded: page.Leaf,405        page_id: u32,406        key: []const u8,407        value_record: []const u8,408        pending: ?*PendingPut,409    ) Error!?Separator {410        var leaf = loaded;411        const image = leaf.bytes;412        const old_record = leaf.get(key);413        try self.applyPutIdentity(write, pending, key, old_record);414        const old_overflow = try overflowRefOrNull(old_record);415        leaf.put(key, value_record) catch |err| switch (err) {416            error.PageFull => {417                const new_child = try write.allocatePage();418                var left_image: [page.size]u8 = undefined;419                var right_image: [page.size]u8 = undefined;420                var left = page.Leaf.init(&left_image, page_id);421                var right = page.Leaf.init(&right_image, new_child);422                const separator = leaf.splitPut(&left, &right, key, value_record) catch |split_err| switch (split_err) {423                    error.PageFull => return error.KeyTooLarge,424                    else => return split_err,425                };426                if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);427                try write.putPage(page_id, &left_image);428                try write.putPage(new_child, &right_image);429                return try Separator.init(separator, new_child);430            },431            else => return err,432        };433        if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);434        try write.putPage(page_id, image);435        return null;436    }437438    fn putBranch(439        self: *Tree,440        write: *Write,441        loaded: page.Branch,442        page_id: u32,443        key: []const u8,444        value_record: []const u8,445        depth: usize,446        pending: ?*PendingPut,447    ) Error!?Separator {448        var branch = loaded;449        const image = branch.bytes;450        const child_id = branch.childFor(key);451        const split = (try self.putNonRoot(write, child_id, key, value_record, depth + 1, pending)) orelse return null;452        branch.put(split.key(), split.child) catch |err| switch (err) {453            error.PageFull => {454                const new_child = try write.allocatePage();455                var left_image: [page.size]u8 = undefined;456                var right_image: [page.size]u8 = undefined;457                var left = page.Branch.init(&left_image, page_id);458                var right = page.Branch.init(&right_image, new_child);459                const separator = branch.splitPut(&left, &right, split.key(), split.child) catch |split_err| switch (split_err) {460                    error.PageFull => return error.KeyTooLarge,461                    else => return split_err,462                };463                try write.putPage(page_id, &left_image);464                try write.putPage(new_child, &right_image);465                return try Separator.init(separator, new_child);466            },467            else => return err,468        };469        try write.putPage(page_id, image);470        return null;471    }472473    fn deleteRootBranch(474        self: *Tree,475        write: *Write,476        loaded: page.Branch,477        key: []const u8,478        scratch: ?*IdentityScratch,479    ) Error!void {480        var branch = loaded;481        const root_image = branch.bytes;482        const child_index = branch.childIndexFor(key);483        const child_id = branch.childAt(child_index);484        const result = try self.deleteNonRoot(write, child_id, key, 1, scratch);485        switch (result) {486            .empty => {487                try branch.remove(child_index);488                try write.releasePage(self.root_page, child_id);489            },490            .lower => |lower| {491                const replacement = if (child_index == 0 and branch.lowerAt(0).len == 0) branch.lowerAt(0) else lower.key();492                try replaceLowerBoundIfFits(&branch, child_index, replacement, child_id);493            },494        }495        if (branch.cellCount() == 0) {496            _ = page.Leaf.init(root_image, self.root_page);497            try write.putPage(self.root_page, root_image);498            return;499        }500        try self.compactRoot(write, root_image, 0);501    }502503    fn deleteNonRoot(self: *Tree, write: *Write, page_id: u32, key: []const u8, depth: usize, scratch: ?*IdentityScratch) Error!DeleteResult {504        if (depth >= max_height) return error.TreeTooDeep;505        var page_scratch: [page.size]u8 = undefined;506        switch (try write.readTreePage(page_id, &page_scratch)) {507            .leaf => |loaded| {508                var leaf = loaded;509                const old_record = leaf.get(key) orelse return error.KeyNotFound;510                try self.applyDeleteIdentity(write, scratch, key, old_record);511                const old_overflow = try overflowRefOrNull(old_record);512                try leaf.delete(key);513                if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);514                if (leaf.cellCount() == 0) return .empty;515                try write.putPage(page_id, leaf.bytes);516                return .{ .lower = try Separator.init(leaf.firstKey() orelse return error.InvalidPage, page_id) };517            },518            .branch => |loaded| {519                var branch = loaded;520                const child_index = branch.childIndexFor(key);521                const child_id = branch.childAt(child_index);522                const result = try self.deleteNonRoot(write, child_id, key, depth + 1, scratch);523                switch (result) {524                    .empty => {525                        try branch.remove(child_index);526                        try write.releasePage(self.root_page, child_id);527                    },528                    .lower => |lower| {529                        const replacement = if (child_index == 0 and branch.lowerAt(0).len == 0) branch.lowerAt(0) else lower.key();530                        try replaceLowerBoundIfFits(&branch, child_index, replacement, child_id);531                    },532                }533                if (branch.cellCount() == 0) return .empty;534                try write.putPage(page_id, branch.bytes);535                return .{ .lower = try Separator.init(branch.firstLower() orelse return error.InvalidPage, page_id) };536            },537        }538    }539540    fn replaceLowerBoundIfFits(branch: *page.Branch, index: usize, lower: []const u8, child: u32) Error!void {541        branch.replace(index, lower, child) catch |err| switch (err) {542            error.PageFull => {},543            else => return err,544        };545    }546547    fn compactRoot(self: *Tree, write: *Write, root_image: *[page.size]u8, depth: usize) Error!void {548        if (depth >= max_height) return error.TreeTooDeep;549        switch (try page.kind(root_image)) {550            .leaf => try write.putPage(self.root_page, root_image),551            .branch => {552                const branch = try page.Branch.load(root_image);553                if (branch.cellCount() == 1) {554                    var child: [page.size]u8 = undefined;555                    const child_id = branch.childAt(0);556                    try write.readExistingPage(child_id, &child);557                    try copyRootPage(root_image, &child, self.root_page);558                    try write.releasePage(self.root_page, child_id);559                    try self.compactRoot(write, root_image, depth + 1);560                    return;561                }562                try write.putPage(self.root_page, root_image);563            },564            .meta => return error.InvalidPage,565            .overflow => return error.InvalidPage,566            .identity => return error.InvalidPage,567        }568    }569570    fn writeValueRecord(self: *Tree, write: *Write, value: []const u8, inline_buffer: *[inline_value_max + 1]u8, overflow_buffer: *[record.overflow_size]u8) Error![]const u8 {571        if (value.len <= inline_value_max) return try record.encodeInline(inline_buffer, value);572        if (value.len > std.math.maxInt(u64)) return error.ValueTooLarge;573        const first_page = try self.writeOverflowValue(write, value);574        return try record.encodeOverflow(overflow_buffer, .{575            .len = @intCast(value.len),576            .first_page = first_page,577        });578    }579580    fn writeOverflowValue(self: *Tree, write: *Write, value: []const u8) Error!u32 {581        _ = self;582        if (value.len == 0) return error.ValueTooLarge;583        var offset: usize = 0;584        const first_page = try write.allocatePage();585        var current_page = first_page;586        while (offset < value.len) {587            const remaining = value.len - offset;588            const chunk_len = @min(page.overflow_capacity, remaining);589            const next_page = if (offset + chunk_len < value.len) try write.allocatePage() else 0;590            var image: [page.size]u8 = undefined;591            _ = try page.Overflow.init(&image, current_page, next_page, value[offset..][0..chunk_len]);592            try write.putPage(current_page, &image);593            current_page = next_page;594            offset += chunk_len;595        }596        return first_page;597    }598599    fn releaseOverflowValue(self: *const Tree, write: *Write, overflow: record.Overflow) Error!void {600        var pages: std.ArrayList(u32) = .empty;601        defer pages.deinit(write.database.allocator);602        try self.collectOverflowPages(write, overflow, &pages);603        for (pages.items) |page_id| try write.releasePage(self.root_page, page_id);604    }605606    fn collectReleasedPages(self: *const Tree, write: *Write, image: *[page.size]u8, depth: usize, pages: *std.ArrayList(u32)) Error!void {607        if (depth >= max_height) return error.TreeTooDeep;608        switch (try page.kind(image)) {609            .leaf => {610                const leaf = try page.Leaf.load(image);611                var leaf_range = try leaf.range(null, null);612                while (leaf_range.next()) |entry| {613                    if (try overflowRefOrNull(entry.value)) |overflow| try self.collectOverflowPages(write, overflow, pages);614                }615            },616            .branch => {617                const branch = try page.Branch.load(image);618                var index: usize = 0;619                while (index < branch.cellCount()) : (index += 1) {620                    const child_id = branch.childAt(index);621                    var child_image: [page.size]u8 = undefined;622                    try write.readExistingPage(child_id, &child_image);623                    try self.collectReleasedPages(write, &child_image, depth + 1, pages);624                    try pages.append(write.database.allocator, child_id);625                }626            },627            .meta => return error.InvalidPage,628            .overflow => return error.InvalidPage,629            .identity => return error.InvalidPage,630        }631    }632633    fn collectOverflowPages(self: *const Tree, write: *Write, overflow: record.Overflow, pages: *std.ArrayList(u32)) Error!void {634        _ = self;635        var remaining = try overflowLengthAsUsize(overflow.len);636        var page_id = overflow.first_page;637        while (page_id != 0) {638            var image: [page.size]u8 = undefined;639            try write.readExistingPage(page_id, &image);640            const overflow_page = try page.Overflow.load(&image);641            const expected = @min(page.overflow_capacity, remaining);642            if (overflow_page.content().len != expected) return error.InvalidPage;643            const next_page = overflow_page.next();644            try pages.append(write.database.allocator, page_id);645            remaining -= expected;646            if (remaining == 0 and next_page != 0) return error.InvalidPage;647            if (remaining > 0 and next_page == 0) return error.InvalidPage;648            page_id = next_page;649        }650        if (remaining != 0) return error.InvalidPage;651    }652};

1pub const Tree = tree.Tree;