]> Untitled Git - bdk/commit
feat(core): add skiplist to CheckPoint for faster traversal
author志宇 <hello@evanlinjin.me>
Thu, 25 Sep 2025 07:20:43 +0000 (07:20 +0000)
committer志宇 <hello@evanlinjin.me>
Fri, 15 May 2026 18:25:56 +0000 (18:25 +0000)
commitd9ce149db413c44c31d8719580876f7bbc31d277
tree6da2b8fb45d2cdeb5226233932e6b8a8c8876592
parent08d1bdee2fae549610abed2db705586305231e0c
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
crates/core/benches/checkpoint_skiplist.rs [new file with mode: 0644]
crates/core/src/checkpoint.rs
crates/core/tests/test_checkpoint_skiplist.rs [new file with mode: 0644]