Struct PersistentVec 

pub struct PersistentVec<T> { /* private fields */ }

A persistent vector with structural sharing. Clone is O(1) (bumps the root Arc); push is amortised O(log₃₂ N) and only allocates fresh nodes along the spine from the root to the affected leaf.

Implementations

impl<T> PersistentVec<T>

pub fn new() -> Self

Empty vector. Allocates one empty Internal root and one empty tail Vec; both are shared across every empty PV via Arc::clone once the first one is built. The shape matches a shift = SHIFT trie so the incorporate path never has to grow the root type.

pub const fn len(&self) -> usize

pub const fn is_empty(&self) -> bool

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

O(log₃₂ N). None for out-of-bounds. Returned reference is valid for the lifetime of &self; structural sharing means the borrow is independent of any other handle that shares the same spine.

pub fn run_containing(&self, i: usize) -> Option<(usize, &[T])>

v7.39 (round 562) — the contiguous run holding i, with the index i sits at inside it, so a caller reading ascending indices can keep the run and descend once per leaf instead of once per element.

This is what iter already does; run_at’s own comment says so. It was private, so a caller that reads BY INDEX — an index-only scan checking one header per matching row — had no way to say it, and paid a descent per row for elements 32 to a leaf.

Returns (start, run): run[i - start] is element i, and the run covers start .. start + run.len().

pub const fn run_cursor(&self) -> RunCursor<'_, T>

v7.39 (round 567) — a cursor that holds the run it last descended to, for a caller reading many elements by ascending index.

Indexing is O(log₃₂ N) — four dependent loads over 500k elements — and a scan that reads every row pays it every row. A leaf holds 32, so keeping it between reads makes that one descent per 32. Ask for a scattered index and it descends, exactly as get would.

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

Sequential iterator, walking a leaf at a time.

v7.39 (round 486) — this used to call get per element, so every scan in the engine paid a full trie descent (a chain of Arc dereferences) for each row it read. The v4.38 comment here said “v4.39 / v4.40 will profile and upgrade if iter shows up as the bottleneck”; it showed up — is_row_visible plus the scan’s own row reads were 17 % of big_in’s profile, both of them descents. One descent now serves up to BRANCH elements.

impl<T: Clone> PersistentVec<T>

pub fn push(&self, x: T) -> Self

O(log₃₂ N) path-copy push. Returns a new handle; self is untouched (structural sharing means the old handle and the new one share every internal node except the spine to the newly written tail / leaf).

pub fn push_mut(&mut self, x: T)

O(1) amortized — transient in-place push. v4.39.1 perf path for the Table::insert hot loop (and any other streaming caller that holds a &mut PersistentVec). Uses Arc::make_mut on the tail buffer: when the tail’s Arc is uniquely owned (the common case), this mutates in place — same cost as Vec::push. If a cloned handle is outstanding (e.g. inside a TX wrap holding a Catalog snapshot), the tail is path- copied just like push and the snapshot is unaffected. Either way, callers observe the same end state as self = self.push(x).

pub fn set(&self, i: usize, x: T) -> Option<Self>

O(log₃₂ N) path-copy set. None for out-of-bounds (matches get). Result shares every node except the spine to the rewritten cell.

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

O(log₃₂ N) transient-mut access — the read-side analogue of push_mut (v5.5.0). Walks the spine with Arc::make_mut: when every node along the path is uniquely owned (the common streaming case) the walk mutates in place at the same cost as Vec::get_mut. If a cloned handle shares the spine (e.g. a Catalog snapshot held by an open TX), the touched nodes are path-copied — the snapshot keeps its old value and only this handle observes the mutation, exactly like set. None for out-of-bounds (matches get / set).

Introduced for the v5.5 HNSW NswGraph switch to PV-backed layers: the insert path needs in-place edits to a node’s neighbour list (layers[l].get_mut(node)) without the set-then-write-back round trip and its extra path-copy.

Trait Implementations

impl<T> Clone for PersistentVec<T>

fn clone(&self) -> Self

O(1) — only Arc bumps, no element copy. This is the whole reason PV exists in v4.38; Catalog::clone in v4.39 inherits the property.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for PersistentVec<T>

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

Formats the value using the given formatter.

impl<T> Default for PersistentVec<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Eq> Eq for PersistentVec<T>

impl<T> Index<usize> for PersistentVec<T>

pv[i] indexing, matching Vec<T>::index’s contract: panics on out-of-bounds. v4.39 lets table.rows[i] work unchanged on the new PV-backed Table for the price of one extra O(log₃₂ N) walk per lookup (vs Vec’s O(1)). Callers in a hot loop should hoist the trie walk where possible (let row = pv.get(i)?;) instead of re-indexing.

type Output = T

The returned type after indexing.

fn index(&self, i: usize) -> &T

Performs the indexing (container[index]) operation.

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

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for PersistentVec<T>

Element-wise equality: two PVs are equal iff they yield the same elements in the same order. Independent of internal trie shape — two PVs built via different push / set sequences with the same end state still compare equal. Used by Catalog::serialize round-trip tests in v4.39+.

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

Equality operator ==.

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

Inequality operator !=.