Struct ostd::collections::xarray::XArray

pub struct XArray<I, M = NoneMark>
where
    I: ItemEntry,
    M: Into<XMark>,
{ /* private fields */ }

XArray is an abstract data type functioning like an expansive array of items where each item must be an 8-byte object, such as Arc<T> or Box<T>.

User-stored pointers must have a minimum alignment of 4 bytes. XArray facilitates efficient sequential access to adjacent entries, supporting multiple concurrent reads and exclusively allowing one write operation at a time.

Features

Copy-on-write (COW): If items within XArray implement the Clone trait, cloning can leverage a COW mechanism. A clone of an XArray initially shares the head node with the original, avoiding immediate deep copying. If a mutable operation is required on either XArray, a deep copy of the relevant nodes is made first, ensuring isolated operations.

Cursors: Interaction with XArray is mediated through Cursor and CursorMut. A Cursor requires an immutable reference, while CursorMut requires a mutable reference. As such, multiple Cursor instances can coexist, but CursorMut operations are singular, reflecting the behavior of shared (&) and exclusive (&mut) references. Cursors offer precise index positioning and traversal capabilities in the XArray.

Marking: XArray enables marking of individual items or the XArray itself for user convenience. Items and the XArray can have up to three distinct marks by default, with each mark independently maintained. Users can use self-defined types as marks by implementing the From<Type> trait for XMark. Marking is also applicable to internal nodes, indicating marked descendant nodes, though such marking is not transparent to users.

Example

use std::sync::Arc;
use std::sync::{Mutex, MutexGuard};
use xarray::*;

let mut xarray_arc: XArray<Arc<i32>> = XArray::new();
let value = Arc::new(10);
xarray_arc.store(10, value);
assert!(*xarray_arc.load(10).unwrap().as_ref() == 10);

let mut xarray_clone = xarray_arc.clone();
assert!(*xarray_clone.load(10).unwrap().as_ref() == 10);
let value = Arc::new(100);
xarray_clone.store(10, value);

assert!(*xarray_arc.load(10).unwrap().as_ref() == 10);
assert!(*xarray_clone.load(10).unwrap().as_ref() == 100);

The XArray concept was originally introduced by Linux, which keeps the data structure of Linux Radix Trees.

Implementations

impl<I, M> XArray<I, M>

where I: ItemEntry, M: Into<XMark>,

pub const fn new() -> XArray<I, M>

Makes a new, empty XArray.

pub fn set_mark(&mut self, mark: M)

Marks the XArray with the input mark.

pub fn unset_mark(&mut self, mark: M)

Unsets the input mark for the XArray.

pub fn is_marked(&self, mark: M) -> bool

Checks whether the XArray is marked with the input mark.

pub fn load(&self, index: u64) -> Option<<I as ItemEntry>::Ref<'_>>

Loads the index-th item.

If the target item exists, it will be returned with Some(_), otherwise, None will be returned.

pub fn store(&mut self, index: u64, item: I) -> Option<I>

Stores the provided item in the XArray at the target index, and returns the old item if some item was previously stored in the same position.

pub fn unset_mark_all(&mut self, mark: M)

Unsets the input mark for all of the items in the XArray.

pub fn remove(&mut self, index: u64) -> Option<I>

Removes the XEntry in the XArray at the target index, and returns the removed item if some item was previously stored in the same position.

pub fn cursor(&self, index: u64) -> Cursor<'_, I, M>

Creates a Cursor to perform read-related operations in the XArray.

pub fn cursor_mut(&mut self, index: u64) -> CursorMut<'_, I, M>

Creates a CursorMut to perform read- and write-related operations in the XArray.

pub fn range(&self, range: Range<u64>) -> Range<'_, I, M>

Creates a Range which can be immutably iterated over the indexes corresponding to the specified range.

Trait Implementations

impl<I, M> Clone for XArray<I, M>

where I: ItemEntry + Clone, M: Into<XMark>,

fn clone(&self) -> XArray<I, M>

Clones the XArray with the COW mechanism.

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

Performs copy-assignment from source.