Struct Format 

pub struct Format { /* private fields */ }

Helpers for a given storage configuration.

Implementations

impl Format

pub fn new<S: Storage>(storage: &S) -> Option<Format>

Extracts the format from a storage.

Returns None if the storage is not supported.

pub fn is_storage_supported<S: Storage>(storage: &S) -> bool

Returns whether a storage is supported.

A storage is supported if the following conditions hold:

• The Storage::word_size is WORD_SIZE bytes.
• The Storage::word_size evenly divides the Storage::page_size.
• The Storage::page_size is between MIN_PAGE_SIZE words and MAX_PAGE_SIZE bytes.
• The Storage::num_pages is between MIN_NUM_PAGES and MAX_PAGE_INDEX + 1.
• The Storage::max_word_writes is at least 2.
• The Storage::max_page_erases is at most MAX_ERASE_CYCLE.

pub fn word_size(&self) -> Nat

The size of a word in bytes.

pub fn page_size(&self) -> Nat

The size of a page in bytes.

This is at least MIN_PAGE_SIZE words and at most MAX_PAGE_SIZE bytes.

pub fn num_pages(&self) -> Nat

The number of pages in the storage, denoted by N.

We have MIN_NUM_PAGES <= N <= MAX_PAGE_INDEX + 1.

pub fn max_page(&self) -> Nat

The maximum page index.

This is at least MIN_NUM_PAGES - 1 and at most MAX_PAGE_INDEX.

pub fn max_page_erases(&self) -> Nat

The maximum number of times a page can be erased, denoted by E.

We have E <= MAX_ERASE_CYCLE.

pub fn max_key(&self) -> Nat

The maximum key.

pub fn max_updates(&self) -> Nat

The maximum number of updates per transaction.

pub fn virt_page_size(&self) -> Nat

The size of a virtual page in words, denoted by Q.

A virtual page is stored in a physical page after the page header.

We have MIN_PAGE_SIZE - 2 <= Q <= MAX_VIRT_PAGE_SIZE.

pub fn max_value_len(&self) -> Nat

The maximum length in bytes of a user payload.

This is at least MIN_PAGE_SIZE - 3 words and at most MAX_VALUE_LEN.

pub fn max_prefix_len(&self) -> Nat

The maximum prefix length in words, denoted by M.

A prefix is the first words of a virtual page that belong to the last entry of the previous virtual page. This happens because entries may overlap up to 2 virtual pages.

We have MIN_PAGE_SIZE - 3 <= M < Q.

pub fn window_size(&self) -> Nat

The virtual window size in words, denoted by W.

This is the span of virtual storage that is accessible. In particular, all store content fits within this window.

We have W = (N - 1) * Q - M.

pub fn virt_size(&self) -> Nat

The total virtual capacity in words, denoted by V.

This is the span of virtual storage after which we trigger a compaction. This is smaller than the virtual window because compaction may transiently overflow out of this virtual capacity.

We have V = W - (N - 1) = (N - 1) * (Q - 1) - M.

pub fn total_capacity(&self) -> Nat

The total user capacity in words, denoted by C.

We have C = V - N = (N - 1) * (Q - 2) - M - 1.

We can show C >= (N - 2) * (Q - 2) - 2 with the following steps:

• M <= Q - 1 from M < Q from M’s definition
• C >= (N - 1) * (Q - 2) - (Q - 1) - 1 from C’s definition
• C >= (N - 2) * (Q - 2) - 2 by calculus

pub fn total_lifetime(&self) -> Position

The total virtual lifetime in words, denoted by L.

We have L = (E * N + N - 1) * Q.

pub fn page_head(&self, init: InitInfo, page: Nat) -> Position

Returns the word position of the first entry of a page.

pub fn index_init(&self, page: Nat) -> StorageIndex

Returns the storage index of the init info of a page.

pub fn parse_init(&self, word: Word) -> Result<WordState<InitInfo>, Error>

Parses the init info of a page from its storage representation.

pub fn build_init(&self, init: InitInfo) -> Result<WordSlice, Error>

Builds the storage representation of an init info.

pub fn index_compact(&self, page: Nat) -> StorageIndex

Returns the storage index of the compact info of a page.

pub fn parse_compact(&self, word: Word) -> Result<WordState<CompactInfo>, Error>

Parses the compact info of a page from its storage representation.

pub fn build_compact(&self, compact: CompactInfo) -> Result<WordSlice, Error>

Builds the storage representation of a compact info.

pub fn build_internal( &self, internal: InternalEntry, ) -> Result<WordSlice, Error>

Builds the storage representation of an internal entry.

pub fn parse_word(&self, word: Word) -> Result<WordState<ParsedWord>, Error>

Parses the first word of an entry from its storage representation.

pub fn build_user(&self, key: Nat, value: &[u8]) -> Result<Vec<u8>, Error>

Builds the storage representation of a user entry.

pub fn set_padding(&self, word: &mut Word) -> Result<(), Error>

Sets the padding bit in the first word of a user entry.

pub fn set_deleted(&self, word: &mut Word)

Sets the deleted bit in the first word of a user entry.

pub fn transaction_capacity<ByteSlice: Borrow<[u8]>>( &self, updates: &[StoreUpdate<ByteSlice>], ) -> Nat

Returns the capacity required by a transaction.

pub fn entry_size(&self, value: &[u8]) -> Nat

Returns the size of a user entry given its value.

pub fn transaction_valid<ByteSlice: Borrow<[u8]>>( &self, updates: &[StoreUpdate<ByteSlice>], ) -> Option<Vec<Nat>>

Checks if a transaction is valid and returns its sorted keys.

Returns None if the transaction is invalid.

pub fn bytes_to_words(&self, bytes: Nat) -> Nat

Returns the minimum number of words to represent a given number of bytes.

Preconditions

• bytes + Self::word_size does not overflow.

Trait Implementations

impl Clone for Format

fn clone(&self) -> Format

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Format

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

Formats the value using the given formatter.