Struct TwoQCore

Source

pub struct TwoQCore<K, V> { /* private fields */ }

Expand description

Core Two-Queue (2Q) cache implementation.

Implements the 2Q replacement algorithm with two queues:

Probation (A1in): FIFO queue for newly inserted items
Protected (Am): LRU queue for frequently accessed items

New items enter probation. Re-accessing an item in probation promotes it to protected. This provides scan resistance by keeping one-time accesses from polluting the main cache.

§Type Parameters

K: Key type, must be Clone + Eq + Hash
V: Value type

§Example

use cachekit::policy::two_q::TwoQCore;

// 100 capacity, 25% probation
let mut cache = TwoQCore::new(100, 0.25);

// Insert goes to probation
cache.insert("key1", "value1");
assert!(cache.contains(&"key1"));

// First get promotes to protected
cache.get(&"key1");

// Update existing key
cache.insert("key1", "new_value");
assert_eq!(cache.get(&"key1"), Some(&"new_value"));

§Eviction Behavior

When capacity is exceeded:

If probation exceeds its cap, evict from probation front (oldest)
Otherwise, evict from protected back (LRU)

§Implementation

Uses raw pointer linked lists for O(1) operations with minimal overhead.

Implementations§

Source §

impl<K, V> TwoQCore<K, V>
where K: Clone + Eq + Hash,

Source

pub fn new(protected_cap: usize, a1_frac: f64) -> Self

Creates a new 2Q cache with the specified capacity and probation fraction.

protected_cap: Total cache capacity (maximum number of entries)
a1_frac: Fraction of capacity allocated to probation queue (0.0 to 1.0)

A typical value for a1_frac is 0.25 (25% for probation).

§Panics

Panics if a1_frac is negative, NaN, or greater than 1.0.

§Example

use cachekit::policy::two_q::TwoQCore;

// 100 capacity, 25% probation (25 items max in probation)
let cache: TwoQCore<String, i32> = TwoQCore::new(100, 0.25);
assert_eq!(cache.capacity(), 100);
assert!(cache.is_empty());

Source

pub fn get(&mut self, key: &K) -> Option<&V>

Retrieves a value by key, promoting from probation to protected if needed.

If the key is in probation, accessing it promotes the entry to the protected queue (demonstrating it’s not a one-time access). If already in protected, moves it to the MRU position.

§Example

use cachekit::policy::two_q::TwoQCore;

let mut cache = TwoQCore::new(100, 0.25);
cache.insert("key", 42);

// First access: in probation, now promotes to protected
assert_eq!(cache.get(&"key"), Some(&42));

// Second access: already in protected, moves to MRU
assert_eq!(cache.get(&"key"), Some(&42));

// Missing key
assert_eq!(cache.get(&"missing"), None);

Source

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts or updates a key-value pair.

If the key exists, updates the value in place (no queue change)
If the key is new, inserts into the probation queue
May trigger eviction if capacity is exceeded

§Example

use cachekit::policy::two_q::TwoQCore;

let mut cache = TwoQCore::new(100, 0.25);

// New insert goes to probation
cache.insert("key", "initial");
assert_eq!(cache.len(), 1);

// Update existing key
cache.insert("key", "updated");
assert_eq!(cache.get(&"key"), Some(&"updated"));
assert_eq!(cache.len(), 1);  // Still 1 entry

Source

pub fn len(&self) -> usize

Returns the number of entries in the cache.

§Example

use cachekit::policy::two_q::TwoQCore;

let mut cache = TwoQCore::new(100, 0.25);
assert_eq!(cache.len(), 0);

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

Source

pub fn is_empty(&self) -> bool

Returns true if the cache is empty.

§Example

use cachekit::policy::two_q::TwoQCore;

let mut cache: TwoQCore<&str, i32> = TwoQCore::new(100, 0.25);
assert!(cache.is_empty());

cache.insert("key", 42);
assert!(!cache.is_empty());

Source

pub fn capacity(&self) -> usize

Returns the total cache capacity.

§Example

use cachekit::policy::two_q::TwoQCore;

let cache: TwoQCore<String, i32> = TwoQCore::new(500, 0.25);
assert_eq!(cache.capacity(), 500);

Source

pub fn contains(&self, key: &K) -> bool

Returns true if the key exists in the cache.

Does not affect queue positions (no promotion on contains).

§Example

use cachekit::policy::two_q::TwoQCore;

let mut cache = TwoQCore::new(100, 0.25);
cache.insert("key", 42);

assert!(cache.contains(&"key"));
assert!(!cache.contains(&"missing"));

Source

pub fn clear(&mut self)

Clears all entries from the cache.

§Example

use cachekit::policy::two_q::TwoQCore;

let mut cache = TwoQCore::new(100, 0.25);
cache.insert("a", 1);
cache.insert("b", 2);

cache.clear();
assert!(cache.is_empty());
assert!(!cache.contains(&"a"));

Source

pub fn peek(&self, key: &K) -> Option<&V>

Side-effect-free lookup by key.

Does not promote entries between queues or update MRU position.

§Example

use cachekit::policy::two_q::TwoQCore;

let mut cache = TwoQCore::new(100, 0.25);
cache.insert("key", 42);
assert_eq!(cache.peek(&"key"), Some(&42));
assert_eq!(cache.peek(&"missing"), None);

Source

pub fn remove(&mut self, key: &K) -> Option<V>

Removes a specific key-value pair, returning the value if it existed.

Detaches the entry from its queue (probation or protected) and adjusts the queue counters.

§Example

use cachekit::policy::two_q::TwoQCore;

let mut cache = TwoQCore::new(100, 0.25);
cache.insert("key", 42);
assert_eq!(cache.remove(&"key"), Some(42));
assert!(!cache.contains(&"key"));

Source §

impl<K, V> TwoQCore<K, V>
where K: Clone + Eq + Hash,

Source

pub fn metrics_snapshot(&self) -> TwoQMetricsSnapshot

Returns a snapshot of cache metrics.

Trait Implementations§

Source §

impl<K, V> Cache<K, V> for TwoQCore<K, V>
where K: Clone + Eq + Hash,

Implementation of the Cache trait for 2Q.

Allows TwoQCore to be used through the unified cache interface.

§Example

use cachekit::traits::Cache;
use cachekit::policy::two_q::TwoQCore;

let mut cache: TwoQCore<&str, i32> = TwoQCore::new(100, 0.25);

// Use via Cache trait
cache.insert("key", 42);
assert_eq!(cache.get(&"key"), Some(&42));
assert!(cache.contains(&"key"));