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>
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)
source§impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>
impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>
sourcefn fix_left_child<A: Allocator + Clone>(
self,
alloc: A
) -> NodeRef<Mut<'a>, K, V, LeafOrInternal>
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.
sourcefn fix_right_child<A: Allocator + Clone>(
self,
alloc: A
) -> NodeRef<Mut<'a>, K, V, LeafOrInternal>
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>
impl<BorrowType: BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>
sourcepub fn next_kv(
self
) -> Result<Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, KV>, NodeRef<BorrowType, K, V, LeafOrInternal>>
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.
sourcepub fn next_back_kv(
self
) -> Result<Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, KV>, NodeRef<BorrowType, K, V, LeafOrInternal>>
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>
impl<BorrowType: BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Internal>, Edge>
sourcefn next_kv(
self
) -> Result<Handle<NodeRef<BorrowType, K, V, Internal>, KV>, NodeRef<BorrowType, K, V, Internal>>
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>
impl<K, V> Handle<NodeRef<Dying, K, V, Leaf>, Edge>
sourceunsafe fn deallocating_next<A: Allocator + Clone>(
self,
alloc: A
) -> Option<(Self, Handle<NodeRef<Dying, K, V, LeafOrInternal>, KV>)>
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.
sourceunsafe fn deallocating_next_back<A: Allocator + Clone>(
self,
alloc: A
) -> Option<(Self, Handle<NodeRef<Dying, K, V, LeafOrInternal>, KV>)>
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.
sourcefn deallocating_end<A: Allocator + Clone>(self, alloc: A)
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>
impl<'a, K, V> Handle<NodeRef<Immut<'a>, K, V, Leaf>, Edge>
sourceunsafe fn next_unchecked(&mut self) -> (&'a K, &'a V)
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.
sourceunsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V)
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>
impl<'a, K, V> Handle<NodeRef<ValMut<'a>, K, V, Leaf>, Edge>
sourceunsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V)
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.
sourceunsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V)
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>
impl<K, V> Handle<NodeRef<Dying, K, V, Leaf>, Edge>
sourceunsafe fn deallocating_next_unchecked<A: Allocator + Clone>(
&mut self,
alloc: A
) -> Handle<NodeRef<Dying, K, V, LeafOrInternal>, KV>
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.
sourceunsafe fn deallocating_next_back_unchecked<A: Allocator + Clone>(
&mut self,
alloc: A
) -> Handle<NodeRef<Dying, K, V, LeafOrInternal>, KV>
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>
impl<BorrowType: BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, KV>
source§impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, KV>
impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, KV>
sourcepub unsafe fn new_kv(
node: NodeRef<BorrowType, K, V, NodeType>,
idx: usize
) -> Self
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()
.
pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, Edge>
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>
impl<BorrowType, K, V, NodeType, HandleType> Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType>
source§impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<Mut<'a>, K, V, NodeType>, HandleType>
impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<Mut<'a>, K, V, NodeType>, HandleType>
sourcepub unsafe fn reborrow_mut(
&mut self
) -> Handle<NodeRef<Mut<'_>, K, V, NodeType>, HandleType>
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
.
sourcepub fn dormant(&self) -> Handle<NodeRef<DormantMut, K, V, NodeType>, HandleType>
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>
impl<K, V, NodeType, HandleType> Handle<NodeRef<DormantMut, K, V, NodeType>, HandleType>
source§impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, Edge>
impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, Edge>
sourcepub unsafe fn new_edge(
node: NodeRef<BorrowType, K, V, NodeType>,
idx: usize
) -> Self
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()
.
pub fn left_kv( self ) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, KV>, Self>
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>
impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>
sourcefn insert<A: Allocator + Clone>(
self,
key: K,
val: V,
alloc: A
) -> (Option<SplitResult<'a, K, V, Leaf>>, Handle<NodeRef<DormantMut, K, V, Leaf>, KV>)
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>
impl<'a, K, V> Handle<NodeRef<Mut<'a>, K, V, Internal>, Edge>
sourcefn correct_parent_link(self)
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,
source§impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, Edge>
impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, Edge>
sourcefn insert_fit(
&mut self,
key: K,
val: V,
edge: NodeRef<Owned, K, V, LeafOrInternal>
)
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.
sourcefn insert<A: Allocator + Clone>(
self,
key: K,
val: V,
edge: NodeRef<Owned, K, V, LeafOrInternal>,
alloc: A
) -> Option<SplitResult<'a, K, V, Internal>>
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>
impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Leaf>, Edge>
sourcepub 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>
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>
impl<BorrowType: BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Internal>, Edge>
sourcepub fn descend(self) -> NodeRef<BorrowType, K, V, LeafOrInternal>
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<Mut<'a>, K, V, NodeType>, KV>
impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<Mut<'a>, K, V, NodeType>, KV>
pub fn key_mut(&mut self) -> &mut K
pub fn into_val_mut(self) -> &'a mut V
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>
impl<'a, K, V, NodeType> Handle<NodeRef<ValMut<'a>, K, V, NodeType>, KV>
pub fn into_kv_valmut(self) -> (&'a K, &'a mut V)
source§impl<K, V, NodeType> Handle<NodeRef<Dying, K, V, NodeType>, KV>
impl<K, V, NodeType> Handle<NodeRef<Dying, K, V, NodeType>, KV>
sourcepub unsafe fn into_key_val(self) -> (K, V)
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.
sourcepub unsafe fn drop_key_val(self)
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>
impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<Mut<'a>, K, V, NodeType>, KV>
sourcefn split_leaf_data(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V)
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>
impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Leaf>, KV>
sourcepub fn split<A: Allocator + Clone>(
self,
alloc: A
) -> SplitResult<'a, K, V, Leaf>
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§impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>
impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>
sourcepub fn split<A: Allocator + Clone>(
self,
alloc: A
) -> SplitResult<'a, K, V, Internal>
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>
impl<'a, K, V> Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>
pub fn consider_for_balancing(self) -> BalancingContext<'a, K, V>
source§impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>
impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>
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>
impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Internal>, Edge>
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>
impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, Leaf>, KV>
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>
impl<BorrowType, K, V, Type> Handle<NodeRef<BorrowType, K, V, LeafOrInternal>, Type>
source§impl<'a, K, V> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, Edge>
impl<'a, K, V> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, Edge>
sourcepub fn move_suffix(
&mut self,
right: &mut NodeRef<Mut<'a>, K, V, LeafOrInternal>
)
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>
impl<'a, K: 'a, V: 'a> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, KV>
sourcepub 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>)
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.