cache_rs/

gdsf.rs

//! Greedy Dual-Size Frequency (GDSF) Cache Implementation
//!
//! GDSF is a sophisticated cache replacement algorithm designed for **variable-sized objects**.
//! It combines object size, access frequency, and aging into a unified priority formula,
//! making it ideal for CDN caches, image caches, and any scenario where cached objects
//! have different sizes.
//!
//! # How the Algorithm Works
//!
//! GDSF calculates priority for each cached item using the formula:
//!
//! ```text
//! Priority = (Frequency / Size) + GlobalAge
//! ```
//!
//! This formula cleverly balances multiple factors:
//! - **Frequency**: More frequently accessed items get higher priority
//! - **Size**: Smaller items are favored (more items fit in cache)
//! - **Aging**: Prevents old popular items from staying forever
//!
//! ## Mathematical Formulation
//!
//! ```text
//! For each cache entry i:
//!   - F_i = access frequency of item i
//!   - S_i = size of item i (in bytes)
//!   - GlobalAge = increases on eviction (set to evicted item's priority)
//!   - Priority_i = (F_i / S_i) + GlobalAge
//!
//! On eviction: select item j where Priority_j = min{Priority_i for all i}
//! ```
//!
//! ## Why Size Matters
//!
//! Consider a cache with 10KB capacity:
//! - Option A: Cache one 10KB file accessed 10 times → Priority = 10/10000 = 0.001
//! - Option B: Cache ten 1KB files accessed once each → Each Priority = 1/1000 = 0.001
//!
//! GDSF recognizes that caching many small frequently-accessed items often yields
//! better hit rates than caching fewer large items.
//!
//! ## Data Structure
//!
//! ```text
//! ┌─────────────────────────────────────────────────────────────────────────────┐
//! │                    GDSF Cache (global_age=1.5, max_size=10MB)               │
//! │                                                                              │
//! │  HashMap<K, *Node>              BTreeMap<Priority, List>                     │
//! │  ┌──────────────┐              ┌─────────────────────────────────────────┐   │
//! │  │ "icon.png" ─────────────────│ pri=3.5: [icon.png]   (f=2, s=1KB)      │   │
//! │  │ "thumb.jpg" ────────────────│ pri=2.5: [thumb.jpg]  (f=1, s=1KB)      │   │
//! │  │ "video.mp4" ────────────────│ pri=1.5: [video.mp4]  (f=10, s=100MB)←E │   │
//! │  └──────────────┘              └─────────────────────────────────────────┘   │
//! │                                        ▲                                     │
//! │                                        │                                     │
//! │                                   min_priority=1.5                           │
//! │                                                                              │
//! │  Note: video.mp4 has high frequency (10) but large size (100MB),            │
//! │        so its priority = 10/100000000 + 1.5 ≈ 1.5 (eviction candidate)      │
//! └─────────────────────────────────────────────────────────────────────────────┘
//! ```
//!
//! ## Operations
//!
//! | Operation | Action | Time |
//! |-----------|--------|------|
//! | `get(key)` | Increment frequency, recalculate priority | O(log P) |
//! | `put(key, value, size)` | Insert with priority=(1/size)+age | O(log P) |
//! | `remove(key)` | Remove from priority list, update min_priority | O(log P) |
//!
//! ## Size-Aware Example
//!
//! ```text
//! Cache: max_size=5KB, global_age=0
//!
//! put("small.txt", data, 1KB)   →  pri=1.0, total_size=1KB
//! put("medium.txt", data, 2KB)  →  pri=0.5, total_size=3KB
//! put("large.txt", data, 3KB)   →  pri=0.33, total_size=6KB  OVERFLOW!
//!
//! Eviction needed: evict "large.txt" (lowest priority=0.33)
//! global_age = 0.33
//!
//! put("large.txt", data, 3KB)   →  pri=0.33+0.33=0.66, total_size=6KB  OVERFLOW!
//!
//! Evict again: now "medium.txt" has lowest priority (0.5 < 0.66)
//! Result: small.txt + large.txt fit in 4KB
//! ```
//!
//! # Dual-Limit Capacity
//!
//! GDSF naturally works with size-based limits:
//!
//! - **`max_entries`**: Maximum number of items (prevents too many tiny items)
//! - **`max_size`**: Maximum total size (primary constraint for GDSF)
//!
//! # Performance Characteristics
//!
//! | Metric | Value |
//! |--------|-------|
//! | Get | O(log P) |
//! | Put | O(log P) amortized |
//! | Remove | O(log P) |
//! | Memory per entry | ~120 bytes overhead + key×2 + value |
//!
//! Where P = number of distinct priority buckets. Priority = (frequency/size) + age,
//! quantized to integer keys. BTreeMap provides O(log P) lookups.
//!
//! Higher overhead than simpler algorithms due to priority calculation and
//! BTreeMap-based priority lists.
//!
//! # When to Use GDSF
//!
//! **Good for:**
//! - CDN and proxy caches with variable object sizes
//! - Image thumbnail caches
//! - API response caches with varying payload sizes
//! - File system caches
//! - Any size-constrained cache with heterogeneous objects
//!
//! **Not ideal for:**
//! - Uniform-size objects (simpler algorithms work equally well)
//! - Entry-count-constrained caches (LRU/LFU are simpler)
//! - Very small caches (overhead not justified)
//!
//! # GDSF vs Other Algorithms
//!
//! | Aspect | LRU | LFU | GDSF |
//! |--------|-----|-----|------|
//! | Size-aware | No | No | **Yes** |
//! | Frequency-aware | No | Yes | Yes |
//! | Aging | Implicit | No | Yes |
//! | Best for | Recency | Frequency | Variable-size objects |
//!
//! # Thread Safety
//!
//! `GdsfCache` is **not thread-safe**. For concurrent access, either:
//! - Wrap with `Mutex` or `RwLock`
//! - Use `ConcurrentGdsfCache` (requires `concurrent` feature)
//!
//! # Examples
//!
//! ## Basic Usage
//!
//! ```
//! use cache_rs::GdsfCache;
//! use cache_rs::config::GdsfCacheConfig;
//! use core::num::NonZeroUsize;
//!
//! // Create cache with max 1000 entries and 10MB size limit
//! let config = GdsfCacheConfig {
//!     capacity: NonZeroUsize::new(1000).unwrap(),
//!     initial_age: 0.0,
//!     max_size: 10 * 1024 * 1024,  // 10MB
//! };
//! let mut cache: GdsfCache<String, Vec<u8>> = GdsfCache::init(config, None);
//!
//! // Insert with explicit size tracking
//! let small_data = vec![0u8; 1024];  // 1KB
//! cache.put("small.txt".to_string(), small_data, 1024);
//!
//! let large_data = vec![0u8; 1024 * 1024];  // 1MB
//! cache.put("large.bin".to_string(), large_data, 1024 * 1024);
//!
//! // Small items get higher priority per byte
//! assert!(cache.get(&"small.txt".to_string()).is_some());
//! ```
//!
//! ## CDN-Style Caching
//!
//! ```
//! use cache_rs::GdsfCache;
//! use cache_rs::config::GdsfCacheConfig;
//! use core::num::NonZeroUsize;
//!
//! // 100MB cache for web assets
//! let config = GdsfCacheConfig {
//!     capacity: NonZeroUsize::new(10000).unwrap(),
//!     initial_age: 0.0,
//!     max_size: 100 * 1024 * 1024,
//! };
//! let mut cache: GdsfCache<String, Vec<u8>> = GdsfCache::init(config, None);
//!
//! // Cache various asset types with their sizes
//! fn cache_asset(cache: &mut GdsfCache<String, Vec<u8>>, url: &str, data: Vec<u8>) {
//!     let size = data.len() as u64;
//!     cache.put(url.to_string(), data, size);
//! }
//!
//! // Small, frequently-accessed assets get priority over large, rarely-used ones
//! ```

extern crate alloc;

use crate::config::GdsfCacheConfig;
use crate::entry::CacheEntry;
use crate::list::{List, ListEntry};
use crate::metrics::{CacheMetrics, GdsfCacheMetrics};

/// Metadata for GDSF (Greedy Dual-Size Frequency) cache entries.
///
/// GDSF is a sophisticated algorithm that considers:
/// - **Frequency**: How often the item is accessed
/// - **Size**: Larger items have lower priority per byte
/// - **Aging**: Global clock advances when items are evicted
///
/// # Priority Calculation
///
/// ```text
/// priority = (frequency / size) + global_age
/// ```
///
/// Items with lower priority are evicted first.
///
/// # Examples
///
/// ```
/// use cache_rs::gdsf::GdsfMeta;
///
/// let meta = GdsfMeta::new(1, 0.5); // frequency=1, priority=0.5
/// assert_eq!(meta.frequency, 1);
/// assert_eq!(meta.priority, 0.5);
/// ```
#[derive(Debug, Clone, Copy, Default, PartialEq)]
pub struct GdsfMeta {
    /// Access frequency count.
    pub frequency: u64,

    /// Calculated priority: (frequency / size) + clock.
    /// Lower priority = more likely to be evicted.
    pub priority: f64,
}

impl GdsfMeta {
    /// Creates a new GDSF metadata with the specified frequency and priority.
    ///
    /// # Arguments
    ///
    /// * `frequency` - Initial frequency count
    /// * `priority` - Calculated priority value
    #[inline]
    pub fn new(frequency: u64, priority: f64) -> Self {
        Self {
            frequency,
            priority,
        }
    }

    /// Increments the frequency counter and returns the new value.
    #[inline]
    pub fn increment(&mut self) -> u64 {
        self.frequency += 1;
        self.frequency
    }

    /// Calculates and updates the priority based on frequency, size, and global age.
    ///
    /// # Arguments
    ///
    /// * `size` - Size of the cached item
    /// * `global_age` - Current global age (clock value) of the cache
    ///
    /// # Returns
    ///
    /// The newly calculated priority value.
    #[inline]
    pub fn calculate_priority(&mut self, size: u64, global_age: f64) -> f64 {
        self.priority = if size == 0 {
            f64::INFINITY
        } else {
            (self.frequency as f64 / size as f64) + global_age
        };
        self.priority
    }
}
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;

/// Internal GDSF segment containing the actual cache algorithm.
///
/// Uses `CacheEntry<K, V, GdsfMeta>` as the unified entry type. The map stores
/// raw pointers to list nodes, and all entry data (key, value, size, metadata)
/// is stored in the `CacheEntry`.
pub(crate) struct GdsfSegment<K, V, S = DefaultHashBuilder> {
    config: GdsfCacheConfig,
    global_age: f64,
    min_priority: f64,
    /// Maps keys to node pointers. The node contains CacheEntry with all data.
    map: HashMap<K, *mut ListEntry<CacheEntry<K, V, GdsfMeta>>, S>,
    /// Priority lists: key is (priority * 1000) as u64 for BTreeMap ordering
    priority_lists: BTreeMap<u64, List<CacheEntry<K, V, GdsfMeta>>>,
    metrics: GdsfCacheMetrics,
    /// Current total size of cached content (sum of entry sizes)
    current_size: u64,
}

// SAFETY: GdsfSegment owns all data and raw pointers point only to nodes owned by
// `priority_lists`. Concurrent access is safe when wrapped in proper synchronization primitives.
unsafe impl<K: Send, V: Send, S: Send> Send for GdsfSegment<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 GdsfSegment<K, V, S> {}

impl<K: Hash + Eq, V: Clone, S: BuildHasher> GdsfSegment<K, V, S> {
    /// Creates a new GDSF segment from a configuration.
    ///
    /// This is the **only** way to create a GDSF segment. All configuration
    /// is specified through the [`GdsfCacheConfig`] struct.
    ///
    /// # Arguments
    ///
    /// * `config` - Configuration specifying capacity, initial age, 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: GdsfCacheConfig, hasher: S) -> Self {
        let map_capacity = config.capacity.get().next_power_of_two();
        GdsfSegment {
            global_age: config.initial_age,
            min_priority: 0.0,
            map: HashMap::with_capacity_and_hasher(map_capacity, hasher),
            priority_lists: BTreeMap::new(),
            metrics: GdsfCacheMetrics::new(config.max_size),
            current_size: 0,
            config,
        }
    }

    #[inline]
    pub(crate) fn cap(&self) -> NonZeroUsize {
        self.config.capacity
    }

    #[inline]
    pub(crate) fn len(&self) -> usize {
        self.map.len()
    }

    #[inline]
    pub(crate) fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    #[inline]
    pub(crate) fn global_age(&self) -> f64 {
        self.global_age
    }

    /// 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.config.max_size
    }

    #[inline]
    pub(crate) fn metrics(&self) -> &GdsfCacheMetrics {
        &self.metrics
    }

    #[inline]
    pub(crate) fn record_miss(&mut self, object_size: u64) {
        self.metrics.core.record_miss(object_size);
    }

    fn calculate_priority(&self, frequency: u64, size: u64) -> f64 {
        if size == 0 {
            return f64::INFINITY;
        }
        (frequency as f64 / size as f64) + self.global_age
    }

    unsafe fn update_priority_by_node(
        &mut self,
        node: *mut ListEntry<CacheEntry<K, V, GdsfMeta>>,
    ) -> *mut ListEntry<CacheEntry<K, V, GdsfMeta>>
    where
        K: Clone + Hash + Eq,
    {
        // SAFETY: node is guaranteed valid by caller's contract
        let entry = (*node).get_value_mut();
        let key_cloned = entry.key.clone();
        let size = entry.metadata.size;
        let meta = &mut entry.metadata.algorithm;
        let old_priority = meta.priority;

        meta.increment();

        let global_age = self.global_age;
        let new_priority = meta.calculate_priority(size, global_age);

        let old_priority_key = (old_priority * 1000.0) as u64;
        let new_priority_key = (new_priority * 1000.0) as u64;

        if old_priority_key == new_priority_key {
            self.priority_lists
                .get_mut(&new_priority_key)
                .unwrap()
                .move_to_front(node);
            return node;
        }

        let boxed_entry = self
            .priority_lists
            .get_mut(&old_priority_key)
            .unwrap()
            .remove(node)
            .unwrap();

        if self
            .priority_lists
            .get(&old_priority_key)
            .unwrap()
            .is_empty()
        {
            self.priority_lists.remove(&old_priority_key);
        }

        let entry_ptr = Box::into_raw(boxed_entry);

        let capacity = self.config.capacity;
        self.priority_lists
            .entry(new_priority_key)
            .or_insert_with(|| List::new(capacity));

        self.priority_lists
            .get_mut(&new_priority_key)
            .unwrap()
            .attach_from_other_list(entry_ptr);

        // Update map with new node pointer
        self.map.insert(key_cloned, entry_ptr);
        entry_ptr
    }

    pub(crate) fn get<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q> + Clone,
        Q: ?Sized + Hash + Eq,
    {
        if let Some(&node) = self.map.get(key) {
            unsafe {
                // SAFETY: node comes from our map
                let entry = (*node).get_value();
                let entry_size = entry.metadata.size;
                let meta = &entry.metadata.algorithm;
                self.metrics.core.record_hit(entry_size);
                self.metrics
                    .record_item_access(meta.frequency, entry.metadata.size, meta.priority);

                let new_node = self.update_priority_by_node(node);
                let value = (*new_node).get_value().value.clone();
                Some(value)
            }
        } else {
            None
        }
    }

    pub(crate) fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q> + Clone,
        Q: ?Sized + Hash + Eq,
    {
        if let Some(&node) = self.map.get(key) {
            unsafe {
                // SAFETY: node comes from our map
                let entry = (*node).get_value();
                let entry_size = entry.metadata.size;
                let meta = &entry.metadata.algorithm;
                self.metrics.core.record_hit(entry_size);
                self.metrics
                    .record_item_access(meta.frequency, entry.metadata.size, meta.priority);

                let new_node = self.update_priority_by_node(node);
                let entry_mut = (*new_node).get_value_mut();
                Some(&mut entry_mut.value)
            }
        } else {
            None
        }
    }

    /// Inserts a key-value pair with size tracking.
    ///
    /// 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, val: V, size: u64) -> Option<Vec<(K, V)>>
    where
        K: Clone,
    {
        if size == 0 {
            return None;
        }

        // Check if key exists - update existing entry
        if let Some(&node) = self.map.get(&key) {
            unsafe {
                // SAFETY: node comes from our map
                let entry = (*node).get_value_mut();
                let old_size = entry.metadata.size;
                let meta = &mut entry.metadata.algorithm;
                let old_priority_key = (meta.priority * 1000.0) as u64;
                let frequency = meta.frequency;

                // Remove from old priority list
                let list = self.priority_lists.get_mut(&old_priority_key).unwrap();
                let boxed_entry = list.remove(node).unwrap();

                if list.is_empty() {
                    self.priority_lists.remove(&old_priority_key);
                }

                let entry_ptr = Box::into_raw(boxed_entry);
                let cache_entry = (*entry_ptr).take_value();
                // Discard old key/value since replacement is not eviction
                let _ = (cache_entry.key, cache_entry.value);
                let _ = Box::from_raw(entry_ptr);

                // Update size tracking
                self.current_size = self.current_size.saturating_sub(old_size);
                self.current_size += size;

                // Create new entry with updated values but preserved frequency
                let new_priority = self.calculate_priority(frequency, size);
                let new_priority_key = (new_priority * 1000.0) as u64;

                let new_entry = CacheEntry::with_algorithm_metadata(
                    key.clone(),
                    val,
                    size,
                    GdsfMeta::new(frequency, new_priority),
                );

                let capacity = self.cap();
                let list = self
                    .priority_lists
                    .entry(new_priority_key)
                    .or_insert_with(|| List::new(capacity));

                if let Some(new_node) = list.add(new_entry) {
                    self.map.insert(key, new_node);
                    self.metrics.core.record_size_change(old_size, size);
                    self.metrics.core.bytes_written_to_cache += size;
                    // Replacement is not eviction - don't return the old value
                    return None;
                } else {
                    self.map.remove(&key);
                    return None;
                }
            }
        }

        // New entry - check capacity and size limits
        let capacity = self.config.capacity.get();
        let max_size = self.config.max_size;

        let mut evicted = Vec::new();
        while self.len() >= capacity
            || (self.current_size + size > max_size && !self.map.is_empty())
        {
            if let Some(entry) = self.evict() {
                self.metrics.core.evictions += 1;
                evicted.push(entry);
            } else {
                break;
            }
        }

        let priority = self.calculate_priority(1, size);
        let priority_key = (priority * 1000.0) as u64;

        let cap = self.config.capacity;
        let list = self
            .priority_lists
            .entry(priority_key)
            .or_insert_with(|| List::new(cap));

        let cache_entry =
            CacheEntry::with_algorithm_metadata(key.clone(), val, size, GdsfMeta::new(1, priority));

        if let Some(node) = list.add(cache_entry) {
            self.map.insert(key, node);
            self.current_size += size;

            if self.len() == 1 || priority < self.min_priority {
                self.min_priority = priority;
            }

            self.metrics.core.record_insertion(size);
            self.metrics
                .record_item_cached(size, self.metrics.average_item_size());
            self.metrics.record_item_access(1, size, priority);
        }

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

    /// Removes and returns the eviction candidate (lowest priority entry).
    ///
    /// Also updates the global age to the evicted item's priority (GDSF aging).
    ///
    /// 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.
    ///
    /// Returns `None` if the cache is empty.
    fn evict(&mut self) -> Option<(K, V)> {
        if self.is_empty() {
            return None;
        }

        let min_priority_key = *self.priority_lists.keys().next()?;
        let list = self.priority_lists.get_mut(&min_priority_key)?;
        let entry = list.remove_last()?;

        unsafe {
            // SAFETY: take_value moves the CacheEntry out by value.
            // Box::from_raw frees memory (MaybeUninit won't double-drop).
            let entry_ptr = Box::into_raw(entry);
            let cache_entry = (*entry_ptr).take_value();
            let evicted_size = cache_entry.metadata.size;
            let priority_to_update = cache_entry.metadata.algorithm.priority;

            // Update global age to the evicted item's priority (GDSF aging)
            self.global_age = priority_to_update;
            self.metrics.core.record_removal(evicted_size);
            self.metrics.record_size_based_eviction();
            self.metrics.record_aging_event(priority_to_update);

            self.map.remove(&cache_entry.key);
            self.current_size = self.current_size.saturating_sub(evicted_size);

            // Remove empty priority list
            if list.is_empty() {
                self.priority_lists.remove(&min_priority_key);
            }

            let _ = Box::from_raw(entry_ptr);
            Some((cache_entry.key, cache_entry.value))
        }
    }

    pub(crate) fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        if let Some(node) = self.map.remove(key) {
            unsafe {
                // SAFETY: node comes from our map
                // Read priority before removal — needed to find the correct priority list
                let priority = (*node).get_value().metadata.algorithm.priority;
                let priority_key = (priority * 1000.0) as u64;

                let list = self.priority_lists.get_mut(&priority_key).unwrap();
                let boxed_entry = list.remove(node).unwrap();

                if list.is_empty() {
                    self.priority_lists.remove(&priority_key);
                }

                let entry_ptr = Box::into_raw(boxed_entry);
                let cache_entry = (*entry_ptr).take_value();
                let removed_size = cache_entry.metadata.size;
                self.current_size = self.current_size.saturating_sub(removed_size);
                self.metrics.core.record_removal(removed_size);
                let _ = Box::from_raw(entry_ptr);

                Some(cache_entry.value)
            }
        } else {
            None
        }
    }

    pub(crate) fn clear(&mut self) {
        self.map.clear();
        self.priority_lists.clear();
        self.global_age = 0.0;
        self.min_priority = 0.0;
        self.current_size = 0;
    }

    /// Check if key exists without updating its priority or 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 updating priority or access metadata.
    ///
    /// Unlike `get()`, this method does NOT recalculate the entry's GDSF priority
    /// or change its position in the priority lists.
    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 entry = (*node).get_value();
            Some(&entry.value)
        }
    }
}

impl<K, V, S> core::fmt::Debug for GdsfSegment<K, V, S> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("GdsfSegment")
            .field("capacity", &self.config.capacity)
            .field("len", &self.map.len())
            .field("global_age", &self.global_age)
            .finish()
    }
}

/// An implementation of a Greedy Dual-Size Frequency (GDSF) cache.
#[derive(Debug)]
pub struct GdsfCache<K, V, S = DefaultHashBuilder> {
    segment: GdsfSegment<K, V, S>,
}

impl<K: Hash + Eq, V: Clone, S: BuildHasher> GdsfCache<K, V, S> {
    #[inline]
    pub fn cap(&self) -> NonZeroUsize {
        self.segment.cap()
    }

    #[inline]
    pub fn len(&self) -> usize {
        self.segment.len()
    }

    #[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()
    }

    #[inline]
    pub fn global_age(&self) -> f64 {
        self.segment.global_age()
    }

    #[inline]
    pub fn record_miss(&mut self, object_size: u64) {
        self.segment.record_miss(object_size);
    }

    #[inline]
    pub fn get<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q> + Clone,
        Q: ?Sized + Hash + Eq,
    {
        self.segment.get(key)
    }

    #[inline]
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q> + Clone,
        Q: ?Sized + Hash + Eq,
    {
        self.segment.get_mut(key)
    }

    /// Inserts a key-value pair with explicit size into the cache.
    ///
    /// GDSF is inherently size-aware: the `size` parameter affects priority
    /// calculation (`priority = global_age + frequency / size`), favoring
    /// small, frequently-accessed items.
    ///
    /// # Arguments
    ///
    /// * `key` - The key to insert
    /// * `val` - The value to insert
    /// * `size` - Optional size in bytes. 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, val: V, size: u64) -> Option<Vec<(K, V)>>
    where
        K: Clone,
    {
        self.segment.put(key, val, size)
    }

    #[inline]
    pub fn clear(&mut self) {
        self.segment.clear()
    }

    /// Check if key exists without updating its priority or access metadata.
    ///
    /// Unlike `get()`, this method does NOT update the entry's frequency
    /// or access metadata.
    ///
    /// # Example
    ///
    /// ```
    /// use cache_rs::GdsfCache;
    /// use cache_rs::config::GdsfCacheConfig;
    /// use core::num::NonZeroUsize;
    ///
    /// let config = GdsfCacheConfig {
    ///     capacity: NonZeroUsize::new(2).unwrap(),
    ///     initial_age: 0.0,
    ///     max_size: u64::MAX,
    /// };
    /// let mut cache = GdsfCache::init(config, None);
    /// cache.put("a", 1, 10);
    /// cache.put("b", 2, 10);
    ///
    /// // contains() does NOT update priority
    /// assert!(cache.contains(&"a"));
    /// ```
    #[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 updating priority or access metadata.
    ///
    /// Unlike [`get()`](Self::get), this does NOT recalculate the entry's GDSF
    /// priority or change its position in the priority lists.
    ///
    /// # Example
    ///
    /// ```
    /// use cache_rs::GdsfCache;
    /// use cache_rs::config::GdsfCacheConfig;
    /// use core::num::NonZeroUsize;
    ///
    /// let config = GdsfCacheConfig {
    ///     capacity: NonZeroUsize::new(3).unwrap(),
    ///     initial_age: 0.0,
    ///     max_size: u64::MAX,
    /// };
    /// let mut cache = GdsfCache::init(config, None);
    /// cache.put("a", 1, 1);
    ///
    /// // peek does not change priority
    /// 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)
    }

    /// Removes a key from the cache, returning the value if the key was present.
    #[inline]
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        self.segment.remove(key)
    }
}

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

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

impl<K: Hash + Eq, V: Clone> GdsfCache<K, V, DefaultHashBuilder> {
    /// Creates a new GDSF cache from a configuration.
    ///
    /// This is the **recommended** way to create a GDSF cache. All configuration
    /// is specified through the [`GdsfCacheConfig`] struct.
    ///
    /// # Arguments
    ///
    /// * `config` - Configuration specifying capacity and optional size limit/initial age
    /// * `hasher` - Optional custom hash builder. Pass `None` to use the default.
    ///
    /// # Example
    ///
    /// ```
    /// use cache_rs::GdsfCache;
    /// use cache_rs::config::GdsfCacheConfig;
    /// use core::num::NonZeroUsize;
    ///
    /// // Simple capacity-only cache
    /// let config = GdsfCacheConfig {
    ///     capacity: NonZeroUsize::new(100).unwrap(),
    ///     initial_age: 0.0,
    ///     max_size: u64::MAX,
    /// };
    /// let mut cache: GdsfCache<&str, i32> = GdsfCache::init(config, None);
    /// cache.put("key", 42, 1);
    ///
    /// // Cache with size limit (recommended for GDSF)
    /// let config = GdsfCacheConfig {
    ///     capacity: NonZeroUsize::new(1000).unwrap(),
    ///     initial_age: 0.0,
    ///     max_size: 10 * 1024 * 1024,  // 10MB
    /// };
    /// let cache: GdsfCache<String, Vec<u8>> = GdsfCache::init(config, None);
    /// ```
    pub fn init(config: GdsfCacheConfig, hasher: Option<DefaultHashBuilder>) -> Self {
        GdsfCache {
            segment: GdsfSegment::init(config, hasher.unwrap_or_default()),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::config::GdsfCacheConfig;
    use core::num::NonZeroUsize;

    /// Helper to create a GdsfCache with the given capacity
    fn make_cache<K: Hash + Eq + Clone, V: Clone>(cap: usize) -> GdsfCache<K, V> {
        let config = GdsfCacheConfig {
            capacity: NonZeroUsize::new(cap).unwrap(),
            initial_age: 0.0,
            max_size: u64::MAX,
        };
        GdsfCache::init(config, None)
    }

    #[test]
    fn test_gdsf_basic_operations() {
        let mut cache = make_cache(3);

        assert_eq!(cache.put("a", 1, 1), None);
        assert_eq!(cache.put("b", 2, 2), None);
        assert_eq!(cache.put("c", 3, 1), None);
        assert_eq!(cache.len(), 3);

        assert_eq!(cache.get(&"a"), Some(1));
        assert_eq!(cache.get(&"b"), Some(2));
        assert_eq!(cache.get(&"c"), Some(3));

        assert!(cache.contains(&"a"));
        assert!(!cache.contains(&"d"));
    }

    #[test]
    fn test_gdsf_frequency_priority() {
        let mut cache = make_cache(2);

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

        cache.get(&"a");
        cache.get(&"a");

        cache.put("c", 3, 1);

        assert!(cache.contains(&"a"));
        assert!(!cache.contains(&"b"));
        assert!(cache.contains(&"c"));
    }

    #[test]
    fn test_gdsf_size_consideration() {
        let mut cache = make_cache(2);

        cache.put("small", 1, 1);
        cache.put("large", 2, 10);

        cache.put("medium", 3, 5);

        assert!(cache.contains(&"small"));
        assert!(!cache.contains(&"large"));
        assert!(cache.contains(&"medium"));
    }

    #[test]
    fn test_gdsf_update_existing() {
        let mut cache = make_cache(2);

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

        // Replacement returns None (not eviction)
        assert!(cache.put("key", 2, 2).is_none());
        assert_eq!(cache.get(&"key"), Some(2));
        assert_eq!(cache.len(), 1);
    }

    #[test]
    fn test_gdsf_zero_size_rejection() {
        let mut cache = make_cache(2);

        assert_eq!(cache.put("key", 1, 0), None);
        assert_eq!(cache.len(), 0);
        assert!(!cache.contains(&"key"));
    }

    #[test]
    fn test_gdsf_remove_by_key_legacy() {
        let mut cache = make_cache(2);

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

        assert_eq!(cache.remove(&"a"), Some(1));
        assert_eq!(cache.len(), 1);
        assert!(!cache.contains(&"a"));
        assert!(cache.contains(&"b"));

        assert_eq!(cache.remove(&"nonexistent"), None);
    }

    #[test]
    fn test_gdsf_clear() {
        let mut cache = make_cache(2);

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

        cache.clear();
        assert_eq!(cache.len(), 0);
        assert!(cache.is_empty());
        assert!(!cache.contains(&"a"));
        assert!(!cache.contains(&"b"));
    }

    #[test]
    fn test_gdsf_global_aging() {
        let mut cache = make_cache(2);

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

        let initial_age = cache.global_age();

        cache.put("c", 3, 1);

        assert!(cache.global_age() > initial_age);
    }

    #[test]
    fn test_miri_stacked_borrows_fix() {
        let mut cache = make_cache(10);

        cache.put("a", 1, 10);
        cache.put("b", 2, 20);
        cache.put("c", 3, 15);

        for _ in 0..3 {
            assert_eq!(cache.get(&"a"), Some(1));
            assert_eq!(cache.get(&"b"), Some(2));
            assert_eq!(cache.get(&"c"), Some(3));
        }

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

        if let Some(val) = cache.get_mut(&"a") {
            *val += 10;
        }
        assert_eq!(cache.get(&"a"), Some(11));
    }

    #[test]
    fn test_gdsf_segment_directly() {
        let config = GdsfCacheConfig {
            capacity: NonZeroUsize::new(2).unwrap(),
            initial_age: 0.0,
            max_size: u64::MAX,
        };
        let mut segment: GdsfSegment<&str, i32, DefaultHashBuilder> =
            GdsfSegment::init(config, DefaultHashBuilder::default());
        assert_eq!(segment.len(), 0);
        assert!(segment.is_empty());
        assert_eq!(segment.cap().get(), 2);
        segment.put("a", 1, 1);
        segment.put("b", 2, 2);
        assert_eq!(segment.len(), 2);
        assert_eq!(segment.get(&"a"), Some(1));
        assert_eq!(segment.get(&"b"), Some(2));
    }

    #[test]
    fn test_gdsf_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)));
        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 size = ((i % 10) + 1) as u64; // Varying sizes 1-10
                    let mut guard = cache.lock().unwrap();
                    guard.put(key.clone(), i, size);
                    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_gdsf_size_aware_tracking() {
        let mut cache = make_cache(10);

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

        // GDSF already requires size in put()
        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);

        // GDSF doesn't have remove method, test clear instead
        cache.clear();
        assert_eq!(cache.current_size(), 0);
    }

    #[test]
    fn test_gdsf_init_constructor() {
        let config = GdsfCacheConfig {
            capacity: NonZeroUsize::new(1000).unwrap(),
            initial_age: 0.0,
            max_size: 1024 * 1024,
        };
        let cache: GdsfCache<String, i32> = GdsfCache::init(config, None);

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

    #[test]
    fn test_gdsf_with_limits_constructor() {
        let config = GdsfCacheConfig {
            capacity: NonZeroUsize::new(100).unwrap(),
            initial_age: 0.0,
            max_size: 1024 * 1024,
        };
        let cache: GdsfCache<String, String> = GdsfCache::init(config, None);

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

    #[test]
    fn test_gdsf_contains_non_promoting() {
        let mut cache = make_cache(2);
        cache.put("a", 1, 10);
        cache.put("b", 2, 10);

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

        // Access "b" to increase its priority
        cache.get(&"b");

        // contains() should NOT increase priority of "a"
        assert!(cache.contains(&"a"));

        // Adding "c" should evict "a" (lowest priority), not "b"
        cache.put("c", 3, 10);
        assert!(!cache.contains(&"a")); // "a" was evicted
        assert!(cache.contains(&"b")); // "b" still exists
        assert!(cache.contains(&"c")); // "c" was just added
    }

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

    #[test]
    fn test_put_returns_single_eviction() {
        let mut cache = make_cache(2);
        cache.put("a", 1, 10);
        cache.put("b", 2, 10);
        let result = cache.put("c", 3, 10);
        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);
        cache.put("a", 1, 10);
        // Replacement is not eviction - returns None
        let result = cache.put("a", 2, 10);
        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 = GdsfCacheConfig {
            capacity: NonZeroUsize::new(10).unwrap(),
            initial_age: 0.0,
            max_size: 100,
        };
        let mut cache = GdsfCache::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_gdsf_remove_by_key() {
        let mut cache = make_cache(2);
        cache.put("a", 1, 10);
        cache.put("b", 2, 10);

        // remove() works
        assert_eq!(cache.remove(&"a"), Some(1));
        assert_eq!(cache.len(), 1);
        assert!(!cache.contains(&"a"));
        assert!(cache.contains(&"b"));

        assert_eq!(cache.remove(&"nonexistent"), None);
    }
}