Struct btree_vec::BTreeVec

pub struct BTreeVec<T, const B: usize = 12> { /* private fields */ }

A growable array (vector) implemented as a B+ tree.

Provides non-amortized O(log n) random accesses, insertions, and removals, and O(n) iteration.

B is the branching factor. It must be at least 3. The standard library uses a value of 6 for its B-tree structures. Larger values are better when T is smaller.

Implementations

impl<T> BTreeVec<T>

pub fn new() -> Self

Creates a new BTreeVec. Note that this function is implemented only for the default value of B; see Self::create for an equivalent that works with all values of B.

impl<T, const B: usize> BTreeVec<T, B>

pub fn create() -> Self

Creates a new BTreeVec. This function exists because BTreeVec::new is implemented only for the default value of B.

Examples found in repository

src/lib.rs (line 153)

    pub fn new() -> Self {
        Self::create()
    }
}

impl<T, const B: usize> BTreeVec<T, B> {
    /// Creates a new [`BTreeVec`]. This function exists because
    /// [`BTreeVec::new`] is implemented only for the default value of `B`.
    pub fn create() -> Self {
        assert!(B >= 3);
        Self {
            root: None,
            size: 0,
            phantom: PhantomData,
        }
    }

    /// # Safety
    ///
    /// * There must not be any mutable references, including other
    ///   [`NodeRef`]s where `R` is [`Mutable`], to any data accessible via the
    ///   returned [`NodeRef`].
    ///
    /// [`Mutable`]: node::Mutable
    unsafe fn leaf_for(&self, index: usize) -> (LeafRef<T, B>, usize) {
        // SAFETY: Caller guarantees safety.
        leaf_for(unsafe { NodeRef::new(self.root.unwrap()) }, index)
    }

    /// # Safety
    ///
    /// There must be no other references, including [`NodeRef`]s, to any data
    /// accessible via the returned [`NodeRef`].
    unsafe fn leaf_for_mut(
        &mut self,
        index: usize,
    ) -> (LeafRef<T, B, Mutable>, usize) {
        // SAFETY: Caller guarantees safety.
        leaf_for(unsafe { NodeRef::new_mutable(self.root.unwrap()) }, index)
    }

    /// Gets the length of the vector.
    pub fn len(&self) -> usize {
        self.size
    }

    /// Checks whether the vector is empty.
    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    /// Gets the item at `index`, or [`None`] if no such item exists.
    pub fn get(&self, index: usize) -> Option<&T> {
        (index < self.size).then(|| {
            // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with
            // standard borrowing rules, so there are no existing mutable
            // references.
            let (leaf, index) = unsafe { self.leaf_for(index) };
            leaf.into_child(index)
        })
    }

    /// Gets a mutable reference to the item at `index`, or [`None`] if no such
    /// item exists.
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        (index < self.size).then(|| {
            // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with
            // standard borrowing rules, so there are no existing references.
            let (leaf, index) = unsafe { self.leaf_for_mut(index) };
            leaf.into_child_mut(index)
        })
    }

    /// Gets the first item in the vector, or [`None`] if the vector is empty.
    pub fn first(&self) -> Option<&T> {
        self.get(0)
    }

    /// Gets a mutable reference to the first item in the vector, or [`None`]
    /// if the vector is empty.
    pub fn first_mut(&mut self) -> Option<&mut T> {
        self.get_mut(0)
    }

    /// Gets the last item in the vector, or [`None`] if the vector is empty.
    pub fn last(&self) -> Option<&T> {
        self.size.checked_sub(1).and_then(|s| self.get(s))
    }

    /// Gets a mutable reference to the last item in the vector, or [`None`] if
    /// the vector is empty.
    pub fn last_mut(&mut self) -> Option<&mut T> {
        self.size.checked_sub(1).and_then(move |s| self.get_mut(s))
    }

    /// Inserts `item` at `index`.
    ///
    /// # Panics
    ///
    /// Panics if `index` is greater than [`self.len()`](Self::len).
    pub fn insert(&mut self, index: usize, item: T) {
        assert!(index <= self.size);
        self.root
            .get_or_insert_with(|| LeafRef::alloc().into_prefix().as_ptr());
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing references.
        let (leaf, index) = unsafe { self.leaf_for_mut(index) };
        let root = insert(leaf, index, item, self.size);
        self.root = Some(root.as_ptr());
        self.size += 1;
    }

    /// Inserts `item` at the end of the vector.
    pub fn push(&mut self, item: T) {
        self.insert(self.size, item);
    }

    /// Removes and returns the item at `index`.
    ///
    /// # Panics
    ///
    /// Panics if `index` is not less than [`self.len()`](Self::len).
    pub fn remove(&mut self, index: usize) -> T {
        assert!(index < self.size);
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with
        // standard borrowing rules, so there are no existing references.
        let (leaf, index) = unsafe { self.leaf_for_mut(index) };
        let (root, item) = remove(leaf, index);
        self.root = Some(root.as_ptr());
        self.size -= 1;
        item
    }

    /// Removes and returns the last item in the vector, or [`None`] if the
    /// vector is empty.
    pub fn pop(&mut self) -> Option<T> {
        self.size.checked_sub(1).map(|s| self.remove(s))
    }

    /// Gets an iterator that returns references to each item in the vector.
    pub fn iter(&self) -> Iter<'_, T, B> {
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing mutable references.
        Iter {
            leaf: self.root.map(|_| unsafe { self.leaf_for(0) }.0),
            index: 0,
            phantom: PhantomData,
        }
    }

    /// Gets an iterator that returns mutable references to each item in the
    /// vector.
    pub fn iter_mut(&mut self) -> IterMut<'_, T, B> {
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing references.
        IterMut {
            leaf: self.root.map(|_| unsafe { self.leaf_for_mut(0) }.0),
            index: 0,
            phantom: PhantomData,
        }
    }
}

impl<T, const B: usize> Default for BTreeVec<T, B> {
    fn default() -> Self {
        Self::create()
    }

pub fn len(&self) -> usize

Gets the length of the vector.

pub fn is_empty(&self) -> bool

Checks whether the vector is empty.

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

Gets the item at index, or None if no such item exists.

Examples found in repository

src/lib.rs (line 227)

    pub fn first(&self) -> Option<&T> {
        self.get(0)
    }

    /// Gets a mutable reference to the first item in the vector, or [`None`]
    /// if the vector is empty.
    pub fn first_mut(&mut self) -> Option<&mut T> {
        self.get_mut(0)
    }

    /// Gets the last item in the vector, or [`None`] if the vector is empty.
    pub fn last(&self) -> Option<&T> {
        self.size.checked_sub(1).and_then(|s| self.get(s))
    }

    /// Gets a mutable reference to the last item in the vector, or [`None`] if
    /// the vector is empty.
    pub fn last_mut(&mut self) -> Option<&mut T> {
        self.size.checked_sub(1).and_then(move |s| self.get_mut(s))
    }

    /// Inserts `item` at `index`.
    ///
    /// # Panics
    ///
    /// Panics if `index` is greater than [`self.len()`](Self::len).
    pub fn insert(&mut self, index: usize, item: T) {
        assert!(index <= self.size);
        self.root
            .get_or_insert_with(|| LeafRef::alloc().into_prefix().as_ptr());
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing references.
        let (leaf, index) = unsafe { self.leaf_for_mut(index) };
        let root = insert(leaf, index, item, self.size);
        self.root = Some(root.as_ptr());
        self.size += 1;
    }

    /// Inserts `item` at the end of the vector.
    pub fn push(&mut self, item: T) {
        self.insert(self.size, item);
    }

    /// Removes and returns the item at `index`.
    ///
    /// # Panics
    ///
    /// Panics if `index` is not less than [`self.len()`](Self::len).
    pub fn remove(&mut self, index: usize) -> T {
        assert!(index < self.size);
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with
        // standard borrowing rules, so there are no existing references.
        let (leaf, index) = unsafe { self.leaf_for_mut(index) };
        let (root, item) = remove(leaf, index);
        self.root = Some(root.as_ptr());
        self.size -= 1;
        item
    }

    /// Removes and returns the last item in the vector, or [`None`] if the
    /// vector is empty.
    pub fn pop(&mut self) -> Option<T> {
        self.size.checked_sub(1).map(|s| self.remove(s))
    }

    /// Gets an iterator that returns references to each item in the vector.
    pub fn iter(&self) -> Iter<'_, T, B> {
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing mutable references.
        Iter {
            leaf: self.root.map(|_| unsafe { self.leaf_for(0) }.0),
            index: 0,
            phantom: PhantomData,
        }
    }

    /// Gets an iterator that returns mutable references to each item in the
    /// vector.
    pub fn iter_mut(&mut self) -> IterMut<'_, T, B> {
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing references.
        IterMut {
            leaf: self.root.map(|_| unsafe { self.leaf_for_mut(0) }.0),
            index: 0,
            phantom: PhantomData,
        }
    }
}

impl<T, const B: usize> Default for BTreeVec<T, B> {
    fn default() -> Self {
        Self::create()
    }
}

impl<T, const B: usize> Index<usize> for BTreeVec<T, B> {
    type Output = T;

    fn index(&self, index: usize) -> &T {
        self.get(index).unwrap()
    }

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

Gets a mutable reference to the item at index, or None if no such item exists.

Examples found in repository

src/lib.rs (line 233)

    pub fn first_mut(&mut self) -> Option<&mut T> {
        self.get_mut(0)
    }

    /// Gets the last item in the vector, or [`None`] if the vector is empty.
    pub fn last(&self) -> Option<&T> {
        self.size.checked_sub(1).and_then(|s| self.get(s))
    }

    /// Gets a mutable reference to the last item in the vector, or [`None`] if
    /// the vector is empty.
    pub fn last_mut(&mut self) -> Option<&mut T> {
        self.size.checked_sub(1).and_then(move |s| self.get_mut(s))
    }

    /// Inserts `item` at `index`.
    ///
    /// # Panics
    ///
    /// Panics if `index` is greater than [`self.len()`](Self::len).
    pub fn insert(&mut self, index: usize, item: T) {
        assert!(index <= self.size);
        self.root
            .get_or_insert_with(|| LeafRef::alloc().into_prefix().as_ptr());
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing references.
        let (leaf, index) = unsafe { self.leaf_for_mut(index) };
        let root = insert(leaf, index, item, self.size);
        self.root = Some(root.as_ptr());
        self.size += 1;
    }

    /// Inserts `item` at the end of the vector.
    pub fn push(&mut self, item: T) {
        self.insert(self.size, item);
    }

    /// Removes and returns the item at `index`.
    ///
    /// # Panics
    ///
    /// Panics if `index` is not less than [`self.len()`](Self::len).
    pub fn remove(&mut self, index: usize) -> T {
        assert!(index < self.size);
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with
        // standard borrowing rules, so there are no existing references.
        let (leaf, index) = unsafe { self.leaf_for_mut(index) };
        let (root, item) = remove(leaf, index);
        self.root = Some(root.as_ptr());
        self.size -= 1;
        item
    }

    /// Removes and returns the last item in the vector, or [`None`] if the
    /// vector is empty.
    pub fn pop(&mut self) -> Option<T> {
        self.size.checked_sub(1).map(|s| self.remove(s))
    }

    /// Gets an iterator that returns references to each item in the vector.
    pub fn iter(&self) -> Iter<'_, T, B> {
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing mutable references.
        Iter {
            leaf: self.root.map(|_| unsafe { self.leaf_for(0) }.0),
            index: 0,
            phantom: PhantomData,
        }
    }

    /// Gets an iterator that returns mutable references to each item in the
    /// vector.
    pub fn iter_mut(&mut self) -> IterMut<'_, T, B> {
        // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with standard
        // borrowing rules, so there are no existing references.
        IterMut {
            leaf: self.root.map(|_| unsafe { self.leaf_for_mut(0) }.0),
            index: 0,
            phantom: PhantomData,
        }
    }
}

impl<T, const B: usize> Default for BTreeVec<T, B> {
    fn default() -> Self {
        Self::create()
    }
}

impl<T, const B: usize> Index<usize> for BTreeVec<T, B> {
    type Output = T;

    fn index(&self, index: usize) -> &T {
        self.get(index).unwrap()
    }
}

impl<T, const B: usize> IndexMut<usize> for BTreeVec<T, B> {
    fn index_mut(&mut self, index: usize) -> &mut T {
        self.get_mut(index).unwrap()
    }

pub fn first(&self) -> Option<&T>

Gets the first item in the vector, or None if the vector is empty.

pub fn first_mut(&mut self) -> Option<&mut T>

Gets a mutable reference to the first item in the vector, or None if the vector is empty.

pub fn last(&self) -> Option<&T>

Gets the last item in the vector, or None if the vector is empty.

pub fn last_mut(&mut self) -> Option<&mut T>

Gets a mutable reference to the last item in the vector, or None if the vector is empty.

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

Inserts item at index.

Panics

Panics if index is greater than self.len().

Examples found in repository

src/lib.rs (line 266)

    pub fn push(&mut self, item: T) {
        self.insert(self.size, item);
    }

pub fn push(&mut self, item: T)

Inserts item at the end of the vector.

pub fn remove(&mut self, index: usize) -> T

Removes and returns the item at index.

Panics

Panics if index is not less than self.len().

Examples found in repository

src/lib.rs (line 288)

    pub fn pop(&mut self) -> Option<T> {
        self.size.checked_sub(1).map(|s| self.remove(s))
    }

pub fn pop(&mut self) -> Option<T>

Removes and returns the last item in the vector, or None if the vector is empty.

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

Gets an iterator that returns references to each item in the vector.

Examples found in repository

src/lib.rs (line 337)

    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

macro_rules! impl_drop_for_btree_vec {
    ($($unsafe:ident)? $(#[$attr:meta])*) => {
        $($unsafe)? impl<$(#[$attr])* T, const B: usize> ::core::ops::Drop
            for $crate::BTreeVec<T, B>
        {
            fn drop(&mut self) {
                if let Some(root) = self.root {
                    // SAFETY: `BTreeVec` uses `NodeRef`s in accordance with
                    // standard borrowing rules, so there are no existing
                    // references.
                    unsafe { NodeRef::new_mutable(root) }.destroy();
                }
            }
        }
    };
}

#[cfg(not(feature = "dropck_eyepatch"))]
impl_drop_for_btree_vec!();

// SAFETY: This `Drop` impl does not directly or indirectly access any data in
// any `T`, except for calling its destructor (see [1]), and `Self` contains a
// `PhantomData<Box<T>>` so dropck knows that `T` may be dropped (see [2]).
//
// [1]: https://doc.rust-lang.org/nomicon/dropck.html
// [2]: https://forge.rust-lang.org/libs/maintaining-std.html
//      #is-there-a-manual-drop-implementation
#[cfg(feature = "dropck_eyepatch")]
impl_drop_for_btree_vec!(unsafe #[may_dangle]);

/// An iterator over the items in a [`BTreeVec`].
pub struct Iter<'a, T, const B: usize> {
    leaf: Option<LeafRef<T, B>>,
    index: usize,
    phantom: PhantomData<&'a T>,
}

impl<'a, T, const B: usize> Iterator for Iter<'a, T, B> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        let mut leaf = self.leaf?;
        if self.index == leaf.length() {
            self.leaf = self.leaf.take().unwrap().into_next().ok();
            leaf = self.leaf?;
            self.index = 0;
        }
        let index = self.index;
        self.index += 1;
        Some(leaf.into_child(index))
    }
}

impl<T, const B: usize> FusedIterator for Iter<'_, T, B> {}

impl<T, const B: usize> Clone for Iter<'_, T, B> {
    fn clone(&self) -> Self {
        Self {
            leaf: self.leaf,
            index: self.index,
            phantom: self.phantom,
        }
    }
}

// SAFETY: This type yields immutable references to items in the vector, so it
// can be `Send` as long as `T` is `Sync` (which means `&T` is `Send`).
unsafe impl<T: Sync, const B: usize> Send for Iter<'_, T, B> {}

// SAFETY: This type has no `&self` methods that access shared data or fields
// with non-`Sync` interior mutability, but `T` must be `Sync` to match the
// `Send` impl, since this type implements `Clone`, effectively allowing it to
// be sent.
unsafe impl<T: Sync, const B: usize> Sync for Iter<'_, T, B> {}

impl<'a, T, const B: usize> IntoIterator for &'a BTreeVec<T, B> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T, B>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }

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

Gets an iterator that returns mutable references to each item in the vector.

Examples found in repository

src/lib.rs (line 467)

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }

Trait Implementations

impl<T: Debug, const B: usize> Debug for BTreeVec<T, B>

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

Formats the value using the given formatter.

impl<T, const B: usize> Default for BTreeVec<T, B>

fn default() -> Self

Returns the “default value” for a type.

impl<T, const B: usize> Drop for BTreeVec<T, B>

fn drop(&mut self)

Executes the destructor for this type.

impl<T, const B: usize> Index<usize> for BTreeVec<T, B>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T, const B: usize> IndexMut<usize> for BTreeVec<T, B>

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

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

impl<'a, T, const B: usize> IntoIterator for &'a BTreeVec<T, B>

type Item = &'a T

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T, const B: usize> IntoIterator for &'a mut BTreeVec<T, B>

type Item = &'a mut T

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const B: usize> IntoIterator for BTreeVec<T, B>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, B>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Send, const B: usize> Send for BTreeVec<T, B>

impl<T: Sync, const B: usize> Sync for BTreeVec<T, B>