holt 0.1.0

An adaptive-radix-tree metadata storage engine for path-shaped keys, with per-blob concurrency and crash-safe persistence.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

//! Recursive ART walker — descent / insert / erase / spillover /
//! migrate. Split into focused submodules (all `pub(super)` —
//! internal to the walker, re-exported as the public surface from
//! this `mod.rs`):
//!
//! - `types` — public outcomes ([`LookupResult`], [`InsertOutcome`],
//!   …) + internal signals (`EraseSignal`, `Victim`, …).
//! - `readers` — decode slot bodies + leaf extents off a
//!   `BlobFrameRef`.
//! - `writers` — allocate fresh slots / extents and populate them.
//! - `lookup` — [`lookup`] / [`lookup_at`] / [`lookup_multi`] and
//!   single-blob descent arms. Zero-copy: walks against
//!   `BlobFrameRef` so it's safe to run under a `BufferManager`
//!   shared read-guard.
//! - `insert` — [`insert`] / [`insert_multi`] + `insert_at`
//!   dispatch + `insert_at_blob_node` cross-blob arm.
//! - `erase` — [`erase`] / [`erase_multi`] + `erase_at` dispatch +
//!   `erase_at_blob_node` cross-blob arm + lone-child collapse
//!   rewiring.
//! - `spillover` — when a blob fills, pick a victim subtree,
//!   migrate it via [`make_blob_from_node`], free the source slots,
//!   install a `BlobNode` placeholder.
//! - `migrate` — deep-clone primitives: [`make_blob_from_node`]
//!   (spillover) + [`compact_blob`] (in-place repack). Share the
//!   internal `clone_subtree` machinery.
//! - `scan` — tree-wide BFS over reachable blobs ([`collect_blob_guids`]).
//!   Used by [`crate::Tree::stats`] and [`crate::Tree::compact`] to
//!   fan out across the whole on-disk tree.
//! - `merge` — tree-wide single-pass walker ([`try_merge_children`])
//!   that folds every mergeable `BlobNode` child back into its
//!   parent via [`merge_blob`]. Wired into [`crate::Tree::compact`]
//!   after the per-blob compaction pass.

use std::mem::size_of;

mod erase;
mod insert;
mod lookup;
mod merge;
mod migrate;
mod range;
mod readers;
mod scan;
mod spillover;
#[cfg(test)]
mod tests;
mod types;
mod writers;

// ---------- public API ----------

pub use erase::{erase, erase_multi};
pub use insert::{insert, insert_multi};
pub use lookup::{lookup, lookup_at, lookup_multi};
pub use merge::{try_merge_children, MergeStats};
pub use migrate::{compact_blob, is_mergeable, make_blob_from_node, merge_blob};
pub use range::{RangeBuilder, RangeEntry, RangeIter};
pub use scan::{collect_blob_guids, refresh_blob_node_pointers};
pub use types::{
    BlobNodeCrossing, CompactStats, EraseOutcome, InsertOutcome, LookupResult, MakeBlobOutcome,
};

// ---------- shared internals ----------

/// Cap on the spillover-retry loop inside `insert_multi` /
/// `insert_at_blob_node`. Each spillover migrates the largest non-
/// Blob subtree out of the current blob.
///
/// With the current heuristic (pick-largest, skip BlobNodes, cross-
/// type Prefix↔Blob free-list fallback) one spillover frees roughly
/// `(largest-child-subtree-size)` worth of slot entries.
///
/// 64 covers a 2-3× workload-vs-blob-capacity ratio for the
/// uniform-key regimes the benchmark + integration tests exercise.
pub(super) const MAX_SPILLOVER_ATTEMPTS: u32 = 64;

/// Reinterpret a slot body as a `#[repr(C)]` layout struct.
///
/// SAFETY: layout types are POD; body length + alignment are
/// guaranteed by `BlobFrame`'s invariants.
pub(super) fn cast<T>(body: &[u8]) -> &T {
    debug_assert_eq!(body.len(), size_of::<T>());
    debug_assert_eq!(body.as_ptr() as usize % std::mem::align_of::<T>(), 0);
    unsafe { &*body.as_ptr().cast::<T>() }
}