//! Filepath: src/leaf.rs
//!
//! Leaf node for [`MassTree`].
//!
//! Leaf nodes store the actual key-value pairs, using a permutation array
//! for logical ordering without data movement.
//!
//! # Storage Modes
//!
//! `LeafNode<S, WIDTH>` is generic over the slot type `S: ValueSlot`:
//!
//! - [`LeafValue<V>`]: Arc-based storage (default mode) - values wrapped in `Arc<V>`
//! - [`LeafValueIndex<V: Copy>`]: Inline storage (index mode) - values stored directly
//!
//! Use the type aliases for convenience:
//! - [`ArcLeafNode<V>`]: Leaf with Arc-based storage
//! - [`InlineLeafNode<V>`]: Leaf with inline storage for `V: Copy`

use std::array as StdArray;
use std::fmt as StdFmt;
use std::marker::PhantomData;
use std::mem as StdMem;
use std::ptr as StdPtr;
use std::sync::Arc;
use std::sync::atomic::{AtomicPtr, AtomicU8, AtomicU64};

use crate::ordering::{CAS_FAILURE, CAS_SUCCESS, READ_ORD, RELAXED, WRITE_ORD};
use seize::{Guard, LocalGuard};

mod freeze;

pub mod cas;
pub mod layer;
pub mod link;

use crate::slot::ValueSlot;
use crate::{nodeversion::NodeVersion, permuter::Permuter, suffix::SuffixBag};

/// Special keylenx value indicating key has a suffix.
pub const KSUF_KEYLENX: u8 = 64;

/// Base keylenx value indicating a layer pointer (>= this means layer).
pub const LAYER_KEYLENX: u8 = 128;

/// Modification state values.
#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ModState {
    /// Node is in insert mode (normal operation).
    Insert = 0,

    /// Node is being removed.
    Remove = 1,

    /// Node's layer has been deleted.
    DeletedLayer = 2,
}

// ============================================================================
//  Split Types
// ============================================================================

/// Result of calculating a split point.
///
/// Contains the logical position where to split and the key that will
/// become the first key of the new (right) leaf.
#[derive(Debug, Clone, Copy)]
pub struct SplitPoint {
    /// Logical position where to split (in post-insert coordinates).
    /// Entries from `pos` to end (in post-insert order) go to new leaf.
    pub pos: usize,

    /// The ikey that will be the first key of the new (right) leaf.
    pub split_ikey: u64,
}

/// Which leaf to insert into after a split.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum InsertTarget {
    /// Insert into the original (left) leaf.
    Left,

    /// Insert into the new (right) leaf.
    Right,
}

/// Result of a leaf split operation.
///
/// Contains the new leaf and information about where to insert.
///
/// # Type Parameters
/// * `S` - The slot type implementing [`ValueSlot`]
/// * `WIDTH` - Node width (number of slots)
#[derive(Debug)]
pub struct LeafSplitResult<S: ValueSlot, const WIDTH: usize = 15> {
    /// The new leaf (right sibling).
    pub new_leaf: Box<LeafNode<S, WIDTH>>,

    /// The split key (first key of new leaf).
    pub split_ikey: u64,

    /// Which leaf the new key should go into.
    pub insert_into: InsertTarget,
}

// ============================================================================
//  Split Point Calculation Functions
// ============================================================================

/// Unit struct for split utilities.
#[derive(Debug)]
pub struct SplitUtils;

impl SplitUtils {
    /// Get the ikey at logical position `i` after the new key is inserted.
    ///
    /// This is critical for correct split point adjustment: we must consider
    /// the post-insert key stream, not just existing keys.
    ///
    /// # Arguments
    /// * `leaf` - The leaf being split
    /// * `i` - Logical position in post-insert order
    /// * `insert_pos` - Where the new key will be inserted
    /// * `insert_ikey` - The ikey of the new key
    fn ikey_after_insert<S: ValueSlot, const WIDTH: usize>(
        leaf: &LeafNode<S, WIDTH>,
        i: usize,
        insert_pos: usize,
        insert_ikey: u64,
    ) -> u64 {
        use std::cmp::Ordering;

        let perm = leaf.permutation();

        match i.cmp(&insert_pos) {
            Ordering::Less => {
                // Before insert point: use existing key at position i
                leaf.ikey(perm.get(i))
            }

            Ordering::Equal => {
                // At insert point: this is the new key
                insert_ikey
            }

            Ordering::Greater => {
                // After insert point: shifted by 1, so use position i-1
                leaf.ikey(perm.get(i - 1))
            }
        }
    }

    /// Adjust split position to keep equal ikey0 values together.
    ///
    /// Uses post-insert key stream to correctly handle the case where the
    /// inserted key affects which keys should stay together.
    ///
    /// Returns None if all entries have the same ikey (layer case).
    fn adjust_split_for_equal_ikeys_post_insert<S: ValueSlot, const WIDTH: usize>(
        leaf: &LeafNode<S, WIDTH>,
        mut pos: usize,
        insert_pos: usize,
        insert_ikey: u64,
        post_insert_size: usize,
    ) -> Option<usize> {
        if post_insert_size <= 1 {
            return Some(pos);
        }

        // Get ikey at current split position (post-insert)
        let split_ikey: u64 = Self::ikey_after_insert(leaf, pos, insert_pos, insert_ikey);

        // Move left while previous entry has same ikey
        while pos > 0 {
            let prev_ikey: u64 = Self::ikey_after_insert(leaf, pos - 1, insert_pos, insert_ikey);

            if prev_ikey != split_ikey {
                break;
            }

            pos -= 1;
        }

        // If we moved to position 0, all entries might have same ikey
        // Try moving right instead
        if pos == 0 {
            let first_ikey: u64 = Self::ikey_after_insert(leaf, 0, insert_pos, insert_ikey);
            pos = 1;

            while pos < post_insert_size {
                let curr_ikey: u64 = Self::ikey_after_insert(leaf, pos, insert_pos, insert_ikey);

                if curr_ikey != first_ikey {
                    break;
                }

                pos += 1;
            }

            // If we reached the end, all entries have same ikey
            if pos >= post_insert_size {
                return None; // Layer case - can't split
            }
        }

        Some(pos)
    }

    /// Calculate the split point for a leaf node.
    ///
    /// Returns the logical position where to split. Entries from `pos` to `size`
    /// (in post-insert coordinates) will move to the new leaf.
    ///
    /// # Arguments
    /// * `leaf` - The leaf node to split
    /// * `insert_pos` - Where the new key would be inserted
    /// * `insert_ikey` - The ikey of the new key
    ///
    /// # Returns
    /// `SplitPoint` with position and split key, or None if split is not possible
    /// (e.g., all entries have same ikey - would need layer instead).
    pub fn calculate_split_point<S: ValueSlot, const WIDTH: usize>(
        leaf: &LeafNode<S, WIDTH>,
        insert_pos: usize,
        insert_ikey: u64,
    ) -> Option<SplitPoint> {
        let perm: Permuter<WIDTH> = leaf.permutation();
        let size: usize = perm.size();

        if size == 0 {
            return None; // Can't split empty leaf
        }

        // Post-insert size is size + 1
        let post_insert_size: usize = size + 1;

        // Default: split in the middle (of post-insert size)
        let mut split_pos: usize = post_insert_size.div_ceil(2);

        // Sequential optimization heuristics
        let is_rightmost: bool = leaf.safe_next().is_null();
        let is_leftmost: bool = leaf.prev().is_null();
        let inserting_at_end: bool = insert_pos >= size;
        let inserting_at_start: bool = insert_pos == 0;

        if is_rightmost && inserting_at_end {
            // Right-sequential: keep left nearly full
            split_pos = post_insert_size - 1;
        } else if is_leftmost && inserting_at_start {
            // Left-sequential: keep right nearly full
            split_pos = 1;
        }

        // Adjust to keep equal ikey0 values together (using post-insert keys)
        split_pos = Self::adjust_split_for_equal_ikeys_post_insert(
            leaf,
            split_pos,
            insert_pos,
            insert_ikey,
            post_insert_size,
        )?;

        // Get the split key (first key of right half, in post-insert order)
        let split_ikey = Self::ikey_after_insert(leaf, split_pos, insert_pos, insert_ikey);

        Some(SplitPoint {
            pos: split_pos,
            split_ikey,
        })
    }
}

/// Value stored in a leaf slot (default mode with `Arc<V>`).
///
/// Each slot can contain either an Arc-wrapped value or a pointer to a next-layer
/// subtree (for keys longer than 8 bytes at this level).
///
/// # Type Parameter
/// * `V` - The value type stored in the tree (stored as `Arc<V>`)
///
/// NOTE: Why `Arc<V>`?
/// Optimistic reads need to return owned values safely.
/// `Arc<V>` allows cheap cloning (refcount) and decouples value
/// lifetime from node lifetime (EBR handles node, `Arc` handles values).
/// More details and rationale can be found in README.md
#[derive(Debug, Default)]
pub enum LeafValue<V> {
    /// Slot is empty (no key assigned).
    #[default]
    Empty,

    /// Slot contains an Arc-wrapped value.
    /// Cloning is cheap (refcount increment), enabling lock-free reads.
    Value(Arc<V>),

    /// Slot contains a pointer to a next-layer subtree.
    /// The pointer is to a `LeafNode` that serves as the root of the sublayer.
    ///
    /// this will be refined to a proper node type.
    Layer(*mut u8),
}

impl<V> LeafValue<V> {
    // ============================================================================
    //  Constructor Methods
    // ============================================================================

    /// Create an empty leaf value.
    #[inline]
    #[must_use]
    pub const fn empty() -> Self {
        Self::Empty
    }

    // ============================================================================
    //  Boolean Methods
    // ============================================================================

    /// Check if this slot is empty.
    #[inline]
    #[must_use]
    pub const fn is_empty(&self) -> bool {
        matches!(self, Self::Empty)
    }

    /// Check if this slot contains a value.
    #[inline]
    #[must_use]
    pub const fn is_value(&self) -> bool {
        matches!(self, Self::Value(_))
    }

    /// Check if this slot contains a layer pointer.
    #[inline]
    #[must_use]
    pub const fn is_layer(&self) -> bool {
        matches!(self, Self::Layer(_))
    }

    // ============================================================================
    //  Safe Try-None Methods
    // ============================================================================

    /// Try to get the Arc value, returning None if not a value variant.
    #[inline]
    #[must_use]
    pub const fn try_as_value(&self) -> Option<&Arc<V>> {
        match self {
            Self::Value(arc) => Some(arc),

            _ => None,
        }
    }

    /// Try to clone the Arc value, returning None if not a value variant.
    #[inline(always)]
    #[must_use]
    pub fn try_clone_arc(&self) -> Option<Arc<V>> {
        match self {
            Self::Value(arc) => Some(Arc::clone(arc)),

            _ => None,
        }
    }

    /// Try to get the layer pointer, returning None if not a Layer variant.
    #[inline(always)]
    #[must_use]
    pub const fn try_as_layer(&self) -> Option<*mut u8> {
        match self {
            Self::Layer(ptr) => Some(*ptr),

            _ => None,
        }
    }

    // ============================================================================
    //  Probable panicky but ergonomic internal use methods
    // ============================================================================

    /// Get the layer pointer.
    ///
    /// WARN: Prefer `try_as_layer()`. This method is
    /// provided for internal use where the variant is known.
    ///
    /// # Panics
    /// Panics if this is not a Layer variant.
    #[inline]
    #[must_use]
    #[expect(clippy::expect_used, reason = "Invariant ensured by caller")]
    pub const fn as_layer(&self) -> *mut u8 {
        self.try_as_layer()
            .expect("LeafValue::as_layer called on non-Layer variant")
    }

    /// Gets a reference to the Arc-wrapped value.
    ///
    ///  WARN: Prefer `try_as_value()`. This was added for internal use where the invariant is known.
    ///
    /// # Panics
    /// Panics if ths is not a Value variant.
    #[inline]
    #[must_use]
    #[expect(clippy::expect_used, reason = "Invariant ensured by caller")]
    pub const fn as_value(&self) -> &Arc<V> {
        self.try_as_value()
            .expect("LeafValue::as_value called on non-Value variant")
    }

    /// Clone the Arc<V> (cheap reference counting increment)
    ///
    ///  WARN: Prefer `try_as_value()`. This was added for internal use where the invariant is known.
    ///
    /// # Panics
    /// Panics if ths is not a Value variant.
    #[inline]
    #[must_use]
    #[expect(clippy::expect_used, reason = "Invariant ensured by caller")]
    pub fn clone_arc(&self) -> Arc<V> {
        self.try_clone_arc()
            .expect("LeafValue::as_value called on non-Value variant")
    }

    /// Get a mutable reference to the Arc-wrapped value.
    ///
    ///  WARN: Prefer checking `is_value()` first if using without invariant checks.
    ///
    /// # Panics
    /// Panics if ths is not a Value variant.
    #[inline]
    #[expect(clippy::panic, reason = "Invariant ensured by caller")]
    pub fn as_value_mut(&mut self) -> &mut Arc<V> {
        match self {
            Self::Value(arc) => arc,

            _ => panic!("LeafValue::as_value_mut called on non-value variant"),
        }
    }
}

impl<V> Clone for LeafValue<V> {
    fn clone(&self) -> Self {
        match self {
            Self::Empty => Self::Empty,

            // This adds some overhead already compared to the raw ptr
            // handling of C++ impl, but it currently seems like the
            // right design decision. The trade off seems justified.
            Self::Value(arc) => Self::Value(Arc::clone(arc)),

            Self::Layer(ptr) => Self::Layer(*ptr),
        }
    }
}

// ============================================================================
//  Send + Sync implementations for LeafValue
// ============================================================================

// SAFETY: LeafValue is safe to send between threads because:
// 1. `Empty` has no data
// 2. `Value(Arc<V>)` is Send when V: Send+Sync (Arc<T> is Send when T: Send+Sync)
// 3. `Layer(*mut u8)` points to tree-owned nodes that are protected by:
//    - Version-based optimistic concurrency control (readers validate before use)
//    - Per-node locks via NodeVersion (writers acquire lock before modification)
//    - Seize-based memory reclamation (nodes are not freed while readers exist)
//
// The raw pointer itself is just an address - it's the ACCESS to the data that
// must be synchronized, which is handled by the tree's concurrency protocol.
unsafe impl<V: Send + Sync> Send for LeafValue<V> {}

// SAFETY: LeafValue is safe to share between threads because:
// 1. `Empty` has no data to share
// 2. `Value(Arc<V>)` is Sync when V: Send+Sync (Arc<T> is Sync when T: Send+Sync)
// 3. `Layer(*mut u8)` - shared access to the pointer is safe because:
//    - Readers use optimistic validation (stable() -> read -> has_changed())
//    - Concurrent reads of the same pointer value are safe (just loading an address)
//    - Writes go through locked paths that update atomically
unsafe impl<V: Send + Sync> Sync for LeafValue<V> {}

/// Value stored in a leaf slot (index mode with inline `V: Copy`).
///
/// For high-perf index use cases values are small and Copy.
///
/// # Type Parameter
/// `V` - The value type stored inline (must be `Copy`)
#[derive(Clone, Copy, Debug, Default)]
pub enum LeafValueIndex<V: Copy> {
    /// Slot is empty (no key assigned).
    #[default]
    Empty,

    /// Slot contains an inline value (copied on read).
    Value(V),

    /// Slot contains a pointer to a next-layer subtree.
    ///
    /// This will be refined to proper node type.
    Layer(*mut u8),
}

// SAFETY: Same reasoning as LeafValue - the Layer pointer is protected by
// the tree's concurrency control (version validation, locks, seize reclamation).
unsafe impl<V: Copy + Send> Send for LeafValueIndex<V> {}
unsafe impl<V: Copy + Sync> Sync for LeafValueIndex<V> {}

impl<V: Copy> LeafValueIndex<V> {
    // ============================================================================
    //  Constructor Methods
    // ============================================================================

    /// Create an empty leaf value.
    #[inline]
    #[must_use]
    pub const fn empty() -> Self {
        Self::Empty
    }

    // ============================================================================
    //  Boolean Methods
    // ============================================================================

    /// Check if this slot is empty.
    #[inline]
    #[must_use]
    pub const fn is_empty(&self) -> bool {
        matches!(self, Self::Empty)
    }

    /// Check if this slot contains a value.
    #[inline]
    #[must_use]
    pub const fn is_value(&self) -> bool {
        matches!(self, Self::Value(_))
    }

    /// Check if this slot contains a layer pointer.
    #[inline]
    #[must_use]
    pub const fn is_layer(&self) -> bool {
        matches!(self, Self::Layer(_))
    }

    // ============================================================================
    //  Safe Try-None Methods
    // ============================================================================

    /// Try to get the value, returning None if not a Value variant.
    #[inline]
    #[must_use]
    pub const fn try_value(&self) -> Option<V> {
        match self {
            Self::Value(v) => Some(*v),

            _ => None,
        }
    }

    /// Try to get the layer pointer, returning None if not a Layer variant.
    #[inline]
    #[must_use]
    pub const fn try_as_layer(&self) -> Option<*mut u8> {
        match self {
            Self::Layer(ptr) => Some(*ptr),

            _ => None,
        }
    }

    // ============================================================================
    //  Probable panicky but ergonomic internal use methods
    // ============================================================================

    /// Get the value (copied).
    ///
    /// WARN: Prefer `try_value()`. This method is
    /// provided for internal use where the variant is known.
    ///
    /// # Panics
    /// Panics if this is not a Value variant.
    #[inline]
    #[must_use]
    #[expect(clippy::expect_used, reason = "Invariant ensured by caller")]
    pub const fn value(&self) -> V {
        self.try_value()
            .expect("LeafValueIndex::value called on non-Value variant")
    }

    /// Get the layer pointer.
    ///
    /// WARN: Prefer `try_as_layer()`. This method is
    /// provided for internal use where the variant is known.
    ///
    /// # Panics
    /// Panics if this is not a Layer variant.
    #[expect(clippy::expect_used, reason = "Invariant ensured by caller")]
    #[inline]
    #[must_use]
    pub const fn as_layer(&self) -> *mut u8 {
        self.try_as_layer()
            .expect("LeafValueIndex::as_layer called on non-Layer variant")
    }
}

/// Leaf node with two-store concurrent slot access.
///
/// # Concurrency Model
/// `SLots` use two-store with version protection:
/// - `keylenx[slot]`: [`AtomicU8`], determines slot type (0-8=inline, 64=suffix, >=128=layer)
/// - `leaf_values[slot]`: [`AtomicPtr<u8>`], stores pointer (provenance-safe)
/// - Writers: `mark_insert()` -> stores -> `unlock()`
/// - Readers: `stable` -> loads -> `has_changed()`
///
/// # Memory Ordering
///
/// - Writers: Release on all stores
/// - Readers: Acquire on all loads after `stable()`
/// - Version validation ensures consistency
///
/// # Provenance Safety
///
/// Using `AtomicPtr<u8>` instead of `AtomicU64` preserves pointer provenance.
/// The type discriminant (Value vs Layer) is in `keylenx`, not pointer bits.
/// This passes Miri strict provenance checks.
///
/// # Suffix Strategy (Concurrent Safety)
///
/// **CRITICAL**: The current `SuffixBag` (`Vec<u8>`) is NOT data-race-free.
/// Even "append-only" `Vec::extend_from_slice` is a data race under concurrency.
///
/// ## C++ Reference Strategy (`masstree_struct.hh:728-778`)
///
/// The C++ allocates a NEW suffix container, copies data, publishes atomically
/// with fences, then defers freeing the old container via RCU:
///
/// ```cpp
/// void assign_ksuf(...) {
///     external_ksuf_type* oksuf = ksuf_;
///     void* ptr = ti.allocate(sz, ...);
///     external_ksuf_type* nksuf = new(ptr) external_ksuf_type(...);
///     // copy active suffixes to nksuf
///     fence();
///     ksuf_ = nksuf;  // atomic publish
///     fence();
///     if (oksuf)
///         ti.deallocate_rcu(oksuf, ...);  // deferred free
/// }
///
/// ## Rust Implementation Strategy
///
/// Use [`AtomicPtr<SuffixBag>`] with copy-on-write semantics:
///
/// 1. **Read Path**: Load `AtomicPtr<SuffixBag>`, access immutable data
/// 2. **Write Path**: Allocate new `Box<SuffixBag>`, copy + append, publish via CAS
/// 3. **Old Container**: Retire via `guard.defer_retire()`
#[repr(C, align(64))]
pub struct LeafNode<S: ValueSlot, const WIDTH: usize = 15> {
    /// Version for optimistic concurrency control.
    version: NodeVersion,

    /// Modification state for suffix operations.
    modstate: ModState,

    /// Permutation (atomic for concurrent reads).
    /// Store is linearization point for new slot visibility.
    permutation: AtomicU64,

    /// 8-byte keys for each slot.
    ikey0: [AtomicU64; WIDTH],

    /// Key length/type for each slot.
    /// Values 0-8: inline key length
    /// Value 64: has suffix
    /// Value ≥128: is layer
    keylenx: [AtomicU8; WIDTH],

    /// Values/layer pointers for each slot.
    /// Stores Arc<V> raw pointer or layer pointer as *mut u8.
    /// Type is determined by keylenx: if < `LAYER_KEYLENX` → Arc<V>, else → layer node.
    /// Using `AtomicPtr` preserves provenance (vs `AtomicU64` which would erase it).
    leaf_values: [AtomicPtr<u8>; WIDTH],

    /// Suffix storage (atomic pointer for concurrent access).
    ///
    /// **CRITICAL**: Uses `AtomicPtr<SuffixBag>` NOT `Option<Box<SuffixBag>>`.
    /// Writers allocate new `SuffixBag`, copy data, publish via store(Release),
    /// then retire old bag via seize. Readers load(Acquire) and access immutably.
    ksuf: AtomicPtr<SuffixBag<WIDTH>>,

    /// Next leaf with mark bit in LSB for split coordination.
    next: AtomicPtr<Self>,

    /// Previous leaf.
    prev: AtomicPtr<Self>,

    /// Parent internode.
    parent: AtomicPtr<u8>,

    /// Phantom for slot type.
    _marker: PhantomData<S>,
}

impl<S: ValueSlot, const WIDTH: usize> StdFmt::Debug for LeafNode<S, WIDTH> {
    fn fmt(&self, f: &mut StdFmt::Formatter<'_>) -> StdFmt::Result {
        f.debug_struct("LeafNode")
            .field("size", &self.size())
            .field("is_root", &self.version.is_root())
            .field("has_parent", &(!self.parent().is_null()))
            .finish_non_exhaustive()
    }
}

// Compile-time assertion: WIDTH must be 1..=15
impl<S: ValueSlot, const WIDTH: usize> LeafNode<S, WIDTH> {
    const WIDTH_CHECK: () = {
        assert!(WIDTH > 0, "WIDTH must be at least 1");

        assert!(WIDTH <= 15, "WIDTH must be at most 15 (u64 permuter limit)");
    };
}

impl<S: ValueSlot, const WIDTH: usize> LeafNode<S, WIDTH> {
    // ============================================================================
    //  Constructor Methods
    // ============================================================================

    /// Create a new leaf node (unboxed).
    #[must_use]
    pub fn new_with_root(is_root: bool) -> Self {
        let version: NodeVersion = NodeVersion::new(true);
        if is_root {
            version.mark_root();
        }

        Self {
            version,
            modstate: ModState::Insert,
            permutation: AtomicU64::new(Permuter::<WIDTH>::empty().value()),
            ikey0: std::array::from_fn(|_| AtomicU64::new(0)),
            keylenx: std::array::from_fn(|_| AtomicU8::new(0)),
            leaf_values: std::array::from_fn(|_| AtomicPtr::new(std::ptr::null_mut())),
            ksuf: AtomicPtr::new(std::ptr::null_mut()), // AtomicPtr instead of Option
            next: AtomicPtr::new(std::ptr::null_mut()),
            prev: AtomicPtr::new(std::ptr::null_mut()),
            parent: AtomicPtr::new(std::ptr::null_mut()),
            _marker: PhantomData,
        }
    }

    /// Create a new leaf node (boxed).
    #[must_use]
    pub fn new() -> Box<Self> {
        Box::new(Self::new_with_root(false))
    }

    /// Create a new leaf node as the root of a tree/layer.
    ///
    /// Same as `new()` but explicitly marks the node as root.
    #[must_use]
    pub fn new_root() -> Box<Self> {
        Box::new(Self::new_with_root(true))
    }

    // ============================================================================
    //  NodeVersion Accessors
    // ============================================================================

    /// Get a reference to the node's version.
    #[inline]
    pub const fn version(&self) -> &NodeVersion {
        &self.version
    }

    /// Get a mutable reference to the nodes version.
    #[inline]
    pub const fn version_mut(&mut self) -> &mut NodeVersion {
        &mut self.version
    }

    // ============================================================================
    //  Key Accessors
    // ============================================================================

    /// Get the ikey at the given physical slot.
    ///
    /// # Panics
    /// Panics in debug mode if `slot >= WIDTH`.
    #[inline(always)]
    #[must_use]
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot from Permuter, valid by construction"
    )]
    pub fn ikey(&self, slot: usize) -> u64 {
        debug_assert!(slot < WIDTH, "ikey: slot out of bounds");

        self.ikey0[slot].load(READ_ORD)
    }

    /// Set the ikey at the given physical slot.
    ///
    /// # Panics
    /// Panics in debug mode if `slot >= WIDTH`.
    #[inline(always)]
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot from Permuter, valid by construction"
    )]
    pub fn set_ikey(&self, slot: usize, ikey: u64) {
        debug_assert!(slot < WIDTH, "set_ikey: slot out of bounds");

        self.ikey0[slot].store(ikey, WRITE_ORD);
    }

    /// Get the keylenx at the given physical slot.
    ///
    /// # Panics
    /// Panics in debug mode if `slot >= WIDTH`.
    #[inline(always)]
    #[must_use]
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot from Permuter, valid by construction"
    )]
    pub fn keylenx(&self, slot: usize) -> u8 {
        debug_assert!(slot < WIDTH, "keylenx: slot out of bounds");

        self.keylenx[slot].load(READ_ORD)
    }

    /// Set the keylenx at the given physical slot.
    ///
    /// # Panics
    /// Panics in debug mode if `slot >= WIDTH`.
    #[inline(always)]
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot from Permuter, valid by construction"
    )]
    pub fn set_keylenx(&self, slot: usize, keylenx: u8) {
        debug_assert!(slot < WIDTH, "set_keylenx: slot out of bounds");

        self.keylenx[slot].store(keylenx, WRITE_ORD);
    }

    /// Get the ikey bound (ikey at slot 0, used for B-link tree routing).
    ///
    /// This is the smallest key that could be in this leaf (after splits).
    #[inline(always)]
    #[must_use]
    pub fn ikey_bound(&self) -> u64 {
        self.ikey0[0].load(READ_ORD)
    }

    /// Get the `keylenx` bound for this leaf (used for B-link navigation).
    ///
    /// The `keylenx` bound is the keylenx of the first key (slot 0 in permutation order).
    /// Combined with `ikey_bound()`, this provides full key comparison for B-link traversal.
    ///
    /// # Panics
    /// Panics in debug mode if the leaf is empty.
    #[inline]
    pub fn keylenx_bound(&self) -> u8 {
        let perm: Permuter<WIDTH> = self.permutation();

        debug_assert!(perm.size() > 0, "keylenx_bound called on empty_leaf");

        self.keylenx(perm.get(0))
    }

    /// Check if the given slot contains a layer pointer.
    ///
    /// # Panics
    /// Panics in debug mode if `slot >= WIDTH`.
    #[inline]
    #[must_use]
    pub fn is_layer(&self, slot: usize) -> bool {
        self.keylenx(slot) >= LAYER_KEYLENX
    }

    /// Check if the given slot has a suffix.
    ///
    /// # Panics
    /// Panics in debug mode if `slot >= WIDTH`.
    #[inline(always)]
    #[must_use]
    pub fn has_ksuf(&self, slot: usize) -> bool {
        self.keylenx(slot) == KSUF_KEYLENX
    }

    /// Check if keylenx indicates a layer pointer (static helper).
    #[inline(always)]
    #[must_use]
    pub const fn keylenx_is_layer(keylenx: u8) -> bool {
        keylenx >= LAYER_KEYLENX
    }

    /// Check if keylenx indicates suffix storage (static helper).
    #[inline(always)]
    #[must_use]
    pub const fn keylenx_has_ksuf(keylenx: u8) -> bool {
        keylenx == KSUF_KEYLENX
    }

    // ============================================================================
    //  Suffix Storage Methods
    // ============================================================================

    /// Load suffix bag pointer (reader).
    #[inline]
    #[must_use]
    pub fn ksuf_ptr(&self) -> *mut SuffixBag<WIDTH> {
        self.ksuf.load(READ_ORD)
    }

    /// Check if this leaf has suffix storage allocated.
    #[inline]
    #[must_use]
    pub fn has_ksuf_storage(&self) -> bool {
        !self.ksuf_ptr().is_null()
    }

    /// Get the suffix for a slot.
    ///
    /// Returns `None` if:
    /// - No suffix storage exists, or
    /// - The slot doesn't have a suffix (`keylenx != KSUF_KEYLENX`)
    ///
    /// # Panics
    /// Panics in debug mode if `slot >= WIDTH`.
    #[must_use]
    pub fn ksuf(&self, slot: usize) -> Option<&[u8]> {
        debug_assert!(slot < WIDTH, "ksuf: slot {slot} >= WIDTH {WIDTH}");

        if !self.has_ksuf(slot) {
            return None;
        }

        let ptr = self.ksuf_ptr();
        if ptr.is_null() {
            return None;
        }

        // SAFETY: Caller must ensure suffix bag is stable (lock or version check).
        unsafe { (*ptr).get(slot) }
    }

    /// Get the suffix for a slot, or an empty slice if none.
    ///
    /// # Panics
    /// Panics in debug mode if `slot >= WIDTH`.
    #[inline]
    #[must_use]
    pub fn ksuf_or_empty(&self, slot: usize) -> &[u8] {
        self.ksuf(slot).unwrap_or(&[])
    }

    /// Assign a suffix to a slot (copy-on-write).
    ///
    /// Publishes a new `SuffixBag` and retires the old one via seize.
    ///
    /// # Safety
    /// - Caller must hold lock and have called `mark_insert()`
    /// - `guard` must come from this tree's collector
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot bounds checked via debug_assert"
    )]
    pub unsafe fn assign_ksuf(&self, slot: usize, suffix: &[u8], guard: &LocalGuard<'_>) {
        debug_assert!(slot < WIDTH, "assign_ksuf: slot {slot} >= WIDTH {WIDTH}");

        let old_ptr: *mut SuffixBag<WIDTH> = self.ksuf.load(RELAXED);
        // SAFETY: If old_ptr is non-null, it came from Box::into_raw in a previous assign_ksuf
        let mut new_bag: SuffixBag<WIDTH> = if old_ptr.is_null() {
            SuffixBag::new()
        } else {
            unsafe { (*old_ptr).clone() }
        };

        new_bag.assign(slot, suffix);
        let new_ptr: *mut SuffixBag<WIDTH> = Box::into_raw(Box::new(new_bag));

        self.ksuf.store(new_ptr, WRITE_ORD);

        if !old_ptr.is_null() {
            // SAFETY: old_ptr is non-null and came from Box::into_raw
            unsafe {
                guard.defer_retire(old_ptr, |ptr, _| {
                    drop(Box::from_raw(ptr));
                });
            }
        }

        self.keylenx[slot].store(KSUF_KEYLENX, WRITE_ORD);
    }

    /// Clear the suffix from a slot (copy-on-write).
    ///
    /// # Safety
    /// - Caller must hold lock and have called `mark_insert()`
    /// - `guard` must come from this tree's collector
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot bounds checked via debug_assert"
    )]
    pub unsafe fn clear_ksuf(&self, slot: usize, guard: &LocalGuard<'_>) {
        debug_assert!(slot < WIDTH, "clear_ksuf: slot {slot} >= WIDTH {WIDTH}");

        let old_ptr: *mut SuffixBag<WIDTH> = self.ksuf.load(RELAXED);
        if old_ptr.is_null() {
            self.keylenx[slot].store(0, WRITE_ORD);
            return;
        }

        // SAFETY: old_ptr is non-null and came from Box::into_raw in a previous assign_ksuf
        let mut new_bag: SuffixBag<WIDTH> = unsafe { (*old_ptr).clone() };
        new_bag.clear(slot);
        let new_ptr: *mut SuffixBag<WIDTH> = Box::into_raw(Box::new(new_bag));

        self.ksuf.store(new_ptr, WRITE_ORD);

        // SAFETY: old_ptr is non-null and came from Box::into_raw
        unsafe {
            guard.defer_retire(old_ptr, |ptr, _| {
                drop(Box::from_raw(ptr));
            });
        }

        self.keylenx[slot].store(0, WRITE_ORD);
    }

    /// Check if a slot's suffix equals the given suffix.
    #[must_use]
    pub fn ksuf_equals(&self, slot: usize, suffix: &[u8]) -> bool {
        debug_assert!(slot < WIDTH, "ksuf_equals: slot {slot} >= WIDTH {WIDTH}");

        if !self.has_ksuf(slot) {
            return false;
        }

        let ptr = self.ksuf_ptr();
        if ptr.is_null() {
            return false;
        }

        // SAFETY: Caller must ensure suffix bag is stable (lock or version check).
        unsafe { (*ptr).suffix_equals(slot, suffix) }
    }

    /// Compare a slot's suffix with the given suffix.
    #[must_use]
    pub fn ksuf_compare(&self, slot: usize, suffix: &[u8]) -> Option<std::cmp::Ordering> {
        debug_assert!(slot < WIDTH, "ksuf_compare: slot {slot} >= WIDTH {WIDTH}");

        if !self.has_ksuf(slot) {
            return None;
        }

        let ptr = self.ksuf_ptr();
        if ptr.is_null() {
            return None;
        }

        // SAFETY: Caller must ensure suffix bag is stable (lock or version check).
        unsafe { (*ptr).suffix_compare(slot, suffix) }
    }

    /// Check if a slot's key (ikey + suffix) matches the given full key.
    ///
    /// This compares both the 8-byte ikey and the suffix (if any).
    ///
    /// # Arguments
    ///
    /// * `slot` - Physical slot index
    /// * `ikey` - The 8-byte key to compare
    /// * `suffix` - The suffix to compare (bytes after the first 8)
    ///
    /// # Returns
    ///
    /// `true` if both ikey and suffix match.
    ///
    /// # Panics
    ///
    /// Panics in debug mode if `slot >= WIDTH`.
    #[must_use]
    pub fn ksuf_matches(&self, slot: usize, ikey: u64, suffix: &[u8]) -> bool {
        debug_assert!(slot < WIDTH, "ksuf_matches: slot {slot} >= WIDTH {WIDTH}");

        // First check ikey
        if self.ikey(slot) != ikey {
            return false;
        }

        // Then check suffix
        if suffix.is_empty() {
            // Key has no suffix - slot should also have no suffix
            !self.has_ksuf(slot)
        } else {
            // Key has suffix - slot must have matching suffix
            self.ksuf_equals(slot, suffix)
        }
    }

    /// Check if a slot matches the given key parameters, with layer detection.
    ///
    /// This is the layer-aware version of `ksuf_matches` that returns detailed
    /// match information needed for layer traversal.
    ///
    /// # Arguments
    ///
    /// * `slot` - Physical slot index
    /// * `keylenx` - The keylenx of the search key (0-8 for inline, `KSUF_KEYLENX` for suffix)
    /// * `suffix` - The suffix bytes to match (empty if inline key)
    ///
    /// # Returns
    ///
    /// * `1` - Exact match (ikey, keylenx, and suffix all match)
    /// * `0` - Same ikey but different key (keylenx or suffix mismatch)
    /// * `-8` - Slot is a layer pointer; caller should shift key by 8 bytes and descend
    ///
    /// # Note
    ///
    /// The ikey is assumed to already match (caller should check `leaf.ikey(slot) == ikey`
    /// before calling this method).
    ///
    /// # Panics
    ///
    /// Panics in debug mode if `slot >= WIDTH`.
    #[inline(always)]
    #[must_use]
    #[expect(
        clippy::cast_possible_wrap,
        clippy::cast_possible_truncation,
        reason = "IKEY_SIZE (8) fits in i32"
    )]
    pub fn ksuf_match_result(&self, slot: usize, keylenx: u8, suffix: &[u8]) -> i32 {
        use crate::key::IKEY_SIZE;

        debug_assert!(
            slot < WIDTH,
            "ksuf_match_result: slot {slot} >= WIDTH {WIDTH}"
        );

        let stored_keylenx: u8 = self.keylenx(slot);

        // Check for layer pointer first
        if Self::keylenx_is_layer(stored_keylenx) {
            return -(IKEY_SIZE as i32);
        }

        // Check keylenx for inline keys (no suffix)
        if !self.has_ksuf(slot) {
            // Slot is an inline key - keylenx must match exactly
            if stored_keylenx == keylenx && suffix.is_empty() {
                return 1; // Exact match
            }
            return 0; // Different keylenx or search has suffix
        }

        // Slot has suffix - search key should also have suffix
        if suffix.is_empty() {
            return 0; // Slot has suffix but key doesn't
        }

        // Both have suffixes - compare them
        i32::from(self.ksuf_equals(slot, suffix))
    }

    /// Compact suffix storage, reclaiming space from deleted entries.
    ///
    /// This garbage-collects unused suffix data by keeping only suffixes
    /// for slots that are currently active in the permutation.
    ///
    /// # Arguments
    ///
    /// * `exclude_slot` - Optional slot to exclude (e.g., slot being removed)
    ///
    /// # Returns
    ///
    /// The number of bytes reclaimed, or 0 if no suffix storage exists.
    ///
    /// # Safety
    ///
    /// - The `guard` must be valid and from the same collector as the tree.
    /// - No concurrent modifications to suffix storage may occur during compaction.
    pub unsafe fn compact_ksuf(
        &self,
        exclude_slot: Option<usize>,
        guard: &LocalGuard<'_>,
    ) -> usize {
        let old_ptr: *mut SuffixBag<WIDTH> = self.ksuf.load(RELAXED);
        if old_ptr.is_null() {
            return 0;
        }

        let perm = self.permutation();
        // SAFETY: old_ptr is non-null and came from Box::into_raw in a previous assign_ksuf
        let mut new_bag: SuffixBag<WIDTH> = unsafe { (*old_ptr).clone() };
        let reclaimed = new_bag.compact_with_permuter(&perm, exclude_slot);
        let new_ptr: *mut SuffixBag<WIDTH> = Box::into_raw(Box::new(new_bag));

        self.ksuf.store(new_ptr, WRITE_ORD);

        // SAFETY: old_ptr is non-null and came from Box::into_raw
        unsafe {
            guard.defer_retire(old_ptr, |ptr, _| {
                drop(Box::from_raw(ptr));
            });
        }

        reclaimed
    }

    // ============================================================================
    //  Value Accessors
    // ============================================================================

    /// Load leaf value pointer at the given slot.
    #[inline(always)]
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot from Permuter; valid by construction"
    )]
    pub fn leaf_value_ptr(&self, slot: usize) -> *mut u8 {
        debug_assert!(slot < WIDTH, "leaf_value_ptr: slot out of bounds");

        self.leaf_values[slot].load(READ_ORD)
    }

    /// Store leaf value pointer at the given slot.
    #[inline(always)]
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot from Permuter; valid by construction"
    )]
    pub fn set_leaf_value_ptr(&self, slot: usize, ptr: *mut u8) {
        debug_assert!(slot < WIDTH, "set_leaf_value_ptr: slot out of bounds");

        self.leaf_values[slot].store(ptr, WRITE_ORD);
    }

    /// Take the leaf value pointer, leaving null in the slot.
    #[inline(always)]
    #[expect(
        clippy::indexing_slicing,
        reason = "Slot from Permuter; valid by construction"
    )]
    pub fn take_leaf_value_ptr(&self, slot: usize) -> *mut u8 {
        debug_assert!(slot < WIDTH, "take_leaf_value_ptr: slot out of bounds");

        self.leaf_values[slot].swap(StdPtr::null_mut(), RELAXED)
    }

    /// Check if a slot is empty (value pointer is null).
    #[inline(always)]
    #[must_use]
    pub fn is_slot_empty(&self, slot: usize) -> bool {
        self.leaf_value_ptr(slot).is_null()
    }

    // ============================================================================
    //  Permutation Accessors
    // ============================================================================

    /// Load permutation with Acquire ordering.
    ///
    /// Returns a `Permuter` wrapper for the permutation value.
    #[inline(always)]
    #[must_use]
    pub fn permutation(&self) -> Permuter<WIDTH> {
        Permuter::from_value(self.permutation.load(READ_ORD))
    }

    /// Store permutation with Release ordering (linearization point for inserts).
    ///
    /// # Note
    /// Takes `&self` (not `&mut self`) because the field is atomic.
    #[inline(always)]
    pub fn set_permutation(&self, perm: Permuter<WIDTH>) {
        self.permutation.store(perm.value(), WRITE_ORD);
    }

    /// Compare-and-swap the permutation atomically (non-freeze contexts only).
    ///
    /// # Errors
    /// Failure returned frozen raw, use `cas_permutation_raw()`
    ///
    /// # Panics
    /// Panics if the failure is due to a frozen permutation. Use `cas_permutation_raw`
    /// in code paths where freezing may occur.
    #[inline]
    pub fn cas_permutation(
        &self,
        expected: Permuter<WIDTH>,
        new: Permuter<WIDTH>,
    ) -> Result<(), Permuter<WIDTH>> {
        match self.cas_permutation_raw(expected, new) {
            Ok(()) => Ok(()),

            Err(failure) => {
                assert!(
                    !failure.is_frozen::<WIDTH>(),
                    "cas_permutation(): failure returned frozen raw, use cas_permutation_raw"
                );

                Err(Permuter::from_value(failure.current_raw()))
            }
        }
    }

    /// Pre-store slot data for CAS-based insert.
    ///
    /// Stores ikey, keylenx, and value pointer with Release ordering.
    /// Must be called **before** [`Self::cas_permutation`] to ensure data
    /// visibility after CAS succeeds.
    ///
    /// # Safety
    ///
    /// Caller must ensure:
    /// - `slot` is in the free region of the current permutation
    /// - No concurrent writer is modifying this slot
    /// - The permutation will be CAS'd to include this slot atomically
    ///
    /// # Memory Ordering
    ///
    /// All stores use Release ordering to synchronize with readers that
    /// observe the new permutation after CAS success.
    #[inline]
    #[expect(
        clippy::indexing_slicing,
        reason = "bounds checked by debug_assert, caller ensures slot < WIDTH"
    )]
    pub unsafe fn store_slot_for_cas(
        &self,
        slot: usize,
        ikey: u64,
        keylenx: u8,
        value_ptr: *mut u8,
    ) {
        debug_assert!(slot < WIDTH, "store_slot_for_cas: slot out of bounds");
        self.ikey0[slot].store(ikey, WRITE_ORD);
        self.keylenx[slot].store(keylenx, WRITE_ORD);
        self.leaf_values[slot].store(value_ptr, WRITE_ORD);
    }

    /// Clear a slot after a failed CAS insert.
    ///
    /// This must be called when CAS fails after `store_slot_for_cas` to prevent
    /// double-free on leaf drop. The slot's value pointer is set to null so
    /// the drop implementation won't try to free it.
    ///
    /// # Safety
    ///
    /// - Caller must have already reclaimed/freed the value that was stored
    /// - Slot must be in the free region (not visible to readers)
    #[inline]
    #[expect(
        clippy::indexing_slicing,
        reason = "bounds checked by debug_assert, caller ensures slot < WIDTH"
    )]
    pub unsafe fn clear_slot_for_cas(&self, slot: usize) {
        debug_assert!(slot < WIDTH, "clear_slot_for_cas: slot out of bounds");
        self.leaf_values[slot].store(std::ptr::null_mut(), WRITE_ORD);
    }

    /// Atomically claim a slot for CAS insert by CAS'ing the value pointer.
    ///
    /// This is the atomic slot reservation mechanism that prevents the slot
    /// collision bug where two threads reading the same permutation would
    /// both try to write to the same slot.
    ///
    /// # Errors
    ///
    /// Returns `Err(actual)` if the slot was already claimed or modified by another thread.
    /// The error contains the actual value pointer found in the slot.
    ///
    /// # Arguments
    ///
    /// - `slot`: The slot index to claim
    /// - `expected`: The expected current value (from `load_slot_value`)
    /// - `new_value`: The new value pointer to store (our Arc pointer)
    #[inline]
    #[expect(clippy::indexing_slicing, reason = "bounds checked by debug_assert")]
    pub fn cas_slot_value(
        &self,
        slot: usize,
        expected: *mut u8,
        new_value: *mut u8,
    ) -> Result<(), *mut u8> {
        debug_assert!(slot < WIDTH, "cas_slot_value: slot out of bounds");

        match self.leaf_values[slot].compare_exchange(expected, new_value, CAS_SUCCESS, CAS_FAILURE)
        {
            Ok(_) => Ok(()),
            Err(actual) => Err(actual),
        }
    }

    /// Load the current value pointer at a slot.
    ///
    /// Used before `cas_slot_value` to get the expected value for CAS.
    #[inline]
    #[expect(clippy::indexing_slicing, reason = "bounds checked by debug_assert")]
    pub fn load_slot_value(&self, slot: usize) -> *mut u8 {
        debug_assert!(slot < WIDTH, "load_slot_value: slot out of bounds");
        self.leaf_values[slot].load(READ_ORD)
    }

    /// Store key data for a slot after successful CAS claim.
    ///
    /// This stores ikey and keylenx with Release ordering to ensure
    /// they are visible to readers after the permutation CAS succeeds.
    ///
    /// # Safety
    ///
    /// - Caller must have successfully claimed the slot via `cas_slot_value`
    /// - Slot must still be in the free region of the permutation
    #[inline]
    #[expect(
        clippy::indexing_slicing,
        reason = "bounds checked by debug_assert, caller ensures slot < WIDTH"
    )]
    pub unsafe fn store_key_data_for_cas(&self, slot: usize, ikey: u64, keylenx: u8) {
        debug_assert!(slot < WIDTH, "store_key_data_for_cas: slot out of bounds");
        self.ikey0[slot].store(ikey, WRITE_ORD);
        self.keylenx[slot].store(keylenx, WRITE_ORD);
    }

    /// Get the number of keys in this leaf.
    #[inline(always)]
    #[must_use]
    pub fn size(&self) -> usize {
        self.permutation().size()
    }

    /// Check if the leaf is empty.
    #[inline(always)]
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.size() == 0
    }

    /// Check if the leaf is full.
    #[inline]
    #[must_use]
    pub fn is_full(&self) -> bool {
        self.size() >= WIDTH
    }

    // ============================================================================
    //  Leaf Linking
    // ============================================================================

    // NOTE: The next pointer uses LSB tagging (mark bit during splits).
    // We use `ptr::map_addr` (stable in Rust 1.84+) to preserve pointer provenance
    // when manipulating the address. This is important for Miri and strict provenance.
    // See: https://doc.rust-lang.org/std/ptr/index.html#provenance

    /// Get the next leaf pointer, masking the mark bit.
    ///
    /// The LSB of `next` is used as a mark during splits. This function
    /// returns the actual pointer with the mark bit cleared.
    #[inline]
    #[must_use]
    pub fn safe_next(&self) -> *mut Self {
        // Load atomic pointer, then use map_addr to preserve provenance while clearing mark bit
        let ptr: *mut Self = self.next.load(READ_ORD);
        ptr.map_addr(|addr: usize| addr & !1)
    }

    /// Get the raw next pointer (including mark bit).
    #[inline]
    #[must_use]
    pub fn next_raw(&self) -> *mut Self {
        self.next.load(READ_ORD)
    }

    /// Check if the next pointer is marked (split in progress).
    #[inline]
    #[must_use]
    pub fn next_is_marked(&self) -> bool {
        // addr() extracts address without exposing provenance
        (self.next.load(READ_ORD).addr() & 1) != 0
    }

    /// Set the next leaf pointer.
    #[inline]
    pub fn set_next(&self, next: *mut Self) {
        self.next.store(next, WRITE_ORD);
    }

    /// Mark the next pointer (during split).
    #[inline]
    pub fn mark_next(&self) {
        // Load, set mark bit, store back
        let ptr: *mut Self = self.next.load(RELAXED);
        let marked: *mut Self = ptr.map_addr(|addr: usize| addr | 1);
        self.next.store(marked, WRITE_ORD);
    }

    /// Unmark the next pointer.
    #[inline]
    pub fn unmark_next(&self) {
        let ptr: *mut Self = self.safe_next();
        self.next.store(ptr, WRITE_ORD);
    }

    /// Get the previous leaf pointer.
    #[inline]
    #[must_use]
    pub fn prev(&self) -> *mut Self {
        self.prev.load(READ_ORD)
    }

    /// Set the previous leaf pointer.
    #[inline]
    pub fn set_prev(&self, prev: *mut Self) {
        self.prev.store(prev, WRITE_ORD);
    }

    // ============================================================================
    //  Parent Accessors
    // ============================================================================

    /// Get the parent pointer.
    #[inline]
    #[must_use]
    pub fn parent(&self) -> *mut u8 {
        self.parent.load(READ_ORD)
    }

    /// Set the parent pointer.
    #[inline]
    pub fn set_parent(&self, parent: *mut u8) {
        self.parent.store(parent, WRITE_ORD);
    }

    // ============================================================================
    //  ModState Accessors
    // ============================================================================

    /// Get the modification state.
    #[inline]
    #[must_use]
    pub const fn modstate(&self) -> ModState {
        self.modstate
    }

    /// Set the modification state.
    #[inline]
    pub const fn set_modstate(&mut self, state: ModState) {
        self.modstate = state;
    }

    // ============================================================================
    //  Slot Assignment
    // ============================================================================

    /// Check if slot 0 can be reused for a new key.
    ///
    /// Slot 0 stores the `ikey_bound` for B-link navigation.
    /// **Correct Rule** (matching C++ reference):
    /// - `prev` is null (no predecessor leaf), **OR**
    /// - New ikey matches current `ikey_bound` (slot 0's ikey)
    ///
    /// # Arguments
    ///
    /// * `new_ikey` - The ikey of the key to insert
    ///
    /// # Returns
    ///
    /// `true` if slot 0 can be reused, `false` otherwise.
    #[inline]
    #[must_use]
    pub fn can_reuse_slot0(&self, new_ikey: u64) -> bool {
        // Rule 1: No predecessor leaf means slot 0 is always available
        if self.prev().is_null() {
            return true;
        }

        // Rule 2: Same ikey as current ikey_bound (slot 0) is safe
        self.ikey_bound() == new_ikey
    }

    /// Check if a new key can be inserted without splitting.
    ///
    /// This considers both space availability and the slot-0 rule.
    ///
    /// # Arguments
    ///
    /// * `ikey` - The ikey of the key to insert
    ///
    /// # Returns
    ///
    /// `true` if the leaf has space and can accept the key, `false` otherwise.
    #[inline]
    #[must_use]
    pub fn can_insert_directly(&self, ikey: u64) -> bool {
        let size: usize = self.size();
        if size >= WIDTH {
            return false;
        }
        let perm: Permuter<WIDTH> = self.permutation();
        let next_free_slot: usize = perm.back();

        // Can insert if:
        // 1. Slot 0 isn't at the back of the free list, OR
        // 2. We can reuse slot 0 (same ikey or no predecessor), OR
        // 3. There are other free slots we can swap to
        next_free_slot != 0 || self.can_reuse_slot0(ikey) || size < WIDTH - 1
    }

    // Slot assignment helpers for concrete value types live in
    // `LeafNode<LeafValue<V>>` and `LeafNode<LeafValueIndex<V>>` impls.

    // ============================================================================
    //  Split Operations
    // ============================================================================

    /// Split this leaf at `split_pos`, moving entries from `split_pos..end` to a new leaf.
    ///
    /// **Important:** The new leaf is returned in a Box. The caller
    /// (`MassTree`) must store it in the arena to ensure pointer stability,
    /// then link the leaves.
    ///
    /// After this operation:
    /// - `self` contains entries from position 0 to split_pos-1
    /// - returned leaf contains entries from `split_pos` to size-1
    /// - Leaf chain pointers are NOT updated here (caller must do it after arena allocation)
    ///
    /// # Arguments
    /// * `split_pos` - Logical position where to split (in pre-insert coordinates)
    ///
    /// # Returns
    /// A new leaf containing the upper half, and the split key.
    ///
    /// # Panics
    /// Panics in debug mode if `split_pos` is 0 or >= size.
    ///
    /// # Safety
    ///
    /// - The `guard` must be valid and from the same collector as the tree.
    /// - The caller must hold the leaf's lock before calling.
    /// - No concurrent reads to the entries being moved may occur.
    ///
    /// FIXED: Suffix Migration
    /// This method now correctly migrates suffix data for keys with `keylenx == KSUF_KEYLENX`.
    /// Previously, suffixes were lost during splits, causing lookup failures for long keys.
    pub unsafe fn split_into(
        &self,
        split_pos: usize,
        guard: &LocalGuard<'_>,
    ) -> LeafSplitResult<S, WIDTH> {
        let new_leaf: Box<Self> = Self::new();
        let old_perm: Permuter<WIDTH> = self.permutation();
        let old_size: usize = old_perm.size();

        debug_assert!(
            split_pos > 0 && (split_pos < old_size),
            "invalid split_pos {split_pos} for size {old_size}"
        );

        // Copy entries from split_pos to end into new leaf
        let entries_to_move: usize = old_size - split_pos;

        for i in 0..entries_to_move {
            let old_logical_pos: usize = split_pos + i;
            let old_slot: usize = old_perm.get(old_logical_pos);

            // Copy key metadata
            let ikey: u64 = self.ikey(old_slot);
            let keylenx: u8 = self.keylenx(old_slot);

            // Allocate slot in new leaf
            let new_slot: usize = i;

            new_leaf.set_ikey(new_slot, ikey);
            new_leaf.set_keylenx(new_slot, keylenx);

            // Move value pointer
            let old_ptr: *mut u8 = self.take_leaf_value_ptr(old_slot);
            new_leaf.set_leaf_value_ptr(new_slot, old_ptr);

            // FIXED: Migrate suffix if present
            if keylenx.eq(&KSUF_KEYLENX) {
                if let Some(suffix) = self.ksuf(old_slot) {
                    // Copy suffix to new leaf
                    // SAFETY: guard comes from caller, new_slot is valid
                    unsafe { new_leaf.assign_ksuf(new_slot, suffix, guard) };
                }

                // Clear suffix from old slot
                // SAFETY: guard comes from caller, old_slot is valid
                unsafe { self.clear_ksuf(old_slot, guard) };
            }
        }

        // Build new leaf's permutation
        let new_perm: Permuter<WIDTH> = Permuter::make_sorted(entries_to_move);
        new_leaf.set_permutation(new_perm);

        // Update old leaf's permutation
        let mut old_perm_updated: Permuter<WIDTH> = old_perm;
        old_perm_updated.set_size(split_pos);
        self.set_permutation(old_perm_updated);

        // Get split key
        let split_ikey: u64 = new_leaf.ikey(new_perm.get(0));

        LeafSplitResult {
            new_leaf,
            split_ikey,
            insert_into: InsertTarget::Left,
        }
    }

    /// Move ALL entries from this leaf to a new right leaf.
    ///
    /// This is used for the left-sequential optimization edge case where
    /// `split_pos == 0` in post-insert coordinates, meaning all existing entries
    /// should go to the right leaf and the new key (being inserted at position 0)
    /// should go into this (left) leaf.
    ///
    /// After this operation:
    /// - `self` is empty (will receive the new key)
    /// - returned leaf contains all entries from `self`
    ///
    /// # Returns
    /// A new leaf containing all entries, and the split key (first key of new leaf).
    ///
    /// # Safety
    ///
    /// - The `guard` must be valid and from the same collector as the tree.
    /// - The caller must hold the leaf's lock before calling.
    /// - No concurrent reads to the entries being moved may occur.
    ///
    /// FIXED: Suffix Migration
    /// This method now correctly migrates suffix data for keys with `keylenx == KSUF_KEYLENX`.
    pub unsafe fn split_all_to_right(&self, guard: &LocalGuard<'_>) -> LeafSplitResult<S, WIDTH> {
        let new_leaf: Box<Self> = Self::new();
        let old_perm: Permuter<WIDTH> = self.permutation();
        let old_size: usize = old_perm.size();

        debug_assert!(old_size > 0, "Cannot split empty leaf");

        // Move all entries to new leaf
        for i in 0..old_size {
            let old_slot: usize = old_perm.get(i);

            let keylenx: u8 = self.keylenx(old_slot);

            new_leaf.set_ikey(i, self.ikey(old_slot));
            new_leaf.set_keylenx(i, keylenx);
            new_leaf.set_leaf_value_ptr(i, self.take_leaf_value_ptr(old_slot));

            // FIXED: Migrate suffix if present
            if keylenx == KSUF_KEYLENX {
                if let Some(suffix) = self.ksuf(old_slot) {
                    // SAFETY: guard comes from caller, slot indices are valid
                    unsafe { new_leaf.assign_ksuf(i, suffix, guard) };
                }

                // SAFETY: guard comes from caller, old_slot is valid
                unsafe { self.clear_ksuf(old_slot, guard) };
            }
        }

        // Set new leaf's permutation
        let new_perm: Permuter<WIDTH> = Permuter::make_sorted(old_size);
        new_leaf.set_permutation(new_perm);

        // Clear this leaf's permutation
        self.set_permutation(Permuter::empty());

        // Split key is first key of new leaf
        let split_ikey: u64 = new_leaf.ikey(new_perm.get(0));

        LeafSplitResult {
            new_leaf,
            split_ikey,
            insert_into: InsertTarget::Left,
        }
    }

    // ============================================================================
    //  Invariant Checker
    // ============================================================================

    /// Verify leaf node invariants (debug builds only).
    ///
    /// Checks:
    /// - Permutation is valid
    /// - keylenx values are consistent with lv variants
    /// - ikeys are in sorted order (via permutation)
    ///
    /// # Panics
    /// If any invariant is violated.
    #[cfg(debug_assertions)]
    pub fn debug_assert_invariants(&self) {
        let perm: Permuter<WIDTH> = self.permutation();

        // Check permutation validity
        perm.debug_assert_valid();

        let size: usize = perm.size();

        // Check keylenx/leaf_values consistency for in-use slots
        for i in 0..size {
            let slot: usize = perm.get(i);
            let keylenx: u8 = self.keylenx(slot);
            let ptr: *mut u8 = self.leaf_value_ptr(slot);

            if keylenx >= LAYER_KEYLENX {
                assert!(
                    !ptr.is_null(),
                    "slot {slot} has layer keylenx but null pointer"
                );
            } else if keylenx > 0 {
                assert!(!ptr.is_null(), "slot {slot} has keylenx but null pointer");
            }
        }

        // Check if ikey ordering (if size > 1)
        if size > 1 {
            for i in 1..size {
                let prev_slot: usize = perm.get(i - 1);
                let curr_slot: usize = perm.get(i);

                let prev_ikey: u64 = self.ikey(prev_slot);
                let curr_ikey: u64 = self.ikey(curr_slot);

                assert!(
                    prev_ikey <= curr_ikey,
                    "ikeys are not in sorted order: slot {prev_slot} ({prev_ikey:#x}) > slot {curr_slot} ({curr_ikey:#x})"
                );
            }
        }
    }

    /// No-op in release builds
    #[cfg(not(debug_assertions))]
    #[inline]
    pub fn debug_assert_invariants(&self) {}

    // ============================================================================
    //  Test Helpers
    // ============================================================================

    /// Assign raw values to a slot for testing (including invalid states).
    ///
    /// This allows setting up deliberately inconsistent states to test
    /// invariant checking. NOT for production use.
    #[cfg(test)]
    pub fn assign_raw_for_test(&self, slot: usize, ikey: u64, keylenx: u8, ptr: *mut u8) {
        debug_assert!(slot < WIDTH, "assign_raw_for_test: slot out of bounds");

        self.set_ikey(slot, ikey);
        self.set_keylenx(slot, keylenx);
        self.set_leaf_value_ptr(slot, ptr);
    }
}

// ============================================================================
//  Mode-Specific Convenience Methods
// ============================================================================

/// Arc-mode specific methods for `LeafNode<LeafValue<V>, WIDTH>`.
impl<V, const WIDTH: usize> LeafNode<LeafValue<V>, WIDTH> {
    /// Assign a value, wrapping it in `Arc::new()`.
    ///
    /// Convenience method for Arc mode. For retry-safe inserts that avoid
    /// re-allocating the Arc, use `assign_output` instead.
    ///
    /// # Parameters
    /// - `slot`: Physical slot index
    /// - `ikey`: 8-byte key (big-endian)
    /// - `key_len`: Actual key length (0-8)
    /// - `value`: The value to store (will be wrapped in Arc)
    pub fn assign_value(&self, slot: usize, ikey: u64, key_len: u8, value: V) {
        debug_assert!(slot < WIDTH, "assign_value: slot out of bounds");
        debug_assert!(
            key_len <= 8,
            "assign_value: key_len must be 0-8 for inline keys"
        );

        self.assign_arc(slot, ikey, key_len, Arc::new(value));
    }

    /// Assign an already-Arc-wrapped value.
    ///
    /// Use this when the Arc has already been allocated (e.g., for retry-safe inserts).
    ///
    /// # Parameters
    /// - `slot`: Physical slot index
    /// - `ikey`: 8-byte key (big-endian)
    /// - `key_len`: Actual key length (0-8)
    /// - `arc_value`: The Arc-wrapped value to store
    pub fn assign_arc(&self, slot: usize, ikey: u64, key_len: u8, arc_value: Arc<V>) {
        debug_assert!(slot < WIDTH, "assign_arc: slot out of bounds");
        debug_assert!(
            key_len <= 8,
            "assign_arc: key_len must be 0-8 for inline keys"
        );
        debug_assert!(self.is_slot_empty(slot), "assign_arc: slot not empty");

        self.set_ikey(slot, ikey);
        self.set_keylenx(slot, key_len);

        let ptr: *mut u8 = Arc::into_raw(arc_value).cast_mut().cast::<u8>();
        self.set_leaf_value_ptr(slot, ptr);
    }

    /// Try to atomically claim a slot for insert.
    ///
    /// Uses CAS to ensure only one thread can claim a slot. Both the CAS fast path
    /// and the locked path use this to coordinate slot allocation.
    ///
    /// # Errors
    ///
    /// Returns `Err(arc)` if the slot was already taken by another thread.
    /// The Arc is returned so the caller can retry with a different slot.
    ///
    /// # Protocol
    /// 1. Convert Arc to raw pointer
    /// 2. CAS slot value from NULL to our pointer
    /// 3. If successful, store key data
    /// 4. If failed, reclaim Arc and return it
    #[inline]
    pub fn try_claim_slot(
        &self,
        slot: usize,
        ikey: u64,
        keylenx: u8,
        value: Arc<V>,
    ) -> Result<(), Arc<V>> {
        debug_assert!(slot < WIDTH, "try_claim_slot: slot out of bounds");

        let arc_ptr: *mut u8 = Arc::into_raw(value).cast_mut().cast::<u8>();

        // Try to claim slot atomically (CAS from NULL to our pointer)
        match self.cas_slot_value(slot, std::ptr::null_mut(), arc_ptr) {
            Ok(()) => {
                // We own the slot - store key data
                // SAFETY: We just claimed this slot atomically via CAS
                unsafe {
                    self.store_key_data_for_cas(slot, ikey, keylenx);
                }
                Ok(())
            }
            Err(_) => {
                // Slot already taken - reclaim Arc and return it
                // SAFETY: We just created this Arc from into_raw, nobody else has it
                Err(unsafe { Arc::from_raw(arc_ptr.cast::<V>()) })
            }
        }
    }

    /// Try to clone Arc value from slot.
    ///
    /// # Safety
    /// - Caller must have validated version (or hold lock)
    #[inline(always)]
    pub unsafe fn try_clone_arc(&self, slot: usize) -> Option<Arc<V>> {
        let keylenx = self.keylenx(slot);
        let ptr: *mut u8 = self.leaf_value_ptr(slot);

        if ptr.is_null() || keylenx >= LAYER_KEYLENX {
            return None;
        }

        let arc_ptr: *const V = ptr.cast();
        // SAFETY: ptr is non-null and came from Arc::into_raw in assign_arc/swap_value
        unsafe {
            Arc::increment_strong_count(arc_ptr);
            Some(Arc::from_raw(arc_ptr))
        }
    }

    /// Get a reference to the value at a slot without cloning the Arc.
    ///
    /// This is significantly faster than [`try_clone_arc`] for read-heavy workloads
    /// because it avoids atomic reference count operations.
    ///
    /// # Safety
    ///
    /// - Caller must have validated version (or hold lock)
    /// - Caller must hold a guard that protects the value from being freed
    /// - The returned reference is valid only while the guard is held
    ///
    /// # Returns
    ///
    /// - `Some(&V)` if the slot contains a value
    /// - `None` if the slot is empty or contains a layer pointer
    #[inline(always)]
    pub unsafe fn try_get_value_ref(&self, slot: usize) -> Option<&V> {
        let keylenx = self.keylenx(slot);
        let ptr: *mut u8 = self.leaf_value_ptr(slot);

        if ptr.is_null() || keylenx >= LAYER_KEYLENX {
            return None;
        }

        // SAFETY: ptr is non-null and came from Arc::into_raw in assign_arc/swap_value.
        // The guard held by caller prevents the Arc from being freed.
        // We return a reference to the value inside the Arc, which is valid
        // as long as the Arc exists (guaranteed by the guard).
        let value_ptr: *const V = ptr.cast();
        Some(unsafe { &*value_ptr })
    }

    /// Swap a value at a slot, returning the old Arc.
    ///
    /// # Safety
    /// - Caller must hold lock and have called `mark_insert()`
    /// - `guard` must come from this tree's collector
    #[inline(always)]
    pub unsafe fn swap_value(
        &self,
        slot: usize,
        new_value: Arc<V>,
        guard: &LocalGuard<'_>,
    ) -> Option<Arc<V>> {
        debug_assert!(slot < WIDTH, "swap_value: slot {slot} >= WIDTH {WIDTH}");
        debug_assert!(
            self.keylenx(slot) < LAYER_KEYLENX,
            "swap_value called on Layer slot; layer pointer would be lost"
        );

        let old_ptr: *mut u8 = self.leaf_value_ptr(slot);
        if old_ptr.is_null() {
            self.set_leaf_value_ptr(slot, Arc::into_raw(new_value).cast_mut().cast::<u8>());
            return None;
        }

        // SAFETY: old_ptr is non-null and came from Arc::into_raw in assign_arc/swap_value
        let old_arc_ptr: *const V = old_ptr.cast();
        let old_arc = unsafe {
            Arc::increment_strong_count(old_arc_ptr);
            Arc::from_raw(old_arc_ptr)
        };

        let new_ptr: *mut u8 = Arc::into_raw(new_value).cast_mut().cast::<u8>();
        self.set_leaf_value_ptr(slot, new_ptr);

        let keylenx: u8 = self.keylenx(slot);
        self.set_keylenx(slot, keylenx);

        // SAFETY: old_ptr is non-null and came from Arc::into_raw
        unsafe {
            guard.defer_retire(old_ptr.cast::<V>(), |ptr, _| {
                drop(Arc::from_raw(ptr));
            });
        }

        Some(old_arc)
    }
}

/// Inline-mode specific methods for `LeafNode<LeafValueIndex<V>, WIDTH>`.
impl<V: Copy, const WIDTH: usize> LeafNode<LeafValueIndex<V>, WIDTH> {
    /// Assign a value directly (inline storage).
    ///
    /// # Parameters
    /// - `slot`: Physical slot index
    /// - `ikey`: 8-byte key (big-endian)
    /// - `key_len`: Actual key length (0-8)
    /// - `value`: The value to store (copied directly)
    pub fn assign_inline(&self, slot: usize, ikey: u64, key_len: u8, value: V) {
        debug_assert!(slot < WIDTH, "assign_inline: slot out of bounds");
        debug_assert!(
            key_len <= 8,
            "assign_inline: key_len must be 0-8 for inline keys"
        );

        self.set_ikey(slot, ikey);
        self.set_keylenx(slot, key_len);

        let ptr: *mut u8 = Box::into_raw(Box::new(value)).cast::<V>().cast::<u8>();
        self.set_leaf_value_ptr(slot, ptr);
    }

    /// Swap a value at a slot, returning the old value.
    ///
    /// This is a specialized hot-path method that avoids trait dispatch
    /// by working directly with `LeafValueIndex<V>`.
    ///
    /// # Panics
    /// Debug-panics if slot is out of bounds or contains a layer pointer.
    #[inline(always)]
    #[expect(clippy::indexing_slicing, reason = "bounds checked via debug_assert")]
    pub fn swap_inline(&self, slot: usize, new_value: V) -> Option<V> {
        debug_assert!(slot < WIDTH, "swap_inline: slot {slot} >= WIDTH {WIDTH}");
        debug_assert!(
            self.keylenx(slot) < LAYER_KEYLENX,
            "swap_inline called on Layer slot; layer pointer would be lost"
        );

        let new_ptr: *mut u8 = Box::into_raw(Box::new(new_value)).cast::<V>().cast::<u8>();
        let old_ptr: *mut u8 = self.leaf_values[slot].swap(new_ptr, WRITE_ORD);
        if old_ptr.is_null() {
            return None;
        }

        // SAFETY: old_ptr came from Box::into_raw
        let old_value: V = unsafe { old_ptr.cast::<V>().read() };
        unsafe { drop(Box::from_raw(old_ptr.cast::<V>())) };

        Some(old_value)
    }
}

impl<S: ValueSlot, const WIDTH: usize> Default for LeafNode<S, WIDTH> {
    fn default() -> Self {
        // Trigger compile-time WIDTH check
        let _: () = Self::WIDTH_CHECK;

        Self {
            version: NodeVersion::new(true),
            modstate: ModState::Insert,
            permutation: AtomicU64::new(Permuter::<WIDTH>::empty().value()),
            ikey0: StdArray::from_fn(|_| AtomicU64::new(0)),
            keylenx: StdArray::from_fn(|_| AtomicU8::new(0)),
            leaf_values: StdArray::from_fn(|_| AtomicPtr::new(StdPtr::null_mut())),
            ksuf: AtomicPtr::new(StdPtr::null_mut()),
            next: AtomicPtr::new(StdPtr::null_mut()),
            prev: AtomicPtr::new(StdPtr::null_mut()),
            parent: AtomicPtr::new(StdPtr::null_mut()),
            _marker: PhantomData,
        }
    }
}

impl<S: ValueSlot, const WIDTH: usize> Drop for LeafNode<S, WIDTH> {
    #[expect(
        clippy::indexing_slicing,
        reason = "slot iterates 0..WIDTH which matches array size"
    )]
    fn drop(&mut self) {
        for slot in 0..WIDTH {
            let ptr: *mut u8 = self.leaf_values[slot].load(RELAXED);
            if ptr.is_null() {
                continue;
            }

            let keylenx: u8 = self.keylenx[slot].load(RELAXED);
            if keylenx < LAYER_KEYLENX {
                // SAFETY: ptr came from the slot type's storage method
                // (Arc::into_raw for LeafValue, Box::into_raw for LeafValueIndex).
                // We only cleanup non-layer slots (keylenx < LAYER_KEYLENX).
                unsafe {
                    S::cleanup_value_ptr(ptr);
                }
            }
            // Note: Layer pointers are owned by the tree and cleaned up
            // during tree teardown, not here.
        }

        let ksuf_ptr: *mut SuffixBag<WIDTH> = self.ksuf.load(RELAXED);
        if !ksuf_ptr.is_null() {
            // SAFETY: ksuf_ptr came from Box::into_raw in assign_ksuf.
            unsafe {
                drop(Box::from_raw(ksuf_ptr));
            }
        }
    }
}

// ============================================================================
//  Type Aliases
// ============================================================================

/// Arc-based leaf node with standard 15 slots.
///
/// This is the default storage mode where values are wrapped in `Arc<V>`.
/// Use this for general-purpose key-value storage.
pub type ArcLeafNode<V, const WIDTH: usize = 15> = LeafNode<LeafValue<V>, WIDTH>;

/// Inline leaf node with standard 15 slots.
///
/// This is the index mode where `V: Copy` values are stored directly.
/// Use this for small, copyable values like `u64`, handles, or pointers.
pub type InlineLeafNode<V, const WIDTH: usize = 15> = LeafNode<LeafValueIndex<V>, WIDTH>;

/// Standard 15-slot leaf node (default mode with Arc<V>).
///
/// Alias for backwards compatibility.
pub type LeafNode15<V> = ArcLeafNode<V, 15>;

/// Compact 7-slot leaf node (fits in ~2 cache lines with small V).
///
/// Alias for backwards compatibility.
pub type LeafNodeCompact<V> = ArcLeafNode<V, 7>;

// ============================================================================
//  Compile-time Size Assertions
// ============================================================================

/// Compile-time size check for `ArcLeafNode<u64, 15>`.
/// Should be around 448 bytes (7 cache lines) after alignment.
///
/// The enum discriminant adds overhead compared to C++ union approach, but keeps
/// type safety. `LeafValue<u64>` is 16 bytes (Arc ptr + discriminant).
const _: () = {
    // Compile-time assertion: ensure node stays cache-friendly
    const SIZE: usize = StdMem::size_of::<ArcLeafNode<u64, 15>>();
    const ALIGN: usize = StdMem::align_of::<ArcLeafNode<u64, 15>>();

    // Should fit in 8 cache lines (512 bytes) at most
    assert!(SIZE <= 512, "ArcLeafNode exceeds 8 cache lines");

    // Should be cache-aligned
    assert!(ALIGN == 64, "ArcLeafNode not cache-line-aligned");
};

/// Compile-time size check for `InlineLeafNode<u64, 15>`.
const _: () = {
    const SIZE: usize = StdMem::size_of::<InlineLeafNode<u64, 15>>();
    const ALIGN: usize = StdMem::align_of::<InlineLeafNode<u64, 15>>();

    // Inline mode should be smaller since there's no Arc pointer
    assert!(SIZE <= 512, "InlineLeafNode exceeds 8 cache lines");
    assert!(ALIGN == 64, "InlineLeafNode not cache-line-aligned");
};

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

    // ============================================================================
    //  Basic Tests
    // ============================================================================

    #[test]
    fn test_leaf_value_empty() {
        let lv: LeafValue<u64> = LeafValue::empty();
        assert!(lv.is_empty());
        assert!(!lv.is_value());
        assert!(!lv.is_layer());
    }

    #[test]
    fn test_leaf_value_value() {
        let lv: LeafValue<u64> = LeafValue::Value(Arc::new(42));
        assert!(!lv.is_empty());
        assert!(lv.is_value());
        assert!(!lv.is_layer());
        assert_eq!(**lv.as_value(), 42); // Double deref: &Arc<u64> -> u64

        // Test clone_arc
        let cloned: Arc<u64> = lv.clone_arc();

        assert_eq!(*cloned, 42);
        assert_eq!(Arc::strong_count(&cloned), 2); // Original + clone
    }

    #[test]
    fn test_leaf_value_layer() {
        //  FIXED: Use a real allocation to get a pointer with valid provenance
        let boxed: Box<u8> = Box::new(0xBE);
        let ptr: *mut u8 = Box::into_raw(boxed);

        let lv: LeafValue<u64> = LeafValue::Layer(ptr);

        assert!(!lv.is_empty());
        assert!(!lv.is_value());
        assert!(lv.is_layer());
        assert_eq!(lv.as_layer(), ptr);

        // Clean up the allocation
        //  SAFETY: ptr came from Box::into_raw above
        unsafe { drop(Box::from_raw(ptr)) };
    }

    #[test]
    fn test_leaf_node_linking() {
        let left: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let right: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // Get raw pointers before linking
        let left_ptr: *mut ArcLeafNode<u64, 15> = StdPtr::from_ref(left.as_ref()).cast_mut();
        let right_ptr: *mut ArcLeafNode<u64, 15> = StdPtr::from_ref(right.as_ref()).cast_mut();

        // Link them
        unsafe {
            assert!(left.link_split(right_ptr));
        }
        assert_eq!(left.safe_next(), right_ptr);
        assert_eq!(right.prev(), left_ptr);
        assert!(right.safe_next().is_null());
    }

    #[test]
    fn test_leaf_node_new() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        assert!(node.version().is_leaf());
        assert_eq!(node.size(), 0);
        assert!(node.is_empty());
        assert!(!node.is_full());
        assert!(node.safe_next().is_null());
        assert!(node.prev().is_null());
        assert!(node.parent().is_null());
    }

    #[test]
    fn test_leaf_node_new_root() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new_root();

        assert!(node.version().is_leaf());
        assert!(node.version().is_root());
    }

    #[test]
    #[expect(clippy::expect_used, reason = "Test code - panics are acceptable")]
    fn test_leaf_node_assign() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // Assign to slot 0 (value is wrapped in Arc internally)
        node.assign_value(0, 0x1234_5678_0000_0000, 4, 100);

        assert_eq!(node.ikey(0), 0x1234_5678_0000_0000);
        assert_eq!(node.keylenx(0), 4);
        // Test clone_arc for optimistic reads
        let cloned: Arc<u64> = unsafe { node.try_clone_arc(0) }.expect("value missing");
        assert_eq!(*cloned, 100);
    }

    #[test]
    fn test_leaf_node_permutation() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // Initially empty
        assert_eq!(node.permutation().size(), 0);

        // Set a permutation with 3 elements
        let perm: Permuter<15> = Permuter::make_sorted(3);
        node.set_permutation(perm);

        assert_eq!(node.size(), 3);
        assert!(!node.is_empty());
        assert!(!node.is_full());
    }

    #[test]
    fn test_safe_next_masks_mark() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // Use a real allocation to get valid provenance
        let other_node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let fake_next: *mut ArcLeafNode<u64, 15> = Box::into_raw(other_node);

        node.set_next(fake_next);
        assert_eq!(node.safe_next(), fake_next);
        assert!(!node.next_is_marked());

        node.mark_next();
        assert!(node.next_is_marked());
        assert_eq!(node.safe_next(), fake_next); // Mark bit masked off

        node.unmark_next();
        assert!(!node.next_is_marked());

        // Clean up the allocation
        // SAFETY: fake_next came from Box::into_raw above
        unsafe { drop(Box::from_raw(fake_next)) };
    }

    #[test]
    fn test_keylenx_helpers() {
        assert!(!ArcLeafNode::<u64>::keylenx_is_layer(0));
        assert!(!ArcLeafNode::<u64>::keylenx_is_layer(8));
        assert!(!ArcLeafNode::<u64>::keylenx_is_layer(64));
        assert!(!ArcLeafNode::<u64>::keylenx_is_layer(127));
        assert!(ArcLeafNode::<u64>::keylenx_is_layer(128));
        assert!(ArcLeafNode::<u64>::keylenx_is_layer(255));

        assert!(!ArcLeafNode::<u64>::keylenx_has_ksuf(0));
        assert!(!ArcLeafNode::<u64>::keylenx_has_ksuf(8));
        assert!(ArcLeafNode::<u64>::keylenx_has_ksuf(64));
        assert!(!ArcLeafNode::<u64>::keylenx_has_ksuf(128));
    }

    #[test]
    fn test_compact_leaf_node() {
        let node: Box<LeafNodeCompact<u64>> = LeafNode::new();

        assert_eq!(node.size(), 0);
        // Compact node should work the same way
    }

    #[test]
    fn test_ikey_bound() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // ikey_bound returns ikey0[0] - use assign_value to set it
        node.assign_value(0, 0xABCD_0000_0000_0000, 4, 42);
        assert_eq!(node.ikey_bound(), 0xABCD_0000_0000_0000);
    }

    #[test]
    fn test_modstate() {
        let mut node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        assert_eq!(node.modstate(), ModState::Insert);

        node.set_modstate(ModState::Remove);
        assert_eq!(node.modstate(), ModState::Remove);

        node.set_modstate(ModState::DeletedLayer);
        assert_eq!(node.modstate(), ModState::DeletedLayer);
    }

    // ============================================================================
    //  WIDTH Edge Cases
    // ============================================================================

    #[test]
    fn test_width_1_node() {
        let node: Box<ArcLeafNode<u64, 1>> = ArcLeafNode::new();

        assert_eq!(node.size(), 0);
        assert!(node.is_empty());
        assert!(!node.is_full());

        // Verify single-slot operations work
        assert_eq!(node.ikey(0), 0);
        assert_eq!(node.keylenx(0), 0);
    }

    #[test]
    fn test_width_15_full() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let perm = Permuter::make_sorted(15);
        node.set_permutation(perm);

        assert_eq!(node.size(), 15);
        assert!(!node.is_empty());
        assert!(node.is_full());
    }

    // ============================================================================
    //  Invariant Tests
    // ============================================================================

    #[test]
    #[should_panic(expected = "ikeys are not in sorted order")]
    #[cfg(debug_assertions)]
    fn test_invariant_unsorted_ikeys() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // Set up unsorted keys
        node.assign_value(0, 0x2000_0000_0000_0000, 2, 200);
        node.assign_value(1, 0x1000_0000_0000_0000, 2, 100);

        let mut perm = Permuter::empty();
        let _ = perm.insert_from_back(0); // slot 0 at logical pos 0
        let _ = perm.insert_from_back(1); // slot 1 at logical pos 1 (but ikey[1] < ikey[0]!)
        node.set_permutation(perm);

        node.debug_assert_invariants(); // Should panic
    }

    #[test]
    #[should_panic(expected = "has layer keylenx but null pointer")]
    #[cfg(debug_assertions)]
    fn test_invariant_layer_mismatch() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // Set keylenx to indicate layer but leave pointer null (invalid)
        node.assign_raw_for_test(0, 0x1000_0000_0000_0000, LAYER_KEYLENX, StdPtr::null_mut());

        let mut perm = Permuter::empty();
        let _ = perm.insert_from_back(0);
        node.set_permutation(perm);

        node.debug_assert_invariants(); // Should panic
    }

    #[test]
    fn test_invariant_valid_node() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // Set up correctly sorted keys
        node.assign_value(0, 0x1000_0000_0000_0000, 2, 100);
        node.assign_value(1, 0x2000_0000_0000_0000, 2, 200);
        node.assign_value(2, 0x3000_0000_0000_0000, 2, 300);

        let mut perm = Permuter::empty();
        let _ = perm.insert_from_back(0); // slot 0
        let _ = perm.insert_from_back(1); // slot 1
        let _ = perm.insert_from_back(2); // slot 2
        node.set_permutation(perm);

        // Should not panic
        node.debug_assert_invariants();
    }

    // ============================================================================
    //  LeafValueIndex Tests (Index Mode)
    // ============================================================================

    #[test]
    fn test_leaf_value_index_empty() {
        let lv: LeafValueIndex<u64> = LeafValueIndex::empty();
        assert!(lv.is_empty());
        assert!(!lv.is_value());
        assert!(!lv.is_layer());
    }

    #[test]
    fn test_leaf_value_index_value() {
        let lv: LeafValueIndex<u64> = LeafValueIndex::Value(42);
        assert!(!lv.is_empty());
        assert!(lv.is_value());
        assert!(!lv.is_layer());
        assert_eq!(lv.value(), 42); // Direct copy, no Arc

        // Copy semantics
        let copied: u64 = lv.value();
        assert_eq!(copied, 42);
    }

    #[test]
    fn test_leaf_value_index_layer() {
        // Use a real allocation to get a pointer with valid provenance
        let boxed: Box<u8> = Box::new(0xBE);
        let ptr: *mut u8 = Box::into_raw(boxed);

        let lv: LeafValueIndex<u64> = LeafValueIndex::Layer(ptr);

        assert!(!lv.is_empty());
        assert!(!lv.is_value());
        assert!(lv.is_layer());
        assert_eq!(lv.as_layer(), ptr);

        // Clean up the allocation
        // SAFETY: ptr came from Box::into_raw above
        unsafe { drop(Box::from_raw(ptr)) };
    }

    #[test]
    fn test_leaf_value_index_is_copy() {
        // LeafValueIndex<V: Copy> should itself be Copy
        let lv: LeafValueIndex<u64> = LeafValueIndex::Value(42);
        let lv2: LeafValueIndex<u64> = lv; // Copy, not move

        assert_eq!(lv.value(), 42);
        assert_eq!(lv2.value(), 42);
    }

    // ============================================================================
    //  Suffix Storage Tests
    // ============================================================================

    #[test]
    fn test_suffix_not_allocated_initially() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        assert!(!node.has_ksuf_storage());
        assert!(node.ksuf(0).is_none());
    }

    #[test]
    fn test_assign_ksuf_lazy_init() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let collector = Collector::new();
        let guard = collector.enter();

        // Before assignment, no storage
        assert!(!node.has_ksuf_storage());

        // Assign suffix to slot 0
        unsafe { node.assign_ksuf(0, b"suffix_data", &guard) };

        // Now storage exists
        assert!(node.has_ksuf_storage());
        assert!(node.has_ksuf(0));
        assert_eq!(node.ksuf(0), Some(b"suffix_data".as_slice()));
    }

    #[test]
    fn test_ksuf_equals() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let collector = Collector::new();
        let guard = collector.enter();
        unsafe { node.assign_ksuf(0, b"hello", &guard) };

        assert!(node.ksuf_equals(0, b"hello"));
        assert!(!node.ksuf_equals(0, b"world"));
        assert!(!node.ksuf_equals(1, b"hello")); // Slot 1 has no suffix
    }

    #[test]
    fn test_ksuf_compare() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let collector = Collector::new();
        let guard = collector.enter();
        unsafe { node.assign_ksuf(0, b"hello", &guard) };

        assert_eq!(
            node.ksuf_compare(0, b"hello"),
            Some(std::cmp::Ordering::Equal)
        );
        assert_eq!(
            node.ksuf_compare(0, b"hella"),
            Some(std::cmp::Ordering::Greater)
        );
        assert_eq!(
            node.ksuf_compare(0, b"hellz"),
            Some(std::cmp::Ordering::Less)
        );
        assert_eq!(node.ksuf_compare(1, b"hello"), None);
    }

    #[test]
    fn test_ksuf_matches() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let collector = Collector::new();
        let guard = collector.enter();

        // Assign ikey and suffix to slot 0
        node.set_ikey(0, 0x1234_5678_0000_0000);
        unsafe { node.assign_ksuf(0, b"suffix", &guard) };

        // Full match
        assert!(node.ksuf_matches(0, 0x1234_5678_0000_0000, b"suffix"));

        // Wrong ikey
        assert!(!node.ksuf_matches(0, 0xABCD_0000_0000_0000, b"suffix"));

        // Wrong suffix
        assert!(!node.ksuf_matches(0, 0x1234_5678_0000_0000, b"other"));
    }

    #[test]
    fn test_ksuf_matches_no_suffix() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();

        // Assign just ikey (no suffix)
        node.set_ikey(0, 0x1234_5678_0000_0000);
        node.set_keylenx(0, 4); // Regular key length, not KSUF_KEYLENX

        // Should match when suffix is empty
        assert!(node.ksuf_matches(0, 0x1234_5678_0000_0000, b""));

        // Should NOT match when suffix is non-empty
        assert!(!node.ksuf_matches(0, 0x1234_5678_0000_0000, b"suffix"));
    }

    #[test]
    fn test_clear_ksuf() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let collector = Collector::new();
        let guard = collector.enter();
        unsafe { node.assign_ksuf(0, b"test", &guard) };

        assert!(node.has_ksuf(0));

        unsafe { node.clear_ksuf(0, &guard) };

        assert!(!node.has_ksuf(0));
        assert!(node.ksuf(0).is_none());
    }

    #[test]
    fn test_ksuf_or_empty() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let collector = Collector::new();
        let guard = collector.enter();
        unsafe { node.assign_ksuf(0, b"data", &guard) };

        assert_eq!(node.ksuf_or_empty(0), b"data".as_slice());
        assert_eq!(node.ksuf_or_empty(1), b"".as_slice());
    }

    #[test]
    fn test_compact_ksuf() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let collector = Collector::new();
        let guard = collector.enter();

        // Assign suffixes to multiple slots
        unsafe {
            node.assign_ksuf(0, b"slot0", &guard);
            node.assign_ksuf(1, b"slot1", &guard);
            node.assign_ksuf(2, b"slot2", &guard);
        }

        // Set up permutation to only include slots 0 and 2
        node.set_permutation(Permuter::make_sorted(2));
        // This makes positions 0→slot0, 1→slot1 active, but we want 0 and 2
        // For this test, let's just check compaction works
        let reclaimed = unsafe { node.compact_ksuf(None, &guard) };

        // Compaction should have run (even if nothing reclaimed in this simple case)
        assert!(node.has_ksuf_storage());
        // The exact bytes reclaimed depends on which slots are active
        let _ = reclaimed;
    }

    #[test]
    fn test_multiple_suffixes() {
        let node: Box<ArcLeafNode<u64, 15>> = ArcLeafNode::new();
        let collector = Collector::new();
        let guard = collector.enter();

        unsafe {
            node.assign_ksuf(0, b"first", &guard);
            node.assign_ksuf(5, b"middle", &guard);
            node.assign_ksuf(14, b"last", &guard);
        }

        assert_eq!(node.ksuf(0), Some(b"first".as_slice()));
        assert_eq!(node.ksuf(5), Some(b"middle".as_slice()));
        assert_eq!(node.ksuf(14), Some(b"last".as_slice()));
        assert_eq!(node.ksuf(1), None);
    }
}
