diff options
Diffstat (limited to 'crates/core/src/hive')
| -rw-r--r-- | crates/core/src/hive/group.rs | 24 | ||||
| -rw-r--r-- | crates/core/src/hive/mod.rs | 82 | ||||
| -rw-r--r-- | crates/core/src/hive/skipfield.rs | 17 |
3 files changed, 114 insertions, 9 deletions
diff --git a/crates/core/src/hive/group.rs b/crates/core/src/hive/group.rs index 32d070e..9217897 100644 --- a/crates/core/src/hive/group.rs +++ b/crates/core/src/hive/group.rs @@ -1,4 +1,4 @@ -//! An implementation of the individual memory blocks that make up a [`Hive`]. +//! An implementation of the individual memory blocks that make up a hive. use core::{ mem::{self, ManuallyDrop}, @@ -27,6 +27,7 @@ where /// implementation. #[repr(C, packed)] #[derive(Copy, Clone)] +#[cfg_attr(feature = "core-fmt", derive(Debug))] pub struct FreeList<Sk> where Sk: skipfield::SkipfieldType, @@ -39,6 +40,7 @@ where } /// 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, @@ -74,7 +76,7 @@ where /// 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`]. + /// Number assigned to this group. pub number: usize, } @@ -98,7 +100,23 @@ const fn compute_element_allocation_size<T, Sk>() -> usize { } else { t_align } + } else if sk2_size > t_size { + sk2_size } else { - if sk2_size > t_size { sk2_size } else { t_size } + 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 index 17568e3..ad14725 100644 --- a/crates/core/src/hive/mod.rs +++ b/crates/core/src/hive/mod.rs @@ -12,6 +12,7 @@ // 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}; @@ -26,6 +27,7 @@ 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, @@ -127,6 +129,14 @@ where 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) } @@ -161,6 +171,9 @@ where /// 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") } @@ -181,6 +194,73 @@ where 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!() } } @@ -202,7 +282,7 @@ pub enum Error { /// Allocation size exceeded `isize::MAX`. CapacityOverflow, - /// An unspecified allocation error occurred. + /// Unspecified allocation error. /// /// The layout used during allocation is provided for troubleshooting /// where that is possible. Ideally, future revisions of the diff --git a/crates/core/src/hive/skipfield.rs b/crates/core/src/hive/skipfield.rs index 0fb2ab4..16a3dcb 100644 --- a/crates/core/src/hive/skipfield.rs +++ b/crates/core/src/hive/skipfield.rs @@ -4,7 +4,10 @@ //! types may be used by implementing this trait on them; the trait is not //! sealed. -use core::ops::{Add, AddAssign, Sub, SubAssign}; +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. @@ -21,9 +24,13 @@ pub trait SkipfieldType: 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; } @@ -34,12 +41,12 @@ impl SkipfieldType for u16 { #[inline(always)] fn from_usize(u: usize) -> Self { - u as u16 + cmp::min(u, Self::MAXIMUM as usize) as u16 } #[inline(always)] fn from_isize(i: isize) -> Self { - i as u16 + cmp::min(i, Self::MAXIMUM as isize) as u16 } } @@ -50,11 +57,11 @@ impl SkipfieldType for u8 { #[inline(always)] fn from_usize(u: usize) -> Self { - u as u8 + cmp::min(u, Self::MAXIMUM as usize) as u8 } #[inline(always)] fn from_isize(i: isize) -> Self { - i as u8 + cmp::min(i, Self::MAXIMUM as isize) as u8 } } |