path: root/crates/core/src/hive/mod.rs

//! An implementation of a bucket array type following the approach used in
//! the [C++26 `hive`](https://eel.is/c++draft/hive) structure.

//TODO: traits to implement for `Hive`:
//      - Ord - Eq - Clone - Debug - Deref<Target=[T]> (?) - AsRef - Borrow
//      - AsMut - Extend - From [array, slice, vec, etc...] - FromIterator
//      - Hash - IntoIterator - Index - IndexMut
//      - PartialEq [array, slice, vec, etc...] - PartialOrd - Write
//TODO: define zero-sized-type handling in `Hive`
//TODO: define situations where we panic
//TODO: consider factoring out code that does not care about the type
//      parameters into a separate struct to reduce the amount of code
//      generated, akin to what the standard library does with `RawVec` and
//      `RawVecInner`
//TODO: try_reserve_exact, reserve_exact

use alloc::alloc::{Allocator, Global, Layout};
use core::{cmp, mem, ptr::NonNull};

#[cfg(feature = "core-fmt")]
use core::fmt;

#[cfg(feature = "core-error")]
use core::error;

pub mod group;
pub mod skipfield;

/// An implementation of a bucket array using a skipfield.
#[cfg_attr(feature = "core-fmt", derive(Debug))]
pub struct Hive<T, Sk = u16, A = Global>
where
    Sk: skipfield::SkipfieldType,
    A: Allocator,
{
    /// Head of the doubly linked list of groups with erased elements
    head_with_erasures: Option<NonNull<group::Group<T, Sk>>>,

    /// Head of the singly linked list of unused groups
    unused_head: Option<NonNull<group::Group<T, Sk>>>,

    /// Number of occupied element spaces
    size: usize,

    /// Total number of element spaces available
    capacity: usize,

    /// Minimum capacity of new [`Group`]s
    min_block_capacity: Sk,

    /// Maximum capacity of new [`Group`]s
    max_block_capacity: Sk,

    /// The allocator used by this [`Hive`].
    alloc: A,
}

impl<T, Sk> Hive<T, Sk, Global>
where
    Sk: skipfield::SkipfieldType,
{
    /// Constructs a new, empty `Hive<T, Sk>`.
    ///
    /// No allocations are performed until elements are inserted.
    pub fn new() -> Self {
        Self::new_in(Global)
    }

    /// Constructs a new, empty `Hive<T, Sk>` with at least the specified
    /// capacity.
    ///
    /// The hive will be able to hold at least `capacity` elements without
    /// reallocating. This method is allowed to allocate for more elements
    /// than `capacity`. If `capacity` is zero, the hive will not
    /// allocate.
    ///
    /// # Panics
    ///
    /// Panics if the allocator reports allocation failure or if the capacity
    /// exceeds `isize::MAX` bytes.
    #[cfg(feature = "core-fmt")]
    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_in(capacity, Global)
    }

    /// Constructs a new, empty `Hive<T, Sk>` with at least the specified
    /// capacity.
    ///
    /// The hive will be able to hold at least `capacity` elements without
    /// reallocating. This method is allowed to allocate for more elements
    /// than `capacity`. If `capacity` is zero, the hive will not
    /// allocate.
    ///
    /// # Errors
    ///
    /// Returns an error if the allocator reports allocation failure or if the
    /// capacity exceeds `isize::MAX` bytes.
    pub fn try_with_capacity(capacity: usize) -> Result<Self, Error> {
        Self::try_with_capacity_in(capacity, Global)
    }
}

impl<T, Sk, A> Hive<T, Sk, A>
where
    Sk: skipfield::SkipfieldType,
    A: Allocator,
{
    /// Function returning the default bounds for individual [`Group`]
    /// capacity
    ///
    /// These are borrowed from [here], as those bounds were determined
    /// according to benchmarking results. However, they have not been
    /// replicated against this implementation of the concept.
    ///
    /// [here]: https://github.com/mattreecebentley/plf_hive/blob/main/plf_hive.h#L293-L307
    fn default_group_capacity_bounds() -> (Sk, Sk)
    where
        Sk: skipfield::SkipfieldType,
    {
        let max_capacity = cmp::min(
            cmp::min(Sk::MAXIMUM, Sk::from_usize(8192)),
            Sk::from_isize(isize::MAX),
        );
        let adaptive_size = (mem::size_of::<Self>()
            + mem::size_of::<group::Group<T, Sk>>() * 2)
            / group::Group::<T, Sk>::ELEMENT_ALLOCATION_SIZE;
        let min_capacity = cmp::max(
            Sk::from_usize(8usize),
            cmp::min(Sk::from_usize(adaptive_size), max_capacity),
        );

        //NOTE: anything that calls `panic` indirectly or does anything that
        // touches standard output      requires core::fmt :skull:
        #[cfg(feature = "core-fmt")]
        debug_assert!(
            max_capacity >= min_capacity,
            "maximum capacity bound is greater than or equal to the minimum capacity bound"
        );

        (min_capacity, max_capacity)
    }

    /// Constructs a new, empty `Hive<T, Sk, A>`.
    ///
    /// No allocations are performed until elements are inserted.
    pub fn new_in(alloc: A) -> Self {
        let (min_block_capacity, max_block_capacity) =
            Self::default_group_capacity_bounds();
        Self {
            head_with_erasures: None,
            unused_head: None,
            size: 0,
            capacity: 0,
            min_block_capacity,
            max_block_capacity,
            alloc,
        }
    }

    /// Constructs a new, empty `Hive<T, Sk, A>` with at least the specified
    /// capacity.
    ///
    /// The hive will be able to hold at least `capacity` elements without
    /// reallocating. This method is allowed to allocate for more elements
    /// than `capacity`. If `capacity` is zero, the hive will not
    /// allocate.
    ///
    /// # Panics
    ///
    /// Panics if the allocator reports allocation failure or if the capacity
    /// exceeds `isize::MAX` bytes.
    #[cfg(feature = "core-fmt")]
    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
        //PANIC: this is acceptable as the panic is mentioned above and it is
        //       used to assert an invariant.
        #[allow(clippy::expect_used)]
        Self::try_with_capacity_in(capacity, alloc)
            .expect("allocation should not fail")
    }

    /// Constructs a new, empty `Hive<T, Sk, A>` with at least the specified
    /// capacity.
    ///
    /// The hive will be able to hold at least `capacity` elements without
    /// reallocating. This method is allowed to allocate for more elements
    /// than `capacity`. If `capacity` is zero, the hive will not
    /// allocate.
    ///
    /// # Errors
    ///
    /// Returns an error if the allocator reports allocation failure or if the
    /// capacity exceeds `isize::MAX` bytes.
    pub fn try_with_capacity_in(
        capacity: usize,
        alloc: A,
    ) -> Result<Self, Error> {
        let mut hive = Self::new_in(alloc);
        hive.try_reserve(capacity)?;
        Ok(hive)
    }

    /// Reserves capacity for at least `additional` more elements to be
    /// inserted in the given `Hive<T, Sk, A>`.
    ///
    /// The collection may reserve more space to avoid future allocations.
    /// After calling `reserve`, the capacity will be greater than or equal to
    /// `self.len() + additional`. Does nothing if the capacity is already
    /// sufficient.
    ///
    /// # Panics
    ///
    /// Panics if the allocator reports allocation failure or if the new
    /// capacity exceeds `isize::MAX` bytes.
    #[cfg(feature = "core-fmt")]
    pub fn reserve(&mut self, additional: usize) {
        todo!()
    }

    /// Reserves capacity for at least `additional` more elements to be
    /// inserted in the given `Hive<T, Sk, A>`.
    ///
    /// The collection may reserve more space to avoid future allocations.
    /// After calling `reserve`, the capacity will be greater than or equal to
    /// `self.len() + additional`. Does nothing if the capacity is already
    /// sufficient.
    ///
    /// # Errors
    ///
    /// Returns an error if the allocator reports allocation failure or if the
    /// new capacity exceeds `isize::MAX` bytes.
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), Error> {
        todo!()
    }

    /// Checks if the container needs to grow to accommodate `additional` more
    /// elements
    #[inline]
    fn needs_to_grow(&self, additional: usize) -> bool {
        additional > self.capacity.wrapping_sub(self.size)
    }

    /// Grow the `Hive<T, Sk, A>` by the given amount, leaving room for more
    /// elements than necessary.
    ///
    /// # Errors
    ///
    /// Returns an error if the allocator reports allocation failure or if the
    /// new capacity exceeds `isize::MAX` bytes.
    fn grow_amortized(&mut self, additional: usize) -> Result<(), Error> {
        #[cfg(feature = "core-fmt")]
        debug_assert!(
            additional > 0,
            "at least space enough for one element will be added"
        );

        if mem::size_of::<T>() == 0 {
            //NOTE: akin to raw_vec in alloc, if we get here with a zero
            //      sized type, since the capacity is definitionally full when
            //      it is holding one, the hive would necessarily
            //      be overfull
            return Err(Error::CapacityOverflow);
        }

        todo!()
    }
}

impl<T, Sk> Default for Hive<T, Sk, Global>
where
    Sk: skipfield::SkipfieldType,
{
    fn default() -> Self {
        Self::new()
    }
}

/// Representation of an error that occurred within [`Hive`].
#[non_exhaustive]
#[derive(Eq, PartialEq)]
#[cfg_attr(feature = "core-fmt", derive(Debug))]
pub enum Error {
    /// Allocation size exceeded `isize::MAX`.
    CapacityOverflow,

    /// Unspecified allocation error.
    ///
    /// The layout used during allocation is provided for troubleshooting
    /// where that is possible. Ideally, future revisions of the
    /// `allocator_api` feature will provide more information in `AllocError`
    /// but for now this is all we can do.
    #[non_exhaustive]
    AllocError {
        /// Layout of the failed allocation.
        layout: Layout,
    },
}

#[cfg(feature = "core-fmt")]
impl fmt::Display for Error {
    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
        fmt.write_str("memory allocation failed")?;
        let reason = match self {
            Error::CapacityOverflow => {
                " because the computed capacity exceeded the hive's maximum"
            }
            Error::AllocError { .. } => {
                " because the memory allocator returned an error"
            }
        };
        fmt.write_str(reason)
    }
}

#[cfg(feature = "core-error")]
impl error::Error for Error {}

/// Guard function ensuring that we don't overflow `isize::MAX`.
///
/// The Rust standard library has a similar function, found [here]. However,
/// that implementation of it ignores the check on platforms with a `usize`
/// wider than 64 bits. This is probably fine, as no platform Rust supports
/// has a virtual address space larger than 8 EiB, but out of caution, we
/// always make the check here.
///
/// [here]: https://github.com/rust-lang/rust/blob/a27f3e3fd1e4d16160f8885b6b06665b5319f56c/library/alloc/src/raw_vec/mod.rs#L802-L817
#[inline]
fn alloc_guard(alloc_size: usize) -> Result<(), Error> {
    //TODO: consider predicating this check over `usize::BITS < 64` as the
    //      rust std does. only do this if it has a measurable performance
    //      impact
    if alloc_size > isize::MAX as usize {
        Err(Error::CapacityOverflow)
    } else {
        Ok(())
    }
}