Struct Arena 

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

An Arena structure containing certain [Node]s.

With the serde feature, deserialization fails if the arena does not pass Arena::validate.

Implementations

impl<T> Arena<T>

pub const fn new() -> Arena<T>

Creates a new empty Arena.

pub fn with_capacity(n: usize) -> Arena<T>

Creates a new empty Arena with enough capacity to store n nodes.

Examples

let arena: Arena<i32> = Arena::with_capacity(10);
assert!(arena.capacity() >= 10);

pub fn capacity(&self) -> usize

Returns the number of nodes the arena can hold without reallocating.

Examples

let arena: Arena<i32> = Arena::with_capacity(10);
assert!(arena.capacity() >= 10);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for additional more nodes to be inserted.

The arena may reserve more space to avoid frequent reallocations.

Panics

Panics if the new capacity exceeds isize::MAX bytes.

Examples

let mut arena: Arena<i32> = Arena::new();
arena.reserve(100);
assert!(arena.capacity() >= 100);

pub fn get_node_id(&self, node: &Node<T>) -> Option<NodeId>

Retrieves the NodeId corresponding to a Node in the Arena.

Returns None if the node is not stored in this arena or was removed.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let node = arena.get(foo).unwrap();

let node_id = arena.get_node_id(node).unwrap();
assert_eq!(*arena[node_id].get(), "foo");

pub fn get_node_id_at(&self, index: NonZero<usize>) -> Option<NodeId>

Retrieves the NodeId corresponding to the Node at index in the Arena, if it exists.

Note: We use 1 based indexing, so the first element is at 1 and not 0.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let node = arena.get(foo).unwrap();
let index: NonZeroUsize = foo.into();

let new_foo = arena.get_node_id_at(index).unwrap();
assert_eq!(foo, new_foo);

foo.remove(&mut arena);
let new_foo = arena.get_node_id_at(index);
assert!(new_foo.is_none(), "must be none if the node at the index doesn't exist");

pub fn new_node(&mut self, data: T) -> NodeId

Creates a new node from its associated data.

Freed slots are reused when available. If a slot’s internal stamp has been exhausted (after ~32K remove/reuse cycles), it is skipped and a fresh slot is appended instead.

Panics

Panics if the arena already has usize::max_value() nodes.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");

assert_eq!(*arena[foo].get(), "foo");

pub fn count(&self) -> usize

👎Deprecated since 4.9.0:

use len() instead

Returns the number of slots in the arena, including removed nodes.

Removed nodes are still counted because they remain in the internal storage. Use live_count() to count only live nodes.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let _bar = arena.new_node("bar");
assert_eq!(arena.count(), 2);
assert_eq!(arena.len(), 2);

foo.remove(&mut arena);
// The removed node is still counted.
assert_eq!(arena.count(), 2);
assert_eq!(arena.len(), 2);

pub fn len(&self) -> usize

Returns the number of slots in the arena, including removed nodes.

Removed nodes are still counted because they remain in the internal storage. Use live_count() to count only live nodes.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let _bar = arena.new_node("bar");
assert_eq!(arena.len(), 2);

foo.remove(&mut arena);
// The removed node is still counted.
assert_eq!(arena.len(), 2);

pub fn is_empty(&self) -> bool

Returns true if arena has no slots, false otherwise.

Like len(), this takes removed nodes into account, so an arena whose nodes have all been removed is not empty. Check live_count() for zero to test for live nodes.

Examples

let mut arena = Arena::new();
assert!(arena.is_empty());

let foo = arena.new_node("foo");
assert!(!arena.is_empty());

foo.remove(&mut arena);
assert!(!arena.is_empty());

pub fn get(&self, id: NodeId) -> Option<&Node<T>>

Returns a reference to the node with the given id if in the arena.

Returns None if the index is out of bounds or the node’s stamp does not match (i.e. the slot was removed and possibly reused).

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
assert_eq!(arena.get(foo).map(|node| *node.get()), Some("foo"));

Stale NodeIds from removed nodes return None:

let mut arena = Arena::new();
let foo = arena.new_node("foo");
foo.remove(&mut arena);
assert!(arena.get(foo).is_none());

pub fn get_mut(&mut self, id: NodeId) -> Option<&mut Node<T>>

Returns a mutable reference to the node with the given id if in the arena.

Returns None if the index is out of bounds or the node’s stamp does not match.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
assert_eq!(arena.get(foo).map(|node| *node.get()), Some("foo"));

*arena.get_mut(foo).expect("The `foo` node exists").get_mut() = "FOO!";
assert_eq!(arena.get(foo).map(|node| *node.get()), Some("FOO!"));

pub fn get_data(&self, id: NodeId) -> Option<&T>

Returns a reference to the data of the node with the given id.

Returns None if the id is out of bounds, the stamp doesn’t match, or the node has been removed.

This is a shorthand for arena.get(id).map(|n| n.get()).

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
assert_eq!(arena.get_data(foo), Some(&"foo"));

foo.remove(&mut arena);
assert_eq!(arena.get_data(foo), None);

pub fn get_data_mut(&mut self, id: NodeId) -> Option<&mut T>

Returns a mutable reference to the data of the node with the given id.

Returns None if the id is out of bounds, the stamp doesn’t match, or the node has been removed.

This is a shorthand for arena.get_mut(id).map(|n| n.get_mut()).

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
*arena.get_data_mut(foo).unwrap() = "bar";
assert_eq!(arena.get_data(foo), Some(&"bar"));

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

Returns an iterator of all nodes in the arena in storage-order.

Note that this iterator returns also removed elements, which can be tested with the is_removed() method on the node.

To iterate over only live nodes by their NodeId, use iter_node_ids() instead.

Examples

let mut arena = Arena::new();
let _foo = arena.new_node("foo");
let _bar = arena.new_node("bar");

let mut iter = arena.iter();
assert_eq!(iter.next().map(|node| *node.get()), Some("foo"));
assert_eq!(iter.next().map(|node| *node.get()), Some("bar"));
assert_eq!(iter.next().map(|node| *node.get()), None);

let mut arena = Arena::new();
let _foo = arena.new_node("foo");
let bar = arena.new_node("bar");
bar.remove(&mut arena);

let mut iter = arena.iter();
assert_eq!(iter.next().map(|node| (*node.get(), node.is_removed())), Some(("foo", false)));
assert_eq!(iter.next().map_or(false, |node| node.is_removed()), true);
assert_eq!(iter.next().map(|node| (*node.get(), node.is_removed())), None);

pub fn iter_node_ids(&self) -> impl Iterator<Item = NodeId>

Returns an iterator of NodeIds of all non-removed nodes in the arena in storage-order.

Unlike iter(), this skips removed nodes and yields NodeIds instead of &Node<T>.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let bar = arena.new_node("bar");
let baz = arena.new_node("baz");
bar.remove(&mut arena);

let ids: Vec<_> = arena.iter_node_ids().collect();
assert_eq!(ids, vec![foo, baz]);

pub fn iter_mut(&mut self) -> IterMut<'_, Node<T>>

Returns a mutable iterator of all nodes in the arena in storage-order.

Note that this iterator returns also removed elements, which can be tested with the is_removed() method on the node.

Example

let arena: &mut Arena<i64> = &mut Arena::new();
let a = arena.new_node(1);
let b = arena.new_node(2);
assert!(a.checked_append(b, arena).is_ok());

for node in arena.iter_mut() {
    let data = node.get_mut();
    *data = data.wrapping_add(4);
}

let node_refs = arena.iter().map(|i| i.get().clone()).collect::<Vec<_>>();
assert_eq!(node_refs, vec![5, 6]);

pub fn roots(&self) -> impl Iterator<Item = NodeId>

Returns an iterator of NodeIds of all root nodes (nodes with no parent) that are not removed.

Examples

let mut arena = Arena::new();
let a = arena.new_node("a");
let b = arena.new_node("b");
let c = arena.new_node("c");
a.append(c, &mut arena);

let roots: Vec<_> = arena.roots().collect();
assert_eq!(roots, vec![a, b]);

pub fn map<U>(&self, f: impl FnMut(&T) -> U) -> Arena<U>

Creates a new arena by applying a function to the data of every live node, preserving the tree structure.

Removed nodes remain as removed slots in the new arena to keep node indices consistent.

Examples

let mut arena = Arena::new();
let root = arena.new_node(1);
let child = root.append_value(2, &mut arena);

let mapped: Arena<String> = arena.map(|x| x.to_string());
assert_eq!(mapped.get_data(root), Some(&"1".to_string()));
assert_eq!(mapped.get_data(child), Some(&"2".to_string()));
assert_eq!(mapped[child].parent(), Some(root));

pub fn shrink_to_fit(&mut self)

Shrinks the internal storage to fit the current number of nodes.

Calls Vec::shrink_to_fit on the underlying node storage.

pub fn live_count(&self) -> usize

Returns the number of live (non-removed) nodes in the arena.

This is O(1). The count is maintained by the arena, so it can be off after replacing whole nodes through IndexMut, Arena::iter_mut or par_iter_mut, e.g. by swapping nodes between arenas. For the total slot count (including removed nodes), use len().

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let bar = arena.new_node("bar");
assert_eq!(arena.live_count(), 2);

foo.remove(&mut arena);
assert_eq!(arena.live_count(), 1);
assert_eq!(arena.len(), 2);

pub fn clear(&mut self)

Clears all the nodes in the arena, but retains its allocated capacity.

Note that this does not mark all nodes as removed, but completely removes them from the arena storage, so all previously created node IDs must no longer be used.

After clearing, NodeId::is_removed returns true for any previously created ID (without panicking), and Arena::get returns None, until new nodes are created. Since the slots and their stamps are discarded, new nodes reuse the indices and initial stamps of the cleared ones, so an old ID may then refer to a new node. Discard all IDs of the cleared arena, or remove the nodes with NodeId::remove_subtree instead to keep stale IDs detectable.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
arena.clear();
assert!(arena.is_empty());
assert!(foo.is_removed(&arena));

pub fn as_slice(&self) -> &[Node<T>]

Returns a slice of the inner nodes collection.

The slice contains all nodes in storage order, including removed nodes. Use Node::is_removed() to filter them out.

Examples

let mut arena = Arena::new();
arena.new_node("foo");
arena.new_node("bar");
assert_eq!(arena.as_slice().len(), 2);

pub fn validate(&self) -> bool

Validates the internal consistency of the arena’s tree structure.

Returns true if the arena passes all of the following checks:

• Every live node contains actual data (not a free-list entry).
• Parent, previous/next sibling, and first/last child pointers all refer to valid, non-removed nodes with matching stamps.
• first_child and last_child are both set or both unset.
• Sibling back-pointers are reciprocal (prev’s next == self, next’s prev == self), and siblings share the same parent.
• Every child in a parent’s child chain points back to that parent, and the chain ends at last_child.
• Every live node is reachable exactly once from a root sibling chain, which rules out cycles in parent and sibling links.
• The free list is well-formed: consistent first/last pointers, all entries are removed nodes with NextFree data, and no cycles.

Deserialization (with the serde feature) already runs this check. It is useful to verify an arena after modifying nodes directly, e.g. through IndexMut or Arena::iter_mut.

Examples

let mut arena = Arena::new();
let root = arena.new_node(1);
root.append_value(2, &mut arena);
assert!(arena.validate());

Trait Implementations

impl<T> Clone for Arena<T>

where T: Clone,

fn clone(&self) -> Arena<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for Arena<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for Arena<T>

fn default() -> Arena<T>

Returns the “default value” for a type.

impl<T> Eq for Arena<T>

where T: Eq,

impl<T> Extend<T> for Arena<T>

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = T>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<T> for Arena<T>

fn from_iter<I>(iter: I) -> Arena<T>

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<T> Index<NodeId> for Arena<T>

Index by NodeId for convenient arena[id] access.

Unlike Arena::get, this does not validate the node’s stamp, so it may silently return data from a reused slot if the NodeId is stale. For safe access, prefer Arena::get or Arena::get_mut.

Panics

Panics if node is out of bounds. Note that indexing does not validate that the NodeId originated from this arena. Using an ID from a different arena may silently access the wrong node or panic.

type Output = Node<T>

The returned type after indexing.

fn index(&self, node: NodeId) -> &Node<T>

Performs the indexing (container[index]) operation.

impl<T> IndexMut<NodeId> for Arena<T>

Mutable index by NodeId.

Like Index<NodeId>, this does not validate the node’s stamp. For safe access, prefer Arena::get_mut.

Panics

Panics if node is out of bounds.

fn index_mut(&mut self, node: NodeId) -> &mut Node<T>

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

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

type Item = &'a Node<T>

The type of the elements being iterated over.

type IntoIter = Iter<'a, Node<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <&'a Arena<T> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut Arena<T>

type Item = &'a mut Node<T>

The type of the elements being iterated over.

type IntoIter = IterMut<'a, Node<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <&'a mut Arena<T> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for Arena<T>

Consumes the arena, returning an iterator over all nodes (including removed ones).

type Item = Node<T>

The type of the elements being iterated over.

type IntoIter = IntoIter<Node<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <Arena<T> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<T> PartialEq for Arena<T>

where T: PartialEq,

fn eq(&self, other: &Arena<T>) -> bool

Equality operator ==.

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

Inequality operator !=.