velesdb_core/cache/

lru.rs

//! LRU Cache implementation for `VelesDB`.
//!
//! Thread-safe LRU cache with O(1) operations using `IndexMap`.
//! Based on arXiv:2310.11703v2 recommendations.
//!
//! # Performance (US-CORE-003-14)
//!
//! | Operation | Complexity | Notes |
//! |-----------|------------|-------|
//! | insert | O(1) | Amortized |
//! | get | O(n) | With recency update (shift_remove) |
//! | remove | O(1) | swap_remove |
//! | eviction | O(1) | shift_remove from front |

#![allow(clippy::cast_precision_loss)] // Precision loss acceptable for hit rate calculation

use indexmap::IndexMap;
use parking_lot::RwLock;
use std::hash::Hash;
use std::sync::atomic::{AtomicU64, Ordering};

/// Cache statistics for monitoring.
#[derive(Debug, Clone, Default)]
pub struct CacheStats {
    /// Number of cache hits.
    pub hits: u64,
    /// Number of cache misses.
    pub misses: u64,
    /// Number of evictions.
    pub evictions: u64,
}

impl CacheStats {
    /// Calculate hit rate (0.0 to 1.0).
    #[must_use]
    pub fn hit_rate(&self) -> f64 {
        let total = self.hits + self.misses;
        if total == 0 {
            0.0
        } else {
            self.hits as f64 / total as f64
        }
    }
}

/// Thread-safe LRU cache with O(1) operations.
///
/// Uses `IndexMap` internally which preserves insertion order
/// and provides O(1) access, making move-to-back operations efficient.
pub struct LruCache<K, V>
where
    K: Hash + Eq + Clone,
    V: Clone,
{
    /// Maximum capacity.
    capacity: usize,
    /// Internal data protected by `RwLock`.
    /// `IndexMap` preserves insertion order (front = LRU, back = MRU).
    inner: RwLock<IndexMap<K, V>>,
    /// Statistics (atomic for lock-free reads).
    hits: AtomicU64,
    misses: AtomicU64,
    evictions: AtomicU64,
}

impl<K, V> LruCache<K, V>
where
    K: Hash + Eq + Clone,
    V: Clone,
{
    /// Create a new LRU cache with the given capacity.
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        Self {
            capacity,
            inner: RwLock::new(IndexMap::with_capacity(capacity)),
            hits: AtomicU64::new(0),
            misses: AtomicU64::new(0),
            evictions: AtomicU64::new(0),
        }
    }

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

    /// Get the current number of entries.
    #[must_use]
    pub fn len(&self) -> usize {
        self.inner.read().len()
    }

    /// Check if the cache is empty.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.inner.read().is_empty()
    }

    /// Insert a key-value pair, evicting LRU entry if at capacity.
    ///
    /// O(1) amortized complexity.
    pub fn insert(&self, key: K, value: V) {
        let mut inner = self.inner.write();

        // Check if key already exists - if so, remove and re-insert to move to back
        if inner.shift_remove(&key).is_some() {
            // Key existed, just re-insert at back
            inner.insert(key, value);
            return;
        }

        // Evict LRU (front) if at capacity
        if inner.len() >= self.capacity {
            // shift_remove(0) removes the first element (LRU)
            if inner.shift_remove_index(0).is_some() {
                self.evictions.fetch_add(1, Ordering::Relaxed);
            }
        }

        // Insert new entry at back (MRU)
        inner.insert(key, value);
    }

    /// Get a value by key, updating recency.
    ///
    /// F-18: Uses a single write lock for lookup + move-to-back in one operation,
    /// eliminating the previous read-lock → clone → write-lock → re-clone pattern
    /// (2 locks + 2 clones → 1 lock + 1 clone).
    #[must_use]
    pub fn get(&self, key: &K) -> Option<V> {
        let mut inner = self.inner.write();
        if let Some((_idx, owned_key, value)) = inner.shift_remove_full(key) {
            let cloned = value.clone();
            // Re-insert at back (MRU position)
            inner.insert(owned_key, value);
            drop(inner);
            self.hits.fetch_add(1, Ordering::Relaxed);
            Some(cloned)
        } else {
            drop(inner);
            self.misses.fetch_add(1, Ordering::Relaxed);
            None
        }
    }

    /// Get a value without updating recency (peek).
    ///
    /// O(1) complexity with only read lock.
    #[must_use]
    pub fn peek(&self, key: &K) -> Option<V> {
        let inner = self.inner.read();
        inner.get(key).cloned()
    }

    /// Remove a key from the cache.
    ///
    /// O(1) complexity using `swap_remove` (doesn't preserve order of other elements).
    pub fn remove(&self, key: &K) {
        let mut inner = self.inner.write();
        inner.swap_remove(key);
    }

    /// Clear all entries.
    pub fn clear(&self) {
        let mut inner = self.inner.write();
        inner.clear();
    }

    /// Get cache statistics.
    #[must_use]
    pub fn stats(&self) -> CacheStats {
        CacheStats {
            hits: self.hits.load(Ordering::Relaxed),
            misses: self.misses.load(Ordering::Relaxed),
            evictions: self.evictions.load(Ordering::Relaxed),
        }
    }
}

impl<K, V> Default for LruCache<K, V>
where
    K: Hash + Eq + Clone,
    V: Clone,
{
    fn default() -> Self {
        Self::new(10_000) // Default 10K entries
    }
}