planck_noalloc/

smallvec.rs

//! A vector that stores elements inline up to a fixed capacity, then spills to the heap.
//!
//! [`SmallVec<T, N>`] behaves like `Vec<T>` but keeps up to `N` elements on the stack.
//! When more than `N` elements are needed, data is moved to a heap-allocated `Vec<T>`.
//!
//! This is useful when the common case fits in a small, fixed buffer but you still need
//! to handle occasional overflow without panicking.
//!
//! # Examples
//!
//! ```
//! use planck_noalloc::smallvec::SmallVec;
//!
//! let mut sv = SmallVec::<i32, 4>::new();
//! sv.push(1);
//! sv.push(2);
//! sv.push(3);
//! assert!(sv.is_inline());
//! assert_eq!(sv.as_slice(), &[1, 2, 3]);
//!
//! // Push beyond inline capacity — spills to heap
//! sv.push(4);
//! sv.push(5);
//! assert!(!sv.is_inline());
//! assert_eq!(sv.as_slice(), &[1, 2, 3, 4, 5]);
//! ```

use alloc::vec::Vec;
use core::mem::MaybeUninit;

/// Internal representation: either inline or heap-allocated.
enum Repr<T, const N: usize> {
    Inline {
        data: [MaybeUninit<T>; N],
        len: usize,
    },
    Heap(Vec<T>),
}

/// A vector that stores up to `N` elements inline on the stack, spilling to the heap
/// when capacity is exceeded.
///
/// # Type Parameters
///
/// - `T`: The element type
/// - `N`: The inline capacity (number of elements stored on the stack)
pub struct SmallVec<T, const N: usize> {
    repr: Repr<T, N>,
}

impl<T, const N: usize> SmallVec<T, N> {
    /// Creates a new, empty `SmallVec`.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            repr: Repr::Inline {
                data: [const { MaybeUninit::uninit() }; N],
                len: 0,
            },
        }
    }

    /// Creates a new `SmallVec` with at least the specified capacity.
    ///
    /// If `cap <= N`, the data stays inline. Otherwise, a heap `Vec` is allocated.
    #[must_use]
    pub fn with_capacity(cap: usize) -> Self {
        if cap <= N {
            Self::new()
        } else {
            Self {
                repr: Repr::Heap(Vec::with_capacity(cap)),
            }
        }
    }

    /// Returns the number of elements.
    #[must_use]
    pub fn len(&self) -> usize {
        match &self.repr {
            Repr::Inline { len, .. } => *len,
            Repr::Heap(v) => v.len(),
        }
    }

    /// Returns `true` if the vector is empty.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns the current capacity.
    #[must_use]
    pub fn capacity(&self) -> usize {
        match &self.repr {
            Repr::Inline { .. } => N,
            Repr::Heap(v) => v.capacity(),
        }
    }

    /// Returns `true` if elements are stored inline (not on the heap).
    #[must_use]
    pub fn is_inline(&self) -> bool {
        matches!(self.repr, Repr::Inline { .. })
    }

    /// Returns a slice of all elements.
    #[must_use]
    pub fn as_slice(&self) -> &[T] {
        match &self.repr {
            Repr::Inline { data, len } => {
                // SAFETY: Elements 0..*len are initialized.
                unsafe { core::slice::from_raw_parts(data.as_ptr().cast::<T>(), *len) }
            }
            Repr::Heap(v) => v.as_slice(),
        }
    }

    /// Returns a mutable slice of all elements.
    #[must_use]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        match &mut self.repr {
            Repr::Inline { data, len } => {
                // SAFETY: Elements 0..*len are initialized.
                unsafe { core::slice::from_raw_parts_mut(data.as_mut_ptr().cast::<T>(), *len) }
            }
            Repr::Heap(v) => v.as_mut_slice(),
        }
    }

    /// Returns a pointer to the first element.
    #[must_use]
    pub fn as_ptr(&self) -> *const T {
        match &self.repr {
            Repr::Inline { data, .. } => data.as_ptr().cast::<T>(),
            Repr::Heap(v) => v.as_ptr(),
        }
    }

    /// Returns a mutable pointer to the first element.
    #[must_use]
    pub fn as_mut_ptr(&mut self) -> *mut T {
        match &mut self.repr {
            Repr::Inline { data, .. } => data.as_mut_ptr().cast::<T>(),
            Repr::Heap(v) => v.as_mut_ptr(),
        }
    }

    /// Appends an element.
    ///
    /// If the inline buffer is full, spills to the heap.
    pub fn push(&mut self, value: T) {
        match &mut self.repr {
            Repr::Inline { data, len } if *len < N => {
                data[*len].write(value);
                *len += 1;
            }
            _ => {
                self.spill_and_push(value);
            }
        }
    }

    /// Spills inline data to the heap (if needed) and pushes the value.
    fn spill_and_push(&mut self, value: T) {
        match &mut self.repr {
            Repr::Heap(v) => {
                v.push(value);
            }
            Repr::Inline { .. } => {
                self.spill();
                if let Repr::Heap(v) = &mut self.repr {
                    v.push(value);
                }
            }
        }
    }

    /// Removes and returns the last element, or `None` if empty.
    #[must_use]
    pub fn pop(&mut self) -> Option<T> {
        match &mut self.repr {
            Repr::Inline { data, len } => {
                if *len == 0 {
                    return None;
                }
                *len -= 1;
                // SAFETY: Element at *len was initialized.
                Some(unsafe { data[*len].assume_init_read() })
            }
            Repr::Heap(v) => v.pop(),
        }
    }

    /// Inserts an element at `index`, shifting elements after it to the right.
    ///
    /// # Panics
    ///
    /// Panics if `index > len`.
    pub fn insert(&mut self, index: usize, value: T) {
        let len = self.len();
        assert!(index <= len, "index out of bounds");

        if let Repr::Inline { .. } = &self.repr {
            if len >= N {
                self.spill();
            }
        }

        match &mut self.repr {
            Repr::Inline { data, len } => {
                // SAFETY: We shift elements [index..*len] one position right.
                unsafe {
                    let ptr = data.as_mut_ptr().add(index);
                    core::ptr::copy(ptr, ptr.add(1), *len - index);
                    ptr.cast::<T>().write(value);
                }
                *len += 1;
            }
            Repr::Heap(v) => v.insert(index, value),
        }
    }

    /// Removes and returns the element at `index`, shifting elements after it left.
    ///
    /// # Panics
    ///
    /// Panics if `index >= len`.
    pub fn remove(&mut self, index: usize) -> T {
        let len = self.len();
        assert!(index < len, "index out of bounds");

        match &mut self.repr {
            Repr::Inline { data, len } => {
                // SAFETY: Element at `index` is initialized. We read it, then
                // shift elements [index+1..*len] one position left.
                unsafe {
                    let ptr = data.as_mut_ptr().add(index);
                    let value = ptr.cast::<T>().read();
                    core::ptr::copy(ptr.add(1), ptr, *len - index - 1);
                    *len -= 1;
                    value
                }
            }
            Repr::Heap(v) => v.remove(index),
        }
    }

    /// Removes the element at `index` by swapping it with the last element.
    /// Does not preserve ordering but is O(1).
    ///
    /// # Panics
    ///
    /// Panics if `index >= len`.
    pub fn swap_remove(&mut self, index: usize) -> T {
        let len = self.len();
        assert!(index < len, "index out of bounds");

        match &mut self.repr {
            Repr::Inline { data, len } => {
                *len -= 1;
                data.swap(index, *len);
                // SAFETY: The element (now at *len) was initialized.
                unsafe { data[*len].assume_init_read() }
            }
            Repr::Heap(v) => v.swap_remove(index),
        }
    }

    /// Removes all elements.
    pub fn clear(&mut self) {
        match &mut self.repr {
            Repr::Inline { data, len } => {
                for item in data.iter_mut().take(*len) {
                    // SAFETY: Elements 0..*len are initialized.
                    unsafe {
                        item.assume_init_drop();
                    }
                }
                *len = 0;
            }
            Repr::Heap(v) => v.clear(),
        }
    }

    /// Truncates the vector to at most `new_len` elements.
    ///
    /// If `new_len >= len`, this is a no-op.
    pub fn truncate(&mut self, new_len: usize) {
        let len = self.len();
        if new_len >= len {
            return;
        }

        match &mut self.repr {
            Repr::Inline { data, len } => {
                for item in data.iter_mut().take(*len).skip(new_len) {
                    // SAFETY: Elements new_len..*len are initialized.
                    unsafe {
                        item.assume_init_drop();
                    }
                }
                *len = new_len;
            }
            Repr::Heap(v) => v.truncate(new_len),
        }
    }

    /// Returns a reference to the last element, or `None` if empty.
    #[must_use]
    pub fn last(&self) -> Option<&T> {
        let len = self.len();
        if len == 0 {
            None
        } else {
            Some(&self.as_slice()[len - 1])
        }
    }

    /// Returns a mutable reference to the last element, or `None` if empty.
    #[must_use]
    pub fn last_mut(&mut self) -> Option<&mut T> {
        let len = self.len();
        if len == 0 {
            None
        } else {
            Some(&mut self.as_mut_slice()[len - 1])
        }
    }

    /// Reserves capacity for at least `additional` more elements.
    ///
    /// If inline and the total needed exceeds `N`, spills to the heap.
    pub fn reserve(&mut self, additional: usize) {
        let needed = self.len() + additional;
        if needed <= self.capacity() {
            return;
        }

        match &self.repr {
            Repr::Inline { .. } => {
                self.spill_with_capacity(needed);
            }
            Repr::Heap(_) => {
                // Take ownership temporarily
                let old = core::mem::replace(&mut self.repr, Repr::Inline {
                    data: [const { MaybeUninit::uninit() }; N],
                    len: 0,
                });
                if let Repr::Heap(mut v) = old {
                    v.reserve(additional);
                    self.repr = Repr::Heap(v);
                }
            }
        }
    }

    /// Moves inline data to a heap `Vec` if currently inline.
    ///
    /// No-op if already on the heap.
    pub fn spill(&mut self) {
        if let Repr::Inline { len, .. } = &self.repr {
            let cap = core::cmp::max(2 * N, *len);
            self.spill_with_capacity(cap);
        }
    }

    /// Spills inline data to a heap `Vec` with the given capacity.
    fn spill_with_capacity(&mut self, cap: usize) {
        let old = core::mem::replace(
            &mut self.repr,
            Repr::Inline {
                data: [const { MaybeUninit::uninit() }; N],
                len: 0,
            },
        );

        if let Repr::Inline { data, len } = old {
            let mut v = Vec::with_capacity(cap);
            // SAFETY: Elements 0..len are initialized. We copy them into the Vec
            // and set its length. MaybeUninit does not drop its contents, so the
            // old array being dropped is safe — no double-free occurs.
            unsafe {
                core::ptr::copy_nonoverlapping(data.as_ptr().cast::<T>(), v.as_mut_ptr(), len);
                v.set_len(len);
            }
            self.repr = Repr::Heap(v);
        }
    }

    /// Shrinks the backing allocation to fit the current length.
    ///
    /// If on the heap and `len <= N`, moves data back inline.
    pub fn shrink_to_fit(&mut self) {
        if let Repr::Heap(_) = &self.repr {
            let len = self.len();
            if len <= N {
                let old = core::mem::replace(
                    &mut self.repr,
                    Repr::Inline {
                        data: [const { MaybeUninit::uninit() }; N],
                        len: 0,
                    },
                );
                if let Repr::Heap(v) = old {
                    let mut data = [const { MaybeUninit::uninit() }; N];
                    // SAFETY: We copy len elements from the Vec into the inline array.
                    unsafe {
                        core::ptr::copy_nonoverlapping(
                            v.as_ptr(),
                            data.as_mut_ptr().cast::<T>(),
                            len,
                        );
                    }
                    // Forget Vec so elements aren't double-dropped; we own them in `data` now.
                    // We need to drop the Vec without dropping elements. Use set_len(0) then drop.
                    let mut v = v;
                    // SAFETY: Setting len to 0 before drop prevents element drops.
                    unsafe {
                        v.set_len(0);
                    }
                    drop(v);
                    self.repr = Repr::Inline { data, len };
                }
            } else {
                // Still on heap, just shrink the Vec
                let old = core::mem::replace(
                    &mut self.repr,
                    Repr::Inline {
                        data: [const { MaybeUninit::uninit() }; N],
                        len: 0,
                    },
                );
                if let Repr::Heap(mut v) = old {
                    v.shrink_to_fit();
                    self.repr = Repr::Heap(v);
                }
            }
        }
    }

    /// Returns an iterator over references to elements.
    pub fn iter(&self) -> core::slice::Iter<'_, T> {
        self.as_slice().iter()
    }

    /// Returns an iterator over mutable references to elements.
    pub fn iter_mut(&mut self) -> core::slice::IterMut<'_, T> {
        self.as_mut_slice().iter_mut()
    }

    /// Converts this `SmallVec` into a heap-allocated `Vec<T>`.
    #[must_use]
    pub fn into_vec(mut self) -> Vec<T> {
        self.spill();
        let old = core::mem::replace(
            &mut self.repr,
            Repr::Inline {
                data: [const { MaybeUninit::uninit() }; N],
                len: 0,
            },
        );
        match old {
            Repr::Heap(v) => v,
            Repr::Inline { .. } => unreachable!(),
        }
    }
}

impl<T: Clone, const N: usize> Clone for SmallVec<T, N> {
    fn clone(&self) -> Self {
        match &self.repr {
            Repr::Inline { data, len } => {
                let mut new_data = [const { MaybeUninit::uninit() }; N];
                for i in 0..*len {
                    // SAFETY: Elements 0..*len are initialized.
                    new_data[i].write(unsafe { data[i].assume_init_ref() }.clone());
                }
                Self {
                    repr: Repr::Inline {
                        data: new_data,
                        len: *len,
                    },
                }
            }
            Repr::Heap(v) => Self {
                repr: Repr::Heap(v.clone()),
            },
        }
    }
}

impl<T: core::fmt::Debug, const N: usize> core::fmt::Debug for SmallVec<T, N> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_list().entries(self.as_slice()).finish()
    }
}

impl<T, const N: usize> Default for SmallVec<T, N> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T, const N: usize> Drop for SmallVec<T, N> {
    fn drop(&mut self) {
        if let Repr::Inline { data, len } = &mut self.repr {
            for item in data.iter_mut().take(*len) {
                // SAFETY: Elements 0..*len are initialized.
                unsafe {
                    item.assume_init_drop();
                }
            }
            *len = 0;
        }
        // Repr::Heap(Vec) is dropped automatically.
    }
}

impl<T: PartialEq, const N: usize> PartialEq for SmallVec<T, N> {
    fn eq(&self, other: &Self) -> bool {
        self.as_slice() == other.as_slice()
    }
}

impl<T: Eq, const N: usize> Eq for SmallVec<T, N> {}

impl<T: core::hash::Hash, const N: usize> core::hash::Hash for SmallVec<T, N> {
    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
        self.as_slice().hash(state);
    }
}

impl<T: PartialOrd, const N: usize> PartialOrd for SmallVec<T, N> {
    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
        self.as_slice().partial_cmp(other.as_slice())
    }
}

impl<T: Ord, const N: usize> Ord for SmallVec<T, N> {
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
        self.as_slice().cmp(other.as_slice())
    }
}

impl<T, const N: usize> core::ops::Deref for SmallVec<T, N> {
    type Target = [T];

    fn deref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T, const N: usize> core::ops::DerefMut for SmallVec<T, N> {
    fn deref_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T, const N: usize> core::ops::Index<usize> for SmallVec<T, N> {
    type Output = T;

    fn index(&self, index: usize) -> &T {
        &self.as_slice()[index]
    }
}

impl<T, const N: usize> core::ops::IndexMut<usize> for SmallVec<T, N> {
    fn index_mut(&mut self, index: usize) -> &mut T {
        &mut self.as_mut_slice()[index]
    }
}

impl<T, const N: usize> From<Vec<T>> for SmallVec<T, N> {
    fn from(v: Vec<T>) -> Self {
        Self {
            repr: Repr::Heap(v),
        }
    }
}

impl<T: Clone, const N: usize> From<&[T]> for SmallVec<T, N> {
    fn from(slice: &[T]) -> Self {
        let mut sv = Self::with_capacity(slice.len());
        for item in slice {
            sv.push(item.clone());
        }
        sv
    }
}

impl<T, const N: usize> From<[T; N]> for SmallVec<T, N> {
    fn from(array: [T; N]) -> Self {
        let mut data: [MaybeUninit<T>; N] = [const { MaybeUninit::uninit() }; N];
        // SAFETY: We move each element from the array into MaybeUninit slots.
        // We read from the array via raw pointer, then forget the array to avoid
        // double-drop. MaybeUninit slots now own the values.
        unsafe {
            let src: *const T = (&raw const array).cast::<T>();
            for (i, slot) in data.iter_mut().enumerate().take(N) {
                slot.write(src.add(i).read());
            }
            core::mem::forget(array);
        }
        Self {
            repr: Repr::Inline { data, len: N },
        }
    }
}

impl<T, const N: usize> AsRef<[T]> for SmallVec<T, N> {
    fn as_ref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T, const N: usize> AsMut<[T]> for SmallVec<T, N> {
    fn as_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T, const N: usize> core::borrow::Borrow<[T]> for SmallVec<T, N> {
    fn borrow(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T, const N: usize> core::borrow::BorrowMut<[T]> for SmallVec<T, N> {
    fn borrow_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T, const N: usize> Extend<T> for SmallVec<T, N> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for item in iter {
            self.push(item);
        }
    }
}

impl<T, const N: usize> FromIterator<T> for SmallVec<T, N> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut sv = Self::new();
        sv.extend(iter);
        sv
    }
}

// --- IntoIterator (owning) ---

/// Owning iterator over a [`SmallVec`].
pub struct SmallVecIntoIter<T, const N: usize> {
    inner: IntoIterRepr<T, N>,
}

enum IntoIterRepr<T, const N: usize> {
    Inline {
        data: [MaybeUninit<T>; N],
        start: usize,
        end: usize,
    },
    Heap(alloc::vec::IntoIter<T>),
}

impl<T, const N: usize> Iterator for SmallVecIntoIter<T, N> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        match &mut self.inner {
            IntoIterRepr::Inline { data, start, end } => {
                if *start >= *end {
                    return None;
                }
                let idx = *start;
                *start += 1;
                // SAFETY: Elements start..end are initialized.
                Some(unsafe { data[idx].assume_init_read() })
            }
            IntoIterRepr::Heap(iter) => iter.next(),
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.len();
        (remaining, Some(remaining))
    }
}

impl<T, const N: usize> DoubleEndedIterator for SmallVecIntoIter<T, N> {
    fn next_back(&mut self) -> Option<T> {
        match &mut self.inner {
            IntoIterRepr::Inline { data, start, end } => {
                if *start >= *end {
                    return None;
                }
                *end -= 1;
                // SAFETY: Elements start..end are initialized.
                Some(unsafe { data[*end].assume_init_read() })
            }
            IntoIterRepr::Heap(iter) => iter.next_back(),
        }
    }
}

impl<T, const N: usize> ExactSizeIterator for SmallVecIntoIter<T, N> {
    fn len(&self) -> usize {
        match &self.inner {
            IntoIterRepr::Inline { start, end, .. } => *end - *start,
            IntoIterRepr::Heap(iter) => iter.len(),
        }
    }
}

impl<T, const N: usize> Drop for SmallVecIntoIter<T, N> {
    fn drop(&mut self) {
        // Drop remaining elements that haven't been consumed.
        if let IntoIterRepr::Inline { data, start, end } = &mut self.inner {
            for item in data.iter_mut().take(*end).skip(*start) {
                // SAFETY: Elements start..end are still initialized.
                unsafe {
                    item.assume_init_drop();
                }
            }
            *start = *end;
        }
        // Heap variant: alloc::vec::IntoIter handles its own drop.
    }
}

impl<T, const N: usize> IntoIterator for SmallVec<T, N> {
    type Item = T;
    type IntoIter = SmallVecIntoIter<T, N>;

    fn into_iter(mut self) -> SmallVecIntoIter<T, N> {
        let inner = match &mut self.repr {
            Repr::Inline { len, .. } => {
                let end = *len;
                // Take ownership of the data array by replacing repr.
                // Set len to 0 so Drop doesn't double-drop.
                *len = 0;
                let old = core::mem::replace(
                    &mut self.repr,
                    Repr::Inline {
                        data: [const { MaybeUninit::uninit() }; N],
                        len: 0,
                    },
                );
                match old {
                    Repr::Inline { data, .. } => IntoIterRepr::Inline {
                        data,
                        start: 0,
                        end,
                    },
                    Repr::Heap(_) => unreachable!(),
                }
            }
            Repr::Heap(_) => {
                let old = core::mem::replace(
                    &mut self.repr,
                    Repr::Inline {
                        data: [const { MaybeUninit::uninit() }; N],
                        len: 0,
                    },
                );
                match old {
                    Repr::Heap(v) => IntoIterRepr::Heap(v.into_iter()),
                    Repr::Inline { .. } => unreachable!(),
                }
            }
        };
        // self.repr is now an empty Inline, so Drop does nothing.
        SmallVecIntoIter { inner }
    }
}

impl<'a, T, const N: usize> IntoIterator for &'a SmallVec<T, N> {
    type Item = &'a T;
    type IntoIter = core::slice::Iter<'a, T>;

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

impl<'a, T, const N: usize> IntoIterator for &'a mut SmallVec<T, N> {
    type Item = &'a mut T;
    type IntoIter = core::slice::IterMut<'a, T>;

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

#[cfg(test)]
mod tests {
    extern crate alloc;
    use alloc::string::String;
    use alloc::vec;

    use super::*;

    #[test]
    fn new_is_empty() {
        let sv = SmallVec::<i32, 4>::new();
        assert!(sv.is_empty());
        assert_eq!(sv.len(), 0);
        assert!(sv.is_inline());
    }

    #[test]
    fn push_within_capacity() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        sv.push(3);
        assert_eq!(sv.len(), 3);
        assert!(sv.is_inline());
        assert_eq!(sv.as_slice(), &[1, 2, 3]);
    }

    #[test]
    fn push_spills_to_heap() {
        let mut sv = SmallVec::<i32, 2>::new();
        sv.push(1);
        sv.push(2);
        assert!(sv.is_inline());
        sv.push(3);
        assert!(!sv.is_inline());
        assert_eq!(sv.as_slice(), &[1, 2, 3]);
    }

    #[test]
    fn pop_inline() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(10);
        sv.push(20);
        assert_eq!(sv.pop(), Some(20));
        assert_eq!(sv.pop(), Some(10));
        assert_eq!(sv.pop(), None);
    }

    #[test]
    fn pop_heap() {
        let mut sv = SmallVec::<i32, 1>::new();
        sv.push(1);
        sv.push(2);
        sv.push(3);
        assert_eq!(sv.pop(), Some(3));
        assert_eq!(sv.pop(), Some(2));
        assert_eq!(sv.pop(), Some(1));
        assert_eq!(sv.pop(), None);
    }

    #[test]
    fn insert_inline() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(3);
        sv.insert(1, 2);
        assert_eq!(sv.as_slice(), &[1, 2, 3]);
        assert!(sv.is_inline());
    }

    #[test]
    fn insert_causes_spill() {
        let mut sv = SmallVec::<i32, 2>::new();
        sv.push(1);
        sv.push(3);
        sv.insert(1, 2);
        assert_eq!(sv.as_slice(), &[1, 2, 3]);
        assert!(!sv.is_inline());
    }

    #[test]
    fn remove_inline() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        sv.push(3);
        let removed = sv.remove(1);
        assert_eq!(removed, 2);
        assert_eq!(sv.as_slice(), &[1, 3]);
    }

    #[test]
    fn swap_remove_inline() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(10);
        sv.push(20);
        sv.push(30);
        let removed = sv.swap_remove(0);
        assert_eq!(removed, 10);
        assert_eq!(sv.as_slice(), &[30, 20]);
    }

    #[test]
    fn clear_inline() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        sv.clear();
        assert!(sv.is_empty());
    }

    #[test]
    fn clear_heap() {
        let mut sv = SmallVec::<i32, 1>::new();
        sv.push(1);
        sv.push(2);
        sv.push(3);
        sv.clear();
        assert!(sv.is_empty());
    }

    #[test]
    fn truncate_inline() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        sv.push(3);
        sv.truncate(1);
        assert_eq!(sv.as_slice(), &[1]);
    }

    #[test]
    fn truncate_noop() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.truncate(5);
        assert_eq!(sv.len(), 1);
    }

    #[test]
    fn last_and_last_mut() {
        let mut sv = SmallVec::<i32, 4>::new();
        assert_eq!(sv.last(), None);
        sv.push(1);
        sv.push(2);
        assert_eq!(sv.last(), Some(&2));
        *sv.last_mut().unwrap() = 99;
        assert_eq!(sv.last(), Some(&99));
    }

    #[test]
    fn capacity_inline() {
        let sv = SmallVec::<i32, 4>::new();
        assert_eq!(sv.capacity(), 4);
    }

    #[test]
    fn with_capacity_inline() {
        let sv = SmallVec::<i32, 4>::with_capacity(3);
        assert!(sv.is_inline());
        assert_eq!(sv.capacity(), 4);
    }

    #[test]
    fn with_capacity_heap() {
        let sv = SmallVec::<i32, 4>::with_capacity(10);
        assert!(!sv.is_inline());
        assert!(sv.capacity() >= 10);
    }

    #[test]
    fn reserve_spills() {
        let mut sv = SmallVec::<i32, 2>::new();
        sv.push(1);
        sv.reserve(5);
        assert!(!sv.is_inline());
        assert!(sv.capacity() >= 6);
        assert_eq!(sv.as_slice(), &[1]);
    }

    #[test]
    fn spill_and_shrink_back() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        sv.spill();
        assert!(!sv.is_inline());
        assert_eq!(sv.as_slice(), &[1, 2]);
        sv.shrink_to_fit();
        assert!(sv.is_inline());
        assert_eq!(sv.as_slice(), &[1, 2]);
    }

    #[test]
    fn clone_inline() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        let sv2 = sv.clone();
        assert_eq!(sv2.as_slice(), &[1, 2]);
        assert!(sv2.is_inline());
    }

    #[test]
    fn clone_heap() {
        let mut sv = SmallVec::<i32, 1>::new();
        sv.push(1);
        sv.push(2);
        let sv2 = sv.clone();
        assert_eq!(sv2.as_slice(), &[1, 2]);
    }

    #[test]
    fn debug_format() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        let s = alloc::format!("{sv:?}");
        assert_eq!(s, "[1, 2]");
    }

    #[test]
    fn eq_and_ord() {
        let mut a = SmallVec::<i32, 4>::new();
        a.push(1);
        a.push(2);
        let mut b = SmallVec::<i32, 4>::new();
        b.push(1);
        b.push(2);
        assert_eq!(a, b);

        let mut c = SmallVec::<i32, 4>::new();
        c.push(1);
        c.push(3);
        assert!(a < c);
    }

    #[test]
    fn index_and_index_mut() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(10);
        sv.push(20);
        assert_eq!(sv[0], 10);
        sv[0] = 99;
        assert_eq!(sv[0], 99);
    }

    #[test]
    fn from_vec() {
        let sv: SmallVec<i32, 4> = SmallVec::from(vec![1, 2, 3]);
        assert!(!sv.is_inline());
        assert_eq!(sv.as_slice(), &[1, 2, 3]);
    }

    #[test]
    fn from_slice() {
        let sv: SmallVec<i32, 4> = SmallVec::from([1, 2, 3].as_slice());
        assert!(sv.is_inline());
        assert_eq!(sv.as_slice(), &[1, 2, 3]);
    }

    #[test]
    fn from_array() {
        let sv: SmallVec<i32, 3> = SmallVec::from([1, 2, 3]);
        assert!(sv.is_inline());
        assert_eq!(sv.as_slice(), &[1, 2, 3]);
    }

    #[test]
    fn extend_and_from_iter() {
        let sv: SmallVec<i32, 2> = (0..5).collect();
        assert_eq!(sv.as_slice(), &[0, 1, 2, 3, 4]);
    }

    #[test]
    fn into_iter_inline() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        sv.push(3);
        let collected: Vec<i32> = sv.into_iter().collect();
        assert_eq!(collected, vec![1, 2, 3]);
    }

    #[test]
    fn into_iter_heap() {
        let mut sv = SmallVec::<i32, 1>::new();
        sv.push(1);
        sv.push(2);
        sv.push(3);
        let collected: Vec<i32> = sv.into_iter().collect();
        assert_eq!(collected, vec![1, 2, 3]);
    }

    #[test]
    fn into_iter_double_ended() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        sv.push(3);
        let collected: Vec<i32> = sv.into_iter().rev().collect();
        assert_eq!(collected, vec![3, 2, 1]);
    }

    #[test]
    fn into_iter_exact_size() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        let mut iter = sv.into_iter();
        assert_eq!(iter.len(), 2);
        iter.next();
        assert_eq!(iter.len(), 1);
    }

    #[test]
    fn into_vec_conversion() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        let v = sv.into_vec();
        assert_eq!(v, vec![1, 2]);
    }

    #[test]
    fn drop_elements_properly() {
        use alloc::rc::Rc;
        let rc = Rc::new(());
        let mut sv = SmallVec::<Rc<()>, 2>::new();
        sv.push(rc.clone());
        sv.push(rc.clone());
        assert_eq!(Rc::strong_count(&rc), 3);
        drop(sv);
        assert_eq!(Rc::strong_count(&rc), 1);
    }

    #[test]
    fn drop_elements_on_heap() {
        use alloc::rc::Rc;
        let rc = Rc::new(());
        let mut sv = SmallVec::<Rc<()>, 1>::new();
        sv.push(rc.clone());
        sv.push(rc.clone());
        sv.push(rc.clone());
        assert_eq!(Rc::strong_count(&rc), 4);
        drop(sv);
        assert_eq!(Rc::strong_count(&rc), 1);
    }

    #[test]
    fn into_iter_drops_remaining() {
        use alloc::rc::Rc;
        let rc = Rc::new(());
        let mut sv = SmallVec::<Rc<()>, 4>::new();
        sv.push(rc.clone());
        sv.push(rc.clone());
        sv.push(rc.clone());
        let mut iter = sv.into_iter();
        iter.next(); // consume one
        assert_eq!(Rc::strong_count(&rc), 3); // 1 original + 2 remaining in iter
        drop(iter);
        assert_eq!(Rc::strong_count(&rc), 1);
    }

    #[test]
    fn as_ref_as_mut_borrow() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(1);
        sv.push(2);
        let r: &[i32] = sv.as_ref();
        assert_eq!(r, &[1, 2]);
        let m: &mut [i32] = sv.as_mut();
        m[0] = 99;
        assert_eq!(sv[0], 99);
    }

    #[test]
    fn deref_and_deref_mut() {
        let mut sv = SmallVec::<i32, 4>::new();
        sv.push(3);
        sv.push(1);
        sv.push(2);
        // Deref to &[T] gives us slice methods
        assert!(sv.contains(&1));
        // DerefMut to &mut [T]
        sv.sort();
        assert_eq!(&*sv, &[1, 2, 3]);
    }

    #[test]
    fn hash_consistent() {
        use core::hash::{Hash, Hasher};

        struct SimpleHasher(u64);
        impl Hasher for SimpleHasher {
            fn finish(&self) -> u64 {
                self.0
            }
            fn write(&mut self, bytes: &[u8]) {
                for &b in bytes {
                    self.0 = self.0.wrapping_mul(31).wrapping_add(u64::from(b));
                }
            }
        }

        let mut a = SmallVec::<i32, 4>::new();
        a.push(1);
        a.push(2);

        let mut b = SmallVec::<i32, 4>::new();
        b.push(1);
        b.push(2);

        let mut ha = SimpleHasher(0);
        let mut hb = SimpleHasher(0);
        a.hash(&mut ha);
        b.hash(&mut hb);
        assert_eq!(ha.finish(), hb.finish());
    }

    #[test]
    fn spill_with_drop_types() {
        let mut sv = SmallVec::<String, 2>::new();
        sv.push(String::from("hello"));
        sv.push(String::from("world"));
        sv.spill();
        assert!(!sv.is_inline());
        assert_eq!(sv.as_slice(), &["hello", "world"]);
    }

    #[test]
    fn shrink_to_fit_stays_heap_when_too_large() {
        let mut sv = SmallVec::<i32, 2>::new();
        for i in 0..10 {
            sv.push(i);
        }
        sv.shrink_to_fit();
        assert!(!sv.is_inline());
        assert_eq!(sv.len(), 10);
    }

    #[test]
    fn zero_inline_capacity() {
        let mut sv = SmallVec::<i32, 0>::new();
        assert!(sv.is_inline());
        sv.push(1); // immediately spills
        assert!(!sv.is_inline());
        assert_eq!(sv.as_slice(), &[1]);
    }
}