Struct PATCH 

pub struct PATCH<const KEY_LEN: usize, O = IdentitySchema, V = ()>
where
    O: KeySchema<KEY_LEN>,
{ /* private fields */ }

A PATCH is a persistent data structure that stores a set of keys. Each key can be reordered and segmented, based on the provided key ordering and segmentation.

The patch supports efficient set operations, like union, intersection, and difference, because it efficiently maintains a hash for all keys that are part of a sub-tree.

The tree itself is a path- and node-compressed a 256-ary trie. Each nodes stores its children in a byte oriented cuckoo hash table, allowing for O(1) access to children, while keeping the memory overhead low. Table sizes are powers of two, starting at 2.

Having a single node type for all branching factors simplifies the implementation, compared to other adaptive trie implementations, like ARTs or Judy Arrays

The PATCH allows for cheap copy-on-write operations, with clone being O(1).

Implementations

impl<const KEY_LEN: usize, O, V> PATCH<KEY_LEN, O, V>

where O: KeySchema<KEY_LEN>,

pub fn new() -> Self

Creates a new empty PATCH.

pub fn insert(&mut self, entry: &Entry<KEY_LEN, V>)

Inserts a shared key into the PATCH.

Takes an Entry object that can be created from a key, and inserted into multiple PATCH instances.

If the key is already present, this is a no-op.

pub fn replace(&mut self, entry: &Entry<KEY_LEN, V>)

Inserts a key into the PATCH, replacing the value if it already exists.

pub fn remove(&mut self, key: &[u8; KEY_LEN])

Removes a key from the PATCH.

If the key is not present, this is a no-op.

pub fn len(&self) -> u64

Returns the number of keys in the PATCH.

pub fn is_empty(&self) -> bool

Returns true if the PATCH contains no keys.

pub fn get(&self, key: &[u8; KEY_LEN]) -> Option<&V>

Returns the value associated with key if present.

pub fn infixes<const PREFIX_LEN: usize, const INFIX_LEN: usize, F>( &self, prefix: &[u8; PREFIX_LEN], for_each: F, )

where F: FnMut(&[u8; INFIX_LEN]),

Allows iteratig over all infixes of a given length with a given prefix. Each infix is passed to the provided closure.

The entire operation is performed over the tree view ordering of the keys.

The length of the prefix and the infix is provided as type parameters, but will usually inferred from the arguments.

The sum of PREFIX_LEN and INFIX_LEN must be less than or equal to KEY_LEN or a compile-time assertion will fail.

Because all infixes are iterated in one go, less bookkeeping is required, than when using an Iterator, allowing for better performance.

pub fn has_prefix<const PREFIX_LEN: usize>( &self, prefix: &[u8; PREFIX_LEN], ) -> bool

Returns true if the PATCH has a key with the given prefix.

PREFIX_LEN must be less than or equal to KEY_LEN or a compile-time assertion will fail.

pub fn segmented_len<const PREFIX_LEN: usize>( &self, prefix: &[u8; PREFIX_LEN], ) -> u64

Returns the number of unique segments in keys with the given prefix.

pub fn iter<'a>(&'a self) -> PATCHIterator<'a, KEY_LEN, O, V>

Iterates over all keys in the PATCH. The keys are returned in key ordering but random order.

pub fn iter_ordered<'a>(&'a self) -> PATCHOrderedIterator<'a, KEY_LEN, O, V>

Iterates over all keys in the PATCH in key order.

The traversal visits every key in lexicographic key order, without accepting a prefix filter. For prefix-aware iteration, see PATCH::iter_prefix_count.

pub fn iter_prefix_count<'a, const PREFIX_LEN: usize>( &'a self, ) -> PATCHPrefixIterator<'a, KEY_LEN, PREFIX_LEN, O, V>

Iterate over all prefixes of the given length in the PATCH. The prefixes are naturally returned in tree ordering and tree order. A count of the number of elements for the given prefix is also returned.

pub fn union(&mut self, other: Self)

Unions this PATCH with another PATCH.

The other PATCH is consumed, and this PATCH is updated in place.

pub fn intersect(&self, other: &Self) -> Self

Intersects this PATCH with another PATCH.

Returns a new PATCH that contains only the keys that are present in both PATCHes.

pub fn difference(&self, other: &Self) -> Self

Returns the difference between this PATCH and another PATCH.

Returns a new PATCH that contains only the keys that are present in this PATCH, but not in the other PATCH.

pub fn debug_branch_fill(&self) -> [f32; 8]

Calculates the average fill level for branch nodes grouped by their branching factor. The returned array contains eight entries for branch sizes 2, 4, 8, 16, 32, 64, 128 and 256 in that order.

impl<const KEY_LEN: usize, O: KeySchema<KEY_LEN>, V> PATCH<KEY_LEN, O, V>

pub fn into_iter_ordered(self) -> PATCHIntoOrderedIterator<KEY_LEN, O, V>

Consume and return an iterator that yields keys in key order.

Trait Implementations

impl<const KEY_LEN: usize, O, V> Clone for PATCH<KEY_LEN, O, V>

where O: KeySchema<KEY_LEN>,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<'a, S: ValueSchema> ContainsConstraint<'a, S> for &'a PATCH<VALUE_LEN, IdentitySchema, ()>

type Constraint = PatchValueConstraint<'a, S>

The concrete constraint type produced by has.

fn has(self, v: Variable<S>) -> Self::Constraint

Create a constraint that filters the values assigned to the variable to only those that are contained in the collection.

impl<'a, S: ValueSchema> ContainsConstraint<'a, S> for PATCH<ID_LEN, IdentitySchema, ()>

type Constraint = PatchIdConstraint<S>

The concrete constraint type produced by has.

fn has(self, v: Variable<S>) -> Self::Constraint

Create a constraint that filters the values assigned to the variable to only those that are contained in the collection.

impl<const KEY_LEN: usize, O, V: Debug> Debug for PATCH<KEY_LEN, O, V>

where O: KeySchema<KEY_LEN> + Debug,

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

Formats the value using the given formatter.

impl<const KEY_LEN: usize, O, V> Default for PATCH<KEY_LEN, O, V>

where O: KeySchema<KEY_LEN>,

fn default() -> Self

Returns the “default value” for a type.

impl<'a, const KEY_LEN: usize, O, V> IntoIterator for &'a PATCH<KEY_LEN, O, V>

where O: KeySchema<KEY_LEN>,

type Item = &'a [u8; KEY_LEN]

The type of the elements being iterated over.

type IntoIter = PATCHIterator<'a, KEY_LEN, O, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<const KEY_LEN: usize, O: KeySchema<KEY_LEN>, V> IntoIterator for PATCH<KEY_LEN, O, V>

type Item = [u8; KEY_LEN]

The type of the elements being iterated over.

type IntoIter = PATCHIntoIterator<KEY_LEN, O, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<const KEY_LEN: usize, O, V> PartialEq for PATCH<KEY_LEN, O, V>

where O: KeySchema<KEY_LEN>,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<const KEY_LEN: usize, O, V> Eq for PATCH<KEY_LEN, O, V>

where O: KeySchema<KEY_LEN>,