bump_stack/

lib.rs

#![doc = include_str!("../README.md")]
#![cfg_attr(not(test), no_std)]

mod chunk;
mod iter;
mod util;

extern crate alloc;

use crate::chunk::*;
use crate::util::TypeProps;
use alloc::alloc::{Layout, alloc, dealloc, handle_alloc_error};
use alloc::vec::Vec;
use core::cell::Cell;
use core::iter::DoubleEndedIterator;
use core::marker::PhantomData;
use core::ptr::{self, NonNull};

pub struct Stack<T> {
    /// The current chunk we are bump allocating within.
    ///
    /// Its `next` link can point to the dead chunk, or to the cached chunk.
    ///
    /// Its `prev` link can point to the dead chunk or to the earlier allocated
    /// chunk.
    current_footer: Cell<NonNull<ChunkFooter>>,

    /// The first chunk we allocated, or the dead chunk if we haven't allocated
    /// anything yet.
    first_footer: Cell<NonNull<ChunkFooter>>,

    /// The capacity of the stack in elements.
    capacity: Cell<usize>,

    /// The number of elements currently in the stack.
    length: Cell<usize>,

    phantom: PhantomData<Cell<T>>, // invariant over `T`
}

// Public API
impl<T> Stack<T> {
    /// Constructs a new, empty `Stack<T>`.
    ///
    /// The stack will not allocate until elements are pushed onto it.
    ///
    /// # Examples
    ///
    /// ```
    /// use bump_stack::Stack;
    ///
    /// let mut stack: Stack<i32> = Stack::new();
    /// ```
    pub const fn new() -> Self {
        Self {
            current_footer: Cell::new(DEAD_CHUNK.footer()),
            first_footer: Cell::new(DEAD_CHUNK.footer()),
            capacity: Cell::new(0),
            length: Cell::new(0),
            phantom: PhantomData,
        }
    }

    /// Constructs a new, empty `Stack<T>` with at least the specified capacity.
    ///
    /// The stack will be able to hold at least `capacity` elements without new
    /// allocations. This method is allowed to allocate for more elements than
    /// `capacity`. If `capacity` is zero, the stack will not allocate.
    ///
    /// If it is important to know the exact allocated capacity of a `Stack`,
    /// always use the [`capacity`] method after construction.
    ///
    /// For `Stack<T>` where `T` is a zero-sized type, there will be no
    /// allocation and the capacity will always be `usize::MAX`.
    ///
    /// [`capacity`]: Stack::capacity
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::with_capacity(10);
    ///
    /// // The stack contains no items, even though it has capacity for more
    /// assert_eq!(stk.len(), 0);
    /// assert!(stk.capacity() >= 10);
    ///
    /// // These are all done without additional allocations...
    /// for i in 0..10 {
    ///     stk.push(i);
    /// }
    /// assert_eq!(stk.len(), 10);
    /// assert!(stk.capacity() >= 10);
    ///
    /// // ...but this may make the stack allocate a new chunk
    /// stk.push(11);
    /// assert_eq!(stk.len(), 11);
    /// assert!(stk.capacity() >= 11);
    ///
    /// // A stack of a zero-sized type will always over-allocate, since no
    /// // allocation is necessary
    /// let stk_units = Stack::<()>::with_capacity(10);
    /// assert_eq!(stk_units.capacity(), usize::MAX);
    /// ```
    pub fn with_capacity(capacity: usize) -> Self {
        let stack = Self::new();
        if const { !T::IS_ZST } && capacity != 0 {
            let chunk_size = Chunk::<T>::chunk_size_for(capacity);
            let footer = unsafe { stack.alloc_chunk(chunk_size) };
            stack.current_footer.set(footer);
            stack.first_footer.set(footer);
        }
        stack
    }

    /// Returns the total number of elements the stack can hold without
    /// additional allocations.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::with_capacity(10);
    /// stk.push(42);
    /// assert!(stk.capacity() >= 10);
    /// ```
    ///
    /// A stack with zero-sized elements will always have a capacity of
    /// `usize::MAX`:
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// #[derive(Clone)]
    /// struct ZeroSized;
    ///
    /// assert_eq!(std::mem::size_of::<ZeroSized>(), 0);
    /// let stk = Stack::<ZeroSized>::with_capacity(0);
    /// assert_eq!(stk.capacity(), usize::MAX);
    /// ```
    #[inline]
    pub const fn capacity(&self) -> usize {
        if const { T::IS_ZST } {
            usize::MAX
        } else {
            self.capacity.get()
        }
    }

    /// Returns the number of elements in the stack.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let stk = Stack::from([1, 2, 3]);
    /// assert_eq!(stk.len(), 3);
    /// ```
    #[inline]
    pub const fn len(&self) -> usize {
        self.length.get()
    }

    /// Returns `true` if the stack contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut s = Stack::new();
    /// assert!(s.is_empty());
    ///
    /// s.push(1);
    /// assert!(!s.is_empty());
    /// ```
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns a reference to the first element of the stack, or `None` if it
    /// is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut s = Stack::new();
    /// assert_eq!(None, s.first());
    ///
    /// s.push(42);
    /// assert_eq!(Some(&42), s.first());
    /// ```
    #[inline]
    #[must_use]
    pub fn first(&self) -> Option<&T> {
        if !self.is_empty() {
            unsafe {
                let first_chunk = wrap::<T>(self.first_footer.get());
                Some(first_chunk.first_unchecked().as_ref())
            }
        } else {
            None
        }
    }

    /// Returns a mutable reference to the first element of the slice, or `None`
    /// if it is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut s = Stack::new();
    /// assert_eq!(None, s.first_mut());
    ///
    /// s.push(1);
    /// if let Some(first) = s.first_mut() {
    ///     *first = 5;
    /// }
    /// assert_eq!(s.first(), Some(&5));
    /// ```
    #[inline]
    #[must_use]
    pub fn first_mut(&mut self) -> Option<&mut T> {
        if !self.is_empty() {
            unsafe {
                let first_chunk = wrap::<T>(self.first_footer.get());
                Some(first_chunk.first_unchecked().as_mut())
            }
        } else {
            None
        }
    }

    /// Returns the reference to last element of the stack, or `None` if it is
    /// empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::new();
    /// assert_eq!(None, stk.last());
    ///
    /// stk.push(1);
    /// assert_eq!(Some(&1), stk.last());
    /// ```
    #[inline]
    #[must_use]
    pub fn last(&self) -> Option<&T> {
        if !self.is_empty() {
            unsafe {
                let mut chunk = wrap::<T>(self.current_footer.get());
                if chunk.is_empty() {
                    chunk = wrap::<T>(chunk.prev());
                }
                Some(chunk.last_unchecked().as_ref())
            }
        } else {
            None
        }
    }
    /// Returns a mutable reference to the last item in the stack, or `None` if
    /// it is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::new();
    /// assert_eq!(None, stk.last_mut());
    ///
    /// stk.push(5);
    /// assert_eq!(Some(&mut 5), stk.last_mut());
    ///
    /// if let Some(last) = stk.last_mut() {
    ///     *last = 10;
    /// }
    /// assert_eq!(Some(&mut 10), stk.last_mut());
    /// ```
    #[inline]
    #[must_use]
    pub fn last_mut(&mut self) -> Option<&mut T> {
        if !self.is_empty() {
            unsafe {
                let mut chunk = wrap::<T>(self.current_footer.get());
                if chunk.is_empty() {
                    chunk = wrap::<T>(chunk.prev());
                }
                Some(chunk.last_unchecked().as_mut())
            }
        } else {
            None
        }
    }

    /// Appends an element to the stack returning a reference to it.
    ///
    /// # Panics
    ///
    /// Panics if the global allocator cannot allocate a new chunk of memory.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let stk = Stack::new();
    /// let new_element = stk.push(3);
    ///
    /// assert_eq!(new_element, &3);
    /// assert_eq!(stk, [3]);
    /// ```
    ///
    /// # Time complexity
    ///
    /// Takes amortized *O*(1) time. If the stack's current chunk of memory is
    /// exhausted, it tries to use the cached one if it exists, otherwise it
    /// tries to allocate a new chunk.
    ///
    /// If the new chunk of memory is too big, it tries to divide the capacity
    /// by two and allocate it again until it reaches the minimum capacity. If
    /// it does, it panics.
    #[inline]
    pub fn push(&self, value: T) -> &T {
        self.push_with(|| value)
    }

    /// Appends an element to the stack, returning a mutable reference to it.
    ///
    /// # Panics
    ///
    /// Panics if there is no way to allocate memory for a new capacity.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::from([1, 2]);
    /// let last = stk.push_mut(3);
    /// assert_eq!(*last, 3);
    /// assert_eq!(stk, [3, 2, 1]);
    ///
    /// let last = stk.push_mut(3);
    /// *last += 1;
    /// assert_eq!(stk, [4, 3, 2, 1]);
    /// ```
    ///
    /// # Time complexity
    ///
    /// Takes amortized *O*(1) time. If the stack's current chunk of memory is
    /// exhausted, it tries to use the cached one if it exists, otherwise it
    /// tries to allocate a new chunk.
    ///
    /// If the new chunk of memory is too big, it tries to divide the capacity
    /// by two and allocate it again until it reaches the minimum capacity. If
    /// it does, it panics.
    #[inline]
    #[must_use = "if you don't need the returned value, consider using `push` instead"]
    pub fn push_mut(&mut self, value: T) -> &mut T {
        self.push_mut_with(|| value)
    }

    /// Pre-allocate space for an element in this stack, initializes it using
    /// the closure, and returns a reference to the new element.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let stk = Stack::new();
    /// let new_element = stk.push_with(|| 3);
    ///
    /// assert_eq!(new_element, &3);
    /// assert_eq!(stk, [3]);
    /// ```
    ///
    /// # Time complexity
    ///
    /// Takes amortized *O*(1) time. If the stack's current chunk of memory is
    /// exhausted, it tries to use the cached one if it exists, otherwise it
    /// tries to allocate a new chunk.
    ///
    /// If the new chunk of memory is too big, it tries to divide the capacity
    /// by two and allocate it again until it reaches the minimum capacity. If
    /// it does, it panics.
    #[inline(always)]
    pub fn push_with<F>(&self, f: F) -> &T
    where
        F: FnOnce() -> T,
    {
        if const { T::IS_ZST } {
            self.length.update(|len| len + 1);
            unsafe { util::zst_ptr::<T>().as_ref() }
        } else {
            unsafe {
                let p = self.alloc_element();
                util::write_with(p.as_ptr(), f);
                self.length.update(|len| len + 1);
                p.as_ref()
            }
        }
    }

    /// Pre-allocate space for an element in this stack, initializes it using
    /// the closure, and returns a mutable reference to the new element.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::from([1, 2]);
    /// let last = stk.push_mut(3);
    /// assert_eq!(*last, 3);
    /// assert_eq!(stk, [3, 2, 1]);
    ///
    /// let last = stk.push_mut(3);
    /// *last += 1;
    /// assert_eq!(stk, [4, 3, 2, 1]);
    /// ```
    ///
    /// # Time complexity
    ///
    /// Takes amortized *O*(1) time. If the stack's current chunk of memory is
    /// exhausted, it tries to use the cached one if it exists, otherwise it
    /// tries to allocate a new chunk.
    ///
    /// If the new chunk of memory is too big, it tries to divide the capacity
    /// by two and allocate it again until it reaches the minimum capacity. If
    /// it does, it panics.
    #[inline(always)]
    pub fn push_mut_with<F>(&mut self, f: F) -> &mut T
    where
        F: FnOnce() -> T,
    {
        if const { T::IS_ZST } {
            self.length.update(|len| len + 1);
            unsafe { util::zst_ptr::<T>().as_mut() }
        } else {
            unsafe {
                let mut p = self.alloc_element();
                util::write_with(p.as_ptr(), f);
                self.length.update(|len| len + 1);
                p.as_mut()
            }
        }
    }

    /// Removes the last element from a vector and returns it, or [`None`] if it
    /// is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::from([1, 2, 3]);
    /// assert_eq!(stk.pop(), Some(3));
    /// assert_eq!(stk, [2, 1]);
    /// ```
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        if const { T::IS_ZST } {
            if self.length.get() > 0 {
                self.length.update(|len| len - 1);
                unsafe { Some(ptr::read(util::zst_ptr::<T>().as_ptr())) }
            } else {
                None
            }
        } else {
            // `T` is not ZST
            if let Some(element_ptr) = unsafe { self.dealloc_element() } {
                self.length.update(|len| len - 1);
                Some(unsafe { ptr::read(element_ptr.as_ptr()) })
            } else {
                None
            }
        }
    }

    /// Removes and returns the last element from a stack if the predicate
    /// returns `true`, or [`None`] if the predicate returns false or the stack
    /// is empty (the predicate will not be called in that case).
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::from([1, 2, 3, 4]);
    /// let pred = |x: &mut i32| *x % 2 == 0;
    ///
    /// assert_eq!(stk.pop_if(pred), Some(4));
    /// assert_eq!(stk, [3, 2, 1]);
    /// assert_eq!(stk.pop_if(pred), None);
    /// ```
    pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
        let last = self.last_mut()?;
        if predicate(last) { self.pop() } else { None }
    }

    /// Clears the stack, dropping all elements.
    ///
    /// This method leaves the biggest chunk of memory for future allocations.
    ///
    /// The order of dropping elements is not defined.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::from([1, 2, 3]);
    ///
    /// stk.clear();
    ///
    /// assert!(stk.is_empty());
    /// assert!(stk.capacity() > 0);
    /// ```
    pub fn clear(&mut self) {
        let mut first_footer = self.first_footer.get();
        let mut first_chunk = unsafe { wrap::<T>(first_footer) };
        if first_chunk.is_dead() {
            return;
        }
        loop {
            let next_footer = first_chunk.next();
            let next_chunk = unsafe { wrap(next_footer) };

            if next_chunk.is_dead() {
                break;
            }

            unsafe { self.dealloc_chunk(first_footer) };

            first_footer = next_footer;
            first_chunk = next_chunk;
        }
        let dropped = unsafe { wrap::<T>(first_footer).drop() };
        debug_assert!(self.len() >= dropped);
        self.length.update(|length| length - dropped);

        first_chunk.set_prev(DEAD_CHUNK.footer());
        self.first_footer.set(first_footer);
        self.current_footer.set(first_footer);
    }

    /// Returns `true` if the stack contains an element with the given value.
    ///
    /// This operation is *O*(*n*).
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let stk = Stack::from([3, 8, 12]);
    /// assert!(stk.contains(&8));
    /// assert!(!stk.contains(&20));
    /// ```
    #[must_use]
    pub fn contains(&self, value: &T) -> bool
    where
        T: PartialEq,
    {
        self.iter().any(|elem| elem == value)
    }

    /// Copies `self` into a `Vec`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let s = Stack::from([10, 40, 30]);
    /// let v = s.to_vec();
    /// assert_eq!(v, &[30, 40, 10]);
    /// ```
    #[inline]
    pub fn to_vec(&self) -> Vec<T>
    where
        T: Clone,
    {
        let mut vec = Vec::with_capacity(self.len());
        for chunk in self.chunks() {
            vec.extend_from_slice(chunk);
        }
        vec
    }

    /// Returns an iterator over the stack.
    ///
    /// The iterator yields all items' references in inverted order of their
    /// insertion, corresponding to a LIFO structure behavior.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let stk = Stack::from([1, 2, 4]);
    /// let mut iterator = stk.iter();
    ///
    /// assert_eq!(iterator.next(), Some(&4));
    /// assert_eq!(iterator.next(), Some(&2));
    /// assert_eq!(iterator.next(), Some(&1));
    /// assert_eq!(iterator.next(), None);
    /// ```
    ///
    /// Since `Stack` allows to push new elements using immutable reference to
    /// itself, you can push during iteration. But iteration is running over
    /// elements existing at the moment of the iterator creating. It guarantees
    /// that you won't get infinite loop.
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let stk = Stack::from([1, 2, 4]);
    ///
    /// for elem in stk.iter() {
    ///     stk.push(*elem);
    /// }
    /// assert_eq!(stk.len(), 6);
    /// assert_eq!(stk, [1, 2, 4, 4, 2, 1]);
    /// ```
    #[inline]
    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> {
        crate::iter::Iter::new(self)
    }

    /// Returns a mutable iterator over the stack.
    ///
    /// The iterator yields all items' references in inverted order of their
    /// insertion, corresponding to a LIFO structure behavior.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::from([1, 2, 4]);
    ///
    /// for elem in stk.iter_mut() {
    ///     *elem *= 2;
    /// }
    ///
    /// assert_eq!(&stk, &[8, 4, 2]);
    /// ```
    #[inline]
    pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T> {
        crate::iter::IterMut::new(self)
    }

    /// Returns an iterator over slices corresponding to the stack's memory
    /// chunks.
    ///
    /// The iterator yields all items' references in inverted order of their
    /// insertion, corresponding to a LIFO structure behavior.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let stk = Stack::from([0, 1, 2]);
    /// assert_eq!(stk.chunks().collect::<Vec<_>>(), [&[2, 1, 0]]);
    ///
    /// // fill up the first chunk
    /// for i in 3..stk.capacity() {
    ///     stk.push(i);
    /// }
    /// assert_eq!(stk.chunks().count(), 1);
    ///
    /// // create a new chunk
    /// stk.push(42);
    /// assert_eq!(stk.chunks().count(), 2);
    /// ```
    #[inline]
    pub fn chunks(&self) -> impl DoubleEndedIterator<Item = &[T]> {
        crate::iter::ChunkIter::new(self)
    }

    /// Returns an iterator over mutable slices corresponding to the stack's
    /// memory chunks.
    ///
    /// The iterator yields all items' references in inverted order of their
    /// insertion, corresponding to a LIFO structure behavior.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bump_stack::Stack;
    /// let mut stk = Stack::from([0, 1, 2]);
    ///
    /// let chunk = stk.chunks_mut().next().unwrap();
    /// assert_eq!(chunk, [2, 1, 0]);
    /// chunk[0] = 42;
    /// assert_eq!(chunk, [42, 1, 0]);
    /// ```
    #[inline]
    pub fn chunks_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut [T]> {
        crate::iter::ChunkIterMut::new(self)
    }
}

impl<T> core::default::Default for Stack<T> {
    /// Creates an empty `Stack<T>`.
    ///
    /// The stack will not allocate until elements are pushed onto it.
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<T> core::clone::Clone for Stack<T>
where
    T: Clone,
{
    fn clone(&self) -> Self {
        Stack::from_iter(self.iter().cloned())
    }
}

impl<T, const N: usize> core::convert::From<&[T; N]> for Stack<T>
where
    T: Clone,
{
    /// Creates a `Stack<T>` with a chunk big enough to contain N items and
    /// fills it by cloning `slice`'s items.
    fn from(slice: &[T; N]) -> Self {
        let stk = Stack::with_capacity(N);
        for item in slice {
            stk.push_with(|| item.clone());
        }
        stk
    }
}

impl<T, const N: usize> core::convert::From<&mut [T; N]> for Stack<T>
where
    T: Clone,
{
    /// Creates a `Stack<T>` with a chunk big enough to contain N items and
    /// fills it by cloning `slice`'s items.
    #[inline]
    fn from(slice: &mut [T; N]) -> Self {
        core::convert::From::<&[T; N]>::from(slice)
    }
}

impl<T, const N: usize> core::convert::From<[T; N]> for Stack<T>
where
    T: Clone,
{
    /// Creates a `Stack<T>` with a chunk big enough to contain N items and
    /// fills it by cloning `array`'s items.
    #[inline]
    fn from(array: [T; N]) -> Self {
        core::convert::From::<&[T; N]>::from(&array)
    }
}

impl<T> core::convert::From<&[T]> for Stack<T>
where
    T: Clone,
{
    /// Creates a `Stack<T>` with a chunk big enough to contain N items and
    /// fills it by cloning `slice`'s items.
    fn from(slice: &[T]) -> Self {
        let stk = Stack::with_capacity(slice.len());
        for item in slice {
            stk.push_with(|| item.clone());
        }
        stk
    }
}

impl<T> core::convert::From<&mut [T]> for Stack<T>
where
    T: Clone,
{
    /// Creates a `Stack<T>` with a chunk big enough to contain N items and
    /// fills it by cloning `slice`'s items.
    #[inline]
    fn from(slice: &mut [T]) -> Self {
        core::convert::From::<&[T]>::from(slice)
    }
}

impl<T> core::ops::Drop for Stack<T> {
    #[inline]
    fn drop(&mut self) {
        self.clear();
        unsafe {
            let current_chunk = wrap::<T>(self.current_footer.get());
            if !current_chunk.is_dead() {
                debug_assert!(wrap::<T>(current_chunk.prev()).is_dead());
                debug_assert!(wrap::<T>(current_chunk.next()).is_dead());
                self.dealloc_chunk(self.current_footer.get());
            }
        }
    }
}

impl<T> core::iter::FromIterator<T> for Stack<T>
where
    T: Clone,
{
    #[inline]
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let iter = iter.into_iter();
        // try to preallocate a chunk big enough to contain iter's items
        let stk = Stack::with_capacity(iter.size_hint().0);
        for item in iter {
            stk.push_with(|| item);
        }
        stk
    }
}

impl<'a, T> core::iter::IntoIterator for &'a Stack<T> {
    type Item = &'a T;
    type IntoIter = crate::iter::Iter<'a, T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        crate::iter::Iter::new(self)
    }
}

impl<'a, T> core::iter::IntoIterator for &'a mut Stack<T> {
    type Item = &'a mut T;
    type IntoIter = crate::iter::IterMut<'a, T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        crate::iter::IterMut::new(self)
    }
}

impl<T> core::iter::IntoIterator for Stack<T> {
    type Item = T;
    type IntoIter = crate::iter::IntoIter<T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        crate::iter::IntoIter::new(self)
    }
}

impl<T, U> core::cmp::PartialEq<[U]> for Stack<T>
where
    T: core::cmp::PartialEq<U>,
{
    fn eq(&self, other: &[U]) -> bool {
        self.len() == other.len() && self.iter().zip(other.iter()).all(|(a, b)| a == b)
    }
}

impl<T, U> core::cmp::PartialEq<&[U]> for Stack<T>
where
    T: core::cmp::PartialEq<U>,
{
    #[inline]
    fn eq(&self, other: &&[U]) -> bool {
        core::cmp::PartialEq::<[U]>::eq(self, other)
    }
}

impl<T, U> core::cmp::PartialEq<&mut [U]> for Stack<T>
where
    T: core::cmp::PartialEq<U>,
{
    #[inline]
    fn eq(&self, other: &&mut [U]) -> bool {
        core::cmp::PartialEq::<[U]>::eq(self, other)
    }
}

impl<T, U, const N: usize> core::cmp::PartialEq<[U; N]> for Stack<T>
where
    T: core::cmp::PartialEq<U>,
{
    fn eq(&self, other: &[U; N]) -> bool {
        self.len() == N && self.iter().zip(other.iter()).all(|(a, b)| a == b)
    }
}

impl<T, U, const N: usize> core::cmp::PartialEq<&[U; N]> for Stack<T>
where
    T: core::cmp::PartialEq<U>,
{
    #[inline]
    fn eq(&self, other: &&[U; N]) -> bool {
        core::cmp::PartialEq::<[U; N]>::eq(self, other)
    }
}

impl<T, U, const N: usize> core::cmp::PartialEq<&mut [U; N]> for Stack<T>
where
    T: core::cmp::PartialEq<U>,
{
    #[inline]
    fn eq(&self, other: &&mut [U; N]) -> bool {
        core::cmp::PartialEq::<[U; N]>::eq(self, other)
    }
}

impl<T, U, const N: usize> core::cmp::PartialEq<Stack<U>> for [T; N]
where
    T: core::cmp::PartialEq<U>,
{
    fn eq(&self, other: &Stack<U>) -> bool {
        self.len() == other.len() && self.iter().zip(other.iter()).all(|(a, b)| a == b)
    }
}

impl<T, U, const N: usize> core::cmp::PartialEq<Stack<U>> for &[T; N]
where
    T: core::cmp::PartialEq<U>,
{
    fn eq(&self, other: &Stack<U>) -> bool {
        *self == other
    }
}

impl<T, U, const N: usize> core::cmp::PartialEq<Stack<U>> for &mut [T; N]
where
    T: core::cmp::PartialEq<U>,
{
    fn eq(&self, other: &Stack<U>) -> bool {
        *self == other
    }
}

impl<T> core::fmt::Debug for Stack<T>
where
    T: core::fmt::Debug,
{
    #[inline]
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

unsafe impl<T> Send for Stack<T> where T: Send {}

/// Maximum typical overhead per allocation imposed by allocators.
const ALLOC_OVERHEAD: usize = 16;

// Private API
impl<T> Stack<T> {
    /// Allocates memory for a new element and return a pointer to it.
    ///
    /// # Safety
    ///
    /// The caller must ensure that the method is called only for non zero-sized
    /// types.
    #[inline(always)]
    unsafe fn alloc_element(&self) -> NonNull<T> {
        debug_assert!(!T::IS_ZST);

        let curr_chunk = unsafe { wrap::<T>(self.current_footer.get()) };
        if let Some(ptr) = curr_chunk.alloc_element() {
            ptr
        } else {
            unsafe { self.alloc_element_slow() }
        }
    }

    // Should be run only if the current chunk is full
    unsafe fn alloc_element_slow(&self) -> NonNull<T> {
        debug_assert!(!T::IS_ZST);
        unsafe {
            let current_chunk = wrap::<T>(self.current_footer.get());
            let next_footer = current_chunk.next();
            let next_chunk = wrap::<T>(next_footer);
            let prev_chunk = wrap::<T>(current_chunk.prev());

            debug_assert!(current_chunk.is_full());

            if current_chunk.is_dead() {
                // this is initial state without allocated chunks at all
                debug_assert!(current_chunk.is_dead());
                debug_assert!(prev_chunk.is_dead());
                debug_assert!(next_chunk.is_dead());

                let new_footer_ptr = self.alloc_chunk(Chunk::<T>::CHUNK_FIRST_SIZE);
                self.current_footer.set(new_footer_ptr);
                self.first_footer.set(new_footer_ptr);
            } else {
                // at least the current chunk is not dead
                if next_chunk.is_dead() {
                    // the current chunk is single, so create a new one, and
                    // make it the current chunk.
                    let current_chunk_size = current_chunk.size();
                    let new_chunk_size = if current_chunk_size == Chunk::<T>::CHUNK_MAX_SIZE {
                        Chunk::<T>::CHUNK_MAX_SIZE
                    } else {
                        debug_assert!(current_chunk_size < Chunk::<T>::CHUNK_MAX_SIZE);
                        ((current_chunk_size + ALLOC_OVERHEAD) << 1) - ALLOC_OVERHEAD
                    };

                    debug_assert!((new_chunk_size + ALLOC_OVERHEAD).is_power_of_two());

                    let new_footer = self.alloc_chunk(new_chunk_size);
                    let new_chunk = wrap::<T>(new_footer);

                    current_chunk.set_next(new_footer);
                    new_chunk.set_prev(self.current_footer.get());

                    self.current_footer.set(new_footer);
                } else {
                    // there is a next empty chunk, so make it the current chunk
                    debug_assert!(next_chunk.is_empty());
                    self.current_footer.set(next_footer);
                }
            }

            let curr_chunk = wrap::<T>(self.current_footer.get());
            curr_chunk.alloc_element().unwrap_unchecked()
        }
    }

    /// Creates a new chunk with the given size. If it can't allocate a chunk
    /// with the given size, it tries to allocate a chunk with a two times
    /// smaller size. Otherwise, it panics.
    ///
    /// Properties `data`, `ptr`, and `layout` are initialized to the values
    /// of the newly allocated chunk.
    ///
    /// Properties `prev` and `next` point to the `DEAD_CHUNK`, so you should
    /// reinitialize them to needed values, if there exist another chunks in the
    /// list.
    unsafe fn alloc_chunk(&self, chunk_size: usize) -> NonNull<ChunkFooter> {
        debug_assert!(chunk_size <= Chunk::<T>::CHUNK_MAX_SIZE);

        let mut chunk_size = chunk_size;
        let chunk_align = Chunk::<T>::CHUNK_ALIGN;

        let (chunk_ptr, chunk_layout) = loop {
            // checks for `Layout::from_size_align_unchecked`
            debug_assert!(chunk_align != 0);
            debug_assert!(chunk_align.is_power_of_two());
            debug_assert!((chunk_size + ALLOC_OVERHEAD).is_power_of_two());
            debug_assert!(chunk_size <= isize::MAX as usize);

            let chunk_layout =
                unsafe { Layout::from_size_align_unchecked(chunk_size, chunk_align) };

            let chunk_ptr = unsafe { alloc(chunk_layout) };
            if !chunk_ptr.is_null() {
                assert!(util::ptr_is_aligned_to(chunk_ptr, Chunk::<T>::CHUNK_ALIGN));
                break (chunk_ptr, chunk_layout);
            }

            // if couldn't get a new chunk, try to shrink the chunk size by half
            chunk_size = ((chunk_size + ALLOC_OVERHEAD) >> 1) - ALLOC_OVERHEAD;
            if chunk_size < Chunk::<T>::CHUNK_MIN_SIZE {
                handle_alloc_error(chunk_layout);
            }
        };

        let chunk_ptr = unsafe { NonNull::new_unchecked(chunk_ptr) };
        let (footer_ptr, chunk_capacity) = unsafe { Chunk::<T>::init(chunk_ptr, chunk_layout) };

        self.capacity.update(|cap| cap + chunk_capacity);

        footer_ptr
    }

    #[inline(always)]
    unsafe fn dealloc_element(&mut self) -> Option<NonNull<T>> {
        debug_assert!(!T::IS_ZST);

        unsafe {
            let curr_chunk = wrap::<T>(self.current_footer.get());
            if let Some(ptr) = curr_chunk.dealloc_element() {
                Some(ptr)
            } else {
                self.dealloc_element_slow()
            }
        }
    }

    unsafe fn dealloc_element_slow(&mut self) -> Option<NonNull<T>> {
        unsafe {
            let current_footer = self.current_footer.get();
            let current_chunk = wrap::<T>(current_footer);

            let next_footer = current_chunk.next();
            let next_chunk = wrap::<T>(next_footer);

            let prev_footer = current_chunk.prev();
            let prev_chunk = wrap::<T>(prev_footer);

            if current_chunk.is_dead() {
                debug_assert!(next_chunk.is_dead());
                debug_assert!(prev_chunk.is_dead());
                return None;
            }

            debug_assert!(current_chunk.is_empty());
            debug_assert!(next_chunk.is_empty());

            if !next_chunk.is_dead() {
                if current_chunk.size() < next_chunk.size() {
                    debug_assert!(wrap::<T>(next_chunk.next()).is_dead());

                    next_chunk.set_prev(prev_footer);
                    self.current_footer.set(next_footer);

                    self.dealloc_chunk(current_footer);
                } else {
                    self.dealloc_chunk(next_footer);
                }
                let current_chunk = wrap::<T>(self.current_footer.get());
                current_chunk.set_next(DEAD_CHUNK.footer());
            }

            if prev_chunk.is_dead() {
                self.first_footer.set(self.current_footer.get());
                None
            } else {
                // check if prev_footer is full
                debug_assert!(prev_chunk.is_full());

                prev_chunk.set_next(self.current_footer.get());
                self.current_footer.set(prev_footer);

                let curr_chunk = wrap::<T>(self.current_footer.get());
                curr_chunk.dealloc_element()
            }
        }
    }

    unsafe fn dealloc_chunk(&mut self, footer: NonNull<ChunkFooter>) {
        unsafe {
            let chunk = wrap::<T>(footer);
            let dropped = chunk.drop();
            debug_assert!(self.len() >= dropped);
            self.length.update(|length| length - dropped);

            let chunk_capacity = chunk.capacity();
            debug_assert!(chunk_capacity <= self.capacity());
            self.capacity.update(|cap| cap - chunk_capacity);
            debug_assert!(self.len() <= self.capacity());
            dealloc(chunk.start().cast().as_ptr(), chunk.layout());
        }
    }
}

/// Unit tests.
#[cfg(test)]
mod utest;