1 files changed, 104 insertions, 0 deletions
diff --git a/crates/core/src/hive/group.rs b/crates/core/src/hive/group.rs
new file mode 100644
index 0000000..32d070e
--- /dev/null
+++ b/crates/core/src/hive/group.rs
@@ -0,0 +1,104 @@
+//! 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)]
+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`.
+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 in the [`Hive`].
+    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 }
+    }
+}