Struct BinarySearchChain 

pub struct BinarySearchChain<E: ChainEntry> { /* private fields */ }

A binary-search optimized version chain — the consolidated core.

Stores committed versions sorted descending by commit_ts, with at most one uncommitted version slot. Uses partition_point for O(log V) lookups.

This struct captures the duplicated logic previously in:

• durable_storage::VersionChain
• mvcc_concurrent::VersionChain

Both modules now wrap BinarySearchChain<E> and delegate the core binary-search / commit / abort / read / conflict-check operations to it.

Implementations

impl<E: ChainEntry> BinarySearchChain<E>

pub fn new() -> Self

Create a new empty chain.

pub fn set_uncommitted(&mut self, entry: E) -> Option<E>

Replace the uncommitted slot. Returns the previous entry if any.

pub fn uncommitted(&self) -> Option<&E>

Reference to the uncommitted entry.

pub fn uncommitted_mut(&mut self) -> Option<&mut E>

Mutable reference to the uncommitted entry.

pub fn commit(&mut self, txn_id: u64, commit_ts: u64) -> bool

Commit the uncommitted version with the given commit_ts.

Moves the entry from the uncommitted slot into the sorted committed list at the correct position. Returns true on success.

Complexity: O(log V) binary search + O(V) insert (amortised O(1) for newest).

pub fn abort(&mut self, txn_id: u64)

Abort a transaction — clear the uncommitted slot if it matches txn_id.

pub fn read_at( &self, snapshot_ts: u64, current_txn_id: Option<u64>, ) -> Option<&E>

Read the visible version at the given snapshot timestamp.

If current_txn_id is provided and matches the uncommitted version’s transaction, the uncommitted version is returned (read-own-writes).

Otherwise performs O(log V) binary search for the newest committed version with commit_ts < snapshot_ts.

pub fn has_write_conflict(&self, my_txn_id: u64) -> bool

Check if there’s a write-write conflict with another transaction.

pub fn gc_by_ts(&mut self, min_active_ts: u64)

GC versions older than min_active_ts.

Retention must agree with read_at, whose visibility rule is strict: a reader at snapshot S observes the newest version with commit_ts < S. The smallest live snapshot is min_active_ts, so the oldest version any reader can still need is the newest one with commit_ts < min_active_ts. We therefore keep every version with commit_ts >= min_active_ts plus one anchor — the newest version strictly below min_active_ts.

Using >= here (rather than >) is load-bearing for read-safety: with >, a boundary version whose commit_ts == min_active_ts would be chosen as the anchor and the genuinely-needed older version (the one a reader at snapshot == min_active_ts resolves, since that boundary version is not visible to it under the strict < rule) would be freed — causing the reader to observe a spurious None.

pub fn version_count(&self) -> usize

Total version count (committed + uncommitted).

pub fn committed_count(&self) -> usize

Number of committed versions.

pub fn is_empty(&self) -> bool

Check if chain is empty.

pub fn committed_versions(&self) -> &[E]

Slice of committed versions (newest first).

pub fn committed_versions_mut(&mut self) -> &mut Vec<E>

Mutable access to committed versions (for custom GC).

pub fn latest(&self) -> Option<&E>

Latest version: uncommitted if present, else newest committed.

pub fn latest_committed(&self) -> Option<&E>

Newest committed version only.

Trait Implementations

impl<E: Debug + ChainEntry> Debug for BinarySearchChain<E>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<E: ChainEntry> Default for BinarySearchChain<E>

fn default() -> Self

Returns the “default value” for a type.