Struct alloc::collections::btree::node::BalancingContext

pub struct BalancingContext<'a, K, V> {
    parent: Handle<NodeRef<Mut<'a>, K, V, Internal>, KV>,
    left_child: NodeRef<Mut<'a>, K, V, LeafOrInternal>,
    right_child: NodeRef<Mut<'a>, K, V, LeafOrInternal>,
}

Represents a session for evaluating and performing a balancing operation around an internal key-value pair.

Fields

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

left_child: NodeRef<Mut<'a>, K, V, LeafOrInternal>

right_child: NodeRef<Mut<'a>, K, V, LeafOrInternal>

Implementations

impl<'a, K, V> BalancingContext<'a, K, V>

pub fn left_child_len(&self) -> usize

pub fn right_child_len(&self) -> usize

pub fn into_left_child(self) -> NodeRef<Mut<'a>, K, V, LeafOrInternal>

pub fn into_right_child(self) -> NodeRef<Mut<'a>, K, V, LeafOrInternal>

pub fn can_merge(&self) -> bool

Returns whether merging is possible, i.e., whether there is enough room in a node to combine the central KV with both adjacent child nodes.

impl<'a, K: 'a, V: 'a> BalancingContext<'a, K, V>

fn do_merge<F: FnOnce(NodeRef<Mut<'a>, K, V, Internal>, NodeRef<Mut<'a>, K, V, LeafOrInternal>) -> R, R, A: Allocator>( self, result: F, alloc: A ) -> R

Performs a merge and lets a closure decide what to return.

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

Merges the parent’s key-value pair and both adjacent child nodes into the left child node and returns the shrunk parent node.

Panics unless we .can_merge().

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

Merges the parent’s key-value pair and both adjacent child nodes into the left child node and returns that child node.

Panics unless we .can_merge().

pub fn merge_tracking_child_edge<A: Allocator + Clone>( self, track_edge_idx: LeftOrRight<usize>, alloc: A ) -> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, Edge>

Merges the parent’s key-value pair and both adjacent child nodes into the left child node and returns the edge handle in that child node where the tracked child edge ended up,

Panics unless we .can_merge().

pub fn steal_left( self, track_right_edge_idx: usize ) -> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, Edge>

Removes a key-value pair from the left child and places it in the key-value storage of the parent, while pushing the old parent key-value pair into the right child. Returns a handle to the edge in the right child corresponding to where the original edge specified by track_right_edge_idx ended up.

pub fn steal_right( self, track_left_edge_idx: usize ) -> Handle<NodeRef<Mut<'a>, K, V, LeafOrInternal>, Edge>

Removes a key-value pair from the right child and places it in the key-value storage of the parent, while pushing the old parent key-value pair onto the left child. Returns a handle to the edge in the left child specified by track_left_edge_idx, which didn’t move.

pub fn bulk_steal_left(&mut self, count: usize)

This does stealing similar to steal_left but steals multiple elements at once.

pub fn bulk_steal_right(&mut self, count: usize)

The symmetric clone of bulk_steal_left.