Union Node 

pub(super) union Node<V> {
    inner: ManuallyDrop<TwoEndedGrove<Self>>,
    leaf: ManuallyDrop<TwoEndedGrove<V>>,
}

A node in the K-dimensional trie structure.

This is an internal implementation detail of KdTrie. It uses a union to represent either an inner node, which contains child nodes, or a leaf node, which contains values. This allows us to store values in contiguous memory instead of creating a separate node for each value.

Node Types

There are two types of nodes in the trie:

1. Inner Nodes: These nodes contain child nodes and are used for all dimensions except the last one. Each inner node is a TwoEndedGrove of other Node instances, allowing for efficient storage of sparse child nodes.

2. Leaf Nodes: These nodes contain the actual values and are used for the last dimension. Each leaf node is a TwoEndedGrove of values of type V.

Thread Safety

The Node struct is designed to be thread-safe and wait-free, allowing concurrent insertions and retrievals from multiple threads. This is achieved through the use of atomic operations in the underlying TwoEndedGrove data structure.

Memory Management

The Node struct uses a Rust union to efficiently represent either an inner node or a leaf node without the overhead of an enum discriminant. This approach saves memory but requires careful manual memory management.

Safety

It is the responsibility of the caller to know which variant is contained in the union. We only use this in KdTrie, where we know which variant is contained based on the number of dimensions.

The inner and leaf variants are wrapped in ManuallyDrop, because union fields can’t have drop glue. Unions don’t know what they contain, and so can’t know which drop implementation to run. We delegate the responsibility of dropping the node to the KdTrie, using drop_level.

Fields

inner: ManuallyDrop<TwoEndedGrove<Self>>

leaf: ManuallyDrop<TwoEndedGrove<V>>

Implementations

impl<V> Node<V>

pub(super) fn new_inner() -> Self

Creates a new inner node.

An inner node contains child nodes and is used for all dimensions except the last one.

pub(super) fn new_leaf() -> Self

Creates a new leaf node.

A leaf node contains values and is used for the last dimension.

pub(super) unsafe fn ensure_child(&self, idx: i32, to_insert: Self) -> &Self

Ensures that a child node exists at the specified index, creating it if necessary.

Parameters

• idx: The index at which to ensure a child node exists
• to_insert: The node to insert if no child exists at the specified index

Returns

A reference to the child node at the specified index

Safety

Can only be called on an inner node.

pub(super) unsafe fn get_child(&self, idx: i32) -> Option<&Self>

Retrieves a reference to the child node at the specified index, if it exists.

Parameters

• idx: The index of the child node to retrieve

Returns

• Some(&Self) if a child node exists at the specified index
• None if no child node exists at the specified index

Safety

Can only be called on an inner node.

pub(super) unsafe fn get_child_mut(&mut self, idx: i32) -> Option<&mut Self>

Retrieves a mutable reference to the child node at the specified index, if it exists.

Parameters

• idx: The index of the child node to retrieve

Returns

• Some(&mut Self) if a child node exists at the specified index
• None if no child node exists at the specified index

Safety

Can only be called on an inner node.

pub(super) unsafe fn get_value(&self, idx: i32) -> Option<&V>

Retrieves a reference to the value at the specified index, if it exists.

Parameters

• idx: The index of the value to retrieve

Returns

• Some(&V) if a value exists at the specified index
• None if no value exists at the specified index

Safety

Can only be called on a leaf node.

pub(super) unsafe fn get_value_mut(&mut self, idx: i32) -> Option<&mut V>

Retrieves a mutable reference to the value at the specified index, if it exists.

Parameters

• idx: The index of the value to retrieve

Returns

• Some(&mut V) if a value exists at the specified index
• None if no value exists at the specified index

Safety

Can only be called on a leaf node.

pub(super) unsafe fn set_value(&self, idx: i32, value: V)

Sets the value at the specified index.

Parameters

• idx: The index at which to set the value
• value: The value to set

Safety

Can only be called on a leaf node.

pub(super) unsafe fn try_set_value(&self, idx: i32, value: V) -> Result<(), V>

Attempts to set the value at the specified index.

Parameters

• idx: The index at which to set the value
• value: The value to set

Returns

• Ok(()) if the value was successfully set
• Err(value) if the index was already occupied, returning the value that we tried to insert

Safety

Can only be called on a leaf node.

pub(super) unsafe fn inner(&self) -> &TwoEndedGrove<Self>

Returns a reference to the inner grove.

Safety

Can only be called on an inner node.

pub(super) unsafe fn leaf(&self) -> &TwoEndedGrove<V>

Returns a reference to the leaf grove.

Safety

Can only be called on a leaf node.

pub(super) fn drop_level(&mut self, dimensions: usize, level: usize)

Recursively drops the node and all its children.

This method is called by the Drop implementation of KdTrie to ensure proper cleanup of all allocated memory.

Parameters

• dimensions: The total number of dimensions in the trie
• level: The current level in the trie (the root node has level 0)

Trait Implementations

impl<'a, V> NodeRef for &'a Node<V>

Shared node reference. Yields &V values.

type Value = &'a V

unsafe fn range(self, is_leaf: bool) -> Range<i32>

Returns the range of indices for this node.

unsafe fn child(self, idx: i32) -> Option<Self>

Returns a handle to the child node at idx, or None if no child exists.

unsafe fn value(self, idx: i32) -> Option<Self::Value>

Returns a reference to the value at idx, or None if the slot is empty.