fsqlite_btree/
lib.rs

1#![allow(internal_features)]
2#![feature(core_intrinsics)]
3
4use std::cmp::Ordering;
5
6pub mod balance;
7pub mod be_tree;
8pub mod cell;
9pub mod cooling;
10pub mod cracking;
11pub mod cursor;
12pub mod delta_chain;
13pub mod freelist;
14pub mod instrumentation;
15pub mod learned_index;
16pub mod learned_rowid;
17pub mod overflow;
18pub mod payload;
19pub mod quotient_filter;
20pub mod swiss_index;
21pub mod swizzle;
22pub mod traits;
23
24#[cfg(test)]
25mod btree_invariant_tests;
26
27#[cfg(test)]
28mod quotient_filter_bench;
29
30pub use be_tree::{
31    BeTree, BeTreeConfig, BeTreeMetricsSnapshot, betree_metrics_snapshot, reset_betree_metrics,
32};
33pub use cell::{
34    BtreePageHeader, BtreePageType, CellRef, has_overflow, header_offset_for_page,
35    local_payload_size, max_local_payload, min_local_payload, read_cell_pointers,
36    read_cell_pointers_into, write_cell_pointers,
37};
38pub use cooling::{
39    CoolingConfig, CoolingMetricsSnapshot, CoolingStateMachine, cooling_metrics_snapshot,
40    reset_cooling_metrics,
41};
42pub use cracking::{
43    CrackedColumn, CrackingMetricsSnapshot, cracking_metrics_snapshot, reset_cracking_metrics,
44};
45pub use cursor::{
46    BtCursor, CursorPositionStamp, MemPageStore, PageReader, PageWriter, TableAppendHint,
47    TransactionPageIo,
48};
49pub use instrumentation::{
50    BtreeCopyProfileSnapshot, BtreeLeafReuseSnapshot, BtreeMetricsSnapshot, BtreeOpType,
51    BtreeOperationTotals, ConflictTopologyPolicyMode, ConflictTopologySplitAdvice,
52    HotPageDeflectionStatus, btree_copy_profile_snapshot, btree_leaf_reuse_snapshot,
53    btree_metrics_enabled, btree_metrics_snapshot, conflict_topology_policy_enabled,
54    conflict_topology_policy_mode, conflict_topology_split_advice, record_conflict_topology_heat,
55    record_conflict_topology_heat_batch, reset_btree_copy_profile, reset_btree_leaf_reuse_profile,
56    reset_btree_metrics, reset_conflict_topology_policy_state, set_btree_copy_profile_enabled,
57    set_btree_metrics_enabled, set_conflict_topology_policy_mode,
58};
59pub use learned_index::{
60    LearnedIndex, LearnedIndexConfig, LearnedIndexMetricsSnapshot, learned_index_metrics_snapshot,
61    reset_learned_index_metrics,
62};
63pub use learned_rowid::LearnedRowIdIndex;
64pub use quotient_filter::{
65    DEFAULT_Q_BITS as QUOTIENT_FILTER_DEFAULT_Q_BITS,
66    DEFAULT_R_BITS as QUOTIENT_FILTER_DEFAULT_R_BITS, QuotientFilter, QuotientFilterError,
67    hash_rowid as quotient_filter_hash_rowid,
68};
69pub use swizzle::{PageTemperature, SwizzleError, SwizzlePtr, SwizzleState};
70pub use traits::{BtreeCursorOps, MockBtreeCursor, SeekResult};
71
72/// Compare two B-tree keys stored as contiguous byte slices.
73///
74/// This is the hot comparison primitive for blobkey paths. It performs
75/// sequential byte access with no pointer chasing or virtual dispatch.
76#[must_use]
77pub fn compare_key_bytes_contiguous(left: &[u8], right: &[u8]) -> Ordering {
78    left.cmp(right)
79}
80
81#[cfg(test)]
82mod hot_path_tests {
83    use super::*;
84
85    const BEAD_ID: &str = "bd-22n.6";
86
87    #[test]
88    fn test_btree_key_comparison_contiguous() {
89        // Both slices are adjacent views into a single contiguous buffer.
90        let backing = b"alpha___beta____".to_vec();
91        let left = &backing[0..8];
92        let right = &backing[8..16];
93
94        assert_eq!(
95            left.as_ptr().wrapping_add(left.len()),
96            right.as_ptr(),
97            "bead_id={BEAD_ID} case=adjacent_contiguous_key_slices"
98        );
99
100        assert_eq!(
101            compare_key_bytes_contiguous(left, right),
102            left.cmp(right),
103            "bead_id={BEAD_ID} case=hot_compare_matches_slice_cmp"
104        );
105    }
106
107    #[test]
108    fn test_no_pointer_chasing_in_hot_comparison() {
109        // Signature guard: hot compare is defined on raw slices only.
110        let hot_compare: fn(&[u8], &[u8]) -> Ordering = compare_key_bytes_contiguous;
111
112        let a = b"abcdefgh12345678";
113        let b = b"abcdefgh12345679";
114        assert_eq!(
115            hot_compare(a, b),
116            Ordering::Less,
117            "bead_id={BEAD_ID} case=expected_ordering"
118        );
119
120        // Sequential index walk mirrors the hot loop memory access pattern.
121        let mut steps = 0usize;
122        for idx in 0..a.len() {
123            steps = steps.saturating_add(1);
124            if a[idx] != b[idx] {
125                break;
126            }
127        }
128        assert_eq!(
129            steps,
130            a.len(),
131            "bead_id={BEAD_ID} case=sequential_access_until_tail_difference"
132        );
133    }
134}
135
136#[cfg(test)]
137mod interior_delete_test;
138
139#[cfg(test)]
140mod table_seek_bug_test;
141
142#[cfg(test)]
143mod index_seek_bug_test;
144mod index_seek_bug_test2;
fsqlite_btree/lib.rs

fsqlite_btree/
lib.rs
