initial commit

Change-Id: I6a6a69640e8a301a692a5455d1261816280d9cde

4 files changed, 482 insertions, 0 deletions

diff --git a/crates/core/src/hive/group.rs b/crates/core/src/hive/group.rs
new file mode 100644
index 0000000..32d070e
--- /dev/null
+++ b/crates/core/src/hive/group.rs
@@ -0,0 +1,104 @@
+//! An implementation of the individual memory blocks that make up a [`Hive`].
+
+use core::{
+    mem::{self, ManuallyDrop},
+    ptr::NonNull,
+};
+
+use crate::hive::skipfield;
+
+/// A type that may be either part of the free list or an element.
+pub union Slot<T, Sk>
+where
+    Sk: skipfield::SkipfieldType,
+{
+    /// An element of the [`Group`].
+    element: ManuallyDrop<T>,
+
+    /// A free list index.
+    free_list: FreeList<Sk>,
+}
+
+/// The contents of a free list index.
+///
+/// This uses the `packed` C representation to avoid any excess space. This is
+/// not a problem in the general case as our type will only ever be `u16` or
+/// `u8` unless an end-user overrides the skipfield type with a custom
+/// implementation.
+#[repr(C, packed)]
+#[derive(Copy, Clone)]
+pub struct FreeList<Sk>
+where
+    Sk: skipfield::SkipfieldType,
+{
+    /// Index of the previous element in the free list.
+    pub previous: Sk,
+
+    /// Index of the next element in the free list.
+    pub next: Sk,
+}
+
+/// A doubly-linked `Group` of `T` with a skipfield type of `Sk`.
+pub struct Group<T, Sk>
+where
+    Sk: skipfield::SkipfieldType,
+{
+    /// Pointer to the start of the skipfield.
+    pub skipfield: Option<NonNull<Sk>>,
+
+    /// Pointer to the next [`Group`].
+    pub next: Option<NonNull<Group<T, Sk>>>,
+
+    /// Pointer to element storage.
+    pub elements: Option<NonNull<Slot<T, Sk>>>,
+
+    /// Pointer to the previous [`Group`].
+    pub previous: Option<NonNull<Group<T, Sk>>>,
+
+    /// Index of the last erased element in the group.
+    ///
+    /// The last erased element contains the index of the next, and so on. If
+    /// this is equal to the maximum value of the underlying integer type,
+    /// then the free list is considered to be empty.
+    pub free_list_head: Sk,
+
+    /// Total number of elements this [`Group`] can hold.
+    pub capacity: Sk,
+
+    /// Number of elements stored in this [`Group`].
+    pub size: Sk,
+
+    /// Pointer to the next [`Group`] with erased elements.
+    pub next_with_erasures: Option<NonNull<Group<T, Sk>>>,
+
+    /// Pointer to the previous [`Group`] with erased elements.
+    pub previous_with_erasures: Option<NonNull<Group<T, Sk>>>,
+
+    /// Number assigned to this group in the [`Hive`].
+    pub number: usize,
+}
+
+impl<T, Sk> Group<T, Sk>
+where
+    Sk: skipfield::SkipfieldType,
+{
+    /// Size of each individual element within a [`Group`]
+    pub const ELEMENT_ALLOCATION_SIZE: usize =
+        compute_element_allocation_size::<T, Sk>();
+}
+
+/// Helper function which computes the allocation size of elements
+const fn compute_element_allocation_size<T, Sk>() -> usize {
+    let t_align = mem::align_of::<T>();
+    let t_size = mem::size_of::<T>();
+    let sk2_size = mem::size_of::<Sk>() * 2;
+    if t_align > t_size {
+        if sk2_size > t_align {
+            sk2_size
+        } else {
+            t_align
+        }
+    } else {
+        if sk2_size > t_size { sk2_size } else { t_size }
+    }
+}
diff --git a/crates/core/src/hive/mod.rs b/crates/core/src/hive/mod.rs
new file mode 100644
index 0000000..17568e3
--- /dev/null
+++ b/crates/core/src/hive/mod.rs
@@ -0,0 +1,256 @@
+//! 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(())
+    }
+}
diff --git a/crates/core/src/hive/skipfield.rs b/crates/core/src/hive/skipfield.rs
new file mode 100644
index 0000000..0fb2ab4
--- /dev/null
+++ b/crates/core/src/hive/skipfield.rs
@@ -0,0 +1,60 @@
+//! An implementation of a trait describing valid skipfield integer types.
+//!
+//! Only `u16`s and `u8`s are supported by default. However, other integral
+//! types may be used by implementing this trait on them; the trait is not
+//! sealed.
+
+use core::ops::{Add, AddAssign, Sub, SubAssign};
+
+/// Trait describing integral types in a generic way suitable for use as the
+/// element type of a skipfield.
+pub trait SkipfieldType:
+    Add + AddAssign + Sub + SubAssign + Ord + PartialOrd + Copy + Sized
+{
+    /// The maximum attainable value of this type.
+    const MAXIMUM: Self;
+
+    /// The zero element of this type.
+    const ZERO: Self;
+
+    /// The one element of this type.
+    const ONE: Self;
+
+    /// Conversion method from `usize` using `as` or an equivalent
+    fn from_usize(u: usize) -> Self;
+
+    /// Conversion method from `isize` using `as` or an equivalent
+    fn from_isize(i: isize) -> Self;
+}
+
+impl SkipfieldType for u16 {
+    const MAXIMUM: Self = u16::MAX;
+    const ZERO: Self = 0;
+    const ONE: Self = 1;
+
+    #[inline(always)]
+    fn from_usize(u: usize) -> Self {
+        u as u16
+    }
+
+    #[inline(always)]
+    fn from_isize(i: isize) -> Self {
+        i as u16
+    }
+}
+
+impl SkipfieldType for u8 {
+    const MAXIMUM: Self = u8::MAX;
+    const ZERO: Self = 0;
+    const ONE: Self = 1;
+
+    #[inline(always)]
+    fn from_usize(u: usize) -> Self {
+        u as u8
+    }
+
+    #[inline(always)]
+    fn from_isize(i: isize) -> Self {
+        i as u8
+    }
+}
diff --git a/crates/core/src/lib.rs b/crates/core/src/lib.rs
new file mode 100644
index 0000000..330ad58
--- /dev/null
+++ b/crates/core/src/lib.rs
@@ -0,0 +1,62 @@
+#![no_std]
+#![warn(
+    clippy::cargo_common_metadata,
+    clippy::dbg_macro,
+    clippy::needless_pass_by_ref_mut,
+    clippy::needless_pass_by_value,
+    clippy::print_stderr,
+    clippy::print_stdout,
+    clippy::todo,
+    clippy::unimplemented
+)]
+#![deny(
+    clippy::await_holding_lock,
+    rustdoc::broken_intra_doc_links,
+    clippy::cast_lossless,
+    clippy::clone_on_ref_ptr,
+    clippy::default_trait_access,
+    clippy::doc_markdown,
+    clippy::empty_enum,
+    clippy::enum_glob_use,
+    clippy::exit,
+    clippy::expect_used,
+    clippy::explicit_deref_methods,
+    clippy::explicit_into_iter_loop,
+    clippy::explicit_iter_loop,
+    clippy::fallible_impl_from,
+    clippy::filetype_is_file,
+    clippy::float_cmp,
+    clippy::float_cmp_const,
+    clippy::imprecise_flops,
+    clippy::inefficient_to_string,
+    clippy::large_digit_groups,
+    clippy::large_stack_arrays,
+    clippy::manual_filter_map,
+    clippy::match_like_matches_macro,
+    missing_docs,
+    clippy::missing_errors_doc,
+    clippy::missing_safety_doc,
+    clippy::mut_mut,
+    clippy::option_option,
+    clippy::panic,
+    clippy::panic_in_result_fn,
+    clippy::redundant_clone,
+    clippy::redundant_else,
+    clippy::rest_pat_in_fully_bound_structs,
+    clippy::single_match_else,
+    clippy::implicit_clone,
+    trivial_casts,
+    trivial_numeric_casts,
+    clippy::undocumented_unsafe_blocks,
+    clippy::unused_self,
+    clippy::unwrap_used,
+    clippy::wildcard_dependencies,
+    clippy::wildcard_imports
+)]
+#![feature(allocator_api)]
+
+//! A highly portable computer algebra system library implemented in Rust
+
+extern crate alloc;
+
+pub mod hive;