Struct Grove 

pub struct Grove<T> {
    blocks: [Block<T>; 32],
    max: AtomicUsize,
}

A sparse vector with pinned elements and geometrically growing capacity.

Grove (a pun on “grow vec”) is a specialized data structure that provides efficient storage for data with the following key features:

• Thread Safety: Safe for concurrent reads and writes from multiple threads
• Memory Efficiency: Uses a block-based allocation strategy that grows geometrically
• Pinned Elements: Once inserted, elements never move in memory
• Sparse Storage: Efficiently handles sparse data with large gaps between indices

This data structure is primarily used as the backing store for other collections in this crate, such as OnceVec and MultiIndexed.

Implementation Details

Grove uses a series of fixed-size blocks to store elements. Each block’s size is a power of 2, and the block number determines its size. This approach allows for efficient memory usage while still supporting large indices without allocating memory for all intermediate elements. We use distinct lazily-allocated blocks to avoid any reallocation, which would invalidate pointers held by other threads.

Examples

use once::Grove;

let grove = Grove::<i32>::new();

// Insert elements at arbitrary indices
grove.insert(0, 10);
grove.insert(100, 20);
grove.insert(1000, 30);

// Retrieve elements
assert_eq!(grove.get(0), Some(&10));
assert_eq!(grove.get(100), Some(&20));
assert_eq!(grove.get(1000), Some(&30));
assert_eq!(grove.get(50), None); // No element at this index

Fields

blocks: [Block<T>; 32]

max: AtomicUsize

The maximum index that has been inserted into the Grove (exclusive).

Implementations

impl<T> Grove<T>

pub fn new() -> Self

Creates a new empty Grove.

Examples

use once::Grove;

let grove = Grove::<i32>::new();

fn locate(&self, index: usize) -> (usize, usize)

Finds the block and offset within the block for the given index.

This is an internal method used to determine which block contains the element at the specified index and the offset within that block.

Parameters

• index: The index to locate

Returns

A tuple containing the block number and the offset within that block.

fn ensure_init(&self, block_num: usize)

Ensures that the specified block is initialized.

This is an internal method that initializes a block if it hasn’t been initialized yet. It is called before any operation that needs to access a block.

Parameters

• block_num: The block number to initialize

pub fn insert(&self, index: usize, value: T)

Inserts a value at the specified index.

This operation is thread-safe and can be called from multiple threads. However, this method panics if a value already exists at the specified index. Therefore, it should only be called at most once for any given index.

Parameters

• index: The index at which to insert the value
• value: The value to insert

Examples

use once::Grove;

let grove = Grove::<i32>::new();
grove.insert(0, 10);
grove.insert(100, 20);

pub fn try_insert(&self, index: usize, value: T) -> Result<(), T>

Attempts to insert a value at the specified index.

This method will only insert the value if the index is not already occupied. If the index is already occupied, the value is returned in the Err variant.

Parameters

• index: The index at which to insert the value
• value: The value to insert

Returns

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

Examples

use once::Grove;

let grove = Grove::<i32>::new();
assert_eq!(grove.try_insert(0, 10), Ok(()));
assert_eq!(grove.try_insert(0, 20), Err(20)); // Index already occupied

pub fn get(&self, index: usize) -> Option<&T>

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

Parameters

• index: The index of the value to retrieve

Returns

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

Examples

use once::Grove;

let grove = Grove::<i32>::new();
grove.insert(0, 10);

assert_eq!(grove.get(0), Some(&10));
assert_eq!(grove.get(1), None);

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

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

This method can only be called if we have an exclusive reference to self, which may not be very common in practice. However, it is useful for Drop implementations.

Parameters

• index: The index of the value to retrieve

Returns

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

Examples

use once::Grove;

let mut grove = Grove::<i32>::new();
grove.insert(0, 10);

if let Some(value) = grove.get_mut(0) {
    *value = 20;
}

assert_eq!(grove.get(0), Some(&20));

pub unsafe fn get_unchecked(&self, index: usize) -> &T

Retrieves a reference to the value at the specified index without checking that a value exists.

Safety

A value must have been previously inserted at the specified index.

pub fn is_set(&self, index: usize) -> bool

Checks if a value exists at the specified index.

Parameters

• index: The index to check

Returns

true if a value exists at the specified index, false otherwise.

Examples

use once::Grove;

let grove = Grove::<i32>::new();
grove.insert(0, 10);

assert!(grove.is_set(0));
assert!(!grove.is_set(1));

pub fn len(&self) -> usize

Returns the length of the Grove.

The length is defined as the maximum index that has been inserted into the Grove plus one. Note that this does not necessarily reflect the number of elements in the Grove, as there may be gaps. Also, since this is a wait-free data structure, the return value may not be accurate, but it will always be a lower bound for the true length from the perspective of any thread.

Returns

The length of the Grove.

Examples

use once::Grove;

let grove = Grove::<i32>::new();
grove.insert(0, 10);
grove.insert(5, 20);

assert_eq!(grove.len(), 6); // 5 + 1

pub fn is_empty(&self) -> bool

pub fn from_vec(v: Vec<T>) -> Self

Creates a Grove from a Vec.

The elements in the vector will be inserted into the Grove at their respective indices.

Parameters

• v: The vector to convert

Returns

A new Grove containing the elements from the vector.

Examples

use once::Grove;

let vec = vec![10, 20, 30];
let grove = Grove::from_vec(vec);

assert_eq!(grove.get(0), Some(&10));
assert_eq!(grove.get(1), Some(&20));
assert_eq!(grove.get(2), Some(&30));

pub fn iter(&self) -> Iter<'_, T>

Returns an iterator over the index-value pairs in the Grove.

The iterator yields pairs in order of their indices, from 0 to len() - 1. Indices that don’t have a value are skipped.

Returns

An iterator over (usize, &T) pairs in the Grove.

Examples

use once::Grove;

let grove = Grove::<i32>::new();
grove.insert(0, 10);
grove.insert(2, 30);

let entries: Vec<_> = grove.iter().collect();
assert_eq!(entries, vec![(0, &10), (2, &30)]);

pub fn iter_mut(&mut self) -> impl Iterator<Item = (usize, &mut T)>

pub fn values(&self) -> Values<'_, T>

Returns an iterator over the values in the Grove.

The iterator yields values in order of their indices, from 0 to len() - 1. Indices that don’t have a value are skipped.

Returns

An iterator over the values in the Grove.

Examples

use once::Grove;

let grove = Grove::<i32>::new();
grove.insert(0, 10);
grove.insert(2, 30);

let values: Vec<_> = grove.values().collect();
assert_eq!(values, vec![&10, &30]);

Trait Implementations

impl<T: Clone> Clone for Grove<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for Grove<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for Grove<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Hash> Hash for Grove<T>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T> Index<usize> for Grove<T>

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for Grove<T>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'a, T> IntoIterator for &'a Grove<T>

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

type Item = (usize, &'a T)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for Grove<T>

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

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for Grove<T>