tether-map 0.2.1

use alloc::vec::Vec;
use core::clone::Clone;
use core::fmt::Debug;
use core::hint::unreachable_unchecked;
use core::mem::MaybeUninit;
use core::ops::Index;
use core::ops::IndexMut;
use core::ptr::NonNull;

use bumpalo::Bump;

use crate::Ptr;

#[cfg(debug_assertions)]
pub(crate) type ArenaContainer<K, T> = alloc::boxed::Box<Arena<K, T>>;
#[cfg(not(debug_assertions))]
pub(crate) type ArenaContainer<K, T> = Arena<K, T>;

pub(crate) struct ActiveSlotRef<K, T> {
    slot: NonNull<LLSlot<K, T>>,
    #[cfg(debug_assertions)]
    arena: *const Arena<K, T>,
}

impl<K, T> Debug for ActiveSlotRef<K, T> {
    fn fmt(
        &self,
        f: &mut core::fmt::Formatter<'_>,
    ) -> core::fmt::Result {
        write!(f, "ActiveSlotRef({:p})", self.slot)
    }
}

impl<K, T> ActiveSlotRef<K, T> {
    #[inline(always)]
    pub(crate) fn data<'a>(
        &self,
        _arena: &'a Arena<K, T>,
    ) -> &'a NodeData<K, T> {
        #[cfg(debug_assertions)]
        {
            debug_assert_eq!(
                self.arena, _arena as *const Arena<K, T>,
                "ActiveSlotRef used with wrong Arena"
            );
        }
        // SAFETY: Our slot is allocated from the incoming arena, so no UAF. We can't
        // have any mutable borrows out because we always tie them to &mut arena
        // methods. We have no uninitialized data in Active slots.
        unsafe { self.slot.as_ref().data.assume_init_ref() }
    }

    #[inline(always)]
    pub(crate) fn data_mut<'a>(
        &mut self,
        _arena: &'a mut Arena<K, T>,
    ) -> &'a mut NodeData<K, T> {
        #[cfg(debug_assertions)]
        {
            debug_assert_eq!(
                self.arena, _arena as *const Arena<K, T>,
                "ActiveSlotRef used with wrong Arena"
            );
        }

        // SAFETY: Our slot is allocated from the incoming arena, so no UAF. We can't
        // have any other borrows because we always tie borrows to the lifetime of
        // either &arena or &mut arena. We have no uninitialized data in Active
        // slots.
        unsafe { self.slot.as_mut().data.assume_init_mut() }
    }

    #[inline(always)]
    pub(crate) fn this(
        &self,
        _arena: &Arena<K, T>,
    ) -> Ptr {
        #[cfg(debug_assertions)]
        {
            debug_assert_eq!(
                self.arena, _arena as *const Arena<K, T>,
                "ActiveSlotRef used with wrong Arena"
            );
        }

        // SAFETY: Our slot is always occupied if we have an ActiveSlotRef.
        unsafe { self.slot.as_ref().this }
    }

    #[inline(always)]
    pub(crate) fn next(
        &self,
        _arena: &Arena<K, T>,
    ) -> ActiveSlotRef<K, T> {
        #[cfg(debug_assertions)]
        {
            debug_assert_eq!(
                self.arena, _arena as *const Arena<K, T>,
                "ActiveSlotRef used with wrong Arena"
            );
        }
        // SAFETY: Our slot is always occupied if we have an ActiveSlotRef.
        unsafe {
            match &self.slot.as_ref().links {
                Links::Occupied { next, .. } => *next,
                Links::Vacant { .. } => unreachable_unchecked(),
            }
        }
    }

    #[inline(always)]
    pub(crate) fn next_mut<'a>(
        &mut self,
        _arena: &'a mut Arena<K, T>,
    ) -> &'a mut ActiveSlotRef<K, T> {
        #[cfg(debug_assertions)]
        {
            debug_assert_eq!(
                self.arena, _arena as *const Arena<K, T>,
                "ActiveSlotRef used with wrong Arena"
            );
        }
        // SAFETY: Our slot is allocated from the incoming arena, so no UAF. We can't
        // have any other borrows because we always tie borrows to the lifetime of
        // either &arena or &mut arena. We have no uninitialized data in Active
        // slots.
        unsafe {
            match &mut self.slot.as_mut().links {
                Links::Occupied { next, .. } => next,
                Links::Vacant { .. } => unreachable_unchecked(),
            }
        }
    }

    #[inline(always)]
    pub(crate) fn prev(
        &self,
        _arena: &Arena<K, T>,
    ) -> ActiveSlotRef<K, T> {
        #[cfg(debug_assertions)]
        {
            debug_assert_eq!(
                self.arena, _arena as *const Arena<K, T>,
                "ActiveSlotRef used with wrong Arena"
            );
        }
        // SAFETY: Our slot is always occupied if we have an ActiveSlotRef.
        unsafe {
            match &self.slot.as_ref().links {
                Links::Occupied { prev, .. } => *prev,
                Links::Vacant { .. } => unreachable_unchecked(),
            }
        }
    }

    #[inline(always)]
    pub(crate) fn prev_mut<'a>(
        &mut self,
        _arena: &'a mut Arena<K, T>,
    ) -> &'a mut ActiveSlotRef<K, T> {
        #[cfg(debug_assertions)]
        {
            debug_assert_eq!(
                self.arena, _arena as *const Arena<K, T>,
                "ActiveSlotRef used with wrong Arena"
            );
        }
        // SAFETY: Our slot is allocated from the incoming arena, so no UAF. We can't
        // have any other borrows because we always tie borrows to the lifetime of
        // either &arena or &mut arena. We have no uninitialized data in Active
        // slots.
        unsafe {
            match &mut self.slot.as_mut().links {
                Links::Occupied { prev, .. } => prev,
                Links::Vacant { .. } => unreachable_unchecked(),
            }
        }
    }

    #[inline(always)]
    pub(crate) fn as_ptr(&self) -> NonNull<LLSlot<K, T>> {
        self.slot
    }
}

impl<K, T> Clone for ActiveSlotRef<K, T> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<K, T> Copy for ActiveSlotRef<K, T> {}

impl<K, T> PartialEq for ActiveSlotRef<K, T> {
    fn eq(
        &self,
        other: &Self,
    ) -> bool {
        self.slot == other.slot
    }
}

impl<K, T> Eq for ActiveSlotRef<K, T> {}

pub(crate) struct NodeData<K, T> {
    pub(crate) key: K,
    pub(crate) value: T,
}

pub(crate) enum Links<K, T> {
    Occupied {
        prev: ActiveSlotRef<K, T>,
        next: ActiveSlotRef<K, T>,
    },
    Vacant {
        next_free: Option<NonNull<LLSlot<K, T>>>,
    },
}

impl<K, T> Debug for Links<K, T> {
    fn fmt(
        &self,
        f: &mut core::fmt::Formatter<'_>,
    ) -> core::fmt::Result {
        match self {
            Links::Occupied { prev, next } => f
                .debug_struct("Links::Occupied")
                .field("prev", prev)
                .field("next", next)
                .finish(),
            Links::Vacant { next_free } => f
                .debug_struct("Links::Vacant")
                .field("next_free", next_free)
                .finish(),
        }
    }
}

pub(crate) struct LLSlot<K, T> {
    pub(crate) this: Ptr,
    pub(crate) links: Links<K, T>,
    pub(crate) data: MaybeUninit<NodeData<K, T>>,
}

impl<K, T> Debug for LLSlot<K, T> {
    fn fmt(
        &self,
        f: &mut core::fmt::Formatter<'_>,
    ) -> core::fmt::Result {
        f.debug_struct("LLSlot")
            .field("this", &self.this)
            .field("links", &self.links)
            .finish()
    }
}

pub(crate) struct FreedSlot<K, T> {
    pub(crate) data: NodeData<K, T>,
    pub(crate) this: Ptr,
    pub(crate) prev_next: Option<(ActiveSlotRef<K, T>, ActiveSlotRef<K, T>)>,
}

#[derive(Debug)]
pub(crate) struct Arena<K, T> {
    bump: Bump,
    slots: Vec<NonNull<LLSlot<K, T>>>,
    #[cfg(feature = "generational")]
    generations: Vec<u32>,
    free_list_head: Option<NonNull<LLSlot<K, T>>>,
}

impl<K, T> Drop for Arena<K, T> {
    fn drop(&mut self) {
        // SAFETY: We mark each slot as vacant before dropping it, so we won't
        // double-drop anything.
        unsafe {
            for slot_ptr in &mut self.slots {
                let slot_ref = slot_ptr.as_mut();
                match &slot_ref.links {
                    Links::Occupied { .. } => {
                        slot_ref.links = Links::Vacant { next_free: None };
                        slot_ref.data.assume_init_drop();
                    }
                    Links::Vacant { .. } => {}
                }
            }
        }
    }
}

impl<K, T> Arena<K, T> {
    #[inline]
    pub(crate) fn with_capacity(capacity: usize) -> ArenaContainer<K, T> {
        #[cfg(debug_assertions)]
        {
            alloc::boxed::Box::new(Self {
                bump: Bump::with_capacity(capacity * core::mem::size_of::<LLSlot<K, T>>()),
                slots: Vec::with_capacity(capacity),
                free_list_head: None,
                #[cfg(feature = "generational")]
                generations: Vec::with_capacity(capacity),
            })
        }
        #[cfg(not(debug_assertions))]
        Self {
            bump: Bump::with_capacity(capacity * core::mem::size_of::<LLSlot<K, T>>()),
            slots: Vec::with_capacity(capacity),
            free_list_head: None,
            #[cfg(feature = "generational")]
            generations: Vec::with_capacity(capacity),
        }
    }

    #[inline]
    pub(crate) fn map_ptr(
        &self,
        ptr: Ptr,
    ) -> Option<ActiveSlotRef<K, T>> {
        self.slots
            .get(ptr.unchecked_get())
            .filter(|slot| {
                // SAFETY: Slot was allocated from our own arena, so it's still valid.
                unsafe { matches!(slot.as_ref().links, Links::Occupied { .. }) }
            })
            .filter(|_slot| {
                // SAFETY: Slot was allocated from our own arena, so it's still valid, we've
                // checked that it's occupied.
                #[cfg(feature = "generational")]
                unsafe {
                    let index = _slot.as_ref().this.unchecked_get();
                    self.generations.get(index) == Some(&ptr.generation)
                }
                #[cfg(not(feature = "generational"))]
                true
            })
            .map(|&slot| ActiveSlotRef {
                slot,
                #[cfg(debug_assertions)]
                arena: self as *const Arena<K, T>,
            })
    }

    #[inline]
    pub(crate) fn is_occupied(
        &self,
        ptr: Ptr,
    ) -> bool {
        self.slots.get(ptr.unchecked_get()).is_some_and(|slot| {
            // SAFETY: Slot was allocated from our own arena, so it's still valid.
            if unsafe { !matches!(slot.as_ref().links, Links::Occupied { .. }) } {
                return false;
            }

            // SAFETY: Slot was allocated from our own arena, so it's still valid, we've
            // checked that it's occupied.
            #[cfg(feature = "generational")]
            unsafe {
                let index = slot.as_ref().this.unchecked_get();
                self.generations.get(index) == Some(&ptr.generation)
            }
            #[cfg(not(feature = "generational"))]
            true
        })
    }

    #[inline]
    pub(crate) fn alloc_circular(
        &mut self,
        key: K,
        value: T,
    ) -> ActiveSlotRef<K, T> {
        if let Some(mut free_slot) = self.free_list_head {
            // SAFETY: The free list only contains valid, uninitialized slots
            // that are not currently in use. We have exclusive
            // access to the arena, so we can safely take a slot
            // from the free list.
            unsafe {
                let next_free = match &free_slot.as_ref().links {
                    Links::Vacant { next_free } => *next_free,
                    Links::Occupied { .. } => unreachable_unchecked(),
                };

                self.free_list_head = next_free;

                let active_slot = ActiveSlotRef {
                    slot: free_slot,
                    #[cfg(debug_assertions)]
                    arena: self as *const Arena<K, T>,
                };

                free_slot.as_mut().links = Links::Occupied {
                    prev: active_slot,
                    next: active_slot,
                };

                free_slot.as_mut().data = MaybeUninit::new(NodeData { key, value });
                #[cfg(feature = "generational")]
                {
                    let index = free_slot.as_ref().this.unchecked_get();
                    self.generations[index] = self.generations[index].wrapping_add(1);
                    free_slot.as_mut().this = Ptr::unchecked_from(index, self.generations[index]);
                }

                active_slot
            }
        } else {
            #[cfg(feature = "generational")]
            let ptr = Ptr::unchecked_from(self.slots.len(), 0);
            #[cfg(not(feature = "generational"))]
            let ptr = Ptr::unchecked_from(self.slots.len());

            let slot = self.bump.alloc(LLSlot {
                this: ptr,
                links: Links::Vacant { next_free: None },
                data: MaybeUninit::new(NodeData { key, value }),
            });
            let mut slot_ptr = NonNull::from_mut(slot);
            let active_slot = ActiveSlotRef {
                slot: slot_ptr,
                #[cfg(debug_assertions)]
                arena: self as *const Arena<K, T>,
            };
            // SAFETY: We just allocated this slot.
            unsafe {
                slot_ptr.as_mut().links = Links::Occupied {
                    prev: active_slot,
                    next: active_slot,
                };
            }

            self.slots.push(slot_ptr);

            #[cfg(feature = "generational")]
            self.generations.push(0);

            active_slot
        }
    }

    #[inline]
    pub(crate) fn alloc(
        &mut self,
        key: K,
        value: T,
        prev: ActiveSlotRef<K, T>,
        next: ActiveSlotRef<K, T>,
    ) -> ActiveSlotRef<K, T> {
        if let Some(mut free_slot) = self.free_list_head {
            // SAFETY: The free list only contains valid, uninitialized slots
            // that are not currently in use. We have exclusive
            // access to the arena, so we can safely take a slot
            // from the free list.
            unsafe {
                let next_free = match &free_slot.as_ref().links {
                    Links::Vacant { next_free } => *next_free,
                    Links::Occupied { .. } => unreachable_unchecked(),
                };

                self.free_list_head = next_free;

                let active_slot = ActiveSlotRef {
                    slot: free_slot,
                    #[cfg(debug_assertions)]
                    arena: self as *const Arena<K, T>,
                };

                free_slot.as_mut().links = Links::Occupied { prev, next };
                free_slot.as_mut().data = MaybeUninit::new(NodeData { key, value });

                #[cfg(feature = "generational")]
                {
                    let index = free_slot.as_ref().this.unchecked_get();
                    self.generations[index] = self.generations[index].wrapping_add(1);
                    free_slot.as_mut().this = Ptr::unchecked_from(index, self.generations[index]);
                }

                active_slot
            }
        } else {
            #[cfg(feature = "generational")]
            let ptr = Ptr::unchecked_from(self.slots.len(), 0);
            #[cfg(not(feature = "generational"))]
            let ptr = Ptr::unchecked_from(self.slots.len());

            let slot = self.bump.alloc(LLSlot {
                this: ptr,
                links: Links::Occupied { prev, next },
                data: MaybeUninit::new(NodeData { key, value }),
            });
            let slot_ptr = NonNull::from_mut(slot);
            let active_slot = ActiveSlotRef {
                slot: slot_ptr,
                #[cfg(debug_assertions)]
                arena: self as *const Arena<K, T>,
            };

            self.slots.push(slot_ptr);
            #[cfg(feature = "generational")]
            self.generations.push(0);
            active_slot
        }
    }

    /// # SAFETY
    ///
    /// The caller **must not** deref any copies of the passed in slot after
    /// calling this function.
    #[inline]
    pub(crate) unsafe fn free_and_unlink(
        &mut self,
        mut slot: ActiveSlotRef<K, T>,
    ) -> FreedSlot<K, T> {
        // SAFETY: Active slots are occupied, so we can access their data and links.
        let (prev_next, data, this) = unsafe {
            let slot_ref = slot.slot.as_mut();
            match slot_ref.links {
                Links::Occupied { mut prev, mut next } => {
                    let data = slot_ref.data.assume_init_read();
                    let this = slot_ref.this;

                    slot_ref.links = Links::Vacant {
                        next_free: self.free_list_head,
                    };
                    self.free_list_head = Some(slot.slot);

                    let prev_next = if prev == slot || next == slot {
                        None
                    } else {
                        *prev.next_mut(self) = next;
                        *next.prev_mut(self) = prev;

                        Some((prev, next))
                    };
                    (prev_next, data, this)
                }
                Links::Vacant { .. } => unreachable_unchecked(),
            }
        };

        FreedSlot {
            data,
            this,
            prev_next,
        }
    }
}

impl<K, T> Index<Ptr> for Arena<K, T> {
    type Output = NodeData<K, T>;

    #[inline]
    fn index(
        &self,
        index: Ptr,
    ) -> &Self::Output {
        self.map_ptr(index)
            .as_ref()
            .expect("Indexing with invalid or freed Ptr")
            .data(self)
    }
}

impl<K, T> IndexMut<Ptr> for Arena<K, T> {
    #[inline]
    fn index_mut(
        &mut self,
        index: Ptr,
    ) -> &mut Self::Output {
        self.map_ptr(index)
            .as_mut()
            .expect("Indexing with invalid or freed Ptr")
            .data_mut(self)
    }
}

#[cfg(test)]
mod tests {
    use alloc::format;
    use alloc::string::String;
    use alloc::string::ToString;

    use super::*;

    #[test]
    fn test_arena_creation() {
        let arena: ArenaContainer<i32, String> = Arena::with_capacity(10);

        assert_eq!(arena.slots.len(), 0);
    }

    #[test]
    fn test_alloc_circular_single_element() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(1, "first".to_string());

        assert_eq!(slot.data(&arena).key, 1);
        assert_eq!(slot.data(&arena).value, "first");
        assert_eq!(slot.next(&arena), slot);
        assert_eq!(slot.prev(&arena), slot);
        assert_eq!(arena.slots.len(), 1);
    }

    #[test]
    fn test_alloc_circular_multiple_elements() {
        let mut arena = Arena::with_capacity(5);
        let first = arena.alloc_circular(1, "first".to_string());
        let second = arena.alloc_circular(2, "second".to_string());

        assert_eq!(first.data(&arena).key, 1);
        assert_eq!(second.data(&arena).key, 2);
        assert_eq!(arena.slots.len(), 2);

        assert_eq!(first.next(&arena), first);
        assert_eq!(first.prev(&arena), first);
        assert_eq!(second.next(&arena), second);
        assert_eq!(second.prev(&arena), second);
    }

    #[test]
    fn test_alloc_with_links() {
        let mut arena = Arena::with_capacity(5);
        let first = arena.alloc_circular(1, "first".to_string());
        let second = arena.alloc(2, "second".to_string(), first, first);

        assert_eq!(second.data(&arena).key, 2);
        assert_eq!(second.prev(&arena), first);
        assert_eq!(second.next(&arena), first);
        assert_eq!(arena.slots.len(), 2);
    }

    #[test]
    fn test_active_slot_ref_data_access() {
        let mut arena = Arena::with_capacity(5);
        let mut slot = arena.alloc_circular(42, "test".to_string());

        let data = slot.data(&arena);
        assert_eq!(data.key, 42);
        assert_eq!(data.value, "test");

        let data_mut = slot.data_mut(&mut arena);
        data_mut.value = "modified".to_string();

        assert_eq!(slot.data(&arena).value, "modified");
    }

    #[test]
    fn test_active_slot_ref_navigation() {
        let mut arena = Arena::with_capacity(5);
        let mut first = arena.alloc_circular(1, "first".to_string());
        let mut second = arena.alloc(2, "second".to_string(), first, first);
        let third = arena.alloc(3, "third".to_string(), second, first);

        *second.next_mut(&mut arena) = third;
        *first.prev_mut(&mut arena) = third;

        assert_eq!(second.next(&arena), third);
        assert_eq!(third.prev(&arena), second);
    }

    #[test]
    fn test_active_slot_ref_this() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(1, "test".to_string());

        let ptr = slot.this(&arena);
        assert_eq!(ptr.unchecked_get(), 0);
    }

    #[test]
    fn test_active_slot_ref_as_ptr() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(1, "test".to_string());

        let raw_ptr = slot.as_ptr();

        assert_eq!(raw_ptr, slot.slot);
    }

    #[test]
    fn test_active_slot_ref_equality() {
        let mut arena = Arena::with_capacity(5);
        let slot1 = arena.alloc_circular(1, "test".to_string());
        let slot2 = slot1;
        let slot3 = arena.alloc_circular(2, "other".to_string());

        assert_eq!(slot1, slot2);
        assert_ne!(slot1, slot3);
    }

    #[test]
    fn test_active_slot_ref_debug() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(1, "test".to_string());

        let debug_str = format!("{:?}", slot);
        assert!(debug_str.starts_with("ActiveSlotRef("));
    }

    #[test]
    fn test_map_ptr_valid() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let ptr = slot.this(&arena);

        let mapped = arena.map_ptr(ptr);
        assert!(mapped.is_some());
        assert_eq!(mapped.unwrap().data(&arena).key, 42);
    }

    #[test]
    fn test_map_ptr_invalid_index() {
        let arena = Arena::<i32, String>::with_capacity(5);

        #[cfg(not(feature = "generational"))]
        let invalid_ptr = Ptr::unchecked_from(999);
        #[cfg(feature = "generational")]
        let invalid_ptr = Ptr::unchecked_from(999, 0);

        let mapped = arena.map_ptr(invalid_ptr);
        assert!(mapped.is_none());
    }

    #[test]
    fn test_is_occupied_valid() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let ptr = slot.this(&arena);

        assert!(arena.is_occupied(ptr));
    }

    #[test]
    fn test_is_occupied_invalid() {
        let arena = Arena::<i32, String>::with_capacity(5);

        #[cfg(not(feature = "generational"))]
        let invalid_ptr = Ptr::unchecked_from(999);
        #[cfg(feature = "generational")]
        let invalid_ptr = Ptr::unchecked_from(999, 0);

        assert!(!arena.is_occupied(invalid_ptr));
    }

    #[test]
    fn test_free_and_unlink_single_element() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let ptr = slot.this(&arena);

        let freed = unsafe { arena.free_and_unlink(slot) };

        assert_eq!(freed.data.key, 42);
        assert_eq!(freed.data.value, "test");
        assert_eq!(freed.this, ptr);
        assert!(freed.prev_next.is_none());

        assert!(!arena.is_occupied(ptr));
        assert!(arena.free_list_head.is_some());
    }

    #[test]
    fn test_free_and_unlink_with_neighbors() {
        let mut arena = Arena::with_capacity(5);
        let mut first = arena.alloc_circular(1, "first".to_string());
        let mut second = arena.alloc(2, "second".to_string(), first, first);
        let mut third = arena.alloc(3, "third".to_string(), second, first);

        *first.next_mut(&mut arena) = second;
        *first.prev_mut(&mut arena) = third;
        *second.next_mut(&mut arena) = third;
        *second.prev_mut(&mut arena) = first;
        *third.next_mut(&mut arena) = first;
        *third.prev_mut(&mut arena) = second;

        let second_ptr = second.this(&arena);
        let freed = unsafe { arena.free_and_unlink(second) };

        assert_eq!(freed.data.key, 2);
        assert!(freed.prev_next.is_some());
        let (prev, next) = freed.prev_next.unwrap();
        assert_eq!(prev, first);
        assert_eq!(next, third);

        assert_eq!(first.next(&arena), third);
        assert_eq!(third.prev(&arena), first);

        assert!(!arena.is_occupied(second_ptr));
    }

    #[test]
    fn test_free_list_reuse() {
        let mut arena = Arena::with_capacity(5);
        let first = arena.alloc_circular(1, "first".to_string());
        let first_ptr = first.this(&arena);

        unsafe { arena.free_and_unlink(first) };

        let second = arena.alloc_circular(2, "second".to_string());
        let second_ptr = second.this(&arena);

        assert_eq!(first_ptr.unchecked_get(), second_ptr.unchecked_get());
        assert_eq!(arena.slots.len(), 1);
    }

    #[test]
    fn test_multiple_free_list_operations() {
        let mut arena = Arena::with_capacity(10);

        let slots: Vec<_> = (0..5)
            .map(|i| arena.alloc_circular(i, format!("value{}", i)))
            .collect();

        assert_eq!(arena.slots.len(), 5);

        unsafe {
            arena.free_and_unlink(slots[1]);
            arena.free_and_unlink(slots[3]);
        }

        let new1 = arena.alloc_circular(10, "new1".to_string());
        let new2 = arena.alloc_circular(11, "new2".to_string());

        assert_eq!(arena.slots.len(), 5);
        assert_eq!(new1.data(&arena).key, 10);
        assert_eq!(new2.data(&arena).key, 11);
    }

    #[test]
    fn test_index_trait() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let ptr = slot.this(&arena);

        assert_eq!(arena[ptr].key, 42);
        assert_eq!(arena[ptr].value, "test");
    }

    #[test]
    fn test_index_mut_trait() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let ptr = slot.this(&arena);

        arena[ptr].value = "modified".to_string();
        assert_eq!(arena[ptr].value, "modified");
    }

    #[test]
    #[should_panic]
    fn test_index_invalid_ptr_panic() {
        let arena = Arena::<i32, String>::with_capacity(5);

        #[cfg(not(feature = "generational"))]
        let invalid_ptr = Ptr::unchecked_from(999);
        #[cfg(feature = "generational")]
        let invalid_ptr = Ptr::unchecked_from(999, 0);

        let _ = &arena[invalid_ptr];
    }

    #[test]
    #[should_panic]
    fn test_index_mut_invalid_ptr_panic() {
        let mut arena = Arena::<i32, String>::with_capacity(5);

        #[cfg(not(feature = "generational"))]
        let invalid_ptr = Ptr::unchecked_from(999);
        #[cfg(feature = "generational")]
        let invalid_ptr = Ptr::unchecked_from(999, 0);

        let _ = &mut arena[invalid_ptr];
    }

    #[test]
    #[should_panic]
    fn test_index_freed_ptr_panic() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let ptr = slot.this(&arena);

        unsafe { arena.free_and_unlink(slot) };

        let _ = &arena[ptr];
    }

    #[test]
    fn test_freed_slot_struct() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let ptr = slot.this(&arena);

        let freed = unsafe { arena.free_and_unlink(slot) };

        assert_eq!(freed.data.key, 42);
        assert_eq!(freed.data.value, "test");
        assert_eq!(freed.this, ptr);
        assert!(freed.prev_next.is_none());
    }

    #[test]
    fn test_drop_behavior() {
        let mut arena = Arena::with_capacity(5);

        let _slot1 = arena.alloc_circular(1, "first".to_string());
        let _slot2 = arena.alloc_circular(2, "second".to_string());
        let slot3 = arena.alloc_circular(3, "third".to_string());

        unsafe { arena.free_and_unlink(slot3) };

        drop(arena);
    }

    #[test]
    fn test_capacity_management() {
        let arena = Arena::<i32, String>::with_capacity(100);

        assert!(arena.slots.capacity() >= 100);

        #[cfg(feature = "generational")]
        assert!(arena.generations.capacity() >= 100);
    }

    #[cfg(feature = "generational")]
    #[test]
    fn test_generational_tracking() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let ptr = slot.this(&arena);

        assert_eq!(ptr.generation, 0);

        unsafe { arena.free_and_unlink(slot) };
        let new_slot = arena.alloc_circular(43, "new".to_string());
        let new_ptr = new_slot.this(&arena);

        assert_eq!(new_ptr.generation, 1);
        assert_eq!(new_ptr.unchecked_get(), ptr.unchecked_get());

        assert!(!arena.is_occupied(ptr));
        assert!(arena.is_occupied(new_ptr));
    }

    #[cfg(feature = "generational")]
    #[test]
    fn test_generational_map_ptr_stale() {
        let mut arena = Arena::with_capacity(5);
        let slot = arena.alloc_circular(42, "test".to_string());
        let old_ptr = slot.this(&arena);

        unsafe { arena.free_and_unlink(slot) };
        let _new_slot = arena.alloc_circular(43, "new".to_string());

        assert!(arena.map_ptr(old_ptr).is_none());
    }
}