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`

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.
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),
        );

        (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 {
        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> {
        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,

    /// An unspecified allocation error occurred.
    ///
    /// 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(())
    }
}