cds 0.10.0

//! A vector with "small size" optimization.

use crate::{
    len::{LengthType, Usize},
    mem::{
        alloc::{alloc_buffer, realloc_buffer, DOHAE, NOHAE},
        errors::ReservationError,
        SpareMemoryPolicy, Uninitialized,
    },
};

use core::{
    marker::PhantomData,
    mem,
    ops::{Bound, RangeBounds},
    ptr, slice,
};

mod buffer;
use buffer::SetLenOnDrop;

mod retain;
use retain::RetainGuard;

/// A continuous growable array with "small size" optimization.
///
/// Written as `SmallVec<T, C, L, SM>`, small vector stores elements of type `T`, has local
/// capacity to store up to `C` elements without allocating a heap buffer, uses `L` as
/// [`length type`], and `SM` as [`spare memory policy`].
///
/// `SmallVec` is mostly compatible with the standard [`Vec`] interface. Moreover, `SmallVec`
/// provides non-panic versions of various methods that in [`Vec`] may panic. In particular,
/// methods which, possibly implicitly, (re)allocate the heap buffer and may fail to reserve more
/// capacity have `try_` counterparts which return an error instead of panicking.
///
/// The "small size" optimization adds a fixed amount of local capacity to the `SmallVec` struct
/// itself. It allows storing up to `C` elements there, without allocating a heap buffer.
/// This may speed up a program, as usually heap allocation is a costly operation. Note, however,
/// that the size of a `SmallVec` struct is proportional to `C`, which may become inefficient for
/// high values of `C` in some use cases.
///
/// Similar to the standard vector, `SmallVec`'s total capacity in bytes is limited by
/// [`isize::MAX`]. Any attempt to allocate more memory fails with capacity overflow error, or a
/// panic in methods that allow it.
///
/// Unlike the standard vector, `SmallVec` doesn't allow customization of the memory allocator via a
/// generic parameter. It always uses the global memory allocator via [`alloc`] and [`realloc`]
/// methods. Support for custom allocators is planned to be added when the [`Allocator`] trait
/// becomes stable.
///
/// `SmallVec` calls [`handle_alloc_error`] when the memory allocator fails in methods allowed to
/// panic. The non-panic methods always return an appropriate `Result`, and [`handle_alloc_error`]
/// is not called.
///
/// [`spare memory policy`]: SpareMemoryPolicy
/// [`length type`]: LengthType
/// [`alloc`]: ::alloc::alloc
/// [`realloc`]: ::alloc::alloc::realloc
/// [`Allocator`]: ::alloc::alloc::Allocator
/// [`handle_alloc_error`]: ::alloc::alloc::handle_alloc_error
///
/// # Examples
///
/// ```rust
/// # use cds::{smallvec::SmallVec, len::U8};
/// let mut v = SmallVec::<u64, 4, U8>::new();
/// assert_eq!(v, []);
/// assert!(v.is_local());
///
/// v.push(1);
/// v.push(2);
///
/// assert_eq!(v, [1, 2]);
/// assert!(v.is_local());
///
/// v[0] = 7;
/// assert_eq!(v, [7, 2]);
///
/// v.extend(3..6);
/// assert_eq!(v, [7, 2, 3, 4, 5]);
/// assert!(v.is_heap());
///
/// for e in &v {
///     println!("{}", e);
/// }
/// ```
pub struct SmallVec<T, const C: usize, L = Usize, SM = Uninitialized>
where
    L: LengthType,
    SM: SpareMemoryPolicy<T>,
{
    /// The buffer
    buf: buffer::Buffer<T, C, L, SM>,

    /// The length of small-vec when local; the capacity of the buffer when on heap
    capacity: L,

    phantom: PhantomData<T>,
}

impl<T, const C: usize, L, SM> SmallVec<T, C, L, SM>
where
    L: LengthType,
    SM: SpareMemoryPolicy<T>,
{
    /// Checks if small-vector uses a heap buffer.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::smallvec::SmallVec;
    /// type V = SmallVec<i32, 5>;
    /// let mut v = V::new();
    /// assert_eq!(v.is_heap(), false);  // <-- capacity <= C; local buffer is used
    /// v.reserve(10);                   // <-- capacity > C; a heap buffer is allocated
    /// assert_eq!(v.is_heap(), true);
    /// ```
    #[inline]
    pub fn is_heap(&self) -> bool {
        (mem::size_of::<T>() != 0) && (self.capacity.as_usize() > C)
    }

    /// Checks if small-vector uses a local buffer.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::smallvec::SmallVec;
    /// type V = SmallVec<i32, 5>;
    /// let mut v = V::new();
    /// assert_eq!(v.is_local(), true);  // <-- capacity <= C; local buffer is used
    /// v.reserve(10);                   // <-- capacity > C; a heap buffer is allocated
    /// assert_eq!(v.is_local(), false);
    /// ```
    #[inline]
    pub fn is_local(&self) -> bool {
        (mem::size_of::<T>() == 0) || (self.capacity.as_usize() <= C)
    }

    /// Creates a new empty small-vector.
    ///
    /// Small-vector doesn't allocate until required capacity exceeds `C`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::smallvec::SmallVec;
    /// let sv = SmallVec::<usize, 5>::new();
    /// assert!(sv.is_empty());
    /// assert_eq!(sv.capacity(), 5);
    /// ```
    #[inline]
    pub fn new() -> Self {
        Self {
            buf: buffer::Buffer::new(),
            capacity: L::new(0),
            phantom: PhantomData,
        }
    }

    /// Constructs an empty small-vector with the specified capacity.
    ///
    /// Note that if `capacity < C` the capacity of the created small-vector is `C`.
    ///
    /// For [zero sized types] the capacity of the created small-vector equals the maximal value
    /// supported by the length-type `L`.
    ///
    /// # Panics
    ///
    /// See [`reserve_exact`] for panic conditions.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::smallvec::SmallVec;
    /// type V = SmallVec<i32, 5>;         // <-- C == 5
    ///
    /// let v = V::with_capacity(3);       // <-- capacity <= C
    /// assert_eq!(v.capacity(), 5);       // <-- effective capacity is C
    /// assert_eq!(v.is_heap(), false);    // <-- the small-vector uses its local buffer
    /// assert!(v.is_empty());
    ///
    /// let v = V::with_capacity(10);      // <-- capacity > C
    /// assert_eq!(v.capacity(), 10);      // <-- effective capacity is the requested value
    /// assert_eq!(v.is_heap(), true);     // <-- the small-vector uses a heap buffer
    /// assert!(v.is_empty());
    /// ```
    ///
    /// [`reserve_exact`]: SmallVec::reserve_exact
    /// [zero sized types]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        let mut v = Self::new();
        v.reserve_exact(capacity);
        v
    }

    /// Returns the capacity of the small-vector.
    ///
    /// The capacity of a small-vector is the number of elements it can hold without reallocating
    /// the buffer.
    ///
    /// When a new small-vector is created, its capacity equals `C`. The capacity grows implicitly
    /// when more elements are added to the vector. The capacity can be pre-allocated via the
    /// [`reserve`] and [`reserve_exact`] methods.
    ///
    /// Note that, when `T` is a [zero sized type], the capacity is always `L::MAX` (even if
    /// `C` is smaller), and the buffer is never allocated on the heap.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; u64];
    /// assert_eq!(v.capacity(), 4);
    /// v.extend(0..6);
    /// assert_eq!(v, [0, 1, 2, 3, 4, 5]);
    /// assert_eq!(v.capacity(), 8);
    ///
    /// ```
    ///
    /// [zero sized type]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts\
    /// [`reserve`]: SmallVec::reserve
    /// [`reserve_exact`]: SmallVec::reserve_exact
    #[inline]
    pub fn capacity(&self) -> usize {
        if mem::size_of::<T>() == 0 {
            L::MAX
        } else {
            self.capacity.as_usize().max(C)
        }
    }

    /// Returns the spare capacity size of the small-vector.
    ///
    /// The spare capacity size of a small-vector is the number of elements it can hold, in addition
    /// to already held ones, without reallocating the buffer.
    ///
    /// This is equivalent to `capacity - len`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![10; u64; 1, 2, 3];
    /// assert_eq!(v.capacity(), 10);
    /// assert_eq!(v.spare_capacity(), 7);
    /// assert_eq!(v.len(), 3);
    /// ```
    #[inline]
    pub fn spare_capacity(&self) -> usize {
        if mem::size_of::<T>() == 0 {
            L::MAX - self.capacity.as_usize()
        } else {
            let cap = self.capacity.as_usize();
            if cap <= C {
                C - cap
            } else {
                cap - self.buf.heap_len().as_usize()
            }
        }
    }

    /// Returns the remaining spare capacity of the small-vector as a slice of `MaybeUninit<T>`.
    ///
    /// The returned slice can be used to fill the small-vector with data (e.g. by reading from a
    /// file) before marking the data as initialized using the [`set_len`] method.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![32; 1, 2];   // <-- a small-vector for IO of 32 elements
    /// assert_eq!(v, [1, 2]);
    ///
    /// let spare_capacity = v.spare_capacity_mut();
    /// spare_capacity[0].write(3);         // <-- read another 2 elements into the small-vector
    /// spare_capacity[1].write(4);
    ///
    /// unsafe { v.set_len(v.len() + 2) };  // <-- reflect the new size
    /// assert_eq!(v, [1, 2, 3, 4]);
    /// ```
    ///
    /// [`set_len`]: SmallVec::set_len
    #[inline]
    pub fn spare_capacity_mut(&mut self) -> &mut [mem::MaybeUninit<T>] {
        if mem::size_of::<T>() == 0 {
            unsafe {
                slice::from_raw_parts_mut(
                    self.buf.local_mut_ptr().cast(),
                    L::MAX - self.capacity.as_usize(),
                )
            }
        } else {
            let cap = self.capacity.as_usize();
            unsafe {
                let (spare_size, p) = if cap <= C {
                    (C - cap, self.buf.local_mut_ptr().add(cap))
                } else {
                    let (len, p) = self.buf.heap_len_mut_p();
                    let len = len.as_usize();
                    (cap - len, p.add(len))
                };
                slice::from_raw_parts_mut(p.cast(), spare_size)
            }
        }
    }

    /// Returns small-vector content as a slice of `T`, along with the remaining spare capacity of
    /// the small-vector as a slice of `MaybeUninit<T>`.
    ///
    /// The returned spare capacity slice can be used to fill the small-vector with data
    /// (e.g. by reading from a file) before marking the data as initialized using the [`set_len`]
    /// method.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![32; 1, 2];   // <-- a small-vector for IO of 32 elements
    ///
    /// let (init, spare) = v.split_at_spare_mut();
    /// assert_eq!(init, &[1, 2]);
    ///
    /// assert_eq!(spare.len(), 30);        // <-- read another 2 elements into the small-vector
    /// spare[0].write(3);
    /// spare[1].write(4);
    ///
    /// unsafe { v.set_len(v.len() + 2) };  // <-- reflect the new size
    /// assert_eq!(v, [1, 2, 3, 4]);
    /// ```
    ///
    /// [`set_len`]: SmallVec::set_len
    #[inline]
    pub fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [mem::MaybeUninit<T>]) {
        let cap = self.capacity.as_usize();
        if mem::size_of::<T>() == 0 {
            let p = self.buf.local_mut_ptr();
            unsafe {
                (
                    slice::from_raw_parts_mut(p, cap),
                    slice::from_raw_parts_mut(p.add(cap).cast(), L::MAX - cap),
                )
            }
        } else if cap <= C {
            let p = self.buf.local_mut_ptr();
            unsafe {
                (
                    slice::from_raw_parts_mut(p, cap),
                    slice::from_raw_parts_mut(p.add(cap).cast(), C - cap),
                )
            }
        } else {
            let (len, p) = self.buf.heap_len_mut_p();
            let len = len.as_usize();
            unsafe {
                (
                    slice::from_raw_parts_mut(p, len),
                    slice::from_raw_parts_mut(p.add(len).cast(), cap - len),
                )
            }
        }
    }

    /// Checks if the small-vector has spare capacity.
    ///
    /// This is equivalent to `spare_capacity > 0`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; 1, 2];
    /// assert_eq!(v.capacity(), 4);
    /// assert_eq!(v.has_spare_capacity(), true);
    /// v.extend(3..5);
    /// assert_eq!(v.has_spare_capacity(), false);
    /// ```
    #[inline]
    pub fn has_spare_capacity(&self) -> bool {
        if mem::size_of::<T>() == 0 {
            L::MAX > self.capacity.as_usize()
        } else {
            let cap = self.capacity.as_usize();
            if cap <= C {
                cap < C
            } else {
                self.buf.heap_len().as_usize() < cap
            }
        }
    }

    /// Returns the length of small-vector.
    ///
    /// The length of small-vector is the number of elements it currently holds.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![8; 1, 2];
    /// assert_eq!(v.len(), 2);
    /// v.push(20);
    /// assert_eq!(v.len(), 3);
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        let cap = self.capacity.as_usize();
        if mem::size_of::<T>() == 0 || cap <= C {
            cap
        } else {
            self.buf.heap_len().as_usize()
        }
    }

    /// Checks if the small-vector is empty.
    ///
    /// This is equivalent to `len == 0`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![8; u64];
    /// assert_eq!(v.is_empty(), true);
    /// v.push(2);
    /// assert_eq!(v.is_empty(), false);
    /// v.clear();
    /// assert_eq!(v.is_empty(), true);
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Checks if the small-vector is full.
    ///
    /// This is equivalent to `len == capacity`.
    ///
    /// # Examples
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![3; u64; 1, 2];
    /// assert_eq!(v.capacity(), 3);
    /// assert_eq!(v.is_full(), false);
    /// v.push(3);
    /// assert_eq!(v.is_full(), true);
    /// ```
    #[inline]
    pub fn is_full(&self) -> bool {
        let cap = self.capacity.as_usize();
        if mem::size_of::<T>() == 0 {
            cap == L::MAX
        } else if cap <= C {
            cap == C
        } else {
            cap == self.buf.heap_len().as_usize()
        }
    }

    /// Forces the length of the small-vector to `len`.
    ///
    /// Note that this method doesn't [`drop`] elements, which may lead to a resource leak if
    /// `len < len()` and `T` has a custom [`Drop`] implementation. See [`truncate`] for a
    /// method that handles small-vector truncation properly.
    ///
    /// # Safety
    ///
    /// - `len` must be less than or equal to current small-vector's [`capacity`]
    /// - the elements at `old_len..len` must be initialized
    ///
    /// # Panics
    ///
    /// This method uses debug assertions to verify that `len` is in bounds.
    ///
    /// [`drop`]: core::mem::drop
    /// [`Drop`]: core::ops::Drop
    /// [`truncate`]: SmallVec::truncate
    /// [`capacity`]: SmallVec::capacity
    #[inline]
    pub unsafe fn set_len(&mut self, len: usize) {
        if mem::size_of::<T>() == 0 {
            debug_assert!(len <= L::MAX);
            self.capacity.set(len);
        } else {
            let cap = self.capacity.as_usize();
            if cap <= C {
                debug_assert!(len <= C);
                self.capacity.set(len);
            } else {
                debug_assert!(len <= cap);
                self.buf.set_heap_len(L::new(len))
            }
        }
    }

    /// Extracts a slice containing the entire small-vector.
    #[inline]
    pub fn as_slice(&self) -> &[T] {
        let (len, p) = self.len_p();
        unsafe { slice::from_raw_parts(p, len.as_usize()) }
    }

    /// Extracts a mutable slice of the entire small-vector.
    #[inline]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        let (len, p) = self.len_mut_p();
        unsafe { slice::from_raw_parts_mut(p, len.as_usize()) }
    }

    /// Returns a raw pointer to the small-vector's buffer.
    ///
    /// The returned value may point either to the local buffer or to the heap.
    #[inline]
    pub fn as_ptr(&self) -> *const T {
        if self.is_local() {
            self.buf.local_ptr()
        } else {
            self.buf.heap_ptr()
        }
    }

    /// Returns an unsafe mutable pointer to the small-vector's buffer.
    ///
    /// The returned value may point either to the local buffer or to the heap.
    #[inline]
    pub fn as_mut_ptr(&mut self) -> *mut T {
        if self.is_local() {
            self.buf.local_mut_ptr()
        } else {
            self.buf.heap_mut_ptr()
        }
    }

    /// Returns an iterator over the slice.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let v = small_vec![3; 1, 2];
    /// let mut iterator = v.iter();
    /// assert_eq!(iterator.next(), Some(&1));
    /// assert_eq!(iterator.next(), Some(&2));
    /// assert_eq!(iterator.next(), None);
    /// ```
    #[inline]
    pub fn iter(&self) -> slice::Iter<'_, T> {
        self.as_slice().iter()
    }

    /// Returns an iterator over the slice that allows modifying each value.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![3; 1, 2];
    /// for e in v.iter_mut() {
    ///     *e *= 2;
    /// }
    /// assert_eq!(v, [2, 4]);
    /// ```
    #[inline]
    pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
        self.as_mut_slice().iter_mut()
    }

    /// Returns (len, ptr)
    #[inline]
    fn len_p(&self) -> (L, *const T) {
        let cap = self.capacity;
        if mem::size_of::<T>() == 0 || cap.as_usize() <= C {
            (cap, self.buf.local_ptr())
        } else {
            self.buf.heap_len_p()
        }
    }

    /// Returns (len, mut_ptr)
    #[inline]
    fn len_mut_p(&mut self) -> (L, *mut T) {
        let cap = self.capacity;
        if mem::size_of::<T>() == 0 || cap.as_usize() <= C {
            (cap, self.buf.local_mut_ptr())
        } else {
            self.buf.heap_len_mut_p()
        }
    }

    /// Reserves capacity for at least the given number of additional elements.
    ///
    /// # Panics
    ///
    /// This method panics on any of the following conditions:
    /// - the total capacity overflows the length type `L::MAX`
    /// - the total capacity in bytes overflows `isize::MAX`
    /// - memory allocation fails ([`handle_alloc_error`] is called)
    ///
    /// See [`try_reserve`] for a method that returns [`ReservationError`] instead.
    ///
    /// [`try_reserve`]: SmallVec::try_reserve
    /// [`handle_alloc_error`]: ::alloc::alloc::handle_alloc_error
    #[inline]
    pub fn reserve(&mut self, additional: usize) {
        self.try_reserve_impl::<DOHAE>(additional)
            .expect("smallvec reserve failed");
    }

    /// Tries to reserve capacity for at least the given number of additional elements.
    ///
    /// This is a non-panic version of [`reserve`].
    ///
    /// [`reserve`]: SmallVec::reserve
    #[inline]
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), ReservationError> {
        self.try_reserve_impl::<NOHAE>(additional).map(|_| ())
    }

    #[inline(never)]
    fn try_reserve_impl<const HAE: bool>(
        &mut self,
        additional: usize,
    ) -> Result<(&mut L, *mut T), ReservationError> {
        self.reserve_core::<_, HAE>(additional, |l, a| {
            Ok(l.checked_add_usize(a)
                .ok_or(ReservationError::CapacityOverflow)?
                .next_power_of_two_or_max())
        })
    }

    /// Reserves the minimum amount of capacity space for a given number of additional elements.
    ///
    /// # Panics
    ///
    /// This method panics on any of the following conditions:
    /// - the total capacity overflows the length type `L::MAX`
    /// - the total capacity in bytes overflows `isize::MAX`
    /// - memory allocation fails ([`handle_alloc_error`] is called)
    ///
    /// See [`try_reserve_exact`] for a method that returns [`ReservationError`] instead.
    ///
    /// [`try_reserve_exact`]: SmallVec::try_reserve_exact
    /// [`handle_alloc_error`]: ::alloc::alloc::handle_alloc_error
    #[inline]
    pub fn reserve_exact(&mut self, additional: usize) {
        self.try_reserve_exact_impl::<DOHAE>(additional)
            .expect("smallvec reserve_exact failed");
    }

    /// Tries to reserve minimum amount of space for a given number of additional elements.
    ///
    /// This method tries to reserve the minimum amount of memory required for `additional`
    /// elements. Upon successful completion the capacity of small-vector is greater or equal
    /// `len + additional`. The method does nothing if the capacity is already sufficient.
    ///
    /// This is a non-panic version of [`reserve_exact`].
    ///
    /// [`reserve_exact`]: SmallVec::reserve_exact
    #[inline]
    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), ReservationError> {
        self.try_reserve_exact_impl::<NOHAE>(additional).map(|_| ())
    }

    #[inline(never)]
    fn try_reserve_exact_impl<const HAE: bool>(
        &mut self,
        additional: usize,
    ) -> Result<(&mut L, *mut T), ReservationError> {
        self.reserve_core::<_, HAE>(additional, |l, a| {
            l.checked_add_usize(a)
                .ok_or(ReservationError::CapacityOverflow)
        })
    }

    #[inline]
    fn reserve_core<F, const HAE: bool>(
        &mut self,
        additional: usize,
        nc: F,
    ) -> Result<(&mut L, *mut T), ReservationError>
    where
        F: FnOnce(L, usize) -> Result<L, ReservationError>,
    {
        let cap = self.capacity.as_usize();
        if mem::size_of::<T>() == 0 {
            let len = cap;
            let cap = L::MAX;
            if cap - len >= additional {
                Ok((&mut self.capacity, self.buf.local_mut_ptr()))
            } else {
                Err(ReservationError::CapacityOverflow)
            }
        } else if cap <= C {
            let len = cap;
            let cap = C;
            if cap - len >= additional {
                return Ok((&mut self.capacity, self.buf.local_mut_ptr()));
            }

            let new_cap = nc(self.capacity, additional)?;
            debug_assert!(new_cap > C);
            debug_assert!(new_cap > cap);

            let p = unsafe {
                // if spare memory policy is a noop do not copy the old spare memory
                let prefix = if SM::NOOP { len } else { cap };
                let tmp = alloc_buffer::<T, HAE>(new_cap.as_usize())?;
                ptr::copy_nonoverlapping(self.buf.local_ptr(), tmp, prefix);
                if !SM::NOOP {
                    // initialize the new spare memory only; old spare memory was preserved
                    SM::init(tmp.add(cap), new_cap.as_usize() - cap);
                    SM::init(self.buf.local_mut_ptr(), len)
                }
                tmp
            };

            self.buf.set_heap(p, self.capacity);
            self.capacity = new_cap;
            Ok(self.buf.heap_mut_len_mut_p())
        } else {
            let len = self.buf.heap_len();
            if cap - len.as_usize() >= additional {
                return Ok(self.buf.heap_mut_len_mut_p());
            }
            let new_cap = nc(len, additional)?;
            debug_assert!(new_cap > cap);
            let p = unsafe {
                let tmp = realloc_buffer::<T, SM, HAE>(
                    self.buf.heap_mut_ptr(),
                    len.as_usize(),
                    cap,
                    new_cap.as_usize(),
                )?;
                SM::init(tmp.add(cap), new_cap.as_usize() - cap);
                tmp
            };
            self.buf.set_heap_ptr(p);
            self.capacity = new_cap;
            Ok(self.buf.heap_mut_len_mut_p())
        }
    }

    /// Appends an element to the back of the small-vector.
    ///
    /// # Panics
    ///
    /// See [`reserve`] for panic conditions.
    ///
    /// See [`try_push`] for a non-panic version of this method.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![2; u64];
    /// assert_eq!(v, []);
    /// v.push(1);
    /// v.push(2);
    /// assert_eq!(v, [1, 2]);
    /// ```
    ///
    /// [`reserve`]: SmallVec::reserve
    /// [`try_push`]: SmallVec::try_push
    #[inline]
    pub fn push(&mut self, e: T) {
        self.try_push_impl::<DOHAE>(e)
            .expect("smallvec push failed")
    }

    /// Tries to append an element to the back of the small-vector.
    ///
    /// This is a non-panic version of [`push`].
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::{small_vec, mem::errors::ReservationError};
    /// # fn foo() -> Result<(), ReservationError> {
    /// let mut v = small_vec![2; u64];
    /// assert_eq!(v, []);
    /// v.try_push(10)?;
    /// v.try_push(20)?;
    /// assert_eq!(v, [10, 20]);
    /// # Ok(())
    /// # }
    /// # foo();
    /// ```
    ///
    /// [`push`]: SmallVec::push
    #[inline]
    pub fn try_push(&mut self, e: T) -> Result<(), ReservationError> {
        self.try_push_impl::<NOHAE>(e)
    }

    #[inline]
    #[allow(clippy::comparison_chain)]
    fn try_push_impl<const HAE: bool>(&mut self, e: T) -> Result<(), ReservationError> {
        let cap = self.capacity.as_usize();
        if mem::size_of::<T>() == 0 {
            if cap < L::MAX {
                self.capacity.add_assign(1);
                unsafe { self.buf.local_mut_ptr().write(e) };
            } else {
                return Err(ReservationError::CapacityOverflow);
            }
            Ok(())
        } else {
            let len;
            let p;
            if cap < C {
                p = self.buf.local_mut_ptr();
                len = cap;
                self.capacity.add_assign(1);
            } else if cap > C {
                len = self.buf.heap_len().as_usize();
                if len == cap {
                    self.try_reserve_impl::<HAE>(1)?;
                }
                p = self.buf.heap_mut_ptr();
                self.buf.heap_len_add_assign(1);
            } else {
                self.try_reserve_impl::<HAE>(1)?;
                p = self.buf.heap_mut_ptr();
                len = self.buf.heap_len().as_usize();
                self.buf.heap_len_add_assign(1);
            }
            unsafe {
                p.add(len).write(e);
            }
            Ok(())
        }
    }

    /// Removes the last element from a small-vector and returns it, or [`None`] if it is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![3; 10, 13];
    /// assert_eq!(v.pop(), Some(13));
    /// assert_eq!(v.pop(), Some(10));
    /// assert_eq!(v.pop(), None);
    /// assert_eq!(v, []);
    /// ```
    #[inline]
    #[allow(clippy::comparison_chain)]
    pub fn pop(&mut self) -> Option<T> {
        if mem::size_of::<T>() == 0 {
            let len = self.capacity.as_usize();
            if len > 0 {
                self.capacity.sub_assign(1);
                unsafe { Some(self.buf.local_ptr().read()) }
            } else {
                None
            }
        } else {
            let cap = self.capacity.as_usize();
            if cap <= C {
                if cap > 0 {
                    let new_len = cap - 1;
                    self.capacity = L::new(new_len);
                    unsafe {
                        let p = self.buf.local_mut_ptr().add(new_len);
                        let e = p.read();
                        SM::init(p, 1);
                        Some(e)
                    }
                } else {
                    None
                }
            } else {
                let len = self.buf.heap_len().as_usize();
                if len > 0 {
                    let new_len = len - 1;
                    self.buf.set_heap_len(L::new(new_len));
                    unsafe {
                        let p = self.buf.heap_mut_ptr().add(new_len);
                        let e = p.read();
                        SM::init(p, 1);
                        Some(e)
                    }
                } else {
                    None
                }
            }
        }
    }

    /// Shortens the small-vector, keeping the first `len` elements and dropping the rest.
    ///
    /// If `len` is greater than small-vector's current length, this has no effect.
    ///
    /// # Safety
    ///
    /// Spare memory policy is invoked only if all truncated elements drop successfully. I.e, if
    /// any of the truncated elements panics during drop, spare memory policy isn't invoked
    /// at all, including on successfully dropped elements.
    ///
    /// # Examples
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![8; 1, 2, 3];
    /// assert_eq!(v, [1, 2, 3]);
    /// v.truncate(1);
    /// assert_eq!(v, [1]);
    /// v.truncate(2);
    /// assert_eq!(v, [1]);
    /// ```
    #[inline]
    pub fn truncate(&mut self, len: usize) {
        let my_len = self.len();

        if len < my_len {
            unsafe {
                // `drop` of any of the truncated slots may panic, which may trigger destruction
                // of `self`. Thus, update `self.len` *before* calling `drop_in_place` to avoid
                // a possible double-drop of a truncated slot.
                self.set_len(len);

                // create a slice of truncated slots
                let s = slice::from_raw_parts_mut(self.as_mut_ptr().add(len), my_len - len);

                // `drop_in_place` drops every slot in the slice. If one slot panics, it will first
                // try to drop the rest and only then re-raise the panic.
                // If more than one slot panic, the program aborts.
                ptr::drop_in_place(s);

                // TODO: invoke SM-policy on every successfully dropped element, even if one panics

                // invoke spare memory policy
                SM::init(s.as_mut_ptr(), s.len());
            }
        }
    }

    /// Clears the small-vector, dropping all values.
    ///
    /// # Examples
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![16; 1, 2, 3];
    /// assert_eq!(v, [1, 2, 3]);
    /// v.clear();
    /// assert_eq!(v, []);
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        self.truncate(0)
    }

    /// Creates a small-vector from an iterator.
    ///
    /// Returns [`ReservationError`] if memory allocation fails.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::{
    /// #     smallvec::SmallVec,
    /// #     len::U8, mem::{Uninitialized, errors::ReservationError},
    /// # };
    /// # fn example() -> Result<(), ReservationError> {
    /// type SV = SmallVec<usize, 3, U8, Uninitialized>;
    /// let a = [1, 2, 3];
    /// let v = SV::try_from_iter(a.iter().filter(|x| **x % 2 == 0).cloned())?;
    /// assert_eq!(v, [2]);
    /// # Ok(())
    /// # }
    /// ```
    #[inline]
    pub fn try_from_iter<I>(iter: I) -> Result<Self, ReservationError>
    where
        I: IntoIterator<Item = T>,
    {
        Self::try_from_iter_impl::<I, NOHAE>(iter)
    }

    #[inline]
    fn try_from_iter_impl<I, const HAE: bool>(iter: I) -> Result<Self, ReservationError>
    where
        I: IntoIterator<Item = T>,
    {
        let mut tmp = Self::new();
        tmp.try_extend_impl::<I, HAE>(iter)?;
        Ok(tmp)
    }

    #[inline]
    fn try_extend_impl<I, const HAE: bool>(&mut self, iter: I) -> Result<(), ReservationError>
    where
        I: IntoIterator<Item = T>,
    {
        let it = iter.into_iter();
        let (min, max) = it.size_hint();
        let cap = max.unwrap_or(min);

        let len = self.len();
        let mut g = SetLenOnDrop::new(self, len);
        g.sv.try_reserve_impl::<HAE>(cap)?;

        let mut cap = g.sv.capacity();
        let mut p = unsafe { g.sv.as_mut_ptr().add(len) };

        for e in it {
            unsafe {
                if g.len >= cap {
                    g.sv.set_len(g.len);
                    let (_, tmp_p) = g.sv.try_reserve_impl::<HAE>(1)?;
                    p = tmp_p.add(g.len);
                    cap = g.sv.capacity();
                }
                p.write(e);
                p = p.add(1);
                g.len += 1;
            }
        }

        drop(g);
        Ok(())
    }

    /// Inserts an element at position `index` within the small-vector, shifting all elements after it to the right.
    ///
    /// # Panics
    ///
    /// This method panics if `index > len`, or when capacity reservation error occurs.
    /// See [`reserve`] for more information.
    ///
    /// See [`try_insert`] for a non-panic version of this method.
    ///
    /// [`reserve`]: SmallVec::reserve
    /// [`try_insert`]: SmallVec::try_insert
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; usize; 1, 2, 4];
    /// v.insert(2, 3);
    /// assert_eq!(v, [1, 2, 3, 4]);
    /// v.insert(4, 5);
    /// assert_eq!(v, [1, 2, 3, 4, 5]);
    /// ```
    #[inline]
    pub fn insert(&mut self, index: usize, value: T) {
        self.try_insert_impl::<DOHAE>(index, value)
            .expect("smallvec insert failed")
    }

    /// Tries to insert an element at position `index` within the small-vector, shifting all elements after it to the right.
    ///
    /// Returns `InsertError::InvalidIndex` if `index > len`. Or `InsertError::ReservationError`
    /// if capacity reservation fails. See [`try_reserve`] for more information.
    ///
    /// This is a non-panic version of [`insert`].
    ///
    /// [`try_reserve`]: SmallVec::try_reserve
    /// [`insert`]: SmallVec::insert
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::{small_vec, smallvec::errors::InsertError};
    /// # fn foo() -> Result<(), InsertError> {
    /// let mut v = small_vec![4; usize; 1, 2, 4];
    /// v.try_insert(2, 3)?;
    /// assert_eq!(v, [1, 2, 3, 4]);
    /// v.try_insert(4, 5)?;
    /// assert_eq!(v, [1, 2, 3, 4, 5]);
    /// # Ok(())
    /// # }
    /// # foo().unwrap();
    /// ```
    #[inline]
    pub fn try_insert(&mut self, index: usize, value: T) -> Result<(), InsertError> {
        self.try_insert_impl::<NOHAE>(index, value)
    }

    #[inline]
    #[allow(clippy::comparison_chain)]
    fn try_insert_impl<const HAE: bool>(
        &mut self,
        index: usize,
        value: T,
    ) -> Result<(), InsertError> {
        let cap = self.capacity.as_usize();
        if mem::size_of::<T>() == 0 {
            if index > cap {
                Err(InsertError::InvalidIndex)
            } else if cap < L::MAX {
                self.capacity.add_assign(1);
                unsafe { self.buf.local_mut_ptr().write(value) };
                Ok(())
            } else {
                Err(InsertError::ReservationError(
                    ReservationError::CapacityOverflow,
                ))
            }
        } else {
            let len;
            let p;
            if cap < C {
                p = self.buf.local_mut_ptr();
                len = cap;
                if index > len {
                    return Err(InsertError::InvalidIndex);
                }
                self.capacity.add_assign(1);
            } else if cap > C {
                len = self.buf.heap_len().as_usize();
                if index > len {
                    return Err(InsertError::InvalidIndex);
                }
                if len == cap {
                    self.try_reserve_impl::<HAE>(1)
                        .map_err(InsertError::ReservationError)?;
                }
                p = self.buf.heap_mut_ptr();
                self.buf.heap_len_add_assign(1);
            } else {
                if index > cap {
                    return Err(InsertError::InvalidIndex);
                }
                self.try_reserve_impl::<HAE>(1)
                    .map_err(InsertError::ReservationError)?;
                p = self.buf.heap_mut_ptr();
                len = self.buf.heap_len().as_usize();
                self.buf.heap_len_add_assign(1);
            }
            unsafe {
                let p = p.add(index);
                ptr::copy(p, p.add(1), len - index);
                p.write(value);
            }
            Ok(())
        }
    }

    /// Removes and returns the element at position `index` within the small-vector, shifting
    /// all elements after it to the left.
    ///
    /// # Panics
    ///
    /// This method panics if `index` is out of bounds.
    ///
    /// See [`try_remove`] for a non-panic version of this method.
    ///
    /// [`try_remove`]: SmallVec::try_remove
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; u64; 1, 2, 3];
    /// assert_eq!(v.remove(1), 2);
    /// assert_eq!(v, [1, 3]);
    /// ```
    ///
    /// The following example panics because `index` is out of bounds:
    ///
    /// ```should_panic
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; u64; 1, 2, 3];
    /// v.remove(4);
    /// ```
    #[inline]
    pub fn remove(&mut self, index: usize) -> T {
        self.try_remove(index)
            .expect("smallvec remove: index out of bounds")
    }

    /// Tries to remove and return the element at position `index` within the small-vector, shifting
    /// all elements after it to the left.
    ///
    /// Returns `None` if `index` is out of bounds.
    ///
    /// This is a non-panic version of [`remove`].
    ///
    /// [`remove`]: SmallVec::remove
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; u64; 1, 2, 3];
    /// assert_eq!(v.try_remove(1), Some(2));
    /// assert_eq!(v.try_remove(2), None);
    /// assert_eq!(v, [1, 3]);
    /// ```
    #[inline]
    pub fn try_remove(&mut self, index: usize) -> Option<T> {
        if mem::size_of::<T>() == 0 {
            let len = self.capacity.as_usize();
            if index < len {
                self.capacity.sub_assign(1);
                unsafe { Some(self.buf.local_ptr().read()) }
            } else {
                None
            }
        } else {
            let len;
            let p;
            let cap = self.capacity.as_usize();
            if cap <= C {
                if index < cap {
                    self.capacity.sub_assign(1);
                    p = self.buf.local_mut_ptr();
                    len = cap;
                } else {
                    return None;
                }
            } else {
                len = self.buf.heap_len().as_usize();
                if index < len {
                    self.buf.set_heap_len(L::new(len - 1));
                    p = self.buf.heap_mut_ptr();
                } else {
                    return None;
                }
            }
            unsafe {
                let p = p.add(index);
                let value = p.read();
                let to_copy = len - index - 1;
                ptr::copy(p.add(1), p, to_copy);
                SM::init(p.add(to_copy), 1);
                Some(value)
            }
        }
    }

    /// Removes an element at position `index` and returns it.
    ///
    /// The removed element is replaced by the last element of the small-vector.
    /// This does not preserve ordering, but is O(1).
    ///
    /// # Panics
    ///
    /// This method panics of `index` is out of bounds. See [`try_swap_remove`] for a non-panic
    /// version of this method.
    ///
    /// [`try_swap_remove`]: SmallVec::try_swap_remove
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; u64; 1, 2, 3, 4];
    /// assert_eq!(v.swap_remove(1), 2);
    /// assert_eq!(v, [1, 4, 3]);
    /// ```
    #[inline]
    pub fn swap_remove(&mut self, index: usize) -> T {
        self.try_swap_remove(index)
            .expect("smallvec swap_remove: index out of bounds")
    }

    /// Tries to remove an element at position `index` and returns it.
    ///
    /// Returns `None` if `index` is out of bounds.
    ///
    /// The removed element is replaced by the last element of the small-vector.
    /// This does not preserve ordering, but is O(1).
    ///
    /// This is a non-panic version of [`swap_remove`].
    ///
    /// [`swap_remove`]: SmallVec::swap_remove
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; u64; 1, 2, 3, 4];
    /// assert_eq!(v.try_swap_remove(1), Some(2));
    /// assert_eq!(v.try_swap_remove(10), None);
    /// assert_eq!(v, [1, 4, 3]);
    /// ```
    #[inline]
    pub fn try_swap_remove(&mut self, index: usize) -> Option<T> {
        if mem::size_of::<T>() == 0 {
            let len = self.capacity.as_usize();
            if index < len {
                self.capacity.sub_assign(1);
                unsafe { Some(self.buf.local_ptr().read()) }
            } else {
                None
            }
        } else {
            let len;
            let p;
            let cap = self.capacity.as_usize();
            if cap <= C {
                if index < cap {
                    self.capacity.sub_assign(1);
                    p = self.buf.local_mut_ptr();
                    len = cap;
                } else {
                    return None;
                }
            } else {
                len = self.buf.heap_len().as_usize();
                if index < len {
                    self.buf.set_heap_len(L::new(len - 1));
                    p = self.buf.heap_mut_ptr();
                } else {
                    return None;
                }
            }
            unsafe {
                let p_last = p.add(len - 1);
                let p = p.add(index);
                let value = p.read();
                ptr::copy(p_last, p, 1);
                SM::init(p_last, 1);
                Some(value)
            }
        }
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
    /// This method operates in place, visiting each element exactly once in the original order,
    /// and preserves the order of the retained elements.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![5; 0, 1, 2, 3, 4];
    /// assert_eq!(v, [0, 1, 2, 3, 4]);
    /// v.retain(|e| (*e & 1) != 0);
    /// assert_eq!(v, [1, 3]);
    /// ```
    #[inline]
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.retain_mut(|e| f(e))
    }

    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
    ///
    /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
    /// This method operates in place, visiting each element exactly once in the original order,
    /// and preserves the order of the retained elements.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![5; 0, 1, 2, 3, 4];
    /// assert_eq!(v, [0, 1, 2, 3, 4]);
    /// v.retain_mut(|e| if (*e & 1) == 0 {
    ///    *e *= *e;
    ///    true
    /// } else {
    ///    false
    /// });
    /// assert_eq!(v, [0, 4, 16]);
    /// ```
    #[inline]
    pub fn retain_mut<F>(&mut self, mut f: F)
    where
        F: FnMut(&mut T) -> bool,
    {
        let mut g = RetainGuard {
            sv: self,
            len: 0,
            deleted: 0,
            processed: 0,
        };

        let cap = g.sv.capacity.as_usize();

        // set `len` to zero, to avoid double-drop of deleted items.
        // `len` is restored by RetainGuard.
        let (len, p) = if mem::size_of::<T>() == 0 || cap <= C {
            g.sv.capacity.set(0);
            (cap, g.sv.buf.local_mut_ptr())
        } else {
            let (l, p) = g.sv.buf.heap_len_mut_p();
            g.sv.buf.set_heap_len(L::new(0));
            (l.as_usize(), p)
        };

        g.len = len;

        unsafe {
            // no empty slot found yet, so there is nothing to move
            while g.processed < len {
                let item_mut_ref = &mut *p.add(g.processed);
                if !f(item_mut_ref) {
                    // update counters before drop_in_place, as it may panic
                    g.processed += 1;
                    g.deleted += 1;
                    ptr::drop_in_place(item_mut_ref);
                    break;
                }
                g.processed += 1;
            }

            // If there are items left to process, there must be an empty slot.
            // Move every retained slot to an empty one.
            while g.processed < len {
                let item_mut_ref = &mut *p.add(g.processed);
                if !f(item_mut_ref) {
                    // update counters before drop_in_place, as it may panic
                    g.processed += 1;
                    g.deleted += 1;
                    ptr::drop_in_place(item_mut_ref);
                } else {
                    ptr::copy_nonoverlapping(
                        item_mut_ref as *const _,
                        p.add(g.processed - g.deleted),
                        1,
                    );
                    g.processed += 1;
                }
            }
        }
    }

    /// Resizes the small-vector in-place so that `len` is equal to `new_len`.
    ///
    /// If `new_len` is greater than `len`, the small-vector is extended by the difference,
    /// with each additional slot filled with the result of calling the closure `f`.
    /// The return values from `f` will end up in the small-vector in the order they have been
    /// generated.
    ///
    /// If `new_len` is less than `len`, the small-vector is simply truncated.
    ///
    /// # Panics
    ///
    /// This method panics on capacity reservation errors. See [`reserve`] for more information.
    ///
    /// See [`try_resize_with`] for a non-panic version of this method.
    ///
    /// [`reserve`]: SmallVec::reserve
    /// [`try_resize_with`]: SmallVec::try_resize_with
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![8; u64; 0, 0];
    /// assert_eq!(v, [0, 0]);
    /// let mut i = 9;
    /// v.resize_with(5, || { i += 1; i });
    /// assert_eq!(v, [0, 0, 10, 11, 12]);
    /// ```
    #[inline]
    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
    where
        F: FnMut() -> T,
    {
        self.try_resize_with_impl::<F, DOHAE>(new_len, f)
            .expect("smallvec resize_with failed")
    }

    /// Tries to resize the small-vector in-place so that `len` is equal to `new_len`.
    ///
    /// If `new_len` is greater than `len`, the small-vector is extended by the difference,
    /// with each additional slot filled with the result of calling the closure `f`.
    /// The return values from `f` will end up in the small-vector in the order they have been
    /// generated.
    ///
    /// If `new_len` is less than `len`, the small-vector is simply truncated.
    ///
    /// This is a non-panic version of [`resize_with`].
    ///
    /// [`resize_with`]: SmallVec::resize_with
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::{small_vec, mem::errors::ReservationError};
    /// # fn foo() -> Result<(), ReservationError> {
    /// let mut v = small_vec![8; u64];
    /// assert_eq!(v, []);
    /// v.try_resize_with(5, || 5)?;
    /// assert_eq!(v, [5, 5, 5, 5, 5]);
    /// v.try_resize_with(5, || 0)?;
    /// assert_eq!(v, [5, 5, 5, 5, 5]);
    /// v.try_resize_with(2, || 0)?;
    /// assert_eq!(v, [5, 5]);
    /// # Ok(())
    /// # }
    /// # foo().unwrap();
    /// ```
    #[inline]
    pub fn try_resize_with<F>(&mut self, new_len: usize, f: F) -> Result<(), ReservationError>
    where
        F: FnMut() -> T,
    {
        self.try_resize_with_impl::<F, NOHAE>(new_len, f)
    }

    #[inline]
    #[allow(clippy::comparison_chain)]
    fn try_resize_with_impl<F, const HAE: bool>(
        &mut self,
        new_len: usize,
        mut f: F,
    ) -> Result<(), ReservationError>
    where
        F: FnMut() -> T,
    {
        let p;
        let len;

        let cap = self.capacity.as_usize();
        let mut g = SetLenOnDrop::unarmed(self, 0);

        if mem::size_of::<T>() == 0 || cap <= C {
            len = cap;
            if new_len < len {
                g.sv.truncate(new_len);
                return Ok(());
            } else if new_len > len {
                if mem::size_of::<T>() != 0 && new_len > C {
                    g.sv.try_reserve_impl::<HAE>(new_len - len)?;
                    p = g.sv.buf.heap_mut_ptr();
                } else {
                    if mem::size_of::<T>() == 0 && new_len > L::MAX {
                        return Err(ReservationError::CapacityOverflow);
                    }
                    p = g.sv.buf.local_mut_ptr();
                }
            } else {
                return Ok(());
            }
        } else {
            len = g.sv.buf.heap_len().as_usize();
            if new_len < len {
                g.sv.truncate(new_len);
                return Ok(());
            } else if new_len > len {
                if new_len > cap {
                    g.sv.try_reserve_impl::<HAE>(new_len - len)?;
                }
                p = g.sv.buf.heap_mut_ptr();
            } else {
                return Ok(());
            }
        }

        g.len = len;
        g.armed = true;

        unsafe {
            let mut p = p.add(len);
            while g.len < new_len {
                p.write(f());
                p = p.add(1);
                g.len += 1;
            }
        }

        Ok(())
    }

    /// Creates a draining iterator that removes the specified range in the small-vector
    /// and yields the removed items.
    ///
    /// When the iterator is dropped, all elements in the range are removed from the small-vector,
    /// even if the iterator was not fully consumed.
    /// If the iterator is not dropped (with [`mem::forget`] for example),
    /// it is unspecified how many elements are removed.
    ///
    /// # Panics
    ///
    /// Panics if the starting point is greater than the end point or if the end point is greater
    /// than the length of the vector.
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![5; usize; 1, 2, 3, 4, 5];
    /// assert_eq!(v, [1, 2, 3, 4, 5]);
    /// for (index, i) in v.drain(0..3).enumerate() {
    ///     assert_eq!(index + 1, i);
    /// }
    /// assert_eq!(v, [4, 5]);
    /// ```
    ///
    /// [`mem::forget`]: core::mem::forget
    #[inline]
    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, L, SM, C>
    where
        R: RangeBounds<usize>,
    {
        let end = match range.end_bound() {
            Bound::Included(e) => e
                .checked_add(1)
                .unwrap_or_else(|| panic!("end bound overflows")),
            Bound::Excluded(e) => *e,
            Bound::Unbounded => self.len(),
        };

        let len = self.len();
        if end > len {
            panic!("invalid end bound");
        }

        let start = match range.start_bound() {
            Bound::Included(s) => *s,
            Bound::Excluded(s) => s
                .checked_add(1)
                .unwrap_or_else(|| panic!("start bound overflows")),
            Bound::Unbounded => 0,
        };

        if start > end {
            panic!("invalid range");
        }

        unsafe {
            let (iter, tail, tail_len) = if start < end {
                // set `len` to reflect the head only
                self.set_len(start);

                (
                    slice::from_raw_parts_mut(self.as_mut_ptr().add(start), end - start).iter(),
                    L::new(end),
                    L::new(len - end),
                )
            } else {
                // empty drained range, mark it with an impossible combination of `tail/tail_len`
                ([].iter(), L::new(L::MAX), L::new(L::MAX))
            };

            Drain {
                sv: ptr::NonNull::new_unchecked(self),
                iter,
                tail,
                tail_len,
            }
        }
    }
}

impl<T, const C: usize, L, SM> SmallVec<T, C, L, SM>
where
    T: Clone,
    L: LengthType,
    SM: SpareMemoryPolicy<T>,
{
    /// Resizes the small-vector in-place so that `len` is equal to `new_len`.
    ///
    /// If `new_len` is greater than `len`, the small-vector is extended by the difference,
    /// with each additional slot filled with `value`. If `new_len` is less than `len`,
    /// the small-vector is simply truncated.
    ///
    /// This method requires `T` to implement [`Clone`], in order to be able to clone the passed
    /// value. If you need more flexibility (or want to rely on [`Default`] instead of [`Clone`]),
    /// use [`resize_with`]. If you only need to resize to a smaller size, use [`truncate`].
    ///
    /// # Panics
    ///
    /// This method may panic on capacity reservation errors. See [`reserve`] for more information.
    ///
    /// See [`try_resize`] for a non-panic version of this method.
    ///
    /// [`resize_with`]: SmallVec::resize_with
    /// [`truncate`]: SmallVec::truncate
    /// [`reserve`]: SmallVec::reserve
    /// [`try_resize`]: SmallVec::try_resize
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![4; u64; 1];
    /// v.resize(4, 0);
    /// assert_eq!(v, [1, 0, 0, 0]);
    /// v.resize(2, 3);
    /// assert_eq!(v, [1, 0]);
    /// ```
    #[inline]
    pub fn resize(&mut self, new_len: usize, value: T) {
        self.try_resize_impl::<DOHAE>(new_len, value)
            .expect("smallvec resize failed")
    }

    /// Tries to resize the small-vector in-place so that `len` is equal to `new_len`.
    ///
    /// If `new_len` is greater than `len`, the small-vector is extended by the difference,
    /// with each additional slot filled with `value`. If `new_len` is less than `len`,
    /// the small-vector is simply truncated.
    ///
    /// This method requires `T` to implement [`Clone`], in order to be able to clone the passed
    /// value. If you need more flexibility (or want to rely on [`Default`] instead of [`Clone`]),
    /// use [`try_resize_with`]. If you only need to resize to a smaller size, use [`truncate`].
    ///
    /// This is a non-panic version of [`resize`].
    ///
    /// [`try_resize_with`]: SmallVec::try_resize_with
    /// [`truncate`]: SmallVec::truncate
    /// [`resize`]: SmallVec::resize
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use cds::{small_vec, mem::errors::ReservationError};
    /// # fn foo() -> Result<(), ReservationError> {
    /// let mut v = small_vec![2; usize];
    /// assert_eq!(v, []);
    /// v.try_resize(2, 7)?;
    /// assert_eq!(v, [7, 7]);
    /// v.try_resize(3, 5)?;
    /// assert_eq!(v, [7, 7, 5]);
    /// v.try_resize(1, 1)?;
    /// assert_eq!(v, [7]);
    /// # Ok(())
    /// # }
    /// # foo().unwrap();
    /// ```
    #[inline]
    pub fn try_resize(&mut self, new_len: usize, value: T) -> Result<(), ReservationError> {
        self.try_resize_impl::<NOHAE>(new_len, value)
    }

    #[inline]
    #[allow(clippy::comparison_chain)]
    fn try_resize_impl<const HAE: bool>(
        &mut self,
        new_len: usize,
        value: T,
    ) -> Result<(), ReservationError> {
        let p;
        let len;

        let cap = self.capacity.as_usize();
        let mut g = SetLenOnDrop::unarmed(self, 0);

        if mem::size_of::<T>() == 0 || cap <= C {
            len = cap;
            if new_len < len {
                g.sv.truncate(new_len);
                return Ok(());
            } else if new_len > len {
                if mem::size_of::<T>() != 0 && new_len > C {
                    g.sv.try_reserve_impl::<HAE>(new_len - len)?;
                    p = g.sv.buf.heap_mut_ptr();
                } else {
                    if mem::size_of::<T>() == 0 && new_len > L::MAX {
                        return Err(ReservationError::CapacityOverflow);
                    }
                    p = g.sv.buf.local_mut_ptr();
                }
            } else {
                return Ok(());
            }
        } else {
            len = g.sv.buf.heap_len().as_usize();
            if new_len < len {
                g.sv.truncate(new_len);
                return Ok(());
            } else if new_len > len {
                if new_len > cap {
                    g.sv.try_reserve_impl::<HAE>(new_len - len)?;
                }
                p = g.sv.buf.heap_mut_ptr();
            } else {
                return Ok(());
            }
        }

        g.len = len;
        g.armed = true;

        unsafe {
            let mut p = p.add(len);
            let to_add = new_len - len;

            for _ in 1..to_add {
                p.write(value.clone());
                p = p.add(1);
                g.len += 1;
            }

            // do not clone the last value
            if to_add > 0 {
                p.write(value);
                g.len += 1;
            }
        }
        Ok(())
    }
}

impl<T, const C: usize, L, SM> SmallVec<T, C, L, SM>
where
    T: Copy,
    L: LengthType,
    SM: SpareMemoryPolicy<T>,
{
    /// Extends the small-vector by copying elements from a slice.
    ///
    /// This is optimized for [`Copy`] types - elements are copied bytewise.
    ///
    /// # Panics
    ///
    /// This method panics on memory reservation errors. See [`reserve`] for more info.
    ///
    /// See [`try_copy_from_slice`] for a non-panic version of this method.
    ///
    /// [`reserve`]: SmallVec::reserve
    /// [`try_copy_from_slice`]: SmallVec::try_copy_from_slice
    ///
    /// # Examples
    /// ```rust
    /// # use cds::small_vec;
    /// let mut v = small_vec![5; 1, 2];
    /// assert_eq!(v, [1, 2]);
    /// v.copy_from_slice(&[3, 4]);
    /// assert_eq!(v, [1, 2, 3, 4]);
    /// ```
    #[inline]
    pub fn copy_from_slice(&mut self, s: &[T]) {
        self.try_copy_from_slice_impl::<DOHAE>(s)
            .expect("smallvec copy_from_slice failed")
    }

    /// Tries to extend the small-vector by copying elements from a slice.
    ///
    /// This is optimized for [`Copy`] types - elements are copied bytewise.
    ///
    /// This is a non-panic version of [`copy_from_slice`].
    ///
    /// [`copy_from_slice`]: SmallVec::copy_from_slice
    ///
    /// # Examples
    /// ```rust
    /// # use cds::{small_vec, mem::errors::ReservationError};
    /// # fn foo() -> Result<(), ReservationError> {
    /// let mut v = small_vec![5; 1, 2];
    /// assert_eq!(v, [1, 2]);
    /// v.try_copy_from_slice(&[3, 4])?;
    /// assert_eq!(v, [1, 2, 3, 4]);
    /// # Ok(())
    /// # }
    /// # foo().unwrap();
    /// ```
    #[inline]
    pub fn try_copy_from_slice(&mut self, s: &[T]) -> Result<(), ReservationError> {
        self.try_copy_from_slice_impl::<NOHAE>(s)
    }

    #[inline]
    fn try_copy_from_slice_impl<const HAE: bool>(
        &mut self,
        s: &[T],
    ) -> Result<(), ReservationError> {
        if mem::size_of::<T>() == 0 {
            if let Some(c) = self.capacity.checked_add_usize(s.len()) {
                self.capacity = c;
                Ok(())
            } else {
                Err(ReservationError::CapacityOverflow)
            }
        } else {
            let cur_len;
            let cap = self.capacity.as_usize();
            let (len, p) = if cap <= C {
                cur_len = cap;
                let cap = C;
                if cap - cur_len >= s.len() {
                    (&mut self.capacity, self.buf.local_mut_ptr())
                } else {
                    self.try_reserve_impl::<HAE>(s.len())?
                }
            } else {
                cur_len = self.buf.heap_len().as_usize();
                if cap - cur_len >= s.len() {
                    self.buf.heap_mut_len_mut_p()
                } else {
                    self.try_reserve_impl::<HAE>(s.len())?
                }
            };
            unsafe { ptr::copy_nonoverlapping(s.as_ptr(), p.add(cur_len), s.len()) };
            len.add_assign(s.len());
            Ok(())
        }
    }
}

#[inline]
unsafe fn clone_from_slice_unchecked<T, L>(s: &[T], len: &mut L, mut p: *mut T)
where
    T: Clone,
    L: LengthType,
{
    // Clone every element in source and append to the back of `self`.
    // Update `len` one-by-one, as `clone()` may panic and `self.drop()` may be implicitly
    // invoked. This way we drop only successfully written slots.
    for e in s {
        p.write(e.clone());
        p = p.add(1);
        len.add_assign(1);
    }
}

pub mod errors;
use errors::*;

mod drain;
pub use drain::*;

mod macros;
mod traits;

#[cfg(all(test, feature = "std"))]
mod test_smallvec;