Bitmap

Struct Bitmap 

Source
pub struct Bitmap<H: CHasher, const N: usize> { /* private fields */ }
Expand description

A bitmap supporting inclusion proofs through Merkelization.

Merkelization of the bitmap is performed over chunks of N bytes. If the goal is to minimize proof sizes, choose an N that is equal to the size or double the size of the hasher’s digest.

§Warning

Even though we use u64 identifiers for bits, on 32-bit machines, the maximum addressable bit is limited to (u32::MAX * N * 8).

Implementations§

Source§

impl<H: CHasher, const N: usize> Bitmap<H, N>

Source

pub const CHUNK_SIZE: usize = N

The size of a chunk in bytes.

Source

pub const CHUNK_SIZE_BITS: u64

The size of a chunk in bits.

Source

pub fn new() -> Self

Return a new empty bitmap.

Source

pub fn size(&self) -> u64

Source

pub fn get_node(&self, position: u64) -> Option<H::Digest>

Source

pub async fn restore_pruned<C: RStorage + Metrics + Clock>( context: C, partition: &str, pool: Option<ThreadPool>, ) -> Result<Self, Error>

Restore the fully pruned state of a bitmap from the metadata in the given partition. (The caller must still replay retained elements to restore its full state.)

The metadata must store the number of pruned chunks and the pinned digests corresponding to that pruning boundary.

Source

pub async fn write_pruned<C: RStorage + Metrics + Clock>( &self, context: C, partition: &str, ) -> Result<(), Error>

Write the information necessary to restore the bitmap in its fully pruned state at its last pruning boundary. Restoring the entire bitmap state is then possible by replaying the retained elements.

Source

pub fn bit_count(&self) -> u64

Return the number of bits currently stored in the bitmap, irrespective of any pruning.

Source

pub fn pruned_bits(&self) -> u64

Return the number of bits that have been pruned from this bitmap.

Source

pub fn prune_to_bit(&mut self, bit_offset: u64)

Prune the bitmap to the most recent chunk boundary that contains the referenced bit.

§Warning
  • Panics if the referenced bit is greater than the number of bits in the bitmap.

  • Panics if there are unprocessed updates.

Source

pub fn last_chunk(&self) -> (&[u8; N], u64)

Return the last chunk of the bitmap and its size in bits. The size can be 0 (meaning the last chunk is empty).

Source

pub fn get_chunk(&self, bit_offset: u64) -> &[u8; N]

Returns the bitmap chunk containing the specified bit.

§Warning

Panics if the bit doesn’t exist or has been pruned.

Source

pub fn append_chunk_unchecked(&mut self, chunk: &[u8; N])

Efficiently add a chunk of bits to the bitmap.

§Warning
  • The update will not impact the root until sync is called.

  • Assumes we are at a chunk boundary (that is, self.next_bit is 0) and panics otherwise.

Source

pub fn append_byte_unchecked(&mut self, byte: u8)

Efficiently add a byte’s worth of bits to the bitmap.

§Warning
  • The update will not impact the root until sync is called.

  • Assumes self.next_bit is currently byte aligned, and panics otherwise.

Source

pub fn append(&mut self, bit: bool)

Add a single bit to the bitmap.

§Warning

The update will not affect the root until sync is called.

Source

pub fn get_bit(&self, bit_offset: u64) -> bool

Get the value of a bit.

§Warning

Panics if the bit doesn’t exist or has been pruned.

Source

pub fn get_bit_from_chunk(chunk: &[u8; N], bit_offset: u64) -> bool

Get the value of a bit from its chunk.

Source

pub fn set_bit(&mut self, bit_offset: u64, bit: bool)

Set the value of the referenced bit.

§Warning

The update will not impact the root until sync is called.

Source

pub fn is_dirty(&self) -> bool

Whether there are any updates that are not yet reflected in this bitmap’s root.

Source

pub fn dirty_chunks(&self) -> Vec<u64>

The chunks (identified by their number) that have been modified or added since the last sync.

Source

pub async fn sync(&mut self, hasher: &mut impl Hasher<H>) -> Result<(), Error>

Process all updates not yet reflected in the bitmap’s root.

Source

pub async fn root( &self, hasher: &mut impl Hasher<H>, ) -> Result<H::Digest, Error>

Return the root digest against which inclusion proofs can be verified.

§Format

The root digest is simply that of the underlying MMR whenever the bit count falls on a chunk boundary. Otherwise, the root is computed as follows in order to capture the bits that are not yet part of the MMR:

hash(mmr_root || next_bit as u64 be_bytes || last_chunk_digest)

§Warning

Panics if there are unprocessed updates.

Source

pub fn partial_chunk_root( hasher: &mut H, mmr_root: &H::Digest, next_bit: u64, last_chunk_digest: &H::Digest, ) -> H::Digest

Returns a root digest that incorporates bits that aren’t part of the MMR yet because they belong to the last (unfilled) chunk.

Source

pub async fn proof( &self, hasher: &mut impl Hasher<H>, bit_offset: u64, ) -> Result<(Proof<H::Digest>, [u8; N]), Error>

Return an inclusion proof for the specified bit, along with the chunk of the bitmap containing that bit. The proof can be used to prove any bit in the chunk.

§Warning

Panics if there are unprocessed updates.

Source

pub fn verify_bit_inclusion( hasher: &mut impl Hasher<H>, proof: &Proof<H::Digest>, chunk: &[u8; N], bit_offset: u64, root: &H::Digest, ) -> bool

Verify whether proof proves that the chunk containing the referenced bit belongs to the bitmap corresponding to root.

Source

pub async fn destroy<C: RStorage + Metrics + Clock>( context: C, partition: &str, ) -> Result<(), Error>

Destroy the bitmap metadata from disk.

Trait Implementations§

Source§

impl<H: CHasher, const N: usize> Default for Bitmap<H, N>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<H: CHasher, const N: usize> Storage<<H as Hasher>::Digest> for Bitmap<H, N>

Source§

fn size(&self) -> u64

Return the number of elements in the MMR.
Source§

async fn get_node(&self, position: u64) -> Result<Option<H::Digest>, Error>

Return the specified node of the MMR if it exists & hasn’t been pruned.

Auto Trait Implementations§

§

impl<H, const N: usize> Freeze for Bitmap<H, N>
where <H as Hasher>::Digest: Freeze,

§

impl<H, const N: usize> !RefUnwindSafe for Bitmap<H, N>

§

impl<H, const N: usize> Send for Bitmap<H, N>

§

impl<H, const N: usize> Sync for Bitmap<H, N>

§

impl<H, const N: usize> Unpin for Bitmap<H, N>
where <H as Hasher>::Digest: Unpin,

§

impl<H, const N: usize> !UnwindSafe for Bitmap<H, N>

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T> FutureExt for T

Source§

fn with_context(self, otel_cx: Context) -> WithContext<Self>

Attaches the provided Context to this type, returning a WithContext wrapper. Read more
Source§

fn with_current_context(self) -> WithContext<Self>

Attaches the current Context to this type, returning a WithContext wrapper. Read more
Source§

impl<T> Instrument for T

Source§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
Source§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> IntoEither for T

Source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

impl<T> Pointable for T

Source§

const ALIGN: usize

The alignment of pointer.
Source§

type Init = T

The type for initializers.
Source§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
Source§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
Source§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
Source§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
Source§

impl<T> PolicyExt for T
where T: ?Sized,

Source§

fn and<P, B, E>(self, other: P) -> And<T, P>
where T: Policy<B, E>, P: Policy<B, E>,

Create a new Policy that returns Action::Follow only if self and other return Action::Follow. Read more
Source§

fn or<P, B, E>(self, other: P) -> Or<T, P>
where T: Policy<B, E>, P: Policy<B, E>,

Create a new Policy that returns Action::Follow if either self or other returns Action::Follow. Read more
Source§

impl<T> Same for T

Source§

type Output = T

Should always be Self
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
Source§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

Source§

fn vzip(self) -> V

Source§

impl<T> WithSubscriber for T

Source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
Source§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more
Source§

impl<T> ErasedDestructor for T
where T: 'static,

Source§

impl<A, B, T> HttpServerConnExec<A, B> for T
where B: Body,