sable_core/

handle.rs

//! Generational index handles for safe resource references.
//!
//! Handles provide a safe way to reference resources that may be deleted.
//! Each handle contains an index and a generation counter that is incremented
//! when the slot is reused, preventing dangling references.
//!
//! # Thread Safety
//!
//! This module provides two allocator variants:
//! - [`HandleAllocator`] — Single-threaded, zero-overhead allocator
//! - [`ConcurrentHandleAllocator`] — Thread-safe allocator using `parking_lot` (requires `parallel` feature)
//!
//! # Parallel Iteration
//!
//! With the `parallel` feature enabled, [`HandleAllocator`] supports parallel iteration
//! via rayon's `par_iter()` method.

use std::marker::PhantomData;

/// A generational index handle.
///
/// The handle contains:
/// - An index into a resource array
/// - A generation counter to detect stale references
/// - A phantom type marker for type safety
#[derive(Debug)]
pub struct Handle<T> {
    index: u32,
    generation: u32,
    _marker: PhantomData<T>,
}

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

impl<T> Copy for Handle<T> {}

impl<T> PartialEq for Handle<T> {
    fn eq(&self, other: &Self) -> bool {
        self.index == other.index && self.generation == other.generation
    }
}

impl<T> Eq for Handle<T> {}

impl<T> std::hash::Hash for Handle<T> {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.index.hash(state);
        self.generation.hash(state);
    }
}

impl<T> Handle<T> {
    /// Creates a new handle with the given index and generation.
    #[inline]
    #[must_use]
    pub const fn new(index: u32, generation: u32) -> Self {
        Self {
            index,
            generation,
            _marker: PhantomData,
        }
    }

    /// Returns the index portion of the handle.
    #[inline]
    #[must_use]
    pub const fn index(self) -> u32 {
        self.index
    }

    /// Returns the generation portion of the handle.
    #[inline]
    #[must_use]
    pub const fn generation(self) -> u32 {
        self.generation
    }

    /// Creates a dangling handle that doesn't point to any valid resource.
    #[inline]
    #[must_use]
    pub const fn dangling() -> Self {
        Self {
            index: u32::MAX,
            generation: 0,
            _marker: PhantomData,
        }
    }

    /// Checks if this handle is dangling.
    #[inline]
    #[must_use]
    pub const fn is_dangling(self) -> bool {
        self.index == u32::MAX
    }
}

impl<T> Default for Handle<T> {
    fn default() -> Self {
        Self::dangling()
    }
}

/// Entry in the handle allocator.
#[derive(Debug, Clone)]
struct AllocatorEntry<T> {
    /// The stored value, if any.
    value: Option<T>,
    /// Current generation for this slot.
    generation: u32,
}

impl<T> Default for AllocatorEntry<T> {
    fn default() -> Self {
        Self {
            value: None,
            generation: 0,
        }
    }
}

/// An allocator for generational handles.
///
/// Manages allocation and deallocation of handles, ensuring that
/// stale handles are detected.
#[derive(Debug)]
pub struct HandleAllocator<T> {
    entries: Vec<AllocatorEntry<T>>,
    free_list: Vec<u32>,
}

impl<T> Default for HandleAllocator<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> HandleAllocator<T> {
    /// Creates a new empty allocator.
    #[must_use]
    pub fn new() -> Self {
        Self {
            entries: Vec::new(),
            free_list: Vec::new(),
        }
    }

    /// Creates an allocator with pre-allocated capacity.
    #[must_use]
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            entries: Vec::with_capacity(capacity),
            free_list: Vec::new(),
        }
    }

    /// Allocates a handle for the given value.
    #[must_use]
    pub fn allocate(&mut self, value: T) -> Handle<T> {
        if let Some(index) = self.free_list.pop() {
            let entry = &mut self.entries[index as usize];
            entry.value = Some(value);
            Handle::new(index, entry.generation)
        } else {
            let index = self.entries.len() as u32;
            self.entries.push(AllocatorEntry {
                value: Some(value),
                generation: 0,
            });
            Handle::new(index, 0)
        }
    }

    /// Deallocates a handle, returning the value if the handle was valid.
    pub fn deallocate(&mut self, handle: Handle<T>) -> Option<T> {
        let index = handle.index as usize;
        if index >= self.entries.len() {
            return None;
        }

        let entry = &mut self.entries[index];
        if entry.generation != handle.generation {
            return None;
        }

        let value = entry.value.take();
        if value.is_some() {
            entry.generation = entry.generation.wrapping_add(1);
            self.free_list.push(handle.index);
        }
        value
    }

    /// Gets a reference to the value, if the handle is valid.
    #[must_use]
    pub fn get(&self, handle: Handle<T>) -> Option<&T> {
        let index = handle.index as usize;
        if index >= self.entries.len() {
            return None;
        }

        let entry = &self.entries[index];
        if entry.generation != handle.generation {
            return None;
        }

        entry.value.as_ref()
    }

    /// Gets a mutable reference to the value, if the handle is valid.
    #[must_use]
    pub fn get_mut(&mut self, handle: Handle<T>) -> Option<&mut T> {
        let index = handle.index as usize;
        if index >= self.entries.len() {
            return None;
        }

        let entry = &mut self.entries[index];
        if entry.generation != handle.generation {
            return None;
        }

        entry.value.as_mut()
    }

    /// Checks if a handle is valid.
    #[must_use]
    pub fn is_valid(&self, handle: Handle<T>) -> bool {
        self.get(handle).is_some()
    }

    /// Returns the number of allocated handles.
    #[must_use]
    pub fn len(&self) -> usize {
        self.entries.len() - self.free_list.len()
    }

    /// Returns true if no handles are allocated.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns the total capacity.
    #[must_use]
    pub fn capacity(&self) -> usize {
        self.entries.capacity()
    }

    /// Clears all entries, deallocating all handles.
    pub fn clear(&mut self) {
        self.entries.clear();
        self.free_list.clear();
    }

    /// Iterates over all valid (handle, value) pairs.
    pub fn iter(&self) -> impl Iterator<Item = (Handle<T>, &T)> {
        self.entries
            .iter()
            .enumerate()
            .filter_map(|(index, entry)| {
                entry
                    .value
                    .as_ref()
                    .map(|value| (Handle::new(index as u32, entry.generation), value))
            })
    }

    /// Iterates over all valid (handle, value) pairs mutably.
    pub fn iter_mut(&mut self) -> impl Iterator<Item = (Handle<T>, &mut T)> {
        self.entries
            .iter_mut()
            .enumerate()
            .filter_map(|(index, entry)| {
                let generation = entry.generation;
                entry
                    .value
                    .as_mut()
                    .map(|value| (Handle::new(index as u32, generation), value))
            })
    }

    /// Returns an iterator over all valid values (without handles).
    pub fn values(&self) -> impl Iterator<Item = &T> {
        self.entries.iter().filter_map(|entry| entry.value.as_ref())
    }

    /// Returns a mutable iterator over all valid values (without handles).
    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> {
        self.entries
            .iter_mut()
            .filter_map(|entry| entry.value.as_mut())
    }
}

// ============================================================================
// Parallel Iteration Support (requires `parallel` feature)
// ============================================================================

#[cfg(feature = "parallel")]
impl<T: Send + Sync> HandleAllocator<T> {
    /// Returns a parallel iterator over all valid values.
    ///
    /// This uses rayon for work-stealing parallelism.
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// use rayon::prelude::*;
    ///
    /// allocator.par_values().for_each(|value| {
    ///     // Process value in parallel
    /// });
    /// ```
    #[must_use]
    pub fn par_values(&self) -> impl rayon::iter::ParallelIterator<Item = &T> {
        use rayon::prelude::*;
        self.entries
            .par_iter()
            .filter_map(|entry| entry.value.as_ref())
    }

    /// Returns a parallel mutable iterator over all valid values.
    pub fn par_values_mut(&mut self) -> impl rayon::iter::ParallelIterator<Item = &mut T> {
        use rayon::prelude::*;
        self.entries
            .par_iter_mut()
            .filter_map(|entry| entry.value.as_mut())
    }
}

// ============================================================================
// Concurrent Handle Allocator (requires `parallel` feature)
// ============================================================================

#[cfg(feature = "parallel")]
mod concurrent {
    use super::{AllocatorEntry, Handle};
    use parking_lot::{Mutex, RwLock};

    /// A thread-safe handle allocator using `parking_lot` primitives.
    ///
    /// This allocator allows concurrent read access and synchronized write access.
    /// Use this when handles need to be shared across threads.
    ///
    /// # Performance Characteristics
    ///
    /// - **Reads** (`get`): Uses `RwLock`, multiple concurrent readers allowed
    /// - **Writes** (`allocate`, `deallocate`): Briefly locks a mutex for the free list
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// use std::sync::Arc;
    ///
    /// let allocator = Arc::new(ConcurrentHandleAllocator::new());
    ///
    /// // Clone for another thread
    /// let alloc_clone = Arc::clone(&allocator);
    /// std::thread::spawn(move || {
    ///     let handle = alloc_clone.allocate(42);
    ///     // ...
    /// });
    /// ```
    #[derive(Debug)]
    pub struct ConcurrentHandleAllocator<T> {
        entries: RwLock<Vec<AllocatorEntry<T>>>,
        free_list: Mutex<Vec<u32>>,
    }

    impl<T> Default for ConcurrentHandleAllocator<T> {
        fn default() -> Self {
            Self::new()
        }
    }

    impl<T> ConcurrentHandleAllocator<T> {
        /// Creates a new empty concurrent allocator.
        #[must_use]
        pub fn new() -> Self {
            Self {
                entries: RwLock::new(Vec::new()),
                free_list: Mutex::new(Vec::new()),
            }
        }

        /// Creates a concurrent allocator with pre-allocated capacity.
        #[must_use]
        pub fn with_capacity(capacity: usize) -> Self {
            Self {
                entries: RwLock::new(Vec::with_capacity(capacity)),
                free_list: Mutex::new(Vec::new()),
            }
        }

        /// Allocates a handle for the given value.
        ///
        /// This operation briefly locks the free list and entries for writing.
        pub fn allocate(&self, value: T) -> Handle<T> {
            let mut free_list = self.free_list.lock();

            if let Some(index) = free_list.pop() {
                let mut entries = self.entries.write();
                let entry = &mut entries[index as usize];
                entry.value = Some(value);
                Handle::new(index, entry.generation)
            } else {
                let mut entries = self.entries.write();
                let index = entries.len() as u32;
                entries.push(AllocatorEntry {
                    value: Some(value),
                    generation: 0,
                });
                Handle::new(index, 0)
            }
        }

        /// Deallocates a handle, returning the value if the handle was valid.
        pub fn deallocate(&self, handle: Handle<T>) -> Option<T> {
            let index = handle.index as usize;

            let mut entries = self.entries.write();
            if index >= entries.len() {
                return None;
            }

            let entry = &mut entries[index];
            if entry.generation != handle.generation {
                return None;
            }

            let value = entry.value.take();
            if value.is_some() {
                entry.generation = entry.generation.wrapping_add(1);
                drop(entries); // Release write lock before acquiring mutex
                self.free_list.lock().push(handle.index);
            }
            value
        }

        /// Gets a reference to the value, if the handle is valid.
        ///
        /// This operation takes a read lock and returns a guard.
        #[must_use]
        pub fn get(&self, handle: Handle<T>) -> Option<ValueRef<'_, T>> {
            let index = handle.index as usize;
            let entries = self.entries.read();

            if index >= entries.len() {
                return None;
            }

            if entries[index].generation != handle.generation {
                return None;
            }

            entries[index].value.as_ref()?;

            Some(ValueRef {
                guard: entries,
                index,
            })
        }

        /// Checks if a handle is valid.
        #[must_use]
        pub fn is_valid(&self, handle: Handle<T>) -> bool {
            let index = handle.index as usize;
            let entries = self.entries.read();

            if index >= entries.len() {
                return false;
            }

            let entry = &entries[index];
            entry.generation == handle.generation && entry.value.is_some()
        }

        /// Returns the number of allocated handles.
        #[must_use]
        pub fn len(&self) -> usize {
            let entries = self.entries.read();
            let free_list = self.free_list.lock();
            entries.len() - free_list.len()
        }

        /// Returns true if no handles are allocated.
        #[must_use]
        pub fn is_empty(&self) -> bool {
            self.len() == 0
        }

        /// Clears all entries, deallocating all handles.
        pub fn clear(&self) {
            let mut entries = self.entries.write();
            let mut free_list = self.free_list.lock();
            entries.clear();
            free_list.clear();
        }
    }

    /// A guard that holds a read lock and provides access to a value.
    pub struct ValueRef<'a, T> {
        guard: parking_lot::RwLockReadGuard<'a, Vec<AllocatorEntry<T>>>,
        index: usize,
    }

    impl<T> std::ops::Deref for ValueRef<'_, T> {
        type Target = T;

        fn deref(&self) -> &Self::Target {
            // SAFETY: We verified the value exists before creating this guard
            self.guard[self.index].value.as_ref().unwrap()
        }
    }
}

#[cfg(feature = "parallel")]
pub use concurrent::ConcurrentHandleAllocator;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_handle_creation() {
        let handle: Handle<i32> = Handle::new(0, 0);
        assert_eq!(handle.index(), 0);
        assert_eq!(handle.generation(), 0);
    }

    #[test]
    fn test_handle_dangling() {
        let handle: Handle<i32> = Handle::dangling();
        assert!(handle.is_dangling());
    }

    #[test]
    fn test_handle_default() {
        let handle: Handle<i32> = Handle::default();
        assert!(handle.is_dangling());
    }

    #[test]
    fn test_handle_equality() {
        let h1: Handle<i32> = Handle::new(1, 2);
        let h2: Handle<i32> = Handle::new(1, 2);
        let h3: Handle<i32> = Handle::new(1, 3);

        assert_eq!(h1, h2);
        assert_ne!(h1, h3);
    }

    #[test]
    fn test_handle_copy() {
        let h1: Handle<i32> = Handle::new(1, 2);
        let h2 = h1;
        assert_eq!(h1, h2);
    }

    #[test]
    fn test_allocator_allocate() {
        let mut alloc = HandleAllocator::new();
        let handle = alloc.allocate(42);

        assert_eq!(handle.index(), 0);
        assert_eq!(handle.generation(), 0);
        assert_eq!(alloc.len(), 1);
    }

    #[test]
    fn test_allocator_get() {
        let mut alloc = HandleAllocator::new();
        let handle = alloc.allocate(42);

        assert_eq!(alloc.get(handle), Some(&42));
    }

    #[test]
    fn test_allocator_get_mut() {
        let mut alloc = HandleAllocator::new();
        let handle = alloc.allocate(42);

        if let Some(value) = alloc.get_mut(handle) {
            *value = 100;
        }

        assert_eq!(alloc.get(handle), Some(&100));
    }

    #[test]
    fn test_allocator_deallocate() {
        let mut alloc = HandleAllocator::new();
        let handle = alloc.allocate(42);

        let value = alloc.deallocate(handle);
        assert_eq!(value, Some(42));
        assert_eq!(alloc.len(), 0);
    }

    #[test]
    fn test_allocator_stale_handle() {
        let mut alloc = HandleAllocator::new();
        let handle1 = alloc.allocate(42);
        alloc.deallocate(handle1);

        // Stale handle should not be valid
        assert!(!alloc.is_valid(handle1));
        assert_eq!(alloc.get(handle1), None);
    }

    #[test]
    fn test_allocator_reuse_slot() {
        let mut alloc = HandleAllocator::new();
        let handle1 = alloc.allocate(42);
        alloc.deallocate(handle1);
        let handle2 = alloc.allocate(100);

        // Same index, different generation
        assert_eq!(handle2.index(), handle1.index());
        assert_eq!(handle2.generation(), handle1.generation() + 1);

        // Old handle invalid, new handle valid
        assert!(!alloc.is_valid(handle1));
        assert!(alloc.is_valid(handle2));
        assert_eq!(alloc.get(handle2), Some(&100));
    }

    #[test]
    fn test_allocator_multiple_allocations() {
        let mut alloc = HandleAllocator::new();
        let h1 = alloc.allocate(1);
        let h2 = alloc.allocate(2);
        let h3 = alloc.allocate(3);

        assert_eq!(alloc.len(), 3);
        assert_eq!(alloc.get(h1), Some(&1));
        assert_eq!(alloc.get(h2), Some(&2));
        assert_eq!(alloc.get(h3), Some(&3));
    }

    #[test]
    fn test_allocator_deallocate_middle() {
        let mut alloc = HandleAllocator::new();
        let h1 = alloc.allocate(1);
        let h2 = alloc.allocate(2);
        let h3 = alloc.allocate(3);

        alloc.deallocate(h2);

        assert!(alloc.is_valid(h1));
        assert!(!alloc.is_valid(h2));
        assert!(alloc.is_valid(h3));
        assert_eq!(alloc.len(), 2);
    }

    #[test]
    fn test_allocator_double_deallocate() {
        let mut alloc = HandleAllocator::new();
        let handle = alloc.allocate(42);

        assert_eq!(alloc.deallocate(handle), Some(42));
        assert_eq!(alloc.deallocate(handle), None);
    }

    #[test]
    fn test_allocator_invalid_handle() {
        let alloc: HandleAllocator<i32> = HandleAllocator::new();
        let invalid = Handle::new(999, 0);

        assert!(!alloc.is_valid(invalid));
        assert_eq!(alloc.get(invalid), None);
    }

    #[test]
    fn test_allocator_clear() {
        let mut alloc = HandleAllocator::new();
        let _ = alloc.allocate(1);
        let _ = alloc.allocate(2);
        let _ = alloc.allocate(3);

        alloc.clear();

        assert!(alloc.is_empty());
        assert_eq!(alloc.len(), 0);
    }

    #[test]
    fn test_allocator_iter() {
        let mut alloc = HandleAllocator::new();
        let h1 = alloc.allocate(1);
        let _h2 = alloc.allocate(2);
        let h3 = alloc.allocate(3);

        alloc.deallocate(h1);

        let values: Vec<_> = alloc.iter().map(|(_, v)| *v).collect();
        assert_eq!(values.len(), 2);
        assert!(values.contains(&2));
        assert!(values.contains(&3));
        assert!(!values.contains(&1));

        // Check that we can get the handles back
        for (handle, _) in alloc.iter() {
            assert!(alloc.is_valid(handle));
            // h3 should still be valid
            if handle == h3 {
                assert_eq!(alloc.get(handle), Some(&3));
            }
        }
    }

    #[test]
    fn test_allocator_iter_mut() {
        let mut alloc = HandleAllocator::new();
        let _ = alloc.allocate(1);
        let _ = alloc.allocate(2);
        let _ = alloc.allocate(3);

        for (_, value) in alloc.iter_mut() {
            *value *= 10;
        }

        let values: Vec<_> = alloc.iter().map(|(_, v)| *v).collect();
        assert!(values.contains(&10));
        assert!(values.contains(&20));
        assert!(values.contains(&30));
    }

    #[test]
    fn test_allocator_with_capacity() {
        let alloc: HandleAllocator<i32> = HandleAllocator::with_capacity(100);
        assert!(alloc.capacity() >= 100);
        assert!(alloc.is_empty());
    }

    #[test]
    fn test_handle_hash() {
        use std::collections::HashSet;

        let mut set = HashSet::new();
        let h1: Handle<i32> = Handle::new(1, 0);
        let h2: Handle<i32> = Handle::new(2, 0);
        let h3: Handle<i32> = Handle::new(1, 0);

        set.insert(h1);
        set.insert(h2);
        set.insert(h3); // Same as h1

        assert_eq!(set.len(), 2);
    }

    #[test]
    fn test_values_iterator() {
        let mut alloc = HandleAllocator::new();
        let _ = alloc.allocate(1);
        let h2 = alloc.allocate(2);
        let _ = alloc.allocate(3);

        alloc.deallocate(h2);

        let values: Vec<_> = alloc.values().copied().collect();
        assert_eq!(values.len(), 2);
        assert!(values.contains(&1));
        assert!(values.contains(&3));
        assert!(!values.contains(&2));
    }
}

#[cfg(all(test, feature = "parallel"))]
mod parallel_tests {
    use super::*;
    use rayon::prelude::*;

    #[test]
    fn test_par_values() {
        let mut alloc = HandleAllocator::new();
        for i in 0..1000 {
            let _ = alloc.allocate(i);
        }

        let sum: i32 = alloc.par_values().sum();
        assert_eq!(sum, (0..1000).sum());
    }

    #[test]
    fn test_par_values_mut() {
        let mut alloc = HandleAllocator::new();
        for i in 0..100 {
            let _ = alloc.allocate(i);
        }

        alloc.par_values_mut().for_each(|v| *v *= 2);

        let sum: i32 = alloc.values().copied().sum();
        assert_eq!(sum, (0..100).map(|i| i * 2).sum());
    }

    #[test]
    fn test_concurrent_allocator_basic() {
        let alloc = ConcurrentHandleAllocator::new();
        let h1 = alloc.allocate(42);
        let h2 = alloc.allocate(100);

        assert!(alloc.is_valid(h1));
        assert!(alloc.is_valid(h2));
        assert_eq!(alloc.len(), 2);

        assert_eq!(*alloc.get(h1).unwrap(), 42);
        assert_eq!(*alloc.get(h2).unwrap(), 100);
    }

    #[test]
    fn test_concurrent_allocator_deallocate() {
        let alloc = ConcurrentHandleAllocator::new();
        let h1 = alloc.allocate(42);

        assert_eq!(alloc.deallocate(h1), Some(42));
        assert!(!alloc.is_valid(h1));
        assert!(alloc.is_empty());
    }

    #[test]
    fn test_concurrent_allocator_stale_handle() {
        let alloc = ConcurrentHandleAllocator::new();
        let h1 = alloc.allocate(42);
        alloc.deallocate(h1);
        let h2 = alloc.allocate(100);

        assert!(!alloc.is_valid(h1));
        assert!(alloc.is_valid(h2));
        assert_eq!(h2.index(), h1.index());
        assert_ne!(h2.generation(), h1.generation());
    }

    #[test]
    fn test_concurrent_allocator_threaded() {
        use std::sync::Arc;
        use std::thread;

        let alloc = Arc::new(ConcurrentHandleAllocator::new());
        let mut handles = Vec::new();

        // Spawn threads that allocate
        let threads: Vec<_> = (0..4)
            .map(|t| {
                let alloc = Arc::clone(&alloc);
                thread::spawn(move || {
                    let mut local_handles = Vec::new();
                    for i in 0..100 {
                        local_handles.push(alloc.allocate(t * 100 + i));
                    }
                    local_handles
                })
            })
            .collect();

        for t in threads {
            handles.extend(t.join().unwrap());
        }

        assert_eq!(alloc.len(), 400);

        // All handles should be valid
        for handle in &handles {
            assert!(alloc.is_valid(*handle));
        }
    }
}