pub struct Handle<Node, Type> {
    node: Node,
    idx: usize,
    _marker: PhantomData<Type>,
}
Expand description

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§

source§

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

source§

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

source

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.

source

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.

source§

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

source

pub 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.

source

pub 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.

source§

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

source

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.

source§

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

source

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.
source

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.
source

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.

source§

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

source

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.

source

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.

source§

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

source

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.

source

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.

source§

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

source

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.

source

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.

source§

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

source

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

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

source

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

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

source§

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

source

pub fn into_node(self) -> Node

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

source

pub fn idx(&self) -> usize

Returns the position of this handle in the node.

source§

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

source

pub 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().

source

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

source

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

source§

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

source

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

Temporarily takes out another immutable handle on the same location.

source§

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

source

pub 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.

source

pub 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.

source§

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

source

pub 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.

source§

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

source

pub 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().

source

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

source

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

source§

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

source

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.

source§

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

source

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.

source§

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

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,

source§

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

source

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.

source

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.

source§

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

source

pub 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.

source§

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

source

pub 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.

source§

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

source

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

source§

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

source

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

source

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

source

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

source§

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

source§

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

source

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

source

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

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

source§

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

source

pub 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.

source

pub 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.

source§

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

source

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.

source§

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

source

pub 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.
source

pub 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.

source§

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

source

pub 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.
source§

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

source§

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

source

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

source§

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

source

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

source§

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

source

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

source§

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

source

pub 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.

source§

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

source

pub 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.

source§

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

source

pub 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.

source§

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

source

pub 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.

source§

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

source

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>)

source§

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

source

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§

source§

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

source§

fn clone(&self) -> Self

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

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

source§

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

This method tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

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

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

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

Auto Trait Implementations§

§

impl<Node, Type> RefUnwindSafe for Handle<Node, Type>where Node: RefUnwindSafe, Type: RefUnwindSafe,

§

impl<Node, Type> Send for Handle<Node, Type>where Node: Send, Type: Send,

§

impl<Node, Type> Sync for Handle<Node, Type>where Node: Sync, Type: Sync,

§

impl<Node, Type> Unpin for Handle<Node, Type>where Node: Unpin, Type: Unpin,

§

impl<Node, Type> UnwindSafe for Handle<Node, Type>where Node: UnwindSafe, Type: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<T> NonDrop for Twhere T: Copy,