Struct alloc::collections::btree::node::NodeRef

pub struct NodeRef<BorrowType, K, V, Type> {
    height: usize,
    node: NonNull<LeafNode<K, V>>,
    _marker: PhantomData<(BorrowType, Type)>,
}

A reference to a node.

This type has a number of parameters that controls how it acts:

• BorrowType: A dummy type that describes the kind of borrow and carries a lifetime.
  • When this is Immut<'a>, the NodeRef acts roughly like &'a Node.
  • When this is ValMut<'a>, the NodeRef acts roughly like &'a Node with respect to keys and tree structure, but also allows many mutable references to values throughout the tree to coexist.
  • When this is Mut<'a>, the NodeRef acts roughly like &'a mut Node, although insert methods allow a mutable pointer to a value to coexist.
  • When this is Owned, the NodeRef acts roughly like Box<Node>, but does not have a destructor, and must be cleaned up manually.
  • When this is Dying, the NodeRef still acts roughly like Box<Node>, but has methods to destroy the tree bit by bit, and ordinary methods, while not marked as unsafe to call, can invoke UB if called incorrectly. Since any NodeRef allows navigating through the tree, BorrowType effectively applies to the entire tree, not just to the node itself.
• K and V: These are the types of keys and values stored in the nodes.
• Type: This can be Leaf, Internal, or LeafOrInternal. When this is Leaf, the NodeRef points to a leaf node, when this is Internal the NodeRef points to an internal node, and when this is LeafOrInternal the NodeRef could be pointing to either type of node. Type is named NodeType when used outside NodeRef.

Both BorrowType and NodeType restrict what methods we implement, to exploit static type safety. There are limitations in the way we can apply such restrictions:

• For each type parameter, we can only define a method either generically or for one particular type. For example, we cannot define a method like into_kv generically for all BorrowType, or once for all types that carry a lifetime, because we want it to return &'a references. Therefore, we define it only for the least powerful type Immut<'a>.
• We cannot get implicit coercion from say Mut<'a> to Immut<'a>. Therefore, we have to explicitly call reborrow on a more powerful NodeRef in order to reach a method like into_kv.

All methods on NodeRef that return some kind of reference, either:

• Take self by value, and return the lifetime carried by BorrowType. Sometimes, to invoke such a method, we need to call reborrow_mut.
• Take self by reference, and (implicitly) return that reference’s lifetime, instead of the lifetime carried by BorrowType. That way, the borrow checker guarantees that the NodeRef remains borrowed as long as the returned reference is used. The methods supporting insert bend this rule by returning a raw pointer, i.e., a reference without any lifetime.

Fields

height: usize

The number of levels that the node and the level of leaves are apart, a constant of the node that cannot be entirely described by Type, and that the node itself does not store. We only need to store the height of the root node, and derive every other node’s height from it. Must be zero if Type is Leaf and non-zero if Type is Internal.

node: NonNull<LeafNode<K, V>>

The pointer to the leaf or internal node. The definition of InternalNode ensures that the pointer is valid either way.

_marker: PhantomData<(BorrowType, Type)>

Implementations

impl<K, V> NodeRef<Owned, K, V, LeafOrInternal>

pub fn append_from_sorted_iters<I, A: Allocator + Clone>( &mut self, left: I, right: I, length: &mut usize, alloc: A )where K: Ord, I: Iterator<Item = (K, V)> + FusedIterator,

Appends all key-value pairs from the union of two ascending iterators, incrementing a length variable along the way. The latter makes it easier for the caller to avoid a leak when a drop handler panicks.

If both iterators produce the same key, this method drops the pair from the left iterator and appends the pair from the right iterator.

If you want the tree to end up in a strictly ascending order, like for a BTreeMap, both iterators should produce keys in strictly ascending order, each greater than all keys in the tree, including any keys already in the tree upon entry.

pub fn bulk_push<I, A: Allocator + Clone>( &mut self, iter: I, length: &mut usize, alloc: A )where I: Iterator<Item = (K, V)>,

Pushes all key-value pairs to the end of the tree, incrementing a length variable along the way. The latter makes it easier for the caller to avoid a leak when the iterator panicks.

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

fn fix_node_through_parent<A: Allocator + Clone>( self, alloc: A ) -> Result<Option<NodeRef<Mut<'a>, K, V, Internal>>, Self>

Stocks up a possibly underfull node by merging with or stealing from a sibling. If successful but at the cost of shrinking the parent node, returns that shrunk parent node. Returns an Err if the node is an empty root.

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

pub fn fix_node_and_affected_ancestors<A: Allocator + Clone>( self, alloc: A ) -> bool

Stocks up a possibly underfull node, and if that causes its parent node to shrink, stocks up the parent, recursively. Returns true if it fixed the tree, false if it couldn’t because the root node became empty.

This method does not expect ancestors to already be underfull upon entry and panics if it encounters an empty ancestor.

impl<K, V> NodeRef<Owned, K, V, LeafOrInternal>

pub fn fix_top<A: Allocator + Clone>(&mut self, alloc: A)

Removes empty levels on the top, but keeps an empty leaf if the entire tree is empty.

pub fn fix_right_border<A: Allocator + Clone>(&mut self, alloc: A)

Stocks up or merge away any underfull nodes on the right border of the tree. The other nodes, those that are not the root nor a rightmost edge, must already have at least MIN_LEN elements.

pub fn fix_left_border<A: Allocator + Clone>(&mut self, alloc: A)

The symmetric clone of fix_right_border.

pub fn fix_right_border_of_plentiful(&mut self)

Stocks up any underfull nodes on the right border of the tree. The other nodes, those that are neither the root nor a rightmost edge, must be prepared to have up to MIN_LEN elements stolen.

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

unsafe fn find_leaf_edges_spanning_range<Q, R>( self, range: R ) -> LeafRange<BorrowType, K, V>where Q: Ord + ?Sized, K: Borrow<Q>, R: RangeBounds<Q>,

Finds the distinct leaf edges delimiting a specified range in a tree.

If such distinct edges exist, returns them in ascending order, meaning that a non-zero number of calls to next_unchecked on the front of the result and/or calls to next_back_unchecked on the back of the result will eventually reach the same edge.

If there are no such edges, i.e., if the tree contains no key within the range, returns an empty front and back.

Safety

Unless BorrowType is Immut, do not use the handles to visit the same KV twice.

impl<'a, K: 'a, V: 'a> NodeRef<Immut<'a>, K, V, LeafOrInternal>

pub fn range_search<Q, R>(self, range: R) -> LeafRange<Immut<'a>, K, V>where Q: ?Sized + Ord, K: Borrow<Q>, R: RangeBounds<Q>,

Finds the pair of leaf edges delimiting a specific range in a tree.

The result is meaningful only if the tree is ordered by key, like the tree in a BTreeMap is.

pub fn full_range(self) -> LazyLeafRange<Immut<'a>, K, V>

Finds the pair of leaf edges delimiting an entire tree.

impl<'a, K: 'a, V: 'a> NodeRef<ValMut<'a>, K, V, LeafOrInternal>

pub fn range_search<Q, R>(self, range: R) -> LeafRange<ValMut<'a>, K, V>where Q: ?Sized + Ord, K: Borrow<Q>, R: RangeBounds<Q>,

Splits a unique reference into a pair of leaf edges delimiting a specified range. The result are non-unique references allowing (some) mutation, which must be used carefully.

The result is meaningful only if the tree is ordered by key, like the tree in a BTreeMap is.

Safety

Do not use the duplicate handles to visit the same KV twice.

pub fn full_range(self) -> LazyLeafRange<ValMut<'a>, K, V>

Splits a unique reference into a pair of leaf edges delimiting the full range of the tree. The results are non-unique references allowing mutation (of values only), so must be used with care.

impl<K, V> NodeRef<Dying, K, V, LeafOrInternal>

pub fn full_range(self) -> LazyLeafRange<Dying, K, V>

Splits a unique reference into a pair of leaf edges delimiting the full range of the tree. The results are non-unique references allowing massively destructive mutation, so must be used with the utmost care.

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

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

Returns the leftmost leaf edge in or underneath a node - in other words, the edge you need first when navigating forward (or last when navigating backward).

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

Returns the rightmost leaf edge in or underneath a node - in other words, the edge you need last when navigating forward (or first when navigating backward).

impl<'a, K: 'a, V: 'a> NodeRef<Immut<'a>, K, V, LeafOrInternal>

pub fn visit_nodes_in_order<F>(self, visit: F)where F: FnMut(Position<Immut<'a>, K, V>),

Visits leaf nodes and internal KVs in order of ascending keys, and also visits internal nodes as a whole in a depth first order, meaning that internal nodes precede their individual KVs and their child nodes.

pub fn calc_length(self) -> usize

Calculates the number of elements in a (sub)tree.

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

pub fn lower_bound<Q>( self, bound: SearchBound<&Q> ) -> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>where Q: Ord + ?Sized, K: Borrow<Q>,

Returns the leaf edge corresponding to the first point at which the given bound is true.

pub fn upper_bound<Q>( self, bound: SearchBound<&Q> ) -> Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>where Q: Ord + ?Sized, K: Borrow<Q>,

Returns the leaf edge corresponding to the last point at which the given bound is true.

impl<K, V> NodeRef<Owned, K, V, Leaf>

pub fn new_leaf<A: Allocator + Clone>(alloc: A) -> Self

fn from_new_leaf<A: Allocator + Clone>(leaf: Box<LeafNode<K, V>, A>) -> Self

impl<K, V> NodeRef<Owned, K, V, Internal>

fn new_internal<A: Allocator + Clone>( child: NodeRef<Owned, K, V, LeafOrInternal>, alloc: A ) -> Self

unsafe fn from_new_internal<A: Allocator + Clone>( internal: Box<InternalNode<K, V>, A>, height: usize ) -> Self

Safety

height must not be zero.

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

fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self

Unpack a node reference that was packed as NodeRef::parent.

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

fn as_internal_ptr(this: &Self) -> *mut InternalNode<K, V>

Exposes the data of an internal node.

Returns a raw ptr to avoid invalidating other references to this node.

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

fn as_internal_mut(&mut self) -> &mut InternalNode<K, V>

Borrows exclusive access to the data of an internal node.

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

pub fn len(&self) -> usize

Finds the length of the node. This is the number of keys or values. The number of edges is len() + 1. Note that, despite being safe, calling this function can have the side effect of invalidating mutable references that unsafe code has created.

pub fn height(&self) -> usize

Returns the number of levels that the node and leaves are apart. Zero height means the node is a leaf itself. If you picture trees with the root on top, the number says at which elevation the node appears. If you picture trees with leaves on top, the number says how high the tree extends above the node.

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

Temporarily takes out another, immutable reference to the same node.

fn as_leaf_ptr(this: &Self) -> *mut LeafNode<K, V>

Exposes the leaf portion of any leaf or internal node.

Returns a raw ptr to avoid invalidating other references to this node.

impl<BorrowType: BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type>

pub fn ascend( self ) -> Result<Handle<NodeRef<BorrowType, K, V, Internal>, Edge>, Self>

Finds the parent of the current node. Returns Ok(handle) if the current node actually has a parent, where handle points to the edge of the parent that points to the current node. Returns Err(self) if the current node has no parent, giving back the original NodeRef.

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.

pub fn first_edge(self) -> Handle<Self, Edge>

pub fn last_edge(self) -> Handle<Self, Edge>

pub fn first_kv(self) -> Handle<Self, KV>

Note that self must be nonempty.

pub fn last_kv(self) -> Handle<Self, KV>

Note that self must be nonempty.

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

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

Could be a public implementation of PartialEq, but only used in this module.

impl<'a, K: 'a, V: 'a, Type> NodeRef<Immut<'a>, K, V, Type>

fn into_leaf(self) -> &'a LeafNode<K, V>

Exposes the leaf portion of any leaf or internal node in an immutable tree.

pub fn keys(&self) -> &[K]

Borrows a view into the keys stored in the node.

impl<K, V> NodeRef<Dying, K, V, LeafOrInternal>

pub unsafe fn deallocate_and_ascend<A: Allocator + Clone>( self, alloc: A ) -> Option<Handle<NodeRef<Dying, K, V, Internal>, Edge>>

Similar to ascend, gets a reference to a node’s parent node, but also deallocates the current node in the process. This is unsafe because the current node will still be accessible despite being deallocated.

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

unsafe fn reborrow_mut(&mut self) -> NodeRef<Mut<'_>, K, V, Type>

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

Because mutable pointers can roam anywhere around the tree, the returned pointer can easily be used to make the original pointer dangling, out of bounds, or invalid under stacked borrow rules.

fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V>

Borrows exclusive access to the leaf portion of a leaf or internal node.

fn into_leaf_mut(self) -> &'a mut LeafNode<K, V>

Offers exclusive access to the leaf portion of a leaf or internal node.

pub fn dormant(&self) -> NodeRef<DormantMut, K, V, Type>

Returns a dormant copy of this node with its lifetime erased which can be reawakened later.

impl<K, V, Type> NodeRef<DormantMut, K, V, Type>

pub unsafe fn awaken<'a>(self) -> NodeRef<Mut<'a>, K, V, Type>

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<K, V, Type> NodeRef<Dying, K, V, Type>

fn as_leaf_dying(&mut self) -> &mut LeafNode<K, V>

Borrows exclusive access to the leaf portion of a dying leaf or internal node.

impl<'a, K: 'a, V: 'a, Type> NodeRef<Mut<'a>, K, V, Type>

unsafe fn key_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Outputwhere I: SliceIndex<[MaybeUninit<K>], Output = Output>,

Borrows exclusive access to an element of the key storage area.

Safety

index is in bounds of 0..CAPACITY

unsafe fn val_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Outputwhere I: SliceIndex<[MaybeUninit<V>], Output = Output>,

Borrows exclusive access to an element or slice of the node’s value storage area.

Safety

index is in bounds of 0..CAPACITY

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

unsafe fn edge_area_mut<I, Output: ?Sized>(&mut self, index: I) -> &mut Outputwhere I: SliceIndex<[MaybeUninit<NonNull<LeafNode<K, V>>>], Output = Output>,

Borrows exclusive access to an element or slice of the node’s storage area for edge contents.

Safety

index is in bounds of 0..CAPACITY + 1

impl<'a, K, V, Type> NodeRef<ValMut<'a>, K, V, Type>

unsafe fn into_key_val_mut_at(self, idx: usize) -> (&'a K, &'a mut V)

Safety

• The node has more than idx initialized elements.

impl<'a, K: 'a, V: 'a, Type> NodeRef<Mut<'a>, K, V, Type>

pub fn len_mut(&mut self) -> &mut u16

Borrows exclusive access to the length of the node.

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

unsafe fn correct_childrens_parent_links<R: Iterator<Item = usize>>( &mut self, range: R )

Safety

Every item returned by range is a valid edge index for the node.

fn correct_all_childrens_parent_links(&mut self)

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

fn set_parent_link( &mut self, parent: NonNull<InternalNode<K, V>>, parent_idx: usize )

Sets the node’s link to its parent edge, without invalidating other references to the node.

impl<K, V> NodeRef<Owned, K, V, LeafOrInternal>

fn clear_parent_link(&mut self)

Clears the root’s link to its parent edge.

impl<K, V> NodeRef<Owned, K, V, LeafOrInternal>

pub fn new<A: Allocator + Clone>(alloc: A) -> Self

Returns a new owned tree, with its own root node that is initially empty.

pub fn push_internal_level<A: Allocator + Clone>( &mut self, alloc: A ) -> NodeRef<Mut<'_>, K, V, Internal>

Adds a new internal node with a single edge pointing to the previous root node, make that new node the root node, and return it. This increases the height by 1 and is the opposite of pop_internal_level.

pub fn pop_internal_level<A: Allocator + Clone>(&mut self, alloc: A)

Removes the internal root node, using its first child as the new root node. As it is intended only to be called when the root node has only one child, no cleanup is done on any of the keys, values and other children. This decreases the height by 1 and is the opposite of push_internal_level.

Requires exclusive access to the NodeRef object but not to the root node; it will not invalidate other handles or references to the root node.

Panics if there is no internal level, i.e., if the root node is a leaf.

impl<K, V, Type> NodeRef<Owned, K, V, Type>

pub fn borrow_mut(&mut self) -> NodeRef<Mut<'_>, K, V, Type>

Mutably borrows the owned root node. Unlike reborrow_mut, this is safe because the return value cannot be used to destroy the root, and there cannot be other references to the tree.

pub fn borrow_valmut(&mut self) -> NodeRef<ValMut<'_>, K, V, Type>

Slightly mutably borrows the owned root node.

pub fn into_dying(self) -> NodeRef<Dying, K, V, Type>

Irreversibly transitions to a reference that permits traversal and offers destructive methods and little else.

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

pub fn push(&mut self, key: K, val: V) -> &mut V

Adds a key-value pair to the end of the node, and returns the mutable reference of the inserted value.

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

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

Adds a key-value pair, and an edge to go to the right of that pair, to the end of the node.

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

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

Removes any static information asserting that this node is a Leaf node.

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

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

Removes any static information asserting that this node is an Internal node.

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

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

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

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

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

Unsafely asserts to the compiler the static information that this node is a Leaf.

unsafe fn cast_to_internal_unchecked(self) -> NodeRef<Mut<'a>, K, V, Internal>

Unsafely asserts to the compiler the static information that this node is an Internal.

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

pub fn choose_parent_kv( self ) -> Result<LeftOrRight<BalancingContext<'a, K, V>>, Self>

Chooses a balancing context involving the node as a child, thus between the KV immediately to the left or to the right in the parent node. Returns an Err if there is no parent. Panics if the parent is empty.

Prefers the left side, to be optimal if the given node is somehow underfull, meaning here only that it has fewer elements than its left sibling and than its right sibling, if they exist. In that case, merging with the left sibling is faster, since we only need to move the node’s N elements, instead of shifting them to the right and moving more than N elements in front. Stealing from the left sibling is also typically faster, since we only need to shift the node’s N elements to the right, instead of shifting at least N of the sibling’s elements to the left.

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

pub fn search_tree<Q>( self, key: &Q ) -> SearchResult<BorrowType, K, V, LeafOrInternal, Leaf>where Q: Ord + ?Sized, K: Borrow<Q>,

Looks up a given key in a (sub)tree headed by the node, recursively. Returns a Found with the handle of the matching KV, if any. Otherwise, returns a GoDown with the handle of the leaf edge where the key belongs.

The result is meaningful only if the tree is ordered by key, like the tree in a BTreeMap is.

pub fn search_tree_for_bifurcation<'r, Q, R>( self, range: &'r R ) -> Result<(NodeRef<BorrowType, K, V, LeafOrInternal>, usize, usize, SearchBound<&'r Q>, SearchBound<&'r Q>), Handle<NodeRef<BorrowType, K, V, Leaf>, Edge>>where Q: Ord + ?Sized, K: Borrow<Q>, R: RangeBounds<Q>,

Descends to the nearest node where the edge matching the lower bound of the range is different from the edge matching the upper bound, i.e., the nearest node that has at least one key contained in the range.

If found, returns an Ok with that node, the strictly ascending pair of edge indices in the node delimiting the range, and the corresponding pair of bounds for continuing the search in the child nodes, in case the node is internal.

If not found, returns an Err with the leaf edge matching the entire range.

As a diagnostic service, panics if the range specifies impossible bounds.

The result is meaningful only if the tree is ordered by key.

pub fn find_lower_bound_edge<'r, Q>( self, bound: SearchBound<&'r Q> ) -> (Handle<Self, Edge>, SearchBound<&'r Q>)where Q: ?Sized + Ord, K: Borrow<Q>,

Finds an edge in the node delimiting the lower bound of a range. Also returns the lower bound to be used for continuing the search in the matching child node, if self is an internal node.

The result is meaningful only if the tree is ordered by key.

pub fn find_upper_bound_edge<'r, Q>( self, bound: SearchBound<&'r Q> ) -> (Handle<Self, Edge>, SearchBound<&'r Q>)where Q: ?Sized + Ord, K: Borrow<Q>,

Clone of find_lower_bound_edge for the upper bound.

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

pub fn search_node<Q>( self, key: &Q ) -> SearchResult<BorrowType, K, V, Type, Type>where Q: Ord + ?Sized, K: Borrow<Q>,

Looks up a given key in the node, without recursion. Returns a Found with the handle of the matching KV, if any. Otherwise, returns a GoDown with the handle of the edge where the key might be found (if the node is internal) or where the key can be inserted.

The result is meaningful only if the tree is ordered by key, like the tree in a BTreeMap is.

unsafe fn find_key_index<Q>(&self, key: &Q, start_index: usize) -> IndexResultwhere Q: Ord + ?Sized, K: Borrow<Q>,

Returns either the KV index in the node at which the key (or an equivalent) exists, or the edge index where the key belongs, starting from a particular index.

The result is meaningful only if the tree is ordered by key, like the tree in a BTreeMap is.

Safety

start_index must be a valid edge index for the node.

fn find_lower_bound_index<'r, Q>( &self, bound: SearchBound<&'r Q> ) -> (usize, SearchBound<&'r Q>)where Q: ?Sized + Ord, K: Borrow<Q>,

Finds an edge index in the node delimiting the lower bound of a range. Also returns the lower bound to be used for continuing the search in the matching child node, if self is an internal node.

The result is meaningful only if the tree is ordered by key.

unsafe fn find_upper_bound_index<'r, Q>( &self, bound: SearchBound<&'r Q>, start_index: usize ) -> (usize, SearchBound<&'r Q>)where Q: ?Sized + Ord, K: Borrow<Q>,

Mirror image of find_lower_bound_index for the upper bound, with an additional parameter to skip part of the key array.

Safety

start_index must be a valid edge index for the node.

impl<K, V> NodeRef<Owned, K, V, LeafOrInternal>

pub fn calc_split_length( total_num: usize, root_a: &NodeRef<Owned, K, V, LeafOrInternal>, root_b: &NodeRef<Owned, K, V, LeafOrInternal> ) -> (usize, usize)

Calculates the length of both trees that result from splitting up a given number of distinct key-value pairs.

pub fn split_off<Q: ?Sized + Ord, A: Allocator + Clone>( &mut self, key: &Q, alloc: A ) -> Selfwhere K: Borrow<Q>,

Split off a tree with key-value pairs at and after the given key. The result is meaningful only if the tree is ordered by key, and if the ordering of Q corresponds to that of K. If self respects all BTreeMap tree invariants, then both self and the returned tree will respect those invariants.

fn new_pillar<A: Allocator + Clone>(height: usize, alloc: A) -> Self

Creates a tree consisting of empty nodes.

Trait Implementations

impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<Immut<'a>, K, V, Type>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<Immut<'a>, K, V, Type>

impl<K: Send, V: Send, Type> Send for NodeRef<Dying, K, V, Type>

impl<K: Sync, V: Sync, Type> Send for NodeRef<Immut<'_>, K, V, Type>

impl<K: Send, V: Send, Type> Send for NodeRef<Mut<'_>, K, V, Type>

impl<K: Send, V: Send, Type> Send for NodeRef<Owned, K, V, Type>

impl<K: Send, V: Send, Type> Send for NodeRef<ValMut<'_>, K, V, Type>

impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type>