Module node

Modules

marker 🔒

Structs

BalancingContext 🔒

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

Handle 🔒

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

InternalNode 🔒

The underlying representation of internal nodes. As with LeafNodes, these should be hidden behind BoxedNodes to prevent dropping uninitialized keys and values. Any pointer to an InternalNode can be directly cast to a pointer to the underlying LeafNode portion of the node, allowing code to act on leaf and internal nodes generically without having to even check which of the two a pointer is pointing at. This property is enabled by the use of repr(C).

LeafNode 🔒

The underlying representation of leaf nodes and part of the representation of internal nodes.

NodeRef 🔒

A reference to a node.

SplitResult 🔒

Result of insertion, when a node needed to expand beyond its capacity.

Enums

ForceResult 🔒

LeftOrRight 🔒

Constants

B 🔒

CAPACITY 🔒

EDGE_IDX_LEFT_OF_CENTER 🔒

EDGE_IDX_RIGHT_OF_CENTER 🔒

KV_IDX_CENTER 🔒

MIN_LEN_AFTER_SPLIT 🔒

Functions

move_to_slice 🔒

Moves all values from a slice of initialized elements to a slice of uninitialized elements, leaving behind src as all uninitialized. Works like dst.copy_from_slice(src) but does not require T to be Copy.

slice_insert 🔒 ^⚠

Inserts a value into a slice of initialized elements followed by one uninitialized element.

slice_remove 🔒 ^⚠

Removes and returns a value from a slice of all initialized elements, leaving behind one trailing uninitialized element.

slice_shl 🔒 ^⚠

Shifts the elements in a slice distance positions to the left.

slice_shr 🔒 ^⚠

Shifts the elements in a slice distance positions to the right.

splitpoint 🔒

Given an edge index where we want to insert into a node filled to capacity, computes a sensible KV index of a split point and where to perform the insertion. The goal of the split point is for its key and value to end up in a parent node; the keys, values and edges to the left of the split point become the left child; the keys, values and edges to the right of the split point become the right child.

Type Aliases

BoxedNode 🔒

A managed, non-null pointer to a node. This is either an owned pointer to LeafNode<K, V> or an owned pointer to InternalNode<K, V>.

Root 🔒

The root node of an owned tree.