diff options
Diffstat (limited to 'crates/core/src/hive/mod.rs')
| -rw-r--r-- | crates/core/src/hive/mod.rs | 256 |
1 files changed, 256 insertions, 0 deletions
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(()) + } +} |