diff options
Diffstat (limited to 'crates/core/src/hive')
| -rw-r--r-- | crates/core/src/hive/group.rs | 122 | ||||
| -rw-r--r-- | crates/core/src/hive/mod.rs | 336 | ||||
| -rw-r--r-- | crates/core/src/hive/skipfield.rs | 67 |
3 files changed, 0 insertions, 525 deletions
diff --git a/crates/core/src/hive/group.rs b/crates/core/src/hive/group.rs deleted file mode 100644 index 9217897..0000000 --- a/crates/core/src/hive/group.rs +++ /dev/null @@ -1,122 +0,0 @@ -//! 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)] -#[cfg_attr(feature = "core-fmt", derive(Debug))] -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`. -#[cfg_attr(feature = "core-fmt", derive(Debug))] -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. - 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 - } -} - -#[cfg(all(test, feature = "core-error"))] -mod test { - use super::*; - - #[test] - fn validate_element_allocation_size() { - assert_eq!( - Group::<u32, u8>::ELEMENT_ALLOCATION_SIZE, - 4, - "element allocation size with T = u32, Sk = u8 is 4" - ); - } -} 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(()) - } -} diff --git a/crates/core/src/hive/skipfield.rs b/crates/core/src/hive/skipfield.rs deleted file mode 100644 index 16a3dcb..0000000 --- a/crates/core/src/hive/skipfield.rs +++ /dev/null @@ -1,67 +0,0 @@ -//! 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::{ - cmp, - 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 - /// - /// Caps the value of the input by the maximum of `Self`. - fn from_usize(u: usize) -> Self; - - /// Conversion method from `isize` using `as` or an equivalent - /// - /// Caps the value of the input by the maximum of `Self`. - 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 { - cmp::min(u, Self::MAXIMUM as usize) as u16 - } - - #[inline(always)] - fn from_isize(i: isize) -> Self { - cmp::min(i, Self::MAXIMUM as isize) 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 { - cmp::min(u, Self::MAXIMUM as usize) as u8 - } - - #[inline(always)] - fn from_isize(i: isize) -> Self { - cmp::min(i, Self::MAXIMUM as isize) as u8 - } -} |