sieve_cache/

sync.rs

use crate::SieveCache;
use std::borrow::Borrow;
use std::fmt;
use std::hash::Hash;
use std::sync::{Arc, Mutex, MutexGuard, PoisonError};

/// A thread-safe wrapper around `SieveCache`.
///
/// This provides a thread-safe implementation of the SIEVE cache algorithm by wrapping
/// the standard `SieveCache` in an `Arc<Mutex<>>`. It offers the same functionality as
/// the underlying cache but with thread safety guarantees.
///
/// # Thread Safety
///
/// All operations acquire a lock on the entire cache, which provides strong consistency
/// but may become a bottleneck under high contention. For workloads with high concurrency,
/// consider using [`ShardedSieveCache`](crate::ShardedSieveCache) instead, which partitions
/// the cache into multiple independently-locked segments.
///
/// ## Lock Behavior
///
/// The thread safety mechanism works as follows:
///
/// - Simple query operations (e.g., `get`, `contains_key`) hold the lock only long enough to
///   read and clone the value
/// - Modification operations (e.g., `insert`, `remove`) hold the lock for the duration of the change
/// - Operations that accept callbacks have specific lock behavior:
///   - `get_mut` acquires and releases the lock repeatedly to avoid deadlocks, using a clone-modify-update pattern
///   - `for_each_value`, `for_each_entry`, and `retain` collect data under the lock, then
///     release it before processing to avoid blocking other threads
///
/// ## Deadlock Prevention
///
/// This implementation prevents deadlocks by:
///
/// - Never allowing callbacks to execute while holding the cache lock
/// - Using a clone-modify-update pattern for all callbacks that need to modify values
/// - Ensuring lock acquisition is always done in a consistent order
/// - Providing explicit transaction methods that make locking transparent to the user
///
/// ## Consistency Guarantees
///
/// - Operations on individual keys are atomic and isolated
/// - Snapshot-based operations (e.g., iteration, bulk operations) may not reflect
///   concurrent modifications
/// - When using callback functions, be aware they execute outside the lock which means
///   the cache state may change between lock acquisitions
///
/// # Examples
///
/// ```
/// # use sieve_cache::SyncSieveCache;
/// let cache = SyncSieveCache::new(100).unwrap();
///
/// // Multiple threads can safely access the cache
/// cache.insert("key1".to_string(), "value1".to_string());
/// assert_eq!(cache.get(&"key1".to_string()), Some("value1".to_string()));
/// ```
///
/// Example with callbacks:
///
/// ```
/// # use sieve_cache::SyncSieveCache;
/// # use std::thread;
/// let cache = SyncSieveCache::new(100).unwrap();
/// cache.insert("key1".to_string(), 1);
/// cache.insert("key2".to_string(), 2);
///
/// // Create a clone to move into another thread
/// let cache_clone = cache.clone();
///
/// // Spawn a thread that modifies values
/// let handle = thread::spawn(move || {
///     // The cache is safely accessible from multiple threads
///     cache_clone.for_each_value(|value| {
///         *value += 10;  // Add 10 to each value
///     });
/// });
///
/// // Wait for the background thread to complete
/// handle.join().unwrap();
///
/// // Values have been updated
/// assert_eq!(cache.get(&"key1".to_string()), Some(11));
/// assert_eq!(cache.get(&"key2".to_string()), Some(12));
/// ```
#[derive(Clone)]
pub struct SyncSieveCache<K, V>
where
    K: Eq + Hash + Clone + Send + Sync,
    V: Send + Sync,
{
    inner: Arc<Mutex<SieveCache<K, V>>>,
}

impl<K, V> Default for SyncSieveCache<K, V>
where
    K: Eq + Hash + Clone + Send + Sync,
    V: Send + Sync,
{
    /// Creates a new cache with a default capacity of 100 entries.
    ///
    /// # Panics
    ///
    /// Panics if the underlying `SieveCache::new()` returns an error, which should never
    /// happen for a non-zero capacity.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// # use std::default::Default;
    /// let cache: SyncSieveCache<String, u32> = Default::default();
    /// assert_eq!(cache.capacity(), 100);
    /// ```
    fn default() -> Self {
        Self::new(100).expect("Failed to create cache with default capacity")
    }
}

impl<K, V> fmt::Debug for SyncSieveCache<K, V>
where
    K: Eq + Hash + Clone + Send + Sync + fmt::Debug,
    V: Send + Sync + fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let guard = self.locked_cache();
        f.debug_struct("SyncSieveCache")
            .field("capacity", &guard.capacity())
            .field("len", &guard.len())
            .finish()
    }
}

impl<K, V> From<SieveCache<K, V>> for SyncSieveCache<K, V>
where
    K: Eq + Hash + Clone + Send + Sync,
    V: Send + Sync,
{
    /// Creates a new thread-safe cache from an existing `SieveCache`.
    ///
    /// This allows for easily converting a single-threaded cache to a thread-safe version.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::{SieveCache, SyncSieveCache};
    /// let mut single_threaded = SieveCache::new(100).unwrap();
    /// single_threaded.insert("key".to_string(), "value".to_string());
    ///
    /// // Convert to thread-safe version
    /// let thread_safe = SyncSieveCache::from(single_threaded);
    /// assert_eq!(thread_safe.get(&"key".to_string()), Some("value".to_string()));
    /// ```
    fn from(cache: SieveCache<K, V>) -> Self {
        Self {
            inner: Arc::new(Mutex::new(cache)),
        }
    }
}

impl<K, V> IntoIterator for SyncSieveCache<K, V>
where
    K: Eq + Hash + Clone + Send + Sync,
    V: Clone + Send + Sync,
{
    type Item = (K, V);
    type IntoIter = std::vec::IntoIter<(K, V)>;

    /// Converts the cache into an iterator over its key-value pairs.
    ///
    /// This collects all entries into a Vec and returns an iterator over that Vec.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// # use std::collections::HashMap;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), "value1".to_string());
    /// cache.insert("key2".to_string(), "value2".to_string());
    ///
    /// // Collect into a HashMap
    /// let map: HashMap<_, _> = cache.into_iter().collect();
    /// assert_eq!(map.len(), 2);
    /// assert_eq!(map.get("key1"), Some(&"value1".to_string()));
    /// ```
    fn into_iter(self) -> Self::IntoIter {
        self.entries().into_iter()
    }
}

impl<K, V> SyncSieveCache<K, V>
where
    K: Eq + Hash + Clone + Send + Sync,
    V: Send + Sync,
{
    /// Creates a new thread-safe cache with the given capacity.
    ///
    /// # Errors
    ///
    /// Returns an error if the capacity is zero.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::<String, String>::new(100).unwrap();
    /// ```
    pub fn new(capacity: usize) -> Result<Self, &'static str> {
        let cache = SieveCache::new(capacity)?;
        Ok(Self {
            inner: Arc::new(Mutex::new(cache)),
        })
    }

    /// Returns a locked reference to the underlying cache.
    ///
    /// This is an internal helper method to abstract away the lock handling.
    /// If the mutex is poisoned due to a panic in another thread, the poison
    /// error is recovered from by calling `into_inner()` to access the underlying data.
    #[inline]
    fn locked_cache(&self) -> MutexGuard<'_, SieveCache<K, V>> {
        self.inner.lock().unwrap_or_else(PoisonError::into_inner)
    }

    /// Returns the capacity of the cache.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::<String, u32>::new(100).unwrap();
    /// assert_eq!(cache.capacity(), 100);
    /// ```
    pub fn capacity(&self) -> usize {
        self.locked_cache().capacity()
    }

    /// Returns the number of cached values.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key".to_string(), "value".to_string());
    /// assert_eq!(cache.len(), 1);
    /// ```
    pub fn len(&self) -> usize {
        self.locked_cache().len()
    }

    /// Returns `true` when no values are currently cached.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::<String, String>::new(100).unwrap();
    /// assert!(cache.is_empty());
    ///
    /// cache.insert("key".to_string(), "value".to_string());
    /// assert!(!cache.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.locked_cache().is_empty()
    }

    /// Returns `true` if there is a value in the cache mapped to by `key`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key".to_string(), "value".to_string());
    ///
    /// assert!(cache.contains_key(&"key".to_string()));
    /// assert!(!cache.contains_key(&"missing".to_string()));
    /// ```
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        Q: Hash + Eq + ?Sized,
        K: Borrow<Q>,
    {
        let guard = self.locked_cache();
        guard.contains_key(key)
    }

    /// Gets a clone of the value in the cache mapped to by `key`.
    ///
    /// If no value exists for `key`, this returns `None`.
    ///
    /// # Note
    ///
    /// Unlike the unwrapped `SieveCache`, this returns a clone of the value
    /// rather than a reference, since the mutex guard would be dropped after
    /// this method returns. This means that `V` must implement `Clone`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key".to_string(), "value".to_string());
    ///
    /// assert_eq!(cache.get(&"key".to_string()), Some("value".to_string()));
    /// assert_eq!(cache.get(&"missing".to_string()), None);
    /// ```
    pub fn get<Q>(&self, key: &Q) -> Option<V>
    where
        Q: Hash + Eq + ?Sized,
        K: Borrow<Q>,
        V: Clone,
    {
        let mut guard = self.locked_cache();
        guard.get(key).cloned()
    }

    /// Gets a mutable reference to the value in the cache mapped to by `key` via a callback function.
    ///
    /// If no value exists for `key`, the callback will not be invoked and this returns `false`.
    /// Otherwise, the callback is invoked with a mutable reference to the value and this returns `true`.
    ///
    /// This operation marks the entry as "visited" in the SIEVE algorithm,
    /// which affects eviction decisions.
    ///
    /// # Thread Safety
    ///
    /// This method operates safely with recursive calls by:
    ///
    /// 1. Cloning the value with a short-lived lock
    /// 2. Releasing the lock during callback execution
    /// 3. Re-acquiring the lock to update the original value
    ///
    /// This approach means:
    ///
    /// - The callback can safely make other calls to the same cache instance
    /// - The value can be modified by other threads during the callback execution
    /// - Changes are not visible to other threads until the callback completes
    /// - Last writer wins if multiple threads modify the same key concurrently
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key".to_string(), "value".to_string());
    ///
    /// // Modify the value in-place
    /// cache.get_mut(&"key".to_string(), |value| {
    ///     *value = "new_value".to_string();
    /// });
    ///
    /// assert_eq!(cache.get(&"key".to_string()), Some("new_value".to_string()));
    /// ```
    pub fn get_mut<Q, F>(&self, key: &Q, f: F) -> bool
    where
        Q: Hash + Eq + ?Sized,
        K: Borrow<Q>,
        F: FnOnce(&mut V),
        V: Clone,
    {
        // Get a clone of the value if it exists, to avoid deadlocks
        // if the callback tries to use other methods on this cache
        let value_opt = {
            let mut guard = self.locked_cache();
            // Clone the value before releasing the lock
            guard.get_mut(key).map(|v| v.clone())
        };

        if let Some(mut value) = value_opt {
            // Execute the callback on the cloned value without holding the lock
            f(&mut value);

            // Update the value back to the cache
            let mut guard = self.locked_cache();
            if let Some(original) = guard.get_mut(key) {
                *original = value;
                true
            } else {
                // Key was removed while callback was executing
                false
            }
        } else {
            false
        }
    }

    /// Maps `key` to `value` in the cache, possibly evicting old entries.
    ///
    /// This method returns `true` when this is a new entry, and `false` if an existing entry was
    /// updated.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    ///
    /// // Insert a new key
    /// assert!(cache.insert("key1".to_string(), "value1".to_string()));
    ///
    /// // Update an existing key
    /// assert!(!cache.insert("key1".to_string(), "updated_value".to_string()));
    /// ```
    pub fn insert(&self, key: K, value: V) -> bool {
        let mut guard = self.locked_cache();
        guard.insert(key, value)
    }

    /// Removes the cache entry mapped to by `key`.
    ///
    /// This method returns the value removed from the cache. If `key` did not map to any value,
    /// then this returns `None`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key".to_string(), "value".to_string());
    ///
    /// // Remove an existing key
    /// assert_eq!(cache.remove(&"key".to_string()), Some("value".to_string()));
    ///
    /// // Attempt to remove a missing key
    /// assert_eq!(cache.remove(&"key".to_string()), None);
    /// ```
    pub fn remove<Q>(&self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Eq + Hash + ?Sized,
    {
        let mut guard = self.locked_cache();
        guard.remove(key)
    }

    /// Removes and returns a value from the cache that was not recently accessed.
    ///
    /// This implements the SIEVE eviction algorithm to select an entry for removal.
    /// If no suitable value exists, this returns `None`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(2).unwrap();
    /// cache.insert("key1".to_string(), "value1".to_string());
    /// cache.insert("key2".to_string(), "value2".to_string());
    ///
    /// // Accessing key1 marks it as recently used
    /// assert_eq!(cache.get(&"key1".to_string()), Some("value1".to_string()));
    ///
    /// // Insert a new key, which should evict key2
    /// cache.insert("key3".to_string(), "value3".to_string());
    ///
    /// // key2 should have been evicted
    /// assert_eq!(cache.get(&"key2".to_string()), None);
    /// ```
    pub fn evict(&self) -> Option<V> {
        let mut guard = self.locked_cache();
        guard.evict()
    }

    /// Removes all entries from the cache.
    ///
    /// This operation clears all stored values and resets the cache to an empty state,
    /// while maintaining the original capacity.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), "value1".to_string());
    /// cache.insert("key2".to_string(), "value2".to_string());
    ///
    /// assert_eq!(cache.len(), 2);
    ///
    /// cache.clear();
    /// assert_eq!(cache.len(), 0);
    /// assert!(cache.is_empty());
    /// ```
    pub fn clear(&self) {
        let mut guard = self.locked_cache();
        guard.clear();
    }

    /// Returns an iterator over all keys in the cache.
    ///
    /// The order of keys is not specified and should not be relied upon.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// # use std::collections::HashSet;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), "value1".to_string());
    /// cache.insert("key2".to_string(), "value2".to_string());
    ///
    /// let keys: HashSet<_> = cache.keys().into_iter().collect();
    /// assert_eq!(keys.len(), 2);
    /// assert!(keys.contains(&"key1".to_string()));
    /// assert!(keys.contains(&"key2".to_string()));
    /// ```
    pub fn keys(&self) -> Vec<K> {
        let guard = self.locked_cache();
        guard.keys().cloned().collect()
    }

    /// Returns all values in the cache.
    ///
    /// The order of values is not specified and should not be relied upon.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// # use std::collections::HashSet;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), "value1".to_string());
    /// cache.insert("key2".to_string(), "value2".to_string());
    ///
    /// let values: HashSet<_> = cache.values().into_iter().collect();
    /// assert_eq!(values.len(), 2);
    /// assert!(values.contains(&"value1".to_string()));
    /// assert!(values.contains(&"value2".to_string()));
    /// ```
    pub fn values(&self) -> Vec<V>
    where
        V: Clone,
    {
        let guard = self.locked_cache();
        guard.values().cloned().collect()
    }

    /// Returns all key-value pairs in the cache.
    ///
    /// The order of pairs is not specified and should not be relied upon.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// # use std::collections::HashMap;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), "value1".to_string());
    /// cache.insert("key2".to_string(), "value2".to_string());
    ///
    /// let entries: HashMap<_, _> = cache.entries().into_iter().collect();
    /// assert_eq!(entries.len(), 2);
    /// assert_eq!(entries.get(&"key1".to_string()), Some(&"value1".to_string()));
    /// assert_eq!(entries.get(&"key2".to_string()), Some(&"value2".to_string()));
    /// ```
    pub fn entries(&self) -> Vec<(K, V)>
    where
        V: Clone,
    {
        let guard = self.locked_cache();
        guard.iter().map(|(k, v)| (k.clone(), v.clone())).collect()
    }

    /// Applies a function to all values in the cache.
    ///
    /// This method safely processes values by collecting them with the lock held,
    /// then releasing the lock before applying the function to each value individually.
    /// If the function modifies the values, the changes are saved back to the cache.
    ///
    /// # Thread Safety
    ///
    /// This method operates in three phases:
    /// 1. It acquires the lock and creates a complete snapshot of the cache
    /// 2. It releases the lock and applies the callback to each value
    /// 3. It acquires the lock again individually for each value when writing changes back
    ///
    /// This approach means:
    /// - The lock is not held during callback execution, preventing lock contention
    /// - If other threads modify the cache between steps 1 and 3, those changes might be overwritten
    /// - The callback sees a point-in-time snapshot that might not reflect the latest state
    /// - For long-running operations, consider using individual key operations instead
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), "value1".to_string());
    /// cache.insert("key2".to_string(), "value2".to_string());
    ///
    /// // Update all values by appending text
    /// cache.for_each_value(|value| {
    ///     *value = format!("{}_updated", value);
    /// });
    ///
    /// assert_eq!(cache.get(&"key1".to_string()), Some("value1_updated".to_string()));
    /// assert_eq!(cache.get(&"key2".to_string()), Some("value2_updated".to_string()));
    /// ```
    pub fn for_each_value<F>(&self, mut f: F)
    where
        F: FnMut(&mut V),
        V: Clone,
    {
        // First, safely collect all keys and values while holding the lock
        let entries = self.with_lock(|inner_cache| {
            inner_cache
                .iter()
                .map(|(k, v)| (k.clone(), v.clone()))
                .collect::<Vec<(K, V)>>()
        });

        // Process each value outside the lock
        let mut updated_entries = Vec::new();
        for (key, mut value) in entries {
            f(&mut value);
            updated_entries.push((key, value));
        }

        // Update any changed values back to the cache
        for (key, value) in updated_entries {
            self.insert(key, value);
        }
    }

    /// Applies a function to all key-value pairs in the cache.
    ///
    /// This method safely processes key-value pairs by collecting them with the lock held,
    /// then releasing the lock before applying the function to each pair individually.
    /// If the function modifies the values, the changes are saved back to the cache.
    ///
    /// # Thread Safety
    ///
    /// This method operates in three phases:
    /// 1. It acquires the lock and creates a complete snapshot of the cache
    /// 2. It releases the lock and applies the callback to each key-value pair
    /// 3. It acquires the lock again individually for each entry when writing changes back
    ///
    /// This approach means:
    /// - The lock is not held during callback execution, preventing lock contention
    /// - If other threads modify the cache between steps 1 and 3, those changes might be overwritten
    /// - The callback sees a point-in-time snapshot that might not reflect the latest state
    /// - For long-running operations, consider using individual key operations instead
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), "value1".to_string());
    /// cache.insert("key2".to_string(), "value2".to_string());
    ///
    /// // Update all values associated with keys containing '1'
    /// cache.for_each_entry(|(key, value)| {
    ///     if key.contains('1') {
    ///         *value = format!("{}_special", value);
    ///     }
    /// });
    ///
    /// assert_eq!(cache.get(&"key1".to_string()), Some("value1_special".to_string()));
    /// assert_eq!(cache.get(&"key2".to_string()), Some("value2".to_string()));
    /// ```
    pub fn for_each_entry<F>(&self, mut f: F)
    where
        F: FnMut((&K, &mut V)),
        V: Clone,
    {
        // First, safely collect all keys and values while holding the lock
        let entries = self.with_lock(|inner_cache| {
            inner_cache
                .iter()
                .map(|(k, v)| (k.clone(), v.clone()))
                .collect::<Vec<(K, V)>>()
        });

        // Process each entry outside the lock
        let mut updated_entries = Vec::new();
        for (key, mut value) in entries {
            let key_ref = &key;
            f((key_ref, &mut value));
            updated_entries.push((key, value));
        }

        // Update any changed values back to the cache
        for (key, value) in updated_entries {
            self.insert(key, value);
        }
    }

    /// Gets exclusive access to the underlying cache to perform multiple operations atomically.
    ///
    /// This is useful when you need to perform a series of operations that depend on each other
    /// and you want to ensure that no other thread can access the cache between operations.
    ///
    /// # Thread Safety
    ///
    /// This method provides the strongest thread safety guarantees by:
    ///
    /// - Acquiring the lock once for the entire duration of the callback
    /// - Allowing multiple operations to be performed atomically within a single lock scope
    /// - Ensuring all operations within the callback are fully isolated from other threads
    ///
    /// However, this also means:
    ///
    /// - The entire cache is locked during the callback execution
    /// - Other threads will be blocked from accessing the cache until the callback completes
    /// - Long-running operations within the callback will cause high contention
    /// - Callbacks must never try to access the same cache instance recursively (deadlock risk)
    ///
    /// This method should be used when you need atomic multi-step operations but used
    /// sparingly in high-concurrency environments.
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    ///
    /// cache.with_lock(|inner_cache| {
    ///     // Perform multiple operations atomically
    ///     inner_cache.insert("key1".to_string(), "value1".to_string());
    ///     inner_cache.insert("key2".to_string(), "value2".to_string());
    ///
    ///     // We can check internal state mid-transaction
    ///     assert_eq!(inner_cache.len(), 2);
    /// });
    /// ```
    pub fn with_lock<F, T>(&self, f: F) -> T
    where
        F: FnOnce(&mut SieveCache<K, V>) -> T,
    {
        let mut guard = self.locked_cache();
        f(&mut guard)
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// Removes all entries for which the provided function returns `false`.
    /// The elements are visited in arbitrary, unspecified order.
    ///
    /// This method offers two modes of operation:
    /// - Default mode: evaluates predicates outside the lock, with separate remove operations
    /// - Batch mode: evaluates predicates outside the lock, then performs removals in a single batch
    ///
    /// # Thread Safety
    ///
    /// This method operates in three phases:
    /// 1. It acquires the lock and creates a complete snapshot of the cache
    /// 2. It releases the lock and applies the predicate to each entry
    /// 3. It either:
    ///    - Acquires the lock again individually for each entry to be removed (default), or
    ///    - Acquires the lock once and removes all entries in a batch (batch mode)
    ///
    /// This approach means:
    /// - The lock is not held during predicate execution, preventing lock contention
    /// - If other threads modify the cache between steps 1 and 3, the method may:
    ///   - Remove entries that were modified and would now pass the predicate
    ///   - Miss removing entries added after the snapshot was taken
    /// - The predicate sees a point-in-time snapshot that might not reflect the latest state
    /// - For strict consistency requirements, use `with_lock` instead
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), 100);
    /// cache.insert("key2".to_string(), 200);
    /// cache.insert("key3".to_string(), 300);
    ///
    /// // Keep only entries with values greater than 150
    /// cache.retain(|_, value| *value > 150);
    ///
    /// assert_eq!(cache.len(), 2);
    /// assert!(!cache.contains_key(&"key1".to_string()));
    /// assert!(cache.contains_key(&"key2".to_string()));
    /// assert!(cache.contains_key(&"key3".to_string()));
    /// ```
    ///
    /// Using batch mode (more efficient):
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), 100);
    /// cache.insert("key2".to_string(), 200);
    /// cache.insert("key3".to_string(), 300);
    ///
    /// // Keep only entries with values greater than 150 (batch mode)
    /// cache.retain_batch(|_, value| *value > 150);
    ///
    /// assert_eq!(cache.len(), 2);
    /// assert!(!cache.contains_key(&"key1".to_string()));
    /// assert!(cache.contains_key(&"key2".to_string()));
    /// assert!(cache.contains_key(&"key3".to_string()));
    /// ```
    pub fn retain<F>(&self, mut f: F)
    where
        F: FnMut(&K, &V) -> bool,
        V: Clone,
    {
        // First, safely collect all entries while holding the lock
        let entries = self.with_lock(|inner_cache| {
            inner_cache
                .iter()
                .map(|(k, v)| (k.clone(), v.clone()))
                .collect::<Vec<(K, V)>>()
        });

        // Now check each entry against the predicate without holding the lock
        for (key, value) in entries {
            if !f(&key, &value) {
                // Remove entries that don't match the predicate
                // This acquires the lock for each removal operation
                self.remove(&key);
            }
        }
    }

    /// Retains only the elements specified by the predicate, using batch processing.
    ///
    /// This is an optimized version of `retain()` that collects all keys to remove first,
    /// then removes them in a single batch operation with a single lock acquisition.
    /// This is more efficient when removing many entries, especially in high-contention scenarios.
    ///
    /// # Thread Safety
    ///
    /// This method has improved performance characteristics:
    /// - Only acquires the lock twice (once for collection, once for removal)
    /// - Performs all removals in a single atomic operation
    /// - Reduces lock contention compared to standard `retain()`
    ///
    /// However, it still has the same consistency characteristics as `retain()`:
    /// - The snapshot might not reflect concurrent modifications
    /// - There's a window between collecting entries and removing them where
    ///   other threads might modify the cache
    ///
    /// # Examples
    ///
    /// ```
    /// # use sieve_cache::SyncSieveCache;
    /// let cache = SyncSieveCache::new(100).unwrap();
    /// cache.insert("key1".to_string(), 100);
    /// cache.insert("key2".to_string(), 200);
    /// cache.insert("key3".to_string(), 300);
    ///
    /// // Keep only entries with values greater than 150
    /// cache.retain_batch(|_, value| *value > 150);
    ///
    /// assert_eq!(cache.len(), 2);
    /// assert!(!cache.contains_key(&"key1".to_string()));
    /// assert!(cache.contains_key(&"key2".to_string()));
    /// assert!(cache.contains_key(&"key3".to_string()));
    /// ```
    pub fn retain_batch<F>(&self, mut f: F)
    where
        F: FnMut(&K, &V) -> bool,
        V: Clone,
    {
        // First, safely collect all entries while holding the lock
        let entries = self.with_lock(|inner_cache| {
            inner_cache
                .iter()
                .map(|(k, v)| (k.clone(), v.clone()))
                .collect::<Vec<(K, V)>>()
        });

        // Collect keys to remove without holding the lock
        let mut keys_to_remove = Vec::new();
        for (key, value) in entries {
            if !f(&key, &value) {
                keys_to_remove.push(key);
            }
        }

        // If there are keys to remove, do it in a single batch operation
        if !keys_to_remove.is_empty() {
            self.with_lock(|inner_cache| {
                for key in keys_to_remove {
                    inner_cache.remove(&key);
                }
            });
        }
    }

    /// Returns a recommended cache capacity based on current utilization.
    ///
    /// This method analyzes the current cache utilization and recommends a new capacity based on:
    /// - The number of entries with the 'visited' flag set
    /// - The current capacity and fill ratio
    /// - A target utilization range
    ///
    /// The recommendation aims to keep the cache size optimal:
    /// - If many entries are frequently accessed (high utilization), it suggests increasing capacity
    /// - If few entries are accessed frequently (low utilization), it suggests decreasing capacity
    /// - Within a normal utilization range, it keeps the capacity stable
    ///
    /// # Arguments
    ///
    /// * `min_factor` - Minimum scaling factor (e.g., 0.5 means never recommend less than 50% of current capacity)
    /// * `max_factor` - Maximum scaling factor (e.g., 2.0 means never recommend more than 200% of current capacity)
    /// * `low_threshold` - Utilization threshold below which capacity is reduced (e.g., 0.3 means 30% utilization)
    /// * `high_threshold` - Utilization threshold above which capacity is increased (e.g., 0.7 means 70% utilization)
    ///
    /// # Examples
    ///
    /// ```rust
    /// # use sieve_cache::SyncSieveCache;
    /// # fn main() {
    /// # let cache = SyncSieveCache::<String, i32>::new(100).unwrap();
    /// #
    /// # // Add items to the cache
    /// # for i in 0..80 {
    /// #     cache.insert(i.to_string(), i);
    /// #     
    /// #     // Accessing some items to mark them as visited
    /// #     if i % 2 == 0 {
    /// #         cache.get(&i.to_string());
    /// #     }
    /// # }
    /// #
    /// // Get a recommended capacity with default parameters
    /// let recommended = cache.recommended_capacity(0.5, 2.0, 0.3, 0.7);
    /// println!("Recommended capacity: {}", recommended);
    /// # }
    /// ```
    ///
    /// # Default Recommendation Parameters
    ///
    /// If you're unsure what parameters to use, these values provide a reasonable starting point:
    /// - `min_factor`: 0.5 (never recommend less than half current capacity)
    /// - `max_factor`: 2.0 (never recommend more than twice current capacity)
    /// - `low_threshold`: 0.3 (reduce capacity if utilization below 30%)
    /// - `high_threshold`: 0.7 (increase capacity if utilization above 70%)
    pub fn recommended_capacity(
        &self,
        min_factor: f64,
        max_factor: f64,
        low_threshold: f64,
        high_threshold: f64,
    ) -> usize {
        self.with_lock(|inner_cache| {
            inner_cache.recommended_capacity(min_factor, max_factor, low_threshold, high_threshold)
        })
    }
}

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

    #[test]
    fn test_sync_cache() {
        let cache = SyncSieveCache::new(100).unwrap();

        // Insert a value
        assert!(cache.insert("key1".to_string(), "value1".to_string()));

        // Read back the value
        assert_eq!(cache.get(&"key1".to_string()), Some("value1".to_string()));

        // Check contains_key
        assert!(cache.contains_key(&"key1".to_string()));

        // Check capacity and length
        assert_eq!(cache.capacity(), 100);
        assert_eq!(cache.len(), 1);

        // Remove a value
        assert_eq!(
            cache.remove(&"key1".to_string()),
            Some("value1".to_string())
        );
        assert_eq!(cache.len(), 0);
        assert!(cache.is_empty());
    }

    #[test]
    fn test_multithreaded_access() {
        let cache = SyncSieveCache::new(100).unwrap();
        let cache_clone = cache.clone();

        // Add some initial data
        cache.insert("shared".to_string(), "initial".to_string());

        // Spawn a thread that updates the cache
        let thread = thread::spawn(move || {
            cache_clone.insert("shared".to_string(), "updated".to_string());
            cache_clone.insert("thread_only".to_string(), "thread_value".to_string());
        });

        // Main thread operations
        cache.insert("main_only".to_string(), "main_value".to_string());

        // Wait for thread to complete
        thread.join().unwrap();

        // Verify results
        assert_eq!(
            cache.get(&"shared".to_string()),
            Some("updated".to_string())
        );
        assert_eq!(
            cache.get(&"thread_only".to_string()),
            Some("thread_value".to_string())
        );
        assert_eq!(
            cache.get(&"main_only".to_string()),
            Some("main_value".to_string())
        );
        assert_eq!(cache.len(), 3);
    }

    #[test]
    fn test_with_lock() {
        let cache = SyncSieveCache::new(100).unwrap();

        // Perform multiple operations atomically
        cache.with_lock(|inner_cache| {
            inner_cache.insert("key1".to_string(), "value1".to_string());
            inner_cache.insert("key2".to_string(), "value2".to_string());
            inner_cache.insert("key3".to_string(), "value3".to_string());
        });

        assert_eq!(cache.len(), 3);
    }

    #[test]
    fn test_get_mut() {
        let cache = SyncSieveCache::new(100).unwrap();
        cache.insert("key".to_string(), "value".to_string());

        // Modify the value in-place
        let modified = cache.get_mut(&"key".to_string(), |value| {
            *value = "new_value".to_string();
        });
        assert!(modified);

        // Verify the value was updated
        assert_eq!(cache.get(&"key".to_string()), Some("new_value".to_string()));

        // Try to modify a non-existent key
        let modified = cache.get_mut(&"missing".to_string(), |_| {
            panic!("This should not be called");
        });
        assert!(!modified);
    }

    #[test]
    fn test_clear() {
        let cache = SyncSieveCache::new(10).unwrap();
        cache.insert("key1".to_string(), "value1".to_string());
        cache.insert("key2".to_string(), "value2".to_string());

        assert_eq!(cache.len(), 2);
        assert!(!cache.is_empty());

        cache.clear();

        assert_eq!(cache.len(), 0);
        assert!(cache.is_empty());
        assert_eq!(cache.get(&"key1".to_string()), None);
        assert_eq!(cache.get(&"key2".to_string()), None);
    }

    #[test]
    fn test_keys_values_entries() {
        let cache = SyncSieveCache::new(10).unwrap();
        cache.insert("key1".to_string(), "value1".to_string());
        cache.insert("key2".to_string(), "value2".to_string());

        // Test keys
        let keys = cache.keys();
        assert_eq!(keys.len(), 2);
        assert!(keys.contains(&"key1".to_string()));
        assert!(keys.contains(&"key2".to_string()));

        // Test values
        let values = cache.values();
        assert_eq!(values.len(), 2);
        assert!(values.contains(&"value1".to_string()));
        assert!(values.contains(&"value2".to_string()));

        // Test entries
        let entries = cache.entries();
        assert_eq!(entries.len(), 2);
        assert!(entries.contains(&("key1".to_string(), "value1".to_string())));
        assert!(entries.contains(&("key2".to_string(), "value2".to_string())));
    }

    #[test]
    fn test_for_each_methods() {
        let cache = SyncSieveCache::new(10).unwrap();
        cache.insert("key1".to_string(), "value1".to_string());
        cache.insert("key2".to_string(), "value2".to_string());

        // Test for_each_value
        cache.for_each_value(|value| {
            *value = format!("{}_updated", value);
        });

        assert_eq!(
            cache.get(&"key1".to_string()),
            Some("value1_updated".to_string())
        );
        assert_eq!(
            cache.get(&"key2".to_string()),
            Some("value2_updated".to_string())
        );

        // Test for_each_entry
        cache.for_each_entry(|(key, value)| {
            if key == "key1" {
                *value = format!("{}_special", value);
            }
        });

        assert_eq!(
            cache.get(&"key1".to_string()),
            Some("value1_updated_special".to_string())
        );
        assert_eq!(
            cache.get(&"key2".to_string()),
            Some("value2_updated".to_string())
        );
    }

    #[test]
    fn test_retain() {
        let cache = SyncSieveCache::new(10).unwrap();

        // Add some entries
        cache.insert("even1".to_string(), 2);
        cache.insert("even2".to_string(), 4);
        cache.insert("odd1".to_string(), 1);
        cache.insert("odd2".to_string(), 3);

        assert_eq!(cache.len(), 4);

        // Keep only entries with even values
        cache.retain(|_, v| v % 2 == 0);

        assert_eq!(cache.len(), 2);
        assert!(cache.contains_key(&"even1".to_string()));
        assert!(cache.contains_key(&"even2".to_string()));
        assert!(!cache.contains_key(&"odd1".to_string()));
        assert!(!cache.contains_key(&"odd2".to_string()));

        // Keep only entries with keys containing '1'
        cache.retain(|k, _| k.contains('1'));

        assert_eq!(cache.len(), 1);
        assert!(cache.contains_key(&"even1".to_string()));
        assert!(!cache.contains_key(&"even2".to_string()));
    }

    #[test]
    fn test_recommended_capacity() {
        // Test case 1: Empty cache - should return current capacity
        let cache = SyncSieveCache::<String, u32>::new(100).unwrap();
        assert_eq!(cache.recommended_capacity(0.5, 2.0, 0.3, 0.7), 100);

        // Test case 2: Low utilization (few visited nodes)
        let cache = SyncSieveCache::new(100).unwrap();
        // Fill the cache first without marking anything as visited
        for i in 0..90 {
            cache.insert(i.to_string(), i);
        }

        // Now mark only a tiny fraction as visited
        for i in 0..5 {
            cache.get(&i.to_string()); // Only 5% visited
        }

        // With very low utilization and high fill, should recommend decreasing capacity
        let recommended = cache.recommended_capacity(0.5, 2.0, 0.1, 0.7); // Lower threshold to ensure test passes
        assert!(recommended < 100);
        assert!(recommended >= 50); // Should not go below min_factor

        // Test case 3: High utilization (many visited nodes)
        let cache = SyncSieveCache::new(100).unwrap();
        for i in 0..90 {
            cache.insert(i.to_string(), i);
            // Mark 80% as visited
            if i % 10 != 0 {
                cache.get(&i.to_string());
            }
        }
        // With 80% utilization, should recommend increasing capacity
        let recommended = cache.recommended_capacity(0.5, 2.0, 0.3, 0.7);
        assert!(recommended > 100);
        assert!(recommended <= 200); // Should not go above max_factor

        // Test case 4: Normal utilization (should keep capacity the same)
        let cache = SyncSieveCache::new(100).unwrap();
        for i in 0..90 {
            cache.insert(i.to_string(), i);
            // Mark 50% as visited
            if i % 2 == 0 {
                cache.get(&i.to_string());
            }
        }
        // With 50% utilization (between thresholds), capacity should be fairly stable
        let recommended = cache.recommended_capacity(0.5, 2.0, 0.3, 0.7);
        assert!(
            recommended >= 95,
            "With normal utilization, capacity should be close to original"
        );
        assert!(
            recommended <= 100,
            "With normal utilization, capacity should not exceed original"
        );

        // Test case 5: Low fill ratio (few entries relative to capacity)
        let cache = SyncSieveCache::new(2000).unwrap();
        // Add only a few entries (5% of capacity)
        for i in 0..100 {
            cache.insert(i.to_string(), i);
            // Mark all as visited to simulate high hit rate
            cache.get(&i.to_string());
        }

        // Even though utilization is high (100% visited), the fill ratio is very low (5%)
        // so it should still recommend decreasing capacity
        let recommended = cache.recommended_capacity(0.5, 2.0, 0.3, 0.7);
        assert!(
            recommended < 2000,
            "With low fill ratio, capacity should be decreased despite high hit rate"
        );
        assert!(
            recommended >= 1000, // min_factor = 0.5
            "Capacity should not go below min_factor of current capacity"
        );
    }

    #[test]
    fn test_deadlock_prevention() {
        let cache = Arc::new(SyncSieveCache::new(100).unwrap());

        // Add some initial data
        cache.insert("key1".to_string(), 1);
        cache.insert("key2".to_string(), 2);

        // Clone for use in threads
        let cache_clone1 = cache.clone();
        let cache_clone2 = cache.clone();

        // Thread 1: Recursively accesses the cache within get_mut callback
        let thread1 = thread::spawn(move || {
            cache_clone1.get_mut(&"key1".to_string(), |value| {
                // This would deadlock with an unsafe implementation!
                // Attempt to get another value while holding the lock
                let value2 = cache_clone1.get(&"key2".to_string());
                assert_eq!(value2, Some(2));

                // Even modify another value
                cache_clone1.insert("key3".to_string(), 3);

                *value += 10;
            });
        });

        // Thread 2: Also performs operations that would deadlock with unsafe impl
        let thread2 = thread::spawn(move || {
            // Sleep to ensure thread1 starts first
            thread::sleep(std::time::Duration::from_millis(10));

            // These operations would deadlock if thread1 held a lock during its callback
            cache_clone2.insert("key4".to_string(), 4);
            assert_eq!(cache_clone2.get(&"key2".to_string()), Some(2));
        });

        // Both threads should complete without deadlock
        thread1.join().unwrap();
        thread2.join().unwrap();

        // Verify final state
        assert_eq!(cache.get(&"key1".to_string()), Some(11)); // 1 + 10
        assert_eq!(cache.get(&"key3".to_string()), Some(3));
        assert_eq!(cache.get(&"key4".to_string()), Some(4));
    }
}