lib/sql/src/tree.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const simd = @import("simd");
3 const file = @import("file.zig");
4 const lattice = @import("lattice.zig");
5 const page = @import("page.zig");
6 const record = @import("record.zig");
7 const trace = @import("trace.zig");
8 const wal = @import("wal.zig");
9
10 const Bytes = simd.ScalableTag(u8);
11
12 const Allocator = std.mem.Allocator;
13 const io = std.Options.debug_io;
14
15 pub const Error = file.Error || page.Error || record.Error || error{
16 OutputTooSmall,
17 TreeTooDeep,
18 TreeSpaceMismatch,
19 TreeIdentityMissing,
20 WriteBatchLimitExceeded,
21 WriteBatchRepeated,
22 };
23
24 pub const hash_bytes = 32;
25 pub const Hash = [hash_bytes]u8;
26
27 const max_height: usize = 16;
28 const max_write_batches: usize = 32;
29 const inline_value_max: usize = 1024;
30
31 /// The longest key that a put with an empty value can carry into any tree
32 /// whose keys are all this short. The leaf cell holds the key beside the
33 /// empty value record, and a split can copy the key into a branch cell
34 /// beside a child page number. Both cells must fit `page.cell_bytes_max`.
35 pub const key_bytes_max: usize = page.cell_bytes_max - page.cellBytes(
36 0,
37 @max(record.inlineSize(&.{}) catch unreachable, page.child_size),
38 );
39
40 const Separator = struct {
41 key_bytes: [page.size]u8 = undefined,
42 key_len: usize,
43 child: u32,
44
45 fn init(lower_key: []const u8, child: u32) Error!Separator {
46 if (lower_key.len > page.size) return error.KeyTooLarge;
47 var separator = Separator{
48 .key_len = lower_key.len,
49 .child = child,
50 };
51 @memcpy(separator.key_bytes[0..lower_key.len], lower_key);
52 return separator;
53 }
54
55 fn key(self: *const Separator) []const u8 {
56 return self.key_bytes[0..self.key_len];
57 }
58 };
59
60 const BranchFrame = struct {
61 page_id: u32,
62 index: usize,
63 };
64
65 const DeleteResult = union(enum) {
66 empty,
67 lower: Separator,
68 };
69
70 /// A leaf or branch read for a write, with cells validated or known valid.
71 /// A page the write staged wraps its staged image, so edits to it are
72 /// staged as they happen.
73 const TreePage = union(enum) {
74 leaf: page.Leaf,
75 branch: page.Branch,
76 };
77
78 const PageSource = enum { transaction, snapshot };
79
80 /// A page image a write read for editing, with where it came from.
81 const SourcedPage = struct {
82 bytes: *[page.size]u8,
83 source: PageSource,
84 };
85
86 /// Snapshot pages a write remembers as validated.
87 const validated_page_capacity = 64;
88
89 const PageIdSort = struct {
90 fn desc(_: void, left: u32, right: u32) bool {
91 return left > right;
92 }
93 };
94
95 pub const Projection = enum {
96 key,
97 record,
98 value,
99 };
100
101 pub const ScanEntry = struct {
102 key: []const u8,
103 bytes: []const u8,
104 };
105
106 pub const RootEntry = struct {
107 key: []const u8,
108 value: []const u8,
109 };
110
111 pub const ScanStats = struct {
112 branch_pages_visited: usize = 0,
113 leaf_pages_visited: usize = 0,
114 entries_returned: usize = 0,
115 separator_children_pruned: usize = 0,
116 };
117
118 pub const Summary = struct {
119 branch_pages: usize = 0,
120 leaf_pages: usize = 0,
121 overflow_pages: usize = 0,
122 entries: usize = 0,
123 inline_records: usize = 0,
124 overflow_records: usize = 0,
125 max_depth: usize = 0,
126 key_bytes: usize = 0,
127 record_bytes: usize = 0,
128 value_bytes: usize = 0,
129 };
130
131 pub const NodeKind = enum {
132 leaf,
133 branch,
134 };
135
136 pub const Node = struct {
137 kind: NodeKind,
138 lower: []u8,
139 upper: ?[]u8 = null,
140 depth: usize,
141 summary: Summary,
142 hash: Hash,
143 children_start: usize = 0,
144 children_len: usize = 0,
145 };
146
147 pub const Root = struct {
148 allocator: Allocator,
149 summary: Summary,
150 hash: Hash,
151 subtree: Hash,
152 nodes: []Node,
153 edges: []usize,
154
155 pub fn deinit(self: *Root) void {
156 for (self.nodes) |node| {
157 self.allocator.free(node.lower);
158 if (node.upper) |upper| self.allocator.free(upper);
159 }
160 self.allocator.free(self.nodes);
161 self.allocator.free(self.edges);
162 self.* = undefined;
163 }
164
165 pub fn clone(self: *const Root, allocator: Allocator) Allocator.Error!Root {
166 const nodes = try allocator.alloc(Node, self.nodes.len);
167 var node_count: usize = 0;
168 errdefer {
169 for (nodes[0..node_count]) |node| {
170 allocator.free(node.lower);
171 if (node.upper) |upper| allocator.free(upper);
172 }
173 allocator.free(nodes);
174 }
175 for (self.nodes, nodes) |node, *target| {
176 const lower = try allocator.dupe(u8, node.lower);
177 errdefer allocator.free(lower);
178 const upper = if (node.upper) |bytes| try allocator.dupe(u8, bytes) else null;
179 errdefer if (upper) |bytes| allocator.free(bytes);
180 target.* = .{
181 .kind = node.kind,
182 .lower = lower,
183 .upper = upper,
184 .depth = node.depth,
185 .summary = node.summary,
186 .hash = node.hash,
187 .children_start = node.children_start,
188 .children_len = node.children_len,
189 };
190 node_count += 1;
191 }
192
193 const edges = try allocator.dupe(usize, self.edges);
194 errdefer allocator.free(edges);
195 return .{
196 .allocator = allocator,
197 .summary = self.summary,
198 .hash = self.hash,
199 .subtree = self.subtree,
200 .nodes = nodes,
201 .edges = edges,
202 };
203 }
204
205 pub fn rootNode(self: *const Root) *const Node {
206 return &self.nodes[0];
207 }
208
209 pub fn childIndexes(self: *const Root, node: *const Node) []const usize {
210 return self.edges[node.children_start..][0..node.children_len];
211 }
212
213 pub fn child(self: *const Root, node: *const Node, index: usize) ?*const Node {
214 if (index >= node.children_len) return null;
215 return &self.nodes[self.edges[node.children_start + index]];
216 }
217 };
218
219 pub const RootCache = struct {
220 entries: std.AutoHashMapUnmanaged(u32, CacheEntry) = .empty,
221
222 const CacheEntry = struct {
223 base_generation: u64,
224 end_mark: usize,
225 root: Root,
226 };
227
228 pub fn deinit(self: *RootCache, allocator: Allocator) void {
229 var values = self.entries.valueIterator();
230 while (values.next()) |entry| entry.root.deinit();
231 self.entries.deinit(allocator);
232 self.* = undefined;
233 }
234
235 pub fn find(self: *const RootCache, root_page: u32, base_generation: u64, end_mark: usize) ?*const Root {
236 const entry = self.entries.getPtr(root_page) orelse return null;
237 if (entry.base_generation != base_generation or entry.end_mark != end_mark) return null;
238 return &entry.root;
239 }
240
241 pub fn store(self: *RootCache, allocator: Allocator, root_page: u32, base_generation: u64, end_mark: usize, root: *const Root) Allocator.Error!void {
242 var cloned = try root.clone(allocator);
243 errdefer cloned.deinit();
244 const slot = try self.entries.getOrPut(allocator, root_page);
245 if (slot.found_existing) slot.value_ptr.root.deinit();
246 slot.value_ptr.* = .{
247 .base_generation = base_generation,
248 .end_mark = end_mark,
249 .root = cloned,
250 };
251 }
252 };
253
254 pub fn rootFromEntries(allocator: Allocator, entries: []const RootEntry) Allocator.Error!Root {
255 const sorted = try allocator.dupe(RootEntry, entries);
256 defer allocator.free(sorted);
257 std.mem.sort(RootEntry, sorted, {}, rootEntryLessThan);
258 return try rootFromSortedEntries(allocator, sorted);
259 }
260
261 pub fn rootFromSortedEntries(
262 allocator: Allocator,
263 entries: []const RootEntry,
264 ) Allocator.Error!Root {
265 if (entries.len > 1) {
266 for (entries[0 .. entries.len - 1], entries[1..]) |previous, current| {
267 std.debug.assert(!rootEntryLessThan({}, current, previous));
268 }
269 }
270
271 var logical = lattice.State.empty;
272 var leaf = HashBuilder.init("sql.map.leaf");
273 leaf.writeU64(0);
274 leaf.writeU64(entries.len);
275
276 var summary = Summary{
277 .leaf_pages = 1,
278 .max_depth = 0,
279 };
280 for (entries) |entry| {
281 summary.entries += 1;
282 summary.inline_records += 1;
283 summary.key_bytes += entry.key.len;
284 summary.record_bytes += entry.value.len;
285 summary.value_bytes += entry.value.len;
286 leaf.bytes(entry.key);
287 leaf.bytes(entry.value);
288 const entry_state = lattice.entryState(entry.key, entry.value);
289 logical.add(&entry_state);
290 }
291
292 const nodes = try allocator.alloc(Node, 1);
293 var node_count: usize = 0;
294 errdefer {
295 for (nodes[0..node_count]) |node| {
296 allocator.free(node.lower);
297 if (node.upper) |upper| allocator.free(upper);
298 }
299 allocator.free(nodes);
300 }
301 const lower = try allocator.dupe(u8, "");
302 var lower_in_node = false;
303 errdefer if (!lower_in_node) allocator.free(lower);
304 nodes[0] = .{
305 .kind = .leaf,
306 .lower = lower,
307 .depth = 0,
308 .summary = summary,
309 .hash = leaf.finish(),
310 };
311 lower_in_node = true;
312 node_count = 1;
313
314 const edges = try allocator.alloc(usize, 0);
315 errdefer allocator.free(edges);
316 return .{
317 .allocator = allocator,
318 .summary = summary,
319 .hash = logical.digest(summary.entries),
320 .subtree = nodes[0].hash,
321 .nodes = nodes,
322 .edges = edges,
323 };
324 }
325
326 const free_entry_size: usize = @sizeOf(u32);
327
328 const Allocation = struct {
329 image: [page.size]u8,
330 dirty: bool,
331
332 fn init(database: *const file.Database, snapshot: file.Snapshot, meta_page: u32, reserved_page_max: u32) Error!Allocation {
333 std.debug.assert(meta_page != 0);
334 var loaded = Allocation{
335 .image = undefined,
336 .dirty = false,
337 };
338 if (try snapshot.copyPage(meta_page, &loaded.image)) {
339 var meta = try page.Meta.load(&loaded.image);
340 if (try meta.reserveThrough(reserved_page_max)) loaded.dirty = true;
341 return loaded;
342 }
343 const highest_page = @max(database.pager.databasePageCount(), reserved_page_max);
344 var allocation = Allocation{
345 .image = undefined,
346 .dirty = true,
347 };
348 _ = page.Meta.init(&allocation.image, meta_page, highest_page);
349 return allocation;
350 }
351
352 fn write(self: *Allocation, meta_page: u32, transaction: *file.Transaction) Error!void {
353 if (self.dirty) try transaction.putPage(meta_page, &self.image);
354 }
355 };
356
357 pub const Options = struct {
358 meta_page: u32 = 1,
359 root_page: u32 = 2,
360 identity_page: u32 = 0,
361 reserved_page_max: u32 = 0,
362 };
363
364 pub const TreeIdentity = struct {
365 state: lattice.State,
366 entries: u64,
367 key_bytes: u64,
368 value_bytes: u64,
369 };
370
371 const IdentityScratch = struct {
372 identity_page: u32,
373 entries: u64,
374 key_bytes: u64,
375 value_bytes: u64,
376 state: lattice.State,
377 dirty: bool = false,
378 };
379
380 const OldEntry = struct {
381 state: lattice.State,
382 value_len: u64,
383 };
384
385 const PendingPut = struct {
386 scratch: *IdentityScratch,
387 fresh: lattice.State,
388 key_len: u64,
389 value_len: u64,
390 };
391
392 pub const WriteOptions = struct {
393 meta_page: u32 = 1,
394 reserved_page_max: u32 = 0,
395 };
396
397 pub const Write = struct {
398 database: *file.Database,
399 meta_page: u32,
400 reserved_page_max: u32,
401 transaction: file.Transaction,
402 read: file.ReadLease,
403 snapshot: file.Snapshot,
404 allocation: Allocation,
405 identities: std.AutoHashMapUnmanaged(u32, IdentityScratch),
406 batch_roots: [max_write_batches]u32 = undefined,
407 batch_root_count: usize = 0,
408 /// Snapshot pages this write validated, by page id modulo the
409 /// capacity. The snapshot cannot change during the write, so a page
410 /// validated once stays valid, and a collision costs one more
411 /// validation.
412 validated_pages: [validated_page_capacity]u32 = @splat(0),
413
414 pub fn begin(database: *file.Database, options: WriteOptions) Error!Write {
415 if (options.meta_page == 0) return error.InvalidPageId;
416 const reserved_page_max = @max(options.reserved_page_max, options.meta_page);
417 var transaction = try database.beginWrite();
418 errdefer transaction.deinit();
419 var read = try database.beginRead();
420 errdefer read.deinit();
421 const snapshot = read.snapshot();
422 return .{
423 .database = database,
424 .meta_page = options.meta_page,
425 .reserved_page_max = reserved_page_max,
426 .transaction = transaction,
427 .read = read,
428 .snapshot = snapshot,
429 .allocation = try Allocation.init(database, snapshot, options.meta_page, reserved_page_max),
430 .identities = .empty,
431 };
432 }
433
434 pub fn beginTree(tree: *const Tree) Error!Write {
435 return try Write.begin(tree.database, .{
436 .meta_page = tree.meta_page,
437 .reserved_page_max = tree.reserved_page_max,
438 });
439 }
440
441 pub fn deinit(self: *Write) void {
442 self.identities.deinit(self.database.allocator);
443 self.transaction.deinit();
444 self.read.deinit();
445 self.* = undefined;
446 }
447
448 fn identityScratch(self: *Write, tree: *const Tree) Error!?*IdentityScratch {
449 if (tree.identity_page == 0) return null;
450 const slot = try self.identities.getOrPut(self.database.allocator, tree.root_page);
451 if (!slot.found_existing) {
452 slot.value_ptr.* = .{
453 .identity_page = tree.identity_page,
454 .entries = 0,
455 .key_bytes = 0,
456 .value_bytes = 0,
457 .state = lattice.State.empty,
458 };
459 var image: [page.size]u8 = undefined;
460 if (try self.readPage(tree.identity_page, &image)) {
461 if (!zeroPage(&image)) {
462 const loaded = try page.Identity.load(&image);
463 slot.value_ptr.entries = loaded.entries();
464 slot.value_ptr.key_bytes = loaded.keyBytes();
465 slot.value_ptr.value_bytes = loaded.valueBytes();
466 slot.value_ptr.state = loaded.state();
467 }
468 }
469 }
470 return slot.value_ptr;
471 }
472
473 pub fn put(self: *Write, tree: *Tree, key: []const u8, value: []const u8) Error!void {
474 try self.ensureTree(tree);
475 try tree.putInWrite(self, key, value);
476 }
477
478 pub fn delete(self: *Write, tree: *Tree, key: []const u8) Error!void {
479 try self.ensureTree(tree);
480 try tree.deleteInWrite(self, key);
481 }
482
483 pub fn clear(self: *Write, tree: *Tree) Error!void {
484 try self.ensureTree(tree);
485 try tree.clearInWrite(self);
486 }
487
488 pub fn claimBatch(self: *Write, root_page: u32) Error!void {
489 if (root_page == 0) return error.InvalidPageId;
490 for (self.batch_roots[0..self.batch_root_count]) |claimed| {
491 if (claimed == root_page) return error.WriteBatchRepeated;
492 }
493 if (self.batch_root_count == self.batch_roots.len) {
494 return error.WriteBatchLimitExceeded;
495 }
496 self.batch_roots[self.batch_root_count] = root_page;
497 self.batch_root_count += 1;
498 }
499
500 pub fn allocateRoot(self: *Write) Error!u32 {
501 const phase = trace.scope("tree.write.allocate_root");
502 defer phase.end();
503 const root_page = try self.allocatePage();
504 var image: [page.size]u8 = @splat(0);
505 try self.putPage(root_page, &image);
506 self.reserved_page_max = @max(self.reserved_page_max, root_page);
507 return root_page;
508 }
509
510 fn allocatePage(self: *Write) Error!u32 {
511 var meta = try page.Meta.load(&self.allocation.image);
512 if (meta.isChained() and meta.freeCount() == 0) return try self.refillFreeList(&meta);
513 const page_id = try meta.allocate();
514 self.allocation.dirty = true;
515 return page_id;
516 }
517
518 fn releasePage(self: *Write, root_page: u32, page_id: u32) Error!void {
519 if (page_id == self.meta_page or page_id == root_page) return error.InvalidPageId;
520 var meta = try page.Meta.load(&self.allocation.image);
521 meta.release(page_id) catch |err| switch (err) {
522 error.FreeListFull => {
523 try self.spillFreeList(&meta);
524 try meta.release(page_id);
525 },
526 else => return err,
527 };
528 self.allocation.dirty = true;
529 }
530
531 fn spillFreeList(self: *Write, meta: *page.Meta) Error!void {
532 const chain_page = try meta.allocate();
533 var entries: [page.meta_chain_page_entries + 1]u32 = undefined;
534 const count = try meta.spillEntries(&entries);
535 var fragment: [page.meta_chain_page_entries * free_entry_size]u8 = undefined;
536 for (entries[0..count], 0..) |entry, index| {
537 std.mem.writeInt(u32, fragment[index * free_entry_size ..][0..free_entry_size], entry, .big);
538 }
539 var image: [page.size]u8 = undefined;
540 _ = try page.Overflow.init(&image, chain_page, meta.chainHead(), fragment[0 .. count * free_entry_size]);
541 try self.transaction.putPage(chain_page, &image);
542 try meta.adoptChain(chain_page);
543 self.allocation.dirty = true;
544 }
545
546 fn refillFreeList(self: *Write, meta: *page.Meta) Error!u32 {
547 const head = meta.chainHead();
548 var image: [page.size]u8 = undefined;
549 try self.readExistingPage(head, &image);
550 const overflow = try page.Overflow.load(&image);
551 const content = overflow.content();
552 if (content.len % free_entry_size != 0) return error.InvalidPage;
553 const count = content.len / free_entry_size;
554 var entries: [page.meta_chain_page_entries]u32 = undefined;
555 if (count > entries.len) return error.InvalidPage;
556 for (entries[0..count], 0..) |*entry, index| {
557 entry.* = std.mem.readInt(u32, content[index * free_entry_size ..][0..free_entry_size], .big);
558 }
559 try meta.refillFromChain(overflow.next(), entries[0..count]);
560 self.allocation.dirty = true;
561 return head;
562 }
563
564 pub fn commit(self: *Write, options: file.CommitOptions) Error!file.Commit {
565 var identities = self.identities.valueIterator();
566 while (identities.next()) |scratch| {
567 if (!scratch.dirty) continue;
568 var image: [page.size]u8 = undefined;
569 var identity = page.Identity.init(&image, scratch.identity_page);
570 identity.setEntries(scratch.entries);
571 identity.setKeyBytes(scratch.key_bytes);
572 identity.setValueBytes(scratch.value_bytes);
573 identity.setState(&scratch.state);
574 try self.transaction.putPage(scratch.identity_page, &image);
575 }
576 try self.allocation.write(self.meta_page, &self.transaction);
577 return try self.transaction.commit(options);
578 }
579
580 fn ensureTree(self: *const Write, tree: *const Tree) Error!void {
581 if (self.database != tree.database) return error.TreeSpaceMismatch;
582 if (self.meta_page != tree.meta_page) return error.TreeSpaceMismatch;
583 if (self.reserved_page_max < tree.reserved_page_max) return error.TreeSpaceMismatch;
584 }
585
586 fn readRoot(self: *const Write, tree: *const Tree, image: *[page.size]u8) Error!void {
587 if (try self.readPage(tree.root_page, image)) {
588 if (!zeroPage(image)) return;
589 }
590 _ = page.Leaf.init(image, tree.root_page);
591 }
592
593 fn readExistingPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!void {
594 if (try self.readPage(page_id, image)) return;
595 return error.InvalidPage;
596 }
597
598 fn readPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!bool {
599 if (try self.transaction.getPage(page_id)) |bytes| {
600 image.* = bytes[0..page.size].*;
601 return true;
602 }
603 return try self.snapshot.copyPage(page_id, image);
604 }
605
606 /// Reads a page for editing. A page this write staged comes back as
607 /// its staged image, and a snapshot page as a copy in `scratch`.
608 fn readPageSource(self: *Write, page_id: u32, scratch: *[page.size]u8) Error!?SourcedPage {
609 if (try self.transaction.editPage(page_id)) |staged| {
610 return .{ .bytes = staged, .source = .transaction };
611 }
612 if (try self.snapshot.copyPage(page_id, scratch)) {
613 return .{ .bytes = scratch, .source = .snapshot };
614 }
615 return null;
616 }
617
618 /// Reads the root of `tree` as a leaf or branch. A reserved root that
619 /// was never written reads as an empty leaf in `scratch`.
620 fn readRootPage(self: *Write, tree: *const Tree, scratch: *[page.size]u8) Error!TreePage {
621 const sourced = (try self.readPageSource(tree.root_page, scratch)) orelse
622 return .{ .leaf = page.Leaf.init(scratch, tree.root_page) };
623 if (zeroPage(sourced.bytes)) return .{ .leaf = page.Leaf.init(scratch, tree.root_page) };
624 return try self.treePage(tree.root_page, sourced);
625 }
626
627 /// Reads a leaf or branch named by a branch this write read.
628 fn readTreePage(self: *Write, page_id: u32, scratch: *[page.size]u8) Error!TreePage {
629 const sourced = (try self.readPageSource(page_id, scratch)) orelse
630 return error.InvalidPage;
631 return try self.treePage(page_id, sourced);
632 }
633
634 /// Wraps a leaf or branch image, validating its cells unless this write
635 /// wrote the page or already validated it in the snapshot. Safety
636 /// builds assert that a page skipped that way still validates.
637 fn treePage(self: *Write, page_id: u32, sourced: SourcedPage) Error!TreePage {
638 std.debug.assert(page_id != 0);
639 const slot = &self.validated_pages[page_id % validated_page_capacity];
640 if (sourced.source == .transaction or slot.* == page_id) {
641 if (std.debug.runtime_safety) std.debug.assert(validTreePage(sourced.bytes));
642 return try trustedTreePage(sourced.bytes);
643 }
644 const loaded = try loadTreePage(sourced.bytes);
645 slot.* = page_id;
646 return loaded;
647 }
648
649 fn copyPage(self: *const Write, page_id: u32, image: *[page.size]u8) Error!bool {
650 return try self.readPage(page_id, image);
651 }
652
653 fn putPage(self: *Write, page_id: u32, image: *const [page.size]u8) Error!void {
654 try self.transaction.putPage(page_id, image);
655 }
656 };
657
658 fn validateOptions(options: Options) Error!u32 {
659 if (options.meta_page == 0) return error.InvalidPageId;
660 if (options.root_page == 0) return error.InvalidPageId;
661 if (options.meta_page == options.root_page) return error.InvalidPageId;
662 if (options.identity_page != 0) {
663 if (options.identity_page == options.meta_page) return error.InvalidPageId;
664 if (options.identity_page == options.root_page) return error.InvalidPageId;
665 }
666 return @max(
667 @max(options.reserved_page_max, options.identity_page),
668 @max(options.meta_page, options.root_page),
669 );
670 }
671
672 /// Copies the root page into `image` and returns the mark of the image it
673 /// copied. A root that was never written reads as an empty leaf with no mark.
674 fn readRoot(snapshot: file.Snapshot, root_page: u32, image: *[page.size]u8) Error!file.PageMark {
675 if (try snapshot.copyMarkedPage(root_page, image)) |mark| {
676 if (!zeroPage(image)) return mark;
677 }
678 _ = page.Leaf.init(image, root_page);
679 return .none;
680 }
681
682 /// Reads the leaf that holds `key` into `image`, reading each page on the way
683 /// down into that one buffer, and returns it loaded.
684 fn readLeafFor(
685 snapshot: file.Snapshot,
686 root_page: u32,
687 key: []const u8,
688 image: *[page.size]u8,
689 ) Error!page.Leaf {
690 var mark = try readRoot(snapshot, root_page, image);
691 var depth: usize = 0;
692 while (depth < max_height) : (depth += 1) {
693 switch (try loadMarkedTreePage(image, mark)) {
694 .leaf => |leaf| return leaf,
695 .branch => |branch| mark = try readMarkedPage(snapshot, branch.childFor(key), image),
696 }
697 }
698 return error.TreeTooDeep;
699 }
700
701 fn readValueRecord(
702 allocator: Allocator,
703 snapshot: file.Snapshot,
704 bytes: []const u8,
705 ) Error![]u8 {
706 const value = try allocator.alloc(u8, try valueRecordLength(bytes));
707 errdefer allocator.free(value);
708 return try readValueRecordInto(snapshot, bytes, value);
709 }
710
711 pub const Reader = struct {
712 snapshot: file.Snapshot,
713 meta_page: u32,
714 root_page: u32,
715 identity_page: u32,
716 reserved_page_max: u32,
717
718 pub fn open(snapshot: file.Snapshot, options: Options) Error!Reader {
719 return .{
720 .snapshot = snapshot,
721 .meta_page = options.meta_page,
722 .root_page = options.root_page,
723 .identity_page = options.identity_page,
724 .reserved_page_max = try validateOptions(options),
725 };
726 }
727
728 pub fn identity(self: *const Reader) Error!TreeIdentity {
729 const phase = trace.scope("tree.identity");
730 defer phase.end();
731
732 if (self.identity_page == 0) return error.TreeIdentityMissing;
733 var image: [page.size]u8 = undefined;
734 if (try self.snapshot.copyPage(self.identity_page, &image)) {
735 if (!zeroPage(&image)) {
736 const loaded = try page.Identity.load(&image);
737 return .{
738 .state = loaded.state(),
739 .entries = loaded.entries(),
740 .key_bytes = loaded.keyBytes(),
741 .value_bytes = loaded.valueBytes(),
742 };
743 }
744 }
745 return .{
746 .state = lattice.State.empty,
747 .entries = 0,
748 .key_bytes = 0,
749 .value_bytes = 0,
750 };
751 }
752
753 /// Returns the digest of `identity_value`, an identity this reader read
754 /// from its identity page, through the snapshot's database memo.
755 pub fn digestIdentity(
756 self: *const Reader,
757 identity_value: *const TreeIdentity,
758 ) [lattice.digest_size]u8 {
759 return self.snapshot.digestIdentity(
760 self.identity_page,
761 &identity_value.state,
762 identity_value.entries,
763 );
764 }
765
766 /// Returns how many entries the tree holds in this reader's snapshot, the
767 /// figure a caller sizes a scan's output by. A tree with an identity page
768 /// reads the count its write path keeps there, in one page read. A tree
769 /// without one counts the entries of a key-only scan, which reads each
770 /// branch and leaf page once and no overflow page.
771 pub fn count(self: *const Reader) Error!usize {
772 const phase = trace.scope("tree.count");
773 defer phase.end();
774
775 if (self.identity_page != 0) {
776 return std.math.cast(usize, (try self.identity()).entries) orelse
777 error.ValueTooLarge;
778 }
779 var keys: Scan = undefined;
780 try self.scan(&keys, Allocator.failing, null, null, .key);
781 defer keys.deinit();
782 var entries: usize = 0;
783 while (try keys.next()) |_| entries += 1;
784 return entries;
785 }
786
787 pub fn get(self: *const Reader, allocator: Allocator, key: []const u8) Error!?[]u8 {
788 const phase = trace.scope("tree.get");
789 defer phase.end();
790
791 var image: [page.size]u8 = undefined;
792 const leaf = try readLeafFor(self.snapshot, self.root_page, key, &image);
793 const value_record = leaf.get(key) orelse return null;
794 return try readValueRecord(allocator, self.snapshot, value_record);
795 }
796
797 pub fn valueLength(self: *const Reader, key: []const u8) Error!?usize {
798 const phase = trace.scope("tree.value_length");
799 defer phase.end();
800
801 var image: [page.size]u8 = undefined;
802 const leaf = try readLeafFor(self.snapshot, self.root_page, key, &image);
803 const value_record = leaf.get(key) orelse return null;
804 return try valueRecordLength(value_record);
805 }
806
807 pub fn getInto(self: *const Reader, key: []const u8, target: []u8) Error!?[]u8 {
808 const phase = trace.scope("tree.get_into");
809 defer phase.end();
810
811 var image: [page.size]u8 = undefined;
812 const leaf = try readLeafFor(self.snapshot, self.root_page, key, &image);
813 const value_record = leaf.get(key) orelse return null;
814 return try readValueRecordInto(self.snapshot, value_record, target);
815 }
816
817 pub fn lastKey(self: *const Reader, buffer: []u8) Error!?[]const u8 {
818 const phase = trace.scope("tree.last_key");
819 defer phase.end();
820
821 var image: [page.size]u8 = undefined;
822 var mark = try readRoot(self.snapshot, self.root_page, &image);
823 var depth: usize = 0;
824 while (depth < max_height) : (depth += 1) {
825 switch (try loadMarkedTreePage(&image, mark)) {
826 .leaf => |leaf| {
827 const last = leaf.lastKey() orelse return null;
828 if (last.len > buffer.len) return error.KeyTooLarge;
829 @memcpy(buffer[0..last.len], last);
830 return buffer[0..last.len];
831 },
832 .branch => |branch| {
833 const cells = branch.cellCount();
834 if (cells == 0) return error.InvalidPage;
835 mark = try readMarkedPage(self.snapshot, branch.childAt(cells - 1), &image);
836 },
837 }
838 }
839 return error.TreeTooDeep;
840 }
841
842 /// Starts a range over the entries from `start` up to `end` in `target`.
843 pub fn range(
844 self: *const Reader,
845 target: *Range,
846 allocator: Allocator,
847 start: ?[]const u8,
848 end: ?[]const u8,
849 ) Error!void {
850 const phase = trace.scope("tree.range");
851 defer phase.end();
852 try self.scan(&target.scan, allocator, start, end, .value);
853 }
854
855 /// Starts a scan of the keys from `start` up to `end` in `target`, which
856 /// the scan fills in place.
857 pub fn scan(
858 self: *const Reader,
859 target: *Scan,
860 allocator: Allocator,
861 start: ?[]const u8,
862 end: ?[]const u8,
863 projection: Projection,
864 ) Error!void {
865 const phase = trace.scope("tree.scan");
866 defer phase.end();
867
868 try target.init(
869 allocator,
870 self.snapshot,
871 self.root_page,
872 start,
873 end,
874 projection,
875 );
876 }
877
878 pub fn summarize(self: *const Reader) Error!Summary {
879 const phase = trace.scope("tree.summarize");
880 defer phase.end();
881
882 var root_image: [page.size]u8 = undefined;
883 _ = try readRoot(self.snapshot, self.root_page, &root_image);
884 var summary = Summary{};
885 try summarizePage(self.snapshot, &root_image, 0, &summary);
886 return summary;
887 }
888 };
889
890 pub const Tree = struct {
891 database: *file.Database,
892 meta_page: u32,
893 root_page: u32,
894 identity_page: u32,
895 reserved_page_max: u32,
896
897 pub fn open(database: *file.Database, options: Options) Error!Tree {
898 const reserved_page_max = try validateOptions(options);
899 return .{
900 .database = database,
901 .meta_page = options.meta_page,
902 .root_page = options.root_page,
903 .identity_page = options.identity_page,
904 .reserved_page_max = reserved_page_max,
905 };
906 }
907
908 pub fn reader(self: *const Tree, snapshot: file.Snapshot) Error!Reader {
909 return .{
910 .snapshot = snapshot,
911 .meta_page = self.meta_page,
912 .root_page = self.root_page,
913 .identity_page = self.identity_page,
914 .reserved_page_max = self.reserved_page_max,
915 };
916 }
917
918 pub fn identity(self: *const Tree) Error!TreeIdentity {
919 var read = try self.database.beginRead();
920 defer read.deinit();
921 const opened = try self.reader(read.snapshot());
922 return try opened.identity();
923 }
924
925 /// Returns the digest of `identity_value`, an identity this tree read
926 /// from its identity page, through its database's memo.
927 pub fn digestIdentity(
928 self: *const Tree,
929 identity_value: *const TreeIdentity,
930 ) [lattice.digest_size]u8 {
931 return self.database.digest_memo.digest(
932 self.identity_page,
933 &identity_value.state,
934 identity_value.entries,
935 );
936 }
937
938 pub fn get(self: *const Tree, allocator: Allocator, key: []const u8) Error!?[]u8 {
939 var read = try self.database.beginRead();
940 defer read.deinit();
941 const opened = try self.reader(read.snapshot());
942 return try opened.get(allocator, key);
943 }
944
945 pub fn valueLength(self: *const Tree, key: []const u8) Error!?usize {
946 var read = try self.database.beginRead();
947 defer read.deinit();
948 const opened = try self.reader(read.snapshot());
949 return try opened.valueLength(key);
950 }
951
952 pub fn getInto(self: *const Tree, key: []const u8, target: []u8) Error!?[]u8 {
953 var read = try self.database.beginRead();
954 defer read.deinit();
955 const opened = try self.reader(read.snapshot());
956 return try opened.getInto(key, target);
957 }
958
959 pub fn lastKey(self: *const Tree, buffer: []u8) Error!?[]const u8 {
960 var read = try self.database.beginRead();
961 defer read.deinit();
962 const opened = try self.reader(read.snapshot());
963 return try opened.lastKey(buffer);
964 }
965
966 pub fn put(self: *Tree, key: []const u8, value: []const u8, options: file.CommitOptions) Error!file.Commit {
967 const phase = trace.scope("tree.put");
968 defer phase.end();
969
970 var write = try Write.beginTree(self);
971 defer write.deinit();
972 try write.put(self, key, value);
973 return try write.commit(options);
974 }
975
976 fn putInWrite(self: *Tree, write: *Write, key: []const u8, value: []const u8) Error!void {
977 var pending_storage: PendingPut = undefined;
978 var pending: ?*PendingPut = null;
979 if (try write.identityScratch(self)) |scratch| {
980 var hasher = lattice.EntryHasher.init(key);
981 hasher.update(value);
982 pending_storage = .{
983 .scratch = scratch,
984 .fresh = hasher.finish(),
985 .key_len = key.len,
986 .value_len = value.len,
987 };
988 pending = &pending_storage;
989 }
990
991 var inline_buffer: [inline_value_max + 1]u8 = undefined;
992 var overflow_buffer: [record.overflow_size]u8 = undefined;
993 const value_record = try self.writeValueRecord(write, value, &inline_buffer, &overflow_buffer);
994 var root_scratch: [page.size]u8 = undefined;
995 switch (try write.readRootPage(self, &root_scratch)) {
996 .leaf => |leaf| try self.putRootLeaf(write, leaf, key, value_record, pending),
997 .branch => |branch| try self.putRootBranch(write, branch, key, value_record, pending),
998 }
999 }
1000
1001 fn applyPutIdentity(self: *const Tree, write: *Write, pending: ?*PendingPut, key: []const u8, old_record: ?[]const u8) Error!void {
1002 const pending_put = pending orelse return;
1003 if (old_record) |encoded| {
1004 const old = try self.entryStateFromRecord(write, key, encoded);
1005 pending_put.scratch.state.subtract(&old.state);
1006 pending_put.scratch.value_bytes -= old.value_len;
1007 } else {
1008 pending_put.scratch.entries += 1;
1009 pending_put.scratch.key_bytes += pending_put.key_len;
1010 }
1011 pending_put.scratch.value_bytes += pending_put.value_len;
1012 pending_put.scratch.state.add(&pending_put.fresh);
1013 pending_put.scratch.dirty = true;
1014 }
1015
1016 fn applyDeleteIdentity(self: *const Tree, write: *Write, scratch: ?*IdentityScratch, key: []const u8, old_record: []const u8) Error!void {
1017 const identity_scratch = scratch orelse return;
1018 const old = try self.entryStateFromRecord(write, key, old_record);
1019 identity_scratch.state.subtract(&old.state);
1020 identity_scratch.entries -= 1;
1021 identity_scratch.key_bytes -= key.len;
1022 identity_scratch.value_bytes -= old.value_len;
1023 identity_scratch.dirty = true;
1024 }
1025
1026 fn entryStateFromRecord(self: *const Tree, write: *Write, key: []const u8, value_record: []const u8) Error!OldEntry {
1027 _ = self;
1028 var hasher = lattice.EntryHasher.init(key);
1029 var value_len: u64 = 0;
1030 switch (try record.kind(value_record)) {
1031 .inline_value => {
1032 const inline_value = try record.inlineValue(value_record);
1033 value_len = inline_value.len;
1034 hasher.update(inline_value);
1035 },
1036 .overflow => {
1037 const overflow = try record.overflow(value_record);
1038 value_len = overflow.len;
1039 var remaining = try overflowLengthAsUsize(overflow.len);
1040 var page_id = overflow.first_page;
1041 while (page_id != 0) {
1042 var image: [page.size]u8 = undefined;
1043 try write.readExistingPage(page_id, &image);
1044 const overflow_page = try page.Overflow.load(&image);
1045 const expected = @min(page.overflow_capacity, remaining);
1046 if (overflow_page.content().len != expected) return error.InvalidPage;
1047 hasher.update(overflow_page.content());
1048 const next_page = overflow_page.next();
1049 remaining -= expected;
1050 if (remaining == 0 and next_page != 0) return error.InvalidPage;
1051 if (remaining > 0 and next_page == 0) return error.InvalidPage;
1052 page_id = next_page;
1053 }
1054 if (remaining != 0) return error.InvalidPage;
1055 },
1056 }
1057 return .{ .state = hasher.finish(), .value_len = value_len };
1058 }
1059
1060 pub fn delete(self: *Tree, key: []const u8, options: file.CommitOptions) Error!file.Commit {
1061 const phase = trace.scope("tree.delete");
1062 defer phase.end();
1063
1064 var write = try Write.beginTree(self);
1065 defer write.deinit();
1066 try write.delete(self, key);
1067 return try write.commit(options);
1068 }
1069
1070 fn deleteInWrite(self: *Tree, write: *Write, key: []const u8) Error!void {
1071 const scratch = try write.identityScratch(self);
1072 var root_scratch: [page.size]u8 = undefined;
1073 switch (try write.readRootPage(self, &root_scratch)) {
1074 .leaf => |loaded| {
1075 var leaf = loaded;
1076 const old_record = leaf.get(key) orelse return error.KeyNotFound;
1077 try self.applyDeleteIdentity(write, scratch, key, old_record);
1078 const old_overflow = try overflowRefOrNull(old_record);
1079 try leaf.delete(key);
1080 if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);
1081 try write.putPage(self.root_page, leaf.bytes);
1082 },
1083 .branch => |branch| try self.deleteRootBranch(write, branch, key, scratch),
1084 }
1085 }
1086
1087 pub fn clear(self: *Tree, options: file.CommitOptions) Error!file.Commit {
1088 const phase = trace.scope("tree.clear");
1089 defer phase.end();
1090
1091 var write = try Write.beginTree(self);
1092 defer write.deinit();
1093 try write.clear(self);
1094 return try write.commit(options);
1095 }
1096
1097 fn clearInWrite(self: *Tree, write: *Write) Error!void {
1098 var root_image: [page.size]u8 = undefined;
1099 try write.readRoot(self, &root_image);
1100 var pages: std.ArrayList(u32) = .empty;
1101 defer pages.deinit(write.database.allocator);
1102 try self.collectReleasedPages(write, &root_image, 0, &pages);
1103 std.mem.sort(u32, pages.items, {}, PageIdSort.desc);
1104 for (pages.items) |page_id| try write.releasePage(self.root_page, page_id);
1105 _ = page.Leaf.init(&root_image, self.root_page);
1106 try write.putPage(self.root_page, &root_image);
1107 if (try write.identityScratch(self)) |scratch| {
1108 scratch.state = lattice.State.empty;
1109 scratch.entries = 0;
1110 scratch.key_bytes = 0;
1111 scratch.value_bytes = 0;
1112 scratch.dirty = true;
1113 }
1114 }
1115
1116 pub fn range(
1117 self: *const Tree,
1118 target: *Range,
1119 allocator: Allocator,
1120 start: ?[]const u8,
1121 end: ?[]const u8,
1122 ) Error!void {
1123 var read = try self.database.beginRead();
1124 defer read.deinit();
1125 const opened = try self.reader(read.snapshot());
1126 try opened.range(target, allocator, start, end);
1127 }
1128
1129 pub fn scan(
1130 self: *const Tree,
1131 target: *Scan,
1132 allocator: Allocator,
1133 start: ?[]const u8,
1134 end: ?[]const u8,
1135 projection: Projection,
1136 ) Error!void {
1137 var read = try self.database.beginRead();
1138 defer read.deinit();
1139 const opened = try self.reader(read.snapshot());
1140 try opened.scan(target, allocator, start, end, projection);
1141 }
1142
1143 pub fn summarize(self: *const Tree) Error!Summary {
1144 var read = try self.database.beginRead();
1145 defer read.deinit();
1146 const opened = try self.reader(read.snapshot());
1147 return try opened.summarize();
1148 }
1149
1150 pub fn count(self: *const Tree) Error!usize {
1151 var read = try self.database.beginRead();
1152 defer read.deinit();
1153 const opened = try self.reader(read.snapshot());
1154 return try opened.count();
1155 }
1156
1157 pub fn summarizeIn(self: *const Tree, write: *const Write) Error!Summary {
1158 const phase = trace.scope("tree.summarize_in");
1159 defer phase.end();
1160
1161 try write.ensureTree(self);
1162 var root_image: [page.size]u8 = undefined;
1163 try write.readRoot(self, &root_image);
1164 var summary = Summary{};
1165 try summarizePage(write, &root_image, 0, &summary);
1166 return summary;
1167 }
1168
1169 pub fn root(self: *const Tree, allocator: Allocator) Error!Root {
1170 const phase = trace.scope("tree.root");
1171 defer phase.end();
1172
1173 var read = try self.database.beginRead();
1174 defer read.deinit();
1175 const snapshot = read.snapshot();
1176 if (self.database.tree_roots.find(self.root_page, snapshot.view.base_generation, snapshot.view.end_mark)) |cached| {
1177 return try cached.clone(allocator);
1178 }
1179 var root_image: [page.size]u8 = undefined;
1180 _ = try readRoot(snapshot, self.root_page, &root_image);
1181 var build = RootBuild.init(allocator);
1182 errdefer build.deinit();
1183 _ = try build.appendNode(snapshot, &root_image, &.{}, null, 0);
1184 const built = try build.finish();
1185 self.database.tree_roots.store(
1186 self.database.allocator,
1187 self.root_page,
1188 snapshot.view.base_generation,
1189 snapshot.view.end_mark,
1190 &built,
1191 ) catch {};
1192 return built;
1193 }
1194
1195 fn putRootLeaf(
1196 self: *Tree,
1197 write: *Write,
1198 loaded: page.Leaf,
1199 key: []const u8,
1200 value_record: []const u8,
1201 pending: ?*PendingPut,
1202 ) Error!void {
1203 var leaf = loaded;
1204 const root_image = leaf.bytes;
1205 const old_record = leaf.get(key);
1206 try self.applyPutIdentity(write, pending, key, old_record);
1207 const old_overflow = try overflowRefOrNull(old_record);
1208 leaf.put(key, value_record) catch |err| switch (err) {
1209 error.PageFull => {
1210 const first_child = try write.allocatePage();
1211 const second_child = try write.allocatePage();
1212 var left_image: [page.size]u8 = undefined;
1213 var right_image: [page.size]u8 = undefined;
1214 var left = page.Leaf.init(&left_image, first_child);
1215 var right = page.Leaf.init(&right_image, second_child);
1216 const separator = leaf.splitPut(&left, &right, key, value_record) catch |split_err| switch (split_err) {
1217 error.PageFull => return error.KeyTooLarge,
1218 else => return split_err,
1219 };
1220 var branch = page.Branch.init(root_image, self.root_page);
1221 try branch.put(&.{}, first_child);
1222 try branch.put(separator, second_child);
1223 if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);
1224 try write.putPage(self.root_page, root_image);
1225 try write.putPage(first_child, &left_image);
1226 try write.putPage(second_child, &right_image);
1227 return;
1228 },
1229 else => return err,
1230 };
1231 if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);
1232 try write.putPage(self.root_page, root_image);
1233 }
1234
1235 fn putRootBranch(
1236 self: *Tree,
1237 write: *Write,
1238 loaded: page.Branch,
1239 key: []const u8,
1240 value_record: []const u8,
1241 pending: ?*PendingPut,
1242 ) Error!void {
1243 var branch = loaded;
1244 const root_image = branch.bytes;
1245 const child_id = branch.childFor(key);
1246 const split = (try self.putNonRoot(write, child_id, key, value_record, 1, pending)) orelse return;
1247 branch.put(split.key(), split.child) catch |err| switch (err) {
1248 error.PageFull => {
1249 const left_child = try write.allocatePage();
1250 const right_child = try write.allocatePage();
1251 var left_image: [page.size]u8 = undefined;
1252 var right_image: [page.size]u8 = undefined;
1253 var left = page.Branch.init(&left_image, left_child);
1254 var right = page.Branch.init(&right_image, right_child);
1255 const separator = branch.splitPut(&left, &right, split.key(), split.child) catch |split_err| switch (split_err) {
1256 error.PageFull => return error.KeyTooLarge,
1257 else => return split_err,
1258 };
1259 const left_lower = left.firstLower() orelse return error.InvalidPage;
1260 var new_root = page.Branch.init(root_image, self.root_page);
1261 try new_root.put(left_lower, left_child);
1262 try new_root.put(separator, right_child);
1263 try write.putPage(self.root_page, root_image);
1264 try write.putPage(left_child, &left_image);
1265 try write.putPage(right_child, &right_image);
1266 return;
1267 },
1268 else => return err,
1269 };
1270 try write.putPage(self.root_page, root_image);
1271 }
1272
1273 fn putNonRoot(self: *Tree, write: *Write, page_id: u32, key: []const u8, value_record: []const u8, depth: usize, pending: ?*PendingPut) Error!?Separator {
1274 if (depth >= max_height) return error.TreeTooDeep;
1275 var scratch: [page.size]u8 = undefined;
1276 return switch (try write.readTreePage(page_id, &scratch)) {
1277 .leaf => |leaf| try self.putLeaf(write, leaf, page_id, key, value_record, pending),
1278 .branch => |branch| try self.putBranch(
1279 write,
1280 branch,
1281 page_id,
1282 key,
1283 value_record,
1284 depth,
1285 pending,
1286 ),
1287 };
1288 }
1289
1290 fn putLeaf(
1291 self: *Tree,
1292 write: *Write,
1293 loaded: page.Leaf,
1294 page_id: u32,
1295 key: []const u8,
1296 value_record: []const u8,
1297 pending: ?*PendingPut,
1298 ) Error!?Separator {
1299 var leaf = loaded;
1300 const image = leaf.bytes;
1301 const old_record = leaf.get(key);
1302 try self.applyPutIdentity(write, pending, key, old_record);
1303 const old_overflow = try overflowRefOrNull(old_record);
1304 leaf.put(key, value_record) catch |err| switch (err) {
1305 error.PageFull => {
1306 const new_child = try write.allocatePage();
1307 var left_image: [page.size]u8 = undefined;
1308 var right_image: [page.size]u8 = undefined;
1309 var left = page.Leaf.init(&left_image, page_id);
1310 var right = page.Leaf.init(&right_image, new_child);
1311 const separator = leaf.splitPut(&left, &right, key, value_record) catch |split_err| switch (split_err) {
1312 error.PageFull => return error.KeyTooLarge,
1313 else => return split_err,
1314 };
1315 if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);
1316 try write.putPage(page_id, &left_image);
1317 try write.putPage(new_child, &right_image);
1318 return try Separator.init(separator, new_child);
1319 },
1320 else => return err,
1321 };
1322 if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);
1323 try write.putPage(page_id, image);
1324 return null;
1325 }
1326
1327 fn putBranch(
1328 self: *Tree,
1329 write: *Write,
1330 loaded: page.Branch,
1331 page_id: u32,
1332 key: []const u8,
1333 value_record: []const u8,
1334 depth: usize,
1335 pending: ?*PendingPut,
1336 ) Error!?Separator {
1337 var branch = loaded;
1338 const image = branch.bytes;
1339 const child_id = branch.childFor(key);
1340 const split = (try self.putNonRoot(write, child_id, key, value_record, depth + 1, pending)) orelse return null;
1341 branch.put(split.key(), split.child) catch |err| switch (err) {
1342 error.PageFull => {
1343 const new_child = try write.allocatePage();
1344 var left_image: [page.size]u8 = undefined;
1345 var right_image: [page.size]u8 = undefined;
1346 var left = page.Branch.init(&left_image, page_id);
1347 var right = page.Branch.init(&right_image, new_child);
1348 const separator = branch.splitPut(&left, &right, split.key(), split.child) catch |split_err| switch (split_err) {
1349 error.PageFull => return error.KeyTooLarge,
1350 else => return split_err,
1351 };
1352 try write.putPage(page_id, &left_image);
1353 try write.putPage(new_child, &right_image);
1354 return try Separator.init(separator, new_child);
1355 },
1356 else => return err,
1357 };
1358 try write.putPage(page_id, image);
1359 return null;
1360 }
1361
1362 fn deleteRootBranch(
1363 self: *Tree,
1364 write: *Write,
1365 loaded: page.Branch,
1366 key: []const u8,
1367 scratch: ?*IdentityScratch,
1368 ) Error!void {
1369 var branch = loaded;
1370 const root_image = branch.bytes;
1371 const child_index = branch.childIndexFor(key);
1372 const child_id = branch.childAt(child_index);
1373 const result = try self.deleteNonRoot(write, child_id, key, 1, scratch);
1374 switch (result) {
1375 .empty => {
1376 try branch.remove(child_index);
1377 try write.releasePage(self.root_page, child_id);
1378 },
1379 .lower => |lower| {
1380 const replacement = if (child_index == 0 and branch.lowerAt(0).len == 0) branch.lowerAt(0) else lower.key();
1381 try replaceLowerBoundIfFits(&branch, child_index, replacement, child_id);
1382 },
1383 }
1384 if (branch.cellCount() == 0) {
1385 _ = page.Leaf.init(root_image, self.root_page);
1386 try write.putPage(self.root_page, root_image);
1387 return;
1388 }
1389 try self.compactRoot(write, root_image, 0);
1390 }
1391
1392 fn deleteNonRoot(self: *Tree, write: *Write, page_id: u32, key: []const u8, depth: usize, scratch: ?*IdentityScratch) Error!DeleteResult {
1393 if (depth >= max_height) return error.TreeTooDeep;
1394 var page_scratch: [page.size]u8 = undefined;
1395 switch (try write.readTreePage(page_id, &page_scratch)) {
1396 .leaf => |loaded| {
1397 var leaf = loaded;
1398 const old_record = leaf.get(key) orelse return error.KeyNotFound;
1399 try self.applyDeleteIdentity(write, scratch, key, old_record);
1400 const old_overflow = try overflowRefOrNull(old_record);
1401 try leaf.delete(key);
1402 if (old_overflow) |overflow| try self.releaseOverflowValue(write, overflow);
1403 if (leaf.cellCount() == 0) return .empty;
1404 try write.putPage(page_id, leaf.bytes);
1405 return .{ .lower = try Separator.init(leaf.firstKey() orelse return error.InvalidPage, page_id) };
1406 },
1407 .branch => |loaded| {
1408 var branch = loaded;
1409 const child_index = branch.childIndexFor(key);
1410 const child_id = branch.childAt(child_index);
1411 const result = try self.deleteNonRoot(write, child_id, key, depth + 1, scratch);
1412 switch (result) {
1413 .empty => {
1414 try branch.remove(child_index);
1415 try write.releasePage(self.root_page, child_id);
1416 },
1417 .lower => |lower| {
1418 const replacement = if (child_index == 0 and branch.lowerAt(0).len == 0) branch.lowerAt(0) else lower.key();
1419 try replaceLowerBoundIfFits(&branch, child_index, replacement, child_id);
1420 },
1421 }
1422 if (branch.cellCount() == 0) return .empty;
1423 try write.putPage(page_id, branch.bytes);
1424 return .{ .lower = try Separator.init(branch.firstLower() orelse return error.InvalidPage, page_id) };
1425 },
1426 }
1427 }
1428
1429 fn replaceLowerBoundIfFits(branch: *page.Branch, index: usize, lower: []const u8, child: u32) Error!void {
1430 branch.replace(index, lower, child) catch |err| switch (err) {
1431 error.PageFull => {},
1432 else => return err,
1433 };
1434 }
1435
1436 fn compactRoot(self: *Tree, write: *Write, root_image: *[page.size]u8, depth: usize) Error!void {
1437 if (depth >= max_height) return error.TreeTooDeep;
1438 switch (try page.kind(root_image)) {
1439 .leaf => try write.putPage(self.root_page, root_image),
1440 .branch => {
1441 const branch = try page.Branch.load(root_image);
1442 if (branch.cellCount() == 1) {
1443 var child: [page.size]u8 = undefined;
1444 const child_id = branch.childAt(0);
1445 try write.readExistingPage(child_id, &child);
1446 try copyRootPage(root_image, &child, self.root_page);
1447 try write.releasePage(self.root_page, child_id);
1448 try self.compactRoot(write, root_image, depth + 1);
1449 return;
1450 }
1451 try write.putPage(self.root_page, root_image);
1452 },
1453 .meta => return error.InvalidPage,
1454 .overflow => return error.InvalidPage,
1455 .identity => return error.InvalidPage,
1456 }
1457 }
1458
1459 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 {
1460 if (value.len <= inline_value_max) return try record.encodeInline(inline_buffer, value);
1461 if (value.len > std.math.maxInt(u64)) return error.ValueTooLarge;
1462 const first_page = try self.writeOverflowValue(write, value);
1463 return try record.encodeOverflow(overflow_buffer, .{
1464 .len = @intCast(value.len),
1465 .first_page = first_page,
1466 });
1467 }
1468
1469 fn writeOverflowValue(self: *Tree, write: *Write, value: []const u8) Error!u32 {
1470 _ = self;
1471 if (value.len == 0) return error.ValueTooLarge;
1472 var offset: usize = 0;
1473 const first_page = try write.allocatePage();
1474 var current_page = first_page;
1475 while (offset < value.len) {
1476 const remaining = value.len - offset;
1477 const chunk_len = @min(page.overflow_capacity, remaining);
1478 const next_page = if (offset + chunk_len < value.len) try write.allocatePage() else 0;
1479 var image: [page.size]u8 = undefined;
1480 _ = try page.Overflow.init(&image, current_page, next_page, value[offset..][0..chunk_len]);
1481 try write.putPage(current_page, &image);
1482 current_page = next_page;
1483 offset += chunk_len;
1484 }
1485 return first_page;
1486 }
1487
1488 fn releaseOverflowValue(self: *const Tree, write: *Write, overflow: record.Overflow) Error!void {
1489 var pages: std.ArrayList(u32) = .empty;
1490 defer pages.deinit(write.database.allocator);
1491 try self.collectOverflowPages(write, overflow, &pages);
1492 for (pages.items) |page_id| try write.releasePage(self.root_page, page_id);
1493 }
1494
1495 fn collectReleasedPages(self: *const Tree, write: *Write, image: *[page.size]u8, depth: usize, pages: *std.ArrayList(u32)) Error!void {
1496 if (depth >= max_height) return error.TreeTooDeep;
1497 switch (try page.kind(image)) {
1498 .leaf => {
1499 const leaf = try page.Leaf.load(image);
1500 var leaf_range = try leaf.range(null, null);
1501 while (leaf_range.next()) |entry| {
1502 if (try overflowRefOrNull(entry.value)) |overflow| try self.collectOverflowPages(write, overflow, pages);
1503 }
1504 },
1505 .branch => {
1506 const branch = try page.Branch.load(image);
1507 var index: usize = 0;
1508 while (index < branch.cellCount()) : (index += 1) {
1509 const child_id = branch.childAt(index);
1510 var child_image: [page.size]u8 = undefined;
1511 try write.readExistingPage(child_id, &child_image);
1512 try self.collectReleasedPages(write, &child_image, depth + 1, pages);
1513 try pages.append(write.database.allocator, child_id);
1514 }
1515 },
1516 .meta => return error.InvalidPage,
1517 .overflow => return error.InvalidPage,
1518 .identity => return error.InvalidPage,
1519 }
1520 }
1521
1522 fn collectOverflowPages(self: *const Tree, write: *Write, overflow: record.Overflow, pages: *std.ArrayList(u32)) Error!void {
1523 _ = self;
1524 var remaining = try overflowLengthAsUsize(overflow.len);
1525 var page_id = overflow.first_page;
1526 while (page_id != 0) {
1527 var image: [page.size]u8 = undefined;
1528 try write.readExistingPage(page_id, &image);
1529 const overflow_page = try page.Overflow.load(&image);
1530 const expected = @min(page.overflow_capacity, remaining);
1531 if (overflow_page.content().len != expected) return error.InvalidPage;
1532 const next_page = overflow_page.next();
1533 try pages.append(write.database.allocator, page_id);
1534 remaining -= expected;
1535 if (remaining == 0 and next_page != 0) return error.InvalidPage;
1536 if (remaining > 0 and next_page == 0) return error.InvalidPage;
1537 page_id = next_page;
1538 }
1539 if (remaining != 0) return error.InvalidPage;
1540 }
1541 };
1542
1543 pub const Range = struct {
1544 scan: Scan,
1545
1546 pub fn deinit(self: *Range) void {
1547 self.scan.deinit();
1548 self.* = undefined;
1549 }
1550
1551 pub fn next(self: *Range) Error!?page.Entry {
1552 if (try self.scan.next()) |entry| {
1553 return .{
1554 .key = entry.key,
1555 .value = entry.bytes,
1556 };
1557 }
1558 return null;
1559 }
1560
1561 pub fn stats(self: *const Range) ScanStats {
1562 return self.scan.stats();
1563 }
1564 };
1565
1566 pub const Scan = struct {
1567 allocator: Allocator,
1568 read: ?file.ReadLease,
1569 snapshot: file.Snapshot,
1570 frames: [max_height]BranchFrame = undefined,
1571 depth: usize = 0,
1572 /// Image of the branch at `frames[depth - 1]`, validated when read. Leaf
1573 /// advances under one parent read only the next leaf.
1574 parent: [page.size]u8 = undefined,
1575 /// Image of the current leaf, validated when read.
1576 leaf: [page.size]u8 = undefined,
1577 value: std.ArrayList(u8) = .empty,
1578 end_key: [page.size]u8 = undefined,
1579 end_len: ?usize,
1580 index: usize,
1581 projection: Projection,
1582 observed: ScanStats = .{},
1583 /// The first error `next` returned. A page that fails to read or validate
1584 /// can be left in `leaf` or `parent`, so the scan stops there and returns
1585 /// the same error from then on.
1586 failure: ?Error = null,
1587
1588 /// Fills `self` in place, since a scan holds three page-sized buffers
1589 /// that a return by value would copy through each caller.
1590 fn init(
1591 self: *Scan,
1592 allocator: Allocator,
1593 snapshot: file.Snapshot,
1594 root_page: u32,
1595 start: ?[]const u8,
1596 end: ?[]const u8,
1597 projection: Projection,
1598 ) Error!void {
1599 const retained = try snapshot.retain();
1600 self.* = .{
1601 .allocator = allocator,
1602 .read = retained,
1603 .snapshot = snapshot,
1604 .end_len = null,
1605 .index = 0,
1606 .projection = projection,
1607 };
1608 errdefer if (self.read) |*read| read.deinit();
1609 if (end) |key| {
1610 if (key.len > page.size) return error.KeyTooLarge;
1611 @memcpy(self.end_key[0..key.len], key);
1612 self.end_len = key.len;
1613 }
1614 const root_mark = try readRoot(snapshot, root_page, &self.leaf);
1615 try self.descend(root_page, root_mark, start);
1616 const leaf = page.Leaf.fromValidated(&self.leaf);
1617 const leaf_range = try leaf.range(start, self.endSlice());
1618 self.index = leaf_range.index;
1619 }
1620
1621 pub fn deinit(self: *Scan) void {
1622 self.value.deinit(self.allocator);
1623 if (self.read) |*read| read.deinit();
1624 self.* = undefined;
1625 }
1626
1627 pub fn next(self: *Scan) Error!?ScanEntry {
1628 if (self.failure) |failure| return failure;
1629 return self.nextEntry() catch |err| {
1630 self.failure = err;
1631 return err;
1632 };
1633 }
1634
1635 fn nextEntry(self: *Scan) Error!?ScanEntry {
1636 while (true) {
1637 const leaf = page.Leaf.fromValidated(&self.leaf);
1638 var leaf_range = page.Range{
1639 .leaf = &leaf,
1640 .end = self.endSlice(),
1641 .index = self.index,
1642 };
1643 if (leaf_range.next()) |entry| {
1644 self.index = leaf_range.index;
1645 self.observed.entries_returned += 1;
1646 return .{
1647 .key = entry.key,
1648 .bytes = try self.valueFor(entry.value),
1649 };
1650 }
1651 if (!(try self.advanceLeaf())) return null;
1652 }
1653 }
1654
1655 fn valueFor(self: *Scan, bytes: []const u8) Error![]const u8 {
1656 return switch (self.projection) {
1657 .key => "",
1658 .record => bytes,
1659 .value => value: {
1660 if (bytes.len == 0) return error.InvalidRecord;
1661 break :value switch (bytes[0]) {
1662 record.inline_tag => bytes[1..],
1663 record.overflow_tag => overflow_value: {
1664 const overflow = try record.overflow(bytes);
1665 const len = try overflowLengthAsUsize(overflow.len);
1666 try self.value.resize(self.allocator, len);
1667 try readOverflowValueInto(self.snapshot, overflow, self.value.items);
1668 break :overflow_value self.value.items;
1669 },
1670 else => error.InvalidRecord,
1671 };
1672 },
1673 };
1674 }
1675
1676 pub fn stats(self: *const Scan) ScanStats {
1677 return self.observed;
1678 }
1679
1680 fn endSlice(self: *const Scan) ?[]const u8 {
1681 const len = self.end_len orelse return null;
1682 return self.end_key[0..len];
1683 }
1684
1685 /// Descends from the page image in `self.leaf`, which is `page_id` with
1686 /// mark `page_mark`, to the leaf that holds `start`, or to the leftmost
1687 /// leaf. Each page is read into scan storage and loaded once. The last
1688 /// branch passed stays in `self.parent`.
1689 fn descend(self: *Scan, page_id: u32, page_mark: file.PageMark, start: ?[]const u8) Error!void {
1690 var current_page = page_id;
1691 var mark = page_mark;
1692 while (true) {
1693 switch (try loadMarkedTreePage(&self.leaf, mark)) {
1694 .leaf => {
1695 self.observed.leaf_pages_visited += 1;
1696 return;
1697 },
1698 .branch => {
1699 if (self.depth >= max_height) return error.TreeTooDeep;
1700 self.parent = self.leaf;
1701 const branch = page.Branch.fromValidated(&self.parent);
1702 self.observed.branch_pages_visited += 1;
1703 const index = if (start) |key| branch.childIndexFor(key) else 0;
1704 self.frames[self.depth] = .{
1705 .page_id = current_page,
1706 .index = index,
1707 };
1708 self.depth += 1;
1709 current_page = branch.childAt(index);
1710 mark = try readMarkedPage(self.snapshot, current_page, &self.leaf);
1711 },
1712 }
1713 }
1714 }
1715
1716 /// Moves to the next leaf in key order. The branch above the current leaf
1717 /// is already in `self.parent`, so an advance to a sibling reads one page.
1718 /// Only an advance past the parent's last child rereads a higher branch.
1719 fn advanceLeaf(self: *Scan) Error!bool {
1720 while (self.depth > 0) {
1721 const frame = &self.frames[self.depth - 1];
1722 const branch = page.Branch.fromValidated(&self.parent);
1723 const next_index = frame.index + 1;
1724 if (next_index < branch.cellCount()) {
1725 if (!self.childStartsBeforeEnd(branch.lowerAt(next_index))) {
1726 self.observed.separator_children_pruned += branch.cellCount() - next_index;
1727 return false;
1728 }
1729 frame.index = next_index;
1730 const child = branch.childAt(next_index);
1731 const mark = try readMarkedPage(self.snapshot, child, &self.leaf);
1732 try self.descend(child, mark, null);
1733 self.index = 0;
1734 return true;
1735 }
1736 self.depth -= 1;
1737 if (self.depth > 0) {
1738 const parent_page = self.frames[self.depth - 1].page_id;
1739 const mark = try readMarkedPage(self.snapshot, parent_page, &self.parent);
1740 switch (try loadMarkedTreePage(&self.parent, mark)) {
1741 .leaf => return error.InvalidPage,
1742 .branch => self.observed.branch_pages_visited += 1,
1743 }
1744 }
1745 }
1746 return false;
1747 }
1748
1749 fn childStartsBeforeEnd(self: *const Scan, lower_key: []const u8) bool {
1750 const end = self.endSlice() orelse return true;
1751 return simd.order(Bytes, lower_key, end) == .lt;
1752 }
1753 };
1754
1755 const RootBuild = struct {
1756 allocator: Allocator,
1757 nodes: std.ArrayList(Node) = .empty,
1758 edges: std.ArrayList(usize) = .empty,
1759 logical: lattice.State,
1760
1761 fn init(allocator: Allocator) RootBuild {
1762 return .{
1763 .allocator = allocator,
1764 .logical = lattice.State.empty,
1765 };
1766 }
1767
1768 fn deinit(self: *RootBuild) void {
1769 for (self.nodes.items) |node| {
1770 self.allocator.free(node.lower);
1771 if (node.upper) |upper| self.allocator.free(upper);
1772 }
1773 self.nodes.deinit(self.allocator);
1774 self.edges.deinit(self.allocator);
1775 self.* = undefined;
1776 }
1777
1778 fn finish(self: *RootBuild) Allocator.Error!Root {
1779 const summary = self.nodes.items[0].summary;
1780 const subtree = self.nodes.items[0].hash;
1781 const logical = self.logical.digest(summary.entries);
1782 const nodes = try self.nodes.toOwnedSlice(self.allocator);
1783 errdefer {
1784 for (nodes) |node| {
1785 self.allocator.free(node.lower);
1786 if (node.upper) |upper| self.allocator.free(upper);
1787 }
1788 self.allocator.free(nodes);
1789 }
1790 const edges = try self.edges.toOwnedSlice(self.allocator);
1791 errdefer self.allocator.free(edges);
1792 self.nodes = .empty;
1793 self.edges = .empty;
1794 return .{
1795 .allocator = self.allocator,
1796 .summary = summary,
1797 .hash = logical,
1798 .subtree = subtree,
1799 .nodes = nodes,
1800 .edges = edges,
1801 };
1802 }
1803
1804 fn appendNode(self: *RootBuild, snapshot: file.Snapshot, image: *const [page.size]u8, lower: []const u8, upper: ?[]const u8, depth: usize) Error!usize {
1805 if (depth >= max_height) return error.TreeTooDeep;
1806 const owned_lower = try self.allocator.dupe(u8, lower);
1807 var lower_in_nodes = false;
1808 errdefer if (!lower_in_nodes) self.allocator.free(owned_lower);
1809 const owned_upper = if (upper) |bytes| try self.allocator.dupe(u8, bytes) else null;
1810 var upper_in_nodes = owned_upper == null;
1811 errdefer if (!upper_in_nodes) self.allocator.free(owned_upper.?);
1812 const node_index = self.nodes.items.len;
1813 try self.nodes.append(self.allocator, .{
1814 .kind = .leaf,
1815 .lower = owned_lower,
1816 .upper = owned_upper,
1817 .depth = depth,
1818 .summary = .{},
1819 .hash = undefined,
1820 });
1821 lower_in_nodes = true;
1822 upper_in_nodes = true;
1823
1824 var current = image.*;
1825 switch (try page.kind(¤t)) {
1826 .leaf => try self.finishLeaf(snapshot, node_index, ¤t, depth),
1827 .branch => try self.finishBranch(snapshot, node_index, ¤t, depth),
1828 .meta => return error.InvalidPage,
1829 .overflow => return error.InvalidPage,
1830 .identity => return error.InvalidPage,
1831 }
1832 return node_index;
1833 }
1834
1835 fn finishLeaf(self: *RootBuild, snapshot: file.Snapshot, node_index: usize, image: *[page.size]u8, depth: usize) Error!void {
1836 var summary = Summary{
1837 .leaf_pages = 1,
1838 .max_depth = depth,
1839 };
1840 var builder = HashBuilder.init("sql.map.leaf");
1841 builder.writeU64(depth);
1842 const leaf = try page.Leaf.load(image);
1843 builder.writeU64(leaf.cellCount());
1844 var range = try leaf.range(null, null);
1845 while (range.next()) |entry| {
1846 try summarizeEntry(snapshot, entry, &summary);
1847 builder.bytes(entry.key);
1848 try builder.recordValue(snapshot, entry.value);
1849 const entry_state = try latticeEntryFromRecord(snapshot, entry.key, entry.value);
1850 self.logical.add(&entry_state);
1851 }
1852 self.nodes.items[node_index].kind = .leaf;
1853 self.nodes.items[node_index].summary = summary;
1854 self.nodes.items[node_index].hash = builder.finish();
1855 }
1856
1857 fn finishBranch(self: *RootBuild, snapshot: file.Snapshot, node_index: usize, image: *[page.size]u8, depth: usize) Error!void {
1858 var summary = Summary{
1859 .branch_pages = 1,
1860 .max_depth = depth,
1861 };
1862 var builder = HashBuilder.init("sql.map.branch");
1863 builder.writeU64(depth);
1864 const branch = try page.Branch.load(image);
1865 builder.writeU64(branch.cellCount());
1866 var child_indexes: std.ArrayList(usize) = .empty;
1867 defer child_indexes.deinit(self.allocator);
1868 const node_upper = self.nodes.items[node_index].upper;
1869 var index: usize = 0;
1870 while (index < branch.cellCount()) : (index += 1) {
1871 var child_image: [page.size]u8 = undefined;
1872 try readExistingPage(snapshot, branch.childAt(index), &child_image);
1873 const child_upper = if (index + 1 < branch.cellCount()) branch.lowerAt(index + 1) else node_upper;
1874 const child_index = try self.appendNode(snapshot, &child_image, branch.lowerAt(index), child_upper, depth + 1);
1875 try child_indexes.append(self.allocator, child_index);
1876 const child_node = self.nodes.items[child_index];
1877 addSummary(&summary, child_node.summary);
1878 builder.bytes(branch.lowerAt(index));
1879 builder.hash(child_node.hash);
1880 builder.summary(child_node.summary);
1881 }
1882 const children_start = self.edges.items.len;
1883 try self.edges.appendSlice(self.allocator, child_indexes.items);
1884 self.nodes.items[node_index].kind = .branch;
1885 self.nodes.items[node_index].summary = summary;
1886 self.nodes.items[node_index].hash = builder.finish();
1887 self.nodes.items[node_index].children_start = children_start;
1888 self.nodes.items[node_index].children_len = branch.cellCount();
1889 }
1890 };
1891
1892 const HashBuilder = struct {
1893 hasher: std.crypto.hash.sha2.Sha256,
1894
1895 fn init(tag: []const u8) HashBuilder {
1896 var builder = HashBuilder{ .hasher = std.crypto.hash.sha2.Sha256.init(.{}) };
1897 builder.bytes(tag);
1898 return builder;
1899 }
1900
1901 fn finish(self: *HashBuilder) Hash {
1902 var digest: Hash = undefined;
1903 self.hasher.final(&digest);
1904 return digest;
1905 }
1906
1907 fn bytes(self: *HashBuilder, value: []const u8) void {
1908 self.writeU64(value.len);
1909 self.hasher.update(value);
1910 }
1911
1912 fn summary(self: *HashBuilder, value: Summary) void {
1913 self.writeU64(value.branch_pages);
1914 self.writeU64(value.leaf_pages);
1915 self.writeU64(value.overflow_pages);
1916 self.writeU64(value.entries);
1917 self.writeU64(value.inline_records);
1918 self.writeU64(value.overflow_records);
1919 self.writeU64(value.max_depth);
1920 self.writeU64(value.key_bytes);
1921 self.writeU64(value.record_bytes);
1922 self.writeU64(value.value_bytes);
1923 }
1924
1925 fn writeU64(self: *HashBuilder, value: anytype) void {
1926 var encoded: [8]u8 = undefined;
1927 std.mem.writeInt(u64, encoded[0..], @intCast(value), .big);
1928 self.hasher.update(&encoded);
1929 }
1930
1931 fn hash(self: *HashBuilder, value: Hash) void {
1932 self.hasher.update(&value);
1933 }
1934
1935 fn recordValue(self: *HashBuilder, snapshot: file.Snapshot, encoded: []const u8) Error!void {
1936 switch (try record.kind(encoded)) {
1937 .inline_value => self.bytes(try record.inlineValue(encoded)),
1938 .overflow => try self.overflowValue(snapshot, try record.overflow(encoded)),
1939 }
1940 }
1941
1942 fn overflowValue(self: *HashBuilder, snapshot: file.Snapshot, overflow: record.Overflow) Error!void {
1943 var remaining = try overflowLengthAsUsize(overflow.len);
1944 self.writeU64(remaining);
1945 var page_id = overflow.first_page;
1946 while (page_id != 0) {
1947 var image: [page.size]u8 = undefined;
1948 try readExistingPage(snapshot, page_id, &image);
1949 const overflow_page = try page.Overflow.load(&image);
1950 const expected = @min(page.overflow_capacity, remaining);
1951 if (overflow_page.content().len != expected) return error.InvalidPage;
1952 self.hasher.update(overflow_page.content());
1953 remaining -= expected;
1954 const next_page = overflow_page.next();
1955 if (remaining == 0 and next_page != 0) return error.InvalidPage;
1956 if (remaining > 0 and next_page == 0) return error.InvalidPage;
1957 page_id = next_page;
1958 }
1959 if (remaining != 0) return error.InvalidPage;
1960 }
1961 };
1962
1963 fn readExistingPage(source: anytype, page_id: u32, image: *[page.size]u8) Error!void {
1964 if (try source.copyPage(page_id, image)) return;
1965 return error.InvalidPage;
1966 }
1967
1968 /// Copies a page the tree refers to and returns the mark of the image it
1969 /// copied.
1970 fn readMarkedPage(
1971 snapshot: file.Snapshot,
1972 page_id: u32,
1973 image: *[page.size]u8,
1974 ) Error!file.PageMark {
1975 return try snapshot.copyMarkedPage(page_id, image) orelse error.InvalidPage;
1976 }
1977
1978 /// Wraps a leaf or branch copied with `mark`. A copy whose stored image
1979 /// already passed its loader only has its header read. Any other copy is
1980 /// validated and its mark recorded. Safety builds validate every copy and
1981 /// panic on a stale mark.
1982 fn loadMarkedTreePage(image: *[page.size]u8, mark: file.PageMark) Error!TreePage {
1983 if (!mark.checked()) {
1984 const loaded = try loadTreePage(image);
1985 mark.record();
1986 return loaded;
1987 }
1988 if (std.debug.runtime_safety) std.debug.assert(validTreePage(image));
1989 return try trustedTreePage(image);
1990 }
1991
1992 fn refreshTestRead(read: *file.ReadLease, database: *file.Database) Error!void {
1993 const next = try database.beginRead();
1994 read.deinit();
1995 read.* = next;
1996 }
1997
1998 fn loadTreePage(image: *[page.size]u8) Error!TreePage {
1999 return switch (try page.kind(image)) {
2000 .leaf => .{ .leaf = try page.Leaf.load(image) },
2001 .branch => .{ .branch = try page.Branch.load(image) },
2002 .meta, .overflow, .identity => error.InvalidPage,
2003 };
2004 }
2005
2006 /// Wraps a leaf or branch whose cells are known valid, reading its kind
2007 /// from the header.
2008 fn trustedTreePage(image: *[page.size]u8) Error!TreePage {
2009 return switch (try page.kind(image)) {
2010 .leaf => .{ .leaf = page.Leaf.fromValidated(image) },
2011 .branch => .{ .branch = page.Branch.fromValidated(image) },
2012 .meta, .overflow, .identity => error.InvalidPage,
2013 };
2014 }
2015
2016 /// Returns whether a trusted image validates, or is no leaf or branch,
2017 /// which `trustedTreePage` rejects itself.
2018 fn validTreePage(image: *[page.size]u8) bool {
2019 return switch (page.kind(image) catch return true) {
2020 .leaf => if (page.Leaf.load(image)) |_| true else |_| false,
2021 .branch => if (page.Branch.load(image)) |_| true else |_| false,
2022 .meta, .overflow, .identity => true,
2023 };
2024 }
2025
2026 fn zeroPage(image: *const [page.size]u8) bool {
2027 return simd.allEqual(Bytes, image, 0);
2028 }
2029
2030 fn addSummary(target: *Summary, source: Summary) void {
2031 target.branch_pages += source.branch_pages;
2032 target.leaf_pages += source.leaf_pages;
2033 target.overflow_pages += source.overflow_pages;
2034 target.entries += source.entries;
2035 target.inline_records += source.inline_records;
2036 target.overflow_records += source.overflow_records;
2037 target.max_depth = @max(target.max_depth, source.max_depth);
2038 target.key_bytes += source.key_bytes;
2039 target.record_bytes += source.record_bytes;
2040 target.value_bytes += source.value_bytes;
2041 }
2042
2043 fn summarizePage(
2044 source: anytype,
2045 image: *const [page.size]u8,
2046 depth: usize,
2047 summary: *Summary,
2048 ) Error!void {
2049 if (depth >= max_height) return error.TreeTooDeep;
2050 summary.max_depth = @max(summary.max_depth, depth);
2051 var current = image.*;
2052 switch (try page.kind(¤t)) {
2053 .leaf => {
2054 summary.leaf_pages += 1;
2055 const leaf = try page.Leaf.load(¤t);
2056 var range = try leaf.range(null, null);
2057 while (range.next()) |entry| {
2058 try summarizeEntry(source, entry, summary);
2059 }
2060 },
2061 .branch => {
2062 summary.branch_pages += 1;
2063 const branch = try page.Branch.load(¤t);
2064 var index: usize = 0;
2065 while (index < branch.cellCount()) : (index += 1) {
2066 var child: [page.size]u8 = undefined;
2067 try readExistingPage(source, branch.childAt(index), &child);
2068 try summarizePage(source, &child, depth + 1, summary);
2069 }
2070 },
2071 .meta => return error.InvalidPage,
2072 .overflow => return error.InvalidPage,
2073 .identity => return error.InvalidPage,
2074 }
2075 }
2076
2077 fn summarizeEntry(source: anytype, entry: page.Entry, summary: *Summary) Error!void {
2078 summary.entries += 1;
2079 summary.key_bytes += entry.key.len;
2080 summary.record_bytes += entry.value.len;
2081 switch (try record.kind(entry.value)) {
2082 .inline_value => {
2083 const value = try record.inlineValue(entry.value);
2084 summary.inline_records += 1;
2085 summary.value_bytes += value.len;
2086 },
2087 .overflow => {
2088 const overflow = try record.overflow(entry.value);
2089 summary.overflow_records += 1;
2090 summary.value_bytes += try overflowLengthAsUsize(overflow.len);
2091 try summarizeOverflowValue(source, overflow, summary);
2092 },
2093 }
2094 }
2095
2096 fn summarizeOverflowValue(
2097 source: anytype,
2098 overflow: record.Overflow,
2099 summary: *Summary,
2100 ) Error!void {
2101 var remaining = try overflowLengthAsUsize(overflow.len);
2102 var page_id = overflow.first_page;
2103 while (page_id != 0) {
2104 var image: [page.size]u8 = undefined;
2105 try readExistingPage(source, page_id, &image);
2106 const overflow_page = try page.Overflow.load(&image);
2107 const expected = @min(page.overflow_capacity, remaining);
2108 if (overflow_page.content().len != expected) return error.InvalidPage;
2109 remaining -= expected;
2110 summary.overflow_pages += 1;
2111 const next_page = overflow_page.next();
2112 if (remaining == 0 and next_page != 0) return error.InvalidPage;
2113 if (remaining > 0 and next_page == 0) return error.InvalidPage;
2114 page_id = next_page;
2115 }
2116 if (remaining != 0) return error.InvalidPage;
2117 }
2118
2119 fn overflowRefOrNull(bytes: ?[]const u8) Error!?record.Overflow {
2120 const value = bytes orelse return null;
2121 return switch (try record.kind(value)) {
2122 .inline_value => null,
2123 .overflow => try record.overflow(value),
2124 };
2125 }
2126
2127 fn rootEntryLessThan(_: void, left: RootEntry, right: RootEntry) bool {
2128 return simd.order(Bytes, left.key, right.key) == .lt;
2129 }
2130
2131 fn overflowLengthAsUsize(len: u64) Error!usize {
2132 if (len > std.math.maxInt(usize)) return error.ValueTooLarge;
2133 return @intCast(len);
2134 }
2135
2136 fn valueRecordLength(bytes: []const u8) Error!usize {
2137 return switch (try record.kind(bytes)) {
2138 .inline_value => (try record.inlineValue(bytes)).len,
2139 .overflow => try overflowLengthAsUsize((try record.overflow(bytes)).len),
2140 };
2141 }
2142
2143 fn readValueRecordInto(snapshot: file.Snapshot, bytes: []const u8, target: []u8) Error![]u8 {
2144 const value_len = try valueRecordLength(bytes);
2145 if (target.len < value_len) return error.OutputTooSmall;
2146 const value = target[0..value_len];
2147 switch (try record.kind(bytes)) {
2148 .inline_value => @memcpy(value, try record.inlineValue(bytes)),
2149 .overflow => try readOverflowValueInto(snapshot, try record.overflow(bytes), value),
2150 }
2151 return value;
2152 }
2153
2154 fn readOverflowValueInto(snapshot: file.Snapshot, overflow: record.Overflow, target: []u8) Error!void {
2155 if (target.len != try overflowLengthAsUsize(overflow.len)) return error.InvalidRecord;
2156 var offset: usize = 0;
2157 var page_id = overflow.first_page;
2158 while (page_id != 0) {
2159 var image: [page.size]u8 = undefined;
2160 try readExistingPage(snapshot, page_id, &image);
2161 const overflow_page = try page.Overflow.load(&image);
2162 const remaining = target.len - offset;
2163 const expected = @min(page.overflow_capacity, remaining);
2164 if (overflow_page.content().len != expected) return error.InvalidPage;
2165 @memcpy(target[offset..][0..expected], overflow_page.content());
2166 offset += expected;
2167 const next_page = overflow_page.next();
2168 if (offset == target.len and next_page != 0) return error.InvalidPage;
2169 if (offset < target.len and next_page == 0) return error.InvalidPage;
2170 page_id = next_page;
2171 }
2172 if (offset != target.len) return error.InvalidPage;
2173 }
2174
2175 fn latticeEntryFromRecord(snapshot: file.Snapshot, entry_key: []const u8, encoded: []const u8) Error!lattice.State {
2176 var hasher = lattice.EntryHasher.init(entry_key);
2177 switch (try record.kind(encoded)) {
2178 .inline_value => hasher.update(try record.inlineValue(encoded)),
2179 .overflow => {
2180 const overflow = try record.overflow(encoded);
2181 var remaining = try overflowLengthAsUsize(overflow.len);
2182 var page_id = overflow.first_page;
2183 while (page_id != 0) {
2184 var image: [page.size]u8 = undefined;
2185 try readExistingPage(snapshot, page_id, &image);
2186 const overflow_page = try page.Overflow.load(&image);
2187 const expected = @min(page.overflow_capacity, remaining);
2188 if (overflow_page.content().len != expected) return error.InvalidPage;
2189 hasher.update(overflow_page.content());
2190 const next_page = overflow_page.next();
2191 remaining -= expected;
2192 if (remaining == 0 and next_page != 0) return error.InvalidPage;
2193 if (remaining > 0 and next_page == 0) return error.InvalidPage;
2194 page_id = next_page;
2195 }
2196 if (remaining != 0) return error.InvalidPage;
2197 },
2198 }
2199 return hasher.finish();
2200 }
2201
2202 fn copyRootPage(root: *[page.size]u8, source: *[page.size]u8, root_page: u32) Error!void {
2203 switch (try page.kind(source)) {
2204 .leaf => {
2205 const source_leaf = try page.Leaf.load(source);
2206 var root_leaf = page.Leaf.init(root, root_page);
2207 try source_leaf.copyTo(&root_leaf);
2208 },
2209 .branch => {
2210 const source_branch = try page.Branch.load(source);
2211 var root_branch = page.Branch.init(root, root_page);
2212 try source_branch.copyTo(&root_branch);
2213 },
2214 .meta => return error.InvalidPage,
2215 .overflow => return error.InvalidPage,
2216 .identity => return error.InvalidPage,
2217 }
2218 }
2219
2220 test "tree reader keeps a fixed read view without write declarations" {
2221 var tmp = std.testing.tmpDir(.{});
2222 defer tmp.cleanup();
2223
2224 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2225 .paths = .{ .database = "reader.db", .wal = "reader.wal" },
2226 .header = testingHeader(),
2227 });
2228 defer database.deinit();
2229 try database.reserve(.{ .wal_frames = 32 });
2230
2231 const options = Options{ .identity_page = 3 };
2232 var mutable = try Tree.open(&database, options);
2233 _ = try mutable.put("a", "one", .{ .durability = .buffered });
2234 _ = try mutable.put("b", "two", .{ .durability = .buffered });
2235 var read = try database.beginRead();
2236 defer read.deinit();
2237 const reader = try Reader.open(read.snapshot(), options);
2238 _ = try mutable.put("c", "three", .{ .durability = .buffered });
2239
2240 const found = (try reader.get(std.testing.allocator, "a")).?;
2241 defer std.testing.allocator.free(found);
2242 try std.testing.expectEqualStrings("one", found);
2243 try std.testing.expectEqual(@as(?usize, 3), try reader.valueLength("b"));
2244 var value_buffer: [8]u8 = undefined;
2245 try std.testing.expectEqualStrings("two", (try reader.getInto("b", &value_buffer)).?);
2246 const missing = try reader.get(std.testing.allocator, "c");
2247 if (missing) |bytes| std.testing.allocator.free(bytes);
2248 try std.testing.expect(missing == null);
2249
2250 var key_buffer: [8]u8 = undefined;
2251 try std.testing.expectEqualStrings("b", (try reader.lastKey(&key_buffer)).?);
2252 try std.testing.expectEqual(@as(u64, 2), (try reader.identity()).entries);
2253 try std.testing.expectEqual(@as(usize, 2), (try reader.summarize()).entries);
2254
2255 var scan: Scan = undefined;
2256 try reader.scan(&scan, std.testing.allocator, null, null, .value);
2257 defer scan.deinit();
2258 try std.testing.expectEqualStrings("a", (try scan.next()).?.key);
2259 try std.testing.expectEqualStrings("b", (try scan.next()).?.key);
2260 try std.testing.expect(try scan.next() == null);
2261 try std.testing.expect(!@hasDecl(Reader, "put"));
2262 try std.testing.expect(!@hasDecl(Reader, "delete"));
2263 try std.testing.expect(!@hasDecl(Reader, "clear"));
2264 }
2265
2266 test "tree staged summary matches committed summary" {
2267 var tmp = std.testing.tmpDir(.{});
2268 defer tmp.cleanup();
2269
2270 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2271 .paths = .{ .database = "summary.db", .wal = "summary.wal" },
2272 .header = testingHeader(),
2273 });
2274 defer database.deinit();
2275 try database.reserve(.{ .wal_frames = 32 });
2276
2277 var source = try Tree.open(&database, .{});
2278 var write = try Write.beginTree(&source);
2279 defer write.deinit();
2280 try write.put(&source, "key", "value");
2281 const staged = try source.summarizeIn(&write);
2282 try std.testing.expectEqual(@as(usize, 1), staged.entries);
2283 try std.testing.expectEqual(@as(usize, 0), (try source.summarize()).entries);
2284 _ = try write.commit(.{ .durability = .buffered });
2285 try std.testing.expect(std.meta.eql(staged, try source.summarize()));
2286 }
2287
2288 test "tree root split creates a branch over leaf children" {
2289 var tmp = std.testing.tmpDir(.{});
2290 defer tmp.cleanup();
2291
2292 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2293 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2294 .header = testingHeader(),
2295 });
2296 defer database.deinit();
2297 try database.reserve(.{ .wal_frames = 220 });
2298
2299 var tree = try Tree.open(&database, .{});
2300 var index: usize = 0;
2301 while (index < 180) : (index += 1) {
2302 var key_buffer: [16]u8 = undefined;
2303 var value_buffer: [16]u8 = undefined;
2304 const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index});
2305 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2306 _ = try tree.put(key, value, .{ .durability = .buffered });
2307 }
2308
2309 var snapshot_read = try database.beginRead();
2310 defer snapshot_read.deinit();
2311 const snapshot = snapshot_read.snapshot();
2312 var root_image: [page.size]u8 = undefined;
2313 try readExistingPage(snapshot, tree.root_page, &root_image);
2314 try std.testing.expectEqual(page.Kind.branch, try page.kind(&root_image));
2315 const branch = try page.Branch.load(&root_image);
2316 try std.testing.expect(branch.cellCount() >= 2);
2317
2318 const value = (try tree.get(std.testing.allocator, "k00000179")).?;
2319 defer std.testing.allocator.free(value);
2320 try std.testing.expectEqualStrings("v00000179", value);
2321
2322 var range: Range = undefined;
2323 try tree.range(&range, std.testing.allocator, null, null);
2324 defer range.deinit();
2325 var count: usize = 0;
2326 while (try range.next()) |_| count += 1;
2327 try std.testing.expectEqual(@as(usize, 180), count);
2328 }
2329
2330 test "tree split root recovers after reopen" {
2331 var tmp = std.testing.tmpDir(.{});
2332 defer tmp.cleanup();
2333
2334 {
2335 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2336 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2337 .header = testingHeader(),
2338 });
2339 defer database.deinit();
2340 try database.reserve(.{ .wal_frames = 220 });
2341
2342 var tree = try Tree.open(&database, .{});
2343 var index: usize = 0;
2344 while (index < 180) : (index += 1) {
2345 var key_buffer: [16]u8 = undefined;
2346 var value_buffer: [16]u8 = undefined;
2347 const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index});
2348 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2349 _ = try tree.put(key, value, .{ .durability = .buffered });
2350 }
2351 try database.syncWal();
2352 }
2353
2354 var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2355 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2356 .header = recoveredHeader(),
2357 });
2358 defer reopened.deinit();
2359
2360 var tree = try Tree.open(&reopened, .{});
2361 const value = (try tree.get(std.testing.allocator, "k00000120")).?;
2362 defer std.testing.allocator.free(value);
2363 try std.testing.expectEqualStrings("v00000120", value);
2364 var range: Range = undefined;
2365 try tree.range(&range, std.testing.allocator, "k00000170", null);
2366 defer range.deinit();
2367 var count: usize = 0;
2368 while (try range.next()) |_| count += 1;
2369 try std.testing.expectEqual(@as(usize, 10), count);
2370 }
2371
2372 test "tree treats sparse reserved root as empty" {
2373 var tmp = std.testing.tmpDir(.{});
2374 defer tmp.cleanup();
2375 {
2376 var base = try tmp.dir.createFile(io, "tree.db", .{ .read = true, .truncate = true });
2377 defer base.close(io);
2378 var meta_image: [page.size]u8 = undefined;
2379 _ = page.Meta.init(&meta_image, 1, 8);
2380 try base.writePositionalAll(io, meta_image[0..], 0);
2381 try base.setLength(io, @as(u64, page.size * 8));
2382 }
2383
2384 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2385 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2386 .header = recoveredHeader(),
2387 });
2388 defer database.deinit();
2389 try database.reserve(.{ .wal_frames = 64 });
2390
2391 var tree = try Tree.open(&database, .{ .root_page = 2, .reserved_page_max = 8 });
2392 var range: Range = undefined;
2393 try tree.range(&range, std.testing.allocator, null, null);
2394 defer range.deinit();
2395 try std.testing.expect(try range.next() == null);
2396
2397 _ = try tree.put("needle", "value", .{ .durability = .buffered });
2398 const found = (try tree.get(std.testing.allocator, "needle")).?;
2399 defer std.testing.allocator.free(found);
2400 try std.testing.expectEqualStrings("value", found);
2401 }
2402
2403 test "tree rejects a reserved root with a byte past a zero header" {
2404 var tmp = std.testing.tmpDir(.{});
2405 defer tmp.cleanup();
2406 {
2407 var base = try tmp.dir.createFile(io, "tree.db", .{ .read = true, .truncate = true });
2408 defer base.close(io);
2409 var meta_image: [page.size]u8 = undefined;
2410 _ = page.Meta.init(&meta_image, 1, 8);
2411 try base.writePositionalAll(io, meta_image[0..], 0);
2412 var root_image: [page.size]u8 = @splat(0);
2413 root_image[page.size - 1] = 1;
2414 try base.writePositionalAll(io, root_image[0..], page.size);
2415 try base.setLength(io, @as(u64, page.size * 8));
2416 }
2417
2418 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2419 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2420 .header = recoveredHeader(),
2421 });
2422 defer database.deinit();
2423 try database.reserve(.{ .wal_frames = 64 });
2424
2425 var tree = try Tree.open(&database, .{ .root_page = 2, .reserved_page_max = 8 });
2426 try std.testing.expectError(error.InvalidPage, tree.get(std.testing.allocator, "needle"));
2427 const put = tree.put("needle", "value", .{ .durability = .buffered });
2428 try std.testing.expectError(error.InvalidPage, put);
2429 }
2430
2431 test "tree splits a full child leaf under branch root" {
2432 var tmp = std.testing.tmpDir(.{});
2433 defer tmp.cleanup();
2434
2435 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2436 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2437 .header = testingHeader(),
2438 });
2439 defer database.deinit();
2440 try database.reserve(.{ .wal_frames = 340 });
2441
2442 var tree = try Tree.open(&database, .{});
2443 var index: usize = 0;
2444 while (index < 260) : (index += 1) {
2445 var key_buffer: [16]u8 = undefined;
2446 var value_buffer: [16]u8 = undefined;
2447 const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index});
2448 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2449 _ = try tree.put(key, value, .{ .durability = .buffered });
2450 }
2451
2452 var snapshot_read = try database.beginRead();
2453 defer snapshot_read.deinit();
2454 const snapshot = snapshot_read.snapshot();
2455 var root_image: [page.size]u8 = undefined;
2456 try readExistingPage(snapshot, tree.root_page, &root_image);
2457 const branch = try page.Branch.load(&root_image);
2458 try std.testing.expect(branch.cellCount() >= 3);
2459
2460 var range: Range = undefined;
2461 try tree.range(&range, std.testing.allocator, null, null);
2462 defer range.deinit();
2463 var count: usize = 0;
2464 while (try range.next()) |_| count += 1;
2465 try std.testing.expectEqual(@as(usize, 260), count);
2466 }
2467
2468 test "tree accepts every fitting key beside short separators" {
2469 var tmp = std.testing.tmpDir(.{});
2470 defer tmp.cleanup();
2471
2472 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2473 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2474 .header = testingHeader(),
2475 });
2476 defer database.deinit();
2477 try database.reserve(.{ .wal_frames = 64 * 8 + 64 });
2478
2479 var long: [key_bytes_max]u8 = @splat('z');
2480 try std.testing.expectEqual(@as(usize, 2020), key_bytes_max);
2481
2482 var tree = try Tree.open(&database, .{});
2483 const value: [500]u8 = @splat('v');
2484 for (0..40) |index| {
2485 var short: [8]u8 = undefined;
2486 _ = try std.fmt.bufPrint(&short, "a{d:0>7}", .{index});
2487 _ = try tree.put(&short, &value, .{ .durability = .buffered });
2488 }
2489 for (0..12) |index| {
2490 _ = try std.fmt.bufPrint(long[0..8], "z{d:0>7}", .{index});
2491 _ = try tree.put(&long, "", .{ .durability = .buffered });
2492 }
2493
2494 const summary = try tree.summarize();
2495 try std.testing.expectEqual(@as(usize, 52), summary.entries);
2496 try std.testing.expect(summary.max_depth >= 2);
2497 }
2498
2499 test "tree recursively splits branch pages" {
2500 var tmp = std.testing.tmpDir(.{});
2501 defer tmp.cleanup();
2502
2503 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2504 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2505 .header = testingHeader(),
2506 });
2507 defer database.deinit();
2508 try database.reserve(.{ .wal_frames = 220 * 8 + 64 });
2509
2510 var tree = try Tree.open(&database, .{});
2511 var index: usize = 0;
2512 while (index < 220) : (index += 1) {
2513 var key_buffer: [512]u8 = undefined;
2514 var value_buffer: [16]u8 = undefined;
2515 const key = wideKey(&key_buffer, index);
2516 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2517 _ = try tree.put(key, value, .{ .durability = .buffered });
2518 }
2519
2520 var snapshot_read = try database.beginRead();
2521 defer snapshot_read.deinit();
2522 const snapshot = snapshot_read.snapshot();
2523 var root_image: [page.size]u8 = undefined;
2524 try readExistingPage(snapshot, tree.root_page, &root_image);
2525 const root_branch = try page.Branch.load(&root_image);
2526 try std.testing.expect(root_branch.cellCount() >= 2);
2527 var child_image: [page.size]u8 = undefined;
2528 try readExistingPage(snapshot, root_branch.childAt(root_branch.cellCount() - 1), &child_image);
2529 try std.testing.expectEqual(page.Kind.branch, try page.kind(&child_image));
2530
2531 var deleted_key_buffer: [512]u8 = undefined;
2532 _ = try tree.delete(wideKey(&deleted_key_buffer, 100), .{ .durability = .buffered });
2533 const deleted_value = try tree.get(std.testing.allocator, wideKey(&deleted_key_buffer, 100));
2534 if (deleted_value) |bytes| std.testing.allocator.free(bytes);
2535 try std.testing.expect(deleted_value == null);
2536
2537 var value_key_buffer: [512]u8 = undefined;
2538 const value = (try tree.get(std.testing.allocator, wideKey(&value_key_buffer, 219))).?;
2539 defer std.testing.allocator.free(value);
2540 try std.testing.expectEqualStrings("v00000219", value);
2541
2542 var range: Range = undefined;
2543 try tree.range(&range, std.testing.allocator, null, null);
2544 defer range.deinit();
2545 var count: usize = 0;
2546 var previous_buffer: [512]u8 = undefined;
2547 var previous_len: usize = 0;
2548 while (try range.next()) |entry| {
2549 if (previous_len > 0) try std.testing.expect(std.mem.order(u8, previous_buffer[0..previous_len], entry.key) == .lt);
2550 @memcpy(previous_buffer[0..entry.key.len], entry.key);
2551 previous_len = entry.key.len;
2552 count += 1;
2553 }
2554 try std.testing.expectEqual(@as(usize, 219), count);
2555 const full_stats = range.stats();
2556 try std.testing.expectEqual(count, full_stats.entries_returned);
2557 try std.testing.expectEqual(@as(usize, 0), full_stats.separator_children_pruned);
2558
2559 const summary = try tree.summarize();
2560 try std.testing.expectEqual(count, summary.entries);
2561 try std.testing.expect(summary.branch_pages > 1);
2562 try std.testing.expect(summary.leaf_pages > 1);
2563 try std.testing.expect(summary.max_depth >= 2);
2564 try std.testing.expectEqual(@as(usize, 0), summary.overflow_records);
2565 try std.testing.expectEqual(@as(usize, 0), summary.overflow_pages);
2566 try std.testing.expectEqual(count * 512, summary.key_bytes);
2567 try std.testing.expectEqual(count * 9, summary.value_bytes);
2568 try std.testing.expectEqual(summary.leaf_pages, full_stats.leaf_pages_visited);
2569
2570 var bounded_start_buffer: [512]u8 = undefined;
2571 var bounded_end_buffer: [512]u8 = undefined;
2572 var bounded: Range = undefined;
2573 try tree.range(
2574 &bounded,
2575 std.testing.allocator,
2576 wideKey(&bounded_start_buffer, 8),
2577 wideKey(&bounded_end_buffer, 17),
2578 );
2579 defer bounded.deinit();
2580 var bounded_count: usize = 0;
2581 while (try bounded.next()) |entry| {
2582 try std.testing.expect(std.mem.order(u8, wideKey(&bounded_start_buffer, 8), entry.key) != .gt);
2583 try std.testing.expect(std.mem.order(u8, entry.key, wideKey(&bounded_end_buffer, 17)) == .lt);
2584 bounded_count += 1;
2585 }
2586 try std.testing.expectEqual(@as(usize, 9), bounded_count);
2587 const bounded_stats = bounded.stats();
2588 try std.testing.expectEqual(bounded_count, bounded_stats.entries_returned);
2589 try std.testing.expect(bounded_stats.separator_children_pruned > 0);
2590 try std.testing.expect(bounded_stats.leaf_pages_visited < full_stats.leaf_pages_visited);
2591 }
2592
2593 test "tree root hash is stable across reopen and changes after write" {
2594 var tmp = std.testing.tmpDir(.{});
2595 defer tmp.cleanup();
2596
2597 var before_hash: Hash = undefined;
2598 {
2599 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2600 .paths = .{ .database = "tree-root.db", .wal = "tree-root.wal" },
2601 .header = testingHeader(),
2602 });
2603 defer database.deinit();
2604 try database.reserve(.{ .wal_frames = 64 });
2605
2606 var tree = try Tree.open(&database, .{});
2607 _ = try tree.put("a", "one", .{ .durability = .buffered });
2608 _ = try tree.put("b", "two", .{ .durability = .buffered });
2609 var root = try tree.root(std.testing.allocator);
2610 defer root.deinit();
2611 before_hash = root.hash;
2612 try std.testing.expectEqual(@as(usize, 2), root.summary.entries);
2613 try database.syncWal();
2614 }
2615
2616 var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2617 .paths = .{ .database = "tree-root.db", .wal = "tree-root.wal" },
2618 .header = recoveredHeader(),
2619 });
2620 defer reopened.deinit();
2621 try reopened.reserve(.{ .wal_frames = 64 });
2622
2623 var tree = try Tree.open(&reopened, .{});
2624 var same = try tree.root(std.testing.allocator);
2625 defer same.deinit();
2626 try std.testing.expectEqualSlices(u8, before_hash[0..], same.hash[0..]);
2627
2628 _ = try tree.put("b", "changed", .{ .durability = .buffered });
2629 var changed = try tree.root(std.testing.allocator);
2630 defer changed.deinit();
2631 try std.testing.expect(!std.mem.eql(u8, before_hash[0..], changed.hash[0..]));
2632 }
2633
2634 test "tree root cache serves unchanged views and recomputes across writes and checkpoints" {
2635 var tmp = std.testing.tmpDir(.{});
2636 defer tmp.cleanup();
2637
2638 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2639 .paths = .{ .database = "tree-cache.db", .wal = "tree-cache.wal" },
2640 .header = testingHeader(),
2641 });
2642 defer database.deinit();
2643 try database.reserve(.{ .wal_frames = 64 });
2644
2645 var tree = try Tree.open(&database, .{});
2646 _ = try tree.put("a", "one", .{ .durability = .buffered });
2647 var first = try tree.root(std.testing.allocator);
2648 defer first.deinit();
2649 var cached = try tree.root(std.testing.allocator);
2650 defer cached.deinit();
2651 try std.testing.expectEqualSlices(u8, first.hash[0..], cached.hash[0..]);
2652 try std.testing.expectEqual(first.summary.entries, cached.summary.entries);
2653 try std.testing.expectEqual(first.nodes.len, cached.nodes.len);
2654
2655 _ = try tree.put("b", "two", .{ .durability = .buffered });
2656 var written = try tree.root(std.testing.allocator);
2657 defer written.deinit();
2658 try std.testing.expect(!std.mem.eql(u8, first.hash[0..], written.hash[0..]));
2659 try std.testing.expectEqual(@as(usize, 2), written.summary.entries);
2660
2661 _ = try database.checkpoint(.{ .restart_header = testingHeader() });
2662 var checkpointed = try tree.root(std.testing.allocator);
2663 defer checkpointed.deinit();
2664 try std.testing.expectEqualSlices(u8, written.hash[0..], checkpointed.hash[0..]);
2665 }
2666
2667 test "tree range after lazy reopen does not retain scanned base pages" {
2668 var tmp = std.testing.tmpDir(.{});
2669 defer tmp.cleanup();
2670
2671 {
2672 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2673 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2674 .header = testingHeader(),
2675 });
2676 defer database.deinit();
2677 try database.reserve(.{ .wal_frames = 220 * 8 + 64 });
2678
2679 var tree = try Tree.open(&database, .{});
2680 var index: usize = 0;
2681 while (index < 220) : (index += 1) {
2682 var key_buffer: [512]u8 = undefined;
2683 var value_buffer: [16]u8 = undefined;
2684 _ = try tree.put(wideKey(&key_buffer, index), try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index}), .{ .durability = .buffered });
2685 }
2686 _ = try database.checkpoint(.{ .restart_header = recoveredHeader() });
2687 }
2688
2689 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2690 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2691 .header = recoveredHeader(),
2692 });
2693 defer database.deinit();
2694 try database.reserve(.{ .wal_frames = 64 });
2695 try std.testing.expectEqual(@as(usize, 0), database.pager.base.items.len);
2696
2697 var tree = try Tree.open(&database, .{});
2698 var range: Range = undefined;
2699 try tree.range(&range, std.testing.allocator, null, null);
2700 defer range.deinit();
2701 var count: usize = 0;
2702 while (try range.next()) |_| count += 1;
2703 try std.testing.expectEqual(@as(usize, 220), count);
2704 try std.testing.expectEqual(@as(usize, 0), database.pager.base.items.len);
2705
2706 const summary = try tree.summarize();
2707 try std.testing.expectEqual(@as(usize, 220), summary.entries);
2708 try std.testing.expectEqual(@as(usize, 0), database.pager.base.items.len);
2709 }
2710
2711 test "tree root exposes subtree hashes for unchanged child regions" {
2712 var tmp = std.testing.tmpDir(.{});
2713 defer tmp.cleanup();
2714
2715 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2716 .paths = .{ .database = "tree-root-subtree.db", .wal = "tree-root-subtree.wal" },
2717 .header = testingHeader(),
2718 });
2719 defer database.deinit();
2720 try database.reserve(.{ .wal_frames = 360 });
2721
2722 var tree = try Tree.open(&database, .{});
2723 var index: usize = 0;
2724 while (index < 260) : (index += 1) {
2725 var key_buffer: [16]u8 = undefined;
2726 var value_buffer: [16]u8 = undefined;
2727 const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index});
2728 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2729 _ = try tree.put(key, value, .{ .durability = .buffered });
2730 }
2731
2732 var before = try tree.root(std.testing.allocator);
2733 defer before.deinit();
2734 const before_root = before.rootNode();
2735 try std.testing.expectEqual(NodeKind.branch, before_root.kind);
2736 try std.testing.expect(before_root.children_len >= 3);
2737 try std.testing.expectEqual(before.summary.entries, before_root.summary.entries);
2738 try std.testing.expectEqualSlices(u8, before.subtree[0..], before_root.hash[0..]);
2739 const before_children = before.childIndexes(before_root);
2740 var before_child_index: usize = 0;
2741 while (before_child_index < before_children.len) : (before_child_index += 1) {
2742 const child_node = &before.nodes[before_children[before_child_index]];
2743 if (before_child_index + 1 < before_children.len) {
2744 const next_node = &before.nodes[before_children[before_child_index + 1]];
2745 try std.testing.expectEqualSlices(u8, next_node.lower, child_node.upper.?);
2746 } else {
2747 try std.testing.expect(child_node.upper == null);
2748 }
2749 }
2750
2751 _ = try tree.put("k00000259", "changed", .{ .durability = .buffered });
2752
2753 var after = try tree.root(std.testing.allocator);
2754 defer after.deinit();
2755 const after_root = after.rootNode();
2756 try std.testing.expectEqual(NodeKind.branch, after_root.kind);
2757 try std.testing.expect(!std.mem.eql(u8, before.hash[0..], after.hash[0..]));
2758 try std.testing.expect(!std.mem.eql(u8, before.subtree[0..], after.subtree[0..]));
2759 try std.testing.expect(hasSharedChildHash(&before, &after));
2760 }
2761
2762 test "tree recursive branch splits recover after reopen" {
2763 var tmp = std.testing.tmpDir(.{});
2764 defer tmp.cleanup();
2765
2766 {
2767 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2768 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2769 .header = testingHeader(),
2770 });
2771 defer database.deinit();
2772 try database.reserve(.{ .wal_frames = 180 * 8 + 64 });
2773
2774 var tree = try Tree.open(&database, .{});
2775 var index: usize = 0;
2776 while (index < 180) : (index += 1) {
2777 var key_buffer: [512]u8 = undefined;
2778 var value_buffer: [16]u8 = undefined;
2779 const key = wideKey(&key_buffer, index);
2780 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2781 _ = try tree.put(key, value, .{ .durability = .buffered });
2782 }
2783 try database.syncWal();
2784 }
2785
2786 var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2787 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2788 .header = recoveredHeader(),
2789 });
2790 defer reopened.deinit();
2791
2792 var tree = try Tree.open(&reopened, .{});
2793 var key_buffer: [512]u8 = undefined;
2794 const value = (try tree.get(std.testing.allocator, wideKey(&key_buffer, 120))).?;
2795 defer std.testing.allocator.free(value);
2796 try std.testing.expectEqualStrings("v00000120", value);
2797
2798 var start_buffer: [512]u8 = undefined;
2799 var range: Range = undefined;
2800 try tree.range(&range, std.testing.allocator, wideKey(&start_buffer, 170), null);
2801 defer range.deinit();
2802 var count: usize = 0;
2803 while (try range.next()) |_| count += 1;
2804 try std.testing.expectEqual(@as(usize, 10), count);
2805 }
2806
2807 test "tree delete removes empty child and collapses root branch" {
2808 var tmp = std.testing.tmpDir(.{});
2809 defer tmp.cleanup();
2810
2811 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2812 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2813 .header = testingHeader(),
2814 });
2815 defer database.deinit();
2816 try database.reserve(.{ .wal_frames = 320 });
2817
2818 var tree = try Tree.open(&database, .{});
2819 var index: usize = 0;
2820 while (index < 180) : (index += 1) {
2821 var key_buffer: [16]u8 = undefined;
2822 var value_buffer: [16]u8 = undefined;
2823 const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index});
2824 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2825 _ = try tree.put(key, value, .{ .durability = .buffered });
2826 }
2827
2828 index = 0;
2829 while (index < 120) : (index += 1) {
2830 var key_buffer: [16]u8 = undefined;
2831 const key = try std.fmt.bufPrint(&key_buffer, "k{d:0>8}", .{index});
2832 _ = try tree.delete(key, .{ .durability = .buffered });
2833 }
2834
2835 var snapshot_read = try database.beginRead();
2836 defer snapshot_read.deinit();
2837 const snapshot = snapshot_read.snapshot();
2838 var root_image: [page.size]u8 = undefined;
2839 try readExistingPage(snapshot, tree.root_page, &root_image);
2840 try std.testing.expectEqual(page.Kind.leaf, try page.kind(&root_image));
2841 const leaf = try page.Leaf.load(&root_image);
2842 try std.testing.expectEqual(@as(u64, tree.root_page), leaf.id());
2843
2844 var deleted_key: [16]u8 = undefined;
2845 const deleted_value = try tree.get(std.testing.allocator, try std.fmt.bufPrint(&deleted_key, "k{d:0>8}", .{0}));
2846 if (deleted_value) |bytes| std.testing.allocator.free(bytes);
2847 try std.testing.expect(deleted_value == null);
2848
2849 const value = (try tree.get(std.testing.allocator, "k00000150")).?;
2850 defer std.testing.allocator.free(value);
2851 try std.testing.expectEqualStrings("v00000150", value);
2852
2853 var range: Range = undefined;
2854 try tree.range(&range, std.testing.allocator, null, null);
2855 defer range.deinit();
2856 var count: usize = 0;
2857 while (try range.next()) |_| count += 1;
2858 try std.testing.expectEqual(@as(usize, 60), count);
2859 }
2860
2861 test "tree delete retains a safe lower bound when exact replacement does not fit" {
2862 var tmp = std.testing.tmpDir(.{});
2863 defer tmp.cleanup();
2864
2865 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2866 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2867 .header = testingHeader(),
2868 });
2869 defer database.deinit();
2870 try database.reserve(.{ .wal_frames = 32 });
2871
2872 var tree = try Tree.open(&database, .{});
2873 var next_key: [1500]u8 = @splat('n');
2874 var upper_key: [3000]u8 = @splat('z');
2875 var encoded_buffer: [16]u8 = undefined;
2876 const encoded = try record.encodeInline(&encoded_buffer, "value");
2877 {
2878 var write = try Write.beginTree(&tree);
2879 defer write.deinit();
2880 const left_id = try write.allocatePage();
2881 const middle_id = try write.allocatePage();
2882 const right_id = try write.allocatePage();
2883
2884 var left_image: [page.size]u8 = undefined;
2885 var middle_image: [page.size]u8 = undefined;
2886 var right_image: [page.size]u8 = undefined;
2887 var root_image: [page.size]u8 = undefined;
2888 var left = page.Leaf.init(&left_image, left_id);
2889 var middle = page.Leaf.init(&middle_image, middle_id);
2890 var right = page.Leaf.init(&right_image, right_id);
2891 var root = page.Branch.init(&root_image, tree.root_page);
2892 try left.put("a", encoded);
2893 try middle.put("m", encoded);
2894 try middle.put(&next_key, encoded);
2895 try right.put(&upper_key, encoded);
2896 try root.put("", left_id);
2897 try root.put("m", middle_id);
2898 try root.put(&upper_key, right_id);
2899 try write.putPage(left_id, &left_image);
2900 try write.putPage(middle_id, &middle_image);
2901 try write.putPage(right_id, &right_image);
2902 try write.putPage(tree.root_page, &root_image);
2903 _ = try write.commit(.{ .durability = .buffered });
2904 }
2905
2906 _ = try tree.delete("m", .{ .durability = .buffered });
2907
2908 try std.testing.expect((try tree.get(std.testing.allocator, "m")) == null);
2909 const value = (try tree.get(std.testing.allocator, &next_key)).?;
2910 defer std.testing.allocator.free(value);
2911 try std.testing.expectEqualStrings("value", value);
2912 }
2913
2914 test "tree delete compacts recursive branches back to a root leaf" {
2915 var tmp = std.testing.tmpDir(.{});
2916 defer tmp.cleanup();
2917
2918 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2919 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2920 .header = testingHeader(),
2921 });
2922 defer database.deinit();
2923 try database.reserve(.{ .wal_frames = 120 * 8 + 120 });
2924
2925 var tree = try Tree.open(&database, .{});
2926 var index: usize = 0;
2927 while (index < 110) : (index += 1) {
2928 var key_buffer: [512]u8 = undefined;
2929 var value_buffer: [16]u8 = undefined;
2930 const key = wideKey(&key_buffer, index);
2931 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2932 _ = try tree.put(key, value, .{ .durability = .buffered });
2933 }
2934
2935 index = 0;
2936 while (index < 104) : (index += 1) {
2937 var key_buffer: [512]u8 = undefined;
2938 _ = try tree.delete(wideKey(&key_buffer, index), .{ .durability = .buffered });
2939 }
2940
2941 var snapshot_read = try database.beginRead();
2942 defer snapshot_read.deinit();
2943 const snapshot = snapshot_read.snapshot();
2944 var root_image: [page.size]u8 = undefined;
2945 try readExistingPage(snapshot, tree.root_page, &root_image);
2946 try std.testing.expectEqual(page.Kind.leaf, try page.kind(&root_image));
2947 const leaf = try page.Leaf.load(&root_image);
2948 try std.testing.expectEqual(@as(u64, tree.root_page), leaf.id());
2949
2950 var value_key_buffer: [512]u8 = undefined;
2951 const value = (try tree.get(std.testing.allocator, wideKey(&value_key_buffer, 109))).?;
2952 defer std.testing.allocator.free(value);
2953 try std.testing.expectEqualStrings("v00000109", value);
2954
2955 var range: Range = undefined;
2956 try tree.range(&range, std.testing.allocator, null, null);
2957 defer range.deinit();
2958 var count: usize = 0;
2959 while (try range.next()) |_| count += 1;
2960 try std.testing.expectEqual(@as(usize, 6), count);
2961 }
2962
2963 test "tree reuses freed pages after delete compaction" {
2964 var tmp = std.testing.tmpDir(.{});
2965 defer tmp.cleanup();
2966
2967 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
2968 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
2969 .header = testingHeader(),
2970 });
2971 defer database.deinit();
2972 try database.reserve(.{ .wal_frames = 160 * 8 + 160 });
2973
2974 var tree = try Tree.open(&database, .{});
2975 var index: usize = 0;
2976 while (index < 110) : (index += 1) {
2977 var key_buffer: [512]u8 = undefined;
2978 var value_buffer: [16]u8 = undefined;
2979 const key = wideKey(&key_buffer, index);
2980 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
2981 _ = try tree.put(key, value, .{ .durability = .buffered });
2982 }
2983
2984 var snapshot_read = try database.beginRead();
2985 defer snapshot_read.deinit();
2986 var snapshot = snapshot_read.snapshot();
2987 var meta_image: [page.size]u8 = undefined;
2988 try readExistingPage(snapshot, tree.meta_page, &meta_image);
2989 var meta = try page.Meta.load(&meta_image);
2990 const highest_after_growth = meta.highestPage();
2991
2992 index = 0;
2993 while (index < 104) : (index += 1) {
2994 var key_buffer: [512]u8 = undefined;
2995 _ = try tree.delete(wideKey(&key_buffer, index), .{ .durability = .buffered });
2996 }
2997
2998 try refreshTestRead(&snapshot_read, &database);
2999 snapshot = snapshot_read.snapshot();
3000 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3001 meta = try page.Meta.load(&meta_image);
3002 const highest_before_reuse = meta.highestPage();
3003 const free_before_reuse = meta.freeCount();
3004 try std.testing.expect(free_before_reuse > 0 or highest_before_reuse < highest_after_growth);
3005
3006 while (index < 122) : (index += 1) {
3007 var key_buffer: [512]u8 = undefined;
3008 var value_buffer: [16]u8 = undefined;
3009 const key = wideKey(&key_buffer, index);
3010 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
3011 _ = try tree.put(key, value, .{ .durability = .buffered });
3012 }
3013
3014 try refreshTestRead(&snapshot_read, &database);
3015 snapshot = snapshot_read.snapshot();
3016 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3017 meta = try page.Meta.load(&meta_image);
3018 try std.testing.expect(meta.highestPage() <= highest_after_growth);
3019 if (free_before_reuse > 0) try std.testing.expect(meta.freeCount() < free_before_reuse);
3020
3021 var range: Range = undefined;
3022 try tree.range(&range, std.testing.allocator, null, null);
3023 defer range.deinit();
3024 var count: usize = 0;
3025 while (try range.next()) |_| count += 1;
3026 try std.testing.expectEqual(@as(usize, 18), count);
3027 }
3028
3029 test "allocated roots clear recycled page images" {
3030 var tmp = std.testing.tmpDir(.{});
3031 defer tmp.cleanup();
3032
3033 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3034 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3035 .header = testingHeader(),
3036 });
3037 defer database.deinit();
3038 try database.reserve(.{ .wal_frames = 32 });
3039
3040 var tree = try Tree.open(&database, .{});
3041 var recycled: [2]u32 = undefined;
3042 {
3043 var write = try Write.beginTree(&tree);
3044 defer write.deinit();
3045 for (&recycled) |*page_id| {
3046 page_id.* = try write.allocatePage();
3047 var image: [page.size]u8 = undefined;
3048 _ = page.Leaf.init(&image, page_id.*);
3049 try write.putPage(page_id.*, &image);
3050 }
3051 const retained = try write.allocatePage();
3052 var image: [page.size]u8 = undefined;
3053 _ = page.Leaf.init(&image, retained);
3054 try write.putPage(retained, &image);
3055 _ = try write.commit(.{ .durability = .buffered });
3056 }
3057 {
3058 var write = try Write.beginTree(&tree);
3059 defer write.deinit();
3060 try write.releasePage(tree.root_page, recycled[0]);
3061 try write.releasePage(tree.root_page, recycled[1]);
3062 _ = try write.commit(.{ .durability = .buffered });
3063 }
3064
3065 var before_read = try database.beginRead();
3066 defer before_read.deinit();
3067 const before = before_read.snapshot();
3068 var meta_image: [page.size]u8 = undefined;
3069 try readExistingPage(before, tree.meta_page, &meta_image);
3070 const meta = try page.Meta.load(&meta_image);
3071 try std.testing.expectEqual(@as(usize, 2), meta.freeCount());
3072
3073 var root_page: u32 = undefined;
3074 var identity_page: u32 = undefined;
3075 {
3076 var write = try Write.beginTree(&tree);
3077 defer write.deinit();
3078 root_page = try write.allocateRoot();
3079 identity_page = try write.allocateRoot();
3080 _ = try write.commit(.{ .durability = .buffered });
3081 }
3082 try std.testing.expect(root_page <= meta.highestPage());
3083 try std.testing.expect(identity_page <= meta.highestPage());
3084
3085 const empty = try Tree.open(&database, .{
3086 .root_page = root_page,
3087 .identity_page = identity_page,
3088 });
3089 const identity = try empty.identity();
3090 try std.testing.expectEqual(@as(u64, 0), identity.entries);
3091 try std.testing.expect((try empty.get(std.testing.allocator, "missing")) == null);
3092 }
3093
3094 test "tree root edges link every node to its direct children" {
3095 var tmp = std.testing.tmpDir(.{});
3096 defer tmp.cleanup();
3097
3098 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3099 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3100 .header = testingHeader(),
3101 });
3102 defer database.deinit();
3103 try database.reserve(.{ .wal_frames = 8192 });
3104
3105 var tree = try Tree.open(&database, .{});
3106 var index: usize = 0;
3107 while (index < 360) : (index += 1) {
3108 var key_buffer: [512]u8 = undefined;
3109 var value_buffer: [16]u8 = undefined;
3110 const key = wideKey(&key_buffer, index);
3111 const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{index});
3112 _ = try tree.put(key, value, .{ .durability = .buffered });
3113 }
3114
3115 var root = try tree.root(std.testing.allocator);
3116 defer root.deinit();
3117 try std.testing.expect(root.summary.max_depth >= 2);
3118
3119 const seen = try std.testing.allocator.alloc(usize, root.nodes.len);
3120 defer std.testing.allocator.free(seen);
3121 @memset(seen, 0);
3122 seen[0] = 1;
3123 for (root.nodes, 0..) |node, parent_index| {
3124 if (node.kind != .branch) {
3125 try std.testing.expectEqual(@as(usize, 0), node.children_len);
3126 continue;
3127 }
3128 try std.testing.expect(node.children_len != 0);
3129 for (root.childIndexes(&root.nodes[parent_index])) |child_index| {
3130 const child = root.nodes[child_index];
3131 try std.testing.expectEqual(node.depth + 1, child.depth);
3132 seen[child_index] += 1;
3133 }
3134 }
3135 for (seen) |count| {
3136 try std.testing.expectEqual(@as(usize, 1), count);
3137 }
3138 }
3139
3140 fn seedFullInlineFreeList(database: *file.Database, tree: *const Tree, first_page: u32) !void {
3141 var snapshot_read = try database.beginRead();
3142 defer snapshot_read.deinit();
3143 const snapshot = snapshot_read.snapshot();
3144 var meta_image: [page.size]u8 = undefined;
3145 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3146 var meta = try page.Meta.load(&meta_image);
3147 const capacity = meta.freeCapacity();
3148 _ = try meta.reserveThrough(first_page + @as(u32, @intCast(capacity + 4)));
3149
3150 var page_id = first_page;
3151 while (meta.freeCount() < capacity) : (page_id += 1) {
3152 if (page_id == tree.meta_page or page_id == tree.root_page) continue;
3153 try meta.release(page_id);
3154 }
3155
3156 var transaction = try database.beginWrite();
3157 defer transaction.deinit();
3158 try transaction.putPage(tree.meta_page, &meta_image);
3159 _ = try transaction.commit(.{ .durability = .buffered });
3160 }
3161
3162 test "tree spills a full inline free list into a chain and refills it" {
3163 var tmp = std.testing.tmpDir(.{});
3164 defer tmp.cleanup();
3165
3166 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3167 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3168 .header = testingHeader(),
3169 });
3170 defer database.deinit();
3171 try database.reserve(.{ .wal_frames = 64 });
3172
3173 var tree = try Tree.open(&database, .{});
3174 var first_large: [page.overflow_capacity * 2 + 37]u8 = undefined;
3175 var second_large: [page.overflow_capacity * 3 + 37]u8 = undefined;
3176 fillLargeValue(&first_large, 71);
3177 fillLargeValue(&second_large, 91);
3178
3179 _ = try tree.put("large", &first_large, .{ .durability = .buffered });
3180 const seeded = try tree.summarize();
3181 try std.testing.expectEqual(@as(usize, 1), seeded.entries);
3182 try std.testing.expectEqual(@as(usize, 3), seeded.overflow_pages);
3183
3184 try seedFullInlineFreeList(&database, &tree, 128);
3185 var snapshot_read = try database.beginRead();
3186 defer snapshot_read.deinit();
3187 var snapshot = snapshot_read.snapshot();
3188 var meta_image: [page.size]u8 = undefined;
3189 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3190 var meta = try page.Meta.load(&meta_image);
3191 try std.testing.expectEqual(meta.freeCapacity(), meta.freeCount());
3192 const seeded_highest = meta.highestPage();
3193
3194 _ = try tree.delete("large", .{ .durability = .buffered });
3195
3196 try refreshTestRead(&snapshot_read, &database);
3197 snapshot = snapshot_read.snapshot();
3198 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3199 meta = try page.Meta.load(&meta_image);
3200 try std.testing.expect(meta.isChained());
3201 try std.testing.expect(meta.chainHead() != 0);
3202 try std.testing.expect(meta.freeCount() > 0);
3203
3204 _ = try tree.put("other", &second_large, .{ .durability = .buffered });
3205
3206 try refreshTestRead(&snapshot_read, &database);
3207 snapshot = snapshot_read.snapshot();
3208 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3209 meta = try page.Meta.load(&meta_image);
3210 try std.testing.expect(!meta.isChained());
3211 try std.testing.expect(meta.highestPage() <= seeded_highest);
3212 try std.testing.expect(meta.freeCount() > 0);
3213
3214 var range: Range = undefined;
3215 try tree.range(&range, std.testing.allocator, null, null);
3216 defer range.deinit();
3217 const entry = (try range.next()).?;
3218 try std.testing.expectEqualStrings("other", entry.key);
3219 try std.testing.expectEqualSlices(u8, &second_large, entry.value);
3220 try std.testing.expect(try range.next() == null);
3221 }
3222
3223 test "tree clear releases durable pages without loading base tree" {
3224 var tmp = std.testing.tmpDir(.{});
3225 defer tmp.cleanup();
3226
3227 {
3228 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3229 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3230 .header = testingHeader(),
3231 });
3232 defer database.deinit();
3233 try database.reserve(.{ .wal_frames = 1024 });
3234
3235 var tree = try Tree.open(&database, .{});
3236 var large: [page.overflow_capacity + 37]u8 = undefined;
3237 fillLargeValue(&large, 33);
3238 var index: usize = 0;
3239 while (index < 64) : (index += 1) {
3240 var key_buffer: [512]u8 = undefined;
3241 _ = try tree.put(wideKey(&key_buffer, index), &large, .{ .durability = .buffered });
3242 }
3243 const before = try tree.summarize();
3244 try std.testing.expect(before.branch_pages > 0);
3245 try std.testing.expect(before.overflow_pages >= 64);
3246 _ = try database.checkpoint(.{ .restart_header = recoveredHeader() });
3247 }
3248
3249 {
3250 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3251 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3252 .header = recoveredHeader(),
3253 });
3254 defer database.deinit();
3255 try database.reserve(.{ .wal_frames = 512 });
3256
3257 var tree = try Tree.open(&database, .{});
3258 _ = try tree.clear(.{ .durability = .buffered });
3259 try std.testing.expect(database.pager.base.items.len <= 1);
3260
3261 var range: Range = undefined;
3262 try tree.range(&range, std.testing.allocator, null, null);
3263 defer range.deinit();
3264 try std.testing.expect(try range.next() == null);
3265
3266 _ = try tree.put("after", "clear", .{ .durability = .buffered });
3267 const value = (try tree.get(std.testing.allocator, "after")).?;
3268 defer std.testing.allocator.free(value);
3269 try std.testing.expectEqualStrings("clear", value);
3270 }
3271 }
3272
3273 test "tree stores large values in overflow pages and reuses replaced chains" {
3274 var tmp = std.testing.tmpDir(.{});
3275 defer tmp.cleanup();
3276
3277 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3278 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3279 .header = testingHeader(),
3280 });
3281 defer database.deinit();
3282 try database.reserve(.{ .wal_frames = 32 });
3283
3284 var tree = try Tree.open(&database, .{});
3285 var large: [page.overflow_capacity * 2 + 37]u8 = undefined;
3286 fillLargeValue(&large, 17);
3287 _ = try tree.put("large", &large, .{ .durability = .buffered });
3288
3289 const stored = (try tree.get(std.testing.allocator, "large")).?;
3290 defer std.testing.allocator.free(stored);
3291 try std.testing.expectEqualSlices(u8, &large, stored);
3292
3293 var range: Range = undefined;
3294 try tree.range(&range, std.testing.allocator, null, null);
3295 defer range.deinit();
3296 const entry = (try range.next()).?;
3297 try std.testing.expectEqualStrings("large", entry.key);
3298 try std.testing.expectEqualSlices(u8, &large, entry.value);
3299 try std.testing.expect(try range.next() == null);
3300
3301 var snapshot_read = try database.beginRead();
3302 defer snapshot_read.deinit();
3303 var snapshot = snapshot_read.snapshot();
3304 var meta_image: [page.size]u8 = undefined;
3305 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3306 var meta = try page.Meta.load(&meta_image);
3307 const highest_after_large = meta.highestPage();
3308 const overflow_pages = (large.len + page.overflow_capacity - 1) / page.overflow_capacity;
3309 var summary = try tree.summarize();
3310 try std.testing.expectEqual(@as(usize, 1), summary.entries);
3311 try std.testing.expectEqual(@as(usize, 1), summary.overflow_records);
3312 try std.testing.expectEqual(overflow_pages, summary.overflow_pages);
3313 try std.testing.expectEqual(large.len, summary.value_bytes);
3314
3315 _ = try tree.put("large", "tiny", .{ .durability = .buffered });
3316 const small = (try tree.get(std.testing.allocator, "large")).?;
3317 defer std.testing.allocator.free(small);
3318 try std.testing.expectEqualStrings("tiny", small);
3319 summary = try tree.summarize();
3320 try std.testing.expectEqual(@as(usize, 1), summary.entries);
3321 try std.testing.expectEqual(@as(usize, 0), summary.overflow_records);
3322 try std.testing.expectEqual(@as(usize, 0), summary.overflow_pages);
3323 try std.testing.expectEqual(@as(usize, 4), summary.value_bytes);
3324
3325 try refreshTestRead(&snapshot_read, &database);
3326 snapshot = snapshot_read.snapshot();
3327 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3328 meta = try page.Meta.load(&meta_image);
3329 try std.testing.expect(meta.highestPage() <= highest_after_large);
3330 try std.testing.expect(meta.freeCount() >= overflow_pages or meta.highestPage() < highest_after_large);
3331 const free_after_release = meta.freeCount();
3332
3333 var second: [page.overflow_capacity * 2 + 37]u8 = undefined;
3334 fillLargeValue(&second, 91);
3335 _ = try tree.put("other", &second, .{ .durability = .buffered });
3336
3337 try refreshTestRead(&snapshot_read, &database);
3338 snapshot = snapshot_read.snapshot();
3339 try readExistingPage(snapshot, tree.meta_page, &meta_image);
3340 meta = try page.Meta.load(&meta_image);
3341 try std.testing.expect(meta.highestPage() <= highest_after_large);
3342 if (free_after_release > 0) try std.testing.expect(meta.freeCount() < free_after_release);
3343
3344 const other = (try tree.get(std.testing.allocator, "other")).?;
3345 defer std.testing.allocator.free(other);
3346 try std.testing.expectEqualSlices(u8, &second, other);
3347 summary = try tree.summarize();
3348 try std.testing.expectEqual(@as(usize, 2), summary.entries);
3349 try std.testing.expectEqual(@as(usize, 1), summary.overflow_records);
3350 try std.testing.expectEqual(overflow_pages, summary.overflow_pages);
3351 try std.testing.expectEqual(second.len + @as(usize, 4), summary.value_bytes);
3352 }
3353
3354 test "tree scan projection controls overflow materialization" {
3355 var tmp = std.testing.tmpDir(.{});
3356 defer tmp.cleanup();
3357
3358 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3359 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3360 .header = testingHeader(),
3361 });
3362 defer database.deinit();
3363 try database.reserve(.{ .wal_frames = 4 });
3364
3365 var tree = try Tree.open(&database, .{});
3366 var record_bytes: [record.overflow_size]u8 = undefined;
3367 const encoded = try record.encodeOverflow(&record_bytes, .{
3368 .len = page.overflow_capacity + 1,
3369 .first_page = 77,
3370 });
3371
3372 var root_image: [page.size]u8 = undefined;
3373 var leaf = page.Leaf.init(&root_image, tree.root_page);
3374 try leaf.put("dangling", encoded);
3375
3376 var meta_image: [page.size]u8 = undefined;
3377 _ = page.Meta.init(&meta_image, tree.meta_page, 77);
3378
3379 var transaction = try database.beginWrite();
3380 defer transaction.deinit();
3381 try transaction.putPage(tree.meta_page, &meta_image);
3382 try transaction.putPage(tree.root_page, &root_image);
3383 _ = try transaction.commit(.{ .durability = .buffered });
3384
3385 var key_scan: Scan = undefined;
3386 try tree.scan(&key_scan, std.testing.allocator, null, null, .key);
3387 defer key_scan.deinit();
3388 const key_entry = (try key_scan.next()).?;
3389 try std.testing.expectEqualStrings("dangling", key_entry.key);
3390 try std.testing.expectEqual(@as(usize, 0), key_entry.bytes.len);
3391 try std.testing.expect(try key_scan.next() == null);
3392
3393 var record_scan: Scan = undefined;
3394 try tree.scan(&record_scan, std.testing.allocator, null, null, .record);
3395 defer record_scan.deinit();
3396 const record_entry = (try record_scan.next()).?;
3397 try std.testing.expectEqualStrings("dangling", record_entry.key);
3398 const overflow = try record.overflow(record_entry.bytes);
3399 try std.testing.expectEqual(@as(u64, page.overflow_capacity + 1), overflow.len);
3400 try std.testing.expectEqual(@as(u32, 77), overflow.first_page);
3401 try std.testing.expect(try record_scan.next() == null);
3402
3403 var decoded: Range = undefined;
3404 try tree.range(&decoded, std.testing.allocator, null, null);
3405 defer decoded.deinit();
3406 try std.testing.expectError(error.InvalidPage, decoded.next());
3407 }
3408
3409 test "tree stores ordered keys through file transactions" {
3410 var tmp = std.testing.tmpDir(.{});
3411 defer tmp.cleanup();
3412
3413 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3414 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3415 .header = testingHeader(),
3416 });
3417 defer database.deinit();
3418
3419 var tree = try Tree.open(&database, .{});
3420 _ = try tree.put("c", "three", .{ .durability = .buffered });
3421 _ = try tree.put("a", "one", .{ .durability = .buffered });
3422 _ = try tree.put("b", "two", .{ .durability = .buffered });
3423
3424 const value = (try tree.get(std.testing.allocator, "b")).?;
3425 defer std.testing.allocator.free(value);
3426 try std.testing.expectEqualStrings("two", value);
3427
3428 var range: Range = undefined;
3429 try tree.range(&range, std.testing.allocator, null, null);
3430 defer range.deinit();
3431 const first = (try range.next()).?;
3432 const second = (try range.next()).?;
3433 const third = (try range.next()).?;
3434 try std.testing.expectEqualStrings("a", first.key);
3435 try std.testing.expectEqualStrings("b", second.key);
3436 try std.testing.expectEqualStrings("c", third.key);
3437 try std.testing.expect(try range.next() == null);
3438 }
3439
3440 test "tree delete removes a key from durable root leaf" {
3441 var tmp = std.testing.tmpDir(.{});
3442 defer tmp.cleanup();
3443
3444 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3445 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3446 .header = testingHeader(),
3447 });
3448 defer database.deinit();
3449
3450 var tree = try Tree.open(&database, .{});
3451 _ = try tree.put("a", "one", .{ .durability = .buffered });
3452 _ = try tree.put("b", "two", .{ .durability = .buffered });
3453 _ = try tree.delete("a", .{ .durability = .buffered });
3454
3455 try std.testing.expect(try tree.get(std.testing.allocator, "a") == null);
3456 const value = (try tree.get(std.testing.allocator, "b")).?;
3457 defer std.testing.allocator.free(value);
3458 try std.testing.expectEqualStrings("two", value);
3459 }
3460
3461 test "tree synced writes recover after reopen" {
3462 var tmp = std.testing.tmpDir(.{});
3463 defer tmp.cleanup();
3464
3465 {
3466 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3467 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3468 .header = testingHeader(),
3469 });
3470 defer database.deinit();
3471
3472 var tree = try Tree.open(&database, .{});
3473 _ = try tree.put("a", "one", .{});
3474 _ = try tree.put("b", "two", .{});
3475 }
3476
3477 var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3478 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3479 .header = recoveredHeader(),
3480 });
3481 defer reopened.deinit();
3482
3483 var tree = try Tree.open(&reopened, .{});
3484 const value = (try tree.get(std.testing.allocator, "a")).?;
3485 defer std.testing.allocator.free(value);
3486 try std.testing.expectEqualStrings("one", value);
3487 var range: Range = undefined;
3488 try tree.range(&range, std.testing.allocator, "b", null);
3489 defer range.deinit();
3490 const entry = (try range.next()).?;
3491 try std.testing.expectEqualStrings("b", entry.key);
3492 try std.testing.expectEqualStrings("two", entry.value);
3493 try std.testing.expect(try range.next() == null);
3494 }
3495
3496 test "tree reports missing delete and invalid root page" {
3497 var tmp = std.testing.tmpDir(.{});
3498 defer tmp.cleanup();
3499
3500 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3501 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3502 .header = testingHeader(),
3503 });
3504 defer database.deinit();
3505
3506 try std.testing.expectError(error.InvalidPageId, Tree.open(&database, .{ .root_page = 0 }));
3507 var tree = try Tree.open(&database, .{});
3508 try std.testing.expectError(error.KeyNotFound, tree.delete("missing", .{ .durability = .buffered }));
3509 }
3510
3511 fn expectIdentityMatchesEntries(tree: *const Tree, expected_entries: u64) !void {
3512 const info = try tree.identity();
3513 try std.testing.expectEqual(expected_entries, info.entries);
3514
3515 var rebuilt = lattice.State.empty;
3516 var count: u64 = 0;
3517 var entries: Range = undefined;
3518 try tree.range(&entries, std.testing.allocator, null, null);
3519 defer entries.deinit();
3520 while (try entries.next()) |entry| {
3521 const state = lattice.entryState(entry.key, entry.value);
3522 rebuilt.add(&state);
3523 count += 1;
3524 }
3525 try std.testing.expectEqual(expected_entries, count);
3526 try std.testing.expect(info.state.eql(&rebuilt));
3527 try std.testing.expect(std.mem.eql(u8, &tree.digestIdentity(&info), &rebuilt.digest(count)));
3528
3529 var traversed = try tree.root(std.testing.allocator);
3530 defer traversed.deinit();
3531 try std.testing.expect(std.mem.eql(u8, &tree.digestIdentity(&info), &traversed.hash));
3532 try std.testing.expectEqual(traversed.summary.key_bytes, @as(usize, @intCast(info.key_bytes)));
3533 try std.testing.expectEqual(traversed.summary.value_bytes, @as(usize, @intCast(info.value_bytes)));
3534 }
3535
3536 test "tree identity tracks put update delete and clear" {
3537 var tmp = std.testing.tmpDir(.{});
3538 defer tmp.cleanup();
3539
3540 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3541 .paths = .{ .database = "identity.db", .wal = "identity.wal" },
3542 .header = testingHeader(),
3543 });
3544 defer database.deinit();
3545
3546 var tree = try Tree.open(&database, .{ .identity_page = 3 });
3547
3548 const fresh = try tree.identity();
3549 try std.testing.expectEqual(@as(u64, 0), fresh.entries);
3550 try std.testing.expect(fresh.state.isEmpty());
3551
3552 _ = try tree.put("alpha", "one", .{ .durability = .buffered });
3553 _ = try tree.put("beta", "two", .{ .durability = .buffered });
3554 try expectIdentityMatchesEntries(&tree, 2);
3555
3556 _ = try tree.put("alpha", "uno", .{ .durability = .buffered });
3557 try expectIdentityMatchesEntries(&tree, 2);
3558
3559 _ = try tree.delete("beta", .{ .durability = .buffered });
3560 try expectIdentityMatchesEntries(&tree, 1);
3561
3562 _ = try tree.delete("alpha", .{ .durability = .buffered });
3563 const drained = try tree.identity();
3564 try std.testing.expectEqual(@as(u64, 0), drained.entries);
3565 try std.testing.expect(drained.state.isEmpty());
3566
3567 _ = try tree.put("gamma", "three", .{ .durability = .buffered });
3568 _ = try tree.clear(.{ .durability = .buffered });
3569 const cleared = try tree.identity();
3570 try std.testing.expectEqual(@as(u64, 0), cleared.entries);
3571 try std.testing.expect(cleared.state.isEmpty());
3572 }
3573
3574 test "tree identity follows overflow values across updates" {
3575 var tmp = std.testing.tmpDir(.{});
3576 defer tmp.cleanup();
3577
3578 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3579 .paths = .{ .database = "identity.db", .wal = "identity.wal" },
3580 .header = testingHeader(),
3581 });
3582 defer database.deinit();
3583
3584 var tree = try Tree.open(&database, .{ .identity_page = 3 });
3585 try database.reserve(.{ .wal_frames = 80 });
3586
3587 var value_buffer: [page.overflow_capacity * 2 + 257]u8 = undefined;
3588 for (&value_buffer, 0..) |*byte, index| byte.* = @intCast(index % 251);
3589
3590 _ = try tree.put("big", value_buffer[0..], .{ .durability = .buffered });
3591 try expectIdentityMatchesEntries(&tree, 1);
3592
3593 _ = try tree.put("big", value_buffer[0 .. page.overflow_capacity + 17], .{ .durability = .buffered });
3594 try expectIdentityMatchesEntries(&tree, 1);
3595
3596 _ = try tree.put("big", "small", .{ .durability = .buffered });
3597 try expectIdentityMatchesEntries(&tree, 1);
3598
3599 _ = try tree.delete("big", .{ .durability = .buffered });
3600 const drained = try tree.identity();
3601 try std.testing.expectEqual(@as(u64, 0), drained.entries);
3602 try std.testing.expect(drained.state.isEmpty());
3603 }
3604
3605 test "tree identity accumulates across one write batch" {
3606 var tmp = std.testing.tmpDir(.{});
3607 defer tmp.cleanup();
3608
3609 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3610 .paths = .{ .database = "identity.db", .wal = "identity.wal" },
3611 .header = testingHeader(),
3612 });
3613 defer database.deinit();
3614
3615 var tree = try Tree.open(&database, .{ .identity_page = 3 });
3616
3617 var write = try Write.beginTree(&tree);
3618 defer write.deinit();
3619 try write.put(&tree, "a", "1");
3620 try write.put(&tree, "b", "2");
3621 try write.put(&tree, "a", "one");
3622 try write.delete(&tree, "b");
3623 _ = try write.commit(.{ .durability = .buffered });
3624
3625 try expectIdentityMatchesEntries(&tree, 1);
3626 }
3627
3628 test "tree identity survives reopen" {
3629 var tmp = std.testing.tmpDir(.{});
3630 defer tmp.cleanup();
3631
3632 {
3633 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3634 .paths = .{ .database = "identity.db", .wal = "identity.wal" },
3635 .header = testingHeader(),
3636 });
3637 defer database.deinit();
3638
3639 var tree = try Tree.open(&database, .{ .identity_page = 3 });
3640 _ = try tree.put("a", "one", .{});
3641 _ = try tree.put("b", "two", .{});
3642 }
3643
3644 var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3645 .paths = .{ .database = "identity.db", .wal = "identity.wal" },
3646 .header = recoveredHeader(),
3647 });
3648 defer reopened.deinit();
3649
3650 var tree = try Tree.open(&reopened, .{ .identity_page = 3 });
3651 try expectIdentityMatchesEntries(&tree, 2);
3652
3653 _ = try tree.put("c", "three", .{});
3654 try expectIdentityMatchesEntries(&tree, 3);
3655 }
3656
3657 test "tree identity requires an identity page" {
3658 var tmp = std.testing.tmpDir(.{});
3659 defer tmp.cleanup();
3660
3661 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3662 .paths = .{ .database = "identity.db", .wal = "identity.wal" },
3663 .header = testingHeader(),
3664 });
3665 defer database.deinit();
3666
3667 var tree = try Tree.open(&database, .{});
3668 try std.testing.expectError(error.TreeIdentityMissing, tree.identity());
3669
3670 try std.testing.expectError(
3671 error.InvalidPageId,
3672 Tree.open(&database, .{ .identity_page = 2 }),
3673 );
3674 }
3675
3676 test "tree count agrees with the full summary across generated writes" {
3677 for ([_]u32{ 3, 0 }) |identity_page| {
3678 var tmp = std.testing.tmpDir(.{});
3679 defer tmp.cleanup();
3680
3681 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3682 .paths = .{ .database = "count.db", .wal = "count.wal" },
3683 .header = testingHeader(),
3684 });
3685 defer database.deinit();
3686 try database.reserve(.{ .wal_frames = 4096 });
3687
3688 var tree = try Tree.open(&database, .{ .identity_page = identity_page });
3689 try std.testing.expectEqual(@as(usize, 0), try tree.count());
3690
3691 var live: [160]bool = @splat(false);
3692 var live_count: usize = 0;
3693 var large: [page.overflow_capacity + 97]u8 = undefined;
3694 fillLargeValue(&large, 7);
3695 var prng = std.Random.DefaultPrng.init(0x5eed_c0de);
3696 const random = prng.random();
3697 var step: usize = 0;
3698 while (step < 480) : (step += 1) {
3699 const slot = random.uintLessThan(usize, live.len);
3700 var key_buffer: [512]u8 = undefined;
3701 const key = wideKey(&key_buffer, slot);
3702 if (live[slot] and random.uintLessThan(u8, 3) == 0) {
3703 _ = try tree.delete(key, .{ .durability = .buffered });
3704 live[slot] = false;
3705 live_count -= 1;
3706 } else {
3707 const value = if (random.uintLessThan(u8, 8) == 0) large[0..] else key[0..9];
3708 _ = try tree.put(key, value, .{ .durability = .buffered });
3709 if (!live[slot]) live_count += 1;
3710 live[slot] = true;
3711 }
3712 if (step % 40 == 39) {
3713 try std.testing.expectEqual(live_count, try tree.count());
3714 try std.testing.expectEqual(live_count, (try tree.summarize()).entries);
3715 }
3716 }
3717 const summary = try tree.summarize();
3718 try std.testing.expect(summary.max_depth >= 2);
3719 try std.testing.expect(summary.overflow_records > 0);
3720 try std.testing.expectEqual(summary.entries, try tree.count());
3721
3722 _ = try tree.clear(.{ .durability = .buffered });
3723 try std.testing.expectEqual(@as(usize, 0), try tree.count());
3724 }
3725 }
3726
3727 test "tree scans and lookups agree with a model across generated trees" {
3728 var tmp = std.testing.tmpDir(.{});
3729 defer tmp.cleanup();
3730
3731 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3732 .paths = .{ .database = "scan.db", .wal = "scan.wal" },
3733 .header = testingHeader(),
3734 });
3735 defer database.deinit();
3736 try database.reserve(.{ .wal_frames = 8192 });
3737
3738 var tree = try Tree.open(&database, .{});
3739 var versions: [400]u32 = @splat(0);
3740 var prng = std.Random.DefaultPrng.init(0x5ca1_ab1e);
3741 const random = prng.random();
3742 var step: u32 = 1;
3743 while (step <= 900) : (step += 1) {
3744 const slot = random.uintLessThan(usize, versions.len);
3745 var key_buffer: [512]u8 = undefined;
3746 const key = wideKey(&key_buffer, slot);
3747 if (versions[slot] != 0 and random.uintLessThan(u8, 5) == 0) {
3748 _ = try tree.delete(key, .{ .durability = .buffered });
3749 versions[slot] = 0;
3750 } else {
3751 var value_buffer: [model_value_max]u8 = undefined;
3752 _ = try tree.put(key, modelValue(&value_buffer, slot, step), .{ .durability = .buffered });
3753 versions[slot] = step;
3754 }
3755 if (step % 150 == 0) try expectScansMatchModel(&tree, &versions, random);
3756 }
3757 const summary = try tree.summarize();
3758 try std.testing.expect(summary.max_depth >= 3);
3759 try std.testing.expect(summary.overflow_records > 0);
3760 }
3761
3762 test "tree scan validates each leaf it reads" {
3763 var tmp = std.testing.tmpDir(.{});
3764 defer tmp.cleanup();
3765
3766 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3767 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3768 .header = testingHeader(),
3769 });
3770 defer database.deinit();
3771 try database.reserve(.{ .wal_frames = 128 });
3772
3773 var tree = try Tree.open(&database, .{});
3774 var index: usize = 0;
3775 while (index < 24) : (index += 1) {
3776 var key_buffer: [512]u8 = undefined;
3777 _ = try tree.put(wideKey(&key_buffer, index), "v", .{ .durability = .buffered });
3778 }
3779
3780 try corruptLastLeaf(&database, &tree);
3781
3782 var range: Range = undefined;
3783 try tree.range(&range, std.testing.allocator, null, null);
3784 defer range.deinit();
3785 var returned: usize = 0;
3786 while (true) {
3787 const entry = range.next() catch |err| {
3788 try std.testing.expectEqual(error.InvalidPage, err);
3789 break;
3790 };
3791 try std.testing.expect(entry != null);
3792 returned += 1;
3793 }
3794 try std.testing.expect(returned > 0);
3795 try std.testing.expect(returned < index);
3796 try std.testing.expectError(error.InvalidPage, range.next());
3797
3798 var key_buffer: [512]u8 = undefined;
3799 try std.testing.expectError(error.InvalidPage, tree.get(std.testing.allocator, wideKey(&key_buffer, index - 1)));
3800 }
3801
3802 test "tree scan that fails in place releases its read lease" {
3803 var tmp = std.testing.tmpDir(.{});
3804 defer tmp.cleanup();
3805
3806 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3807 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3808 .header = testingHeader(),
3809 });
3810 defer database.deinit();
3811 try database.reserve(.{ .wal_frames = 128 });
3812
3813 var tree = try Tree.open(&database, .{});
3814 var key_buffer: [512]u8 = undefined;
3815 var index: usize = 0;
3816 while (index < 24) : (index += 1) {
3817 _ = try tree.put(wideKey(&key_buffer, index), "v", .{ .durability = .buffered });
3818 }
3819 try corruptLastLeaf(&database, &tree);
3820
3821 var scan: Scan = undefined;
3822 const long_end: [page.size + 1]u8 = @splat(0);
3823 try std.testing.expectError(
3824 error.KeyTooLarge,
3825 tree.scan(&scan, std.testing.allocator, null, &long_end, .value),
3826 );
3827 try std.testing.expectEqual(@as(u8, 0), database.read_leases.active);
3828 try std.testing.expectError(
3829 error.InvalidPage,
3830 tree.scan(&scan, std.testing.allocator, wideKey(&key_buffer, index - 1), null, .value),
3831 );
3832 try std.testing.expectEqual(@as(u8, 0), database.read_leases.active);
3833 }
3834
3835 test "tree reads mark the pages they validate" {
3836 var tmp = std.testing.tmpDir(.{});
3837 defer tmp.cleanup();
3838
3839 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3840 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3841 .header = testingHeader(),
3842 });
3843 defer database.deinit();
3844 try database.reserve(.{ .wal_frames = 128 });
3845
3846 var tree = try Tree.open(&database, .{});
3847 const key_count = 24;
3848 var key_buffer: [512]u8 = undefined;
3849 var index: usize = 0;
3850 while (index < key_count) : (index += 1) {
3851 _ = try tree.put(wideKey(&key_buffer, index), "v", .{ .durability = .buffered });
3852 }
3853
3854 var read = try database.beginRead();
3855 defer read.deinit();
3856 const snapshot = read.snapshot();
3857 const reader = try tree.reader(snapshot);
3858 var root_image: [page.size]u8 = undefined;
3859 try std.testing.expect(!(try readMarkedPage(snapshot, tree.root_page, &root_image)).checked());
3860 const root = try page.Branch.load(&root_image);
3861 const leaves = root.cellCount();
3862 try std.testing.expect(leaves >= 3);
3863
3864 try std.testing.expect(try reader.valueLength(wideKey(&key_buffer, 0)) != null);
3865 try std.testing.expect(try testPageChecked(snapshot, tree.root_page));
3866 try std.testing.expect(try testPageChecked(snapshot, root.childAt(0)));
3867 try std.testing.expect(!try testPageChecked(snapshot, root.childAt(1)));
3868
3869 try std.testing.expect(try reader.lastKey(&key_buffer) != null);
3870 try std.testing.expect(try testPageChecked(snapshot, root.childAt(leaves - 1)));
3871 try std.testing.expect(!try testPageChecked(snapshot, root.childAt(1)));
3872
3873 var keys: Scan = undefined;
3874 try reader.scan(&keys, std.testing.allocator, null, null, .key);
3875 defer keys.deinit();
3876 var scanned: usize = 0;
3877 while (try keys.next()) |_| scanned += 1;
3878 try std.testing.expectEqual(@as(usize, key_count), scanned);
3879 var child: usize = 0;
3880 while (child < leaves) : (child += 1) {
3881 try std.testing.expect(try testPageChecked(snapshot, root.childAt(child)));
3882 }
3883 }
3884
3885 test "tree write validates each snapshot leaf it reads" {
3886 var tmp = std.testing.tmpDir(.{});
3887 defer tmp.cleanup();
3888
3889 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3890 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3891 .header = testingHeader(),
3892 });
3893 defer database.deinit();
3894 try database.reserve(.{ .wal_frames = 128 });
3895
3896 var tree = try Tree.open(&database, .{});
3897 const key_count = 24;
3898 var key_buffer: [512]u8 = undefined;
3899 var index: usize = 0;
3900 while (index < key_count) : (index += 1) {
3901 _ = try tree.put(wideKey(&key_buffer, index), "v", .{ .durability = .buffered });
3902 }
3903 try corruptLastLeaf(&database, &tree);
3904
3905 var write = try Write.beginTree(&tree);
3906 defer write.deinit();
3907 try write.put(&tree, wideKey(&key_buffer, 0), "first");
3908 try write.put(&tree, wideKey(&key_buffer, 0), "again");
3909 const last = write.put(&tree, wideKey(&key_buffer, key_count - 1), "last");
3910 try std.testing.expectError(error.InvalidPage, last);
3911 }
3912
3913 test "tree write trusts a snapshot page only after validating it" {
3914 var tmp = std.testing.tmpDir(.{});
3915 defer tmp.cleanup();
3916
3917 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3918 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3919 .header = testingHeader(),
3920 });
3921 defer database.deinit();
3922 var write = try Write.begin(&database, .{});
3923 defer write.deinit();
3924
3925 const page_id = 3;
3926 const colliding = page_id + validated_page_capacity;
3927 var valid: [page.size]u8 = undefined;
3928 var leaf = page.Leaf.init(&valid, page_id);
3929 try leaf.put("key", "value");
3930 var corrupt = valid;
3931 corrupt[leaf_flags_low_byte] = 1;
3932 const valid_page: SourcedPage = .{ .bytes = &valid, .source = .snapshot };
3933 const corrupt_page: SourcedPage = .{ .bytes = &corrupt, .source = .snapshot };
3934
3935 try std.testing.expectError(error.InvalidPage, write.treePage(page_id, corrupt_page));
3936 try std.testing.expectError(error.InvalidPage, write.treePage(page_id, corrupt_page));
3937 _ = try write.treePage(page_id, valid_page);
3938 _ = try write.treePage(page_id, valid_page);
3939 try std.testing.expectError(error.InvalidPage, write.treePage(colliding, corrupt_page));
3940 try std.testing.expectError(error.InvalidPage, write.treePage(colliding, corrupt_page));
3941 }
3942
3943 test "tree write edits the pages it staged in place" {
3944 var tmp = std.testing.tmpDir(.{});
3945 defer tmp.cleanup();
3946
3947 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
3948 .paths = .{ .database = "tree.db", .wal = "tree.wal" },
3949 .header = testingHeader(),
3950 });
3951 defer database.deinit();
3952 try database.reserve(.{ .wal_frames = 256 });
3953
3954 var tree = try Tree.open(&database, .{});
3955 _ = try tree.put("seed", "v", .{ .durability = .buffered });
3956
3957 var write = try Write.beginTree(&tree);
3958 defer write.deinit();
3959 var scratch: [page.size]u8 = undefined;
3960 const copied = try write.readRootPage(&tree, &scratch);
3961 try std.testing.expectEqual(@intFromPtr(&scratch), @intFromPtr(copied.leaf.bytes));
3962 try write.put(&tree, "seed", "w");
3963 const staged = (try write.transaction.editPage(tree.root_page)).?;
3964 const edited = try write.readRootPage(&tree, &scratch);
3965 try std.testing.expectEqual(@intFromPtr(staged), @intFromPtr(edited.leaf.bytes));
3966
3967 const key_count = 96;
3968 var key_buffer: [512]u8 = undefined;
3969 for (0..key_count) |index| try write.put(&tree, wideKey(&key_buffer, index), "w");
3970 for (0..key_count) |index| {
3971 const key = wideKey(&key_buffer, index);
3972 if (index < 40 or index % 5 == 0) {
3973 try write.delete(&tree, key);
3974 } else if (index % 2 == 1) {
3975 try write.put(&tree, key, "x");
3976 }
3977 }
3978 try write.delete(&tree, "seed");
3979 _ = try write.commit(.{ .durability = .buffered });
3980
3981 var expected_count: usize = 0;
3982 for (0..key_count) |index| {
3983 const value = try tree.get(std.testing.allocator, wideKey(&key_buffer, index));
3984 defer if (value) |bytes| std.testing.allocator.free(bytes);
3985 if (index < 40 or index % 5 == 0) {
3986 try std.testing.expect(value == null);
3987 } else {
3988 expected_count += 1;
3989 const expected = if (index % 2 == 1) "x" else "w";
3990 try std.testing.expectEqualStrings(expected, value.?);
3991 }
3992 }
3993 try std.testing.expectEqual(expected_count, try tree.count());
3994 }
3995
3996 const model_value_max = page.overflow_capacity + 97;
3997
3998 /// Offset of the low byte of a page's flags. `page.kind` does not read it,
3999 /// and full validation requires the flags to be zero.
4000 const leaf_flags_low_byte = 7;
4001
4002 /// Sets the flags of the last leaf under the root branch of `tree` and
4003 /// commits it, so the leaf passes `page.kind` and fails validation.
4004 fn testPageChecked(snapshot: file.Snapshot, page_id: u32) !bool {
4005 var image: [page.size]u8 = undefined;
4006 return (try readMarkedPage(snapshot, page_id, &image)).checked();
4007 }
4008
4009 fn corruptLastLeaf(database: *file.Database, tree: *const Tree) !void {
4010 var last_leaf: u32 = 0;
4011 var leaf_image: [page.size]u8 = undefined;
4012 {
4013 var read = try database.beginRead();
4014 defer read.deinit();
4015 var root_image: [page.size]u8 = undefined;
4016 try readExistingPage(read.snapshot(), tree.root_page, &root_image);
4017 const root = try page.Branch.load(&root_image);
4018 try std.testing.expect(root.cellCount() >= 2);
4019 last_leaf = root.childAt(root.cellCount() - 1);
4020 try readExistingPage(read.snapshot(), last_leaf, &leaf_image);
4021 _ = try page.Leaf.load(&leaf_image);
4022 }
4023 leaf_image[leaf_flags_low_byte] = 1;
4024 var transaction = try database.beginWrite();
4025 defer transaction.deinit();
4026 try transaction.putPage(last_leaf, &leaf_image);
4027 _ = try transaction.commit(.{ .durability = .buffered });
4028 }
4029
4030 /// The value slot `slot` holds after the write at `version`. Every seventh
4031 /// version spills into an overflow chain.
4032 fn modelValue(buffer: *[model_value_max]u8, slot: usize, version: u32) []const u8 {
4033 if (version % 7 == 0) {
4034 fillLargeValue(buffer, @intCast(version % 251));
4035 return buffer;
4036 }
4037 return std.fmt.bufPrint(buffer, "v{d}.{d}", .{ slot, version }) catch unreachable;
4038 }
4039
4040 /// Checks full scans, bounded scans and point lookups against the model. A
4041 /// full scan reads each leaf once. It reads each branch once on the way down
4042 /// and rereads a branch above the leaves' parents once per exhausted child,
4043 /// so it reads at most twice the tree's branch pages.
4044 fn expectScansMatchModel(tree: *const Tree, versions: []const u32, random: std.Random) !void {
4045 const summary = try tree.summarize();
4046 {
4047 var scan: Scan = undefined;
4048 try tree.scan(&scan, std.testing.allocator, null, null, .value);
4049 defer scan.deinit();
4050 try expectScanEntries(&scan, versions, 0, versions.len, .value);
4051 const stats = scan.stats();
4052 try std.testing.expectEqual(summary.leaf_pages, stats.leaf_pages_visited);
4053 try std.testing.expect(stats.branch_pages_visited <= 2 * summary.branch_pages);
4054 }
4055
4056 var trial: usize = 0;
4057 while (trial < 8) : (trial += 1) {
4058 const first = random.uintAtMost(usize, versions.len);
4059 const second = random.uintAtMost(usize, versions.len);
4060 const low = @min(first, second);
4061 const high = @max(first, second);
4062 const bounded_start = random.boolean();
4063 const bounded_end = random.boolean();
4064 var start_buffer: [512]u8 = undefined;
4065 var end_buffer: [512]u8 = undefined;
4066 const start = if (bounded_start) wideKey(&start_buffer, low) else null;
4067 const end = if (bounded_end) wideKey(&end_buffer, high) else null;
4068 const projection: Projection = if (trial % 2 == 0) .key else .value;
4069 var scan: Scan = undefined;
4070 try tree.scan(&scan, std.testing.allocator, start, end, projection);
4071 defer scan.deinit();
4072 try expectScanEntries(
4073 &scan,
4074 versions,
4075 if (bounded_start) low else 0,
4076 if (bounded_end) high else versions.len,
4077 projection,
4078 );
4079 }
4080
4081 trial = 0;
4082 while (trial < 16) : (trial += 1) {
4083 const slot = random.uintLessThan(usize, versions.len);
4084 var key_buffer: [512]u8 = undefined;
4085 const found = try tree.get(std.testing.allocator, wideKey(&key_buffer, slot));
4086 defer if (found) |bytes| std.testing.allocator.free(bytes);
4087 if (versions[slot] == 0) {
4088 try std.testing.expect(found == null);
4089 } else {
4090 var value_buffer: [model_value_max]u8 = undefined;
4091 try std.testing.expectEqualSlices(u8, modelValue(&value_buffer, slot, versions[slot]), found.?);
4092 }
4093 }
4094 }
4095
4096 fn expectScanEntries(scan: *Scan, versions: []const u32, low: usize, high: usize, projection: Projection) !void {
4097 var expected: usize = 0;
4098 var slot = low;
4099 while (slot < high) : (slot += 1) {
4100 if (versions[slot] == 0) continue;
4101 const next_entry = try scan.next();
4102 try std.testing.expect(next_entry != null);
4103 const entry = next_entry.?;
4104 var key_buffer: [512]u8 = undefined;
4105 try std.testing.expectEqualSlices(u8, wideKey(&key_buffer, slot), entry.key);
4106 switch (projection) {
4107 .key => try std.testing.expectEqual(@as(usize, 0), entry.bytes.len),
4108 .value => {
4109 var value_buffer: [model_value_max]u8 = undefined;
4110 try std.testing.expectEqualSlices(u8, modelValue(&value_buffer, slot, versions[slot]), entry.bytes);
4111 },
4112 .record => unreachable,
4113 }
4114 expected += 1;
4115 }
4116 try std.testing.expect(try scan.next() == null);
4117 try std.testing.expectEqual(expected, scan.stats().entries_returned);
4118 }
4119
4120 fn testingHeader() wal.Header {
4121 return .{
4122 .sequence = 201,
4123 .salt = .{ .first = 0x1234_4321, .second = 0xabcd_dcba },
4124 };
4125 }
4126
4127 fn recoveredHeader() wal.Header {
4128 return .{
4129 .sequence = 202,
4130 .salt = .{ .first = 0x5678_8765, .second = 0xfedc_cdef },
4131 };
4132 }
4133
4134 fn wideKey(buffer: *[512]u8, index: usize) []const u8 {
4135 @memset(buffer, 'x');
4136 _ = std.fmt.bufPrint(buffer[0..9], "k{d:0>8}", .{index}) catch unreachable;
4137 return buffer[0..];
4138 }
4139
4140 fn hasSharedChildHash(before: *const Root, after: *const Root) bool {
4141 const before_root = before.rootNode();
4142 const after_root = after.rootNode();
4143 for (before.childIndexes(before_root)) |before_index| {
4144 const before_child = before.nodes[before_index];
4145 for (after.childIndexes(after_root)) |after_index| {
4146 const after_child = after.nodes[after_index];
4147 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;
4148 }
4149 }
4150 return false;
4151 }
4152
4153 fn fillLargeValue(buffer: []u8, seed: u8) void {
4154 for (buffer, 0..) |*byte, index| {
4155 byte.* = @intCast((index + seed) % 251);
4156 }
4157 }