lib/sql/src/page.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const simd = @import("simd");
3 const lattice = @import("lattice.zig");
4 const trace = @import("trace.zig");
5
6 const Bytes = simd.ScalableTag(u8);
7
8 pub const size: usize = 4096;
9 pub const header_size: usize = 32;
10
11 pub const Error = error{
12 FreeListFull,
13 GenerationOverflow,
14 InvalidPage,
15 InvalidPageId,
16 InvalidRange,
17 KeyNotFound,
18 KeyTooLarge,
19 PageFull,
20 ValueTooLarge,
21 };
22
23 pub const Entry = struct {
24 key: []const u8,
25 value: []const u8,
26 };
27
28 pub const BranchEntry = struct {
29 lower: []const u8,
30 child: u32,
31 };
32
33 pub const Kind = enum {
34 leaf,
35 branch,
36 meta,
37 overflow,
38 identity,
39 };
40
41 pub fn kind(bytes: *const [size]u8) Error!Kind {
42 if (!std.mem.eql(u8, bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage;
43 if (bytes[version_offset] != format_version) return error.InvalidPage;
44 return switch (bytes[kind_offset]) {
45 leaf_kind => .leaf,
46 branch_kind => .branch,
47 meta_kind => .meta,
48 overflow_kind => .overflow,
49 identity_kind => .identity,
50 else => error.InvalidPage,
51 };
52 }
53
54 const magic = [_]u8{ 't', 's', 'q', 'l' };
55 const format_version: u8 = 1;
56 const leaf_kind: u8 = 1;
57 const branch_kind: u8 = 2;
58 const meta_kind: u8 = 3;
59 const overflow_kind: u8 = 4;
60 const identity_kind: u8 = 5;
61 const identity_entries_offset: usize = header_size;
62 const identity_key_bytes_offset: usize = header_size + 8;
63 const identity_value_bytes_offset: usize = header_size + 16;
64 const identity_state_offset: usize = header_size + 24;
65 const slot_size: usize = 8;
66 /// Branch cells hold their child page number in this many bytes.
67 pub const child_size: usize = 4;
68 /// A put of a cell no larger than this, counting its key, value and slot
69 /// bytes, succeeds on any page whose cells are no larger: a split that
70 /// balances bytes leaves both halves within one page.
71 pub const cell_bytes_max: usize = (size - header_size) / 2;
72 const magic_offset: usize = 0;
73 const version_offset: usize = 4;
74 const kind_offset: usize = 5;
75 const flags_offset: usize = 6;
76 const id_offset: usize = 8;
77 const generation_offset: usize = 16;
78 const lower_offset: usize = 24;
79 const upper_offset: usize = 26;
80 const cells_offset: usize = 28;
81 const reserved_offset: usize = 30;
82 const meta_highest_offset: usize = 24;
83 const meta_free_count_offset: usize = 28;
84 const meta_reserved_offset: usize = 30;
85 const meta_entry_size: usize = 4;
86 const meta_chained_flag: u16 = 1;
87 const meta_chain_offset: usize = 32;
88 const meta_chained_entries_offset: usize = meta_chain_offset + meta_entry_size;
89 pub const meta_chain_page_entries: usize = (size - meta_chained_entries_offset) / meta_entry_size;
90 const overflow_next_offset: usize = 24;
91 const overflow_used_offset: usize = 28;
92 const overflow_reserved_offset: usize = 30;
93 pub const overflow_capacity: usize = size - header_size;
94
95 const Slot = struct {
96 offset: u16,
97 key_len: u16,
98 value_len: u16,
99 flags: u16 = 0,
100 };
101
102 pub const Leaf = struct {
103 bytes: *[size]u8,
104
105 pub fn init(bytes: *[size]u8, page_id: u64) Leaf {
106 var leaf = Leaf{ .bytes = bytes };
107 @memset(leaf.bytes, 0);
108 @memcpy(leaf.bytes[magic_offset..][0..magic.len], magic[0..]);
109 leaf.bytes[version_offset] = format_version;
110 leaf.bytes[kind_offset] = leaf_kind;
111 leaf.writeU16(flags_offset, 0);
112 leaf.writeU64(id_offset, page_id);
113 leaf.writeU64(generation_offset, 0);
114 leaf.writeU16(lower_offset, header_size);
115 leaf.writeU16(upper_offset, size);
116 leaf.writeU16(cells_offset, 0);
117 leaf.writeU16(reserved_offset, 0);
118 return leaf;
119 }
120
121 pub fn load(bytes: *[size]u8) Error!Leaf {
122 const leaf = Leaf{ .bytes = bytes };
123 try leaf.validate();
124 return leaf;
125 }
126
127 /// Wraps a leaf image that `load` validated, without walking its cells
128 /// again. The image must be unchanged since that `load`. A reader that
129 /// returns to one leaf once per cell validates it once through `load` and
130 /// resumes through this.
131 pub fn fromValidated(bytes: *[size]u8) Leaf {
132 std.debug.assert(bytes[kind_offset] == leaf_kind);
133 return .{ .bytes = bytes };
134 }
135
136 pub fn id(self: *const Leaf) u64 {
137 return self.readU64(id_offset);
138 }
139
140 pub fn generation(self: *const Leaf) u64 {
141 return self.readU64(generation_offset);
142 }
143
144 pub fn cellCount(self: *const Leaf) usize {
145 return self.readU16(cells_offset);
146 }
147
148 pub fn firstKey(self: *const Leaf) ?[]const u8 {
149 if (self.cellCount() == 0) return null;
150 return self.keyAt(0);
151 }
152
153 pub fn freeBytes(self: *const Leaf) usize {
154 const lower_bound = self.lower();
155 const upper_bound = self.upper();
156 if (upper_bound < lower_bound) return 0;
157 return upper_bound - lower_bound;
158 }
159
160 pub fn usedBytes(self: *const Leaf) usize {
161 return size - self.freeBytes();
162 }
163
164 pub fn get(self: *const Leaf, key: []const u8) ?[]const u8 {
165 const phase = trace.scope("page.leaf.get");
166 defer phase.end();
167 const index = self.lowerBound(key);
168 if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), key)) return self.valueAt(index);
169 return null;
170 }
171
172 pub fn put(self: *Leaf, key: []const u8, value: []const u8) Error!void {
173 const phase = trace.scope("page.leaf.put");
174 defer phase.end();
175 try checkLengths(key, value);
176 const next_generation = try self.nextGeneration();
177
178 const existing_index = self.lowerBound(key);
179 if (existing_index == self.cellCount() or
180 !std.mem.eql(u8, self.keyAt(existing_index), key))
181 {
182 try self.cells().insert(existing_index, key, value);
183 self.writeU64(generation_offset, next_generation);
184 trace.progress("page.leaf.put.insert.complete");
185 return;
186 }
187 const slot = self.slotAt(existing_index);
188 if (value.len == slot.value_len) {
189 const value_offset: usize = slot.offset + slot.key_len;
190 @memcpy(self.bytes[value_offset..][0..value.len], value);
191 self.writeU64(generation_offset, next_generation);
192 trace.progress("page.leaf.put.inplace.complete");
193 return;
194 }
195
196 var scratch: [size]u8 = undefined;
197 var rebuilt = Leaf.init(&scratch, self.id());
198 rebuilt.writeU64(generation_offset, next_generation);
199
200 var inserted = false;
201 var index: usize = 0;
202 while (index < self.cellCount()) : (index += 1) {
203 const entry = self.entryAt(index);
204 switch (simd.order(Bytes, entry.key, key)) {
205 .lt => try rebuilt.appendEntry(entry.key, entry.value),
206 .eq => {
207 if (!inserted) {
208 try rebuilt.appendEntry(key, value);
209 inserted = true;
210 }
211 },
212 .gt => {
213 if (!inserted) {
214 try rebuilt.appendEntry(key, value);
215 inserted = true;
216 }
217 try rebuilt.appendEntry(entry.key, entry.value);
218 },
219 }
220 }
221 if (!inserted) try rebuilt.appendEntry(key, value);
222
223 self.bytes.* = scratch;
224 trace.progress("page.leaf.put.complete");
225 }
226
227 pub fn delete(self: *Leaf, key: []const u8) Error!void {
228 const phase = trace.scope("page.leaf.delete");
229 defer phase.end();
230 const next_generation = try self.nextGeneration();
231 const index = self.lowerBound(key);
232 if (index == self.cellCount() or !std.mem.eql(u8, self.keyAt(index), key)) {
233 return error.KeyNotFound;
234 }
235 self.cells().remove(index);
236 self.writeU64(generation_offset, next_generation);
237 trace.progress("page.leaf.delete.complete");
238 }
239
240 pub fn range(self: *const Leaf, start: ?[]const u8, end: ?[]const u8) Error!Range {
241 if (start) |lower_key| {
242 if (end) |upper_key| {
243 if (simd.order(Bytes, lower_key, upper_key) == .gt) return error.InvalidRange;
244 }
245 }
246 return .{
247 .leaf = self,
248 .end = end,
249 .index = if (start) |key| self.lowerBound(key) else 0,
250 };
251 }
252
253 pub fn splitPut(self: *const Leaf, left: *Leaf, right: *Leaf, key: []const u8, value: []const u8) Error![]const u8 {
254 const phase = trace.scope("page.leaf.split_put");
255 defer phase.end();
256 try checkLengths(key, value);
257 const next_generation = try self.nextGeneration();
258 left.writeU64(generation_offset, next_generation);
259 right.writeU64(generation_offset, next_generation);
260
261 var replacement = false;
262 var index: usize = 0;
263 while (index < self.cellCount()) : (index += 1) {
264 if (std.mem.eql(u8, self.keyAt(index), key)) replacement = true;
265 }
266
267 const total = self.cellCount() + if (replacement) @as(usize, 0) else 1;
268 const split_index = try splitIndexFor(self, key, value.len, total);
269 var ordinal: usize = 0;
270 var inserted = false;
271 index = 0;
272 while (index < self.cellCount()) : (index += 1) {
273 const entry = self.entryAt(index);
274 switch (simd.order(Bytes, entry.key, key)) {
275 .lt => {
276 try appendSplitEntry(left, right, split_index, &ordinal, entry.key, entry.value);
277 },
278 .eq => {
279 if (!inserted) {
280 try appendSplitEntry(left, right, split_index, &ordinal, key, value);
281 inserted = true;
282 }
283 },
284 .gt => {
285 if (!inserted) {
286 try appendSplitEntry(left, right, split_index, &ordinal, key, value);
287 inserted = true;
288 }
289 try appendSplitEntry(left, right, split_index, &ordinal, entry.key, entry.value);
290 },
291 }
292 }
293 if (!inserted) try appendSplitEntry(left, right, split_index, &ordinal, key, value);
294 return right.firstKey() orelse error.InvalidPage;
295 }
296
297 pub fn copyTo(self: *const Leaf, target: *Leaf) Error!void {
298 target.writeU64(generation_offset, self.generation());
299 var index: usize = 0;
300 while (index < self.cellCount()) : (index += 1) {
301 const entry = self.entryAt(index);
302 try target.appendEntry(entry.key, entry.value);
303 }
304 }
305
306 fn validate(self: *const Leaf) Error!void {
307 if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage;
308 if (self.bytes[version_offset] != format_version) return error.InvalidPage;
309 if (self.bytes[kind_offset] != leaf_kind) return error.InvalidPage;
310 if (self.readU16(flags_offset) != 0) return error.InvalidPage;
311 if (self.readU16(reserved_offset) != 0) return error.InvalidPage;
312 const count = self.cellCount();
313 if (count > (size - header_size) / slot_size) return error.InvalidPage;
314 const lower_bound = self.lower();
315 const upper_bound = self.upper();
316 if (lower_bound != header_size + count * slot_size) return error.InvalidPage;
317 if (upper_bound < lower_bound or upper_bound > size) return error.InvalidPage;
318
319 var index: usize = 0;
320 while (index < count) : (index += 1) {
321 const slot = self.slotAt(index);
322 const offset: usize = slot.offset;
323 const payload_end = offset + @as(usize, slot.key_len) + @as(usize, slot.value_len);
324 if (offset < upper_bound or payload_end > size) return error.InvalidPage;
325 if (slot.flags != 0) return error.InvalidPage;
326 if (index > 0 and simd.order(Bytes, self.keyAt(index - 1), self.keyAt(index)) != .lt) return error.InvalidPage;
327 }
328 }
329
330 fn appendEntry(self: *Leaf, key: []const u8, value: []const u8) Error!void {
331 try self.cells().insert(self.cellCount(), key, value);
332 }
333
334 fn cells(self: *Leaf) Cells {
335 return .{ .bytes = self.bytes };
336 }
337
338 fn lowerBound(self: *const Leaf, key: []const u8) usize {
339 var low: usize = 0;
340 var high = self.cellCount();
341 while (low < high) {
342 const mid = low + (high - low) / 2;
343 switch (simd.order(Bytes, self.keyAt(mid), key)) {
344 .lt => low = mid + 1,
345 .eq, .gt => high = mid,
346 }
347 }
348 return low;
349 }
350
351 fn nextGeneration(self: *const Leaf) Error!u64 {
352 const current = self.generation();
353 if (current == std.math.maxInt(u64)) return error.GenerationOverflow;
354 return current + 1;
355 }
356
357 pub fn lastKey(self: *const Leaf) ?[]const u8 {
358 const count = self.cellCount();
359 if (count == 0) return null;
360 return self.keyAt(count - 1);
361 }
362
363 fn entryAt(self: *const Leaf, index: usize) Entry {
364 return .{ .key = self.keyAt(index), .value = self.valueAt(index) };
365 }
366
367 fn keyAt(self: *const Leaf, index: usize) []const u8 {
368 const slot = self.slotAt(index);
369 const start: usize = slot.offset;
370 return self.bytes[start..][0..slot.key_len];
371 }
372
373 fn valueAt(self: *const Leaf, index: usize) []const u8 {
374 const slot = self.slotAt(index);
375 const start: usize = slot.offset + slot.key_len;
376 return self.bytes[start..][0..slot.value_len];
377 }
378
379 fn slotAt(self: *const Leaf, index: usize) Slot {
380 const offset = header_size + index * slot_size;
381 return .{
382 .offset = self.readU16(offset),
383 .key_len = self.readU16(offset + 2),
384 .value_len = self.readU16(offset + 4),
385 .flags = self.readU16(offset + 6),
386 };
387 }
388
389 fn lower(self: *const Leaf) usize {
390 return self.readU16(lower_offset);
391 }
392
393 fn upper(self: *const Leaf) usize {
394 return self.readU16(upper_offset);
395 }
396
397 fn readU16(self: *const Leaf, offset: usize) u16 {
398 return std.mem.readInt(u16, self.bytes[offset..][0..2], .big);
399 }
400
401 fn readU64(self: *const Leaf, offset: usize) u64 {
402 return std.mem.readInt(u64, self.bytes[offset..][0..8], .big);
403 }
404
405 fn writeU16(self: *Leaf, offset: usize, value: u16) void {
406 std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big);
407 }
408
409 fn writeU64(self: *Leaf, offset: usize, value: u64) void {
410 std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big);
411 }
412 };
413
414 pub const Branch = struct {
415 bytes: *[size]u8,
416
417 pub fn init(bytes: *[size]u8, page_id: u64) Branch {
418 var branch = Branch{ .bytes = bytes };
419 @memset(branch.bytes, 0);
420 @memcpy(branch.bytes[magic_offset..][0..magic.len], magic[0..]);
421 branch.bytes[version_offset] = format_version;
422 branch.bytes[kind_offset] = branch_kind;
423 branch.writeU16(flags_offset, 0);
424 branch.writeU64(id_offset, page_id);
425 branch.writeU64(generation_offset, 0);
426 branch.writeU16(lower_offset, header_size);
427 branch.writeU16(upper_offset, size);
428 branch.writeU16(cells_offset, 0);
429 branch.writeU16(reserved_offset, 0);
430 return branch;
431 }
432
433 pub fn load(bytes: *[size]u8) Error!Branch {
434 const branch = Branch{ .bytes = bytes };
435 try branch.validate();
436 return branch;
437 }
438
439 /// Wraps a branch image that `load` validated, without walking its cells
440 /// again. The image must be unchanged since that `load`.
441 pub fn fromValidated(bytes: *[size]u8) Branch {
442 std.debug.assert(bytes[kind_offset] == branch_kind);
443 return .{ .bytes = bytes };
444 }
445
446 pub fn id(self: *const Branch) u64 {
447 return self.readU64(id_offset);
448 }
449
450 pub fn generation(self: *const Branch) u64 {
451 return self.readU64(generation_offset);
452 }
453
454 pub fn cellCount(self: *const Branch) usize {
455 return self.readU16(cells_offset);
456 }
457
458 pub fn childAt(self: *const Branch, index: usize) u32 {
459 return self.childPayloadAt(index);
460 }
461
462 pub fn lowerAt(self: *const Branch, index: usize) []const u8 {
463 return self.keyAt(index);
464 }
465
466 pub fn firstLower(self: *const Branch) ?[]const u8 {
467 if (self.cellCount() == 0) return null;
468 return self.keyAt(0);
469 }
470
471 pub fn childIndexFor(self: *const Branch, key: []const u8) usize {
472 const index = self.lowerBound(key);
473 if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), key)) return index;
474 if (index == 0) return 0;
475 return index - 1;
476 }
477
478 pub fn childFor(self: *const Branch, key: []const u8) u32 {
479 return self.childAt(self.childIndexFor(key));
480 }
481
482 pub fn put(self: *Branch, lower_key: []const u8, child: u32) Error!void {
483 if (child == 0) return error.InvalidPage;
484 const child_bytes = childBytes(child);
485 try checkLengths(lower_key, child_bytes[0..]);
486 const next_generation = try self.nextGeneration();
487 const index = self.lowerBound(lower_key);
488 if (index < self.cellCount() and std.mem.eql(u8, self.keyAt(index), lower_key)) {
489 const slot = self.slotAt(index);
490 const child_offset: usize = slot.offset + slot.key_len;
491 self.bytes[child_offset..][0..child_bytes.len].* = child_bytes;
492 } else {
493 try self.cells().insert(index, lower_key, child_bytes[0..]);
494 }
495 self.writeU64(generation_offset, next_generation);
496 }
497
498 pub fn splitPut(self: *const Branch, left: *Branch, right: *Branch, lower_key: []const u8, child: u32) Error![]const u8 {
499 if (child == 0) return error.InvalidPage;
500 const child_bytes = childBytes(child);
501 try checkLengths(lower_key, child_bytes[0..]);
502 const next_generation = try self.nextGeneration();
503 left.writeU64(generation_offset, next_generation);
504 right.writeU64(generation_offset, next_generation);
505
506 var replacement = false;
507 var index: usize = 0;
508 while (index < self.cellCount()) : (index += 1) {
509 if (std.mem.eql(u8, self.keyAt(index), lower_key)) replacement = true;
510 }
511
512 const total = self.cellCount() + if (replacement) @as(usize, 0) else 1;
513 const split_index = try splitIndexFor(self, lower_key, child_bytes.len, total);
514 var ordinal: usize = 0;
515 var inserted = false;
516 index = 0;
517 while (index < self.cellCount()) : (index += 1) {
518 const entry = self.entryAt(index);
519 switch (simd.order(Bytes, entry.lower, lower_key)) {
520 .lt => try appendSplitBranchEntry(left, right, split_index, &ordinal, entry.lower, entry.child),
521 .eq => {
522 if (!inserted) {
523 try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child);
524 inserted = true;
525 }
526 },
527 .gt => {
528 if (!inserted) {
529 try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child);
530 inserted = true;
531 }
532 try appendSplitBranchEntry(left, right, split_index, &ordinal, entry.lower, entry.child);
533 },
534 }
535 }
536 if (!inserted) try appendSplitBranchEntry(left, right, split_index, &ordinal, lower_key, child);
537 return right.firstLower() orelse error.InvalidPage;
538 }
539
540 pub fn replace(self: *Branch, index: usize, lower_key: []const u8, child: u32) Error!void {
541 if (index >= self.cellCount()) return error.InvalidPage;
542 if (child == 0) return error.InvalidPage;
543 const child_bytes = childBytes(child);
544 try checkLengths(lower_key, child_bytes[0..]);
545 const next_generation = try self.nextGeneration();
546
547 var scratch: [size]u8 = undefined;
548 var rebuilt = Branch.init(&scratch, self.id());
549 rebuilt.writeU64(generation_offset, next_generation);
550
551 var cursor: usize = 0;
552 while (cursor < self.cellCount()) : (cursor += 1) {
553 if (cursor == index) {
554 try rebuilt.appendEntry(lower_key, child);
555 } else {
556 const entry = self.entryAt(cursor);
557 try rebuilt.appendEntry(entry.lower, entry.child);
558 }
559 }
560 self.bytes.* = scratch;
561 }
562
563 pub fn remove(self: *Branch, index: usize) Error!void {
564 if (index >= self.cellCount()) return error.InvalidPage;
565 const next_generation = try self.nextGeneration();
566 self.cells().remove(index);
567 self.writeU64(generation_offset, next_generation);
568 }
569
570 pub fn copyTo(self: *const Branch, target: *Branch) Error!void {
571 target.writeU64(generation_offset, self.generation());
572 var index: usize = 0;
573 while (index < self.cellCount()) : (index += 1) {
574 const entry = self.entryAt(index);
575 try target.appendEntry(entry.lower, entry.child);
576 }
577 }
578
579 fn validate(self: *const Branch) Error!void {
580 if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage;
581 if (self.bytes[version_offset] != format_version) return error.InvalidPage;
582 if (self.bytes[kind_offset] != branch_kind) return error.InvalidPage;
583 if (self.readU16(flags_offset) != 0) return error.InvalidPage;
584 if (self.readU16(reserved_offset) != 0) return error.InvalidPage;
585 const count = self.cellCount();
586 if (count > (size - header_size) / slot_size) return error.InvalidPage;
587 const lower_bound = self.lower();
588 const upper_bound = self.upper();
589 if (lower_bound != header_size + count * slot_size) return error.InvalidPage;
590 if (upper_bound < lower_bound or upper_bound > size) return error.InvalidPage;
591 if (count == 0) return error.InvalidPage;
592
593 var index: usize = 0;
594 while (index < count) : (index += 1) {
595 const slot = self.slotAt(index);
596 const offset: usize = slot.offset;
597 const payload_end = offset + @as(usize, slot.key_len) + @as(usize, slot.value_len);
598 if (offset < upper_bound or payload_end > size) return error.InvalidPage;
599 if (slot.flags != 0) return error.InvalidPage;
600 if (slot.value_len != 4) return error.InvalidPage;
601 if (self.childPayloadAt(index) == 0) return error.InvalidPage;
602 if (index > 0 and simd.order(Bytes, self.keyAt(index - 1), self.keyAt(index)) != .lt) return error.InvalidPage;
603 }
604 }
605
606 fn appendEntry(self: *Branch, lower_key: []const u8, child: u32) Error!void {
607 const child_bytes = childBytes(child);
608 try self.cells().insert(self.cellCount(), lower_key, child_bytes[0..]);
609 }
610
611 fn cells(self: *Branch) Cells {
612 return .{ .bytes = self.bytes };
613 }
614
615 fn entryAt(self: *const Branch, index: usize) BranchEntry {
616 return .{ .lower = self.keyAt(index), .child = self.childPayloadAt(index) };
617 }
618
619 fn lowerBound(self: *const Branch, key: []const u8) usize {
620 var low: usize = 0;
621 var high = self.cellCount();
622 while (low < high) {
623 const mid = low + (high - low) / 2;
624 switch (simd.order(Bytes, self.keyAt(mid), key)) {
625 .lt => low = mid + 1,
626 .eq, .gt => high = mid,
627 }
628 }
629 return low;
630 }
631
632 fn nextGeneration(self: *const Branch) Error!u64 {
633 const current = self.generation();
634 if (current == std.math.maxInt(u64)) return error.GenerationOverflow;
635 return current + 1;
636 }
637
638 fn keyAt(self: *const Branch, index: usize) []const u8 {
639 const slot = self.slotAt(index);
640 const start: usize = slot.offset;
641 return self.bytes[start..][0..slot.key_len];
642 }
643
644 fn childPayloadAt(self: *const Branch, index: usize) u32 {
645 const slot = self.slotAt(index);
646 const start: usize = slot.offset + slot.key_len;
647 return std.mem.readInt(u32, self.bytes[start..][0..4], .big);
648 }
649
650 fn slotAt(self: *const Branch, index: usize) Slot {
651 const offset = header_size + index * slot_size;
652 return .{
653 .offset = self.readU16(offset),
654 .key_len = self.readU16(offset + 2),
655 .value_len = self.readU16(offset + 4),
656 .flags = self.readU16(offset + 6),
657 };
658 }
659
660 fn lower(self: *const Branch) usize {
661 return self.readU16(lower_offset);
662 }
663
664 fn upper(self: *const Branch) usize {
665 return self.readU16(upper_offset);
666 }
667
668 fn readU16(self: *const Branch, offset: usize) u16 {
669 return std.mem.readInt(u16, self.bytes[offset..][0..2], .big);
670 }
671
672 fn readU64(self: *const Branch, offset: usize) u64 {
673 return std.mem.readInt(u64, self.bytes[offset..][0..8], .big);
674 }
675
676 fn writeU16(self: *Branch, offset: usize, value: u16) void {
677 std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big);
678 }
679
680 fn writeU64(self: *Branch, offset: usize, value: u64) void {
681 std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big);
682 }
683 };
684
685 pub const Identity = struct {
686 bytes: *[size]u8,
687
688 pub const state_size = lattice.encoded_size;
689
690 pub fn init(bytes: *[size]u8, page_id: u64) Identity {
691 var identity = Identity{ .bytes = bytes };
692 @memset(identity.bytes, 0);
693 @memcpy(identity.bytes[magic_offset..][0..magic.len], magic[0..]);
694 identity.bytes[version_offset] = format_version;
695 identity.bytes[kind_offset] = identity_kind;
696 std.mem.writeInt(u16, identity.bytes[flags_offset..][0..2], 0, .big);
697 std.mem.writeInt(u64, identity.bytes[id_offset..][0..8], page_id, .big);
698 std.mem.writeInt(u64, identity.bytes[generation_offset..][0..8], 0, .big);
699 return identity;
700 }
701
702 pub fn load(bytes: *[size]u8) Error!Identity {
703 if (try kind(bytes) != .identity) return error.InvalidPage;
704 return .{ .bytes = bytes };
705 }
706
707 pub fn entries(self: *const Identity) u64 {
708 return std.mem.readInt(u64, self.bytes[identity_entries_offset..][0..8], .big);
709 }
710
711 pub fn setEntries(self: *Identity, value: u64) void {
712 std.mem.writeInt(u64, self.bytes[identity_entries_offset..][0..8], value, .big);
713 }
714
715 pub fn keyBytes(self: *const Identity) u64 {
716 return std.mem.readInt(u64, self.bytes[identity_key_bytes_offset..][0..8], .big);
717 }
718
719 pub fn setKeyBytes(self: *Identity, value: u64) void {
720 std.mem.writeInt(u64, self.bytes[identity_key_bytes_offset..][0..8], value, .big);
721 }
722
723 pub fn valueBytes(self: *const Identity) u64 {
724 return std.mem.readInt(u64, self.bytes[identity_value_bytes_offset..][0..8], .big);
725 }
726
727 pub fn setValueBytes(self: *Identity, value: u64) void {
728 std.mem.writeInt(u64, self.bytes[identity_value_bytes_offset..][0..8], value, .big);
729 }
730
731 pub fn state(self: *const Identity) lattice.State {
732 return lattice.State.decode(self.bytes[identity_state_offset..][0..state_size]);
733 }
734
735 pub fn setState(self: *Identity, value: *const lattice.State) void {
736 value.encode(self.bytes[identity_state_offset..][0..state_size]);
737 }
738 };
739
740 pub const Meta = struct {
741 bytes: *[size]u8,
742
743 pub fn init(bytes: *[size]u8, page_id: u64, highest_page: u32) Meta {
744 var meta = Meta{ .bytes = bytes };
745 @memset(meta.bytes, 0);
746 @memcpy(meta.bytes[magic_offset..][0..magic.len], magic[0..]);
747 meta.bytes[version_offset] = format_version;
748 meta.bytes[kind_offset] = meta_kind;
749 meta.writeU16(flags_offset, 0);
750 meta.writeU64(id_offset, page_id);
751 meta.writeU64(generation_offset, 0);
752 meta.writeU32(meta_highest_offset, highest_page);
753 meta.writeU16(meta_free_count_offset, 0);
754 meta.writeU16(meta_reserved_offset, 0);
755 return meta;
756 }
757
758 pub fn load(bytes: *[size]u8) Error!Meta {
759 const meta = Meta{ .bytes = bytes };
760 try meta.validate();
761 return meta;
762 }
763
764 pub fn id(self: *const Meta) u64 {
765 return self.readU64(id_offset);
766 }
767
768 pub fn generation(self: *const Meta) u64 {
769 return self.readU64(generation_offset);
770 }
771
772 pub fn highestPage(self: *const Meta) u32 {
773 return self.readU32(meta_highest_offset);
774 }
775
776 pub fn freeCount(self: *const Meta) usize {
777 return self.readU16(meta_free_count_offset);
778 }
779
780 pub fn isChained(self: *const Meta) bool {
781 return self.readU16(flags_offset) & meta_chained_flag != 0;
782 }
783
784 pub fn chainHead(self: *const Meta) u32 {
785 if (!self.isChained()) return 0;
786 return self.readU32(meta_chain_offset);
787 }
788
789 pub fn freeCapacity(self: *const Meta) usize {
790 return (size - self.entriesOffset()) / meta_entry_size;
791 }
792
793 fn entriesOffset(self: *const Meta) usize {
794 return if (self.isChained()) meta_chained_entries_offset else header_size;
795 }
796
797 pub fn allocate(self: *Meta) Error!u32 {
798 const next_generation = try self.nextGeneration();
799 const count = self.freeCount();
800 if (count > 0) {
801 const page_id = self.freeAt(count - 1);
802 self.writeU16(meta_free_count_offset, @intCast(count - 1));
803 self.writeU64(generation_offset, next_generation);
804 return page_id;
805 }
806 const highest = self.highestPage();
807 if (highest == std.math.maxInt(u32)) return error.InvalidPageId;
808 const page_id = highest + 1;
809 self.writeU32(meta_highest_offset, page_id);
810 self.writeU64(generation_offset, next_generation);
811 return page_id;
812 }
813
814 pub fn reserveThrough(self: *Meta, page_id: u32) Error!bool {
815 if (page_id == 0) return error.InvalidPageId;
816 if (page_id <= self.highestPage()) return false;
817 const next_generation = try self.nextGeneration();
818 self.writeU32(meta_highest_offset, page_id);
819 self.writeU64(generation_offset, next_generation);
820 return true;
821 }
822
823 pub fn release(self: *Meta, page_id: u32) Error!void {
824 if (page_id == 0 or @as(u64, page_id) == self.id() or page_id > self.highestPage()) return error.InvalidPageId;
825 if (self.contains(page_id)) return error.InvalidPage;
826 if (page_id == self.highestPage()) return self.releaseHighest();
827 const count = self.freeCount();
828 if (count >= self.freeCapacity()) return error.FreeListFull;
829 const next_generation = try self.nextGeneration();
830 self.writeFree(count, page_id);
831 self.writeU16(meta_free_count_offset, @intCast(count + 1));
832 self.writeU64(generation_offset, next_generation);
833 }
834
835 pub fn spillEntries(self: *Meta, buffer: []u32) Error!usize {
836 const count = self.freeCount();
837 if (count == 0 or count > buffer.len) return error.InvalidPage;
838 const next_generation = try self.nextGeneration();
839 var index: usize = 0;
840 while (index < count) : (index += 1) buffer[index] = self.freeAt(index);
841 self.writeU16(meta_free_count_offset, 0);
842 self.writeU64(generation_offset, next_generation);
843 return count;
844 }
845
846 pub fn adoptChain(self: *Meta, head: u32) Error!void {
847 if (head == 0 or @as(u64, head) == self.id() or head > self.highestPage()) return error.InvalidPageId;
848 if (self.freeCount() != 0) return error.InvalidPage;
849 const next_generation = try self.nextGeneration();
850 self.writeU16(flags_offset, meta_chained_flag);
851 self.writeU32(meta_chain_offset, head);
852 self.writeU64(generation_offset, next_generation);
853 }
854
855 pub fn refillFromChain(self: *Meta, next_head: u32, entries: []const u32) Error!void {
856 if (!self.isChained()) return error.InvalidPage;
857 if (self.freeCount() != 0) return error.InvalidPage;
858 if (next_head != 0 and (@as(u64, next_head) == self.id() or next_head > self.highestPage())) return error.InvalidPageId;
859 for (entries) |entry| {
860 if (entry == 0 or @as(u64, entry) == self.id() or entry > self.highestPage()) return error.InvalidPage;
861 }
862 const target_entries_offset: usize = if (next_head == 0) header_size else meta_chained_entries_offset;
863 if (entries.len > (size - target_entries_offset) / meta_entry_size) return error.InvalidPage;
864 const next_generation = try self.nextGeneration();
865 if (next_head == 0) {
866 self.writeU16(flags_offset, 0);
867 self.writeU32(meta_chain_offset, 0);
868 } else {
869 self.writeU32(meta_chain_offset, next_head);
870 }
871 for (entries, 0..) |entry, index| self.writeFree(index, entry);
872 self.writeU16(meta_free_count_offset, @intCast(entries.len));
873 self.writeU64(generation_offset, next_generation);
874 }
875
876 pub fn freeAt(self: *const Meta, index: usize) u32 {
877 return self.readU32(self.entriesOffset() + index * meta_entry_size);
878 }
879
880 fn validate(self: *const Meta) Error!void {
881 if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage;
882 if (self.bytes[version_offset] != format_version) return error.InvalidPage;
883 if (self.bytes[kind_offset] != meta_kind) return error.InvalidPage;
884 const flags = self.readU16(flags_offset);
885 if (flags & ~meta_chained_flag != 0) return error.InvalidPage;
886 if (self.readU16(meta_reserved_offset) != 0) return error.InvalidPage;
887 if (flags & meta_chained_flag != 0) {
888 const head = self.readU32(meta_chain_offset);
889 if (head == 0 or @as(u64, head) == self.id() or head > self.highestPage()) return error.InvalidPage;
890 }
891 const count = self.freeCount();
892 if (count > self.freeCapacity()) return error.InvalidPage;
893 if (self.highestPage() == 0) return error.InvalidPage;
894 var index: usize = 0;
895 while (index < count) : (index += 1) {
896 const page_id = self.freeAt(index);
897 if (page_id == 0 or @as(u64, page_id) == self.id() or page_id > self.highestPage()) return error.InvalidPage;
898 var compare: usize = index + 1;
899 while (compare < count) : (compare += 1) {
900 if (page_id == self.freeAt(compare)) return error.InvalidPage;
901 }
902 }
903 }
904
905 fn contains(self: *const Meta, page_id: u32) bool {
906 var index: usize = 0;
907 while (index < self.freeCount()) : (index += 1) {
908 if (self.freeAt(index) == page_id) return true;
909 }
910 return false;
911 }
912
913 fn releaseHighest(self: *Meta) Error!void {
914 const next_generation = try self.nextGeneration();
915 var highest = self.highestPage() - 1;
916 var count = self.freeCount();
917 while (count > 0) {
918 const index = self.freeIndex(highest, count) orelse break;
919 count -= 1;
920 if (index != count) self.writeFree(index, self.freeAt(count));
921 highest -= 1;
922 }
923 self.writeU32(meta_highest_offset, highest);
924 self.writeU16(meta_free_count_offset, @intCast(count));
925 self.writeU64(generation_offset, next_generation);
926 }
927
928 fn freeIndex(self: *const Meta, page_id: u32, count: usize) ?usize {
929 var index: usize = 0;
930 while (index < count) : (index += 1) {
931 if (self.freeAt(index) == page_id) return index;
932 }
933 return null;
934 }
935
936 fn nextGeneration(self: *const Meta) Error!u64 {
937 const current = self.generation();
938 if (current == std.math.maxInt(u64)) return error.GenerationOverflow;
939 return current + 1;
940 }
941
942 fn writeFree(self: *Meta, index: usize, page_id: u32) void {
943 self.writeU32(self.entriesOffset() + index * meta_entry_size, page_id);
944 }
945
946 fn readU16(self: *const Meta, offset: usize) u16 {
947 return std.mem.readInt(u16, self.bytes[offset..][0..2], .big);
948 }
949
950 fn readU32(self: *const Meta, offset: usize) u32 {
951 return std.mem.readInt(u32, self.bytes[offset..][0..4], .big);
952 }
953
954 fn readU64(self: *const Meta, offset: usize) u64 {
955 return std.mem.readInt(u64, self.bytes[offset..][0..8], .big);
956 }
957
958 fn writeU16(self: *Meta, offset: usize, value: u16) void {
959 std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big);
960 }
961
962 fn writeU32(self: *Meta, offset: usize, value: u32) void {
963 std.mem.writeInt(u32, self.bytes[offset..][0..4], value, .big);
964 }
965
966 fn writeU64(self: *Meta, offset: usize, value: u64) void {
967 std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big);
968 }
969 };
970
971 pub const Overflow = struct {
972 bytes: *[size]u8,
973
974 pub fn init(bytes: *[size]u8, page_id: u64, next_page: u32, fragment: []const u8) Error!Overflow {
975 if (fragment.len == 0 or fragment.len > overflow_capacity) return error.ValueTooLarge;
976 if (next_page != 0 and @as(u64, next_page) == page_id) return error.InvalidPageId;
977 var overflow = Overflow{ .bytes = bytes };
978 @memset(overflow.bytes, 0);
979 @memcpy(overflow.bytes[magic_offset..][0..magic.len], magic[0..]);
980 overflow.bytes[version_offset] = format_version;
981 overflow.bytes[kind_offset] = overflow_kind;
982 overflow.writeU16(flags_offset, 0);
983 overflow.writeU64(id_offset, page_id);
984 overflow.writeU64(generation_offset, 0);
985 overflow.writeU32(overflow_next_offset, next_page);
986 overflow.writeU16(overflow_used_offset, @intCast(fragment.len));
987 overflow.writeU16(overflow_reserved_offset, 0);
988 @memcpy(overflow.bytes[header_size..][0..fragment.len], fragment);
989 return overflow;
990 }
991
992 pub fn load(bytes: *[size]u8) Error!Overflow {
993 const overflow = Overflow{ .bytes = bytes };
994 try overflow.validate();
995 return overflow;
996 }
997
998 pub fn id(self: *const Overflow) u64 {
999 return self.readU64(id_offset);
1000 }
1001
1002 pub fn next(self: *const Overflow) u32 {
1003 return self.readU32(overflow_next_offset);
1004 }
1005
1006 pub fn used(self: *const Overflow) usize {
1007 return self.readU16(overflow_used_offset);
1008 }
1009
1010 pub fn content(self: *const Overflow) []const u8 {
1011 return self.bytes[header_size..][0..self.used()];
1012 }
1013
1014 fn validate(self: *const Overflow) Error!void {
1015 if (!std.mem.eql(u8, self.bytes[magic_offset..][0..magic.len], magic[0..])) return error.InvalidPage;
1016 if (self.bytes[version_offset] != format_version) return error.InvalidPage;
1017 if (self.bytes[kind_offset] != overflow_kind) return error.InvalidPage;
1018 if (self.readU16(flags_offset) != 0) return error.InvalidPage;
1019 if (self.readU16(overflow_reserved_offset) != 0) return error.InvalidPage;
1020 if (self.used() == 0 or self.used() > overflow_capacity) return error.InvalidPage;
1021 if (self.next() != 0 and @as(u64, self.next()) == self.id()) return error.InvalidPage;
1022 }
1023
1024 fn readU16(self: *const Overflow, offset: usize) u16 {
1025 return std.mem.readInt(u16, self.bytes[offset..][0..2], .big);
1026 }
1027
1028 fn readU32(self: *const Overflow, offset: usize) u32 {
1029 return std.mem.readInt(u32, self.bytes[offset..][0..4], .big);
1030 }
1031
1032 fn readU64(self: *const Overflow, offset: usize) u64 {
1033 return std.mem.readInt(u64, self.bytes[offset..][0..8], .big);
1034 }
1035
1036 fn writeU16(self: *Overflow, offset: usize, value: u16) void {
1037 std.mem.writeInt(u16, self.bytes[offset..][0..2], value, .big);
1038 }
1039
1040 fn writeU32(self: *Overflow, offset: usize, value: u32) void {
1041 std.mem.writeInt(u32, self.bytes[offset..][0..4], value, .big);
1042 }
1043
1044 fn writeU64(self: *Overflow, offset: usize, value: u64) void {
1045 std.mem.writeInt(u64, self.bytes[offset..][0..8], value, .big);
1046 }
1047 };
1048
1049 pub const Range = struct {
1050 leaf: *const Leaf,
1051 end: ?[]const u8,
1052 index: usize,
1053
1054 pub fn next(self: *Range) ?Entry {
1055 const phase = trace.scope("page.range.next");
1056 defer phase.end();
1057 if (self.index >= self.leaf.cellCount()) return null;
1058 const entry = self.leaf.entryAt(self.index);
1059 if (self.end) |upper| {
1060 if (simd.order(Bytes, entry.key, upper) != .lt) return null;
1061 }
1062 self.index += 1;
1063 return entry;
1064 }
1065 };
1066
1067 fn checkLengths(key: []const u8, value: []const u8) Error!void {
1068 if (key.len > std.math.maxInt(u16)) return error.KeyTooLarge;
1069 if (value.len > std.math.maxInt(u16)) return error.ValueTooLarge;
1070 if (key.len + value.len > std.math.maxInt(u16)) return error.PageFull;
1071 }
1072
1073 /// The cell layout leaf and branch pages share. Slots grow up from the
1074 /// header in key order, cells grow down from the end of the page, and the
1075 /// free bytes between them read as zero.
1076 const Cells = struct {
1077 bytes: *[size]u8,
1078
1079 /// Writes a cell holding `key` and then `value` below the lowest cell
1080 /// and opens slot `index` for it, moving the slots from `index` up by
1081 /// one. A page without room for the cell and its slot stays unchanged.
1082 fn insert(self: Cells, index: usize, key: []const u8, value: []const u8) Error!void {
1083 try checkLengths(key, value);
1084 const count = self.read(cells_offset);
1085 const lower_bound = self.read(lower_offset);
1086 const upper_bound = self.read(upper_offset);
1087 std.debug.assert(index <= count);
1088 std.debug.assert(lower_bound == header_size + count * slot_size);
1089 if (upper_bound < lower_bound) return error.PageFull;
1090 const payload_len = key.len + value.len;
1091 if (payload_len + slot_size > upper_bound - lower_bound) return error.PageFull;
1092
1093 const cell = upper_bound - payload_len;
1094 @memcpy(self.bytes[cell..][0..key.len], key);
1095 @memcpy(self.bytes[cell + key.len ..][0..value.len], value);
1096 const slot = header_size + index * slot_size;
1097 if (index < count) {
1098 const moved_slots = self.bytes[slot..lower_bound];
1099 @memmove(self.bytes[slot + slot_size ..][0..moved_slots.len], moved_slots);
1100 }
1101 self.write(slot, cell);
1102 self.write(slot + 2, key.len);
1103 self.write(slot + 4, value.len);
1104 self.write(slot + 6, 0);
1105 self.write(cells_offset, count + 1);
1106 self.write(lower_offset, lower_bound + slot_size);
1107 self.write(upper_offset, cell);
1108 }
1109
1110 /// Removes slot `index` and its cell. The cells below it move up by its
1111 /// length and the later slots move down by one, so the free bytes stay
1112 /// one zeroed gap.
1113 fn remove(self: Cells, index: usize) void {
1114 const count = self.read(cells_offset);
1115 const lower_bound = self.read(lower_offset);
1116 const upper_bound = self.read(upper_offset);
1117 std.debug.assert(index < count);
1118 std.debug.assert(lower_bound == header_size + count * slot_size);
1119 const slot = header_size + index * slot_size;
1120 const cell = self.read(slot);
1121 const cell_len = self.read(slot + 2) + self.read(slot + 4);
1122 std.debug.assert(cell >= upper_bound);
1123 std.debug.assert(cell + cell_len <= size);
1124
1125 const moved_cells = self.bytes[upper_bound..cell];
1126 @memmove(self.bytes[upper_bound + cell_len ..][0..moved_cells.len], moved_cells);
1127 @memset(self.bytes[upper_bound..][0..cell_len], 0);
1128 const last_slot = lower_bound - slot_size;
1129 @memmove(self.bytes[slot..last_slot], self.bytes[slot + slot_size .. lower_bound]);
1130 @memset(self.bytes[last_slot..lower_bound], 0);
1131 var moved: usize = header_size;
1132 while (moved < last_slot) : (moved += slot_size) {
1133 const offset = self.read(moved);
1134 if (offset < cell) self.write(moved, offset + cell_len);
1135 }
1136 self.write(cells_offset, count - 1);
1137 self.write(lower_offset, last_slot);
1138 self.write(upper_offset, upper_bound + cell_len);
1139 }
1140
1141 fn read(self: Cells, offset: usize) usize {
1142 return std.mem.readInt(u16, self.bytes[offset..][0..2], .big);
1143 }
1144
1145 fn write(self: Cells, offset: usize, value: usize) void {
1146 std.mem.writeInt(u16, self.bytes[offset..][0..2], @intCast(value), .big);
1147 }
1148 };
1149
1150 fn appendSplitEntry(left: *Leaf, right: *Leaf, split_index: usize, ordinal: *usize, key: []const u8, value: []const u8) Error!void {
1151 if (ordinal.* < split_index) {
1152 try left.appendEntry(key, value);
1153 } else {
1154 try right.appendEntry(key, value);
1155 }
1156 ordinal.* += 1;
1157 }
1158
1159 /// Returns the page bytes a cell with a key and value of these lengths takes.
1160 pub fn cellBytes(key_len: usize, value_len: usize) usize {
1161 return key_len + value_len + slot_size;
1162 }
1163
1164 fn storedCellBytes(source: anytype, index: usize) usize {
1165 const slot = source.slotAt(index);
1166 return cellBytes(slot.key_len, slot.value_len);
1167 }
1168
1169 /// Returns the split point that balances bytes between the halves of a leaf
1170 /// or branch merged with one put of `key`. A cell with that key is replaced.
1171 fn splitIndexFor(source: anytype, key: []const u8, value_len: usize, total: usize) Error!usize {
1172 const put_bytes = cellBytes(key.len, value_len);
1173 var search = SplitSearch{
1174 .total = total,
1175 .total_bytes = mergedBytes(source, key, put_bytes),
1176 };
1177 var inserted = false;
1178 var index: usize = 0;
1179 while (index < source.cellCount()) : (index += 1) {
1180 switch (simd.order(Bytes, source.keyAt(index), key)) {
1181 .lt => search.add(storedCellBytes(source, index)),
1182 .eq => {
1183 if (!inserted) {
1184 search.add(put_bytes);
1185 inserted = true;
1186 }
1187 },
1188 .gt => {
1189 if (!inserted) {
1190 search.add(put_bytes);
1191 inserted = true;
1192 }
1193 search.add(storedCellBytes(source, index));
1194 },
1195 }
1196 }
1197 if (!inserted) search.add(put_bytes);
1198 if (search.best_index == 0) return error.PageFull;
1199 return search.best_index;
1200 }
1201
1202 fn mergedBytes(source: anytype, key: []const u8, put_bytes: usize) usize {
1203 var bytes = put_bytes;
1204 var index: usize = 0;
1205 while (index < source.cellCount()) : (index += 1) {
1206 if (!std.mem.eql(u8, source.keyAt(index), key)) bytes += storedCellBytes(source, index);
1207 }
1208 return bytes;
1209 }
1210
1211 /// Walks the cells of a split in key order and keeps the split point whose
1212 /// larger half is smallest among the points where both halves fit a page.
1213 const SplitSearch = struct {
1214 total: usize,
1215 total_bytes: usize,
1216 ordinal: usize = 0,
1217 left_bytes: usize = 0,
1218 best_index: usize = 0,
1219 best_score: usize = std.math.maxInt(usize),
1220
1221 fn add(search: *SplitSearch, bytes: usize) void {
1222 search.ordinal += 1;
1223 search.left_bytes += bytes;
1224 if (search.ordinal >= search.total) return;
1225 const right_bytes = search.total_bytes - search.left_bytes;
1226 const capacity = size - header_size;
1227 if (search.left_bytes > capacity or right_bytes > capacity) return;
1228 const score = @max(search.left_bytes, right_bytes);
1229 if (score < search.best_score) {
1230 search.best_score = score;
1231 search.best_index = search.ordinal;
1232 }
1233 }
1234 };
1235
1236 fn appendSplitBranchEntry(left: *Branch, right: *Branch, split_index: usize, ordinal: *usize, lower_key: []const u8, child: u32) Error!void {
1237 if (ordinal.* < split_index) {
1238 try left.appendEntry(lower_key, child);
1239 } else {
1240 try right.appendEntry(lower_key, child);
1241 }
1242 ordinal.* += 1;
1243 }
1244
1245 fn childBytes(child: u32) [child_size]u8 {
1246 var bytes: [child_size]u8 = undefined;
1247 std.mem.writeInt(u32, &bytes, child, .big);
1248 return bytes;
1249 }
1250
1251 test "leaf page initializes a stable header" {
1252 var bytes: [size]u8 = undefined;
1253 const leaf = Leaf.init(&bytes, 42);
1254
1255 try std.testing.expectEqualStrings("tsql", bytes[0..4]);
1256 try std.testing.expectEqual(@as(u8, 1), bytes[version_offset]);
1257 try std.testing.expectEqual(@as(u8, leaf_kind), bytes[kind_offset]);
1258 try std.testing.expectEqual(@as(u64, 42), leaf.id());
1259 try std.testing.expectEqual(@as(u64, 0), leaf.generation());
1260 try std.testing.expectEqual(@as(usize, 0), leaf.cellCount());
1261 try std.testing.expectEqual(@as(usize, size - header_size), leaf.freeBytes());
1262 _ = try Leaf.load(&bytes);
1263 }
1264
1265 test "leaf page stores byte keys in sorted order" {
1266 var bytes: [size]u8 = undefined;
1267 var leaf = Leaf.init(&bytes, 7);
1268
1269 try leaf.put("c", "three");
1270 try leaf.put("a", "one");
1271 try leaf.put("b", "two");
1272
1273 try std.testing.expectEqual(@as(usize, 3), leaf.cellCount());
1274 try std.testing.expectEqualStrings("one", leaf.get("a").?);
1275 try std.testing.expectEqualStrings("two", leaf.get("b").?);
1276 try std.testing.expectEqualStrings("three", leaf.get("c").?);
1277 try std.testing.expect(leaf.get("d") == null);
1278
1279 const loaded = try Leaf.load(&bytes);
1280 var range = try loaded.range(null, null);
1281 const first = range.next().?;
1282 const second = range.next().?;
1283 const third = range.next().?;
1284 try std.testing.expectEqualStrings("a", first.key);
1285 try std.testing.expectEqualStrings("b", second.key);
1286 try std.testing.expectEqualStrings("c", third.key);
1287 try std.testing.expect(range.next() == null);
1288 }
1289
1290 test "leaf page replacement and deletion compact payload bytes" {
1291 var bytes: [size]u8 = undefined;
1292 var leaf = Leaf.init(&bytes, 9);
1293
1294 try leaf.put("k", "v1");
1295 const used_after_insert = leaf.usedBytes();
1296 try leaf.put("k", "replacement");
1297 try std.testing.expectEqualStrings("replacement", leaf.get("k").?);
1298 try std.testing.expect(leaf.usedBytes() > used_after_insert);
1299 try std.testing.expectEqual(@as(u64, 2), leaf.generation());
1300
1301 try leaf.delete("k");
1302 try std.testing.expectEqual(@as(usize, 0), leaf.cellCount());
1303 try std.testing.expectEqual(@as(usize, size - header_size), leaf.freeBytes());
1304 try std.testing.expect(leaf.get("k") == null);
1305 try std.testing.expectEqual(@as(u64, 3), leaf.generation());
1306 }
1307
1308 test "leaf page same size replacement updates cell in place" {
1309 var bytes: [size]u8 = undefined;
1310 var leaf = Leaf.init(&bytes, 10);
1311
1312 try leaf.put("k", "v1");
1313 const used_after_insert = leaf.usedBytes();
1314 const slot_after_insert = leaf.slotAt(0);
1315 try leaf.put("k", "v2");
1316
1317 try std.testing.expectEqualStrings("v2", leaf.get("k").?);
1318 try std.testing.expectEqual(@as(u64, 2), leaf.generation());
1319 try std.testing.expectEqual(used_after_insert, leaf.usedBytes());
1320 try std.testing.expectEqual(slot_after_insert.offset, leaf.slotAt(0).offset);
1321 try std.testing.expectEqual(slot_after_insert.key_len, leaf.slotAt(0).key_len);
1322 try std.testing.expectEqual(slot_after_insert.value_len, leaf.slotAt(0).value_len);
1323 _ = try Leaf.load(&bytes);
1324 }
1325
1326 test "leaf page range scans honor half open bounds" {
1327 var bytes: [size]u8 = undefined;
1328 var leaf = Leaf.init(&bytes, 11);
1329
1330 try leaf.put("a", "1");
1331 try leaf.put("b", "2");
1332 try leaf.put("c", "3");
1333 try leaf.put("d", "4");
1334
1335 var range = try leaf.range("b", "d");
1336 const first = range.next().?;
1337 const second = range.next().?;
1338 try std.testing.expectEqualStrings("b", first.key);
1339 try std.testing.expectEqualStrings("c", second.key);
1340 try std.testing.expect(range.next() == null);
1341 try std.testing.expectError(error.InvalidRange, leaf.range("d", "b"));
1342 }
1343
1344 test "leaf page failed writes leave existing bytes intact" {
1345 var bytes: [size]u8 = undefined;
1346 var leaf = Leaf.init(&bytes, 13);
1347
1348 try leaf.put("a", "1");
1349 const before = bytes;
1350 var large_value: [size]u8 = undefined;
1351 @memset(&large_value, 'x');
1352
1353 try std.testing.expectError(error.PageFull, leaf.put("b", &large_value));
1354 try std.testing.expectEqualSlices(u8, before[0..], bytes[0..]);
1355 try std.testing.expectEqualStrings("1", leaf.get("a").?);
1356 }
1357
1358 test "leaf page inserts between cells without moving them" {
1359 var bytes: [size]u8 = undefined;
1360 var leaf = Leaf.init(&bytes, 14);
1361
1362 try leaf.put("a", "one");
1363 try leaf.put("c", "three");
1364 const first = leaf.slotAt(0);
1365 const last = leaf.slotAt(1);
1366 try leaf.put("b", "two");
1367
1368 try std.testing.expectEqual(@as(usize, 3), leaf.cellCount());
1369 try std.testing.expectEqual(first, leaf.slotAt(0));
1370 try std.testing.expectEqual(last, leaf.slotAt(2));
1371 try std.testing.expectEqualStrings("two", leaf.get("b").?);
1372 try std.testing.expectEqual(@as(u64, 3), leaf.generation());
1373 try expectCompactCells(&bytes);
1374 _ = try Leaf.load(&bytes);
1375 }
1376
1377 test "leaf page deletion closes the gap and zeroes the freed bytes" {
1378 var bytes: [size]u8 = undefined;
1379 var leaf = Leaf.init(&bytes, 15);
1380
1381 try leaf.put("a", "one");
1382 try leaf.put("b", "two");
1383 try leaf.put("c", "three");
1384 try leaf.put("d", "four");
1385 try leaf.delete("b");
1386 try std.testing.expectError(error.KeyNotFound, leaf.delete("b"));
1387
1388 var fresh_bytes: [size]u8 = undefined;
1389 var fresh = Leaf.init(&fresh_bytes, 15);
1390 try fresh.put("a", "one");
1391 try fresh.put("c", "three");
1392 try fresh.put("d", "four");
1393 try std.testing.expectEqual(fresh.freeBytes(), leaf.freeBytes());
1394 try std.testing.expect(leaf.get("b") == null);
1395 try std.testing.expectEqualStrings("one", leaf.get("a").?);
1396 try std.testing.expectEqualStrings("three", leaf.get("c").?);
1397 try std.testing.expectEqualStrings("four", leaf.get("d").?);
1398 try std.testing.expectEqual(@as(u64, 5), leaf.generation());
1399 try expectCompactCells(&bytes);
1400 _ = try Leaf.load(&bytes);
1401 }
1402
1403 test "leaf page insert into a full page leaves it unchanged" {
1404 var bytes: [size]u8 = undefined;
1405 var leaf = Leaf.init(&bytes, 16);
1406 const value: [200]u8 = @splat('v');
1407 var key = [_]u8{ 'k', 0 };
1408 while (true) : (key[1] += 2) {
1409 leaf.put(&key, &value) catch |err| switch (err) {
1410 error.PageFull => break,
1411 else => return err,
1412 };
1413 }
1414 const before = bytes;
1415 key[1] = 1;
1416 try std.testing.expectError(error.PageFull, leaf.put(&key, &value));
1417 try std.testing.expectEqualSlices(u8, before[0..], bytes[0..]);
1418 }
1419
1420 test "leaf page split balances uneven value sizes" {
1421 var bytes: [size]u8 = undefined;
1422 var leaf = Leaf.init(&bytes, 14);
1423 var large: [430]u8 = undefined;
1424 @memset(&large, 'x');
1425
1426 for (0..9) |index| {
1427 const key_bytes = [_]u8{ 'a', @intCast('0' + index / 10), @intCast('0' + index % 10) };
1428 try leaf.put(key_bytes[0..], "s");
1429 }
1430 for (0..8) |index| {
1431 const key_bytes = [_]u8{ 'z', @intCast('0' + index / 10), @intCast('0' + index % 10) };
1432 try leaf.put(key_bytes[0..], large[0..]);
1433 }
1434
1435 var left_bytes: [size]u8 = undefined;
1436 var right_bytes: [size]u8 = undefined;
1437 var left = Leaf.init(&left_bytes, 15);
1438 var right = Leaf.init(&right_bytes, 16);
1439 const new_key = [_]u8{ 'z', '0', '8' };
1440 const separator = try leaf.splitPut(&left, &right, new_key[0..], large[0..]);
1441
1442 _ = try Leaf.load(&left_bytes);
1443 _ = try Leaf.load(&right_bytes);
1444 try std.testing.expect(left.cellCount() > 0);
1445 try std.testing.expect(right.cellCount() > 0);
1446 try std.testing.expect(right.get(new_key[0..]) != null);
1447 try std.testing.expectEqualStrings(right.firstKey().?, separator);
1448 }
1449
1450 test "branch page stores lower bounds and routes children" {
1451 var bytes: [size]u8 = undefined;
1452 var branch = Branch.init(&bytes, 21);
1453
1454 try std.testing.expectEqual(Kind.branch, try kind(&bytes));
1455 try std.testing.expectError(error.InvalidPage, Branch.load(&bytes));
1456
1457 try branch.put("m", 3);
1458 try branch.put(&.{}, 2);
1459 try branch.put("t", 4);
1460
1461 const loaded = try Branch.load(&bytes);
1462 try std.testing.expectEqual(@as(u64, 21), loaded.id());
1463 try std.testing.expectEqual(@as(u64, 3), loaded.generation());
1464 try std.testing.expectEqual(@as(usize, 3), loaded.cellCount());
1465 try std.testing.expectEqualStrings("", loaded.lowerAt(0));
1466 try std.testing.expectEqualStrings("m", loaded.lowerAt(1));
1467 try std.testing.expectEqualStrings("t", loaded.lowerAt(2));
1468 try std.testing.expectEqual(@as(u32, 2), loaded.childFor("a"));
1469 try std.testing.expectEqual(@as(u32, 3), loaded.childFor("m"));
1470 try std.testing.expectEqual(@as(u32, 3), loaded.childFor("s"));
1471 try std.testing.expectEqual(@as(u32, 4), loaded.childFor("t"));
1472 try std.testing.expectEqual(@as(u32, 4), loaded.childFor("z"));
1473 }
1474
1475 test "branch page replacement preserves lower bound order" {
1476 var bytes: [size]u8 = undefined;
1477 var branch = Branch.init(&bytes, 22);
1478
1479 try branch.put(&.{}, 2);
1480 try branch.put("m", 3);
1481 try branch.put("t", 4);
1482 try branch.put("m", 5);
1483
1484 const loaded = try Branch.load(&bytes);
1485 try std.testing.expectEqual(@as(u64, 4), loaded.generation());
1486 try std.testing.expectEqual(@as(usize, 3), loaded.cellCount());
1487 try std.testing.expectEqual(@as(u32, 2), loaded.childAt(0));
1488 try std.testing.expectEqual(@as(u32, 5), loaded.childAt(1));
1489 try std.testing.expectEqual(@as(u32, 4), loaded.childAt(2));
1490 try std.testing.expectEqual(@as(u32, 5), loaded.childFor("q"));
1491 }
1492
1493 test "branch page rejects zero child identifiers" {
1494 var bytes: [size]u8 = undefined;
1495 var branch = Branch.init(&bytes, 23);
1496
1497 try std.testing.expectError(error.InvalidPage, branch.put(&.{}, 0));
1498 try std.testing.expectError(error.InvalidPage, Branch.load(&bytes));
1499 }
1500
1501 test "branch page split returns the first lower bound of the right page" {
1502 var bytes: [size]u8 = undefined;
1503 var branch = Branch.init(&bytes, 24);
1504
1505 try branch.put(&.{}, 2);
1506 try branch.put("c", 3);
1507 try branch.put("f", 4);
1508 try branch.put("j", 5);
1509 try branch.put("n", 6);
1510
1511 var left_bytes: [size]u8 = undefined;
1512 var right_bytes: [size]u8 = undefined;
1513 var left = Branch.init(&left_bytes, 25);
1514 var right = Branch.init(&right_bytes, 26);
1515 const separator = try branch.splitPut(&left, &right, "h", 7);
1516
1517 try std.testing.expectEqualStrings("h", separator);
1518 const loaded_left = try Branch.load(&left_bytes);
1519 const loaded_right = try Branch.load(&right_bytes);
1520 try std.testing.expectEqualStrings("", loaded_left.lowerAt(0));
1521 try std.testing.expectEqualStrings("h", loaded_right.lowerAt(0));
1522 try std.testing.expectEqual(@as(u32, 4), loaded_left.childFor("g"));
1523 try std.testing.expectEqual(@as(u32, 7), loaded_right.childFor("h"));
1524 try std.testing.expectEqual(@as(u32, 6), loaded_right.childFor("z"));
1525 }
1526
1527 test "branch page split balances uneven lower bound sizes" {
1528 var bytes: [size]u8 = undefined;
1529 var branch = Branch.init(&bytes, 28);
1530 try branch.put(&.{}, 2);
1531 for (0..12) |index| {
1532 const short = [_]u8{ 'a', @intCast('0' + index / 10), @intCast('0' + index % 10) };
1533 try branch.put(short[0..], @intCast(3 + index));
1534 }
1535 var long: [279]u8 = @splat('x');
1536 long[0] = 'z';
1537 for (0..13) |index| {
1538 long[1] = @intCast('0' + index / 10);
1539 long[2] = @intCast('0' + index % 10);
1540 try branch.put(long[0..], @intCast(20 + index));
1541 }
1542 long[1] = '1';
1543 long[2] = '3';
1544 try std.testing.expectError(error.PageFull, branch.put(long[0..], 40));
1545
1546 var left_bytes: [size]u8 = undefined;
1547 var right_bytes: [size]u8 = undefined;
1548 var left = Branch.init(&left_bytes, 29);
1549 var right = Branch.init(&right_bytes, 30);
1550 const separator = try branch.splitPut(&left, &right, long[0..], 40);
1551
1552 const loaded_left = try Branch.load(&left_bytes);
1553 const loaded_right = try Branch.load(&right_bytes);
1554 try std.testing.expect(loaded_left.cellCount() > 13);
1555 try std.testing.expectEqual(@as(usize, 27), loaded_left.cellCount() + loaded_right.cellCount());
1556 try std.testing.expectEqualStrings(loaded_right.firstLower().?, separator);
1557 try std.testing.expectEqual(@as(u32, 40), loaded_right.childFor(long[0..]));
1558 }
1559
1560 test "branch page replaces and removes child entries by index" {
1561 var bytes: [size]u8 = undefined;
1562 var branch = Branch.init(&bytes, 27);
1563
1564 try branch.put(&.{}, 2);
1565 try branch.put("m", 3);
1566 try branch.put("t", 4);
1567 try branch.replace(1, "n", 5);
1568
1569 var loaded = try Branch.load(&bytes);
1570 try std.testing.expectEqual(@as(usize, 3), loaded.cellCount());
1571 try std.testing.expectEqualStrings("n", loaded.lowerAt(1));
1572 try std.testing.expectEqual(@as(u32, 5), loaded.childFor("s"));
1573
1574 try branch.remove(0);
1575 loaded = try Branch.load(&bytes);
1576 try std.testing.expectEqual(@as(usize, 2), loaded.cellCount());
1577 try std.testing.expectEqualStrings("n", loaded.lowerAt(0));
1578 try std.testing.expectEqual(@as(u32, 5), loaded.childFor("a"));
1579 }
1580
1581 test "branch page inserts replaces children and removes cells in place" {
1582 var bytes: [size]u8 = undefined;
1583 var branch = Branch.init(&bytes, 28);
1584
1585 try branch.put(&.{}, 2);
1586 try branch.put("t", 4);
1587 const last = branch.slotAt(1);
1588 try branch.put("m", 3);
1589 try std.testing.expectEqual(last, branch.slotAt(2));
1590 try std.testing.expectEqual(@as(u32, 3), branch.childFor("p"));
1591
1592 try branch.put("m", 5);
1593 try std.testing.expectEqual(@as(usize, 3), branch.cellCount());
1594 try std.testing.expectEqual(@as(u32, 5), branch.childFor("p"));
1595
1596 try branch.remove(1);
1597 try std.testing.expectEqual(@as(usize, 2), branch.cellCount());
1598 try std.testing.expectEqual(@as(u32, 2), branch.childFor("p"));
1599 try std.testing.expectEqual(@as(u32, 4), branch.childFor("u"));
1600 try std.testing.expectEqual(@as(u64, 5), branch.generation());
1601 try expectCompactCells(&bytes);
1602 _ = try Branch.load(&bytes);
1603 }
1604
1605 /// Checks that the cells of a leaf or branch image fill the end of the
1606 /// page without gaps and that its free bytes read as zero.
1607 fn expectCompactCells(bytes: *[size]u8) !void {
1608 const cells = Cells{ .bytes = bytes };
1609 const count = cells.read(cells_offset);
1610 const lower_bound = cells.read(lower_offset);
1611 const upper_bound = cells.read(upper_offset);
1612 var payload: usize = 0;
1613 var index: usize = 0;
1614 while (index < count) : (index += 1) {
1615 const slot = header_size + index * slot_size;
1616 payload += cells.read(slot + 2) + cells.read(slot + 4);
1617 }
1618 try std.testing.expectEqual(size - upper_bound, payload);
1619 try std.testing.expect(std.mem.allEqual(u8, bytes[lower_bound..upper_bound], 0));
1620 }
1621
1622 test "pages copy entries into a new page identity" {
1623 var leaf_bytes: [size]u8 = undefined;
1624 var copied_leaf_bytes: [size]u8 = undefined;
1625 var leaf = Leaf.init(&leaf_bytes, 31);
1626 try leaf.put("a", "1");
1627 try leaf.put("b", "2");
1628 var copied_leaf = Leaf.init(&copied_leaf_bytes, 32);
1629 try leaf.copyTo(&copied_leaf);
1630 const loaded_leaf = try Leaf.load(&copied_leaf_bytes);
1631 try std.testing.expectEqual(@as(u64, 32), loaded_leaf.id());
1632 try std.testing.expectEqualStrings("1", loaded_leaf.get("a").?);
1633 try std.testing.expectEqualStrings("2", loaded_leaf.get("b").?);
1634
1635 var branch_bytes: [size]u8 = undefined;
1636 var copied_branch_bytes: [size]u8 = undefined;
1637 var branch = Branch.init(&branch_bytes, 33);
1638 try branch.put(&.{}, 2);
1639 try branch.put("m", 3);
1640 var copied_branch = Branch.init(&copied_branch_bytes, 34);
1641 try branch.copyTo(&copied_branch);
1642 const loaded_branch = try Branch.load(&copied_branch_bytes);
1643 try std.testing.expectEqual(@as(u64, 34), loaded_branch.id());
1644 try std.testing.expectEqual(@as(u32, 2), loaded_branch.childFor("a"));
1645 try std.testing.expectEqual(@as(u32, 3), loaded_branch.childFor("z"));
1646 }
1647
1648 test "meta page allocates appends and reuses released pages" {
1649 var bytes: [size]u8 = undefined;
1650 var meta = Meta.init(&bytes, 1, 4);
1651
1652 try std.testing.expectEqual(Kind.meta, try kind(&bytes));
1653 try std.testing.expectEqual(@as(u64, 1), meta.id());
1654 try std.testing.expectEqual(@as(u32, 4), meta.highestPage());
1655 try std.testing.expectEqual(@as(usize, 0), meta.freeCount());
1656
1657 try std.testing.expectEqual(@as(u32, 5), try meta.allocate());
1658 try std.testing.expectEqual(@as(u32, 5), meta.highestPage());
1659 try std.testing.expectEqual(@as(u64, 1), meta.generation());
1660
1661 try meta.release(3);
1662 try meta.release(4);
1663 try std.testing.expectEqual(@as(usize, 2), meta.freeCount());
1664 try std.testing.expectEqual(@as(u32, 4), try meta.allocate());
1665 try std.testing.expectEqual(@as(u32, 3), try meta.allocate());
1666 try std.testing.expectEqual(@as(u32, 6), try meta.allocate());
1667
1668 const loaded = try Meta.load(&bytes);
1669 try std.testing.expectEqual(@as(u32, 6), loaded.highestPage());
1670 try std.testing.expectEqual(@as(usize, 0), loaded.freeCount());
1671 }
1672
1673 test "meta page truncates descending high-page releases" {
1674 var bytes: [size]u8 = undefined;
1675 var meta = Meta.init(&bytes, 1, 6000);
1676
1677 var page_id: u32 = 6000;
1678 while (page_id >= 2000) : (page_id -= 1) try meta.release(page_id);
1679
1680 try std.testing.expectEqual(@as(u32, 1999), meta.highestPage());
1681 try std.testing.expectEqual(@as(usize, 0), meta.freeCount());
1682 try std.testing.expectEqual(@as(u32, 2000), try meta.allocate());
1683 }
1684
1685 test "meta reserves explicit root pages before allocation" {
1686 var bytes: [size]u8 = undefined;
1687 var meta = Meta.init(&bytes, 1, 2);
1688 try std.testing.expect(try meta.reserveThrough(4));
1689 try std.testing.expectEqual(@as(u32, 4), meta.highestPage());
1690 try std.testing.expect(!(try meta.reserveThrough(3)));
1691 try std.testing.expectEqual(@as(u32, 5), try meta.allocate());
1692 }
1693
1694 test "meta page rejects invalid free-list entries" {
1695 var bytes: [size]u8 = undefined;
1696 var meta = Meta.init(&bytes, 1, 3);
1697
1698 try std.testing.expectError(error.InvalidPageId, meta.release(0));
1699 try std.testing.expectError(error.InvalidPageId, meta.release(1));
1700 try std.testing.expectError(error.InvalidPageId, meta.release(4));
1701
1702 try meta.release(2);
1703 try std.testing.expectError(error.InvalidPage, meta.release(2));
1704 _ = try Meta.load(&bytes);
1705 }
1706
1707 test "meta page spills and refills a chained free list" {
1708 var bytes: [size]u8 = undefined;
1709 var meta = Meta.init(&bytes, 1, 100_000);
1710
1711 const inline_capacity = meta.freeCapacity();
1712 var page_id: u32 = 2;
1713 while (meta.freeCount() < inline_capacity) : (page_id += 2) try meta.release(page_id);
1714 try std.testing.expectError(error.FreeListFull, meta.release(page_id));
1715
1716 const chain_page = try meta.allocate();
1717 var spilled: [meta_chain_page_entries + 1]u32 = undefined;
1718 const count = try meta.spillEntries(&spilled);
1719 try std.testing.expectEqual(inline_capacity - 1, count);
1720 try std.testing.expectEqual(@as(usize, 0), meta.freeCount());
1721
1722 try meta.adoptChain(chain_page);
1723 try std.testing.expect(meta.isChained());
1724 try std.testing.expectEqual(chain_page, meta.chainHead());
1725 try std.testing.expectEqual(meta_chain_page_entries, meta.freeCapacity());
1726 _ = try Meta.load(&bytes);
1727
1728 try meta.release(page_id);
1729 try std.testing.expectEqual(@as(usize, 1), meta.freeCount());
1730 try std.testing.expectEqual(page_id, try meta.allocate());
1731
1732 try meta.refillFromChain(0, spilled[0..count]);
1733 try std.testing.expect(!meta.isChained());
1734 try std.testing.expectEqual(@as(u32, 0), meta.chainHead());
1735 try std.testing.expectEqual(count, meta.freeCount());
1736 try std.testing.expectEqual(spilled[count - 1], try meta.allocate());
1737 const loaded = try Meta.load(&bytes);
1738 try std.testing.expectEqual(count - 1, loaded.freeCount());
1739 }
1740
1741 test "meta page rejects malformed chain transitions" {
1742 var bytes: [size]u8 = undefined;
1743 var meta = Meta.init(&bytes, 1, 50);
1744
1745 var buffer: [4]u32 = undefined;
1746 try std.testing.expectError(error.InvalidPage, meta.spillEntries(&buffer));
1747 try std.testing.expectError(error.InvalidPageId, meta.adoptChain(0));
1748 try std.testing.expectError(error.InvalidPageId, meta.adoptChain(1));
1749 try std.testing.expectError(error.InvalidPageId, meta.adoptChain(51));
1750 try std.testing.expectError(error.InvalidPage, meta.refillFromChain(0, &.{2}));
1751
1752 try meta.release(2);
1753 try std.testing.expectError(error.InvalidPage, meta.adoptChain(3));
1754 _ = try meta.allocate();
1755 try meta.adoptChain(3);
1756 try std.testing.expectError(error.InvalidPage, meta.refillFromChain(0, &.{0}));
1757 try std.testing.expectError(error.InvalidPage, meta.refillFromChain(0, &.{1}));
1758 try std.testing.expectError(error.InvalidPage, meta.refillFromChain(0, &.{51}));
1759 try std.testing.expectError(error.InvalidPageId, meta.refillFromChain(1, &.{4}));
1760 try std.testing.expectError(error.InvalidPageId, meta.refillFromChain(51, &.{4}));
1761
1762 try meta.refillFromChain(5, &.{4});
1763 try std.testing.expect(meta.isChained());
1764 try std.testing.expectEqual(@as(u32, 5), meta.chainHead());
1765 try std.testing.expectEqual(@as(usize, 1), meta.freeCount());
1766 _ = try Meta.load(&bytes);
1767 }
1768
1769 test "overflow page stores a linked content fragment" {
1770 var bytes: [size]u8 = undefined;
1771 const overflow = try Overflow.init(&bytes, 40, 41, "fragment");
1772
1773 try std.testing.expectEqual(Kind.overflow, try kind(&bytes));
1774 try std.testing.expectEqual(@as(u64, 40), overflow.id());
1775 try std.testing.expectEqual(@as(u32, 41), overflow.next());
1776 try std.testing.expectEqualStrings("fragment", overflow.content());
1777
1778 const loaded = try Overflow.load(&bytes);
1779 try std.testing.expectEqual(@as(u32, 41), loaded.next());
1780 try std.testing.expectEqualStrings("fragment", loaded.content());
1781 }
1782
1783 test "overflow page rejects empty oversized and self-linked fragments" {
1784 var bytes: [size]u8 = undefined;
1785 var oversized: [overflow_capacity + 1]u8 = undefined;
1786 @memset(&oversized, 'x');
1787
1788 try std.testing.expectError(error.ValueTooLarge, Overflow.init(&bytes, 50, 0, &.{}));
1789 try std.testing.expectError(error.ValueTooLarge, Overflow.init(&bytes, 50, 0, &oversized));
1790 try std.testing.expectError(error.InvalidPageId, Overflow.init(&bytes, 50, 50, "fragment"));
1791 }