robinxx_map 0.1.0

//! Low-level `RawTable` implementation: probing, insert, erase, resize, and `DfH` logic.
//!
//! Contains all `unsafe` block invariants for index masking, prefetching, and
//! contiguous `SoA` memory manipulation. Public API surface is strictly safe and
//! confined to this module's internal boundaries.
//!
//! # Memory Layout
//! ```text
//! [ Meta(u8) | Padding... | Keys(K) | Padding... | Values(V) | Padding... ]
//! ^ 64B aligned
//! ```
//! Each section is padded to 64-byte boundaries to guarantee SIMD-friendly stride
//! and cache-line alignment for auto-vectorized probing loops.
//!
//! # Robin Hood Displacement
//! Entries with higher Distance from Home (`DfH`) values are prioritized during probing.
//! When inserting, if a slot with lower `DfH` is encountered, the new entry displaces it
//! and continues probing with the displaced entry. This bounds worst-case probe chains.
//!
//! # Safety Guarantees
//! - All public methods are safe; `unsafe` is confined to allocation, pointer arithmetic,
//!   and memory initialization with documented invariants.
//! - Keys/Values are only accessed where `meta[i] > 0`, guaranteeing initialized memory.
//! - Drop semantics respect Rust move semantics: initialized slots are dropped before
//!   deallocation.

use crate::hash::RobinHoodKey;
use crate::memory;
use core::marker::PhantomData;
use core::mem;
use core::ptr::{self, NonNull};

/// Raw, unguarded open-addressing hash table using Robin Hood displacement.
///
/// # Summary
/// Low-level hash table with Robin Hood probing, `SoA` layout, and manual memory management.
///
/// # Description
/// `RawTable` implements an open-addressing hash table with linear probing and
/// Distance from Home (`DfH`) tracking. Keys and values are stored in parallel
/// 64-byte aligned arrays (Structure of Arrays) for cache-friendly access and
/// auto-vectorization potential.
///
/// Insertion uses Robin Hood displacement: entries with higher `DfH` values are
/// prioritized, and new entries displace those with lower `DfH` to bound probe chains.
/// Deletion uses backward shift to eliminate tombstones and maintain probe continuity.
///
/// # Invariants
/// - `capacity` is a power of two and `> 0`.
/// - `mask == capacity - 1` for bitwise index masking.
/// - `base_ptr`, `meta_ptr`, `keys_ptr`, `vals_ptr` point to valid, aligned, SoA-allocated memory.
/// - `meta[i] == 0` denotes an empty slot. `meta[i] > 0` denotes occupied with `DfH = meta[i] - 1`.
/// - `size <= capacity * 0.8` before `insert` triggers resize.
/// - Keys/Values are only initialized where `meta[i] > 0`.
///
/// # Examples
/// ```
/// use robinxx_map::hash::RobinHoodKey;
/// use robinxx_map::table::RawTable;
///
/// // RawTable requires K: RobinHoodKey + PartialEq
/// let mut table: RawTable<u64, String> = RawTable::with_capacity(8);
/// assert!(table.insert(42u64, String::from("answer")));
/// assert_eq!(table.get(&42u64), Some(&String::from("answer")));
/// assert!(!table.insert(42u64, String::from("duplicate"))); // Key exists
/// assert!(table.remove(&42u64));
/// assert_eq!(table.get(&42u64), None);
/// ```
///
/// # Panics
/// - `with_capacity` panics if allocation fails (OOM) via `handle_alloc_error`.
/// - `insert` panics if resize allocation fails.
/// - All methods assume `K: PartialEq` for key comparison; violating this at call site
///   causes undefined behavior (enforced by trait bounds on `impl` block).
///
/// # Errors
/// Not applicable. Public methods return `bool` or `Option` for infallible semantics.
/// Allocation failures panic via `handle_alloc_error` per `no_std` conventions.
///
/// # Safety
/// - `unsafe impl Send/Sync` is sound because `RawTable` owns all data and uses
///   global allocator; thread-safety is enforced at the `RobinHoodMap` layer.
/// - `Drop` iterates only where `meta[i] > 0`, guaranteeing initialized memory for
///   `ptr::drop_in_place`.
/// - Pointer arithmetic is bounded by `mask` and `capacity`; indices are always
///   valid due to power-of-two capacity and bitwise masking.
///
/// # See Also
/// - [`RobinHoodMap`](crate::map::RobinHoodMap) for the safe, public API wrapper.
/// - [`memory`] for `SoA` allocation primitives.
/// - [`hash::RobinHoodKey`](crate::hash::RobinHoodKey) for the hashing trait.
pub struct RawTable<K, V> {
    /// Base pointer to the allocated `SoA` memory block.
    base_ptr: NonNull<u8>,
    /// Pointer to the metadata array (`DfH` values).
    pub(crate) meta_ptr: *mut u8,
    /// Pointer to the keys array.
    pub(crate) keys_ptr: *mut K,
    /// Pointer to the values array.
    pub(crate) vals_ptr: *mut V,
    /// Total allocated slot count (power of two).
    pub(crate) capacity: usize,
    /// Number of occupied slots.
    size: usize,
    /// Bitmask for index wrapping: `mask == capacity - 1`.
    mask: usize,
    /// Byte offset from `base_ptr` to the keys array.
    keys_offset: usize,
    /// Byte offset from `base_ptr` to the values array.
    vals_offset: usize,
    /// Phantom marker for variance and drop-check.
    _marker: PhantomData<(K, V)>,
}

// SAFETY: `RawTable` manually manages `Send`/`Sync` via owned data and global allocator.
// No interior mutability; all mutation requires `&mut self`. Thread-safety is enforced
// at the `RobinHoodMap` layer via `SpinMutex`.
unsafe impl<K: Send, V: Send> Send for RawTable<K, V> {}
unsafe impl<K: Sync, V: Sync> Sync for RawTable<K, V> {}

// Trait bounds added here for methods that require key comparison and hashing.
// Struct itself remains unbounded to allow `Drop` and basic operations without constraints.
impl<K: RobinHoodKey + PartialEq, V> RawTable<K, V> {
    /// Allocates an empty `RawTable` with default capacity.
    ///
    /// # Summary
    /// Creates a new table with initial capacity of 16 slots.
    ///
    /// # Description
    /// Convenience constructor that delegates to `with_capacity(16)`. Suitable for
    /// small tables or when exact capacity is unknown upfront.
    ///
    /// # Examples
    /// ```ignore
    /// use robinxx_map::table::RawTable;
    ///
    /// let table: RawTable<u32, String> = RawTable::new();
    /// assert_eq!(table.capacity(), 16);
    /// assert!(table.is_empty());
    /// ```
    ///
    /// # Panics
    /// Panics if allocation fails (OOM) via `handle_alloc_error`.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Not applicable. Public safe constructor.
    ///
    /// # See Also
    /// - [`with_capacity`](Self::with_capacity) for custom initial capacity.
    #[inline]
    #[must_use]
    pub fn new() -> Self {
        Self::with_capacity(16)
    }

    /// Allocates an empty `RawTable` with at least the specified capacity.
    ///
    /// # Summary
    /// Creates a new table rounded up to the nearest power-of-two capacity.
    ///
    /// # Description
    /// Allocates a `SoA` memory block with capacity rounded up to the nearest power
    /// of two. Metadata is zero-initialized; keys/values regions are uninitialized
    /// and will be initialized on first insert.
    ///
    /// # Examples
    /// ```ignore
    /// use robinxx_map::table::RawTable;
    ///
    /// let table: RawTable<&str, i32> = RawTable::with_capacity(100);
    /// assert_eq!(table.capacity(), 128); // Rounded up to power of two
    /// ```
    ///
    /// # Panics
    /// Panics if allocation fails (OOM) via `handle_alloc_error`.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Caller must ensure `K` and `V` satisfy `RobinHoodKey + PartialEq` at call site.
    /// The returned table is valid for all safe operations defined in this `impl` block.
    ///
    /// # See Also
    /// - [`new`](Self::new) for default capacity.
    /// - [`reserve`](Self::reserve) for post-construction capacity adjustment.
    #[must_use]
    pub fn with_capacity(mut capacity: usize) -> Self {
        if capacity == 0 {
            capacity = 1;
        }
        let capacity = capacity.next_power_of_two();
        let k_size = mem::size_of::<K>();
        let v_size = mem::size_of::<V>();
        // SAFETY: capacity is power-of-two > 0. sizes are compile-time constants.
        // `allocate_block` returns a valid, aligned, zero-initialized metadata region.
        let base = unsafe { memory::allocate_block(capacity, k_size, v_size) };
        let (_, keys_offset, vals_offset) = memory::calc_layout(capacity, k_size, v_size);
        // SAFETY: layout matches allocation parameters, pointers derived from valid base.
        // Offsets are computed by `calc_layout` and guaranteed within bounds.
        let (meta_ptr, keys_ptr, vals_ptr) =
            unsafe { memory::get_array_ptrs::<K, V>(base, keys_offset, vals_offset) };
        Self {
            base_ptr: base,
            meta_ptr,
            keys_ptr,
            vals_ptr,
            capacity,
            size: 0,
            mask: capacity - 1,
            keys_offset,
            vals_offset,
            _marker: PhantomData,
        }
    }

    /// Returns the number of occupied slots.
    ///
    /// # Summary
    /// Retrieves the current element count in O(1) time.
    ///
    /// # Description
    /// Returns the internal `size` counter, which is maintained on every insert/remove.
    /// Does not traverse the table; constant-time operation.
    ///
    /// # Examples
    /// ```ignore
    /// use robinxx_map::table::RawTable;
    ///
    /// let mut table: RawTable<u64, bool> = RawTable::new();
    /// assert_eq!(table.size(), 0);
    /// table.insert(1u64, true);
    /// assert_eq!(table.size(), 1);
    /// ```
    ///
    /// # Panics
    /// Never panics.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Not applicable. Read-only access to internal counter.
    ///
    /// # See Also
    /// - [`capacity`](Self::capacity) for total slot count.
    /// - [`is_empty`](Self::is_empty) for boolean emptiness check.
    #[inline]
    pub(crate) fn size(&self) -> usize {
        self.size
    }

    /// Returns the total allocated capacity.
    ///
    /// # Summary
    /// Retrieves the total slot count (power of two) in O(1) time.
    ///
    /// # Description
    /// Returns the `capacity` field, which is always a power of two due to
    /// `next_power_of_two` rounding in constructors and `resize`.
    ///
    /// # Examples
    /// ```ignore
    /// use robinxx_map::table::RawTable;
    ///
    /// let table: RawTable<String, Vec<u8>> = RawTable::with_capacity(50);
    /// assert_eq!(table.capacity(), 64);
    /// ```
    ///
    /// # Panics
    /// Never panics.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Not applicable. Read-only access to internal field.
    ///
    /// # See Also
    /// - [`size`](Self::size) for occupied slot count.
    /// - [`reserve`](Self::reserve) to ensure minimum capacity.
    #[inline]
    pub(crate) fn capacity(&self) -> usize {
        self.capacity
    }

    /// Checks if the table is empty.
    ///
    /// # Summary
    /// Returns `true` if no elements are stored.
    ///
    /// # Description
    /// Convenience method equivalent to `size() == 0`. Useful for conditional logic
    /// without exposing the internal counter directly.
    ///
    /// # Examples
    /// ```ignore
    /// use robinxx_map::table::RawTable;
    ///
    /// let mut table: RawTable<i32, f64> = RawTable::new();
    /// assert!(table.is_empty());
    /// table.insert(42, 3.14);
    /// assert!(!table.is_empty());
    /// ```
    ///
    /// # Panics
    /// Never panics.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Not applicable.
    ///
    /// # See Also
    /// - [`size`](Self::size) for exact element count.
    #[inline]
    pub(crate) fn is_empty(&self) -> bool {
        self.size == 0
    }

    /// Inserts a key-value pair using Robin Hood displacement.
    ///
    /// # Summary
    /// Stores a key-value pair; returns `true` if newly inserted, `false` if duplicate.
    ///
    /// # Description
    /// Computes the key's xxHash3 digest, probes linearly with `DfH` tracking, and
    /// displaces entries with lower `DfH` to bound probe chains. Triggers resize at
    /// 80% load factor to maintain amortized O(1) performance.
    ///
    /// Duplicate keys are not updated; the existing value is preserved and `false`
    /// is returned. To update, use `get_mut` followed by in-place mutation.
    ///
    /// # Examples
    /// ```
    /// use robinxx_map::table::RawTable;
    ///
    /// let mut table: RawTable<&str, i32> = RawTable::new();
    /// assert!(table.insert("key", 100));      // Insert new
    /// assert!(!table.insert("key", 200));     // Duplicate, no update
    /// assert_eq!(table.get(&"key"), Some(&100)); // Original value preserved
    /// ```
    ///
    /// # Panics
    /// Panics if allocation fails during resize (OOM) via `handle_alloc_error`.
    ///
    /// # Errors
    /// Not applicable. Returns `bool` for infallible semantics.
    ///
    /// # Safety
    /// Caller must ensure `K: PartialEq` for correct duplicate detection.
    /// The table maintains ownership of inserted keys/values; dropping the table
    /// will drop all stored elements.
    ///
    /// # See Also
    /// - [`get`](Self::get) for immutable lookup.
    /// - [`get_mut`](Self::get_mut) for mutable lookup and in-place update.
    /// - [`remove`](Self::remove) for deletion.
    /// - [`reserve`](Self::reserve) to pre-allocate capacity and avoid mid-insert resize.
    #[inline]
    pub fn insert(&mut self, key: K, value: V) -> bool {
        if self.size * 5 >= self.capacity * 4 {
            self.resize();
        }

        let hash = key.hash_xxh3();
        let mut idx = usize::try_from(hash).unwrap() & self.mask;
        let mut dfh: u8 = 0;
        let mut current_key = key;
        let mut current_val = value;

        unsafe {
            loop {
                let meta_val = *self.meta_ptr.add(idx);
                if meta_val == 0 {
                    ptr::write(self.keys_ptr.add(idx), current_key);
                    ptr::write(self.vals_ptr.add(idx), current_val);
                    *self.meta_ptr.add(idx) = dfh + 1;
                    self.size += 1;
                    return true;
                }

                if meta_val < dfh + 1 {
                    let old_key = ptr::replace(self.keys_ptr.add(idx), current_key);
                    let old_val = ptr::replace(self.vals_ptr.add(idx), current_val);
                    current_key = old_key;
                    current_val = old_val;
                    // Record the new entry's DfH at this slot.
                    *self.meta_ptr.add(idx) = dfh + 1;
                    // Displaced entry had DfH = meta_val - 1 here; at next slot it is meta_val.
                    // After dfh += 1 below, dfh will equal meta_val. ✓
                    dfh = meta_val - 1;
                } else if meta_val == dfh + 1 && *self.keys_ptr.add(idx) == current_key {
                    drop(current_key);
                    drop(current_val);
                    return false;
                }

                idx = (idx + 1) & self.mask;
                dfh = dfh.checked_add(1).expect(
                    "DfH overflow: probe chain exceeded 255. \
                    This indicates a hash distribution problem or adversarial input.",
                );
            }
        }
    }

    /// Finds an immutable reference to the value associated with `key`.
    ///
    /// # Summary
    /// Returns `Some(&V)` if key exists, `None` otherwise.
    ///
    /// # Description
    /// Probes linearly using the key's xxHash3 digest and `DfH` bounds. Stops at the
    /// first matching key or when an empty slot or `DfH` violation is encountered.
    ///
    /// # Examples
    /// ```
    /// use robinxx_map::table::RawTable;
    ///
    /// let mut table: RawTable<u64, String> = RawTable::new();
    /// table.insert(42u64, String::from("answer"));
    /// assert_eq!(table.get(&42u64), Some(&String::from("answer")));
    /// assert_eq!(table.get(&99u64), None);
    /// ```
    ///
    /// # Panics
    /// Never panics.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Returned reference is valid for the lifetime of `&self`. Caller must not
    /// mutate the table through other means while the reference is held (aliasing
    /// rules enforced by Rust borrow checker).
    ///
    /// # See Also
    /// - [`get_mut`](Self::get_mut) for mutable access.
    /// - [`insert`](Self::insert) to add new entries.
    #[inline]
    pub fn get(&self, key: &K) -> Option<&V> {
        let hash = key.hash_xxh3();
        let mut idx = usize::try_from(hash).unwrap() & self.mask;
        let mut dfh: u8 = 0;
        // SAFETY: probing loop bounded by empty slot or DfH < current dfh.
        // Reads only initialized keys/values where meta[i] > 0.
        unsafe {
            loop {
                let meta_val = *self.meta_ptr.add(idx);
                if meta_val == 0 || meta_val < dfh.saturating_add(1) {
                    return None;
                }
                if *self.keys_ptr.add(idx) == *key {
                    return Some(&*self.vals_ptr.add(idx));
                }
                idx = (idx + 1) & self.mask;
                dfh = dfh.checked_add(1).expect(
                    "DfH overflow: probe chain exceeded 255. \
                    This indicates a hash distribution problem or adversarial input.",
                );
            }
        }
    }

    /// Finds a mutable reference to the value associated with `key`.
    ///
    /// # Summary
    /// Returns `Some(&mut V)` if key exists, `None` otherwise.
    ///
    /// # Description
    /// Identical to `get` but yields a mutable reference for in-place modification.
    /// Useful for updating values without re-insertion.
    ///
    /// # Examples
    /// ```
    /// use robinxx_map::table::RawTable;
    ///
    /// let mut table: RawTable<String, Vec<u8>> = RawTable::new();
    /// table.insert(String::from("data"), vec![1, 2, 3]);
    /// if let Some(v) = table.get_mut(&String::from("data")) {
    ///     v.push(4);
    /// }
    /// assert_eq!(table.get(&String::from("data")), Some(&vec![1, 2, 3, 4]));
    /// ```
    ///
    /// # Panics
    /// Never panics.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Returned mutable reference is valid for the lifetime of `&mut self`.
    /// Caller must not access the same key through other references while the
    /// mutable borrow is active (enforced by Rust borrow checker).
    ///
    /// # See Also
    /// - [`get`](Self::get) for immutable access.
    /// - [`insert`](Self::insert) to add new entries.
    #[inline]
    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        let hash = key.hash_xxh3();
        let mut idx = usize::try_from(hash).unwrap() & self.mask;
        let mut dfh: u8 = 0;
        // SAFETY: identical to `get`, but yields `&mut V` for in-place mutation.
        unsafe {
            loop {
                let meta_val = *self.meta_ptr.add(idx);
                if meta_val == 0 || meta_val < dfh.saturating_add(1) {
                    return None;
                }
                if *self.keys_ptr.add(idx) == *key {
                    return Some(&mut *self.vals_ptr.add(idx));
                }
                idx = (idx + 1) & self.mask;
                dfh = dfh.checked_add(1).expect(
                    "DfH overflow: probe chain exceeded 255. \
                    This indicates a hash distribution problem or adversarial input.",
                );
            }
        }
    }

    /// Removes a key-value pair using `DfH` backward shift deletion.
    ///
    /// # Summary
    /// Deletes a key if present; returns `true` on success, `false` if absent.
    ///
    /// # Description
    /// Probes to locate the key, then shifts subsequent entries backward to fill
    /// the gap, decrementing their `DfH` values. This eliminates tombstones and
    /// maintains probe continuity for future lookups.
    ///
    /// # Examples
    /// ```
    /// use robinxx_map::table::RawTable;
    ///
    /// let mut table: RawTable<i32, bool> = RawTable::new();
    /// table.insert(10, true);
    /// assert!(table.remove(&10));   // Success
    /// assert!(!table.remove(&10));  // Already removed
    /// assert_eq!(table.get(&10), None);
    /// ```
    ///
    /// # Panics
    /// Never panics.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Caller must ensure `K: PartialEq` for correct key matching.
    /// Dropped keys/values are deallocated via `ptr::drop_in_place`; no double-drop
    /// occurs due to `meta[i]` tracking.
    ///
    /// # See Also
    /// - [`insert`](Self::insert) to add entries.
    /// - [`clear`](Self::clear) to remove all entries at once.
    #[inline]
    pub fn remove(&mut self, key: &K) -> bool {
        let hash = key.hash_xxh3();
        let mut idx = usize::try_from(hash).unwrap() & self.mask;
        let mut dfh: u8 = 0;
        // SAFETY: probing finds occupied slot or terminates early.
        unsafe {
            loop {
                let meta_val = *self.meta_ptr.add(idx);
                if meta_val == 0 || meta_val < dfh {
                    return false;
                }
                if *self.keys_ptr.add(idx) == *key {
                    break;
                }
                idx = (idx + 1) & self.mask;
                dfh = dfh.checked_add(1).expect(
                    "DfH overflow: probe chain exceeded 255. \
                    This indicates a hash distribution problem or adversarial input.",
                );
            }
            // Drop the element being removed before shifting over it.
            ptr::drop_in_place(self.keys_ptr.add(idx));
            ptr::drop_in_place(self.vals_ptr.add(idx));
            // Backward shift loop: pull later cluster entries one slot back.
            let mut shift_idx = idx;
            loop {
                let next = (shift_idx + 1) & self.mask;
                let next_meta = *self.meta_ptr.add(next);
                if next_meta <= 1 {
                    // next is empty (0) or at its home slot (DfH=0); nothing left to shift.
                    break;
                }
                // Shift next into current; ownership moves — no extra drop needed.
                ptr::copy(self.keys_ptr.add(next), self.keys_ptr.add(shift_idx), 1);
                ptr::copy(self.vals_ptr.add(next), self.vals_ptr.add(shift_idx), 1);
                *self.meta_ptr.add(shift_idx) = next_meta - 1;
                shift_idx = next;
            }
            *self.meta_ptr.add(shift_idx) = 0;
            self.size -= 1;
            true
        }
    }

    /// Clears all elements, dropping keys/values but retaining capacity.
    ///
    /// # Summary
    /// Removes all entries and resets size to zero; allocation is preserved.
    ///
    /// # Description
    /// Iterates over all slots, dropping initialized keys/values where `meta[i] > 0`,
    /// then resets metadata to zero. Capacity and allocated memory are retained for
    /// reuse, avoiding reallocation on subsequent inserts.
    ///
    /// # Examples
    /// ```ignore
    /// use robinxx_map::table::RawTable;
    ///
    /// let mut table: RawTable<u64, String> = RawTable::with_capacity(32);
    /// table.insert(1, String::from("one"));
    /// table.insert(2, String::from("two"));
    /// assert_eq!(table.size(), 2);
    /// table.clear();
    /// assert_eq!(table.size(), 0);
    /// assert_eq!(table.capacity(), 32); // Capacity unchanged
    /// ```
    ///
    /// # Panics
    /// Never panics.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// All initialized slots are dropped via `ptr::drop_in_place`; no memory leaks
    /// occur. Metadata reset ensures no stale `DfH` values remain.
    ///
    /// # See Also
    /// - [`remove`](Self::remove) for selective deletion.
    /// - [`reserve`](Self::reserve) to adjust capacity post-clear.
    #[inline]
    pub fn clear(&mut self) {
        // SAFETY: iterates only occupied slots. Drops each, resets meta to 0.
        unsafe {
            for i in 0..self.capacity {
                if *self.meta_ptr.add(i) != 0 {
                    ptr::drop_in_place(self.keys_ptr.add(i));
                    ptr::drop_in_place(self.vals_ptr.add(i));
                    *self.meta_ptr.add(i) = 0;
                }
            }
        }
        self.size = 0;
    }

    /// Reserves additional capacity to accommodate future inserts.
    ///
    /// # Summary
    /// Ensures the table can hold at least `size + additional` elements without resize.
    ///
    /// # Description
    /// If the target capacity exceeds current capacity, rounds up to the nearest
    /// power of two and triggers a resize. No-op if sufficient capacity already exists.
    ///
    /// # Examples
    /// ```ignore
    /// use robinxx_map::table::RawTable;
    ///
    /// let mut table: RawTable<&str, i32> = RawTable::new();
    /// table.reserve(100);
    /// assert!(table.capacity() >= 100);
    /// ```
    ///
    /// # Panics
    /// Panics if allocation fails during resize (OOM).
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Caller should call `reserve` before bulk inserts to avoid mid-operation resize.
    /// All existing references to values are invalidated if resize occurs.
    ///
    /// # See Also
    /// - [`with_capacity`](Self::with_capacity) for initial capacity planning.
    /// - [`insert`](Self::insert) which auto-resizes at 80% load factor.
    pub fn reserve(&mut self, additional: usize) {
        let target = self.size.saturating_add(additional);
        if target * 5 >= self.capacity * 4 {
            let new_cap = (target * 5 / 4).next_power_of_two();
            if new_cap > self.capacity {
                self.resize_to(new_cap);
            }
        }
    }

    /// Doubles capacity and rehashes all elements.
    ///
    /// # Summary
    /// Internal helper to grow the table by a factor of two.
    ///
    /// # Description
    /// Allocates a new `SoA` block with double capacity, re-inserts all existing
    /// elements using Robin Hood probing, then deallocates the old block.
    ///
    /// # Panics
    /// Panics if allocation fails (OOM).
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// All keys/values are moved via `ptr::read`/`ptr::write`; no double-drop occurs.
    /// Old block is deallocated only after successful migration.
    ///
    /// # See Also
    /// - [`resize_to`](Self::resize_to) for exact capacity resize.
    /// - [`insert`](Self::insert) which triggers this at 80% load factor.
    fn resize(&mut self) {
        self.resize_to(self.capacity * 2);
    }

    /// Resizes to exact power-of-two capacity.
    ///
    /// # Summary
    /// Internal helper to resize to a specific power-of-two capacity.
    ///
    /// # Description
    /// Allocates a new block, rehashes all elements, deallocates the old block,
    /// and updates internal pointers. Used by `resize` and `reserve`.
    ///
    /// # Panics
    /// Panics if allocation fails (OOM).
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Caller must ensure `new_capacity` is a power of two and `> current capacity`.
    /// All keys/values are moved safely; old block is deallocated after migration.
    ///
    /// # See Also
    /// - [`resize`](Self::resize) for doubling capacity.
    /// - [`reserve`](Self::reserve) for capacity planning.
    fn resize_to(&mut self, new_capacity: usize) {
        let old_cap = self.capacity;
        let old_base = self.base_ptr;
        let old_meta = self.meta_ptr;
        let old_keys = self.keys_ptr;
        let old_vals = self.vals_ptr;
        let k_size = mem::size_of::<K>();
        let v_size = mem::size_of::<V>();

        let new_base = unsafe { memory::allocate_block(new_capacity, k_size, v_size) };
        let (new_keys_offset, new_vals_offset) = {
            let (_, k_off, v_off) = memory::calc_layout(new_capacity, k_size, v_size);
            (k_off, v_off)
        };
        let (new_meta, new_keys, new_vals) =
            unsafe { memory::get_array_ptrs::<K, V>(new_base, new_keys_offset, new_vals_offset) };

        let mut new_size = 0;
        let new_mask = new_capacity - 1;

        // SAFETY: reads old block, writes new block. No overlap.
        unsafe {
            for i in 0..old_cap {
                if *old_meta.add(i) != 0 {
                    let k = ptr::read(old_keys.add(i));
                    let v = ptr::read(old_vals.add(i));
                    let hash = k.hash_xxh3();
                    let mut idx = usize::try_from(hash).unwrap() & new_mask;
                    let mut dfh: u8 = 0;
                    let mut cur_k = k;
                    let mut cur_v = v;

                    // Robin Hood migration to empty table (no duplicate check needed)
                    loop {
                        let meta_val = *new_meta.add(idx);
                        if meta_val == 0 {
                            ptr::write(new_keys.add(idx), cur_k);
                            ptr::write(new_vals.add(idx), cur_v);
                            *new_meta.add(idx) = dfh + 1;
                            new_size += 1;
                            break;
                        }

                        if meta_val < dfh + 1 {
                            // Displace entry with lower DfH
                            let tk = ptr::replace(new_keys.add(idx), cur_k);
                            let tv = ptr::replace(new_vals.add(idx), cur_v);
                            cur_k = tk;
                            cur_v = tv;
                            // Record cur_k's DfH at this slot so future probes see the right value.
                            *new_meta.add(idx) = dfh + 1;
                            // Displaced item had DfH = meta_val - 1.
                            // We move to next slot, so its DfH becomes (meta_val - 1) + 1 = meta_val.
                            // We set dfh here to meta_val - 1, then increment at loop end.
                            dfh = meta_val - 1;
                        }

                        idx = (idx + 1) & new_mask;
                        dfh = dfh.checked_add(1).expect(
                            "DfH overflow: probe chain exceeded 255. \
                            This indicates a hash distribution problem or adversarial input.",
                        );
                    }
                }
            }
        }

        // Debug invariant: compare against self.size (element count), not old_cap (slot count).
        debug_assert_eq!(new_size, self.size, "Migration lost elements!");

        unsafe {
            memory::deallocate_block(old_base, old_cap, k_size, v_size);
        }

        self.base_ptr = new_base;
        self.meta_ptr = new_meta;
        self.keys_ptr = new_keys;
        self.vals_ptr = new_vals;
        self.capacity = new_capacity;
        self.mask = new_mask;
        self.size = new_size;
        self.keys_offset = new_keys_offset;
        self.vals_offset = new_vals_offset;
    }

    /// Decrements the internal size counter by 1.
    ///
    /// # Summary
    /// Safely reduces the occupied slot count during `Drain` iteration.
    ///
    /// # Description
    /// Used internally by the `Drain` iterator to keep `size` synchronized as
    /// elements are extracted and metadata zeroed.
    ///
    /// # Examples
    /// Internal use only; not exposed in public API.
    ///
    /// # Panics
    /// Never panics.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Caller must ensure that an element was actually removed.
    ///
    /// # See Also
    /// - [`Drain`](crate::iter::Drain)
    #[inline]
    pub(crate) fn decrement_size(&mut self) {
        self.size = self.size.saturating_sub(1);
    }
}

impl<K: RobinHoodKey + PartialEq, V> Default for RawTable<K, V> {
    /// Creates an empty `RawTable` with default capacity.
    ///
    /// # Summary
    /// Implements the `Default` trait for ergonomic construction.
    ///
    /// # Description
    /// Delegates to `RawTable::new()`, providing a default capacity of 16 slots.
    ///
    /// # Examples
    /// ```ignore
    /// use robinxx_map::table::RawTable;
    ///
    /// let table: RawTable<u32, String> = RawTable::default();
    /// assert_eq!(table.capacity(), 16);
    /// ```
    ///
    /// # Panics
    /// Panics if allocation fails (OOM).
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Not applicable.
    ///
    /// # See Also
    /// - [`new`](Self::new) for explicit construction.
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

// Drop impl: No trait bounds on K/V because ptr::drop_in_place is unsafe
// and we manually check initialization via meta[i] > 0.
impl<K, V> Drop for RawTable<K, V> {
    /// Drops all initialized keys/values and deallocates the `SoA` memory block.
    ///
    /// # Summary
    /// Cleans up resources when the table is destroyed.
    ///
    /// # Description
    /// Iterates over all slots, dropping initialized keys/values where `meta[i] > 0`,
    /// then deallocates the entire `SoA` block via `memory::deallocate_block`.
    ///
    /// # Examples
    /// Automatically invoked when `RawTable` goes out of scope.
    ///
    /// # Panics
    /// Never panics. Drop must not unwind.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// - Only slots with `meta[i] > 0` are dropped, guaranteeing initialized memory.
    /// - `base_ptr` is valid and exclusively owned; deallocation occurs exactly once.
    /// - No references to dropped keys/values may outlive this call.
    ///
    /// # See Also
    /// - [`clear`](Self::clear) for manual cleanup without deallocation.
    /// - [`memory::deallocate_block`] for low-level deallocation.
    fn drop(&mut self) {
        // SAFETY: drops all initialized slots before deallocation.
        // We iterate only where meta[i] > 0, guaranteeing initialized memory.
        unsafe {
            for i in 0..self.capacity {
                if *self.meta_ptr.add(i) != 0 {
                    ptr::drop_in_place(self.keys_ptr.add(i));
                    ptr::drop_in_place(self.vals_ptr.add(i));
                }
            }
            // base_ptr is already NonNull<u8>, direct usage is safe.
            memory::deallocate_block(
                self.base_ptr,
                self.capacity,
                mem::size_of::<K>(),
                mem::size_of::<V>(),
            );
        }
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    use alloc::string::String;

    #[test]
    fn test_raw_table_basic_ops() {
        let mut table: RawTable<u32, String> = RawTable::new();
        assert!(table.is_empty());
        assert!(table.insert(1, String::from("one")));
        assert_eq!(table.size(), 1);
        assert_eq!(table.get(&1), Some(&String::from("one")));
        assert!(!table.insert(1, String::from("updated"))); // Duplicate
        assert!(table.remove(&1));
        assert_eq!(table.get(&1), None);
        assert!(table.is_empty());
    }

    #[test]
    fn test_raw_table_resize_chain() {
        let mut table: RawTable<usize, usize> = RawTable::with_capacity(4);
        for i in 0..20 {
            assert!(table.insert(i, i * 10));
        }
        assert!(table.capacity() >= 25);
        for i in 0..20 {
            assert_eq!(table.get(&i), Some(&(i * 10)));
        }
    }

    #[test]
    fn test_raw_table_clear_retains_capacity() {
        let mut table: RawTable<u64, u64> = RawTable::with_capacity(32);
        for i in 0..10 {
            table.insert(i, i);
        }
        let cap_before = table.capacity();
        table.clear();
        assert_eq!(table.size(), 0);
        assert_eq!(table.capacity(), cap_before);
    }
}