tiny.sql.TreeWrite

1pub const Write = struct {2    database: *file.Database,3    meta_page: u32,4    reserved_page_max: u32,5    transaction: file.Transaction,6    read: file.ReadLease,7    snapshot: file.Snapshot,8    allocation: Allocation,9    identities: std.AutoHashMapUnmanaged(u32, IdentityScratch),10    batch_roots: [max_write_batches]u32 = undefined,11    batch_root_count: usize = 0,12    /// Snapshot pages this write validated, by page id modulo the13    /// capacity. The snapshot cannot change during the write, so a page14    /// validated once stays valid, and a collision costs one more15    /// validation.16    validated_pages: [validated_page_capacity]u32 = @splat(0),1718    pub fn begin(database: *file.Database, options: WriteOptions) Error!Write {19        if (options.meta_page == 0) return error.InvalidPageId;20        const reserved_page_max = @max(options.reserved_page_max, options.meta_page);21        var transaction = try database.beginWrite();22        errdefer transaction.deinit();23        var read = try database.beginRead();24        errdefer read.deinit();25        const snapshot = read.snapshot();26        return .{27            .database = database,28            .meta_page = options.meta_page,29            .reserved_page_max = reserved_page_max,30            .transaction = transaction,31            .read = read,32            .snapshot = snapshot,33            .allocation = try Allocation.init(database, snapshot, options.meta_page, reserved_page_max),34            .identities = .empty,35        };36    }3738    pub fn beginTree(tree: *const Tree) Error!Write {39        return try Write.begin(tree.database, .{40            .meta_page = tree.meta_page,41            .reserved_page_max = tree.reserved_page_max,42        });43    }4445    pub fn deinit(self: *Write) void {46        self.identities.deinit(self.database.allocator);47        self.transaction.deinit();48        self.read.deinit();49        self.* = undefined;50    }5152    fn identityScratch(self: *Write, tree: *const Tree) Error!?*IdentityScratch {53        if (tree.identity_page == 0) return null;54        const slot = try self.identities.getOrPut(self.database.allocator, tree.root_page);55        if (!slot.found_existing) {56            slot.value_ptr.* = .{57                .identity_page = tree.identity_page,58                .entries = 0,59                .key_bytes = 0,60                .value_bytes = 0,61                .state = lattice.State.empty,62            };63            var image: [page.size]u8 = undefined;64            if (try self.readPage(tree.identity_page, &image)) {65                if (!zeroPage(&image)) {66                    const loaded = try page.Identity.load(&image);67                    slot.value_ptr.entries = loaded.entries();68                    slot.value_ptr.key_bytes = loaded.keyBytes();69                    slot.value_ptr.value_bytes = loaded.valueBytes();70                    slot.value_ptr.state = loaded.state();71                }72            }73        }74        return slot.value_ptr;75    }7677    pub fn put(self: *Write, tree: *Tree, key: []const u8, value: []const u8) Error!void {78        try self.ensureTree(tree);79        try tree.putInWrite(self, key, value);80    }8182    pub fn delete(self: *Write, tree: *Tree, key: []const u8) Error!void {83        try self.ensureTree(tree);84        try tree.deleteInWrite(self, key);85    }8687    pub fn clear(self: *Write, tree: *Tree) Error!void {88        try self.ensureTree(tree);89        try tree.clearInWrite(self);90    }9192    pub fn claimBatch(self: *Write, root_page: u32) Error!void {93        if (root_page == 0) return error.InvalidPageId;94        for (self.batch_roots[0..self.batch_root_count]) |claimed| {95            if (claimed == root_page) return error.WriteBatchRepeated;96        }97        if (self.batch_root_count == self.batch_roots.len) {98            return error.WriteBatchLimitExceeded;99        }100        self.batch_roots[self.batch_root_count] = root_page;101        self.batch_root_count += 1;102    }103104    pub fn allocateRoot(self: *Write) Error!u32 {105        const phase = trace.scope("tree.write.allocate_root");106        defer phase.end();107        const root_page = try self.allocatePage();108        var image: [page.size]u8 = @splat(0);109        try self.putPage(root_page, &image);110        self.reserved_page_max = @max(self.reserved_page_max, root_page);111        return root_page;112    }113114    fn allocatePage(self: *Write) Error!u32 {115        var meta = try page.Meta.load(&self.allocation.image);116        if (meta.isChained() and meta.freeCount() == 0) return try self.refillFreeList(&meta);117        const page_id = try meta.allocate();118        self.allocation.dirty = true;119        return page_id;120    }121122    fn releasePage(self: *Write, root_page: u32, page_id: u32) Error!void {123        if (page_id == self.meta_page or page_id == root_page) return error.InvalidPageId;124        var meta = try page.Meta.load(&self.allocation.image);125        meta.release(page_id) catch |err| switch (err) {126            error.FreeListFull => {127                try self.spillFreeList(&meta);128                try meta.release(page_id);129            },130            else => return err,131        };132        self.allocation.dirty = true;133    }134135    fn spillFreeList(self: *Write, meta: *page.Meta) Error!void {136        const chain_page = try meta.allocate();137        var entries: [page.meta_chain_page_entries + 1]u32 = undefined;138        const count = try meta.spillEntries(&entries);139        var fragment: [page.meta_chain_page_entries * free_entry_size]u8 = undefined;140        for (entries[0..count], 0..) |entry, index| {141            std.mem.writeInt(u32, fragment[index * free_entry_size ..][0..free_entry_size], entry, .big);142        }143        var image: [page.size]u8 = undefined;144        _ = try page.Overflow.init(&image, chain_page, meta.chainHead(), fragment[0 .. count * free_entry_size]);145        try self.transaction.putPage(chain_page, &image);146        try meta.adoptChain(chain_page);147        self.allocation.dirty = true;148    }149150    fn refillFreeList(self: *Write, meta: *page.Meta) Error!u32 {151        const head = meta.chainHead();152        var image: [page.size]u8 = undefined;153        try self.readExistingPage(head, &image);154        const overflow = try page.Overflow.load(&image);155        const content = overflow.content();156        if (content.len % free_entry_size != 0) return error.InvalidPage;157        const count = content.len / free_entry_size;158        var entries: [page.meta_chain_page_entries]u32 = undefined;159        if (count > entries.len) return error.InvalidPage;160        for (entries[0..count], 0..) |*entry, index| {161            entry.* = std.mem.readInt(u32, content[index * free_entry_size ..][0..free_entry_size], .big);162        }163        try meta.refillFromChain(overflow.next(), entries[0..count]);164        self.allocation.dirty = true;165        return head;166    }167168    pub fn commit(self: *Write, options: file.CommitOptions) Error!file.Commit {169        var identities = self.identities.valueIterator();170        while (identities.next()) |scratch| {171            if (!scratch.dirty) continue;172            var image: [page.size]u8 = undefined;173            var identity = page.Identity.init(&image, scratch.identity_page);174            identity.setEntries(scratch.entries);175            identity.setKeyBytes(scratch.key_bytes);176            identity.setValueBytes(scratch.value_bytes);177            identity.setState(&scratch.state);178            try self.transaction.putPage(scratch.identity_page, &image);179        }180        try self.allocation.write(self.meta_page, &self.transaction);181        return try self.transaction.commit(options);182    }183184    fn ensureTree(self: *const Write, tree: *const Tree) Error!void {185        if (self.database != tree.database) return error.TreeSpaceMismatch;186        if (self.meta_page != tree.meta_page) return error.TreeSpaceMismatch;187        if (self.reserved_page_max < tree.reserved_page_max) return error.TreeSpaceMismatch;188    }189190    fn readRoot(self: *const Write, tree: *const Tree, image: *[page.size]u8) Error!void {191        if (try self.readPage(tree.root_page, image)) {192            if (!zeroPage(image)) return;193        }194        _ = page.Leaf.init(image, tree.root_page);195    }196197    fn readExistingPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!void {198        if (try self.readPage(page_id, image)) return;199        return error.InvalidPage;200    }201202    fn readPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!bool {203        if (try self.transaction.getPage(page_id)) |bytes| {204            image.* = bytes[0..page.size].*;205            return true;206        }207        return try self.snapshot.copyPage(page_id, image);208    }209210    /// Reads a page for editing. A page this write staged comes back as211    /// its staged image, and a snapshot page as a copy in `scratch`.212    fn readPageSource(self: *Write, page_id: u32, scratch: *[page.size]u8) Error!?SourcedPage {213        if (try self.transaction.editPage(page_id)) |staged| {214            return .{ .bytes = staged, .source = .transaction };215        }216        if (try self.snapshot.copyPage(page_id, scratch)) {217            return .{ .bytes = scratch, .source = .snapshot };218        }219        return null;220    }221222    /// Reads the root of `tree` as a leaf or branch. A reserved root that223    /// was never written reads as an empty leaf in `scratch`.224    fn readRootPage(self: *Write, tree: *const Tree, scratch: *[page.size]u8) Error!TreePage {225        const sourced = (try self.readPageSource(tree.root_page, scratch)) orelse226            return .{ .leaf = page.Leaf.init(scratch, tree.root_page) };227        if (zeroPage(sourced.bytes)) return .{ .leaf = page.Leaf.init(scratch, tree.root_page) };228        return try self.treePage(tree.root_page, sourced);229    }230231    /// Reads a leaf or branch named by a branch this write read.232    fn readTreePage(self: *Write, page_id: u32, scratch: *[page.size]u8) Error!TreePage {233        const sourced = (try self.readPageSource(page_id, scratch)) orelse234            return error.InvalidPage;235        return try self.treePage(page_id, sourced);236    }237238    /// Wraps a leaf or branch image, validating its cells unless this write239    /// wrote the page or already validated it in the snapshot. Safety240    /// builds assert that a page skipped that way still validates.241    fn treePage(self: *Write, page_id: u32, sourced: SourcedPage) Error!TreePage {242        std.debug.assert(page_id != 0);243        const slot = &self.validated_pages[page_id % validated_page_capacity];244        if (sourced.source == .transaction or slot.* == page_id) {245            if (std.debug.runtime_safety) std.debug.assert(validTreePage(sourced.bytes));246            return try trustedTreePage(sourced.bytes);247        }248        const loaded = try loadTreePage(sourced.bytes);249        slot.* = page_id;250        return loaded;251    }252253    fn copyPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!bool {254        return try self.readPage(page_id, image);255    }256257    fn putPage(self: *Write, page_id: u32, image: *const [page.size]u8) Error!void {258        try self.transaction.putPage(page_id, image);259    }260};

1pub const TreeWrite = tree.Write;