Trait InnerNode

pub trait InnerNode<const PREFIX_LEN: usize>:
    Node<PREFIX_LEN>
    + Sized
    + Debug {
    type GrownNode: InnerNode<PREFIX_LEN, Key = Self::Key, Value = Self::Value>;
    type ShrunkNode: InnerNode<PREFIX_LEN, Key = Self::Key, Value = Self::Value>;
    type Iter<'a>: Iterator<Item = (u8, OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>)> + DoubleEndedIterator + FusedIterator
       where Self: 'a;

    // Required methods
    fn from_header(header: Header<PREFIX_LEN>) -> Self;
    fn header(&self) -> &Header<PREFIX_LEN>;
    fn lookup_child(
        &self,
        key_fragment: u8,
    ) -> Option<OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>>;
    fn write_child(
        &mut self,
        key_fragment: u8,
        child_pointer: OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>,
    );
    fn remove_child(
        &mut self,
        key_fragment: u8,
    ) -> Option<OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>>;
    fn grow(&self) -> Self::GrownNode;
    fn shrink(&self) -> Self::ShrunkNode;
    fn iter(&self) -> Self::Iter<'_>;
    fn range(
        &self,
        bound: impl RangeBounds<u8>,
    ) -> impl DoubleEndedIterator<Item = (u8, OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>)> + FusedIterator;
    fn min(&self) -> (u8, OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>);
    fn max(&self) -> (u8, OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>);

    // Provided methods
    fn empty() -> Self { ... }
    fn from_prefix(prefix: &[u8], prefix_len: usize) -> Self { ... }
    fn is_full(&self) -> bool { ... }
    fn optimistic_match_prefix(
        &self,
        truncated_key: &[u8],
    ) -> Result<PrefixMatch, OptimisticMismatch> { ... }
    fn attempt_pessimistic_match_prefix(
        &self,
        truncated_key: &[u8],
    ) -> Result<AttemptOptimisticPrefixMatch, PessimisticMismatch> { ... }
    fn match_full_prefix(
        &self,
        key: &[u8],
        current_depth: usize,
    ) -> Result<PrefixMatch, ExplicitMismatch<Self::Key, Self::Value, PREFIX_LEN>>
       where Self::Key: AsBytes { ... }
    fn read_full_prefix(
        &self,
        current_depth: usize,
    ) -> (&[u8], Option<NodePtr<PREFIX_LEN, LeafNode<Self::Key, Self::Value, PREFIX_LEN>>>)
       where Self::Key: AsBytes { ... }
}

Common methods implemented by all inner node.

Required Associated Types

type GrownNode: InnerNode<PREFIX_LEN, Key = Self::Key, Value = Self::Value>

The type of the next larger node type.

type ShrunkNode: InnerNode<PREFIX_LEN, Key = Self::Key, Value = Self::Value>

The type of the next smaller node type.

type Iter<'a>: Iterator<Item = (u8, OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>)> + DoubleEndedIterator + FusedIterator where Self: 'a

The type of the iterator over all children of the inner node

Required Methods

fn from_header(header: Header<PREFIX_LEN>) -> Self

Create a new InnerNode using a Header

fn header(&self) -> &Header<PREFIX_LEN>

Get the Header from the InnerNode

fn lookup_child( &self, key_fragment: u8, ) -> Option<OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>>

Search through this node for a child node that corresponds to the given key fragment.

fn write_child( &mut self, key_fragment: u8, child_pointer: OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>, )

Write a child pointer with key fragment to this inner node.

If the key fragment already exists in the node, overwrite the existing child pointer.

Panics

• Panics when the node is full.

fn remove_child( &mut self, key_fragment: u8, ) -> Option<OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>>

Attempt to remove a child pointer at the key fragment from this inner node.

If the key fragment does not exist in this node, return None.

fn grow(&self) -> Self::GrownNode

Grow this node into the next larger class, copying over children and prefix information.

fn shrink(&self) -> Self::ShrunkNode

Shrink this node into the next smaller class, copying over children and prefix information.

Panics

• Panics if the new, smaller node size does not have enough capacity to hold all the children.

fn iter(&self) -> Self::Iter<'_>

Create an iterator over all (key bytes, child pointers) in this inner node.

fn range( &self, bound: impl RangeBounds<u8>, ) -> impl DoubleEndedIterator<Item = (u8, OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>)> + FusedIterator

Create an iterator over a subset of (key bytes, child pointers), using the given bound as a restriction on the set of key bytes.

fn min(&self) -> (u8, OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>)

Returns the minimum child pointer from this node and it’s key

Safety

• Since this is a InnerNode we assume that the we have at least one child, (more strictly we have 2, because with one child the node would have collapsed) so in this way we can avoid the Option. This is safe because if we had no children this current node should have been deleted.

fn max(&self) -> (u8, OpaqueNodePtr<Self::Key, Self::Value, PREFIX_LEN>)

Returns the maximum child pointer from this node and it’s key

Safety

• Since this is a InnerNode we assume that the we have at least one child, (more strictly we have 2, because with one child the node would have collapsed) so in this way we can avoid the Option. This is safe because if we had, no children this current node should have been deleted.

Provided Methods

fn empty() -> Self

Create an empty InnerNode, with no children and no prefix

fn from_prefix(prefix: &[u8], prefix_len: usize) -> Self

Create a new InnerNode using prefix as the node prefix and prefix_len as the node prefix length and

This is done because when a prefix mismatch happens the length of the mismatch can be grater or equal to prefix size, since we search for the first child of the node to recreate the prefix, that’s why we don’t use prefix.len() as the node prefix length

fn is_full(&self) -> bool

Returns true if this node has no more space to store children.

fn optimistic_match_prefix( &self, truncated_key: &[u8], ) -> Result<PrefixMatch, OptimisticMismatch>

Test the given key against the inner node header prefix by checking that the key length is greater than or equal to the length of the header prefix.

The truncated_key argument should be the overall key bytes shortened to the current depth.

This is called “optimistic” matching, because it assumes that there will not be a mismatch in the contents of the header prefix when compared to the key. The caller who uses this function must perform a final check against the leaf key bytes to make sure that the search key matches the found key.

fn attempt_pessimistic_match_prefix( &self, truncated_key: &[u8], ) -> Result<AttemptOptimisticPrefixMatch, PessimisticMismatch>

Test the given key against the inner node header prefix by comparing the bytes.

The truncated_key argument should be the overall key bytes shortened to the current depth.

If the length of the header prefix is greater than the number of bytes stored (there are implicit bytes), then this falls back to using optimistic_match_prefix.

If this function fell into that condition, then the any_implicit_bytes flag will be set to true in the Ok case and prefix_byte will be set to None in the Err case.

If either of those conditions are true, and the caller of this function reaches a leaf node using these results, then the caller must perform a final check against the leaf key bytes to make sure that the search key matches the found key.

fn match_full_prefix( &self, key: &[u8], current_depth: usize, ) -> Result<PrefixMatch, ExplicitMismatch<Self::Key, Self::Value, PREFIX_LEN>>

where Self::Key: AsBytes,

Compares the compressed path of a node with the key and returns the number of equal bytes.

This function will read the full prefix for this inner node, even if it needs to search a descendant leaf node to find implicit bytes.

Safety

• current_depth > key len

fn read_full_prefix( &self, current_depth: usize, ) -> (&[u8], Option<NodePtr<PREFIX_LEN, LeafNode<Self::Key, Self::Value, PREFIX_LEN>>>)

where Self::Key: AsBytes,

Read the prefix as a whole, by reconstructing it if necessary from a leaf

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<K, V, const PREFIX_LEN: usize> InnerNode<PREFIX_LEN> for InnerNode48<K, V, PREFIX_LEN>

type GrownNode = InnerNode256<K, V, PREFIX_LEN>

type Iter<'a> = Map<FilterMap<Enumerate<Iter<'a, RestrictedNodeIndex<48>>>, impl FnMut((usize, &'a RestrictedNodeIndex<48>))>, impl FnMut((u8, usize))> where Self: 'a

type ShrunkNode = InnerNodeCompressed<K, V, PREFIX_LEN, 16>

impl<K, V, const PREFIX_LEN: usize> InnerNode<PREFIX_LEN> for InnerNode256<K, V, PREFIX_LEN>

type GrownNode = InnerNode256<K, V, PREFIX_LEN>

type Iter<'a> = FilterMap<Enumerate<Iter<'a, Option<OpaqueNodePtr<K, V, PREFIX_LEN>>>>, impl FnMut((usize, &'a Option<OpaqueNodePtr<K, V, PREFIX_LEN>>))> where Self: 'a

type ShrunkNode = InnerNode48<K, V, PREFIX_LEN>

impl<K, V, const PREFIX_LEN: usize> InnerNode<PREFIX_LEN> for InnerNode4<K, V, PREFIX_LEN>

type GrownNode = InnerNodeCompressed<K, V, PREFIX_LEN, 16>

type Iter<'a> = Zip<Copied<Iter<'a, u8>>, Copied<Iter<'a, OpaqueNodePtr<K, V, PREFIX_LEN>>>> where Self: 'a

type ShrunkNode = InnerNodeCompressed<K, V, PREFIX_LEN, 4>

impl<K, V, const PREFIX_LEN: usize> InnerNode<PREFIX_LEN> for InnerNode16<K, V, PREFIX_LEN>

type GrownNode = InnerNode48<K, V, PREFIX_LEN>

type Iter<'a> = Zip<Copied<Iter<'a, u8>>, Copied<Iter<'a, OpaqueNodePtr<K, V, PREFIX_LEN>>>> where Self: 'a

type ShrunkNode = InnerNodeCompressed<K, V, PREFIX_LEN, 4>