cache_rs/

slru.rs

//! Segmented Least Recently Used (SLRU) Cache Implementation
//!
//! SLRU is a scan-resistant cache algorithm that divides the cache into two segments:
//! a **probationary segment** for new entries and a **protected segment** for frequently
//! accessed entries. This design prevents one-time access patterns (scans) from evicting
//! valuable cached items.
//!
//! # How the Algorithm Works
//!
//! SLRU uses a two-tier approach to distinguish between items that are accessed once
//! (scans, sequential reads) versus items accessed repeatedly (working set).
//!
//! ## Segment Architecture
//!
//! ```text
//! ┌──────────────────────────────────────────────────────────────────────────────┐
//! │                              SLRU Cache                                      │
//! │                                                                              │
//! │  ┌──────────────────────────────────────────────────────────────────────┐    │
//! │  │                    PROTECTED SEGMENT (20%)                           │    │
//! │  │          Frequently accessed items - harder to evict                 │    │
//! │  │  ┌────────────────────────────────────────────────────────────────┐  │    │
//! │  │  │ MRU ◀──▶ [hot_1] ◀──▶ [hot_2] ◀──▶ ... ◀──▶ [demote] LRU  │  │    │
//! │  │  └────────────────────────────────────────────────────────────────┘  │    │
//! │  └──────────────────────────────────────────────────────────────────────┘    │
//! │                              │ demote                   ▲ promote            │
//! │                              ▼                          │                    │
//! │  ┌──────────────────────────────────────────────────────────────────────┐    │
//! │  │                   PROBATIONARY SEGMENT (80%)                         │    │
//! │  │          New items and demoted items - easier to evict               │    │
//! │  │  ┌────────────────────────────────────────────────────────────────┐  │    │
//! │  │  │ MRU ◀──▶ [new_1] ◀──▶ [new_2] ◀──▶ ... ◀──▶ [evict] LRU   │  │    │
//! │  │  └────────────────────────────────────────────────────────────────┘  │    │
//! │  └──────────────────────────────────────────────────────────────────────┘    │
//! │                              ▲                                               │
//! │                              │ insert                                        │
//! │                         new items                                            │
//! └──────────────────────────────────────────────────────────────────────────────┘
//! ```
//!
//! ## Entry Lifecycle
//!
//! 1. **Insert**: New items enter the probationary segment
//! 2. **First access in probationary**: Item promoted to protected segment
//! 3. **Protected segment full**: LRU item demoted back to probationary
//! 4. **Eviction**: Always from the LRU end of the probationary segment
//!
//! ## Scan Resistance Example
//!
//! ```text
//! Initial state: Protected=[A, B, C], Probationary=[D, E, F]
//! (A, B, C are hot items; D, E, F are warm items)
//!
//! Sequential scan of X, Y, Z (one-time access):
//!   put(X) → Protected=[A, B, C], Probationary=[X, D, E]  (F evicted)
//!   put(Y) → Protected=[A, B, C], Probationary=[Y, X, D]  (E evicted)
//!   put(Z) → Protected=[A, B, C], Probationary=[Z, Y, X]  (D evicted)
//!
//! Hot items A, B, C remain in protected segment!
//! The scan only displaced probationary items.
//! ```
//!
//! ## Operations
//!
//! | Operation | Action | Time |
//! |-----------|--------|------|
//! | `get(key)` | Promote to protected if in probationary | O(1) |
//! | `put(key, value)` | Insert to probationary, may evict | O(1) |
//! | `remove(key)` | Remove from whichever segment contains it | O(1) |
//!
//! # Dual-Limit Capacity
//!
//! This implementation supports two independent limits:
//!
//! - **`max_entries`**: Maximum total items across both segments
//! - **`max_size`**: Maximum total size of content
//!
//! The protected segment size is configured separately (default: 20% of total).
//!
//! # Performance Characteristics
//!
//! | Metric | Value |
//! |--------|-------|
//! | Get | O(1) |
//! | Put | O(1) |
//! | Remove | O(1) |
//! | Memory per entry | ~90 bytes overhead + key×2 + value |
//!
//! Memory overhead includes: two list pointers, location tag, size tracking,
//! HashMap bucket, and allocator overhead.
//!
//! # When to Use SLRU
//!
//! **Good for:**
//! - Mixed workloads with both hot data and sequential scans
//! - Database buffer pools
//! - File system caches
//! - Any scenario where scans shouldn't evict the working set
//!
//! **Not ideal for:**
//! - Pure recency-based access patterns (LRU is simpler)
//! - Frequency-dominant patterns (LFU/LFUDA is better)
//! - Very small caches where the two-segment overhead isn't justified
//!
//! # Tuning the Protected Ratio
//!
//! The protected segment size controls the trade-off:
//! - **Larger protected**: More scan resistance, but new items evicted faster
//! - **Smaller protected**: Less scan resistance, but more room for new items
//!
//! Default is 20% protected, which works well for most workloads.
//!
//! # Thread Safety
//!
//! `SlruCache` is **not thread-safe**. For concurrent access, either:
//! - Wrap with `Mutex` or `RwLock`
//! - Use `ConcurrentSlruCache` (requires `concurrent` feature)
//!
//! # Examples
//!
//! ## Basic Usage
//!
//! ```
//! use cache_rs::SlruCache;
//! use cache_rs::config::SlruCacheConfig;
//! use core::num::NonZeroUsize;
//!
//! // Total capacity 100, protected segment 20
//! let config = SlruCacheConfig {
//!     capacity: NonZeroUsize::new(100).unwrap(),
//!     protected_capacity: NonZeroUsize::new(20).unwrap(),
//!     max_size: u64::MAX,
//! };
//! let mut cache = SlruCache::init(config, None);
//!
//! cache.put("a", 1, 1);  // Enters probationary
//! cache.get(&"a");    // Promoted to protected!
//! cache.put("b", 2, 1);  // Enters probationary
//!
//! assert_eq!(cache.get(&"a"), Some(&1));  // Still in protected
//! ```
//!
//! ## Scan Resistance Demo
//!
//! ```
//! use cache_rs::SlruCache;
//! use cache_rs::config::SlruCacheConfig;
//! use core::num::NonZeroUsize;
//!
//! let config = SlruCacheConfig {
//!     capacity: NonZeroUsize::new(10).unwrap(),
//!     protected_capacity: NonZeroUsize::new(3).unwrap(),
//!     max_size: u64::MAX,
//! };
//! let mut cache: SlruCache<i32, i32> = SlruCache::init(config, None);
//!
//! // Establish hot items in protected segment
//! for key in [1, 2, 3] {
//!     cache.put(key, 100, 1);
//!     cache.get(&key);  // Promote to protected
//! }
//!
//! // Simulate a scan - these items only enter probationary
//! for i in 100..120 {
//!     cache.put(i, i, 1);  // One-time insertions
//! }
//!
//! // Hot items survive the scan!
//! assert!(cache.get(&1).is_some());
//! assert!(cache.get(&2).is_some());
//! assert!(cache.get(&3).is_some());
//! ```

extern crate alloc;

use crate::config::SlruCacheConfig;
use crate::entry::CacheEntry;
use crate::list::{List, ListEntry};
use crate::metrics::{CacheMetrics, SlruCacheMetrics};
use alloc::boxed::Box;
use alloc::collections::BTreeMap;
use alloc::string::String;
use alloc::vec::Vec;
use core::borrow::Borrow;
use core::hash::{BuildHasher, Hash};
use core::num::NonZeroUsize;

#[cfg(feature = "hashbrown")]
use hashbrown::DefaultHashBuilder;
#[cfg(feature = "hashbrown")]
use hashbrown::HashMap;

#[cfg(not(feature = "hashbrown"))]
use std::collections::hash_map::RandomState as DefaultHashBuilder;
#[cfg(not(feature = "hashbrown"))]
use std::collections::HashMap;

/// Entry location within the SLRU cache.
///
/// Tracks whether an entry is in the probationary or protected segment.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum Location {
    /// Entry is in the probationary segment (default for new entries)
    #[default]
    Probationary,
    /// Entry is in the protected segment (promoted on second access)
    Protected,
}

/// SLRU-specific metadata stored in each cache entry.
///
/// This uses the unified `CacheEntry<K, V, SlruMeta>` pattern, eliminating
/// the need for a complex tuple in the HashMap. Size and timestamps are
/// handled by `CacheMetadata`, this struct only holds SLRU-specific data.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct SlruMeta {
    /// Which segment this entry is in
    pub location: Location,
}

/// Internal SLRU segment containing the actual cache algorithm.
///
/// This is shared between `SlruCache` (single-threaded) and
/// `ConcurrentSlruCache` (multi-threaded). All algorithm logic is
/// implemented here to avoid code duplication.
///
/// Uses `CacheEntry<K, V, SlruMeta>` for unified entry management with built-in
/// size tracking and timestamps. The `SlruMeta` stores segment location, and
/// all other metadata (size, last_accessed) is handled by `CacheMetadata`.
///
/// # Safety
///
/// This struct contains raw pointers in the `map` field. These pointers
/// are always valid as long as:
/// - The pointer was obtained from `probationary.add()` or `protected.add()`
/// - The node has not been removed from the list
/// - The segment has not been dropped
pub(crate) struct SlruInner<K, V, S = DefaultHashBuilder> {
    /// Configuration for the SLRU cache
    config: SlruCacheConfig,

    /// The probationary list holding newer or less frequently accessed items
    probationary: List<CacheEntry<K, V, SlruMeta>>,

    /// The protected list holding frequently accessed items
    protected: List<CacheEntry<K, V, SlruMeta>>,

    /// Maps keys to their list nodes. All metadata (size, timestamp, location)
    /// is stored in the CacheEntry itself, not in the map.
    map: HashMap<K, *mut ListEntry<CacheEntry<K, V, SlruMeta>>, S>,

    /// Metrics for tracking cache performance and segment behavior
    metrics: SlruCacheMetrics,

    /// Current total size of cached content (sum of entry sizes)
    current_size: u64,

    /// Maximum content size the cache can hold
    max_size: u64,
}

// SAFETY: SlruInner owns all data and raw pointers point only to nodes owned by
// `probationary` or `protected` lists. Concurrent access is safe when wrapped in
// proper synchronization primitives.
unsafe impl<K: Send, V: Send, S: Send> Send for SlruInner<K, V, S> {}

// SAFETY: All mutation requires &mut self; shared references cannot cause data races.
unsafe impl<K: Send, V: Send, S: Sync> Sync for SlruInner<K, V, S> {}

impl<K: Hash + Eq, V: Clone, S: BuildHasher> SlruInner<K, V, S> {
    /// Creates a new SLRU segment from a configuration.
    ///
    /// This is the **recommended** way to create an SLRU segment. All configuration
    /// is specified through the [`SlruCacheConfig`] struct.
    ///
    /// # Arguments
    ///
    /// * `config` - Configuration specifying capacity, protected capacity, and optional size limit
    /// * `hasher` - Hash builder for the internal HashMap
    #[allow(dead_code)] // Used by concurrent module when feature is enabled
    pub(crate) fn init(config: SlruCacheConfig, hasher: S) -> Self {
        let capacity = config.capacity.get();
        let protected = config.protected_capacity.get();

        assert!(
            protected < capacity,
            "SlruCacheConfig invalid: protected_capacity ({}) must be strictly less than capacity ({})",
            protected,
            capacity
        );

        let probationary_max_size = NonZeroUsize::new(capacity - protected).unwrap();

        SlruInner {
            config,
            probationary: List::new(probationary_max_size),
            protected: List::new(config.protected_capacity),
            map: HashMap::with_capacity_and_hasher(
                config.capacity.get().next_power_of_two(),
                hasher,
            ),
            metrics: SlruCacheMetrics::new(config.max_size, config.protected_capacity.get() as u64),
            current_size: 0,
            max_size: config.max_size,
        }
    }

    /// Returns the maximum number of key-value pairs the segment can hold.
    #[inline]
    pub(crate) fn cap(&self) -> NonZeroUsize {
        self.config.capacity
    }

    /// Returns the maximum size of the protected segment.
    #[inline]
    pub(crate) fn protected_max_size(&self) -> NonZeroUsize {
        self.config.protected_capacity
    }

    /// Returns the current number of key-value pairs in the segment.
    #[inline]
    pub(crate) fn len(&self) -> usize {
        self.map.len()
    }

    /// Returns `true` if the segment contains no key-value pairs.
    #[inline]
    pub(crate) fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Returns the current total size of cached content.
    #[inline]
    pub(crate) fn current_size(&self) -> u64 {
        self.current_size
    }

    /// Returns the maximum content size the cache can hold.
    #[inline]
    pub(crate) fn max_size(&self) -> u64 {
        self.max_size
    }

    /// Returns a reference to the metrics for this segment.
    #[inline]
    pub(crate) fn metrics(&self) -> &SlruCacheMetrics {
        &self.metrics
    }

    /// Moves an entry from the probationary segment to the protected segment.
    /// If the protected segment is full, the LRU item from protected is demoted to probationary.
    ///
    /// Returns a raw pointer to the entry in its new location.
    unsafe fn promote_to_protected(
        &mut self,
        node: *mut ListEntry<CacheEntry<K, V, SlruMeta>>,
    ) -> *mut ListEntry<CacheEntry<K, V, SlruMeta>> {
        // Remove from probationary list
        let boxed_entry = self
            .probationary
            .remove(node)
            .expect("Node should exist in probationary");

        // If protected segment is full, demote LRU protected item to probationary
        if self.protected.len() >= self.protected_max_size().get() {
            // We need to make room in probationary first if it's full
            if self.probationary.len() >= self.probationary.cap().get() {
                // Evict LRU from probationary
                if let Some(old_entry) = self.probationary.remove_last() {
                    let old_ptr = Box::into_raw(old_entry);
                    let cache_entry = (*old_ptr).get_value();
                    let evicted_size = cache_entry.metadata.size;
                    self.map.remove(&cache_entry.key);
                    self.current_size = self.current_size.saturating_sub(evicted_size);
                    self.metrics.record_probationary_eviction(evicted_size);
                    let _ = Box::from_raw(old_ptr);
                }
            }
            self.demote_lru_protected();
        }

        // Get the raw pointer from the box
        let entry_ptr = Box::into_raw(boxed_entry);

        // Update location and timestamp in the entry
        let cache_entry = (*entry_ptr).get_value_mut();
        cache_entry.metadata.algorithm.location = Location::Protected;
        cache_entry.touch(); // Update last_accessed timestamp

        // Update the map pointer
        if let Some(node_ptr) = self.map.get_mut(&cache_entry.key) {
            *node_ptr = entry_ptr;
        }

        // Add to protected list using the pointer from the Box
        unsafe {
            self.protected.attach_from_other_list(entry_ptr);
        }

        entry_ptr
    }

    /// Demotes the least recently used item from the protected segment to the probationary segment.
    unsafe fn demote_lru_protected(&mut self) {
        if let Some(lru_protected) = self.protected.remove_last() {
            let lru_ptr = Box::into_raw(lru_protected);
            let cache_entry = (*lru_ptr).get_value_mut();

            // Update location in the entry
            cache_entry.metadata.algorithm.location = Location::Probationary;

            // Update the map pointer
            if let Some(node_ptr) = self.map.get_mut(&cache_entry.key) {
                *node_ptr = lru_ptr;
            }

            // Add to probationary list
            self.probationary.attach_from_other_list(lru_ptr);

            // Record demotion
            self.metrics.record_demotion();
        }
    }

    /// Returns a reference to the value corresponding to the key.
    pub(crate) fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let node = self.map.get(key).copied()?;

        unsafe {
            // SAFETY: node comes from our map, so it's a valid pointer
            let cache_entry = (*node).get_value();
            let location = cache_entry.metadata.algorithm.location;
            let size = cache_entry.metadata.size;

            match location {
                Location::Probationary => {
                    self.metrics.record_probationary_hit(size);

                    // Promote from probationary to protected (updates timestamp and location)
                    let entry_ptr = self.promote_to_protected(node);

                    // Record promotion
                    self.metrics.record_promotion();

                    // Update segment sizes
                    self.metrics.update_segment_sizes(
                        self.probationary.len() as u64,
                        self.protected.len() as u64,
                    );

                    // SAFETY: entry_ptr is the return value from promote_to_protected
                    Some(&(*entry_ptr).get_value().value)
                }
                Location::Protected => {
                    self.metrics.record_protected_hit(size);

                    // Already protected, just move to MRU position and update timestamp
                    self.protected.move_to_front(node);
                    (*node).get_value_mut().touch();
                    Some(&(*node).get_value().value)
                }
            }
        }
    }

    /// Returns a mutable reference to the value corresponding to the key.
    pub(crate) fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let node = self.map.get(key).copied()?;

        unsafe {
            // SAFETY: node comes from our map, so it's a valid pointer
            let cache_entry = (*node).get_value();
            let location = cache_entry.metadata.algorithm.location;
            let size = cache_entry.metadata.size;

            match location {
                Location::Probationary => {
                    self.metrics.record_probationary_hit(size);

                    // Promote from probationary to protected (updates timestamp and location)
                    let entry_ptr = self.promote_to_protected(node);

                    // Record promotion
                    self.metrics.record_promotion();

                    // Update segment sizes
                    self.metrics.update_segment_sizes(
                        self.probationary.len() as u64,
                        self.protected.len() as u64,
                    );

                    // SAFETY: entry_ptr is the return value from promote_to_protected
                    Some(&mut (*entry_ptr).get_value_mut().value)
                }
                Location::Protected => {
                    self.metrics.record_protected_hit(size);

                    // Already protected, just move to MRU position and update timestamp
                    self.protected.move_to_front(node);
                    (*node).get_value_mut().touch();
                    Some(&mut (*node).get_value_mut().value)
                }
            }
        }
    }

    /// Records a cache miss for metrics tracking
    #[inline]
    pub(crate) fn record_miss(&mut self, object_size: u64) {
        self.metrics.core.record_miss(object_size);
    }
}

impl<K: Hash + Eq + Clone, V, S: BuildHasher> SlruInner<K, V, S> {
    /// Inserts a key-value pair into the segment.
    ///
    /// # Arguments
    ///
    /// * `key` - The key to insert
    /// * `value` - The value to insert
    /// * `size` - Optional size in bytes. Use `SIZE_UNIT` (1) for count-based caching.
    ///
    /// Returns evicted entries, or `None` if no entries were evicted.
    /// Note: Replacing an existing key does not return the old value.
    pub(crate) fn put(&mut self, key: K, value: V, size: u64) -> Option<Vec<(K, V)>>
    where
        V: Clone,
    {
        // If key is already in the cache, update it in place
        if let Some(&node) = self.map.get(&key) {
            unsafe {
                // SAFETY: node comes from our map
                let cache_entry = (*node).get_value();
                let location = cache_entry.metadata.algorithm.location;
                let old_size = cache_entry.metadata.size;

                match location {
                    Location::Probationary => {
                        self.probationary.move_to_front(node);
                        // Create new CacheEntry with updated value
                        let new_entry = CacheEntry::with_algorithm_metadata(
                            key.clone(),
                            value,
                            size,
                            SlruMeta {
                                location: Location::Probationary,
                            },
                        );
                        let old_entry = self.probationary.update(node, new_entry, true);
                        // Update size tracking
                        self.current_size = self.current_size.saturating_sub(old_size);
                        self.current_size += size;
                        self.metrics.core.record_size_change(old_size, size);
                        self.metrics.core.bytes_written_to_cache += size;
                        // Replacement is not eviction - discard old entry
                        let _ = old_entry;
                        return None;
                    }
                    Location::Protected => {
                        self.protected.move_to_front(node);
                        // Create new CacheEntry with updated value
                        let new_entry = CacheEntry::with_algorithm_metadata(
                            key.clone(),
                            value,
                            size,
                            SlruMeta {
                                location: Location::Protected,
                            },
                        );
                        let old_entry = self.protected.update(node, new_entry, true);
                        // Update size tracking
                        self.current_size = self.current_size.saturating_sub(old_size);
                        self.current_size += size;
                        self.metrics.core.record_size_change(old_size, size);
                        self.metrics.core.bytes_written_to_cache += size;
                        // Replacement is not eviction - discard old entry
                        let _ = old_entry;
                        return None;
                    }
                }
            }
        }

        let mut evicted = Vec::new();

        // Evict while entry count limit OR size limit would be exceeded
        // This mirrors LRU's eviction logic to properly respect max_size
        while self.len() >= self.cap().get()
            || (self.current_size + size > self.config.max_size && !self.map.is_empty())
        {
            if let Some(entry) = self.evict() {
                self.metrics.core.evictions += 1;
                evicted.push(entry);
            } else {
                break;
            }
        }

        // Add the new key-value pair to the probationary segment
        let cache_entry = CacheEntry::with_algorithm_metadata(
            key.clone(),
            value,
            size,
            SlruMeta {
                location: Location::Probationary,
            },
        );
        let node = self.probationary.add_unchecked(cache_entry);
        self.map.insert(key, node);
        self.current_size += size;

        // Record insertion and update segment sizes
        self.metrics.core.record_insertion(size);
        self.metrics
            .update_segment_sizes(self.probationary.len() as u64, self.protected.len() as u64);

        if evicted.is_empty() {
            None
        } else {
            Some(evicted)
        }
    }

    /// Removes a key from the segment, returning the value if the key was present.
    pub(crate) fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let node = self.map.remove(key)?;

        unsafe {
            // SAFETY: node comes from our map
            let cache_entry = (*node).get_value();
            let location = cache_entry.metadata.algorithm.location;
            let removed_size = cache_entry.metadata.size;

            match location {
                Location::Probationary => {
                    // SAFETY: take_value moves the value out and Box::from_raw frees memory
                    let boxed_entry = self.probationary.remove(node)?;
                    let entry_ptr = Box::into_raw(boxed_entry);
                    let cache_entry = (*entry_ptr).take_value();
                    self.current_size = self.current_size.saturating_sub(removed_size);
                    self.metrics.record_probationary_removal(removed_size);
                    let _ = Box::from_raw(entry_ptr);
                    Some(cache_entry.value)
                }
                Location::Protected => {
                    // SAFETY: take_value moves the value out and Box::from_raw frees memory
                    let boxed_entry = self.protected.remove(node)?;
                    let entry_ptr = Box::into_raw(boxed_entry);
                    let cache_entry = (*entry_ptr).take_value();
                    self.current_size = self.current_size.saturating_sub(removed_size);
                    self.metrics.record_protected_removal(removed_size);
                    let _ = Box::from_raw(entry_ptr);
                    Some(cache_entry.value)
                }
            }
        }
    }

    /// Clears the segment, removing all key-value pairs.
    pub(crate) fn clear(&mut self) {
        self.map.clear();
        self.probationary.clear();
        self.protected.clear();
        self.current_size = 0;
    }

    /// Check if key exists without promoting it between segments.
    ///
    /// Unlike `get()`, this method does NOT promote the entry from probationary
    /// to protected, and does not update any access metadata.
    #[inline]
    pub(crate) fn contains<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        self.map.contains_key(key)
    }

    /// Returns a reference to the value without promoting or updating access metadata.
    ///
    /// Unlike `get()`, this method does NOT promote the entry from probationary
    /// to protected, and does not update any ordering.
    pub(crate) fn peek<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let node = self.map.get(key)?;
        unsafe {
            // SAFETY: node comes from our map, so it's a valid pointer
            let cache_entry = (**node).get_value();
            Some(&cache_entry.value)
        }
    }

    /// Removes and returns the eviction candidate.
    ///
    /// For SLRU, the eviction candidate is the LRU entry from the probationary
    /// segment. If probationary is empty, falls back to the LRU entry from the
    /// protected segment.
    ///
    /// This method does **not** increment the eviction counter in metrics.
    /// Eviction metrics are only recorded when the cache internally evicts
    /// entries to make room during `put()` operations.
    fn evict(&mut self) -> Option<(K, V)> {
        // Try probationary first (normal eviction target)
        if let Some(old_entry) = self.probationary.remove_last() {
            unsafe {
                // SAFETY: take_value reads the CacheEntry out of MaybeUninit by value.
                // Box::from_raw frees memory (MaybeUninit won't double-drop).
                let entry_ptr = Box::into_raw(old_entry);
                let cache_entry = (*entry_ptr).take_value();
                let evicted_size = cache_entry.metadata.size;
                self.map.remove(&cache_entry.key);
                self.current_size = self.current_size.saturating_sub(evicted_size);
                self.metrics.record_probationary_removal(evicted_size);
                let _ = Box::from_raw(entry_ptr);
                return Some((cache_entry.key, cache_entry.value));
            }
        }

        // Fall back to protected if probationary is empty
        if let Some(old_entry) = self.protected.remove_last() {
            unsafe {
                // SAFETY: take_value reads the CacheEntry out of MaybeUninit by value.
                // Box::from_raw frees memory (MaybeUninit won't double-drop).
                let entry_ptr = Box::into_raw(old_entry);
                let cache_entry = (*entry_ptr).take_value();
                let evicted_size = cache_entry.metadata.size;
                self.map.remove(&cache_entry.key);
                self.current_size = self.current_size.saturating_sub(evicted_size);
                self.metrics.record_protected_removal(evicted_size);
                let _ = Box::from_raw(entry_ptr);
                return Some((cache_entry.key, cache_entry.value));
            }
        }

        None
    }
}

// Implement Debug for SlruInner manually since it contains raw pointers
impl<K, V, S> core::fmt::Debug for SlruInner<K, V, S> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("SlruInner")
            .field("capacity", &self.config.capacity)
            .field("protected_capacity", &self.config.protected_capacity)
            .field("len", &self.map.len())
            .finish()
    }
}

/// An implementation of a Segmented Least Recently Used (SLRU) cache.
///
/// The cache is divided into two segments:
/// - Probationary segment: Where new entries are initially placed
/// - Protected segment: Where frequently accessed entries are promoted to
///
/// When the cache reaches capacity, the least recently used entry from the
/// probationary segment is evicted. If the probationary segment is empty,
/// entries from the protected segment may be demoted back to probationary.
///
/// # Examples
///
/// ```
/// use cache_rs::slru::SlruCache;
/// use cache_rs::config::SlruCacheConfig;
/// use core::num::NonZeroUsize;
///
/// // Create an SLRU cache with a total capacity of 4,
/// // with a protected capacity of 2 (half protected, half probationary)
/// let config = SlruCacheConfig {
///     capacity: NonZeroUsize::new(4).unwrap(),
///     protected_capacity: NonZeroUsize::new(2).unwrap(),
///     max_size: u64::MAX,
/// };
/// let mut cache = SlruCache::init(config, None);
///
/// // Add some items
/// cache.put("a", 1, 1);
/// cache.put("b", 2, 1);
/// cache.put("c", 3, 1);
/// cache.put("d", 4, 1);
///
/// // Access "a" to promote it to the protected segment
/// assert_eq!(cache.get(&"a"), Some(&1));
///
/// // Add a new item, which will evict the least recently used item
/// // from the probationary segment (likely "b")
/// cache.put("e", 5, 1);
/// assert_eq!(cache.get(&"b"), None);
/// ```
#[derive(Debug)]
pub struct SlruCache<K, V, S = DefaultHashBuilder> {
    segment: SlruInner<K, V, S>,
}

impl<K: Hash + Eq, V: Clone, S: BuildHasher> SlruCache<K, V, S> {
    /// Returns the maximum number of key-value pairs the cache can hold.
    #[inline]
    pub fn cap(&self) -> NonZeroUsize {
        self.segment.cap()
    }

    /// Returns the maximum size of the protected segment.
    #[inline]
    pub fn protected_max_size(&self) -> NonZeroUsize {
        self.segment.protected_max_size()
    }

    /// Returns the current number of key-value pairs in the cache.
    #[inline]
    pub fn len(&self) -> usize {
        self.segment.len()
    }

    /// Returns `true` if the cache contains no key-value pairs.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.segment.is_empty()
    }

    /// Returns the current total size of cached content.
    #[inline]
    pub fn current_size(&self) -> u64 {
        self.segment.current_size()
    }

    /// Returns the maximum content size the cache can hold.
    #[inline]
    pub fn max_size(&self) -> u64 {
        self.segment.max_size()
    }

    /// Returns a reference to the value corresponding to the key.
    ///
    /// The key may be any borrowed form of the cache's key type, but
    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
    /// the key type.
    ///
    /// If a value is returned from the probationary segment, it is promoted
    /// to the protected segment.
    #[inline]
    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        self.segment.get(key)
    }

    /// Returns a mutable reference to the value corresponding to the key.
    ///
    /// The key may be any borrowed form of the cache's key type, but
    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
    /// the key type.
    ///
    /// If a value is returned from the probationary segment, it is promoted
    /// to the protected segment.
    #[inline]
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        self.segment.get_mut(key)
    }

    /// Records a cache miss for metrics tracking (to be called by simulation system)
    #[inline]
    pub fn record_miss(&mut self, object_size: u64) {
        self.segment.record_miss(object_size);
    }
}

impl<K: Hash + Eq + Clone, V, S: BuildHasher> SlruCache<K, V, S> {
    /// Inserts a key-value pair into the cache.
    ///
    /// If the key already exists, it is replaced. If at capacity, the least recently
    /// used item from the probationary segment is evicted. The inserted entry always
    /// starts in the probationary segment.
    ///
    /// # Arguments
    ///
    /// * `key` - The key to insert
    /// * `value` - The value to insert
    /// * `size` - Optional size in bytes for size-aware caching. Use `SIZE_UNIT` (1) for count-based caching.
    ///
    /// # Returns
    ///
    /// - `Some(vec)` containing evicted entries (not replaced entries)
    /// - `None` if no entries were evicted (zero allocation)
    #[inline]
    pub fn put(&mut self, key: K, value: V, size: u64) -> Option<Vec<(K, V)>>
    where
        V: Clone,
    {
        self.segment.put(key, value, size)
    }

    /// Removes a key from the cache, returning the value at the key if the key was previously in the cache.
    ///
    /// The key may be any borrowed form of the cache's key type, but
    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
    /// the key type.
    #[inline]
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
        V: Clone,
    {
        self.segment.remove(key)
    }

    /// Clears the cache, removing all key-value pairs.
    #[inline]
    pub fn clear(&mut self) {
        self.segment.clear()
    }

    /// Check if key exists without promoting it between segments.
    ///
    /// Unlike `get()`, this method does NOT promote the entry from probationary
    /// to protected, and does not update any access metadata.
    ///
    /// # Example
    ///
    /// ```
    /// use cache_rs::SlruCache;
    /// use cache_rs::config::SlruCacheConfig;
    /// use core::num::NonZeroUsize;
    ///
    /// let config = SlruCacheConfig {
    ///     capacity: NonZeroUsize::new(10).unwrap(),
    ///     protected_capacity: NonZeroUsize::new(3).unwrap(),
    ///     max_size: u64::MAX,
    /// };
    /// let mut cache = SlruCache::init(config, None);
    /// cache.put("a", 1, 1);
    /// assert!(cache.contains(&"a"));
    /// assert!(!cache.contains(&"b"));
    /// ```
    #[inline]
    pub fn contains<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        self.segment.contains(key)
    }

    /// Returns a reference to the value without promoting or updating access metadata.
    ///
    /// Unlike [`get()`](Self::get), this does NOT promote the entry from
    /// probationary to protected, and does not update any ordering.
    ///
    /// # Example
    ///
    /// ```
    /// use cache_rs::SlruCache;
    /// use cache_rs::config::SlruCacheConfig;
    /// use core::num::NonZeroUsize;
    ///
    /// let config = SlruCacheConfig {
    ///     capacity: NonZeroUsize::new(3).unwrap(),
    ///     protected_capacity: NonZeroUsize::new(1).unwrap(),
    ///     max_size: u64::MAX,
    /// };
    /// let mut cache = SlruCache::init(config, None);
    /// cache.put("a", 1, 1);
    ///
    /// // peek does not promote between segments
    /// assert_eq!(cache.peek(&"a"), Some(&1));
    /// assert_eq!(cache.peek(&"missing"), None);
    /// ```
    #[inline]
    pub fn peek<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        self.segment.peek(key)
    }
}

impl<K: Hash + Eq, V> SlruCache<K, V>
where
    V: Clone,
{
    /// Creates a new SLRU cache from a configuration.
    ///
    /// This is the **only** way to create an SLRU cache. All configuration
    /// is specified through the [`SlruCacheConfig`] struct.
    ///
    /// # Arguments
    ///
    /// * `config` - Configuration specifying capacity, protected capacity, and optional size limit
    /// * `hasher` - Optional custom hash builder. If `None`, uses the default.
    ///
    /// # Example
    ///
    /// ```
    /// use cache_rs::SlruCache;
    /// use cache_rs::config::SlruCacheConfig;
    /// use core::num::NonZeroUsize;
    ///
    /// // Simple capacity-only cache with 20% protected segment
    /// let config = SlruCacheConfig {
    ///     capacity: NonZeroUsize::new(100).unwrap(),
    ///     protected_capacity: NonZeroUsize::new(20).unwrap(),
    ///     max_size: u64::MAX,
    /// };
    /// let mut cache: SlruCache<&str, i32> = SlruCache::init(config, None);
    /// cache.put("key", 42, 1);
    ///
    /// // Cache with size limit
    /// let config = SlruCacheConfig {
    ///     capacity: NonZeroUsize::new(1000).unwrap(),
    ///     protected_capacity: NonZeroUsize::new(200).unwrap(),
    ///     max_size: 10 * 1024 * 1024,  // 10MB
    /// };
    /// let cache: SlruCache<String, Vec<u8>> = SlruCache::init(config, None);
    /// ```
    pub fn init(
        config: SlruCacheConfig,
        hasher: Option<DefaultHashBuilder>,
    ) -> SlruCache<K, V, DefaultHashBuilder> {
        SlruCache {
            segment: SlruInner::init(config, hasher.unwrap_or_default()),
        }
    }
}

impl<K: Hash + Eq, V: Clone, S: BuildHasher> CacheMetrics for SlruCache<K, V, S> {
    fn metrics(&self) -> BTreeMap<String, f64> {
        self.segment.metrics().metrics()
    }

    fn algorithm_name(&self) -> &'static str {
        self.segment.metrics().algorithm_name()
    }
}

#[cfg(test)]
mod tests {
    extern crate std;
    use std::string::ToString;

    use super::*;
    use crate::config::SlruCacheConfig;
    use alloc::format;
    use alloc::string::String;

    /// Helper to create an SlruCache with the given capacity and protected capacity
    fn make_cache<K: Hash + Eq + Clone, V: Clone>(
        cap: usize,
        protected_cap: usize,
    ) -> SlruCache<K, V> {
        let config = SlruCacheConfig {
            capacity: NonZeroUsize::new(cap).unwrap(),
            protected_capacity: NonZeroUsize::new(protected_cap).unwrap(),
            max_size: u64::MAX,
        };
        SlruCache::init(config, None)
    }

    #[test]
    fn test_slru_basic() {
        // Create a cache with capacity 4, with protected capacity 2
        // (2 probationary, 2 protected)
        let mut cache = make_cache(4, 2);

        // Add items to fill probationary segment
        assert_eq!(cache.put("a", 1, 1), None);
        assert_eq!(cache.put("b", 2, 1), None);
        assert_eq!(cache.put("c", 3, 1), None);
        assert_eq!(cache.put("d", 4, 1), None);

        // Cache should be at capacity
        assert_eq!(cache.len(), 4);

        // Access "a" and "b" to promote them to protected segment
        assert_eq!(cache.get(&"a"), Some(&1));
        assert_eq!(cache.get(&"b"), Some(&2));

        // Add a new item "e", should evict "c" from probationary
        let evicted = cache.put("e", 5, 1);
        assert!(evicted.is_some());
        let (evicted_key, evicted_val) = evicted.unwrap()[0];
        assert_eq!(evicted_key, "c");
        assert_eq!(evicted_val, 3);

        // Add another item "f", should evict "d" from probationary
        let evicted = cache.put("f", 6, 1);
        assert!(evicted.is_some());
        let (evicted_key, evicted_val) = evicted.unwrap()[0];
        assert_eq!(evicted_key, "d");
        assert_eq!(evicted_val, 4);

        // Check presence
        assert_eq!(cache.get(&"a"), Some(&1)); // Protected
        assert_eq!(cache.get(&"b"), Some(&2)); // Protected
        assert_eq!(cache.get(&"c"), None); // Evicted
        assert_eq!(cache.get(&"d"), None); // Evicted
        assert_eq!(cache.get(&"e"), Some(&5)); // Probationary
        assert_eq!(cache.get(&"f"), Some(&6)); // Probationary
    }

    #[test]
    fn test_slru_update() {
        // Create a cache with capacity 4, with protected capacity 2
        let mut cache = make_cache(4, 2);

        // Add items
        cache.put("a", 1, 1);
        cache.put("b", 2, 1);

        // Access "a" to promote it to protected
        assert_eq!(cache.get(&"a"), Some(&1));

        // Update values - replacement returns None
        assert!(cache.put("a", 10, 1).is_none());
        assert!(cache.put("b", 20, 1).is_none());

        // Check updated values
        assert_eq!(cache.get(&"a"), Some(&10));
        assert_eq!(cache.get(&"b"), Some(&20));
    }

    #[test]
    fn test_slru_remove() {
        // Create a cache with capacity 4, with protected capacity 2
        let mut cache = make_cache(4, 2);

        // Add items
        cache.put("a", 1, 1);
        cache.put("b", 2, 1);

        // Access "a" to promote it to protected
        assert_eq!(cache.get(&"a"), Some(&1));

        // Remove items
        assert_eq!(cache.remove(&"a"), Some(1)); // From protected
        assert_eq!(cache.remove(&"b"), Some(2)); // From probationary

        // Check that items are gone
        assert_eq!(cache.get(&"a"), None);
        assert_eq!(cache.get(&"b"), None);

        // Check that removing non-existent item returns None
        assert_eq!(cache.remove(&"c"), None);
    }

    #[test]
    fn test_slru_clear() {
        // Create a cache with capacity 4, with protected capacity 2
        let mut cache = make_cache(4, 2);

        // Add items
        cache.put("a", 1, 1);
        cache.put("b", 2, 1);
        cache.put("c", 3, 1);
        cache.put("d", 4, 1);

        // Clear the cache
        cache.clear();

        // Check that cache is empty
        assert_eq!(cache.len(), 0);
        assert!(cache.is_empty());

        // Check that items are gone
        assert_eq!(cache.get(&"a"), None);
        assert_eq!(cache.get(&"b"), None);
        assert_eq!(cache.get(&"c"), None);
        assert_eq!(cache.get(&"d"), None);
    }

    #[test]
    fn test_slru_complex_values() {
        // Create a cache with capacity 4, with protected capacity 2
        let mut cache = make_cache(4, 2);

        #[derive(Debug, Clone, PartialEq)]
        struct ComplexValue {
            id: usize,
            data: String,
        }

        // Add complex values
        cache.put(
            "a",
            ComplexValue {
                id: 1,
                data: "a-data".to_string(),
            },
            1,
        );
        cache.put(
            "b",
            ComplexValue {
                id: 2,
                data: "b-data".to_string(),
            },
            1,
        );

        // Modify a value using get_mut
        if let Some(value) = cache.get_mut(&"a") {
            value.id = 100;
            value.data = "a-modified".to_string();
        }

        // Check the modified value
        let a = cache.get(&"a").unwrap();
        assert_eq!(a.id, 100);
        assert_eq!(a.data, "a-modified");
    }

    #[test]
    fn test_slru_with_ratio() {
        // Test the with_ratio constructor
        let mut cache = make_cache(4, 2);

        assert_eq!(cache.cap().get(), 4);
        assert_eq!(cache.protected_max_size().get(), 2);

        // Test basic functionality
        assert_eq!(cache.put("a", 1, 1), None);
        assert_eq!(cache.put("b", 2, 1), None);

        // Access "a" to promote it to protected
        assert_eq!(cache.get(&"a"), Some(&1));

        // Fill the cache
        assert_eq!(cache.put("c", 3, 1), None);
        assert_eq!(cache.put("d", 4, 1), None);

        // Add another item, should evict "b" from probationary
        let result = cache.put("e", 5, 1);
        assert_eq!(result.unwrap()[0].0, "b");

        // Check that protected items remain
        assert_eq!(cache.get(&"a"), Some(&1));
    }

    // Test that SlruInner works correctly (internal tests)
    #[test]
    fn test_slru_segment_directly() {
        let config = SlruCacheConfig {
            capacity: NonZeroUsize::new(4).unwrap(),
            protected_capacity: NonZeroUsize::new(2).unwrap(),
            max_size: u64::MAX,
        };
        let mut segment: SlruInner<&str, i32, DefaultHashBuilder> =
            SlruInner::init(config, DefaultHashBuilder::default());

        assert_eq!(segment.len(), 0);
        assert!(segment.is_empty());
        assert_eq!(segment.cap().get(), 4);
        assert_eq!(segment.protected_max_size().get(), 2);

        segment.put("a", 1, 1);
        segment.put("b", 2, 1);
        assert_eq!(segment.len(), 2);

        // Access to promote
        assert_eq!(segment.get(&"a"), Some(&1));
        assert_eq!(segment.get(&"b"), Some(&2));
    }

    #[test]
    fn test_slru_concurrent_access() {
        extern crate std;
        use std::sync::{Arc, Mutex};
        use std::thread;
        use std::vec::Vec;

        let cache = Arc::new(Mutex::new(make_cache::<String, i32>(100, 50)));
        let num_threads = 4;
        let ops_per_thread = 100;

        let mut handles: Vec<std::thread::JoinHandle<()>> = Vec::new();

        for t in 0..num_threads {
            let cache = Arc::clone(&cache);
            handles.push(thread::spawn(move || {
                for i in 0..ops_per_thread {
                    let key = std::format!("key_{}_{}", t, i);
                    let mut guard = cache.lock().unwrap();
                    guard.put(key.clone(), i, 1);
                    let _ = guard.get(&key);
                }
            }));
        }

        for handle in handles {
            handle.join().unwrap();
        }

        let mut guard = cache.lock().unwrap();
        assert!(guard.len() <= 100);
        guard.clear(); // Clean up for MIRI
    }

    #[test]
    fn test_slru_size_aware_tracking() {
        let mut cache = make_cache(10, 3);

        assert_eq!(cache.current_size(), 0);
        assert_eq!(cache.max_size(), u64::MAX);

        cache.put("a", 1, 100);
        cache.put("b", 2, 200);
        cache.put("c", 3, 150);

        assert_eq!(cache.current_size(), 450);
        assert_eq!(cache.len(), 3);

        // Clear should reset size
        cache.clear();
        assert_eq!(cache.current_size(), 0);
    }

    #[test]
    fn test_slru_init_constructor() {
        let config = SlruCacheConfig {
            capacity: NonZeroUsize::new(1000).unwrap(),
            protected_capacity: NonZeroUsize::new(300).unwrap(),
            max_size: 1024 * 1024,
        };
        let cache: SlruCache<String, i32> = SlruCache::init(config, None);

        assert_eq!(cache.current_size(), 0);
        assert_eq!(cache.max_size(), 1024 * 1024);
    }

    #[test]
    fn test_slru_with_limits_constructor() {
        let config = SlruCacheConfig {
            capacity: NonZeroUsize::new(100).unwrap(),
            protected_capacity: NonZeroUsize::new(30).unwrap(),
            max_size: 1024 * 1024,
        };
        let cache: SlruCache<String, String> = SlruCache::init(config, None);

        assert_eq!(cache.current_size(), 0);
        assert_eq!(cache.max_size(), 1024 * 1024);
        assert_eq!(cache.cap().get(), 100);
        assert_eq!(cache.protected_max_size().get(), 30);
    }

    #[test]
    fn test_slru_record_miss() {
        use crate::metrics::CacheMetrics;

        let mut cache: SlruCache<String, i32> = make_cache(100, 30);

        cache.record_miss(100);
        cache.record_miss(200);

        let metrics = cache.metrics();
        assert_eq!(metrics.get("cache_misses").unwrap(), &2.0);
    }

    #[test]
    fn test_slru_get_mut() {
        let mut cache: SlruCache<String, i32> = make_cache(100, 30);

        cache.put("key".to_string(), 10, 1);
        assert_eq!(cache.get(&"key".to_string()), Some(&10));

        // Modify via get_mut
        if let Some(val) = cache.get_mut(&"key".to_string()) {
            *val = 42;
        }
        assert_eq!(cache.get(&"key".to_string()), Some(&42));

        // get_mut on missing key returns None
        assert!(cache.get_mut(&"missing".to_string()).is_none());
    }

    /// Helper to create an SlruCache with max_size limit
    fn make_cache_with_max_size(
        cap: usize,
        protected: usize,
        max_size: u64,
    ) -> SlruCache<String, i32> {
        let config = SlruCacheConfig {
            capacity: NonZeroUsize::new(cap).unwrap(),
            protected_capacity: NonZeroUsize::new(protected).unwrap(),
            max_size,
        };
        SlruCache::init(config, None)
    }

    /// Test that SLRU evicts items when max_size would be exceeded.
    /// This test verifies the cache respects the max_size limit, not just entry count.
    #[test]
    fn test_slru_max_size_triggers_eviction() {
        // Create cache with large entry capacity (100) but small max_size (100 bytes)
        // This means size limit should be the constraint, not entry count
        let mut cache = make_cache_with_max_size(100, 30, 100);

        // Insert items that fit within max_size
        cache.put("a".to_string(), 1, 30); // total: 30
        cache.put("b".to_string(), 2, 30); // total: 60
        cache.put("c".to_string(), 3, 30); // total: 90

        assert_eq!(cache.len(), 3, "Should have 3 items");
        assert_eq!(cache.current_size(), 90, "Size should be 90");

        // Insert item that would exceed max_size (90 + 20 = 110 > 100)
        // This SHOULD trigger eviction to stay within max_size
        cache.put("d".to_string(), 4, 20);

        // Cache should evict to stay within max_size
        // The LRU item ("a") should be evicted, leaving b, c, d
        // Total size should be: 30 + 30 + 20 = 80 (after evicting "a")
        assert!(
            cache.current_size() <= 100,
            "current_size {} exceeds max_size 100",
            cache.current_size()
        );

        // Verify that "a" was evicted
        assert!(
            cache.get(&"a".to_string()).is_none() || cache.current_size() <= 100,
            "Either 'a' should be evicted OR size should be within limits"
        );
    }

    /// Test that max_size eviction works even with larger objects
    #[test]
    fn test_slru_max_size_eviction_large_objects() {
        // Create cache with max_size = 500 bytes, large entry capacity
        let mut cache = make_cache_with_max_size(1000, 200, 500);

        // Insert objects that each take 100 bytes
        for i in 0..5 {
            cache.put(format!("key{}", i), i, 100);
        }

        assert_eq!(cache.len(), 5);
        assert_eq!(cache.current_size(), 500, "Should have exactly 500 bytes");

        // Insert one more - should trigger eviction to stay within 500
        cache.put("overflow".to_string(), 99, 100);

        // Expected: oldest item evicted, size still <= 500
        assert!(
            cache.current_size() <= 500,
            "SLRU BUG: current_size {} exceeds max_size 500 after insert. \
             SLRU must evict items to respect max_size limit.",
            cache.current_size()
        );
    }

    #[test]
    fn test_slru_contains_non_promoting() {
        // Create cache: 4 total (2 probationary, 2 protected)
        let mut cache = make_cache(4, 2);
        cache.put("a", 1, 1);
        cache.put("b", 2, 1);

        // contains() should return true for existing keys
        assert!(cache.contains(&"a"));
        assert!(cache.contains(&"b"));
        assert!(!cache.contains(&"c"));

        // contains() should NOT promote entries
        // Both should still be in probationary
        // Adding "c" and "d" should fill probationary
        cache.put("c", 3, 1);
        cache.put("d", 4, 1);

        // At this point all 4 items are in probationary (none accessed twice)
        assert_eq!(cache.len(), 4);
        assert!(cache.contains(&"a"));
        assert!(cache.contains(&"d"));
    }

    #[test]
    fn test_put_returns_none_when_no_eviction() {
        let mut cache = make_cache(10, 3);
        assert!(cache.put("a", 1, 1).is_none());
        assert!(cache.put("b", 2, 1).is_none());
    }

    #[test]
    fn test_put_returns_single_eviction() {
        let mut cache = make_cache(2, 1);
        cache.put("a", 1, 1);
        cache.put("b", 2, 1);
        let result = cache.put("c", 3, 1);
        assert!(result.is_some());
        let evicted = result.unwrap();
        assert_eq!(evicted.len(), 1);
    }

    #[test]
    fn test_put_replacement_returns_none() {
        let mut cache = make_cache(10, 3);
        cache.put("a", 1, 1);
        // Replacement is not eviction - returns None
        let result = cache.put("a", 2, 1);
        assert!(result.is_none());
        // Value should be updated
        assert_eq!(cache.get(&"a"), Some(&2));
    }

    #[test]
    fn test_put_returns_multiple_evictions_size_based() {
        let config = SlruCacheConfig {
            capacity: NonZeroUsize::new(10).unwrap(),
            protected_capacity: NonZeroUsize::new(3).unwrap(),
            max_size: 100,
        };
        let mut cache = SlruCache::init(config, None);
        for i in 0..10 {
            cache.put(i, i, 10);
        }
        let result = cache.put(99, 99, 50);
        let evicted = result.unwrap();
        assert_eq!(evicted.len(), 5);
    }

    #[test]
    fn test_slru_peek_non_promoting() {
        // Create cache: 4 total (2 probationary, 2 protected)
        let mut cache = make_cache(4, 2);
        cache.put("a", 1, 1);
        cache.put("b", 2, 1);

        // peek() should return value without promoting
        assert_eq!(cache.peek(&"a"), Some(&1));
        assert_eq!(cache.peek(&"b"), Some(&2));
        assert_eq!(cache.peek(&"c"), None);

        // "a" and "b" should still be in probationary (not promoted)
        // Now access "a" with get() to promote it
        cache.get(&"a");

        // Add "c" and "d" - if peek promoted, this would evict "a"
        cache.put("c", 3, 1);
        cache.put("d", 4, 1);

        // "a" was promoted by get(), so it should still exist
        assert!(cache.contains(&"a"));
    }
}