Trait blart::InnerNode

source · 
pub trait InnerNode: Node {
    type GrownNode: InnerNode<Key = <Self as Node>::Key, Value = <Self as Node>::Value>;
    type ShrunkNode: InnerNode<Key = <Self as Node>::Key, Value = <Self as Node>::Value>;
    type Iter: Iterator<Item = (u8, OpaqueNodePtr<<Self as Node>::Key, <Self as Node>::Value>)> + DoubleEndedIterator + Into<InnerNodeIter<<Self as Node>::Key, <Self as Node>::Value>>;

    // Required methods
    fn lookup_child(
        &self,
        key_fragment: u8
    ) -> Option<OpaqueNodePtr<<Self as Node>::Key, <Self as Node>::Value>>;
    fn write_child(
        &mut self,
        key_fragment: u8,
        child_pointer: OpaqueNodePtr<<Self as Node>::Key, <Self as Node>::Value>
    );
    fn remove_child(
        &mut self,
        key_fragment: u8
    ) -> Option<OpaqueNodePtr<<Self as Node>::Key, <Self as Node>::Value>>;
    fn grow(&self) -> Self::GrownNode;
    fn shrink(&self) -> Self::ShrunkNode;
    fn header(&self) -> &Header;
    fn header_mut(&mut self) -> &mut Header;
    unsafe fn iter(&self) -> Self::Iter;
    fn split_at(&mut self, key_fragment: u8) -> Self;
    fn num_children_after_split(&self, key_fragment: u8) -> (usize, usize);

    // Provided method
    fn is_full(&self) -> bool { ... }
}
Expand description

Common methods implemented by all inner node.

Required Associated Types§

source

type GrownNode: InnerNode<Key = <Self as Node>::Key, Value = <Self as Node>::Value>

The type of the next larger node type.

source

type ShrunkNode: InnerNode<Key = <Self as Node>::Key, Value = <Self as Node>::Value>

The type of the next smaller node type.

source

type Iter: Iterator<Item = (u8, OpaqueNodePtr<<Self as Node>::Key, <Self as Node>::Value>)> + DoubleEndedIterator + Into<InnerNodeIter<<Self as Node>::Key, <Self as Node>::Value>>

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

Required Methods§

source

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

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

source

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

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.

source

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

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.

source

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

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

source

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.

source

fn header(&self) -> &Header

Access the header information for this node.

source

fn header_mut(&mut self) -> &mut Header

Access the header information for this node.

source

unsafe fn iter(&self) -> Self::Iter

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

Safety

The iterator type does not carry any lifetime, so the caller of this function must enforce that the lifetime of the iterator does not overlap with any mutating operations on the node.

source

fn split_at(&mut self, key_fragment: u8) -> Self

Split the inner node at the given key-byte, returning a new InnerNode of the same type that contains all children including and after the given key fragment. The original inner node has those children removed.

The header key prefix is duplicated to the new split-off node.

source

fn num_children_after_split(&self, key_fragment: u8) -> (usize, usize)

This function will count the number of children before and after the split point.

Similar to the split_at function, the first count is the number of children which have a key fragment less than the given one. The second count is the number of children which has a key fragment greater than or equal to the given one.

The sum of the first and second integers must be equal to the total number of children (self.header().num_children()).

Provided Methods§

source

fn is_full(&self) -> bool

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

Implementors§