zipora 4.1.0

//! FastVec: High-performance vector using realloc for growth
//!
//! This is a direct port of the C++ `valvec` with Rust safety guarantees.
//! Unlike std::Vec which uses malloc+memcpy for growth, FastVec uses realloc
//! which can often avoid copying when the allocator can expand in place.

use crate::error::{Result, ZiporaError};
use crate::memory::simd_ops::{fast_copy, fast_fill};
use crate::simd::{AdaptiveSimdSelector, Operation};
use std::alloc::{self, Layout};
use std::mem;
use std::ptr::{self, NonNull};
use std::slice;
use std::time::Instant;

/// Check that a pointer is properly aligned for type T
#[inline]
fn check_alignment<T>(ptr: *mut u8) {
    debug_assert!(!ptr.is_null());
    debug_assert!((ptr as usize).is_multiple_of(mem::align_of::<T>()));
}

/// Safely cast an aligned u8 pointer to T pointer with alignment verification
#[inline]
fn cast_aligned_ptr<T>(ptr: *mut u8) -> *mut T {
    check_alignment::<T>(ptr);
    ptr as *mut T
}

/// Check if a type is suitable for SIMD operations (Copy + no custom drop)
#[inline]
const fn is_simd_safe<T>() -> bool {
    // Use const traits when available, for now rely on Copy bound in caller
    !mem::needs_drop::<T>()
}

/// Check if an operation size is large enough to benefit from SIMD
#[inline]
const fn is_simd_beneficial<T>(element_count: usize) -> bool {
    // SIMD beneficial threshold: 64 bytes minimum
    const SIMD_THRESHOLD: usize = 64;
    element_count * mem::size_of::<T>() >= SIMD_THRESHOLD
}

/// Prefetch distance for lookahead operations (based on successful patterns)
/// Matches the PREFETCH_DISTANCE=8 pattern from RankSelectInterleaved256
const PREFETCH_DISTANCE: usize = 8;

/// Prefetch utilities for FastVec operations
struct PrefetchOps;

impl PrefetchOps {
    /// Prefetch memory location for reading with cache hints
    #[inline]
    fn prefetch_read<T>(ptr: *const T) {
        #[cfg(target_arch = "x86_64")]
        // SAFETY: _mm_prefetch is always safe - it's a hint that can be ignored; ptr validity checked by caller
        unsafe {
            std::arch::x86_64::_mm_prefetch(ptr as *const i8, std::arch::x86_64::_MM_HINT_T0);
        }

        #[cfg(target_arch = "aarch64")]
        // SAFETY: prfm is always safe - it's a prefetch hint that can be ignored; ptr validity checked by caller
        unsafe {
            // ARM64 PRFM PLDL1KEEP - prefetch for load to L1 cache, temporal
            std::arch::asm!(
                "prfm pldl1keep, [{0}]",
                in(reg) ptr,
                options(nostack, preserves_flags, readonly)
            );
        }

        #[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
        {
            // Compiler hint for other architectures
            std::hint::black_box(ptr);
        }
    }

    /// Prefetch range of memory with stride
    #[inline]
    fn prefetch_range<T>(start: *const T, count: usize, distance: usize) {
        if count <= distance {
            return;
        }

        // Prefetch using cache line strides
        const CACHE_LINE_SIZE: usize = 64;
        let element_size = mem::size_of::<T>();
        let elements_per_line = (CACHE_LINE_SIZE / element_size).max(1);

        for i in (0..count).step_by(elements_per_line) {
            if i + distance < count {
                // SAFETY: i + distance < count guaranteed by check at line 100
                unsafe {
                    Self::prefetch_read(start.add(i + distance));
                }
            }
        }
    }
}

/// Convert a slice of T to a slice of u8 for SIMD operations
///
/// # Safety
///
/// T must be Copy and have no custom Drop implementation
#[inline]
unsafe fn slice_as_bytes<T>(slice: &[T]) -> &[u8] {
    if slice.is_empty() {
        &[]
    } else {
        // SAFETY: slice pointer valid by reference, length computed from valid slice length * size_of::<T>()
        unsafe { slice::from_raw_parts(slice.as_ptr() as *const u8, std::mem::size_of_val(slice)) }
    }
}

/// Convert a mutable slice of T to a mutable slice of u8 for SIMD operations
///
/// # Safety
///
/// T must be Copy and have no custom Drop implementation
#[inline]
unsafe fn slice_as_bytes_mut<T>(slice: &mut [T]) -> &mut [u8] {
    if slice.is_empty() {
        &mut []
    } else {
        // SAFETY: slice pointer valid by mutable reference, length computed from valid slice length * size_of::<T>()
        unsafe {
            slice::from_raw_parts_mut(slice.as_mut_ptr() as *mut u8, std::mem::size_of_val(slice))
        }
    }
}

/// High-performance vector using realloc for growth
///
/// FastVec is designed for maximum performance when dealing with types that are
/// memmove-safe (most primitive types and simple structs). It uses realloc()
/// for growth which can avoid memory copying in many cases.
///
/// # Safety
///
/// FastVec is safe to use with any type T, but performs best with types that
/// are `Copy` or have trivial move semantics.
///
/// # Examples
///
/// ```rust
/// use zipora::FastVec;
///
/// let mut vec = FastVec::new();
/// vec.push(42);
/// vec.push(84);
/// assert_eq!(vec.len(), 2);
/// assert_eq!(vec[0], 42);
/// ```
pub struct FastVec<T> {
    ptr: Option<NonNull<T>>,
    len: usize,
    cap: usize,
}

impl<T> FastVec<T> {
    /// Create a new empty FastVec
    #[inline]
    pub fn new() -> Self {
        Self {
            ptr: None,
            len: 0,
            cap: 0,
        }
    }

    /// Create a FastVec with the specified capacity
    pub fn with_capacity(cap: usize) -> Result<Self> {
        // ZST: passing a zero-size Layout to alloc is UB per the GlobalAlloc
        // contract. A dangling aligned pointer is valid for all ZST accesses,
        // and capacity is virtually unlimited since elements occupy no memory.
        if mem::size_of::<T>() == 0 {
            return Ok(Self {
                ptr: Some(NonNull::dangling()),
                len: 0,
                cap: usize::MAX,
            });
        }

        if cap == 0 {
            return Ok(Self::new());
        }

        if cap > (isize::MAX as usize) / mem::size_of::<T>().max(1) {
            return Err(ZiporaError::out_of_memory(cap * mem::size_of::<T>()));
        }

        let layout = Layout::array::<T>(cap)
            .map_err(|_| ZiporaError::out_of_memory(cap * mem::size_of::<T>()))?;

        // SAFETY: alloc::alloc returns valid pointer for non-zero layout
        let ptr = unsafe {
            let raw_ptr = alloc::alloc(layout);
            if raw_ptr.is_null() {
                return Err(ZiporaError::out_of_memory(layout.size()));
            }
            cast_aligned_ptr::<T>(raw_ptr)
        };

        Ok(Self {
            // SAFETY: ptr is non-null after successful allocation verified at line 207
            ptr: Some(unsafe { NonNull::new_unchecked(ptr) }),
            len: 0,
            cap,
        })
    }

    /// Create a FastVec with zeroed memory using `alloc_zeroed` (maps to `calloc`).
    ///
    /// For large allocations, `calloc` leverages kernel zero-page mapping,
    /// avoiding physical zeroing entirely. This makes it significantly faster
    /// than `alloc` + `memset` for zero-initialized buffers.
    ///
    /// The returned vector has `len == cap` — all elements are zero-initialized.
    ///
    /// `T: bytemuck::Zeroable` guarantees the all-zero byte pattern is a valid
    /// value, so this is sound for any `T` that compiles (types with non-zero
    /// invariants like `String` or `Box<T>` are rejected at compile time).
    pub fn with_capacity_zeroed(cap: usize) -> Result<Self>
    where
        T: bytemuck::Zeroable,
    {
        // ZST: no memory to zero; all `cap` elements trivially exist.
        // See with_capacity for why alloc must not be called with size 0.
        if mem::size_of::<T>() == 0 {
            return Ok(Self {
                ptr: Some(NonNull::dangling()),
                len: cap,
                cap: usize::MAX,
            });
        }

        if cap == 0 {
            return Ok(Self::new());
        }

        if cap > (isize::MAX as usize) / mem::size_of::<T>().max(1) {
            return Err(ZiporaError::out_of_memory(cap * mem::size_of::<T>()));
        }

        let layout = Layout::array::<T>(cap)
            .map_err(|_| ZiporaError::out_of_memory(cap * mem::size_of::<T>()))?;

        // SAFETY: alloc_zeroed returns zeroed memory; calloc kernel optimization
        // avoids physical zeroing for large allocations via zero-page mapping.
        let ptr = unsafe {
            let raw_ptr = alloc::alloc_zeroed(layout);
            if raw_ptr.is_null() {
                return Err(ZiporaError::out_of_memory(layout.size()));
            }
            cast_aligned_ptr::<T>(raw_ptr)
        };

        Ok(Self {
            // SAFETY: ptr is non-null after successful allocation
            ptr: Some(unsafe { NonNull::new_unchecked(ptr) }),
            len: cap, // all elements are valid (zeroed)
            cap,
        })
    }

    /// Create a FastVec by taking ownership of a `Vec<T>` without copying.
    ///
    /// The Vec's buffer is transferred to FastVec. The original Vec is consumed.
    pub fn from_vec(vec: Vec<T>) -> Self {
        let mut vec = std::mem::ManuallyDrop::new(vec);
        let ptr = vec.as_mut_ptr();
        let len = vec.len();
        let cap = vec.capacity();

        Self {
            ptr: NonNull::new(ptr),
            len,
            cap,
        }
    }

    /// Create a FastVec with the specified size, filled with the given value
    pub fn with_size(size: usize, value: T) -> Result<Self>
    where
        T: Clone,
    {
        let mut vec = Self::with_capacity(size)?;
        vec.resize(size, value)?;
        Ok(vec)
    }

    /// Get the number of elements in the vector
    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

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

    /// Get the capacity of the vector
    #[inline]
    pub fn capacity(&self) -> usize {
        self.cap
    }

    /// Get a pointer to the underlying data
    #[inline]
    pub fn as_ptr(&self) -> *const T {
        match self.ptr {
            Some(ptr) => ptr.as_ptr(),
            None => ptr::null(),
        }
    }

    /// Get a mutable pointer to the underlying data
    #[inline]
    pub fn as_mut_ptr(&mut self) -> *mut T {
        match self.ptr {
            Some(ptr) => ptr.as_ptr(),
            None => ptr::null_mut(),
        }
    }

    /// Set length without dropping or allocating
    ///
    /// # Safety
    ///
    /// - `new_len` must be less than or equal to `capacity()`.
    /// - The elements at `old_len..new_len` must be initialized.
    #[inline]
    pub unsafe fn set_len(&mut self, new_len: usize) {
        debug_assert!(new_len <= self.cap);
        self.len = new_len;
    }

    /// Get the vector as a slice
    #[inline]
    pub fn as_slice(&self) -> &[T] {
        // Branch-free: when len==0, from_raw_parts with a dangling aligned
        // pointer and length 0 is safe. When len>0, ptr is always Some.
        // SAFETY: ptr is valid+aligned when len > 0 (allocation invariant).
        // When len == 0, dangling() provides aligned non-null pointer.
        unsafe { slice::from_raw_parts(self.ptr.unwrap_or(NonNull::dangling()).as_ptr(), self.len) }
    }

    /// Get the vector as a mutable slice
    #[inline(always)]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        // SAFETY: same as as_slice — dangling pointer with len=0 is safe.
        unsafe {
            slice::from_raw_parts_mut(self.ptr.unwrap_or(NonNull::dangling()).as_ptr(), self.len)
        }
    }

    /// Reserve space for at least `additional` more elements
    pub fn reserve(&mut self, additional: usize) -> Result<()> {
        if additional > (isize::MAX as usize) / mem::size_of::<T>().max(1) {
            return Err(ZiporaError::out_of_memory(additional * mem::size_of::<T>()));
        }

        let required = self
            .len
            .checked_add(additional)
            .ok_or_else(|| ZiporaError::out_of_memory(usize::MAX))?;

        if required <= self.cap {
            return Ok(());
        }

        self.realloc(required)
    }

    /// Ensure the vector has at least the specified capacity
    pub fn ensure_capacity(&mut self, min_cap: usize) -> Result<()> {
        if min_cap > (isize::MAX as usize) / mem::size_of::<T>().max(1) {
            return Err(ZiporaError::out_of_memory(min_cap * mem::size_of::<T>()));
        }
        debug_assert!(min_cap >= self.len);

        if min_cap <= self.cap {
            return Ok(());
        }

        self.realloc(min_cap)
    }

    /// Reallocate to the new capacity using realloc for optimal performance
    fn realloc(&mut self, new_cap: usize) -> Result<()> {
        debug_assert!(new_cap >= self.len);

        // ZST: capacity is virtual — never call alloc/realloc with a
        // zero-size Layout (UB per the GlobalAlloc contract).
        if mem::size_of::<T>() == 0 {
            self.ptr = Some(NonNull::dangling());
            self.cap = usize::MAX;
            return Ok(());
        }

        if new_cap > (isize::MAX as usize) / mem::size_of::<T>().max(1) {
            return Err(ZiporaError::out_of_memory(new_cap * mem::size_of::<T>()));
        }

        // Use exponential growth with a minimum increase
        let target_cap = new_cap.max(self.cap.saturating_mul(2));

        let new_layout = Layout::array::<T>(target_cap)
            .map_err(|_| ZiporaError::out_of_memory(target_cap * mem::size_of::<T>()))?;

        let new_ptr = match self.ptr {
            Some(ptr) => {
                if self.cap == 0 {
                    // This shouldn't happen, but handle it safely
                    // SAFETY: alloc returns valid pointer or null; cast_aligned_ptr checks alignment
                    unsafe {
                        let raw_ptr = alloc::alloc(new_layout);
                        if raw_ptr.is_null() {
                            std::ptr::null_mut()
                        } else {
                            cast_aligned_ptr::<T>(raw_ptr)
                        }
                    }
                } else {
                    let old_layout = Layout::array::<T>(self.cap)
                        .map_err(|_| ZiporaError::out_of_memory(self.cap * mem::size_of::<T>()))?;
                    // SAFETY: ptr from self.ptr valid allocation, old_layout matches original allocation, new_layout.size() >= old_layout.size()
                    unsafe {
                        let raw_ptr =
                            alloc::realloc(ptr.as_ptr() as *mut u8, old_layout, new_layout.size());
                        if raw_ptr.is_null() {
                            std::ptr::null_mut()
                        } else {
                            cast_aligned_ptr::<T>(raw_ptr)
                        }
                    }
                }
            }
            // SAFETY: alloc returns valid pointer or null; cast_aligned_ptr checks alignment
            None => unsafe {
                let raw_ptr = alloc::alloc(new_layout);
                if raw_ptr.is_null() {
                    std::ptr::null_mut()
                } else {
                    cast_aligned_ptr::<T>(raw_ptr)
                }
            },
        };

        if new_ptr.is_null() {
            return Err(ZiporaError::out_of_memory(new_layout.size()));
        }

        // SAFETY: new_ptr is non-null after check at line 373
        self.ptr = Some(unsafe { NonNull::new_unchecked(new_ptr) });
        self.cap = target_cap;
        Ok(())
    }

    /// Push an element to the end of the vector
    pub fn push(&mut self, value: T) -> Result<()> {
        debug_assert!(self.len <= self.cap);
        if self.len >= (isize::MAX as usize) {
            return Err(ZiporaError::invalid_state(
                "vector length would exceed maximum",
            ));
        }

        if self.len >= self.cap {
            self.ensure_capacity(self.len + 1)?;
        }

        debug_assert!(self.len < self.cap);
        debug_assert!(self.ptr.is_some() || self.len == 0);

        // SAFETY: self.len < self.cap after ensure_capacity, ptr valid from allocation
        unsafe {
            ptr::write(self.as_mut_ptr().add(self.len), value);
        }
        self.len += 1;
        Ok(())
    }

    /// Pop an element from the end of the vector
    pub fn pop(&mut self) -> Option<T> {
        debug_assert!(self.len <= self.cap);

        if self.len == 0 {
            None
        } else {
            debug_assert!(self.ptr.is_some());

            self.len -= 1;
            // SAFETY: self.len < original len guaranteed by check at line 414, ptr valid from verification
            Some(unsafe { ptr::read(self.as_ptr().add(self.len)) })
        }
    }

    /// Insert an element at the specified index
    pub fn insert(&mut self, index: usize, value: T) -> Result<()> {
        if index > self.len {
            return Err(ZiporaError::out_of_bounds(index, self.len));
        }

        debug_assert!(index <= self.len);

        if self.len >= self.cap {
            self.ensure_capacity(self.len + 1)?;
        }

        let move_count = self.len - index;

        // SAFETY: index <= self.len verified above, ptr valid after ensure_capacity, move_count computed safely
        unsafe {
            let ptr = self.as_mut_ptr().add(index);

            if move_count > 0 {
                // ptr::copy handles overlapping memory correctly (compiles to memmove,
                // which LLVM/glibc already optimizes with SIMD for large buffers)
                ptr::copy(ptr, ptr.add(1), move_count);
            }

            // Write the new value
            ptr::write(ptr, value);
        }
        self.len += 1;
        Ok(())
    }

    /// Remove and return the element at the specified index
    pub fn remove(&mut self, index: usize) -> Result<T> {
        if index >= self.len {
            return Err(ZiporaError::out_of_bounds(index, self.len));
        }

        let move_count = self.len - index - 1;

        // SAFETY: index < self.len verified above, ptr valid from allocation, move_count computed safely
        unsafe {
            let ptr = self.as_mut_ptr().add(index);
            let value = ptr::read(ptr);

            if move_count > 0 {
                // ptr::copy handles overlapping memory correctly (compiles to memmove,
                // which LLVM/glibc already optimizes with SIMD for large buffers)
                ptr::copy(ptr.add(1), ptr, move_count);
            }

            self.len -= 1;
            Ok(value)
        }
    }

    /// Resize the vector to the specified length
    pub fn resize(&mut self, new_len: usize, value: T) -> Result<()>
    where
        T: Clone,
    {
        if new_len > (isize::MAX as usize) / mem::size_of::<T>().max(1) {
            return Err(ZiporaError::out_of_memory(new_len * mem::size_of::<T>()));
        }
        debug_assert!(self.len <= self.cap);

        if new_len > self.len {
            self.ensure_capacity(new_len)?;

            debug_assert!(self.cap >= new_len);
            debug_assert!(self.ptr.is_some());

            let fill_count = new_len - self.len;

            // Use SIMD optimization for large fill operations on Copy types
            if is_simd_safe::<T>()
                && is_simd_beneficial::<T>(fill_count)
                && mem::size_of::<T>() == 1
            {
                // For u8-sized Copy types, use direct SIMD fill
                // SAFETY: self.len + fill_count == new_len <= cap after ensure_capacity, ptr valid from verification
                unsafe {
                    let fill_slice = slice::from_raw_parts_mut(
                        self.as_mut_ptr().add(self.len) as *mut u8,
                        fill_count,
                    );
                    fast_fill(fill_slice, *((&value) as *const T as *const u8));
                }
            } else {
                // Standard fill for non-Copy types or small operations.
                // Bump len after each write so that if value.clone() panics,
                // the elements already written are owned by the vector and
                // dropped during unwinding instead of leaking.
                for i in self.len..new_len {
                    // SAFETY: i < new_len <= cap after ensure_capacity, ptr valid from verification
                    unsafe {
                        ptr::write(self.as_mut_ptr().add(i), value.clone());
                    }
                    self.len = i + 1;
                }
            }
        } else if new_len < self.len {
            // Verify we have valid memory to drop elements from
            debug_assert!(self.ptr.is_some() || self.len == 0);

            // Drop excess elements
            for i in new_len..self.len {
                // SAFETY: new_len <= i < self.len, ptr valid from debug_assert above
                unsafe {
                    ptr::drop_in_place(self.as_mut_ptr().add(i));
                }
            }
        }
        self.len = new_len;

        debug_assert!(self.len <= self.cap);
        Ok(())
    }

    /// Resize the vector to the specified length, using a closure to create new elements
    pub fn resize_with<F>(&mut self, new_len: usize, f: F) -> Result<()>
    where
        F: FnMut() -> T,
    {
        if new_len > (isize::MAX as usize) / mem::size_of::<T>().max(1) {
            return Err(ZiporaError::out_of_memory(new_len * mem::size_of::<T>()));
        }
        debug_assert!(self.len <= self.cap);

        if new_len > self.len {
            self.ensure_capacity(new_len)?;

            debug_assert!(self.cap >= new_len);
            debug_assert!(self.ptr.is_some());

            let mut closure = f;
            // Bump len after each write so that if closure() panics, the
            // elements already written are dropped during unwinding instead
            // of leaking.
            for i in self.len..new_len {
                // SAFETY: i < new_len <= cap after ensure_capacity, ptr valid from debug_assert above
                unsafe {
                    ptr::write(self.as_mut_ptr().add(i), closure());
                }
                self.len = i + 1;
            }
        } else if new_len < self.len {
            // Drop excess elements
            for i in new_len..self.len {
                // SAFETY: new_len <= i < self.len, ptr valid since len > 0
                unsafe {
                    ptr::drop_in_place(self.as_mut_ptr().add(i));
                }
            }
        }
        self.len = new_len;

        debug_assert!(self.len <= self.cap);
        Ok(())
    }

    /// Clear all elements from the vector
    pub fn clear(&mut self) {
        debug_assert!(self.len <= self.cap);
        debug_assert!(self.ptr.is_some() || self.len == 0);

        for i in 0..self.len {
            // SAFETY: i < self.len, ptr valid from debug_assert above
            unsafe {
                ptr::drop_in_place(self.as_mut_ptr().add(i));
            }
        }
        self.len = 0;

        debug_assert!(self.len <= self.cap);
    }

    /// Shrink the capacity to fit the current length
    pub fn shrink_to_fit(&mut self) -> Result<()> {
        // ZST: nothing was ever allocated, nothing to shrink or dealloc.
        if mem::size_of::<T>() == 0 {
            return Ok(());
        }

        if self.len == self.cap {
            return Ok(());
        }

        if self.len == 0 {
            if let Some(ptr) = self.ptr {
                // SAFETY: ptr from valid allocation, layout matches original allocation parameters
                unsafe {
                    let layout = Layout::array::<T>(self.cap)
                        .map_err(|_| ZiporaError::out_of_memory(self.cap * mem::size_of::<T>()))?;
                    alloc::dealloc(ptr.as_ptr() as *mut u8, layout);
                }
            }
            self.ptr = None;
            self.cap = 0;
            return Ok(());
        }

        let new_layout = Layout::array::<T>(self.len)
            .map_err(|_| ZiporaError::out_of_memory(self.len * mem::size_of::<T>()))?;

        let new_ptr = if let Some(ptr) = self.ptr {
            let old_layout = Layout::array::<T>(self.cap)
                .map_err(|_| ZiporaError::out_of_memory(self.cap * mem::size_of::<T>()))?;
            // SAFETY: ptr from valid allocation, old_layout matches original, new_layout.size() <= old_layout.size() (shrinking)
            unsafe {
                let raw_ptr =
                    alloc::realloc(ptr.as_ptr() as *mut u8, old_layout, new_layout.size());
                if raw_ptr.is_null() {
                    std::ptr::null_mut()
                } else {
                    cast_aligned_ptr::<T>(raw_ptr)
                }
            }
        } else {
            return Ok(()); // Nothing to shrink
        };

        if new_ptr.is_null() {
            return Err(ZiporaError::out_of_memory(new_layout.size()));
        }

        // SAFETY: new_ptr is non-null after check at line 670
        self.ptr = Some(unsafe { NonNull::new_unchecked(new_ptr) });
        self.cap = self.len;
        Ok(())
    }

    /// Get a reference to the element at the specified index without bounds checking
    ///
    /// # Safety
    ///
    /// The caller must ensure that `index < self.len()`
    #[inline(always)]
    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
        debug_assert!(index < self.len);
        // SAFETY: if len > 0, ptr is always Some. unwrap_unchecked eliminates the Option branch.
        unsafe { &*self.ptr.unwrap_unchecked().as_ptr().add(index) }
    }

    /// Get a mutable reference to the element at the specified index without bounds checking
    ///
    /// # Safety
    ///
    /// The caller must ensure that `index < self.len()`
    #[inline(always)]
    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
        debug_assert!(index < self.len);
        // SAFETY: if len > 0, ptr is always Some (set by with_capacity/push/resize).
        // unwrap_unchecked eliminates the Option branch that the compiler can't prove away.
        unsafe { &mut *self.ptr.unwrap_unchecked().as_ptr().add(index) }
    }

    /// Extend the vector with elements from an iterator.
    /// For bulk slice copies, prefer `extend_from_slice_fast` which uses SIMD.
    pub fn extend<I>(&mut self, iter: I) -> Result<()>
    where
        I: IntoIterator<Item = T>,
        I::IntoIter: ExactSizeIterator,
    {
        let iter = iter.into_iter();
        let additional = iter.len();
        self.reserve(additional)?;

        // Bump len after each write so that if iter.next() panics, the items
        // already written are dropped during unwinding instead of leaking.
        for item in iter {
            // SAFETY: self.len < original len + additional <= cap after reserve
            unsafe {
                ptr::write(self.as_mut_ptr().add(self.len), item);
            }
            self.len += 1;
        }

        Ok(())
    }

    //==============================================================================
    // SIMD-OPTIMIZED BULK OPERATIONS
    //==============================================================================

    /// Fast fill a range of the vector with the given value using SIMD optimization
    ///
    /// This method provides 2-3x performance improvement over standard fill operations
    /// for bulk data when T is Copy and the operation size is ≥64 bytes.
    ///
    /// # Performance
    /// - Uses **Adaptive SIMD Selection** for optimal implementation choice
    /// - **Advanced Prefetching** with PREFETCH_DISTANCE=8 for large ranges
    /// - Falls back to standard operations for small ranges or non-Copy types
    /// - Provides optimal performance for primitive types (u8, u16, u32, u64, etc.)
    pub fn fill_range_fast(&mut self, start: usize, end: usize, value: T) -> Result<()>
    where
        T: Copy,
    {
        if start > end || end > self.len {
            return Err(ZiporaError::out_of_bounds(end, self.len));
        }

        debug_assert!(start <= end);
        debug_assert!(end <= self.len);
        debug_assert!(self.len <= self.cap);
        debug_assert!(self.ptr.is_some() || self.len == 0);

        if start == end {
            return Ok(()); // Nothing to fill
        }

        let range_len = end - start;

        // Adaptive SIMD selection for optimal implementation
        if is_simd_safe::<T>() && is_simd_beneficial::<T>(range_len) {
            let selector = AdaptiveSimdSelector::global();
            let _ = selector.select_optimal_impl(
                Operation::MemZero,
                range_len * mem::size_of::<T>(),
                None, // No density for fill operations
            );

            // Monitor performance for adaptive optimization
            let start_time = Instant::now();

            // For u8-sized types, use direct SIMD fill
            if mem::size_of::<T>() == 1 {
                // SAFETY: start + range_len == end <= self.len verified at line 762, ptr valid from verification at line 770
                unsafe {
                    let range_slice = slice::from_raw_parts_mut(
                        self.as_mut_ptr().add(start) as *mut u8,
                        range_len,
                    );

                    // Advanced prefetching for large fills
                    if range_len >= PREFETCH_DISTANCE * 8 {
                        PrefetchOps::prefetch_range(
                            range_slice.as_ptr(),
                            range_len,
                            PREFETCH_DISTANCE,
                        );
                    }

                    fast_fill(range_slice, *((&value) as *const T as *const u8));
                }
            } else {
                // For other Copy types, use bulk fill with prefetching
                // SAFETY: start + range_len == end <= self.len verified at line 762, ptr valid from verification at line 770
                let range_slice =
                    unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(start), range_len) };

                // Prefetch-optimized fill for large ranges
                if range_len >= PREFETCH_DISTANCE * 2 {
                    for i in 0..range_len {
                        // Lookahead prefetching (PREFETCH_DISTANCE=8)
                        if i + PREFETCH_DISTANCE < range_len {
                            PrefetchOps::prefetch_read(
                                &range_slice[i + PREFETCH_DISTANCE] as *const T as *const u8
                                    as *const i8,
                            );
                        }
                        range_slice[i] = value;
                    }
                } else {
                    // Standard fill for smaller ranges
                    for item in range_slice.iter_mut() {
                        *item = value;
                    }
                }
            }

            // Record performance for monitoring
            selector.monitor_performance(
                Operation::MemZero,
                start_time.elapsed(),
                range_len as u64,
            );
        } else {
            // Standard fill for small ranges or non-Copy types
            let range_slice = &mut self.as_mut_slice()[start..end];
            for item in range_slice.iter_mut() {
                *item = value;
            }
        }

        Ok(())
    }

    /// Fast copy data from a slice using SIMD optimization
    ///
    /// This method provides 2-3x performance improvement over standard copy operations
    /// for bulk data when T is Copy and the operation size is ≥64 bytes.
    ///
    /// # Performance
    /// - Uses **Adaptive SIMD Selection** for optimal implementation choice
    /// - **Advanced Prefetching** with PREFETCH_DISTANCE=8 for large copies
    /// - Falls back to standard operations for small slices or non-Copy types
    /// - Provides optimal performance for primitive types and simple structs
    pub fn copy_from_slice_fast(&mut self, src: &[T]) -> Result<()>
    where
        T: Copy,
    {
        if src.len() > (isize::MAX as usize) / mem::size_of::<T>().max(1) {
            return Err(ZiporaError::out_of_memory(std::mem::size_of_val(src)));
        }
        debug_assert!(self.len <= self.cap);

        if src.is_empty() {
            return Ok(());
        }

        self.ensure_capacity(src.len())?;

        debug_assert!(self.cap >= src.len());
        debug_assert!(self.ptr.is_some());

        // Adaptive SIMD selection for optimal copy implementation
        if is_simd_safe::<T>() && is_simd_beneficial::<T>(src.len()) {
            let selector = AdaptiveSimdSelector::global();
            let _ = selector.select_optimal_impl(
                Operation::Copy,
                std::mem::size_of_val(src),
                None, // No density for copy operations
            );

            // Monitor performance for adaptive optimization
            let start_time = Instant::now();

            // SAFETY: src.len() <= cap after ensure_capacity, ptr valid from verification at line 885
            unsafe {
                // Advanced prefetching for large copies
                if src.len() >= PREFETCH_DISTANCE * 8 {
                    PrefetchOps::prefetch_range(src.as_ptr(), src.len(), PREFETCH_DISTANCE);
                }

                let src_bytes = slice_as_bytes(src);
                let dst_bytes =
                    slice_as_bytes_mut(slice::from_raw_parts_mut(self.as_mut_ptr(), src.len()));
                fast_copy(src_bytes, dst_bytes)?;
            }

            // Record performance for monitoring
            selector.monitor_performance(Operation::Copy, start_time.elapsed(), src.len() as u64);
        } else {
            // Standard copy for small slices or non-Copy types
            // SAFETY: src.len() <= cap after ensure_capacity, no overlap (src is external)
            unsafe {
                ptr::copy_nonoverlapping(src.as_ptr(), self.as_mut_ptr(), src.len());
            }
        }

        self.len = src.len();
        Ok(())
    }

    /// Fast extend with SIMD optimization for slice data
    ///
    /// This method provides 2-3x performance improvement over standard extend operations
    /// for bulk data when T is Copy and the operation size is ≥64 bytes.
    ///
    /// # Performance
    /// - Uses **Adaptive SIMD Selection** for optimal implementation choice
    /// - **Advanced Prefetching** with PREFETCH_DISTANCE=8 for large extends
    /// - Continuous performance monitoring for adaptive optimization
    pub fn extend_from_slice_fast(&mut self, src: &[T]) -> Result<()>
    where
        T: Copy,
    {
        if src.is_empty() {
            return Ok(());
        }

        let old_len = self.len;
        self.reserve(src.len())?;

        // Adaptive SIMD selection for optimal extend implementation
        if is_simd_safe::<T>() && is_simd_beneficial::<T>(src.len()) {
            let selector = AdaptiveSimdSelector::global();
            let _ = selector.select_optimal_impl(
                Operation::Copy,
                std::mem::size_of_val(src),
                None, // No density for extend operations
            );

            // Monitor performance for adaptive optimization
            let start_time = Instant::now();

            // SAFETY: old_len + src.len() <= cap after reserve, ptr valid from allocation
            unsafe {
                // Advanced prefetching for large extends
                if src.len() >= PREFETCH_DISTANCE * 8 {
                    PrefetchOps::prefetch_range(src.as_ptr(), src.len(), PREFETCH_DISTANCE);
                }

                let src_bytes = slice_as_bytes(src);
                let dst_bytes = slice_as_bytes_mut(slice::from_raw_parts_mut(
                    self.as_mut_ptr().add(old_len),
                    src.len(),
                ));
                fast_copy(src_bytes, dst_bytes)?;
            }

            // Record performance for monitoring
            selector.monitor_performance(Operation::Copy, start_time.elapsed(), src.len() as u64);
        } else {
            // Standard copy for small slices or non-Copy types
            // SAFETY: old_len + src.len() <= cap after reserve, no overlap (src is external)
            unsafe {
                ptr::copy_nonoverlapping(src.as_ptr(), self.as_mut_ptr().add(old_len), src.len());
            }
        }

        self.len += src.len();
        Ok(())
    }
}

mod traits;

#[cfg(test)]
mod tests;