Struct BucketChain

pub struct BucketChain<S: Bucket> {
    content: BTreeMap<S::Timestamp, (u32, S)>,
}

A sorted list of buckets, representing data bucketed by timestamp.

Bucket chains support three main APIs: finding buckets for a given timestamp, peeling off buckets up to a frontier, and restoring the chain property. All operations aim to be amortized logarithmic in the number of outstanding timestamps.

We achieve this by storing buckets of increasing size for timestamps that are further out in the future. At the same time, in a well-formed chain, adjacent buckets span a time range at most factor 4 different. Factor 4 means that we can skip at most one bucket size for adjacent buckets, limiting the amount of work we need to do when peeling off buckets or restoring the chain property.

A bucket chain is well-formed if all buckets are within two bits of each other, with an imaginary bucket of -2 bits at the start. A chain does not need to be well-formed at all times, and supports peeling and finding even if not well-formed. However, peel might need to split more buckets to extract the desired data.

The restore method can be used to restore the chain property. It needs to be called repeatedly with a positive amount of fuel while the remaining fuel after the call is non-positive. This allows the caller to control the amount of work done in a single call and interleave it with other work.

Fields

content: BTreeMap<S::Timestamp, (u32, S)>

Implementations

impl<S: Bucket> BucketChain<S>

pub fn new(storage: S) -> Self

Construct a new bucket chain. Spans the whole time domain.

pub fn range_of(&self, timestamp: &S::Timestamp) -> Option<Range<S::Timestamp>>

Find the time range for the bucket that contains data for time timestamp. Returns a range of the lower (inclusive) and upper (exclusive) time bound of the bucket, or None if there is no bucket for the requested time. Only times that haven’t been peeled can still be found.

The bounds are only valid until the next call to peel or restore.

pub fn find(&self, timestamp: &S::Timestamp) -> Option<&S>

Find the bucket that contains data for time timestamp. Returns a reference to the bucket, or None if there is no bucket for the requested time.

Only times that haven’t been peeled can still be found.

pub fn find_mut(&mut self, timestamp: &S::Timestamp) -> Option<&mut S>

Find the bucket that contains data for time timestamp. Returns a mutable reference to the bucket, or None if there is no bucket for the requested time.

Only times that haven’t been peeled can still be found.

pub fn peel(&mut self, frontier: AntichainRef<'_, S::Timestamp>) -> Vec<S>

Peel off all data up to frontier, where the returned buckets contain all data strictly less than the frontier.

pub fn restore(&mut self, fuel: &mut i64)

Restore the chain property by splitting buckets as necessary.

The chain is well-formed if all buckets are within two bits of each other, with an imaginary bucket of -2 bits just before the smallest bucket.

pub fn is_empty(&self) -> bool

Returns true if the chain is empty. This means there are no outstanding times left.

pub fn len(&self) -> usize

The number of buckets in the chain.

fn split_and_insert( &mut self, fuel: &mut i64, bits: u32, offset: S::Timestamp, storage: S, )

Split the bucket specified by (bits, offset, storage) and insert the new buckets. Updates fuel.

Panics if the bucket cannot be split, i.e, it covers 0 bits.

Trait Implementations

impl<S: Debug + Bucket> Debug for BucketChain<S>

where S::Timestamp: Debug,

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

Formats the value using the given formatter.