Struct S3FIFO 

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

S3FIFO is a non-thread-safe implementation of an S3-FIFO

Paper here: https://jasony.me/publication/sosp23-s3fifo.pdf

S3FIFO is a cache that is split into three parts:

1. A small cache that holds the most recently used items
2. A main cache that holds the most frequently used items
3. A ghost cache that holds keys that have been evicted from the main cache

use s3_fifo::{S3FIFO, S3FIFOKey};

// The cached value must be Clone.
// Hash is optional and allows using the S3FIFOKey struct
#[derive(Clone, Hash)]
struct Foobar { a: i32 }

// Create a cache with a capacity of 128 (small: 12, main: 115, ghost: 115)
let mut cache = S3FIFO::new(128);
let value = Foobar { a: 1 };
let key = S3FIFOKey::new(&value);

// Check if the item is in the cache before inserting
if let None = cache.get(&key) {
    cache.put(key.clone(), value);
    assert!(cache.get(&key).is_some());
}

Implementations

impl<K: PartialEq + Clone, V> S3FIFO<K, V>

pub fn new(capacity: usize) -> Self

Create a new S3FIFO cache with 10% of the capacity for the small cache and 90% of the capacity for the main cache.

The ghost cache is also 90% of the capacity but only holds keys and not values.

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

Read an item from the cache. If the item is present, then its frequency is incremented and a reference is returned.

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

Read an item from the cache. If the item is present, then its frequency is incremented and a mutable reference is returned.

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

Write an item to the cache. This may evict an item from the cache. The returnted tuple is a mutable reference to the value in the cache and any evicted value.

pub fn pop(&mut self) -> Option<V>

Remove an item from the cache.

pub fn drain(&mut self) -> Vec<V>

Remove all items from the cache, leaving it empty and with the same capacity.