Struct BalancingContext

pub(super) 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(super) fn left_child_len(&self) -> usize

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

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

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

pub(super) 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(super) 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(super) 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(super) 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(super) 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(super) 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(super) fn bulk_steal_left(&mut self, count: usize)

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

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

The symmetric clone of bulk_steal_left.