Struct btree_vec::BTreeVec

pub struct BTreeVec<T, const B: usize = 12, A: Allocator = Global> { /* 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, A: Allocator> BTreeVec<T, 12, A>

pub fn new_in(alloc: A) -> Self

Creates a new BTreeVec with the given allocator. Note that this function is implemented only for the default value of B; see Self::create_in 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 189)

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

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

pub fn create_in(alloc: A) -> Self

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

Examples found in repository

src/lib.rs (line 203)

    pub fn new_in(alloc: A) -> Self {
        Self::create_in(alloc)
    }
}

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 {
        Self::create_in(Global)
    }
}

impl<T, const B: usize, A: Allocator> BTreeVec<T, B, A> {
    #[cfg_attr(
        not(any(feature = "allocator_api", feature = "allocator-fallback")),
        doc(hidden)
    )]
    /// Creates a new [`BTreeVec`] with the given allocator. This function
    /// exists because [`BTreeVec::new_in`] is implemented only for the default
    /// value of `B`.
    pub fn create_in(alloc: A) -> Self {
        assert!(B >= 3);
        // SAFETY:
        //
        // * All nodes are allocated by `alloc`, either via the calls to
        //  `insert` and `LeafRef::alloc` in `Self::insert`. Nodes are
        //  deallocated in two places: via the call to `remove` in
        //  `Self::remove`, and via the call to `NodeRef::destroy` in
        //  `Self::drop`. In both of these cases, `alloc` is provided as the
        //  allocator with which to deallocate the nodes.
        //
        // * When `alloc` (`Self.alloc`) is dropped, `Self::drop` will have
        //   run, which destroys all nodes. If `alloc`'s memory is reused
        //   (e.g., via `mem::forget`), the only way this can happen is if the
        //   operation that made its memory able to be reused applied to the
        //   entire `BTreeVec`. Thus, all allocated nodes will become
        //   inaccessible as they are not exposed via any public APIs,
        //   guaranteeing that they will never be accessed.
        let alloc = unsafe { VerifiedAlloc::new(alloc) };
        Self {
            root: None,
            size: 0,
            alloc,
            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(&self.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(
            ItemInsertion {
                node: leaf,
                index,
                item,
                root_size: self.size,
            },
            &self.alloc,
        );
        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.alloc);
        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, A> Default for BTreeVec<T, B, A>
where
    A: Allocator + Default,
{
    fn default() -> Self {
        Self::create_in(A::default())
    }

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 308)

    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(&self.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(
            ItemInsertion {
                node: leaf,
                index,
                item,
                root_size: self.size,
            },
            &self.alloc,
        );
        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.alloc);
        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, A> Default for BTreeVec<T, B, A>
where
    A: Allocator + Default,
{
    fn default() -> Self {
        Self::create_in(A::default())
    }
}

impl<T, const B: usize, A: Allocator> Index<usize> for BTreeVec<T, B, A> {
    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 314)

    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(&self.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(
            ItemInsertion {
                node: leaf,
                index,
                item,
                root_size: self.size,
            },
            &self.alloc,
        );
        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.alloc);
        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, A> Default for BTreeVec<T, B, A>
where
    A: Allocator + Default,
{
    fn default() -> Self {
        Self::create_in(A::default())
    }
}

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

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

impl<T, const B: usize, A: Allocator> IndexMut<usize> for BTreeVec<T, B, A> {
    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 356)

    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 378)

    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 430)

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

// 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_attr(feature = "dropck_eyepatch", add_syntax::prepend(unsafe))]
impl<#[cfg_attr(feature = "dropck_eyepatch", may_dangle)] T, const B: usize, A>
    Drop for BTreeVec<T, B, A>
where
    A: Allocator,
{
    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(&self.alloc);
        }
    }
}

/// 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, A> IntoIterator for &'a BTreeVec<T, B, A>
where
    A: Allocator,
{
    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 559)

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

Trait Implementations

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

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

Formats the value using the given formatter.

impl<T, const B: usize, A> Default for BTreeVec<T, B, A>where
    A: Allocator + Default,

fn default() -> Self

Returns the “default value” for a type.

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

fn drop(&mut self)

Executes the destructor for this type.

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

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, A: Allocator> IndexMut<usize> for BTreeVec<T, B, A>

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

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

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

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, A> IntoIterator for &'a mut BTreeVec<T, B, A>where
    A: Allocator,

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, A: Allocator> IntoIterator for BTreeVec<T, B, A>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, B, A>

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, A> Send for BTreeVec<T, B, A>where
    T: Send,
    A: Allocator,

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