From d9ce149db413c44c31d8719580876f7bbc31d277 Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E5=BF=97=E5=AE=87?= Date: Thu, 25 Sep 2025 07:20:43 +0000 Subject: [PATCH] feat(core): add skiplist to CheckPoint for faster traversal Adds a skip pointer and an index field to CheckPoint to accelerate get(), floor_at(), and range(). push() and insert() maintain the index/skip invariants on the rebuilt chain. The skip pointer follows Bitcoin Core's `CBlockIndex::pskip` pattern, adapted to operate on checkpoint indices (not heights) so it works on sparse chains. Skip distances grow exponentially as you walk back, yielding O(log n) traversal. --- crates/core/Cargo.toml | 6 + crates/core/benches/checkpoint_skiplist.rs | 236 +++++++++++++++ crates/core/src/checkpoint.rs | 220 +++++++++++++- crates/core/tests/test_checkpoint_skiplist.rs | 275 ++++++++++++++++++ 4 files changed, 722 insertions(+), 15 deletions(-) create mode 100644 crates/core/benches/checkpoint_skiplist.rs create mode 100644 crates/core/tests/test_checkpoint_skiplist.rs diff --git a/crates/core/Cargo.toml b/crates/core/Cargo.toml index a56863d9..ed313f3a 100644 --- a/crates/core/Cargo.toml +++ b/crates/core/Cargo.toml @@ -23,3 +23,9 @@ serde = ["dep:serde", "bitcoin/serde", "hashbrown?/serde"] [dev-dependencies] bdk_chain = { path = "../chain" } bdk_testenv = { path = "../testenv", default-features = false } +criterion = { version = "0.7" } +proptest = "1.2.0" + +[[bench]] +name = "checkpoint_skiplist" +harness = false diff --git a/crates/core/benches/checkpoint_skiplist.rs b/crates/core/benches/checkpoint_skiplist.rs new file mode 100644 index 00000000..2b9ea29c --- /dev/null +++ b/crates/core/benches/checkpoint_skiplist.rs @@ -0,0 +1,236 @@ +use bdk_core::CheckPoint; +use bitcoin::hashes::Hash; +use bitcoin::BlockHash; +use core::hint::black_box; +use criterion::{criterion_group, criterion_main, Bencher, Criterion}; + +/// Create a checkpoint chain with the given length +fn create_checkpoint_chain(length: u32) -> CheckPoint { + let mut cp = CheckPoint::new(0, BlockHash::all_zeros()); + for height in 1..=length { + let hash = BlockHash::from_byte_array([(height % 256) as u8; 32]); + cp = cp.push(height, hash).unwrap(); + } + cp +} + +/// Benchmark get() operations at various depths +fn bench_checkpoint_get(c: &mut Criterion) { + // Small chain - get near start + c.bench_function("get_100_near_start", |b: &mut Bencher| { + let cp = create_checkpoint_chain(100); + let target = 10; + b.iter(|| { + black_box(cp.get(target)); + }); + }); + + // Medium chain - get middle + c.bench_function("get_1000_middle", |b: &mut Bencher| { + let cp = create_checkpoint_chain(1000); + let target = 500; + b.iter(|| { + black_box(cp.get(target)); + }); + }); + + // Large chain - get near end + c.bench_function("get_10000_near_end", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + let target = 9000; + b.iter(|| { + black_box(cp.get(target)); + }); + }); + + // Large chain - get near start (best case for skiplist) + c.bench_function("get_10000_near_start", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + let target = 100; + b.iter(|| { + black_box(cp.get(target)); + }); + }); +} + +/// Benchmark floor_at() operations +fn bench_checkpoint_floor_at(c: &mut Criterion) { + c.bench_function("floor_at_1000", |b: &mut Bencher| { + let cp = create_checkpoint_chain(1000); + let target = 750; // Target that might not exist exactly + b.iter(|| { + black_box(cp.floor_at(target)); + }); + }); + + c.bench_function("floor_at_10000", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + let target = 7500; + b.iter(|| { + black_box(cp.floor_at(target)); + }); + }); +} + +/// Benchmark range() iteration +fn bench_checkpoint_range(c: &mut Criterion) { + // Small range in middle (tests skip pointer efficiency) + c.bench_function("range_1000_middle_10pct", |b: &mut Bencher| { + let cp = create_checkpoint_chain(1000); + b.iter(|| { + let range: Vec<_> = cp.range(450..=550).collect(); + black_box(range); + }); + }); + + // Large range (tests iteration performance) + c.bench_function("range_10000_large_50pct", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + b.iter(|| { + let range: Vec<_> = cp.range(2500..=7500).collect(); + black_box(range); + }); + }); + + // Range from start (tests early termination) + c.bench_function("range_10000_from_start", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + b.iter(|| { + let range: Vec<_> = cp.range(..=100).collect(); + black_box(range); + }); + }); + + // Range near tip (minimal skip pointer usage) + c.bench_function("range_10000_near_tip", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + b.iter(|| { + let range: Vec<_> = cp.range(9900..).collect(); + black_box(range); + }); + }); + + // Single element range (edge case) + c.bench_function("range_single_element", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + b.iter(|| { + let range: Vec<_> = cp.range(5000..=5000).collect(); + black_box(range); + }); + }); +} + +/// Benchmark insert() operations +fn bench_checkpoint_insert(c: &mut Criterion) { + c.bench_function("insert_sparse_1000", |b: &mut Bencher| { + // Create a sparse chain + let mut cp = CheckPoint::new(0, BlockHash::all_zeros()); + for i in 1..=100 { + let height = i * 10; + let hash = BlockHash::from_byte_array([(height % 256) as u8; 32]); + cp = cp.push(height, hash).unwrap(); + } + + let insert_height = 505; + let insert_hash = BlockHash::from_byte_array([255; 32]); + + b.iter(|| { + let result = cp.clone().insert(insert_height, insert_hash); + black_box(result); + }); + }); +} + +/// Compare linear traversal vs skiplist-enhanced get() +fn bench_traversal_comparison(c: &mut Criterion) { + // Linear traversal benchmark + c.bench_function("linear_traversal_10000", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + let target = 100; // Near the beginning + + b.iter(|| { + let mut current = cp.clone(); + while current.height() > target { + if let Some(prev) = current.prev() { + current = prev; + } else { + break; + } + } + black_box(current); + }); + }); + + // Skiplist-enhanced get() for comparison + c.bench_function("skiplist_get_10000", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + let target = 100; // Same target + + b.iter(|| { + black_box(cp.get(target)); + }); + }); +} + +/// Analyze skip pointer distribution and usage +fn bench_skip_pointer_analysis(c: &mut Criterion) { + c.bench_function("count_skip_pointers_10000", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + + b.iter(|| { + let mut count = 0; + let mut current = cp.clone(); + loop { + if current.skip().is_some() { + count += 1; + } + if let Some(prev) = current.prev() { + current = prev; + } else { + break; + } + } + black_box(count); + }); + }); + + // Measure actual skip pointer usage during traversal + c.bench_function("skip_usage_in_traversal", |b: &mut Bencher| { + let cp = create_checkpoint_chain(10000); + let target = 100; + + b.iter(|| { + let mut current = cp.clone(); + let mut skips_used = 0; + + while current.height() > target { + if let Some(skip_cp) = current.skip() { + if skip_cp.height() >= target { + current = skip_cp; + skips_used += 1; + continue; + } + } + + if let Some(prev) = current.prev() { + current = prev; + } else { + break; + } + } + black_box((current, skips_used)); + }); + }); +} + +criterion_group!( + benches, + bench_checkpoint_get, + bench_checkpoint_floor_at, + bench_checkpoint_range, + bench_checkpoint_insert, + bench_traversal_comparison, + bench_skip_pointer_analysis +); + +criterion_main!(benches); diff --git a/crates/core/src/checkpoint.rs b/crates/core/src/checkpoint.rs index 3d33a268..e560fd6b 100644 --- a/crates/core/src/checkpoint.rs +++ b/crates/core/src/checkpoint.rs @@ -6,6 +6,93 @@ use core::ops::RangeBounds; use crate::{BlockId, CheckPointEntry, CheckPointEntryIter}; +/// Returns the checkpoint index that index `i` should hold a skip pointer to. +/// +/// Mirrors Bitcoin Core's `GetSkipHeight` (operating on checkpoint indices rather than block +/// heights, so sparse chains work). The chosen targets give skip distances that grow +/// exponentially as you walk back, yielding `O(log n)` traversal. +/// +/// For `i < 2` returns `0` — `prev` already covers those distances trivially. +fn skip_index(i: u32) -> u32 { + // Clears the lowest set bit of `n`. This is what unlocks the exponential skip range: + // each call strips one trailing 1-bit, so the result lands at a power-of-two-aligned + // index below `n`. + fn invert_lowest_one(n: u32) -> u32 { + // Wrapping sub so that `invert_lowest_one(0) == 0` (matches Bitcoin Core's signed-int + // `n & (n-1)` semantics). The odd-i branch below relies on `invert_lowest_one(0) == 0` + // when `i == 3`. + n & n.wrapping_sub(1) + } + if i < 2 { + return 0; + } + if i & 1 == 0 { + return invert_lowest_one(i); + } + invert_lowest_one(invert_lowest_one(i - 1)) + 1 +} + +/// Walks back from `start` to the ancestor at `target` index, riding skip pointers in `O(log n)`. +/// +/// Equivalent to Bitcoin Core's `CBlockIndex::GetAncestor`. +fn ancestor_by_index(start: &Arc>, target: u32) -> Arc> { + debug_assert!(target <= start.index); + let mut curr = start.clone(); + while curr.index > target { + let skip_i = skip_index(curr.index); + let skip_i_prev = skip_index(curr.index.saturating_sub(1)); + + // Prev's skip is "strictly better" when it lands more than 2 indices below current's + // skip AND still reaches `target`. In that case we'd rather take one step back via + // `prev` and ride its longer skip next iteration. + let prev_skip_strictly_better = + skip_i > skip_i_prev.saturating_add(2) && skip_i_prev >= target; + let use_skip = curr.skip.is_some() + && (skip_i == target || (skip_i > target && !prev_skip_strictly_better)); + + curr = if use_skip { + curr.skip.clone().expect("checked above") + } else { + curr.prev + .clone() + .expect("walking toward smaller target requires prev") + }; + } + + curr +} + +/// Walks back from `current` to the highest checkpoint at or below `target_height`. +/// +/// Internally rides skip pointers using Bitcoin Core's `GetAncestor` skip-vs-prev heuristic, +/// adapted to operate on heights so it works on sparse checkpoint chains. +/// +/// Returns `None` only when the chain's base is itself above `target_height` (no ancestor exists +/// at or below the target). +fn walk_to_floor(current: &CheckPoint, target_height: u32) -> Option> { + let mut curr = current.clone(); + while curr.height() > target_height { + let skip = curr.skip(); + let take_skip = match &skip { + Some(skip_cp) if skip_cp.height() < target_height => false, + Some(skip_cp) if skip_cp.height() == target_height => true, + // Skip lands above target. Prefer prev's skip if it's a strictly bigger jump (lands + // more than 2 heights lower than current's skip) that still reaches target. + Some(skip_cp) => match curr.prev().and_then(|p| p.skip()) { + Some(prev_skip_cp) => { + let prev_skip_h = prev_skip_cp.height(); + let skip_gap = skip_cp.height().saturating_sub(prev_skip_h); + !(skip_gap > 2 && prev_skip_h >= target_height) + } + None => true, + }, + None => false, + }; + curr = if take_skip { skip? } else { curr.prev()? }; + } + Some(curr) +} + /// A checkpoint is a node of a reference-counted linked list of [`BlockId`]s. /// /// Checkpoints are cheaply cloneable and are useful to find the agreement point between two sparse @@ -28,6 +115,10 @@ struct CPInner { data: D, /// Previous checkpoint (if any). prev: Option>>, + /// Skip pointer for fast traversals. + skip: Option>>, + /// Index of this checkpoint (number of checkpoints from the first). + index: u32, } /// When a `CPInner` is dropped we need to go back down the chain and manually remove any @@ -46,8 +137,10 @@ impl Drop for CPInner { let arc_inner = Arc::into_inner(arc_node); match arc_inner { - // Keep going backwards. - Some(mut node) => current = node.prev.take(), + Some(mut node) => { + node.skip.take(); // We don't want to recursively drop `node.skip`. + current = node.prev.take(); + } None => break, } } @@ -144,6 +237,25 @@ impl CheckPoint { self.0.prev.clone().map(CheckPoint) } + /// Get the index of this checkpoint (number of checkpoints from the first). + pub fn index(&self) -> u32 { + self.0.index + } + + /// Get this checkpoint's pskip ancestor, if one exists. + /// + /// Returns the ancestor at the [skip index](Self::index) — a deterministically chosen + /// checkpoint that lets traversals cover exponentially-growing distances per hop. Returns + /// `None` for the genesis checkpoint (index `0`); for index `1`, the skip ancestor is the same + /// checkpoint as `prev`. + /// + /// This accessor exposes the internal pskip topology and is intended for diagnostics and + /// benchmarks, not for general-purpose traversal — use [`get`](Self::get), + /// [`range`](Self::range), or [`floor_at`](Self::floor_at) instead. + pub fn skip(&self) -> Option> { + self.0.skip.clone().map(CheckPoint) + } + /// Iterate from this checkpoint in descending height. pub fn iter(&self) -> CheckPointIter { self.clone().into_iter() @@ -153,7 +265,15 @@ impl CheckPoint { /// /// Returns `None` if checkpoint at `height` does not exist`. pub fn get(&self, height: u32) -> Option { - self.range(height..=height).next() + if self.height() < height { + return None; + } + let floor = walk_to_floor(self, height)?; + if floor.height() == height { + Some(floor) + } else { + None + } } /// Iterate checkpoints over a height range. @@ -166,12 +286,18 @@ impl CheckPoint { { let start_bound = range.start_bound().cloned(); let end_bound = range.end_bound().cloned(); - self.iter() - .skip_while(move |cp| match end_bound { - core::ops::Bound::Included(inc_bound) => cp.height() > inc_bound, - core::ops::Bound::Excluded(exc_bound) => cp.height() >= exc_bound, - core::ops::Bound::Unbounded => false, - }) + + // Find the highest checkpoint at or below the upper bound in `O(log n)`. For unbounded + // upper, start at `self`; for an excluded `0`, the range is empty. + let start = match end_bound { + core::ops::Bound::Included(b) => walk_to_floor(self, b), + core::ops::Bound::Excluded(b) => b.checked_sub(1).and_then(|b| walk_to_floor(self, b)), + core::ops::Bound::Unbounded => Some(self.clone()), + }; + + start + .into_iter() + .flat_map(IntoIterator::into_iter) .take_while(move |cp| match start_bound { core::ops::Bound::Included(inc_bound) => cp.height() >= inc_bound, core::ops::Bound::Excluded(exc_bound) => cp.height() > exc_bound, @@ -246,6 +372,8 @@ where }, data, prev: None, + skip: None, + index: 0, })) } @@ -408,6 +536,13 @@ where } } + let new_index = self.0.index + 1; + + // Wire the pskip pointer to the ancestor at skip_index(new_index). This is what makes + // traversal O(log n): each checkpoint carries one skip Arc to a deterministically chosen + // ancestor, and the chosen distances grow exponentially as you walk back. + let skip = Some(ancestor_by_index(&self.0, skip_index(new_index))); + Ok(Self(Arc::new(CPInner { block_id: BlockId { height, @@ -415,6 +550,8 @@ where }, data, prev: Some(self.0), + skip, + index: new_index, }))) } } @@ -471,9 +608,11 @@ mod tests { #[test] fn checkpoint_does_not_leak() { + const CHAIN_LEN: u32 = 1000; + let mut cp = CheckPoint::new(0, bitcoin::hashes::Hash::hash(b"genesis")); - for height in 1u32..=1000 { + for height in 1u32..=CHAIN_LEN { let hash: BlockHash = bitcoin::hashes::Hash::hash(height.to_be_bytes().as_slice()); cp = cp.push(height, hash).unwrap(); } @@ -481,15 +620,22 @@ mod tests { let genesis = cp.get(0).expect("genesis exists"); let weak = Arc::downgrade(&genesis.0); - // At this point there should be exactly two strong references to the - // genesis checkpoint: the variable `genesis` and the chain `cp`. + // Expected strong references to genesis: + // - the `genesis` local variable + // - the chain `cp` via index 1's prev pointer + // - one skip Arc per node `i` in `1..=CHAIN_LEN` where `skip_index(i) == 0` (under pskip, + // those are i=1 and every power of 2 in [2, CHAIN_LEN]). + let expected_skips_to_genesis = (1..=CHAIN_LEN).filter(|&i| skip_index(i) == 0).count(); + let expected_strong = 2 + expected_skips_to_genesis; + assert_eq!( Arc::strong_count(&genesis.0), - 2, - "`cp` and `genesis` should be the only strong references", + expected_strong, + "`genesis`, the chain's prev to genesis, and every pskip ancestor pointing to genesis \ + should be the only strong references", ); - // Dropping the chain should remove one strong reference. + // Dropping the chain should leave `genesis` as the only remaining strong reference. drop(cp); assert_eq!( Arc::strong_count(&genesis.0), @@ -505,4 +651,48 @@ mod tests { "the checkpoint node should be freed when all strong references are dropped", ); } + + #[test] + fn skip_index_formula_table() { + // Hand-computed table of skip_index(i) for i in 0..=32, matching Bitcoin Core's + // GetSkipHeight. This locks the bit-twiddling formula against silent breakage. + let expected: [u32; 33] = [ + 0, // 0 + 0, // 1 + 0, // 2 -> 010 & 001 = 000 + 1, // 3 odd: ilo(ilo(2))+1 = ilo(0)+1 = 1 + 0, // 4 -> 100 & 011 = 000 + 1, // 5 odd: ilo(ilo(4))+1 = 1 + 4, // 6 -> 110 & 101 = 100 + 1, // 7 odd: ilo(ilo(6))+1 = ilo(4)+1 = 1 + 0, // 8 + 1, // 9 + 8, // 10 -> 1010 & 1001 = 1000 + 1, // 11 + 8, // 12 -> 1100 & 1011 = 1000 + 1, // 13 + 12, // 14 -> 1110 & 1101 = 1100 + 9, // 15 odd: ilo(ilo(14))+1 = ilo(12)+1 = 8+1 = 9 + 0, // 16 + 1, // 17 + 16, // 18 + 1, // 19 + 16, // 20 + 1, // 21 + 20, // 22 -> 10110 & 10101 = 10100 + 17, // 23 odd: ilo(ilo(22))+1 = ilo(20)+1 = 16+1 = 17 + 16, // 24 + 1, // 25 + 24, // 26 -> 11010 & 11001 = 11000 + 17, // 27 odd: ilo(ilo(26))+1 = ilo(24)+1 = 16+1 = 17 + 24, // 28 -> 11100 & 11011 = 11000 + 17, // 29 odd: ilo(ilo(28))+1 = ilo(24)+1 = 17 + 28, // 30 -> 11110 & 11101 = 11100 + 25, // 31 odd: ilo(ilo(30))+1 = ilo(28)+1 = 24+1 = 25 + 0, // 32 + ]; + for (i, want) in expected.iter().enumerate() { + assert_eq!(skip_index(i as u32), *want, "skip_index({i}) mismatch"); + } + } } diff --git a/crates/core/tests/test_checkpoint_skiplist.rs b/crates/core/tests/test_checkpoint_skiplist.rs new file mode 100644 index 00000000..56e61a3e --- /dev/null +++ b/crates/core/tests/test_checkpoint_skiplist.rs @@ -0,0 +1,275 @@ +use bdk_core::CheckPoint; +use bitcoin::hashes::Hash; +use bitcoin::BlockHash; +use proptest::prelude::*; + +/// Independent reference implementation of `bdk_core`'s private `skip_index` formula (mirrors +/// Bitcoin Core's `GetSkipHeight`, operating on 0-based checkpoint indices). Reimplementing the +/// formula in the test file keeps the structural-invariant assertion meaningful — if someone +/// changes the library's `skip_index`, this test will catch it instead of vacuously agreeing with +/// itself. +fn expected_skip_index(i: u32) -> u32 { + if i < 2 { + return 0; + } + fn invert_lowest_one(n: u32) -> u32 { + n & n.wrapping_sub(1) + } + if i & 1 == 0 { + invert_lowest_one(i) + } else { + invert_lowest_one(invert_lowest_one(i - 1)) + 1 + } +} + +#[test] +fn test_skiplist_indices() { + // Build a chain spanning multiple log levels and assert that each node carries the pskip + // pointer mandated by the formula. + let mut cp = CheckPoint::new(0, BlockHash::all_zeros()); + assert_eq!(cp.index(), 0); + assert!(cp.skip().is_none(), "genesis must not have a skip pointer"); + + const N: u32 = 5000; + for height in 1..=N { + let hash = BlockHash::from_byte_array([(height % 256) as u8; 32]); + cp = cp.push(height, hash).unwrap(); + assert_eq!(cp.index(), height); + } + assert_eq!(cp.index(), N); + + // Walk the chain once and verify every non-genesis node skips to expected_skip_index(i). + let mut current = cp; + loop { + let i = current.index(); + match current.skip() { + Some(skip) => { + let skip_index = skip.index(); + let exp_skip_index = expected_skip_index(i); + assert_eq!( + skip_index, exp_skip_index, + "node at index {i} should skip to {exp_skip_index} but skips to {skip_index}", + ) + } + None => assert_eq!(i, 0, "only the genesis node may have no skip pointer"), + } + match current.prev() { + Some(prev) => current = prev, + None => break, + } + } +} + +#[test] +fn test_skiplist_insert_maintains_indices() { + let mut cp = CheckPoint::new(0, BlockHash::all_zeros()); + + // Build initial chain + for height in [10, 20, 30, 40, 50] { + let hash = BlockHash::from_byte_array([height as u8; 32]); + cp = cp.push(height, hash).unwrap(); + } + + // Insert a block in the middle + let hash = BlockHash::from_byte_array([25; 32]); + cp = cp.insert(25, hash); + + // Check the full chain has correct indices + let mut current = cp.clone(); + let expected_heights = [50, 40, 30, 25, 20, 10, 0]; + let expected_indices = [6, 5, 4, 3, 2, 1, 0]; + + for (expected_height, expected_index) in expected_heights.iter().zip(expected_indices.iter()) { + assert_eq!(current.height(), *expected_height); + assert_eq!(current.index(), *expected_index); + if *expected_height > 0 { + current = current.prev().unwrap(); + } + } +} + +#[test] +fn test_range_edge_cases() { + let mut cp = CheckPoint::new(0, BlockHash::all_zeros()); + + // Create sparse chain: 0, 100, 200, 300, 400, 500 + for i in 1..=5 { + let height = i * 100; + let hash = BlockHash::from_byte_array([i as u8; 32]); + cp = cp.push(height, hash).unwrap(); + } + + // Empty range (start > end) + #[allow(clippy::reversed_empty_ranges)] + let empty: Vec<_> = cp.range(300..200).collect(); + assert!(empty.is_empty()); + + // Single element range + let single: Vec<_> = cp.range(300..=300).collect(); + assert_eq!(single.len(), 1); + assert_eq!(single[0].height(), 300); + + // Range with non-existent bounds (150..250) + let partial: Vec<_> = cp.range(150..250).collect(); + assert_eq!(partial.len(), 1); + assert_eq!(partial[0].height(), 200); + + // Exclusive end bound (100..300 includes 100 and 200, but not 300) + let exclusive: Vec<_> = cp.range(100..300).collect(); + assert_eq!(exclusive.len(), 2); + assert_eq!(exclusive[0].height(), 200); + assert_eq!(exclusive[1].height(), 100); + + // Unbounded range (..) + let all: Vec<_> = cp.range(..).collect(); + assert_eq!(all.len(), 6); + assert_eq!(all.first().unwrap().height(), 500); + assert_eq!(all.last().unwrap().height(), 0); + + // Range beyond chain bounds + let beyond: Vec<_> = cp.range(600..700).collect(); + assert!(beyond.is_empty()); + + // Range from genesis + let from_genesis: Vec<_> = cp.range(0..=200).collect(); + assert_eq!(from_genesis.len(), 3); + assert_eq!(from_genesis[0].height(), 200); + assert_eq!(from_genesis[2].height(), 0); +} + +/// Build a sparse chain at the given heights (genesis at 0 is implicit; `heights` must be a +/// strictly increasing sequence of positive heights). +fn build_chain(heights: &[u32]) -> CheckPoint { + let mut cp = CheckPoint::new(0, BlockHash::all_zeros()); + for (i, &h) in heights.iter().enumerate() { + let hash = BlockHash::from_byte_array([((i + 1) & 0xff) as u8; 32]); + cp = cp.push(h, hash).unwrap(); + } + cp +} + +/// Linear-scan reference implementations against which the pskip-accelerated `get`/`range`/ +/// `floor_at` are compared. Walks the chain via `prev()` only. +mod reference { + use super::*; + use core::ops::{Bound, RangeBounds}; + + pub(super) fn get(cp: &CheckPoint, height: u32) -> Option> { + cp.iter().find(|c| c.height() == height) + } + + pub(super) fn floor_at( + cp: &CheckPoint, + height: u32, + ) -> Option> { + cp.iter().find(|c| c.height() <= height) + } + + pub(super) fn range_heights>( + cp: &CheckPoint, + range: R, + ) -> Vec { + let lo = match range.start_bound() { + Bound::Included(&v) => v, + Bound::Excluded(&v) => v.saturating_add(1), + Bound::Unbounded => 0, + }; + let hi = match range.end_bound() { + Bound::Included(&v) => v, + Bound::Excluded(&v) => v.saturating_sub(1), + Bound::Unbounded => u32::MAX, + }; + if lo > hi { + return vec![]; + } + cp.iter() + .filter(|c| c.height() >= lo && c.height() <= hi) + .map(|c| c.height()) + .collect() + } +} + +/// Strategy: pick a small, strictly-increasing set of positive heights up to a bound. +fn arbitrary_sparse_heights() -> impl Strategy> { + prop::collection::vec(1u32..=10_000, 0..200).prop_map(|mut v| { + v.sort_unstable(); + v.dedup(); + v + }) +} + +proptest! { + #![proptest_config(ProptestConfig { + cases: 64, + ..ProptestConfig::default() + })] + + /// `get(h)` matches a linear scan for any chain and any query height (existing, missing, + /// genesis, beyond tip, etc.). + #[test] + fn pskip_get_matches_linear(heights in arbitrary_sparse_heights(), q in 0u32..=10_500) { + let cp = build_chain(&heights); + let expected = reference::get(&cp, q).map(|c| c.height()); + let got = cp.get(q).map(|c| c.height()); + prop_assert_eq!(got, expected); + } + + /// `floor_at(h)` matches a linear scan. + #[test] + fn pskip_floor_at_matches_linear(heights in arbitrary_sparse_heights(), q in 0u32..=10_500) { + let cp = build_chain(&heights); + let expected = reference::floor_at(&cp, q).map(|c| c.height()); + let got = cp.floor_at(q).map(|c| c.height()); + prop_assert_eq!(got, expected); + } + + /// `range(a..=b)` (inclusive) matches a linear scan. + #[test] + fn pskip_range_inclusive_matches_linear( + heights in arbitrary_sparse_heights(), + a in 0u32..=10_500, + b in 0u32..=10_500, + ) { + let cp = build_chain(&heights); + let expected = reference::range_heights(&cp, a..=b); + let got: Vec = cp.range(a..=b).map(|c| c.height()).collect(); + prop_assert_eq!(got, expected); + } + + /// `range(a..b)` (exclusive end) matches a linear scan. + #[test] + fn pskip_range_exclusive_matches_linear( + heights in arbitrary_sparse_heights(), + a in 0u32..=10_500, + b in 0u32..=10_500, + ) { + let cp = build_chain(&heights); + let expected = reference::range_heights(&cp, a..b); + let got: Vec = cp.range(a..b).map(|c| c.height()).collect(); + prop_assert_eq!(got, expected); + } + + /// `range(..=b)` (unbounded start) matches a linear scan. + #[test] + fn pskip_range_unbounded_start_matches_linear( + heights in arbitrary_sparse_heights(), + b in 0u32..=10_500, + ) { + let cp = build_chain(&heights); + let expected = reference::range_heights(&cp, ..=b); + let got: Vec = cp.range(..=b).map(|c| c.height()).collect(); + prop_assert_eq!(got, expected); + } + + /// `range(a..)` (unbounded end) matches a linear scan. + #[test] + fn pskip_range_unbounded_end_matches_linear( + heights in arbitrary_sparse_heights(), + a in 0u32..=10_500, + ) { + let cp = build_chain(&heights); + let expected = reference::range_heights(&cp, a..); + let got: Vec = cp.range(a..).map(|c| c.height()).collect(); + prop_assert_eq!(got, expected); + } +} -- 2.49.0