Struct Handle

pub(super) struct Handle<Node, Type> {
    node: Node,
    idx: usize,
    _marker: PhantomData<Type>,
}

A reference to a specific key-value pair or edge within a node. The Node parameter must be a NodeRef, while the Type can either be KV (signifying a handle on a key-value pair) or Edge (signifying a handle on an edge).

Note that even Leaf nodes can have Edge handles. Instead of representing a pointer to a child node, these represent the spaces where child pointers would go between the key-value pairs. For example, in a node with length 2, there would be 3 possible edge locations - one to the left of the node, one between the two pairs, and one at the right of the node.

Fields

node: Node

idx: usize

_marker: PhantomData<Type>

Implementations

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, KV>

fn fix_left_border_of_left_edge<A: Allocator + Clone>(self, alloc: A)

fn fix_right_border_of_right_edge<A: Allocator + Clone>(self, alloc: A)

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>

fn fix_left_child<A: Allocator + Clone>( self, alloc: A, ) -> NodeRef<Mut<'a>, K, V, LeafOrInternal>

Stocks up the left child, assuming the right child isn’t underfull, and provisions an extra element to allow merging its children in turn without becoming underfull. Returns the left child.

fn fix_right_child<A: Allocator + Clone>( self, alloc: A, ) -> NodeRef<Mut<'a>, K, V, LeafOrInternal>

Stocks up the right child, assuming the left child isn’t underfull, and provisions an extra element to allow merging its children in turn without becoming underfull. Returns wherever the right child ended up.

impl<BorrowType: BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>

pub(super) fn next_kv( self, ) -> Result<Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, KV>, NodeRef<BorrowType, K, V, LeafOrInternal>>

Given a leaf edge handle, returns Result::Ok with a handle to the neighboring KV on the right side, which is either in the same leaf node or in an ancestor node. If the leaf edge is the last one in the tree, returns Result::Err with the root node.

pub(super) fn next_back_kv( self, ) -> Result<Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, KV>, NodeRef<BorrowType, K, V, LeafOrInternal>>

Given a leaf edge handle, returns Result::Ok with a handle to the neighboring KV on the left side, which is either in the same leaf node or in an ancestor node. If the leaf edge is the first one in the tree, returns Result::Err with the root node.

impl<BorrowType: BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Internal>, Edge>

fn next_kv( self, ) -> Result<Handle<NodeRef<BorrowType, K, V, Internal>, KV>, NodeRef<BorrowType, K, V, Internal>>

Given an internal edge handle, returns Result::Ok with a handle to the neighboring KV on the right side, which is either in the same internal node or in an ancestor node. If the internal edge is the last one in the tree, returns Result::Err with the root node.

impl<K, V> Handle<NodeRef<Dying, K, V, Leaf>, Edge>

unsafe fn deallocating_next<A: Allocator + Clone>( self, alloc: A, ) -> Option<(Self, Handle<NodeRef<Dying, K, V, LeafOrInternal>, KV>)>

Given a leaf edge handle into a dying tree, returns the next leaf edge on the right side, and the key-value pair in between, if they exist.

If the given edge is the last one in a leaf, this method deallocates the leaf, as well as any ancestor nodes whose last edge was reached. This implies that if no more key-value pair follows, the entire tree will have been deallocated and there is nothing left to return.

Safety

• The given edge must not have been previously returned by counterpart deallocating_next_back.
• The returned KV handle is only valid to access the key and value, and only valid until the next call to a deallocating_ method.

unsafe fn deallocating_next_back<A: Allocator + Clone>( self, alloc: A, ) -> Option<(Self, Handle<NodeRef<Dying, K, V, LeafOrInternal>, KV>)>

Given a leaf edge handle into a dying tree, returns the next leaf edge on the left side, and the key-value pair in between, if they exist.

If the given edge is the first one in a leaf, this method deallocates the leaf, as well as any ancestor nodes whose first edge was reached. This implies that if no more key-value pair follows, the entire tree will have been deallocated and there is nothing left to return.

Safety

• The given edge must not have been previously returned by counterpart deallocating_next.
• The returned KV handle is only valid to access the key and value, and only valid until the next call to a deallocating_ method.

fn deallocating_end<A: Allocator + Clone>(self, alloc: A)

Deallocates a pile of nodes from the leaf up to the root. This is the only way to deallocate the remainder of a tree after deallocating_next and deallocating_next_back have been nibbling at both sides of the tree, and have hit the same edge. As it is intended only to be called when all keys and values have been returned, no cleanup is done on any of the keys or values.

impl<'a, K, V> Handle<NodeRef<Immut<'a>, K, V, Leaf>, Edge>

unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V)

Moves the leaf edge handle to the next leaf edge and returns references to the key and value in between.

Safety

There must be another KV in the direction travelled.

unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V)

Moves the leaf edge handle to the previous leaf edge and returns references to the key and value in between.

Safety

There must be another KV in the direction travelled.

impl<'a, K, V> Handle<NodeRef<ValMut<'a>, K, V, Leaf>, Edge>

unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V)

Moves the leaf edge handle to the next leaf edge and returns references to the key and value in between.

Safety

There must be another KV in the direction travelled.

unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V)

Moves the leaf edge handle to the previous leaf and returns references to the key and value in between.

Safety

There must be another KV in the direction travelled.

impl<K, V> Handle<NodeRef<Dying, K, V, Leaf>, Edge>

unsafe fn deallocating_next_unchecked<A: Allocator + Clone>( &mut self, alloc: A, ) -> Handle<NodeRef<Dying, K, V, LeafOrInternal>, KV>

Moves the leaf edge handle to the next leaf edge and returns the key and value in between, deallocating any node left behind while leaving the corresponding edge in its parent node dangling.

Safety

• There must be another KV in the direction travelled.
• That KV was not previously returned by counterpart deallocating_next_back_unchecked on any copy of the handles being used to traverse the tree.

The only safe way to proceed with the updated handle is to compare it, drop it, or call this method or counterpart deallocating_next_back_unchecked again.

unsafe fn deallocating_next_back_unchecked<A: Allocator + Clone>( &mut self, alloc: A, ) -> Handle<NodeRef<Dying, K, V, LeafOrInternal>, KV>

Moves the leaf edge handle to the previous leaf edge and returns the key and value in between, deallocating any node left behind while leaving the corresponding edge in its parent node dangling.

Safety

• There must be another KV in the direction travelled.
• That leaf edge was not previously returned by counterpart deallocating_next_unchecked on any copy of the handles being used to traverse the tree.

The only safe way to proceed with the updated handle is to compare it, drop it, or call this method or counterpart deallocating_next_unchecked again.

impl<BorrowType: BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, KV>

pub(super) fn next_leaf_edge( self, ) -> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>

Returns the leaf edge closest to a KV for forward navigation.

pub(super) fn next_back_leaf_edge( self, ) -> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>

Returns the leaf edge closest to a KV for backward navigation.

impl<Node, Type> Handle<Node, Type>

pub(super) fn into_node(self) -> Node

Retrieves the node that contains the edge or key-value pair this handle points to.

pub(super) fn idx(&self) -> usize

Returns the position of this handle in the node.

impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, KV>

pub(super) unsafe fn new_kv( node: NodeRef<BorrowType, K, V, NodeType>, idx: usize, ) -> Self

Creates a new handle to a key-value pair in node. Unsafe because the caller must ensure that idx < node.len().

pub(super) fn left_edge( self, ) -> Handle<NodeRef<BorrowType, K, V, NodeType>, Edge>

pub(super) fn right_edge( self, ) -> Handle<NodeRef<BorrowType, K, V, NodeType>, Edge>

impl<BorrowType, K, V, NodeType, HandleType> Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>

pub(super) fn reborrow( &self, ) -> Handle<NodeRef<Immut<'_>, K, V, NodeType>, HandleType>

Temporarily takes out another immutable handle on the same location.

impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<Mut<'a>, K, V, NodeType>, HandleType>

pub(super) unsafe fn reborrow_mut( &mut self, ) -> Handle<NodeRef<Mut<'_>, K, V, NodeType>, HandleType>

Temporarily takes out another mutable handle on the same location. Beware, as this method is very dangerous, doubly so since it might not immediately appear dangerous.

For details, see NodeRef::reborrow_mut.

pub(super) fn dormant( &self, ) -> Handle<NodeRef<DormantMut, K, V, NodeType>, HandleType>

Returns a dormant copy of this handle which can be reawakened later.

See DormantMutRef for more details.

impl<K, V, NodeType, HandleType> Handle<NodeRef<DormantMut, K, V, NodeType>, HandleType>

pub(super) unsafe fn awaken<'a>( self, ) -> Handle<NodeRef<Mut<'a>, K, V, NodeType>, HandleType>

Revert to the unique borrow initially captured.

Safety

The reborrow must have ended, i.e., the reference returned by new and all pointers and references derived from it, must not be used anymore.

impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, Edge>

pub(super) unsafe fn new_edge( node: NodeRef<BorrowType, K, V, NodeType>, idx: usize, ) -> Self

Creates a new handle to an edge in node. Unsafe because the caller must ensure that idx <= node.len().

pub(super) fn left_kv( self, ) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, KV>, Self>

pub(super) fn right_kv( self, ) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, KV>, Self>

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>

unsafe fn insert_fit( self, key: K, val: V, ) -> Handle<NodeRef<Mut<'a>, K, V, Leaf>, KV>

Inserts a new key-value pair between the key-value pairs to the right and left of this edge. This method assumes that there is enough space in the node for the new pair to fit.

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>

fn insert<A: Allocator + Clone>( self, key: K, val: V, alloc: A, ) -> (Option<SplitResult<'a, K, V, Leaf>>, Handle<NodeRef<DormantMut, K, V, Leaf>, KV>)

Inserts a new key-value pair between the key-value pairs to the right and left of this edge. This method splits the node if there isn’t enough room.

Returns a dormant handle to the inserted node which can be reawakened once splitting is complete.

impl<'a, K, V> Handle<NodeRef<Mut<'a>, K, V, Internal>, Edge>

fn correct_parent_link(self)

Fixes the parent pointer and index in the child node that this edge links to. This is useful when the ordering of edges has been changed,

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, Edge>

fn insert_fit( &mut self, key: K, val: V, edge: NodeRef<Owned, K, V, LeafOrInternal>, )

Inserts a new key-value pair and an edge that will go to the right of that new pair between this edge and the key-value pair to the right of this edge. This method assumes that there is enough space in the node for the new pair to fit.

fn insert<A: Allocator + Clone>( self, key: K, val: V, edge: NodeRef<Owned, K, V, LeafOrInternal>, alloc: A, ) -> Option<SplitResult<'a, K, V, Internal>>

Inserts a new key-value pair and an edge that will go to the right of that new pair between this edge and the key-value pair to the right of this edge. This method splits the node if there isn’t enough room.

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>

pub(super) fn insert_recursing<A: Allocator + Clone>( self, key: K, value: V, alloc: A, split_root: impl FnOnce(SplitResult<'a, K, V, LeafOrInternal>), ) -> Handle<NodeRef<Mut<'a>, K, V, Leaf>, KV>

Inserts a new key-value pair between the key-value pairs to the right and left of this edge. This method splits the node if there isn’t enough room, and tries to insert the split off portion into the parent node recursively, until the root is reached.

If the returned result is some SplitResult, the left field will be the root node. The returned pointer points to the inserted value, which in the case of SplitResult is in the left or right tree.

impl<BorrowType: BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Internal>, Edge>

pub(super) fn descend(self) -> NodeRef<BorrowType, K, V, LeafOrInternal>

Finds the node pointed to by this edge.

The method name assumes you picture trees with the root node on top.

edge.descend().ascend().unwrap() and node.ascend().unwrap().descend() should both, upon success, do nothing.

impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<Immut<'a>, K, V, NodeType>, KV>

pub(super) fn into_kv(self) -> (&'a K, &'a V)

impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<Mut<'a>, K, V, NodeType>, KV>

pub(super) fn key_mut(&mut self) -> &mut K

pub(super) fn into_val_mut(self) -> &'a mut V

pub(super) fn into_kv_mut(self) -> (&'a mut K, &'a mut V)

impl<'a, K, V, NodeType> Handle<NodeRef<ValMut<'a>, K, V, NodeType>, KV>

pub(super) fn into_kv_valmut(self) -> (&'a K, &'a mut V)

impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<Mut<'a>, K, V, NodeType>, KV>

pub(super) fn kv_mut(&mut self) -> (&mut K, &mut V)

pub(super) fn replace_kv(&mut self, k: K, v: V) -> (K, V)

Replaces the key and value that the KV handle refers to.

impl<K, V, NodeType> Handle<NodeRef<Dying, K, V, NodeType>, KV>

pub(super) unsafe fn into_key_val(self) -> (K, V)

Extracts the key and value that the KV handle refers to.

Safety

The node that the handle refers to must not yet have been deallocated.

pub(super) unsafe fn drop_key_val(self)

Drops the key and value that the KV handle refers to.

Safety

The node that the handle refers to must not yet have been deallocated.

impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<Mut<'a>, K, V, NodeType>, KV>

fn split_leaf_data(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V)

Helps implementations of split for a particular NodeType, by taking care of leaf data.

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Leaf>, KV>

pub(super) fn split<A: Allocator + Clone>( self, alloc: A, ) -> SplitResult<'a, K, V, Leaf>

Splits the underlying node into three parts:

• The node is truncated to only contain the key-value pairs to the left of this handle.
• The key and value pointed to by this handle are extracted.
• All the key-value pairs to the right of this handle are put into a newly allocated node.

pub(super) fn remove( self, ) -> ((K, V), Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>)

Removes the key-value pair pointed to by this handle and returns it, along with the edge that the key-value pair collapsed into.

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>

pub(super) fn split<A: Allocator + Clone>( self, alloc: A, ) -> SplitResult<'a, K, V, Internal>

Splits the underlying node into three parts:

• The node is truncated to only contain the edges and key-value pairs to the left of this handle.
• The key and value pointed to by this handle are extracted.
• All the edges and key-value pairs to the right of this handle are put into a newly allocated node.

impl<'a, K, V> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>

pub(super) fn consider_for_balancing(self) -> BalancingContext<'a, K, V>

impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>

pub(super) fn forget_node_type( self, ) -> Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, Edge>

impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Internal>, Edge>

pub(super) fn forget_node_type( self, ) -> Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, Edge>

impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Leaf>, KV>

pub(super) fn forget_node_type( self, ) -> Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, KV>

impl<BorrowType, K, V, Type> Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, Type>

pub(super) fn force( self, ) -> ForceResult<Handle<NodeRef<BorrowType, K, V, Leaf>, Type>, Handle<NodeRef<BorrowType, K, V, Internal>, Type>>

Checks whether the underlying node is an Internal node or a Leaf node.

impl<'a, K, V, Type> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, Type>

pub(super) unsafe fn cast_to_leaf_unchecked( self, ) -> Handle<NodeRef<Mut<'a>, K, V, Leaf>, Type>

Unsafely asserts to the compiler the static information that the handle’s node is a Leaf.

impl<'a, K, V> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, Edge>

pub(super) fn move_suffix( &mut self, right: &mut NodeRef<Mut<'a>, K, V, LeafOrInternal>, )

Move the suffix after self from one node to another one. right must be empty. The first edge of right remains unchanged.

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, KV>

pub(super) fn remove_kv_tracking<F: FnOnce(), A: Allocator + Clone>( self, handle_emptied_internal_root: F, alloc: A, ) -> ((K, V), Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>)

Removes a key-value pair from the tree, and returns that pair, as well as the leaf edge corresponding to that former pair. It’s possible this empties a root node that is internal, which the caller should pop from the map holding the tree. The caller should also decrement the map’s length.

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Leaf>, KV>

fn remove_leaf_kv<F: FnOnce(), A: Allocator + Clone>( self, handle_emptied_internal_root: F, alloc: A, ) -> ((K, V), Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>)

impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>

fn remove_internal_kv<F: FnOnce(), A: Allocator + Clone>( self, handle_emptied_internal_root: F, alloc: A, ) -> ((K, V), Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>)

Trait Implementations

impl<Node: Copy, Type> Clone for Handle<Node, Type>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<BorrowType, K, V, NodeType, HandleType> PartialEq for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>

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<Node: Copy, Type> Copy for Handle<Node, Type>