tiny.sql.tree
Defined in tiny.sql.
API (37)
Actions
Public operations.
Reader.count: Returns how many entries the tree holds in this reader's snapshot, the figure a caller sizes a scan's output by.Reader.digestIdentity: Returns the digest ofidentity_value, an identity this reader read from its identity page, through the snapshot's database memo.Reader.getReader.getIntoReader.identityReader.lastKeyReader.openReader.range: Starts a range over the entries fromstartup toendintarget.Reader.scan: Starts a scan of the keys fromstartup toendintarget, which the scan fills in place.Reader.summarizeReader.valueLengthRootCache.deinitRootCache.findRootCache.storerootFromEntriesrootFromSortedEntries
Types and contracts
Public types and contracts.
ErrorHashNodeNodeKindOptionsProjectionRangeReaderRootRootCacheRootEntryScanScanEntryScanStatsSummaryTreeTreeIdentityWriteWriteOptions
Values and defaults
Public values and defaults.
hash_byteskey_bytes_max: The longest key that a put with an empty value can carry into any tree whose keys are all this short.
Source
Source: lib/sql/src/root.zig:46
zig
pub const tree = @import("tree.zig");Source: lib/sql/src/tree.zig:7
zig
const std = @import("std");const simd = @import("simd");const file = @import("file.zig");const lattice = @import("lattice.zig");const page = @import("page.zig");const record = @import("record.zig");const trace = @import("trace.zig");const wal = @import("wal.zig");const Bytes = simd.ScalableTag(u8);const Allocator = std.mem.Allocator;const io = std.Options.debug_io;pub const Error = file.Error || page.Error || record.Error || error{ OutputTooSmall, TreeTooDeep, TreeSpaceMismatch, TreeIdentityMissing, WriteBatchLimitExceeded, WriteBatchRepeated,};pub const hash_bytes = 32;pub const Hash = [hash_bytes]u8;const max_height: usize = 16;const max_write_batches: usize = 32;const inline_value_max: usize = 1024;/// The longest key that a put with an empty value can carry into any tree/// whose keys are all this short. The leaf cell holds the key beside the/// empty value record, and a split can copy the key into a branch cell/// beside a child page number. Both cells must fit `page.cell_bytes_max`.pub const key_bytes_max: usize = page.cell_bytes_max - page.cellBytes( 0, @max(record.inlineSize(&.{}) catch unreachable, page.child_size),);const Separator = struct { key_bytes: [page.size]u8 = undefined, key_len: usize, child: u32, fn init(lower_key: []const u8, child: u32) Error!Separator { if (lower_key.len > page.size) return error.KeyTooLarge; var separator = Separator{ .key_len = lower_key.len, .child = child, }; @memcpy(separator.key_bytes[0..lower_key.len], lower_key); return separator; } fn key(self: *const Separator) []const u8 { return self.key_bytes[0..self.key_len]; }};const BranchFrame = struct { page_id: u32, index: usize,};const DeleteResult = union(enum) { empty, lower: Separator,};/// A leaf or branch read for a write, with cells validated or known valid./// A page the write staged wraps its staged image, so edits to it are/// staged as they happen.const TreePage = union(enum) { leaf: page.Leaf, branch: page.Branch,};const PageSource = enum { transaction, snapshot };/// A page image a write read for editing, with where it came from.const SourcedPage = struct { bytes: *[page.size]u8, source: PageSource,};/// Snapshot pages a write remembers as validated.const validated_page_capacity = 64;const PageIdSort = struct { fn desc(_: void, left: u32, right: u32) bool { return left > right; }};pub const Projection = enum { key, record, value,};pub const ScanEntry = struct { key: []const u8, bytes: []const u8,};pub const RootEntry = struct { key: []const u8, value: []const u8,};pub const ScanStats = struct { branch_pages_visited: usize = 0, leaf_pages_visited: usize = 0, entries_returned: usize = 0, separator_children_pruned: usize = 0,};pub const Summary = struct { branch_pages: usize = 0, leaf_pages: usize = 0, overflow_pages: usize = 0, entries: usize = 0, inline_records: usize = 0, overflow_records: usize = 0, max_depth: usize = 0, key_bytes: usize = 0, record_bytes: usize = 0, value_bytes: usize = 0,};pub const NodeKind = enum { leaf, branch,};pub const Node = struct { kind: NodeKind, lower: []u8, upper: ?[]u8 = null, depth: usize, summary: Summary, hash: Hash, children_start: usize = 0, children_len: usize = 0,};pub const Root = struct { allocator: Allocator, summary: Summary, hash: Hash, subtree: Hash, nodes: []Node, edges: []usize, pub fn deinit(self: *Root) void { for (self.nodes) |node| { self.allocator.free(node.lower); if (node.upper) |upper| self.allocator.free(upper); } self.allocator.free(self.nodes); self.allocator.free(self.edges); self.* = undefined; } pub fn clone(self: *const Root, allocator: Allocator) Allocator.Error!Root { const nodes = try allocator.alloc(Node, self.nodes.len); var node_count: usize = 0; errdefer { for (nodes[0..node_count]) |node| { allocator.free(node.lower); if (node.upper) |upper| allocator.free(upper); } allocator.free(nodes); } for (self.nodes, nodes) |node, *target| { const lower = try allocator.dupe(u8, node.lower); errdefer allocator.free(lower); const upper = if (node.upper) |bytes| try allocator.dupe(u8, bytes) else null; errdefer if (upper) |bytes| allocator.free(bytes); target.* = .{ .kind = node.kind, .lower = lower, .upper = upper, .depth = node.depth, .summary = node.summary, .hash = node.hash, .children_start = node.children_start, .children_len = node.children_len, }; node_count += 1; } const edges = try allocator.dupe(usize, self.edges); errdefer allocator.free(edges); return .{ .allocator = allocator, .summary = self.summary, .hash = self.hash, .subtree = self.subtree, .nodes = nodes, .edges = edges, }; } pub fn rootNode(self: *const Root) *const Node { return &self.nodes[0]; } pub fn childIndexes(self: *const Root, node: *const Node) []const usize { return self.edges[node.children_start..][0..node.children_len]; } pub fn child(self: *const Root, node: *const Node, index: usize) ?*const Node { if (index >= node.children_len) return null; return &self.nodes[self.edges[node.children_start + index]]; }};pub const RootCache = struct { entries: std.AutoHashMapUnmanaged(u32, CacheEntry) = .empty, const CacheEntry = struct { base_generation: u64, end_mark: usize, root: Root, }; pub fn deinit(self: *RootCache, allocator: Allocator) void { var values = self.entries.valueIterator(); while (values.next()) |entry| entry.root.deinit(); self.entries.deinit(allocator); self.* = undefined; } pub fn find(self: *const RootCache, root_page: u32, base_generation: u64, end_mark: usize) ?*const Root { const entry = self.entries.getPtr(root_page) orelse return null; if (entry.base_generation != base_generation or entry.end_mark != end_mark) return null; return &entry.root; } pub fn store(self: *RootCache, allocator: Allocator, root_page: u32, base_generation: u64, end_mark: usize, root: *const Root) Allocator.Error!void { var cloned = try root.clone(allocator); errdefer cloned.deinit(); const slot = try self.entries.getOrPut(allocator, root_page); if (slot.found_existing) slot.value_ptr.root.deinit(); slot.value_ptr.* = .{ .base_generation = base_generation, .end_mark = end_mark, .root = cloned, }; }};pub fn rootFromEntries(allocator: Allocator, entries: []const RootEntry) Allocator.Error!Root { const sorted = try allocator.dupe(RootEntry, entries); defer allocator.free(sorted); std.mem.sort(RootEntry, sorted, {}, rootEntryLessThan); return try rootFromSortedEntries(allocator, sorted);}pub fn rootFromSortedEntries( allocator: Allocator, entries: []const RootEntry,) Allocator.Error!Root { if (entries.len > 1) { for (entries[0 .. entries.len - 1], entries[1..]) |previous, current| { std.debug.assert(!rootEntryLessThan({}, current, previous)); } } var logical = lattice.State.empty; var leaf = HashBuilder.init("sql.map.leaf"); leaf.writeU64(0); leaf.writeU64(entries.len); var summary = Summary{ .leaf_pages = 1, .max_depth = 0, }; for (entries) |entry| { summary.entries += 1; summary.inline_records += 1; summary.key_bytes += entry.key.len; summary.record_bytes += entry.value.len; summary.value_bytes += entry.value.len; leaf.bytes(entry.key); leaf.bytes(entry.value); const entry_state = lattice.entryState(entry.key, entry.value); logical.add(&entry_state); } const nodes = try allocator.alloc(Node, 1); var node_count: usize = 0; errdefer { for (nodes[0..node_count]) |node| { allocator.free(node.lower); if (node.upper) |upper| allocator.free(upper); } allocator.free(nodes); } const lower = try allocator.dupe(u8, ""); var lower_in_node = false; errdefer if (!lower_in_node) allocator.free(lower); nodes[0] = .{ .kind = .leaf, .lower = lower, .depth = 0, .summary = summary, .hash = leaf.finish(), }; lower_in_node = true; node_count = 1; const edges = try allocator.alloc(usize, 0); errdefer allocator.free(edges); return .{ .allocator = allocator, .summary = summary, .hash = logical.digest(summary.entries), .subtree = nodes[0].hash, .nodes = nodes, .edges = edges, };}const free_entry_size: usize = @sizeOf(u32);const Allocation = struct { image: [page.size]u8, dirty: bool, fn init(database: *const file.Database, snapshot: file.Snapshot, meta_page: u32, reserved_page_max: u32) Error!Allocation { std.debug.assert(meta_page != 0); var loaded = Allocation{ .image = undefined, .dirty = false, }; if (try snapshot.copyPage(meta_page, &loaded.image)) { var meta = try page.Meta.load(&loaded.image); if (try meta.reserveThrough(reserved_page_max)) loaded.dirty = true; return loaded; } const highest_page = @max(database.pager.databasePageCount(), reserved_page_max); var allocation = Allocation{ .image = undefined, .dirty = true, }; _ = page.Meta.init(&allocation.image, meta_page, highest_page); return allocation; } fn write(self: *Allocation, meta_page: u32, transaction: *file.Transaction) Error!void { if (self.dirty) try transaction.putPage(meta_page, &self.image); }};pub const Options = struct { meta_page: u32 = 1, root_page: u32 = 2, identity_page: u32 = 0, reserved_page_max: u32 = 0,};pub const TreeIdentity = struct { state: lattice.State, entries: u64, key_bytes: u64, value_bytes: u64,};const IdentityScratch = struct { identity_page: u32, entries: u64, key_bytes: u64, value_bytes: u64, state: lattice.State, dirty: bool = false,};const OldEntry = struct { state: lattice.State, value_len: u64,};const PendingPut = struct { scratch: *IdentityScratch, fresh: lattice.State, key_len: u64, value_len: u64,};pub const WriteOptions = struct { meta_page: u32 = 1, reserved_page_max: u32 = 0,};pub const Write = struct { database: *file.Database, meta_page: u32, reserved_page_max: u32, transaction: file.Transaction, read: file.ReadLease, snapshot: file.Snapshot, allocation: Allocation, identities: std.AutoHashMapUnmanaged(u32, IdentityScratch), batch_roots: [max_write_batches]u32 = undefined, batch_root_count: usize = 0, /// Snapshot pages this write validated, by page id modulo the /// capacity. The snapshot cannot change during the write, so a page /// validated once stays valid, and a collision costs one more /// validation. validated_pages: [validated_page_capacity]u32 = @splat(0), pub fn begin(database: *file.Database, options: WriteOptions) Error!Write { if (options.meta_page == 0) return error.InvalidPageId; const reserved_page_max = @max(options.reserved_page_max, options.meta_page); var transaction = try database.beginWrite(); errdefer transaction.deinit(); var read = try database.beginRead(); errdefer read.deinit(); const snapshot = read.snapshot(); return .{ .database = database, .meta_page = options.meta_page, .reserved_page_max = reserved_page_max, .transaction = transaction, .read = read, .snapshot = snapshot, .allocation = try Allocation.init(database, snapshot, options.meta_page, reserved_page_max), .identities = .empty, }; } pub fn beginTree(tree: *const Tree) Error!Write { return try Write.begin(tree.database, .{ .meta_page = tree.meta_page, .reserved_page_max = tree.reserved_page_max, }); } pub fn deinit(self: *Write) void { self.identities.deinit(self.database.allocator); self.transaction.deinit(); self.read.deinit(); self.* = undefined; } fn identityScratch(self: *Write, tree: *const Tree) Error!?*IdentityScratch { if (tree.identity_page == 0) return null; const slot = try self.identities.getOrPut(self.database.allocator, tree.root_page); if (!slot.found_existing) { slot.value_ptr.* = .{ .identity_page = tree.identity_page, .entries = 0, .key_bytes = 0, .value_bytes = 0, .state = lattice.State.empty, }; var image: [page.size]u8 = undefined; if (try self.readPage(tree.identity_page, &image)) { if (!zeroPage(&image)) { const loaded = try page.Identity.load(&image); slot.value_ptr.entries = loaded.entries(); slot.value_ptr.key_bytes = loaded.keyBytes(); slot.value_ptr.value_bytes = loaded.valueBytes(); slot.value_ptr.state = loaded.state(); } } } return slot.value_ptr; } pub fn put(self: *Write, tree: *Tree, key: []const u8, value: []const u8) Error!void { try self.ensureTree(tree); try tree.putInWrite(self, key, value); } pub fn delete(self: *Write, tree: *Tree, key: []const u8) Error!void { try self.ensureTree(tree); try tree.deleteInWrite(self, key); } pub fn clear(self: *Write, tree: *Tree) Error!void { try self.ensureTree(tree); try tree.clearInWrite(self); } pub fn claimBatch(self: *Write, root_page: u32) Error!void { if (root_page == 0) return error.InvalidPageId; for (self.batch_roots[0..self.batch_root_count]) |claimed| { if (claimed == root_page) return error.WriteBatchRepeated; } if (self.batch_root_count == self.batch_roots.len) { return error.WriteBatchLimitExceeded; } self.batch_roots[self.batch_root_count] = root_page; self.batch_root_count += 1; } pub fn allocateRoot(self: *Write) Error!u32 { const phase = trace.scope("tree.write.allocate_root"); defer phase.end(); const root_page = try self.allocatePage(); var image: [page.size]u8 = @splat(0); try self.putPage(root_page, &image); self.reserved_page_max = @max(self.reserved_page_max, root_page); return root_page; } fn allocatePage(self: *Write) Error!u32 { var meta = try page.Meta.load(&self.allocation.image); if (meta.isChained() and meta.freeCount() == 0) return try self.refillFreeList(&meta); const page_id = try meta.allocate(); self.allocation.dirty = true; return page_id; } fn releasePage(self: *Write, root_page: u32, page_id: u32) Error!void { if (page_id == self.meta_page or page_id == root_page) return error.InvalidPageId; var meta = try page.Meta.load(&self.allocation.image); meta.release(page_id) catch |err| switch (err) { error.FreeListFull => { try self.spillFreeList(&meta); try meta.release(page_id); }, else => return err, }; self.allocation.dirty = true; } fn spillFreeList(self: *Write, meta: *page.Meta) Error!void { const chain_page = try meta.allocate(); var entries: [page.meta_chain_page_entries + 1]u32 = undefined; const count = try meta.spillEntries(&entries); var fragment: [page.meta_chain_page_entries * free_entry_size]u8 = undefined; for (entries[0..count], 0..) |entry, index| { std.mem.writeInt(u32, fragment[index * free_entry_size ..][0..free_entry_size], entry, .big); } var image: [page.size]u8 = undefined; _ = try page.Overflow.init(&image, chain_page, meta.chainHead(), fragment[0 .. count * free_entry_size]); try self.transaction.putPage(chain_page, &image); try meta.adoptChain(chain_page); self.allocation.dirty = true; } fn refillFreeList(self: *Write, meta: *page.Meta) Error!u32 { const head = meta.chainHead(); var image: [page.size]u8 = undefined; try self.readExistingPage(head, &image); const overflow = try page.Overflow.load(&image); const content = overflow.content(); if (content.len % free_entry_size != 0) return error.InvalidPage; const count = content.len / free_entry_size; var entries: [page.meta_chain_page_entries]u32 = undefined; if (count > entries.len) return error.InvalidPage; for (entries[0..count], 0..) |*entry, index| { entry.* = std.mem.readInt(u32, content[index * free_entry_size ..][0..free_entry_size], .big); } try meta.refillFromChain(overflow.next(), entries[0..count]); self.allocation.dirty = true; return head; } pub fn commit(self: *Write, options: file.CommitOptions) Error!file.Commit { var identities = self.identities.valueIterator(); while (identities.next()) |scratch| { if (!scratch.dirty) continue; var image: [page.size]u8 = undefined; var identity = page.Identity.init(&image, scratch.identity_page); identity.setEntries(scratch.entries); identity.setKeyBytes(scratch.key_bytes); identity.setValueBytes(scratch.value_bytes); identity.setState(&scratch.state); try self.transaction.putPage(scratch.identity_page, &image); } try self.allocation.write(self.meta_page, &self.transaction); return try self.transaction.commit(options); } fn ensureTree(self: *const Write, tree: *const Tree) Error!void { if (self.database != tree.database) return error.TreeSpaceMismatch; if (self.meta_page != tree.meta_page) return error.TreeSpaceMismatch; if (self.reserved_page_max < tree.reserved_page_max) return error.TreeSpaceMismatch; } fn readRoot(self: *const Write, tree: *const Tree, image: *[page.size]u8) Error!void { if (try self.readPage(tree.root_page, image)) { if (!zeroPage(image)) return; } _ = page.Leaf.init(image, tree.root_page); } fn readExistingPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!void { if (try self.readPage(page_id, image)) return; return error.InvalidPage; } fn readPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!bool { if (try self.transaction.getPage(page_id)) |bytes| { image.* = bytes[0..page.size].*; return true; } return try self.snapshot.copyPage(page_id, image); } /// Reads a page for editing. A page this write staged comes back as /// its staged image, and a snapshot page as a copy in `scratch`. fn readPageSource(self: *Write, page_id: u32, scratch: *[page.size]u8) Error!?SourcedPage { if (try self.transaction.editPage(page_id)) |staged| { return .{ .bytes = staged, .source = .transaction }; } if (try self.snapshot.copyPage(page_id, scratch)) { return .{ .bytes = scratch, .source = .snapshot }; } return null; } /// Reads the root of `tree` as a leaf or branch. A reserved root that /// was never written reads as an empty leaf in `scratch`. fn readRootPage(self: *Write, tree: *const Tree, scratch: *[page.size]u8) Error!TreePage { const sourced = (try self.readPageSource(tree.root_page, scratch)) orelse return .{ .leaf = page.Leaf.init(scratch, tree.root_page) }; if (zeroPage(sourced.bytes)) return .{ .leaf = page.Leaf.init(scratch, tree.root_page) }; return try self.treePage(tree.root_page, sourced); } /// Reads a leaf or branch named by a branch this write read. fn readTreePage(self: *Write, page_id: u32, scratch: *[page.size]u8) Error!TreePage { const sourced = (try self.readPageSource(page_id, scratch)) orelse return error.InvalidPage; return try self.treePage(page_id, sourced); } /// Wraps a leaf or branch image, validating its cells unless this write /// wrote the page or already validated it in the snapshot. Safety /// builds assert that a page skipped that way still validates. fn treePage(self: *Write, page_id: u32, sourced: SourcedPage) Error!TreePage { std.debug.assert(page_id != 0); const slot = &self.validated_pages[page_id % validated_page_capacity]; if (sourced.source == .transaction or slot.* == page_id) { if (std.debug.runtime_safety) std.debug.assert(validTreePage(sourced.bytes)); return try trustedTreePage(sourced.bytes); } const loaded = try loadTreePage(sourced.bytes); slot.* = page_id; return loaded; } fn copyPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!bool { return try self.readPage(page_id, image); } fn putPage(self: *Write, page_id: u32, image: *const [page.size]u8) Error!void { try self.transaction.putPage(page_id, image); }};fn validateOptions(options: Options) Error!u32 { if (options.meta_page == 0) return error.InvalidPageId; if (options.root_page == 0) return error.InvalidPageId; if (options.meta_page == options.root_page) return error.InvalidPageId; if (options.identity_page != 0) { if (options.identity_page == options.meta_page) return error.InvalidPageId; if (options.identity_page == options.root_page) return error.InvalidPageId; } return @max( @max(options.reserved_page_max, options.identity_page), @max(options.meta_page, options.root_page), );}/// Copies the root page into `image` and returns the mark of the image it/// copied. A root that was never written reads as an empty leaf with no mark.fn readRoot(snapshot: file.Snapshot, root_page: u32, image: *[page.size]u8) Error!file.PageMark { if (try snapshot.copyMarkedPage(root_page, image)) |mark| { if (!zeroPage(image)) return mark; } _ = page.Leaf.init(image, root_page); return .none;}/// Reads the leaf that holds `key` into `image`, reading each page on the way/// down into that one buffer, and returns it loaded.fn readLeafFor( snapshot: file.Snapshot, root_page: u32, key: []const u8, image: *[page.size]u8,) Error!page.Leaf { var mark = try readRoot(snapshot, root_page, image); var depth: usize = 0; while (depth < max_height) : (depth += 1) { switch (try loadMarkedTreePage(image, mark)) { .leaf => |leaf| return leaf, .branch => |branch| mark = try readMarkedPage(snapshot, branch.childFor(key), image), } } return error.TreeTooDeep;}fn readValueRecord( allocator: Allocator, snapshot: file.Snapshot, bytes: []const u8,) Error![]u8 { const value = try allocator.alloc(u8, try valueRecordLength(bytes)); errdefer allocator.free(value); return try readValueRecordInto(snapshot, bytes, value);}pub const Reader = struct { snapshot: file.Snapshot, meta_page: u32, root_page: u32, identity_page: u32, reserved_page_max: u32, pub fn open(snapshot: file.Snapshot, options: Options) Error!Reader { return .{ .snapshot = snapshot, .meta_page = options.meta_page, .root_page = options.root_page, .identity_page = options.identity_page, .reserved_page_max = try validateOptions(options), }; } pub fn identity(self: *const Reader) Error!TreeIdentity { const phase = trace.scope("tree.identity"); defer phase.end(); if (self.identity_page == 0) return error.TreeIdentityMissing; var image: [page.size]u8 = undefined; if (try self.snapshot.copyPage(self.identity_page, &image)) { if (!zeroPage(&image)) { const loaded = try page.Identity.load(&image); return .{ .state = loaded.state(), .entries = loaded.entries(), .key_bytes = loaded.keyBytes(), .value_bytes = loaded.valueBytes(), }; } } return .{ .state = lattice.State.empty, .entries = 0, .key_bytes = 0, .value_bytes = 0, }; } /// Returns the digest of `identity_value`, an identity this reader read /// from its identity page, through the snapshot's database memo. pub fn digestIdentity( self: *const Reader, identity_value: *const TreeIdentity, ) [lattice.digest_size]u8 { return self.snapshot.digestIdentity( self.identity_page, &identity_value.state, identity_value.entries, ); } /// Returns how many entries the tree holds in this reader's snapshot, the /// figure a caller sizes a scan's output by. A tree with an identity page /// reads the count its write path keeps there, in one page read. A tree /// without one counts the entries of a key-only scan, which reads each /// branch and leaf page once and no overflow page. pub fn count(self: *const Reader) Error!usize { const phase = trace.scope("tree.count"); defer phase.end(); if (self.identity_page != 0) { return std.math.cast(usize, (try self.identity()).entries) orelse error.ValueTooLarge; } var keys: Scan = undefined; try self.scan(&keys, Allocator.failing, null, null, .key); defer keys.deinit(); var entries: usize = 0; while (try keys.next()) |_| entries += 1; return entries; } pub fn get(self: *const Reader, allocator: Allocator, key: []const u8) Error!?[]u8 { const phase = trace.scope("tree.get"); defer phase.end(); var image: [page.size]u8 = undefined; const leaf = try readLeafFor(self.snapshot, self.root_page, key, &image); const value_record = leaf.get(key) orelse return null; return try readValueRecord(allocator, self.snapshot, value_record); } pub fn valueLength(self: *const Reader, key: []const u8) Error!?usize { const phase = trace.scope("tree.value_length"); defer phase.end(); var image: [page.size]u8 = undefined; const leaf = try readLeafFor(self.snapshot, self.root_page, key, &image); const value_record = leaf.get(key) orelse return null; return try valueRecordLength(value_record); } pub fn getInto(self: *const Reader, key: []const u8, target: []u8) Error!?[]u8 { const phase = trace.scope("tree.get_into"); defer phase.end(); var image: [page.size]u8 = undefined; const leaf = try readLeafFor(self.snapshot, self.root_page, key, &image); const value_record = leaf.get(key) orelse return null; return try readValueRecordInto(self.snapshot, value_record, target); } pub fn lastKey(self: *const Reader, buffer: []u8) Error!?[]const u8 { const phase = trace.scope("tree.last_key"); defer phase.end(); var image: [page.size]u8 = undefined; var mark = try readRoot(self.snapshot, self.root_page, &image); var depth: usize = 0; while (depth < max_height) : (depth += 1) { switch (try loadMarkedTreePage(&image, mark)) { .leaf => |leaf| { const last = leaf.lastKey() orelse return null; if (last.len > buffer.len) return error.KeyTooLarge; @memcpy(buffer[0..last.len], last); return buffer[0..last.len]; }, .branch => |branch| { const cells = branch.cellCount(); if (cells == 0) return error.InvalidPage; mark = try readMarkedPage(self.snapshot, branch.childAt(cells - 1), &image); }, } } return error.TreeTooDeep; } /// Starts a range over the entries from `start` up to `end` in `target`. pub fn range( self: *const Reader, target: *Range, allocator: Allocator, start: ?[]const u8, end: ?[]const u8, ) Error!void { const phase = trace.scope("tree.range"); defer phase.end(); try self.scan(&target.scan, allocator, start, end, .value); } /// Starts a scan of the keys from `start` up to `end` in `target`, which /// the scan fills in place. pub fn scan( self: *const Reader, target: *Scan, allocator: Allocator, start: ?[]const u8, end: ?[]const u8, projection: Projection, ) Error!void { const phase = trace.scope("tree.scan"); defer phase.end(); try target.init( allocator, self.snapshot, self.root_page, start, end, projection, ); } pub fn summarize(self: *const Reader) Error!Summary { const phase = trace.scope("tree.summarize"); defer phase.end(); var root_image: [page.size]u8 = undefined; _ = try readRoot(self.snapshot, self.root_page, &root_image); var summary = Summary{}; try summarizePage(self.snapshot, &root_image, 0, &summary); return summary; }};pub const Tree = struct { database: *file.Database, meta_page: u32, root_page: u32, identity_page: u32, reserved_page_max: u32, pub fn open(database: *file.Database, options: Options) Error!Tree { const reserved_page_max = try validateOptions(options); return .{ .database = database, .meta_page = options.meta_page, .root_page = options.root_page, .identity_page = options.identity_page, .reserved_page_max = reserved_page_max, }; } pub fn reader(self: *const Tree, snapshot: file.Snapshot) Error!Reader { return .{ .snapshot = snapshot, .meta_page = self.meta_page, .root_page = self.root_page, .identity_page = self.identity_page, .reserved_page_max = self.reserved_page_max, }; } pub fn identity(self: *const Tree) Error!TreeIdentity { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); return try opened.identity(); } /// Returns the digest of `identity_value`, an identity this tree read /// from its identity page, through its database's memo. pub fn digestIdentity( self: *const Tree, identity_value: *const TreeIdentity, ) [lattice.digest_size]u8 { return self.database.digest_memo.digest( self.identity_page, &identity_value.state, identity_value.entries, ); } pub fn get(self: *const Tree, allocator: Allocator, key: []const u8) Error!?[]u8 { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); return try opened.get(allocator, key); } pub fn valueLength(self: *const Tree, key: []const u8) Error!?usize { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); return try opened.valueLength(key); } pub fn getInto(self: *const Tree, key: []const u8, target: []u8) Error!?[]u8 { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); return try opened.getInto(key, target); } pub fn lastKey(self: *const Tree, buffer: []u8) Error!?[]const u8 { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); return try opened.lastKey(buffer); } pub fn put(self: *Tree, key: []const u8, value: []const u8, options: file.CommitOptions) Error!file.Commit { const phase = trace.scope("tree.put"); defer phase.end(); var write = try Write.beginTree(self); defer write.deinit(); try write.put(self, key, value); return try write.commit(options); } fn putInWrite(self: *Tree, write: *Write, key: []const u8, value: []const u8) Error!void { var pending_storage: PendingPut = undefined; var pending: ?*PendingPut = null; if (try write.identityScratch(self)) |scratch| { var hasher = lattice.EntryHasher.init(key); hasher.update(value); pending_storage = .{ .scratch = scratch, .fresh = hasher.finish(), .key_len = key.len, .value_len = value.len, }; pending = &pending_storage; } var inline_buffer: [inline_value_max + 1]u8 = undefined; var overflow_buffer: [record.overflow_size]u8 = undefined; const value_record = try self.writeValueRecord(write, value, &inline_buffer, &overflow_buffer); var root_scratch: [page.size]u8 = undefined; switch (try write.readRootPage(self, &root_scratch)) { .leaf => |leaf| try self.putRootLeaf(write, leaf, key, value_record, pending), .branch => |branch| try self.putRootBranch(write, branch, key, value_record, pending), } } fn applyPutIdentity(self: *const Tree, write: *Write, pending: ?*PendingPut, key: []const u8, old_record: ?[]const u8) Error!void { const pending_put = pending orelse return; if (old_record) |encoded| { const old = try self.entryStateFromRecord(write, key, encoded); pending_put.scratch.state.subtract(&old.state); pending_put.scratch.value_bytes -= old.value_len; } else { pending_put.scratch.entries += 1; pending_put.scratch.key_bytes += pending_put.key_len; } pending_put.scratch.value_bytes += pending_put.value_len; pending_put.scratch.state.add(&pending_put.fresh); pending_put.scratch.dirty = true; } fn applyDeleteIdentity(self: *const Tree, write: *Write, scratch: ?*IdentityScratch, key: []const u8, old_record: []const u8) Error!void { const identity_scratch = scratch orelse return; const old = try self.entryStateFromRecord(write, key, old_record); identity_scratch.state.subtract(&old.state); identity_scratch.entries -= 1; identity_scratch.key_bytes -= key.len; identity_scratch.value_bytes -= old.value_len; identity_scratch.dirty = true; } fn entryStateFromRecord(self: *const Tree, write: *Write, key: []const u8, value_record: []const u8) Error!OldEntry { _ = self; var hasher = lattice.EntryHasher.init(key); var value_len: u64 = 0; switch (try record.kind(value_record)) { .inline_value => { const inline_value = try record.inlineValue(value_record); value_len = inline_value.len; hasher.update(inline_value); }, .overflow => { const overflow = try record.overflow(value_record); value_len = overflow.len; var remaining = try overflowLengthAsUsize(overflow.len); var page_id = overflow.first_page; while (page_id != 0) { var image: [page.size]u8 = undefined; try write.readExistingPage(page_id, &image); const overflow_page = try page.Overflow.load(&image); const expected = @min(page.overflow_capacity, remaining); if (overflow_page.content().len != expected) return error.InvalidPage; hasher.update(overflow_page.content()); const next_page = overflow_page.next(); remaining -= expected; if (remaining == 0 and next_page != 0) return error.InvalidPage; if (remaining > 0 and next_page == 0) return error.InvalidPage; page_id = next_page; } if (remaining != 0) return error.InvalidPage; }, } return .{ .state = hasher.finish(), .value_len = value_len }; } pub fn delete(self: *Tree, key: []const u8, options: file.CommitOptions) Error!file.Commit { const phase = trace.scope("tree.delete"); defer phase.end(); var write = try Write.beginTree(self); defer write.deinit(); try write.delete(self, key); return try write.commit(options); } fn deleteInWrite(self: *Tree, write: *Write, key: []const u8) Error!void { const scratch = try write.identityScratch(self); var root_scratch: [page.size]u8 = undefined; switch (try write.readRootPage(self, &root_scratch)) { .leaf => |loaded| { var leaf = loaded; const old_record = leaf.get(key) orelse return error.KeyNotFound; try self.applyDeleteIdentity(write, scratch, key, old_record); const old_overflow = try overflowRefOrNull(old_record); try leaf.delete(key); if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow); try write.putPage(self.root_page, leaf.bytes); }, .branch => |branch| try self.deleteRootBranch(write, branch, key, scratch), } } pub fn clear(self: *Tree, options: file.CommitOptions) Error!file.Commit { const phase = trace.scope("tree.clear"); defer phase.end(); var write = try Write.beginTree(self); defer write.deinit(); try write.clear(self); return try write.commit(options); } fn clearInWrite(self: *Tree, write: *Write) Error!void { var root_image: [page.size]u8 = undefined; try write.readRoot(self, &root_image); var pages: std.ArrayList(u32) = .empty; defer pages.deinit(write.database.allocator); try self.collectReleasedPages(write, &root_image, 0, &pages); std.mem.sort(u32, pages.items, {}, PageIdSort.desc); for (pages.items) |page_id| try write.releasePage(self.root_page, page_id); _ = page.Leaf.init(&root_image, self.root_page); try write.putPage(self.root_page, &root_image); if (try write.identityScratch(self)) |scratch| { scratch.state = lattice.State.empty; scratch.entries = 0; scratch.key_bytes = 0; scratch.value_bytes = 0; scratch.dirty = true; } } pub fn range( self: *const Tree, target: *Range, allocator: Allocator, start: ?[]const u8, end: ?[]const u8, ) Error!void { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); try opened.range(target, allocator, start, end); } pub fn scan( self: *const Tree, target: *Scan, allocator: Allocator, start: ?[]const u8, end: ?[]const u8, projection: Projection, ) Error!void { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); try opened.scan(target, allocator, start, end, projection); } pub fn summarize(self: *const Tree) Error!Summary { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); return try opened.summarize(); } pub fn count(self: *const Tree) Error!usize { var read = try self.database.beginRead(); defer read.deinit(); const opened = try self.reader(read.snapshot()); return try opened.count(); } pub fn summarizeIn(self: *const Tree, write: *const Write) Error!Summary { const phase = trace.scope("tree.summarize_in"); defer phase.end(); try write.ensureTree(self); var root_image: [page.size]u8 = undefined; try write.readRoot(self, &root_image); var summary = Summary{}; try summarizePage(write, &root_image, 0, &summary); return summary; } pub fn root(self: *const Tree, allocator: Allocator) Error!Root { const phase = trace.scope("tree.root"); defer phase.end(); var read = try self.database.beginRead(); defer read.deinit(); const snapshot = read.snapshot(); if (self.database.tree_roots.find(self.root_page, snapshot.view.base_generation, snapshot.view.end_mark)) |cached| { return try cached.clone(allocator); } var root_image: [page.size]u8 = undefined; _ = try readRoot(snapshot, self.root_page, &root_image); var build = RootBuild.init(allocator); errdefer build.deinit(); _ = try build.appendNode(snapshot, &root_image, &.{}, null, 0); const built = try build.finish(); self.database.tree_roots.store( self.database.allocator, self.root_page, snapshot.view.base_generation, snapshot.view.end_mark, &built, ) catch {}; return built; } fn putRootLeaf( self: *Tree, write: *Write, loaded: page.Leaf, key: []const u8, value_record: []const u8, pending: ?*PendingPut, ) Error!void { var leaf = loaded; const root_image = leaf.bytes; const old_record = leaf.get(key); try self.applyPutIdentity(write, pending, key, old_record); const old_overflow = try overflowRefOrNull(old_record); leaf.put(key, value_record) catch |err| switch (err) { error.PageFull => { const first_child = try write.allocatePage(); const second_child = try write.allocatePage(); var left_image: [page.size]u8 = undefined; var right_image: [page.size]u8 = undefined; var left = page.Leaf.init(&left_image, first_child); var right = page.Leaf.init(&right_image, second_child); const separator = leaf.splitPut(&left, &right, key, value_record) catch |split_err| switch (split_err) { error.PageFull => return error.KeyTooLarge, else => return split_err, }; var branch = page.Branch.init(root_image, self.root_page); try branch.put(&.{}, first_child); try branch.put(separator, second_child); if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow); try write.putPage(self.root_page, root_image); try write.putPage(first_child, &left_image); try write.putPage(second_child, &right_image); return; }, else => return err, }; if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow); try write.putPage(self.root_page, root_image); } fn putRootBranch( self: *Tree, write: *Write, loaded: page.Branch, key: []const u8, value_record: []const u8, pending: ?*PendingPut, ) Error!void { var branch = loaded; const root_image = branch.bytes; const child_id = branch.childFor(key); const split = (try self.putNonRoot(write, child_id, key, value_record, 1, pending)) orelse return; branch.put(split.key(), split.child) catch |err| switch (err) { error.PageFull => { const left_child = try write.allocatePage(); const right_child = try write.allocatePage(); var left_image: [page.size]u8 = undefined; var right_image: [page.size]u8 = undefined; var left = page.Branch.init(&left_image, left_child); var right = page.Branch.init(&right_image, right_child); const separator = branch.splitPut(&left, &right, split.key(), split.child) catch |split_err| switch (split_err) { error.PageFull => return error.KeyTooLarge, else => return split_err, }; const left_lower = left.firstLower() orelse return error.InvalidPage; var new_root = page.Branch.init(root_image, self.root_page); try new_root.put(left_lower, left_child); try new_root.put(separator, right_child); try write.putPage(self.root_page, root_image); try write.putPage(left_child, &left_image); try write.putPage(right_child, &right_image); return; }, else => return err, }; try write.putPage(self.root_page, root_image); } fn putNonRoot(self: *Tree, write: *Write, page_id: u32, key: []const u8, value_record: []const u8, depth: usize, pending: ?*PendingPut) Error!?Separator { if (depth >= max_height) return error.TreeTooDeep; var scratch: [page.size]u8 = undefined; return switch (try write.readTreePage(page_id, &scratch)) { .leaf => |leaf| try self.putLeaf(write, leaf, page_id, key, value_record, pending), .branch => |branch| try self.putBranch( write, branch, page_id, key, value_record, depth, pending, ), }; } fn putLeaf( self: *Tree, write: *Write, loaded: page.Leaf, page_id: u32, key: []const u8, value_record: []const u8, pending: ?*PendingPut, ) Error!?Separator { var leaf = loaded; const image = leaf.bytes; const old_record = leaf.get(key); try self.applyPutIdentity(write, pending, key, old_record); const old_overflow = try overflowRefOrNull(old_record); leaf.put(key, value_record) catch |err| switch (err) { error.PageFull => { const new_child = try write.allocatePage(); var left_image: [page.size]u8 = undefined; var right_image: [page.size]u8 = undefined; var left = page.Leaf.init(&left_image, page_id); var right = page.Leaf.init(&right_image, new_child); const separator = leaf.splitPut(&left, &right, key, value_record) catch |split_err| switch (split_err) { error.PageFull => return error.KeyTooLarge, else => return split_err, }; if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow); try write.putPage(page_id, &left_image); try write.putPage(new_child, &right_image); return try Separator.init(separator, new_child); }, else => return err, }; if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow); try write.putPage(page_id, image); return null; } fn putBranch( self: *Tree, write: *Write, loaded: page.Branch, page_id: u32, key: []const u8, value_record: []const u8, depth: usize, pending: ?*PendingPut, ) Error!?Separator { var branch = loaded; const image = branch.bytes; const child_id = branch.childFor(key); const split = (try self.putNonRoot(write, child_id, key, value_record, depth + 1, pending)) orelse return null; branch.put(split.key(), split.child) catch |err| switch (err) { error.PageFull => { const new_child = try write.allocatePage(); var left_image: [page.size]u8 = undefined; var right_image: [page.size]u8 = undefined; var left = page.Branch.init(&left_image, page_id); var right = page.Branch.init(&right_image, new_child); const separator = branch.splitPut(&left, &right, split.key(), split.child) catch |split_err| switch (split_err) { error.PageFull => return error.KeyTooLarge, else => return split_err, }; try write.putPage(page_id, &left_image); try write.putPage(new_child, &right_image); return try Separator.init(separator, new_child); }, else => return err, }; try write.putPage(page_id, image); return null; } fn deleteRootBranch( self: *Tree, write: *Write, loaded: page.Branch, key: []const u8, scratch: ?*IdentityScratch, ) Error!void { var branch = loaded; const root_image = branch.bytes; const child_index = branch.childIndexFor(key); const child_id = branch.childAt(child_index); const result = try self.deleteNonRoot(write, child_id, key, 1, scratch); switch (result) { .empty => { try branch.remove(child_index); try write.releasePage(self.root_page, child_id); }, .lower => |lower| { const replacement = if (child_index == 0 and branch.lowerAt(0).len == 0) branch.lowerAt(0) else lower.key(); try replaceLowerBoundIfFits(&branch, child_index, replacement, child_id); }, } if (branch.cellCount() == 0) { _ = page.Leaf.init(root_image, self.root_page); try write.putPage(self.root_page, root_image); return; } try self.compactRoot(write, root_image, 0); } fn deleteNonRoot(self: *Tree, write: *Write, page_id: u32, key: []const u8, depth: usize, scratch: ?*IdentityScratch) Error!DeleteResult { if (depth >= max_height) return error.TreeTooDeep; var page_scratch: [page.size]u8 = undefined; switch (try write.readTreePage(page_id, &page_scratch)) { .leaf => |loaded| { var leaf = loaded; const old_record = leaf.get(key) orelse return error.KeyNotFound; try self.applyDeleteIdentity(write, scratch, key, old_record); const old_overflow = try overflowRefOrNull(old_record); try leaf.delete(key); if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow); if (leaf.cellCount() == 0) return .empty; try write.putPage(page_id, leaf.bytes); return .{ .lower = try Separator.init(leaf.firstKey() orelse return error.InvalidPage, page_id) }; }, .branch => |loaded| { var branch = loaded; const child_index = branch.childIndexFor(key); const child_id = branch.childAt(child_index); const result = try self.deleteNonRoot(write, child_id, key, depth + 1, scratch); switch (result) { .empty => { try branch.remove(child_index); try write.releasePage(self.root_page, child_id); }, .lower => |lower| { const replacement = if (child_index == 0 and branch.lowerAt(0).len == 0) branch.lowerAt(0) else lower.key(); try replaceLowerBoundIfFits(&branch, child_index, replacement, child_id); }, } if (branch.cellCount() == 0) return .empty; try write.putPage(page_id, branch.bytes); return .{ .lower = try Separator.init(branch.firstLower() orelse return error.InvalidPage, page_id) }; }, } } fn replaceLowerBoundIfFits(branch: *page.Branch, index: usize, lower: []const u8, child: u32) Error!void { branch.replace(index, lower, child) catch |err| switch (err) { error.PageFull => {}, else => return err, }; } fn compactRoot(self: *Tree, write: *Write, root_image: *[page.size]u8, depth: usize) Error!void { if (depth >= max_height) return error.TreeTooDeep; switch (try page.kind(root_image)) { .leaf => try write.putPage(self.root_page, root_image), .branch => { const branch = try page.Branch.load(root_image); if (branch.cellCount() == 1) { var child: [page.size]u8 = undefined; const child_id = branch.childAt(0); try write.readExistingPage(child_id, &child); try copyRootPage(root_image, &child, self.root_page); try write.releasePage(self.root_page, child_id); try self.compactRoot(write, root_image, depth + 1); return; } try write.putPage(self.root_page, root_image); }, .meta => return error.InvalidPage, .overflow => return error.InvalidPage, .identity => return error.InvalidPage, } } 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 { if (value.len <= inline_value_max) return try record.encodeInline(inline_buffer, value); if (value.len > std.math.maxInt(u64)) return error.ValueTooLarge; const first_page = try self.writeOverflowValue(write, value); return try record.encodeOverflow(overflow_buffer, .{ .len = @intCast(value.len), .first_page = first_page, }); } fn writeOverflowValue(self: *Tree, write: *Write, value: []const u8) Error!u32 { _ = self; if (value.len == 0) return error.ValueTooLarge; var offset: usize = 0; const first_page = try write.allocatePage(); var current_page = first_page; while (offset < value.len) { const remaining = value.len - offset; const chunk_len = @min(page.overflow_capacity, remaining); const next_page = if (offset + chunk_len < value.len) try write.allocatePage() else 0; var image: [page.size]u8 = undefined; _ = try page.Overflow.init(&image, current_page, next_page, value[offset..][0..chunk_len]); try write.putPage(current_page, &image); current_page = next_page; offset += chunk_len; } return first_page; } fn releaseOverflowValue(self: *const Tree, write: *Write, overflow: record.Overflow) Error!void { var pages: std.ArrayList(u32) = .empty; defer pages.deinit(write.database.allocator); try self.collectOverflowPages(write, overflow, &pages); for (pages.items) |page_id| try write.releasePage(self.root_page, page_id); } fn collectReleasedPages(self: *const Tree, write: *Write, image: *[page.size]u8, depth: usize, pages: *std.ArrayList(u32)) Error!void { if (depth >= max_height) return error.TreeTooDeep; switch (try page.kind(image)) { .leaf => { const leaf = try page.Leaf.load(image); var leaf_range = try leaf.range(null, null); while (leaf_range.next()) |entry| { if (try overflowRefOrNull(entry.value)) |overflow| try self.collectOverflowPages(write, overflow, pages); } }, .branch => { const branch = try page.Branch.load(image); var index: usize = 0; while (index < branch.cellCount()) : (index += 1) { const child_id = branch.childAt(index); var child_image: [page.size]u8 = undefined; try write.readExistingPage(child_id, &child_image); try self.collectReleasedPages(write, &child_image, depth + 1, pages); try pages.append(write.database.allocator, child_id); } }, .meta => return error.InvalidPage, .overflow => return error.InvalidPage, .identity => return error.InvalidPage, } } fn collectOverflowPages(self: *const Tree, write: *Write, overflow: record.Overflow, pages: *std.ArrayList(u32)) Error!void { _ = self; var remaining = try overflowLengthAsUsize(overflow.len); var page_id = overflow.first_page; while (page_id != 0) { var image: [page.size]u8 = undefined; try write.readExistingPage(page_id, &image); const overflow_page = try page.Overflow.load(&image); const expected = @min(page.overflow_capacity, remaining); if (overflow_page.content().len != expected) return error.InvalidPage; const next_page = overflow_page.next(); try pages.append(write.database.allocator, page_id); remaining -= expected; if (remaining == 0 and next_page != 0) return error.InvalidPage; if (remaining > 0 and next_page == 0) return error.InvalidPage; page_id = next_page; } if (remaining != 0) return error.InvalidPage; }};pub const Range = struct { scan: Scan, pub fn deinit(self: *Range) void { self.scan.deinit(); self.* = undefined; } pub fn next(self: *Range) Error!?page.Entry { if (try self.scan.next()) |entry| { return .{ .key = entry.key, .value = entry.bytes, }; } return null; } pub fn stats(self: *const Range) ScanStats { return self.scan.stats(); }};pub const Scan = struct { allocator: Allocator, read: ?file.ReadLease, snapshot: file.Snapshot, frames: [max_height]BranchFrame = undefined, depth: usize = 0, /// Image of the branch at `frames[depth - 1]`, validated when read. Leaf /// advances under one parent read only the next leaf. parent: [page.size]u8 = undefined, /// Image of the current leaf, validated when read. leaf: [page.size]u8 = undefined, value: std.ArrayList(u8) = .empty, end_key: [page.size]u8 = undefined, end_len: ?usize, index: usize, projection: Projection, observed: ScanStats = .{}, /// The first error `next` returned. A page that fails to read or validate /// can be left in `leaf` or `parent`, so the scan stops there and returns /// the same error from then on. failure: ?Error = null, /// Fills `self` in place, since a scan holds three page-sized buffers /// that a return by value would copy through each caller. fn init( self: *Scan, allocator: Allocator, snapshot: file.Snapshot, root_page: u32, start: ?[]const u8, end: ?[]const u8, projection: Projection, ) Error!void { const retained = try snapshot.retain(); self.* = .{ .allocator = allocator, .read = retained, .snapshot = snapshot, .end_len = null, .index = 0, .projection = projection, }; errdefer if (self.read) |*read| read.deinit(); if (end) |key| { if (key.len > page.size) return error.KeyTooLarge; @memcpy(self.end_key[0..key.len], key); self.end_len = key.len; } const root_mark = try readRoot(snapshot, root_page, &self.leaf); try self.descend(root_page, root_mark, start); const leaf = page.Leaf.fromValidated(&self.leaf); const leaf_range = try leaf.range(start, self.endSlice()); self.index = leaf_range.index; } pub fn deinit(self: *Scan) void { self.value.deinit(self.allocator); if (self.read) |*read| read.deinit(); self.* = undefined; } pub fn next(self: *Scan) Error!?ScanEntry { if (self.failure) |failure| return failure; return self.nextEntry() catch |err| { self.failure = err; return err; }; } fn nextEntry(self: *Scan) Error!?ScanEntry { while (true) { const leaf = page.Leaf.fromValidated(&self.leaf); var leaf_range = page.Range{ .leaf = &leaf, .end = self.endSlice(), .index = self.index, }; if (leaf_range.next()) |entry| { self.index = leaf_range.index; self.observed.entries_returned += 1; return .{ .key = entry.key, .bytes = try self.valueFor(entry.value), }; } if (!(try self.advanceLeaf())) return null; } } fn valueFor(self: *Scan, bytes: []const u8) Error![]const u8 { return switch (self.projection) { .key => "", .record => bytes, .value => value: { if (bytes.len == 0) return error.InvalidRecord; break :value switch (bytes[0]) { record.inline_tag => bytes[1..], record.overflow_tag => overflow_value: { const overflow = try record.overflow(bytes); const len = try overflowLengthAsUsize(overflow.len); try self.value.resize(self.allocator, len); try readOverflowValueInto(self.snapshot, overflow, self.value.items); break :overflow_value self.value.items; }, else => error.InvalidRecord, }; }, }; } pub fn stats(self: *const Scan) ScanStats { return self.observed; } fn endSlice(self: *const Scan) ?[]const u8 { const len = self.end_len orelse return null; return self.end_key[0..len]; } /// Descends from the page image in `self.leaf`, which is `page_id` with /// mark `page_mark`, to the leaf that holds `start`, or to the leftmost /// leaf. Each page is read into scan storage and loaded once. The last /// branch passed stays in `self.parent`. fn descend(self: *Scan, page_id: u32, page_mark: file.PageMark, start: ?[]const u8) Error!void { var current_page = page_id; var mark = page_mark; while (true) { switch (try loadMarkedTreePage(&self.leaf, mark)) { .leaf => { self.observed.leaf_pages_visited += 1; return; }, .branch => { if (self.depth >= max_height) return error.TreeTooDeep; self.parent = self.leaf; const branch = page.Branch.fromValidated(&self.parent); self.observed.branch_pages_visited += 1; const index = if (start) |key| branch.childIndexFor(key) else 0; self.frames[self.depth] = .{ .page_id = current_page, .index = index, }; self.depth += 1; current_page = branch.childAt(index); mark = try readMarkedPage(self.snapshot, current_page, &self.leaf); }, } } } /// Moves to the next leaf in key order. The branch above the current leaf /// is already in `self.parent`, so an advance to a sibling reads one page. /// Only an advance past the parent's last child rereads a higher branch. fn advanceLeaf(self: *Scan) Error!bool { while (self.depth > 0) { const frame = &self.frames[self.depth - 1]; const branch = page.Branch.fromValidated(&self.parent); const next_index = frame.index + 1; if (next_index < branch.cellCount()) { if (!self.childStartsBeforeEnd(branch.lowerAt(next_index))) { self.observed.separator_children_pruned += branch.cellCount() - next_index; return false; } frame.index = next_index; const child = branch.childAt(next_index); const mark = try readMarkedPage(self.snapshot, child, &self.leaf); try self.descend(child, mark, null); self.index = 0; return true; } self.depth -= 1; if (self.depth > 0) { const parent_page = self.frames[self.depth - 1].page_id; const mark = try readMarkedPage(self.snapshot, parent_page, &self.parent); switch (try loadMarkedTreePage(&self.parent, mark)) { .leaf => return error.InvalidPage, .branch => self.observed.branch_pages_visited += 1, } } } return false; } fn childStartsBeforeEnd(self: *const Scan, lower_key: []const u8) bool { const end = self.endSlice() orelse return true; return simd.order(Bytes, lower_key, end) == .lt; }};const RootBuild = struct { allocator: Allocator, nodes: std.ArrayList(Node) = .empty, edges: std.ArrayList(usize) = .empty, logical: lattice.State, fn init(allocator: Allocator) RootBuild { return .{ .allocator = allocator, .logical = lattice.State.empty, }; } fn deinit(self: *RootBuild) void { for (self.nodes.items) |node| { self.allocator.free(node.lower); if (node.upper) |upper| self.allocator.free(upper); } self.nodes.deinit(self.allocator); self.edges.deinit(self.allocator); self.* = undefined; } fn finish(self: *RootBuild) Allocator.Error!Root { const summary = self.nodes.items[0].summary; const subtree = self.nodes.items[0].hash; const logical = self.logical.digest(summary.entries); const nodes = try self.nodes.toOwnedSlice(self.allocator); errdefer { for (nodes) |node| { self.allocator.free(node.lower); if (node.upper) |upper| self.allocator.free(upper); } self.allocator.free(nodes); } const edges = try self.edges.toOwnedSlice(self.allocator); errdefer self.allocator.free(edges); self.nodes = .empty; self.edges = .empty; return .{ .allocator = self.allocator, .summary = summary, .hash = logical, .subtree = subtree, .nodes = nodes, .edges = edges, }; } fn appendNode(self: *RootBuild, snapshot: file.Snapshot, image: *const [page.size]u8, lower: []const u8, upper: ?[]const u8, depth: usize) Error!usize { if (depth >= max_height) return error.TreeTooDeep; const owned_lower = try self.allocator.dupe(u8, lower); var lower_in_nodes = false; errdefer if (!lower_in_nodes) self.allocator.free(owned_lower); const owned_upper = if (upper) |bytes| try self.allocator.dupe(u8, bytes) else null; var upper_in_nodes = owned_upper == null; errdefer if (!upper_in_nodes) self.allocator.free(owned_upper.?); const node_index = self.nodes.items.len; try self.nodes.append(self.allocator, .{ .kind = .leaf, .lower = owned_lower, .upper = owned_upper, .depth = depth, .summary = .{}, .hash = undefined, }); lower_in_nodes = true; upper_in_nodes = true; var current = image.*; switch (try page.kind(¤t)) { .leaf => try self.finishLeaf(snapshot, node_index, ¤t, depth), .branch => try self.finishBranch(snapshot, node_index, ¤t, depth), .meta => return error.InvalidPage, .overflow => return error.InvalidPage, .identity => return error.InvalidPage, } return node_index; } fn finishLeaf(self: *RootBuild, snapshot: file.Snapshot, node_index: usize, image: *[page.size]u8, depth: usize) Error!void { var summary = Summary{ .leaf_pages = 1, .max_depth = depth, }; var builder = HashBuilder.init("sql.map.leaf"); builder.writeU64(depth); const leaf = try page.Leaf.load(image); builder.writeU64(leaf.cellCount()); var range = try leaf.range(null, null); while (range.next()) |entry| { try summarizeEntry(snapshot, entry, &summary); builder.bytes(entry.key); try builder.recordValue(snapshot, entry.value); const entry_state = try latticeEntryFromRecord(snapshot, entry.key, entry.value); self.logical.add(&entry_state); } self.nodes.items[node_index].kind = .leaf; self.nodes.items[node_index].summary = summary; self.nodes.items[node_index].hash = builder.finish(); } fn finishBranch(self: *RootBuild, snapshot: file.Snapshot, node_index: usize, image: *[page.size]u8, depth: usize) Error!void { var summary = Summary{ .branch_pages = 1, .max_depth = depth, }; var builder = HashBuilder.init("sql.map.branch"); builder.writeU64(depth); const branch = try page.Branch.load(image); builder.writeU64(branch.cellCount()); var child_indexes: std.ArrayList(usize) = .empty; defer child_indexes.deinit(self.allocator); const node_upper = self.nodes.items[node_index].upper; var index: usize = 0; while (index < branch.cellCount()) : (index += 1) { var child_image: [page.size]u8 = undefined; try readExistingPage(snapshot, branch.childAt(index), &child_image); const child_upper = if (index + 1 < branch.cellCount()) branch.lowerAt(index + 1) else node_upper; const child_index = try self.appendNode(snapshot, &child_image, branch.lowerAt(index), child_upper, depth + 1); try child_indexes.append(self.allocator, child_index); const child_node = self.nodes.items[child_index]; addSummary(&summary, child_node.summary); builder.bytes(branch.lowerAt(index)); builder.hash(child_node.hash); builder.summary(child_node.summary); } const children_start = self.edges.items.len; try self.edges.appendSlice(self.allocator, child_indexes.items); self.nodes.items[node_index].kind = .branch; self.nodes.items[node_index].summary = summary; self.nodes.items[node_index].hash = builder.finish(); self.nodes.items[node_index].children_start = children_start; self.nodes.items[node_index].children_len = branch.cellCount(); }};const HashBuilder = struct { hasher: std.crypto.hash.sha2.Sha256, fn init(tag: []const u8) HashBuilder { var builder = HashBuilder{ .hasher = std.crypto.hash.sha2.Sha256.init(.{}) }; builder.bytes(tag); return builder; } fn finish(self: *HashBuilder) Hash { var digest: Hash = undefined; self.hasher.final(&digest); return digest; } fn bytes(self: *HashBuilder, value: []const u8) void { self.writeU64(value.len); self.hasher.update(value); } fn summary(self: *HashBuilder, value: Summary) void { self.writeU64(value.branch_pages); self.writeU64(value.leaf_pages); self.writeU64(value.overflow_pages); self.writeU64(value.entries); self.writeU64(value.inline_records); self.writeU64(value.overflow_records); self.writeU64(value.max_depth); self.writeU64(value.key_bytes); self.writeU64(value.record_bytes); self.writeU64(value.value_bytes); } fn writeU64(self: *HashBuilder, value: anytype) void { var encoded: [8]u8 = undefined; std.mem.writeInt(u64, encoded[0..], @intCast(value), .big); self.hasher.update(&encoded); } fn hash(self: *HashBuilder, value: Hash) void { self.hasher.update(&value); } fn recordValue(self: *HashBuilder, snapshot: file.Snapshot, encoded: []const u8) Error!void { switch (try record.kind(encoded)) { .inline_value => self.bytes(try record.inlineValue(encoded)), .overflow => try self.overflowValue(snapshot, try record.overflow(encoded)), } } fn overflowValue(self: *HashBuilder, snapshot: file.Snapshot, overflow: record.Overflow) Error!void { var remaining = try overflowLengthAsUsize(overflow.len); self.writeU64(remaining); var page_id = overflow.first_page; while (page_id != 0) { var image: [page.size]u8 = undefined; try readExistingPage(snapshot, page_id, &image); const overflow_page = try page.Overflow.load(&image); const expected = @min(page.overflow_capacity, remaining); if (overflow_page.content().len != expected) return error.InvalidPage; self.hasher.update(overflow_page.content()); remaining -= expected; const next_page = overflow_page.next(); if (remaining == 0 and next_page != 0) return error.InvalidPage; if (remaining > 0 and next_page == 0) return error.InvalidPage; page_id = next_page; } if (remaining != 0) return error.InvalidPage; }};fn readExistingPage(source: anytype, page_id: u32, image: *[page.size]u8) Error!void { if (try source.copyPage(page_id, image)) return; return error.InvalidPage;}/// Copies a page the tree refers to and returns the mark of the image it/// copied.fn readMarkedPage( snapshot: file.Snapshot, page_id: u32, image: *[page.size]u8,) Error!file.PageMark { return try snapshot.copyMarkedPage(page_id, image) orelse error.InvalidPage;}/// Wraps a leaf or branch copied with `mark`. A copy whose stored image/// already passed its loader only has its header read. Any other copy is/// validated and its mark recorded. Safety builds validate every copy and/// panic on a stale mark.fn loadMarkedTreePage(image: *[page.size]u8, mark: file.PageMark) Error!TreePage { if (!mark.checked()) { const loaded = try loadTreePage(image); mark.record(); return loaded; } if (std.debug.runtime_safety) std.debug.assert(validTreePage(image)); return try trustedTreePage(image);}fn refreshTestRead(read: *file.ReadLease, database: *file.Database) Error!void { const next = try database.beginRead(); read.deinit(); read.* = next;}fn loadTreePage(image: *[page.size]u8) Error!TreePage { return switch (try page.kind(image)) { .leaf => .{ .leaf = try page.Leaf.load(image) }, .branch => .{ .branch = try page.Branch.load(image) }, .meta, .overflow, .identity => error.InvalidPage, };}/// Wraps a leaf or branch whose cells are known valid, reading its kind/// from the header.fn trustedTreePage(image: *[page.size]u8) Error!TreePage { return switch (try page.kind(image)) { .leaf => .{ .leaf = page.Leaf.fromValidated(image) }, .branch => .{ .branch = page.Branch.fromValidated(image) }, .meta, .overflow, .identity => error.InvalidPage, };}/// Returns whether a trusted image validates, or is no leaf or branch,/// which `trustedTreePage` rejects itself.fn validTreePage(image: *[page.size]u8) bool { return switch (page.kind(image) catch return true) { .leaf => if (page.Leaf.load(image)) |_| true else |_| false, .branch => if (page.Branch.load(image)) |_| true else |_| false, .meta, .overflow, .identity => true, };}fn zeroPage(image: *const [page.size]u8) bool { return simd.allEqual(Bytes, image, 0);}fn addSummary(target: *Summary, source: Summary) void { target.branch_pages += source.branch_pages; target.leaf_pages += source.leaf_pages; target.overflow_pages += source.overflow_pages; target.entries += source.entries; target.inline_records += source.inline_records; target.overflow_records += source.overflow_records; target.max_depth = @max(target.max_depth, source.max_depth); target.key_bytes += source.key_bytes; target.record_bytes += source.record_bytes; target.value_bytes += source.value_bytes;}fn summarizePage( source: anytype, image: *const [page.size]u8, depth: usize, summary: *Summary,) Error!void { if (depth >= max_height) return error.TreeTooDeep; summary.max_depth = @max(summary.max_depth, depth); var current = image.*; switch (try page.kind(¤t)) { .leaf => { summary.leaf_pages += 1; const leaf = try page.Leaf.load(¤t); var range = try leaf.range(null, null); while (range.next()) |entry| { try summarizeEntry(source, entry, summary); } }, .branch => { summary.branch_pages += 1; const branch = try page.Branch.load(¤t); var index: usize = 0; while (index < branch.cellCount()) : (index += 1) { var child: [page.size]u8 = undefined; try readExistingPage(source, branch.childAt(index), &child); try summarizePage(source, &child, depth + 1, summary); } }, .meta => return error.InvalidPage, .overflow => return error.InvalidPage, .identity => return error.InvalidPage, }}fn summarizeEntry(source: anytype, entry: page.Entry, summary: *Summary) Error!void { summary.entries += 1; summary.key_bytes += entry.key.len; summary.record_bytes += entry.value.len; switch (try record.kind(entry.value)) { .inline_value => { const value = try record.inlineValue(entry.value); summary.inline_records += 1; summary.value_bytes += value.len; }, .overflow => { const overflow = try record.overflow(entry.value); summary.overflow_records += 1; summary.value_bytes += try overflowLengthAsUsize(overflow.len); try summarizeOverflowValue(source, overflow, summary); }, }}fn summarizeOverflowValue( source: anytype, overflow: record.Overflow, summary: *Summary,) Error!void { var remaining = try overflowLengthAsUsize(overflow.len); var page_id = overflow.first_page; while (page_id != 0) { var image: [page.size]u8 = undefined; try readExistingPage(source, page_id, &image); const overflow_page = try page.Overflow.load(&image); const expected = @min(page.overflow_capacity, remaining); if (overflow_page.content().len != expected) return error.InvalidPage; remaining -= expected; summary.overflow_pages += 1; const next_page = overflow_page.next(); if (remaining == 0 and next_page != 0) return error.InvalidPage; if (remaining > 0 and next_page == 0) return error.InvalidPage; page_id = next_page; } if (remaining != 0) return error.InvalidPage;}fn overflowRefOrNull(bytes: ?[]const u8) Error!?record.Overflow { const value = bytes orelse return null; return switch (try record.kind(value)) { .inline_value => null, .overflow => try record.overflow(value), };}fn rootEntryLessThan(_: void, left: RootEntry, right: RootEntry) bool { return simd.order(Bytes, left.key, right.key) == .lt;}fn overflowLengthAsUsize(len: u64) Error!usize { if (len > std.math.maxInt(usize)) return error.ValueTooLarge; return @intCast(len);}fn valueRecordLength(bytes: []const u8) Error!usize { return switch (try record.kind(bytes)) { .inline_value => (try record.inlineValue(bytes)).len, .overflow => try overflowLengthAsUsize((try record.overflow(bytes)).len), };}fn readValueRecordInto(snapshot: file.Snapshot, bytes: []const u8, target: []u8) Error![]u8 { const value_len = try valueRecordLength(bytes); if (target.len < value_len) return error.OutputTooSmall; const value = target[0..value_len]; switch (try record.kind(bytes)) { .inline_value => @memcpy(value, try record.inlineValue(bytes)), .overflow => try readOverflowValueInto(snapshot, try record.overflow(bytes), value), } return value;}fn readOverflowValueInto(snapshot: file.Snapshot, overflow: record.Overflow, target: []u8) Error!void { if (target.len != try overflowLengthAsUsize(overflow.len)) return error.InvalidRecord; var offset: usize = 0; var page_id = overflow.first_page; while (page_id != 0) { var image: [page.size]u8 = undefined; try readExistingPage(snapshot, page_id, &image); const overflow_page = try page.Overflow.load(&image); const remaining = target.len - offset; const expected = @min(page.overflow_capacity, remaining); if (overflow_page.content().len != expected) return error.InvalidPage; @memcpy(target[offset..][0..expected], overflow_page.content()); offset += expected; const next_page = overflow_page.next(); if (offset == target.len and next_page != 0) return error.InvalidPage; if (offset < target.len and next_page == 0) return error.InvalidPage; page_id = next_page; } if (offset != target.len) return error.InvalidPage;}fn latticeEntryFromRecord(snapshot: file.Snapshot, entry_key: []const u8, encoded: []const u8) Error!lattice.State { var hasher = lattice.EntryHasher.init(entry_key); switch (try record.kind(encoded)) { .inline_value => hasher.update(try record.inlineValue(encoded)), .overflow => { const overflow = try record.overflow(encoded); var remaining = try overflowLengthAsUsize(overflow.len); var page_id = overflow.first_page; while (page_id != 0) { var image: [page.size]u8 = undefined; try readExistingPage(snapshot, page_id, &image); const overflow_page = try page.Overflow.load(&image); const expected = @min(page.overflow_capacity, remaining); if (overflow_page.content().len != expected) return error.InvalidPage; hasher.update(overflow_page.content()); const next_page = overflow_page.next(); remaining -= expected; if (remaining == 0 and next_page != 0) return error.InvalidPage; if (remaining > 0 and next_page == 0) return error.InvalidPage; page_id = next_page; } if (remaining != 0) return error.InvalidPage; }, } return hasher.finish();}fn copyRootPage(root: *[page.size]u8, source: *[page.size]u8, root_page: u32) Error!void { switch (try page.kind(source)) { .leaf => { const source_leaf = try page.Leaf.load(source); var root_leaf = page.Leaf.init(root, root_page); try source_leaf.copyTo(&root_leaf); }, .branch => { const source_branch = try page.Branch.load(source); var root_branch = page.Branch.init(root, root_page); try source_branch.copyTo(&root_branch); }, .meta => return error.InvalidPage, .overflow => return error.InvalidPage, .identity => return error.InvalidPage, }}test "tree reader keeps a fixed read view without write declarations" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "reader.db", .wal = "reader.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 32 }); const options = Options{ .identity_page = 3 }; var mutable = try Tree.open(&database, options); _ = try mutable.put("a", "one", .{ .durability = .buffered }); _ = try mutable.put("b", "two", .{ .durability = .buffered }); var read = try database.beginRead(); defer read.deinit(); const reader = try Reader.open(read.snapshot(), options); _ = try mutable.put("c", "three", .{ .durability = .buffered }); const found = (try reader.get(std.testing.allocator, "a")).?; defer std.testing.allocator.free(found); try std.testing.expectEqualStrings("one", found); try std.testing.expectEqual(@as(?usize, 3), try reader.valueLength("b")); var value_buffer: [8]u8 = undefined; try std.testing.expectEqualStrings("two", (try reader.getInto("b", &value_buffer)).?); const missing = try reader.get(std.testing.allocator, "c"); if (missing) |bytes| std.testing.allocator.free(bytes); try std.testing.expect(missing == null); var key_buffer: [8]u8 = undefined; try std.testing.expectEqualStrings("b", (try reader.lastKey(&key_buffer)).?); try std.testing.expectEqual(@as(u64, 2), (try reader.identity()).entries); try std.testing.expectEqual(@as(usize, 2), (try reader.summarize()).entries); var scan: Scan = undefined; try reader.scan(&scan, std.testing.allocator, null, null, .value); defer scan.deinit(); try std.testing.expectEqualStrings("a", (try scan.next()).?.key); try std.testing.expectEqualStrings("b", (try scan.next()).?.key); try std.testing.expect(try scan.next() == null); try std.testing.expect(!@hasDecl(Reader, "put")); try std.testing.expect(!@hasDecl(Reader, "delete")); try std.testing.expect(!@hasDecl(Reader, "clear"));}test "tree staged summary matches committed summary" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "summary.db", .wal = "summary.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 32 }); var source = try Tree.open(&database, .{}); var write = try Write.beginTree(&source); defer write.deinit(); try write.put(&source, "key", "value"); const staged = try source.summarizeIn(&write); try std.testing.expectEqual(@as(usize, 1), staged.entries); try std.testing.expectEqual(@as(usize, 0), (try source.summarize()).entries); _ = try write.commit(.{ .durability = .buffered }); try std.testing.expect(std.meta.eql(staged, try source.summarize()));}test "tree root split creates a branch over leaf children" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 220 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 180) : (index += 1) { var key_buffer: [16]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index}); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); const snapshot = snapshot_read.snapshot(); var root_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.root_page, &root_image); try std.testing.expectEqual(page.Kind.branch, try page.kind(&root_image)); const branch = try page.Branch.load(&root_image); try std.testing.expect(branch.cellCount() >= 2); const value = (try tree.get(std.testing.allocator, "k00000179")).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("v00000179", value); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); var count: usize = 0; while (try range.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 180), count);}test "tree split root recovers after reopen" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); { var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 220 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 180) : (index += 1) { var key_buffer: [16]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index}); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } try database.syncWal(); } var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = recoveredHeader(), }); defer reopened.deinit(); var tree = try Tree.open(&reopened, .{}); const value = (try tree.get(std.testing.allocator, "k00000120")).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("v00000120", value); var range: Range = undefined; try tree.range(&range, std.testing.allocator, "k00000170", null); defer range.deinit(); var count: usize = 0; while (try range.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 10), count);}test "tree treats sparse reserved root as empty" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); { var base = try tmp.dir.createFile(io, "tree.db", .{ .read = true, .truncate = true }); defer base.close(io); var meta_image: [page.size]u8 = undefined; _ = page.Meta.init(&meta_image, 1, 8); try base.writePositionalAll(io, meta_image[0..], 0); try base.setLength(io, @as(u64, page.size * 8)); } var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = recoveredHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 64 }); var tree = try Tree.open(&database, .{ .root_page = 2, .reserved_page_max = 8 }); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); try std.testing.expect(try range.next() == null); _ = try tree.put("needle", "value", .{ .durability = .buffered }); const found = (try tree.get(std.testing.allocator, "needle")).?; defer std.testing.allocator.free(found); try std.testing.expectEqualStrings("value", found);}test "tree rejects a reserved root with a byte past a zero header" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); { var base = try tmp.dir.createFile(io, "tree.db", .{ .read = true, .truncate = true }); defer base.close(io); var meta_image: [page.size]u8 = undefined; _ = page.Meta.init(&meta_image, 1, 8); try base.writePositionalAll(io, meta_image[0..], 0); var root_image: [page.size]u8 = @splat(0); root_image[page.size - 1] = 1; try base.writePositionalAll(io, root_image[0..], page.size); try base.setLength(io, @as(u64, page.size * 8)); } var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = recoveredHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 64 }); var tree = try Tree.open(&database, .{ .root_page = 2, .reserved_page_max = 8 }); try std.testing.expectError(error.InvalidPage, tree.get(std.testing.allocator, "needle")); const put = tree.put("needle", "value", .{ .durability = .buffered }); try std.testing.expectError(error.InvalidPage, put);}test "tree splits a full child leaf under branch root" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 340 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 260) : (index += 1) { var key_buffer: [16]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index}); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); const snapshot = snapshot_read.snapshot(); var root_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.root_page, &root_image); const branch = try page.Branch.load(&root_image); try std.testing.expect(branch.cellCount() >= 3); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); var count: usize = 0; while (try range.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 260), count);}test "tree accepts every fitting key beside short separators" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 64 * 8 + 64 }); var long: [key_bytes_max]u8 = @splat('z'); try std.testing.expectEqual(@as(usize, 2020), key_bytes_max); var tree = try Tree.open(&database, .{}); const value: [500]u8 = @splat('v'); for (0..40) |index| { var short: [8]u8 = undefined; _ = try std.fmt.bufPrint(&short, "a{d:0>7}", .{index}); _ = try tree.put(&short, &value, .{ .durability = .buffered }); } for (0..12) |index| { _ = try std.fmt.bufPrint(long[0..8], "z{d:0>7}", .{index}); _ = try tree.put(&long, "", .{ .durability = .buffered }); } const summary = try tree.summarize(); try std.testing.expectEqual(@as(usize, 52), summary.entries); try std.testing.expect(summary.max_depth >= 2);}test "tree recursively splits branch pages" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 220 * 8 + 64 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 220) : (index += 1) { var key_buffer: [512]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = wideKey(&key_buffer, index); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); const snapshot = snapshot_read.snapshot(); var root_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.root_page, &root_image); const root_branch = try page.Branch.load(&root_image); try std.testing.expect(root_branch.cellCount() >= 2); var child_image: [page.size]u8 = undefined; try readExistingPage(snapshot, root_branch.childAt(root_branch.cellCount() - 1), &child_image); try std.testing.expectEqual(page.Kind.branch, try page.kind(&child_image)); var deleted_key_buffer: [512]u8 = undefined; _ = try tree.delete(wideKey(&deleted_key_buffer, 100), .{ .durability = .buffered }); const deleted_value = try tree.get(std.testing.allocator, wideKey(&deleted_key_buffer, 100)); if (deleted_value) |bytes| std.testing.allocator.free(bytes); try std.testing.expect(deleted_value == null); var value_key_buffer: [512]u8 = undefined; const value = (try tree.get(std.testing.allocator, wideKey(&value_key_buffer, 219))).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("v00000219", value); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); var count: usize = 0; var previous_buffer: [512]u8 = undefined; var previous_len: usize = 0; while (try range.next()) |entry| { if (previous_len > 0) try std.testing.expect(std.mem.order(u8, previous_buffer[0..previous_len], entry.key) == .lt); @memcpy(previous_buffer[0..entry.key.len], entry.key); previous_len = entry.key.len; count += 1; } try std.testing.expectEqual(@as(usize, 219), count); const full_stats = range.stats(); try std.testing.expectEqual(count, full_stats.entries_returned); try std.testing.expectEqual(@as(usize, 0), full_stats.separator_children_pruned); const summary = try tree.summarize(); try std.testing.expectEqual(count, summary.entries); try std.testing.expect(summary.branch_pages > 1); try std.testing.expect(summary.leaf_pages > 1); try std.testing.expect(summary.max_depth >= 2); try std.testing.expectEqual(@as(usize, 0), summary.overflow_records); try std.testing.expectEqual(@as(usize, 0), summary.overflow_pages); try std.testing.expectEqual(count * 512, summary.key_bytes); try std.testing.expectEqual(count * 9, summary.value_bytes); try std.testing.expectEqual(summary.leaf_pages, full_stats.leaf_pages_visited); var bounded_start_buffer: [512]u8 = undefined; var bounded_end_buffer: [512]u8 = undefined; var bounded: Range = undefined; try tree.range( &bounded, std.testing.allocator, wideKey(&bounded_start_buffer, 8), wideKey(&bounded_end_buffer, 17), ); defer bounded.deinit(); var bounded_count: usize = 0; while (try bounded.next()) |entry| { try std.testing.expect(std.mem.order(u8, wideKey(&bounded_start_buffer, 8), entry.key) != .gt); try std.testing.expect(std.mem.order(u8, entry.key, wideKey(&bounded_end_buffer, 17)) == .lt); bounded_count += 1; } try std.testing.expectEqual(@as(usize, 9), bounded_count); const bounded_stats = bounded.stats(); try std.testing.expectEqual(bounded_count, bounded_stats.entries_returned); try std.testing.expect(bounded_stats.separator_children_pruned > 0); try std.testing.expect(bounded_stats.leaf_pages_visited < full_stats.leaf_pages_visited);}test "tree root hash is stable across reopen and changes after write" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var before_hash: Hash = undefined; { var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree-root.db", .wal = "tree-root.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 64 }); var tree = try Tree.open(&database, .{}); _ = try tree.put("a", "one", .{ .durability = .buffered }); _ = try tree.put("b", "two", .{ .durability = .buffered }); var root = try tree.root(std.testing.allocator); defer root.deinit(); before_hash = root.hash; try std.testing.expectEqual(@as(usize, 2), root.summary.entries); try database.syncWal(); } var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree-root.db", .wal = "tree-root.wal" }, .header = recoveredHeader(), }); defer reopened.deinit(); try reopened.reserve(.{ .wal_frames = 64 }); var tree = try Tree.open(&reopened, .{}); var same = try tree.root(std.testing.allocator); defer same.deinit(); try std.testing.expectEqualSlices(u8, before_hash[0..], same.hash[0..]); _ = try tree.put("b", "changed", .{ .durability = .buffered }); var changed = try tree.root(std.testing.allocator); defer changed.deinit(); try std.testing.expect(!std.mem.eql(u8, before_hash[0..], changed.hash[0..]));}test "tree root cache serves unchanged views and recomputes across writes and checkpoints" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree-cache.db", .wal = "tree-cache.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 64 }); var tree = try Tree.open(&database, .{}); _ = try tree.put("a", "one", .{ .durability = .buffered }); var first = try tree.root(std.testing.allocator); defer first.deinit(); var cached = try tree.root(std.testing.allocator); defer cached.deinit(); try std.testing.expectEqualSlices(u8, first.hash[0..], cached.hash[0..]); try std.testing.expectEqual(first.summary.entries, cached.summary.entries); try std.testing.expectEqual(first.nodes.len, cached.nodes.len); _ = try tree.put("b", "two", .{ .durability = .buffered }); var written = try tree.root(std.testing.allocator); defer written.deinit(); try std.testing.expect(!std.mem.eql(u8, first.hash[0..], written.hash[0..])); try std.testing.expectEqual(@as(usize, 2), written.summary.entries); _ = try database.checkpoint(.{ .restart_header = testingHeader() }); var checkpointed = try tree.root(std.testing.allocator); defer checkpointed.deinit(); try std.testing.expectEqualSlices(u8, written.hash[0..], checkpointed.hash[0..]);}test "tree range after lazy reopen does not retain scanned base pages" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); { var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 220 * 8 + 64 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 220) : (index += 1) { var key_buffer: [512]u8 = undefined; var value_buffer: [16]u8 = undefined; _ = try tree.put(wideKey(&key_buffer, index), try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}), .{ .durability = .buffered }); } _ = try database.checkpoint(.{ .restart_header = recoveredHeader() }); } var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = recoveredHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 64 }); try std.testing.expectEqual(@as(usize, 0), database.pager.base.items.len); var tree = try Tree.open(&database, .{}); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); var count: usize = 0; while (try range.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 220), count); try std.testing.expectEqual(@as(usize, 0), database.pager.base.items.len); const summary = try tree.summarize(); try std.testing.expectEqual(@as(usize, 220), summary.entries); try std.testing.expectEqual(@as(usize, 0), database.pager.base.items.len);}test "tree root exposes subtree hashes for unchanged child regions" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree-root-subtree.db", .wal = "tree-root-subtree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 360 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 260) : (index += 1) { var key_buffer: [16]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index}); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } var before = try tree.root(std.testing.allocator); defer before.deinit(); const before_root = before.rootNode(); try std.testing.expectEqual(NodeKind.branch, before_root.kind); try std.testing.expect(before_root.children_len >= 3); try std.testing.expectEqual(before.summary.entries, before_root.summary.entries); try std.testing.expectEqualSlices(u8, before.subtree[0..], before_root.hash[0..]); const before_children = before.childIndexes(before_root); var before_child_index: usize = 0; while (before_child_index < before_children.len) : (before_child_index += 1) { const child_node = &before.nodes[before_children[before_child_index]]; if (before_child_index + 1 < before_children.len) { const next_node = &before.nodes[before_children[before_child_index + 1]]; try std.testing.expectEqualSlices(u8, next_node.lower, child_node.upper.?); } else { try std.testing.expect(child_node.upper == null); } } _ = try tree.put("k00000259", "changed", .{ .durability = .buffered }); var after = try tree.root(std.testing.allocator); defer after.deinit(); const after_root = after.rootNode(); try std.testing.expectEqual(NodeKind.branch, after_root.kind); try std.testing.expect(!std.mem.eql(u8, before.hash[0..], after.hash[0..])); try std.testing.expect(!std.mem.eql(u8, before.subtree[0..], after.subtree[0..])); try std.testing.expect(hasSharedChildHash(&before, &after));}test "tree recursive branch splits recover after reopen" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); { var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 180 * 8 + 64 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 180) : (index += 1) { var key_buffer: [512]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = wideKey(&key_buffer, index); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } try database.syncWal(); } var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = recoveredHeader(), }); defer reopened.deinit(); var tree = try Tree.open(&reopened, .{}); var key_buffer: [512]u8 = undefined; const value = (try tree.get(std.testing.allocator, wideKey(&key_buffer, 120))).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("v00000120", value); var start_buffer: [512]u8 = undefined; var range: Range = undefined; try tree.range(&range, std.testing.allocator, wideKey(&start_buffer, 170), null); defer range.deinit(); var count: usize = 0; while (try range.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 10), count);}test "tree delete removes empty child and collapses root branch" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 320 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 180) : (index += 1) { var key_buffer: [16]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index}); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } index = 0; while (index < 120) : (index += 1) { var key_buffer: [16]u8 = undefined; const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index}); _ = try tree.delete(key, .{ .durability = .buffered }); } var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); const snapshot = snapshot_read.snapshot(); var root_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.root_page, &root_image); try std.testing.expectEqual(page.Kind.leaf, try page.kind(&root_image)); const leaf = try page.Leaf.load(&root_image); try std.testing.expectEqual(@as(u64, tree.root_page), leaf.id()); var deleted_key: [16]u8 = undefined; const deleted_value = try tree.get(std.testing.allocator, try std.fmt.bufPrint(&deleted_key, "k{d:0>8}", .{0})); if (deleted_value) |bytes| std.testing.allocator.free(bytes); try std.testing.expect(deleted_value == null); const value = (try tree.get(std.testing.allocator, "k00000150")).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("v00000150", value); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); var count: usize = 0; while (try range.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 60), count);}test "tree delete retains a safe lower bound when exact replacement does not fit" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 32 }); var tree = try Tree.open(&database, .{}); var next_key: [1500]u8 = @splat('n'); var upper_key: [3000]u8 = @splat('z'); var encoded_buffer: [16]u8 = undefined; const encoded = try record.encodeInline(&encoded_buffer, "value"); { var write = try Write.beginTree(&tree); defer write.deinit(); const left_id = try write.allocatePage(); const middle_id = try write.allocatePage(); const right_id = try write.allocatePage(); var left_image: [page.size]u8 = undefined; var middle_image: [page.size]u8 = undefined; var right_image: [page.size]u8 = undefined; var root_image: [page.size]u8 = undefined; var left = page.Leaf.init(&left_image, left_id); var middle = page.Leaf.init(&middle_image, middle_id); var right = page.Leaf.init(&right_image, right_id); var root = page.Branch.init(&root_image, tree.root_page); try left.put("a", encoded); try middle.put("m", encoded); try middle.put(&next_key, encoded); try right.put(&upper_key, encoded); try root.put("", left_id); try root.put("m", middle_id); try root.put(&upper_key, right_id); try write.putPage(left_id, &left_image); try write.putPage(middle_id, &middle_image); try write.putPage(right_id, &right_image); try write.putPage(tree.root_page, &root_image); _ = try write.commit(.{ .durability = .buffered }); } _ = try tree.delete("m", .{ .durability = .buffered }); try std.testing.expect((try tree.get(std.testing.allocator, "m")) == null); const value = (try tree.get(std.testing.allocator, &next_key)).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("value", value);}test "tree delete compacts recursive branches back to a root leaf" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 120 * 8 + 120 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 110) : (index += 1) { var key_buffer: [512]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = wideKey(&key_buffer, index); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } index = 0; while (index < 104) : (index += 1) { var key_buffer: [512]u8 = undefined; _ = try tree.delete(wideKey(&key_buffer, index), .{ .durability = .buffered }); } var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); const snapshot = snapshot_read.snapshot(); var root_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.root_page, &root_image); try std.testing.expectEqual(page.Kind.leaf, try page.kind(&root_image)); const leaf = try page.Leaf.load(&root_image); try std.testing.expectEqual(@as(u64, tree.root_page), leaf.id()); var value_key_buffer: [512]u8 = undefined; const value = (try tree.get(std.testing.allocator, wideKey(&value_key_buffer, 109))).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("v00000109", value); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); var count: usize = 0; while (try range.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 6), count);}test "tree reuses freed pages after delete compaction" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 160 * 8 + 160 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 110) : (index += 1) { var key_buffer: [512]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = wideKey(&key_buffer, index); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); var snapshot = snapshot_read.snapshot(); var meta_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.meta_page, &meta_image); var meta = try page.Meta.load(&meta_image); const highest_after_growth = meta.highestPage(); index = 0; while (index < 104) : (index += 1) { var key_buffer: [512]u8 = undefined; _ = try tree.delete(wideKey(&key_buffer, index), .{ .durability = .buffered }); } try refreshTestRead(&snapshot_read, &database); snapshot = snapshot_read.snapshot(); try readExistingPage(snapshot, tree.meta_page, &meta_image); meta = try page.Meta.load(&meta_image); const highest_before_reuse = meta.highestPage(); const free_before_reuse = meta.freeCount(); try std.testing.expect(free_before_reuse > 0 or highest_before_reuse < highest_after_growth); while (index < 122) : (index += 1) { var key_buffer: [512]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = wideKey(&key_buffer, index); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } try refreshTestRead(&snapshot_read, &database); snapshot = snapshot_read.snapshot(); try readExistingPage(snapshot, tree.meta_page, &meta_image); meta = try page.Meta.load(&meta_image); try std.testing.expect(meta.highestPage() <= highest_after_growth); if (free_before_reuse > 0) try std.testing.expect(meta.freeCount() < free_before_reuse); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); var count: usize = 0; while (try range.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 18), count);}test "allocated roots clear recycled page images" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 32 }); var tree = try Tree.open(&database, .{}); var recycled: [2]u32 = undefined; { var write = try Write.beginTree(&tree); defer write.deinit(); for (&recycled) |*page_id| { page_id.* = try write.allocatePage(); var image: [page.size]u8 = undefined; _ = page.Leaf.init(&image, page_id.*); try write.putPage(page_id.*, &image); } const retained = try write.allocatePage(); var image: [page.size]u8 = undefined; _ = page.Leaf.init(&image, retained); try write.putPage(retained, &image); _ = try write.commit(.{ .durability = .buffered }); } { var write = try Write.beginTree(&tree); defer write.deinit(); try write.releasePage(tree.root_page, recycled[0]); try write.releasePage(tree.root_page, recycled[1]); _ = try write.commit(.{ .durability = .buffered }); } var before_read = try database.beginRead(); defer before_read.deinit(); const before = before_read.snapshot(); var meta_image: [page.size]u8 = undefined; try readExistingPage(before, tree.meta_page, &meta_image); const meta = try page.Meta.load(&meta_image); try std.testing.expectEqual(@as(usize, 2), meta.freeCount()); var root_page: u32 = undefined; var identity_page: u32 = undefined; { var write = try Write.beginTree(&tree); defer write.deinit(); root_page = try write.allocateRoot(); identity_page = try write.allocateRoot(); _ = try write.commit(.{ .durability = .buffered }); } try std.testing.expect(root_page <= meta.highestPage()); try std.testing.expect(identity_page <= meta.highestPage()); const empty = try Tree.open(&database, .{ .root_page = root_page, .identity_page = identity_page, }); const identity = try empty.identity(); try std.testing.expectEqual(@as(u64, 0), identity.entries); try std.testing.expect((try empty.get(std.testing.allocator, "missing")) == null);}test "tree root edges link every node to its direct children" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 8192 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 360) : (index += 1) { var key_buffer: [512]u8 = undefined; var value_buffer: [16]u8 = undefined; const key = wideKey(&key_buffer, index); const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}); _ = try tree.put(key, value, .{ .durability = .buffered }); } var root = try tree.root(std.testing.allocator); defer root.deinit(); try std.testing.expect(root.summary.max_depth >= 2); const seen = try std.testing.allocator.alloc(usize, root.nodes.len); defer std.testing.allocator.free(seen); @memset(seen, 0); seen[0] = 1; for (root.nodes, 0..) |node, parent_index| { if (node.kind != .branch) { try std.testing.expectEqual(@as(usize, 0), node.children_len); continue; } try std.testing.expect(node.children_len != 0); for (root.childIndexes(&root.nodes[parent_index])) |child_index| { const child = root.nodes[child_index]; try std.testing.expectEqual(node.depth + 1, child.depth); seen[child_index] += 1; } } for (seen) |count| { try std.testing.expectEqual(@as(usize, 1), count); }}fn seedFullInlineFreeList(database: *file.Database, tree: *const Tree, first_page: u32) !void { var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); const snapshot = snapshot_read.snapshot(); var meta_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.meta_page, &meta_image); var meta = try page.Meta.load(&meta_image); const capacity = meta.freeCapacity(); _ = try meta.reserveThrough(first_page + @as(u32, @intCast(capacity + 4))); var page_id = first_page; while (meta.freeCount() < capacity) : (page_id += 1) { if (page_id == tree.meta_page or page_id == tree.root_page) continue; try meta.release(page_id); } var transaction = try database.beginWrite(); defer transaction.deinit(); try transaction.putPage(tree.meta_page, &meta_image); _ = try transaction.commit(.{ .durability = .buffered });}test "tree spills a full inline free list into a chain and refills it" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 64 }); var tree = try Tree.open(&database, .{}); var first_large: [page.overflow_capacity * 2 + 37]u8 = undefined; var second_large: [page.overflow_capacity * 3 + 37]u8 = undefined; fillLargeValue(&first_large, 71); fillLargeValue(&second_large, 91); _ = try tree.put("large", &first_large, .{ .durability = .buffered }); const seeded = try tree.summarize(); try std.testing.expectEqual(@as(usize, 1), seeded.entries); try std.testing.expectEqual(@as(usize, 3), seeded.overflow_pages); try seedFullInlineFreeList(&database, &tree, 128); var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); var snapshot = snapshot_read.snapshot(); var meta_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.meta_page, &meta_image); var meta = try page.Meta.load(&meta_image); try std.testing.expectEqual(meta.freeCapacity(), meta.freeCount()); const seeded_highest = meta.highestPage(); _ = try tree.delete("large", .{ .durability = .buffered }); try refreshTestRead(&snapshot_read, &database); snapshot = snapshot_read.snapshot(); try readExistingPage(snapshot, tree.meta_page, &meta_image); meta = try page.Meta.load(&meta_image); try std.testing.expect(meta.isChained()); try std.testing.expect(meta.chainHead() != 0); try std.testing.expect(meta.freeCount() > 0); _ = try tree.put("other", &second_large, .{ .durability = .buffered }); try refreshTestRead(&snapshot_read, &database); snapshot = snapshot_read.snapshot(); try readExistingPage(snapshot, tree.meta_page, &meta_image); meta = try page.Meta.load(&meta_image); try std.testing.expect(!meta.isChained()); try std.testing.expect(meta.highestPage() <= seeded_highest); try std.testing.expect(meta.freeCount() > 0); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); const entry = (try range.next()).?; try std.testing.expectEqualStrings("other", entry.key); try std.testing.expectEqualSlices(u8, &second_large, entry.value); try std.testing.expect(try range.next() == null);}test "tree clear releases durable pages without loading base tree" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); { var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 1024 }); var tree = try Tree.open(&database, .{}); var large: [page.overflow_capacity + 37]u8 = undefined; fillLargeValue(&large, 33); var index: usize = 0; while (index < 64) : (index += 1) { var key_buffer: [512]u8 = undefined; _ = try tree.put(wideKey(&key_buffer, index), &large, .{ .durability = .buffered }); } const before = try tree.summarize(); try std.testing.expect(before.branch_pages > 0); try std.testing.expect(before.overflow_pages >= 64); _ = try database.checkpoint(.{ .restart_header = recoveredHeader() }); } { var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = recoveredHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 512 }); var tree = try Tree.open(&database, .{}); _ = try tree.clear(.{ .durability = .buffered }); try std.testing.expect(database.pager.base.items.len <= 1); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); try std.testing.expect(try range.next() == null); _ = try tree.put("after", "clear", .{ .durability = .buffered }); const value = (try tree.get(std.testing.allocator, "after")).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("clear", value); }}test "tree stores large values in overflow pages and reuses replaced chains" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 32 }); var tree = try Tree.open(&database, .{}); var large: [page.overflow_capacity * 2 + 37]u8 = undefined; fillLargeValue(&large, 17); _ = try tree.put("large", &large, .{ .durability = .buffered }); const stored = (try tree.get(std.testing.allocator, "large")).?; defer std.testing.allocator.free(stored); try std.testing.expectEqualSlices(u8, &large, stored); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); const entry = (try range.next()).?; try std.testing.expectEqualStrings("large", entry.key); try std.testing.expectEqualSlices(u8, &large, entry.value); try std.testing.expect(try range.next() == null); var snapshot_read = try database.beginRead(); defer snapshot_read.deinit(); var snapshot = snapshot_read.snapshot(); var meta_image: [page.size]u8 = undefined; try readExistingPage(snapshot, tree.meta_page, &meta_image); var meta = try page.Meta.load(&meta_image); const highest_after_large = meta.highestPage(); const overflow_pages = (large.len + page.overflow_capacity - 1) / page.overflow_capacity; var summary = try tree.summarize(); try std.testing.expectEqual(@as(usize, 1), summary.entries); try std.testing.expectEqual(@as(usize, 1), summary.overflow_records); try std.testing.expectEqual(overflow_pages, summary.overflow_pages); try std.testing.expectEqual(large.len, summary.value_bytes); _ = try tree.put("large", "tiny", .{ .durability = .buffered }); const small = (try tree.get(std.testing.allocator, "large")).?; defer std.testing.allocator.free(small); try std.testing.expectEqualStrings("tiny", small); summary = try tree.summarize(); try std.testing.expectEqual(@as(usize, 1), summary.entries); try std.testing.expectEqual(@as(usize, 0), summary.overflow_records); try std.testing.expectEqual(@as(usize, 0), summary.overflow_pages); try std.testing.expectEqual(@as(usize, 4), summary.value_bytes); try refreshTestRead(&snapshot_read, &database); snapshot = snapshot_read.snapshot(); try readExistingPage(snapshot, tree.meta_page, &meta_image); meta = try page.Meta.load(&meta_image); try std.testing.expect(meta.highestPage() <= highest_after_large); try std.testing.expect(meta.freeCount() >= overflow_pages or meta.highestPage() < highest_after_large); const free_after_release = meta.freeCount(); var second: [page.overflow_capacity * 2 + 37]u8 = undefined; fillLargeValue(&second, 91); _ = try tree.put("other", &second, .{ .durability = .buffered }); try refreshTestRead(&snapshot_read, &database); snapshot = snapshot_read.snapshot(); try readExistingPage(snapshot, tree.meta_page, &meta_image); meta = try page.Meta.load(&meta_image); try std.testing.expect(meta.highestPage() <= highest_after_large); if (free_after_release > 0) try std.testing.expect(meta.freeCount() < free_after_release); const other = (try tree.get(std.testing.allocator, "other")).?; defer std.testing.allocator.free(other); try std.testing.expectEqualSlices(u8, &second, other); summary = try tree.summarize(); try std.testing.expectEqual(@as(usize, 2), summary.entries); try std.testing.expectEqual(@as(usize, 1), summary.overflow_records); try std.testing.expectEqual(overflow_pages, summary.overflow_pages); try std.testing.expectEqual(second.len + @as(usize, 4), summary.value_bytes);}test "tree scan projection controls overflow materialization" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 4 }); var tree = try Tree.open(&database, .{}); var record_bytes: [record.overflow_size]u8 = undefined; const encoded = try record.encodeOverflow(&record_bytes, .{ .len = page.overflow_capacity + 1, .first_page = 77, }); var root_image: [page.size]u8 = undefined; var leaf = page.Leaf.init(&root_image, tree.root_page); try leaf.put("dangling", encoded); var meta_image: [page.size]u8 = undefined; _ = page.Meta.init(&meta_image, tree.meta_page, 77); var transaction = try database.beginWrite(); defer transaction.deinit(); try transaction.putPage(tree.meta_page, &meta_image); try transaction.putPage(tree.root_page, &root_image); _ = try transaction.commit(.{ .durability = .buffered }); var key_scan: Scan = undefined; try tree.scan(&key_scan, std.testing.allocator, null, null, .key); defer key_scan.deinit(); const key_entry = (try key_scan.next()).?; try std.testing.expectEqualStrings("dangling", key_entry.key); try std.testing.expectEqual(@as(usize, 0), key_entry.bytes.len); try std.testing.expect(try key_scan.next() == null); var record_scan: Scan = undefined; try tree.scan(&record_scan, std.testing.allocator, null, null, .record); defer record_scan.deinit(); const record_entry = (try record_scan.next()).?; try std.testing.expectEqualStrings("dangling", record_entry.key); const overflow = try record.overflow(record_entry.bytes); try std.testing.expectEqual(@as(u64, page.overflow_capacity + 1), overflow.len); try std.testing.expectEqual(@as(u32, 77), overflow.first_page); try std.testing.expect(try record_scan.next() == null); var decoded: Range = undefined; try tree.range(&decoded, std.testing.allocator, null, null); defer decoded.deinit(); try std.testing.expectError(error.InvalidPage, decoded.next());}test "tree stores ordered keys through file transactions" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); var tree = try Tree.open(&database, .{}); _ = try tree.put("c", "three", .{ .durability = .buffered }); _ = try tree.put("a", "one", .{ .durability = .buffered }); _ = try tree.put("b", "two", .{ .durability = .buffered }); const value = (try tree.get(std.testing.allocator, "b")).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("two", value); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); const first = (try range.next()).?; const second = (try range.next()).?; const third = (try range.next()).?; try std.testing.expectEqualStrings("a", first.key); try std.testing.expectEqualStrings("b", second.key); try std.testing.expectEqualStrings("c", third.key); try std.testing.expect(try range.next() == null);}test "tree delete removes a key from durable root leaf" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); var tree = try Tree.open(&database, .{}); _ = try tree.put("a", "one", .{ .durability = .buffered }); _ = try tree.put("b", "two", .{ .durability = .buffered }); _ = try tree.delete("a", .{ .durability = .buffered }); try std.testing.expect(try tree.get(std.testing.allocator, "a") == null); const value = (try tree.get(std.testing.allocator, "b")).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("two", value);}test "tree synced writes recover after reopen" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); { var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); var tree = try Tree.open(&database, .{}); _ = try tree.put("a", "one", .{}); _ = try tree.put("b", "two", .{}); } var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = recoveredHeader(), }); defer reopened.deinit(); var tree = try Tree.open(&reopened, .{}); const value = (try tree.get(std.testing.allocator, "a")).?; defer std.testing.allocator.free(value); try std.testing.expectEqualStrings("one", value); var range: Range = undefined; try tree.range(&range, std.testing.allocator, "b", null); defer range.deinit(); const entry = (try range.next()).?; try std.testing.expectEqualStrings("b", entry.key); try std.testing.expectEqualStrings("two", entry.value); try std.testing.expect(try range.next() == null);}test "tree reports missing delete and invalid root page" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try std.testing.expectError(error.InvalidPageId, Tree.open(&database, .{ .root_page = 0 })); var tree = try Tree.open(&database, .{}); try std.testing.expectError(error.KeyNotFound, tree.delete("missing", .{ .durability = .buffered }));}fn expectIdentityMatchesEntries(tree: *const Tree, expected_entries: u64) !void { const info = try tree.identity(); try std.testing.expectEqual(expected_entries, info.entries); var rebuilt = lattice.State.empty; var count: u64 = 0; var entries: Range = undefined; try tree.range(&entries, std.testing.allocator, null, null); defer entries.deinit(); while (try entries.next()) |entry| { const state = lattice.entryState(entry.key, entry.value); rebuilt.add(&state); count += 1; } try std.testing.expectEqual(expected_entries, count); try std.testing.expect(info.state.eql(&rebuilt)); try std.testing.expect(std.mem.eql(u8, &tree.digestIdentity(&info), &rebuilt.digest(count))); var traversed = try tree.root(std.testing.allocator); defer traversed.deinit(); try std.testing.expect(std.mem.eql(u8, &tree.digestIdentity(&info), &traversed.hash)); try std.testing.expectEqual(traversed.summary.key_bytes, @as(usize, @intCast(info.key_bytes))); try std.testing.expectEqual(traversed.summary.value_bytes, @as(usize, @intCast(info.value_bytes)));}test "tree identity tracks put update delete and clear" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "identity.db", .wal = "identity.wal" }, .header = testingHeader(), }); defer database.deinit(); var tree = try Tree.open(&database, .{ .identity_page = 3 }); const fresh = try tree.identity(); try std.testing.expectEqual(@as(u64, 0), fresh.entries); try std.testing.expect(fresh.state.isEmpty()); _ = try tree.put("alpha", "one", .{ .durability = .buffered }); _ = try tree.put("beta", "two", .{ .durability = .buffered }); try expectIdentityMatchesEntries(&tree, 2); _ = try tree.put("alpha", "uno", .{ .durability = .buffered }); try expectIdentityMatchesEntries(&tree, 2); _ = try tree.delete("beta", .{ .durability = .buffered }); try expectIdentityMatchesEntries(&tree, 1); _ = try tree.delete("alpha", .{ .durability = .buffered }); const drained = try tree.identity(); try std.testing.expectEqual(@as(u64, 0), drained.entries); try std.testing.expect(drained.state.isEmpty()); _ = try tree.put("gamma", "three", .{ .durability = .buffered }); _ = try tree.clear(.{ .durability = .buffered }); const cleared = try tree.identity(); try std.testing.expectEqual(@as(u64, 0), cleared.entries); try std.testing.expect(cleared.state.isEmpty());}test "tree identity follows overflow values across updates" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "identity.db", .wal = "identity.wal" }, .header = testingHeader(), }); defer database.deinit(); var tree = try Tree.open(&database, .{ .identity_page = 3 }); try database.reserve(.{ .wal_frames = 80 }); var value_buffer: [page.overflow_capacity * 2 + 257]u8 = undefined; for (&value_buffer, 0..) |*byte, index| byte.* = @intCast(index % 251); _ = try tree.put("big", value_buffer[0..], .{ .durability = .buffered }); try expectIdentityMatchesEntries(&tree, 1); _ = try tree.put("big", value_buffer[0 .. page.overflow_capacity + 17], .{ .durability = .buffered }); try expectIdentityMatchesEntries(&tree, 1); _ = try tree.put("big", "small", .{ .durability = .buffered }); try expectIdentityMatchesEntries(&tree, 1); _ = try tree.delete("big", .{ .durability = .buffered }); const drained = try tree.identity(); try std.testing.expectEqual(@as(u64, 0), drained.entries); try std.testing.expect(drained.state.isEmpty());}test "tree identity accumulates across one write batch" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "identity.db", .wal = "identity.wal" }, .header = testingHeader(), }); defer database.deinit(); var tree = try Tree.open(&database, .{ .identity_page = 3 }); var write = try Write.beginTree(&tree); defer write.deinit(); try write.put(&tree, "a", "1"); try write.put(&tree, "b", "2"); try write.put(&tree, "a", "one"); try write.delete(&tree, "b"); _ = try write.commit(.{ .durability = .buffered }); try expectIdentityMatchesEntries(&tree, 1);}test "tree identity survives reopen" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); { var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "identity.db", .wal = "identity.wal" }, .header = testingHeader(), }); defer database.deinit(); var tree = try Tree.open(&database, .{ .identity_page = 3 }); _ = try tree.put("a", "one", .{}); _ = try tree.put("b", "two", .{}); } var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "identity.db", .wal = "identity.wal" }, .header = recoveredHeader(), }); defer reopened.deinit(); var tree = try Tree.open(&reopened, .{ .identity_page = 3 }); try expectIdentityMatchesEntries(&tree, 2); _ = try tree.put("c", "three", .{}); try expectIdentityMatchesEntries(&tree, 3);}test "tree identity requires an identity page" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "identity.db", .wal = "identity.wal" }, .header = testingHeader(), }); defer database.deinit(); var tree = try Tree.open(&database, .{}); try std.testing.expectError(error.TreeIdentityMissing, tree.identity()); try std.testing.expectError( error.InvalidPageId, Tree.open(&database, .{ .identity_page = 2 }), );}test "tree count agrees with the full summary across generated writes" { for ([_]u32{ 3, 0 }) |identity_page| { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "count.db", .wal = "count.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 4096 }); var tree = try Tree.open(&database, .{ .identity_page = identity_page }); try std.testing.expectEqual(@as(usize, 0), try tree.count()); var live: [160]bool = @splat(false); var live_count: usize = 0; var large: [page.overflow_capacity + 97]u8 = undefined; fillLargeValue(&large, 7); var prng = std.Random.DefaultPrng.init(0x5eed_c0de); const random = prng.random(); var step: usize = 0; while (step < 480) : (step += 1) { const slot = random.uintLessThan(usize, live.len); var key_buffer: [512]u8 = undefined; const key = wideKey(&key_buffer, slot); if (live[slot] and random.uintLessThan(u8, 3) == 0) { _ = try tree.delete(key, .{ .durability = .buffered }); live[slot] = false; live_count -= 1; } else { const value = if (random.uintLessThan(u8, 8) == 0) large[0..] else key[0..9]; _ = try tree.put(key, value, .{ .durability = .buffered }); if (!live[slot]) live_count += 1; live[slot] = true; } if (step % 40 == 39) { try std.testing.expectEqual(live_count, try tree.count()); try std.testing.expectEqual(live_count, (try tree.summarize()).entries); } } const summary = try tree.summarize(); try std.testing.expect(summary.max_depth >= 2); try std.testing.expect(summary.overflow_records > 0); try std.testing.expectEqual(summary.entries, try tree.count()); _ = try tree.clear(.{ .durability = .buffered }); try std.testing.expectEqual(@as(usize, 0), try tree.count()); }}test "tree scans and lookups agree with a model across generated trees" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "scan.db", .wal = "scan.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 8192 }); var tree = try Tree.open(&database, .{}); var versions: [400]u32 = @splat(0); var prng = std.Random.DefaultPrng.init(0x5ca1_ab1e); const random = prng.random(); var step: u32 = 1; while (step <= 900) : (step += 1) { const slot = random.uintLessThan(usize, versions.len); var key_buffer: [512]u8 = undefined; const key = wideKey(&key_buffer, slot); if (versions[slot] != 0 and random.uintLessThan(u8, 5) == 0) { _ = try tree.delete(key, .{ .durability = .buffered }); versions[slot] = 0; } else { var value_buffer: [model_value_max]u8 = undefined; _ = try tree.put(key, modelValue(&value_buffer, slot, step), .{ .durability = .buffered }); versions[slot] = step; } if (step % 150 == 0) try expectScansMatchModel(&tree, &versions, random); } const summary = try tree.summarize(); try std.testing.expect(summary.max_depth >= 3); try std.testing.expect(summary.overflow_records > 0);}test "tree scan validates each leaf it reads" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 128 }); var tree = try Tree.open(&database, .{}); var index: usize = 0; while (index < 24) : (index += 1) { var key_buffer: [512]u8 = undefined; _ = try tree.put(wideKey(&key_buffer, index), "v", .{ .durability = .buffered }); } try corruptLastLeaf(&database, &tree); var range: Range = undefined; try tree.range(&range, std.testing.allocator, null, null); defer range.deinit(); var returned: usize = 0; while (true) { const entry = range.next() catch |err| { try std.testing.expectEqual(error.InvalidPage, err); break; }; try std.testing.expect(entry != null); returned += 1; } try std.testing.expect(returned > 0); try std.testing.expect(returned < index); try std.testing.expectError(error.InvalidPage, range.next()); var key_buffer: [512]u8 = undefined; try std.testing.expectError(error.InvalidPage, tree.get(std.testing.allocator, wideKey(&key_buffer, index - 1)));}test "tree scan that fails in place releases its read lease" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 128 }); var tree = try Tree.open(&database, .{}); var key_buffer: [512]u8 = undefined; var index: usize = 0; while (index < 24) : (index += 1) { _ = try tree.put(wideKey(&key_buffer, index), "v", .{ .durability = .buffered }); } try corruptLastLeaf(&database, &tree); var scan: Scan = undefined; const long_end: [page.size + 1]u8 = @splat(0); try std.testing.expectError( error.KeyTooLarge, tree.scan(&scan, std.testing.allocator, null, &long_end, .value), ); try std.testing.expectEqual(@as(u8, 0), database.read_leases.active); try std.testing.expectError( error.InvalidPage, tree.scan(&scan, std.testing.allocator, wideKey(&key_buffer, index - 1), null, .value), ); try std.testing.expectEqual(@as(u8, 0), database.read_leases.active);}test "tree reads mark the pages they validate" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 128 }); var tree = try Tree.open(&database, .{}); const key_count = 24; var key_buffer: [512]u8 = undefined; var index: usize = 0; while (index < key_count) : (index += 1) { _ = try tree.put(wideKey(&key_buffer, index), "v", .{ .durability = .buffered }); } var read = try database.beginRead(); defer read.deinit(); const snapshot = read.snapshot(); const reader = try tree.reader(snapshot); var root_image: [page.size]u8 = undefined; try std.testing.expect(!(try readMarkedPage(snapshot, tree.root_page, &root_image)).checked()); const root = try page.Branch.load(&root_image); const leaves = root.cellCount(); try std.testing.expect(leaves >= 3); try std.testing.expect(try reader.valueLength(wideKey(&key_buffer, 0)) != null); try std.testing.expect(try testPageChecked(snapshot, tree.root_page)); try std.testing.expect(try testPageChecked(snapshot, root.childAt(0))); try std.testing.expect(!try testPageChecked(snapshot, root.childAt(1))); try std.testing.expect(try reader.lastKey(&key_buffer) != null); try std.testing.expect(try testPageChecked(snapshot, root.childAt(leaves - 1))); try std.testing.expect(!try testPageChecked(snapshot, root.childAt(1))); var keys: Scan = undefined; try reader.scan(&keys, std.testing.allocator, null, null, .key); defer keys.deinit(); var scanned: usize = 0; while (try keys.next()) |_| scanned += 1; try std.testing.expectEqual(@as(usize, key_count), scanned); var child: usize = 0; while (child < leaves) : (child += 1) { try std.testing.expect(try testPageChecked(snapshot, root.childAt(child))); }}test "tree write validates each snapshot leaf it reads" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 128 }); var tree = try Tree.open(&database, .{}); const key_count = 24; var key_buffer: [512]u8 = undefined; var index: usize = 0; while (index < key_count) : (index += 1) { _ = try tree.put(wideKey(&key_buffer, index), "v", .{ .durability = .buffered }); } try corruptLastLeaf(&database, &tree); var write = try Write.beginTree(&tree); defer write.deinit(); try write.put(&tree, wideKey(&key_buffer, 0), "first"); try write.put(&tree, wideKey(&key_buffer, 0), "again"); const last = write.put(&tree, wideKey(&key_buffer, key_count - 1), "last"); try std.testing.expectError(error.InvalidPage, last);}test "tree write trusts a snapshot page only after validating it" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); var write = try Write.begin(&database, .{}); defer write.deinit(); const page_id = 3; const colliding = page_id + validated_page_capacity; var valid: [page.size]u8 = undefined; var leaf = page.Leaf.init(&valid, page_id); try leaf.put("key", "value"); var corrupt = valid; corrupt[leaf_flags_low_byte] = 1; const valid_page: SourcedPage = .{ .bytes = &valid, .source = .snapshot }; const corrupt_page: SourcedPage = .{ .bytes = &corrupt, .source = .snapshot }; try std.testing.expectError(error.InvalidPage, write.treePage(page_id, corrupt_page)); try std.testing.expectError(error.InvalidPage, write.treePage(page_id, corrupt_page)); _ = try write.treePage(page_id, valid_page); _ = try write.treePage(page_id, valid_page); try std.testing.expectError(error.InvalidPage, write.treePage(colliding, corrupt_page)); try std.testing.expectError(error.InvalidPage, write.treePage(colliding, corrupt_page));}test "tree write edits the pages it staged in place" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "tree.db", .wal = "tree.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 256 }); var tree = try Tree.open(&database, .{}); _ = try tree.put("seed", "v", .{ .durability = .buffered }); var write = try Write.beginTree(&tree); defer write.deinit(); var scratch: [page.size]u8 = undefined; const copied = try write.readRootPage(&tree, &scratch); try std.testing.expectEqual(@intFromPtr(&scratch), @intFromPtr(copied.leaf.bytes)); try write.put(&tree, "seed", "w"); const staged = (try write.transaction.editPage(tree.root_page)).?; const edited = try write.readRootPage(&tree, &scratch); try std.testing.expectEqual(@intFromPtr(staged), @intFromPtr(edited.leaf.bytes)); const key_count = 96; var key_buffer: [512]u8 = undefined; for (0..key_count) |index| try write.put(&tree, wideKey(&key_buffer, index), "w"); for (0..key_count) |index| { const key = wideKey(&key_buffer, index); if (index < 40 or index % 5 == 0) { try write.delete(&tree, key); } else if (index % 2 == 1) { try write.put(&tree, key, "x"); } } try write.delete(&tree, "seed"); _ = try write.commit(.{ .durability = .buffered }); var expected_count: usize = 0; for (0..key_count) |index| { const value = try tree.get(std.testing.allocator, wideKey(&key_buffer, index)); defer if (value) |bytes| std.testing.allocator.free(bytes); if (index < 40 or index % 5 == 0) { try std.testing.expect(value == null); } else { expected_count += 1; const expected = if (index % 2 == 1) "x" else "w"; try std.testing.expectEqualStrings(expected, value.?); } } try std.testing.expectEqual(expected_count, try tree.count());}const model_value_max = page.overflow_capacity + 97;/// Offset of the low byte of a page's flags. `page.kind` does not read it,/// and full validation requires the flags to be zero.const leaf_flags_low_byte = 7;/// Sets the flags of the last leaf under the root branch of `tree` and/// commits it, so the leaf passes `page.kind` and fails validation.fn testPageChecked(snapshot: file.Snapshot, page_id: u32) !bool { var image: [page.size]u8 = undefined; return (try readMarkedPage(snapshot, page_id, &image)).checked();}fn corruptLastLeaf(database: *file.Database, tree: *const Tree) !void { var last_leaf: u32 = 0; var leaf_image: [page.size]u8 = undefined; { var read = try database.beginRead(); defer read.deinit(); var root_image: [page.size]u8 = undefined; try readExistingPage(read.snapshot(), tree.root_page, &root_image); const root = try page.Branch.load(&root_image); try std.testing.expect(root.cellCount() >= 2); last_leaf = root.childAt(root.cellCount() - 1); try readExistingPage(read.snapshot(), last_leaf, &leaf_image); _ = try page.Leaf.load(&leaf_image); } leaf_image[leaf_flags_low_byte] = 1; var transaction = try database.beginWrite(); defer transaction.deinit(); try transaction.putPage(last_leaf, &leaf_image); _ = try transaction.commit(.{ .durability = .buffered });}/// The value slot `slot` holds after the write at `version`. Every seventh/// version spills into an overflow chain.fn modelValue(buffer: *[model_value_max]u8, slot: usize, version: u32) []const u8 { if (version % 7 == 0) { fillLargeValue(buffer, @intCast(version % 251)); return buffer; } return std.fmt.bufPrint(buffer, "v{d}.{d}", .{ slot, version }) catch unreachable;}/// Checks full scans, bounded scans and point lookups against the model. A/// full scan reads each leaf once. It reads each branch once on the way down/// and rereads a branch above the leaves' parents once per exhausted child,/// so it reads at most twice the tree's branch pages.fn expectScansMatchModel(tree: *const Tree, versions: []const u32, random: std.Random) !void { const summary = try tree.summarize(); { var scan: Scan = undefined; try tree.scan(&scan, std.testing.allocator, null, null, .value); defer scan.deinit(); try expectScanEntries(&scan, versions, 0, versions.len, .value); const stats = scan.stats(); try std.testing.expectEqual(summary.leaf_pages, stats.leaf_pages_visited); try std.testing.expect(stats.branch_pages_visited <= 2 * summary.branch_pages); } var trial: usize = 0; while (trial < 8) : (trial += 1) { const first = random.uintAtMost(usize, versions.len); const second = random.uintAtMost(usize, versions.len); const low = @min(first, second); const high = @max(first, second); const bounded_start = random.boolean(); const bounded_end = random.boolean(); var start_buffer: [512]u8 = undefined; var end_buffer: [512]u8 = undefined; const start = if (bounded_start) wideKey(&start_buffer, low) else null; const end = if (bounded_end) wideKey(&end_buffer, high) else null; const projection: Projection = if (trial % 2 == 0) .key else .value; var scan: Scan = undefined; try tree.scan(&scan, std.testing.allocator, start, end, projection); defer scan.deinit(); try expectScanEntries( &scan, versions, if (bounded_start) low else 0, if (bounded_end) high else versions.len, projection, ); } trial = 0; while (trial < 16) : (trial += 1) { const slot = random.uintLessThan(usize, versions.len); var key_buffer: [512]u8 = undefined; const found = try tree.get(std.testing.allocator, wideKey(&key_buffer, slot)); defer if (found) |bytes| std.testing.allocator.free(bytes); if (versions[slot] == 0) { try std.testing.expect(found == null); } else { var value_buffer: [model_value_max]u8 = undefined; try std.testing.expectEqualSlices(u8, modelValue(&value_buffer, slot, versions[slot]), found.?); } }}fn expectScanEntries(scan: *Scan, versions: []const u32, low: usize, high: usize, projection: Projection) !void { var expected: usize = 0; var slot = low; while (slot < high) : (slot += 1) { if (versions[slot] == 0) continue; const next_entry = try scan.next(); try std.testing.expect(next_entry != null); const entry = next_entry.?; var key_buffer: [512]u8 = undefined; try std.testing.expectEqualSlices(u8, wideKey(&key_buffer, slot), entry.key); switch (projection) { .key => try std.testing.expectEqual(@as(usize, 0), entry.bytes.len), .value => { var value_buffer: [model_value_max]u8 = undefined; try std.testing.expectEqualSlices(u8, modelValue(&value_buffer, slot, versions[slot]), entry.bytes); }, .record => unreachable, } expected += 1; } try std.testing.expect(try scan.next() == null); try std.testing.expectEqual(expected, scan.stats().entries_returned);}fn testingHeader() wal.Header { return .{ .sequence = 201, .salt = .{ .first = 0x1234_4321, .second = 0xabcd_dcba }, };}fn recoveredHeader() wal.Header { return .{ .sequence = 202, .salt = .{ .first = 0x5678_8765, .second = 0xfedc_cdef }, };}fn wideKey(buffer: *[512]u8, index: usize) []const u8 { @memset(buffer, 'x'); _ = std.fmt.bufPrint(buffer[0..9], "k{d:0>8}", .{index}) catch unreachable; return buffer[0..];}fn hasSharedChildHash(before: *const Root, after: *const Root) bool { const before_root = before.rootNode(); const after_root = after.rootNode(); for (before.childIndexes(before_root)) |before_index| { const before_child = before.nodes[before_index]; for (after.childIndexes(after_root)) |after_index| { const after_child = after.nodes[after_index]; if (std.mem.eql(u8, before_child.lower, after_child.lower) and std.mem.eql(u8, before_child.hash[0..], after_child.hash[0..])) return true; } } return false;}fn fillLargeValue(buffer: []u8, seed: u8) void { for (buffer, 0..) |*byte, index| { byte.* = @intCast((index + seed) % 251); }}Audit
| Definitions | 25 |
|---|---|
| Public names | 25 |
| Members | 16 |
| Version | 26.7.0 |
| Revision | daab053ee433 |