//! 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 where Sk: skipfield::SkipfieldType, { /// An element of the [`Group`]. element: ManuallyDrop, /// A free list index. free_list: FreeList, } /// 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 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 where Sk: skipfield::SkipfieldType, { /// Pointer to the start of the skipfield. pub skipfield: Option>, /// Pointer to the next [`Group`]. pub next: Option>>, /// Pointer to element storage. pub elements: Option>>, /// Pointer to the previous [`Group`]. pub previous: Option>>, /// 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>>, /// Pointer to the previous [`Group`] with erased elements. pub previous_with_erasures: Option>>, /// Number assigned to this group. pub number: usize, } impl Group where Sk: skipfield::SkipfieldType, { /// Size of each individual element within a [`Group`] pub const ELEMENT_ALLOCATION_SIZE: usize = compute_element_allocation_size::(); } /// Helper function which computes the allocation size of elements const fn compute_element_allocation_size() -> usize { let t_align = mem::align_of::(); let t_size = mem::size_of::(); let sk2_size = mem::size_of::() * 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::::ELEMENT_ALLOCATION_SIZE, 4, "element allocation size with T = u32, Sk = u8 is 4" ); } }