diff options
Diffstat (limited to 'crates/core/src/hive/mod.rs')
| -rw-r--r-- | crates/core/src/hive/mod.rs | 336 |
1 files changed, 0 insertions, 336 deletions
diff --git a/crates/core/src/hive/mod.rs b/crates/core/src/hive/mod.rs deleted file mode 100644 index 3f83099..0000000 --- a/crates/core/src/hive/mod.rs +++ /dev/null @@ -1,336 +0,0 @@ -//! 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, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.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" - } - }; - f.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(()) - } -} |