From 386279ce28a54002fa91f436d5b60815c537e910 Mon Sep 17 00:00:00 2001
From: superwhiskers <whiskerdev@protonmail.com>
Date: Sat, 26 Jul 2025 23:02:34 -0400
Subject: initial commit

Change-Id: I6a6a69640e8a301a692a5455d1261816280d9cde
---
 crates/core/src/hive/group.rs | 104 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 104 insertions(+)
 create mode 100644 crates/core/src/hive/group.rs

(limited to 'crates/core/src/hive/group.rs')

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 }
+    }
+}
-- 
cgit 1.4.1-2-gfad0