Struct SieveCache

pub struct SieveCache<K: Eq + Hash + Clone, V> { /* private fields */ }

A cache based on the SIEVE eviction algorithm.

SieveCache provides an efficient in-memory cache with a carefully designed eviction strategy that balances simplicity with good performance characteristics, especially on skewed workloads common in real-world applications.

This is the single-threaded implementation. For thread-safe variants, see SyncSieveCache (with the sync feature) and ShardedSieveCache (with the sharded feature).

Type Parameters

• K - The key type, which must implement Eq, Hash, and Clone
• V - The value type, with no constraints

Example

use sieve_cache::SieveCache;

// Create a new cache with capacity for 1000 items
let mut cache = SieveCache::new(1000).unwrap();

// Insert some values
cache.insert("key1".to_string(), "value1".to_string());
cache.insert("key2".to_string(), "value2".to_string());

// Retrieve values - returns references to the values
assert_eq!(cache.get("key1"), Some(&"value1".to_string()));

// Check if the cache contains a key
assert!(cache.contains_key("key1"));
assert!(!cache.contains_key("missing_key"));

// Get a mutable reference to modify a value
if let Some(value) = cache.get_mut("key1") {
    *value = "modified".to_string();
}

// Verify the modification
assert_eq!(cache.get("key1"), Some(&"modified".to_string()));

// Remove a value
let removed = cache.remove("key2");
assert_eq!(removed, Some("value2".to_string()));

Implementations

impl<K: Eq + Hash + Clone, V> SieveCache<K, V>

pub fn new(capacity: usize) -> Result<Self, &'static str>

Creates a new cache with the given capacity.

The capacity represents the maximum number of key-value pairs that can be stored in the cache. When this limit is reached, the cache will use the SIEVE algorithm to evict entries.

Errors

Returns an error if the capacity is zero.

Examples

use sieve_cache::SieveCache;

// Create a cache with space for 100 entries
let cache: SieveCache<String, u32> = SieveCache::new(100).unwrap();

// Capacity of zero is invalid
let invalid = SieveCache::<String, u32>::new(0);
assert!(invalid.is_err());

pub fn capacity(&self) -> usize

Returns the capacity of the cache.

This is the maximum number of entries that can be stored before the cache begins evicting old entries.

Examples

use sieve_cache::SieveCache;

let cache = SieveCache::<String, u32>::new(100).unwrap();
assert_eq!(cache.capacity(), 100);

pub fn len(&self) -> usize

Returns the number of entries currently in the cache.

This value will never exceed the capacity.

Examples

use sieve_cache::SieveCache;

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

cache.insert("key".to_string(), 42);
assert_eq!(cache.len(), 1);

pub fn is_empty(&self) -> bool

Returns true when no values are currently cached.

Examples

use sieve_cache::SieveCache;

let mut cache = SieveCache::<String, u32>::new(100).unwrap();
assert!(cache.is_empty());

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

cache.remove("key");
assert!(cache.is_empty());

pub fn contains_key<Q>(&mut self, key: &Q) -> bool

where Q: Hash + Eq + ?Sized, K: Borrow<Q>,

Returns true if there is a value in the cache mapped to by key.

This operation does not count as an access for the SIEVE algorithm’s visited flag.

Examples

use sieve_cache::SieveCache;

let mut cache = SieveCache::new(100).unwrap();
cache.insert("key".to_string(), "value".to_string());

assert!(cache.contains_key("key"));
assert!(!cache.contains_key("missing"));

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

where Q: Hash + Eq + ?Sized, K: Borrow<Q>,

Gets an immutable reference to the value in the cache mapped to by key.

If no value exists for key, this returns None.

This operation marks the entry as “visited” in the SIEVE algorithm, which affects eviction decisions.

Examples

use sieve_cache::SieveCache;

let mut cache = SieveCache::new(100).unwrap();
cache.insert("key".to_string(), "value".to_string());

assert_eq!(cache.get("key"), Some(&"value".to_string()));
assert_eq!(cache.get("missing"), None);

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

where Q: Hash + Eq + ?Sized, K: Borrow<Q>,

Gets a mutable reference to the value in the cache mapped to by key.

If no value exists for key, this returns None.

This operation marks the entry as “visited” in the SIEVE algorithm, which affects eviction decisions.

Examples

use sieve_cache::SieveCache;

let mut cache = SieveCache::new(100).unwrap();
cache.insert("key".to_string(), "value".to_string());

// Modify the value in-place
if let Some(value) = cache.get_mut("key") {
    *value = "new_value".to_string();
}

assert_eq!(cache.get("key"), Some(&"new_value".to_string()));

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

Maps key to value in the cache, possibly evicting old entries.

If the key already exists, its value is updated and the entry is marked as visited. If the key doesn’t exist and the cache is at capacity, the SIEVE algorithm is used to evict an entry before the new key-value pair is inserted.

Return Value

Returns true when this is a new entry, and false if an existing entry was updated.

Examples

use sieve_cache::SieveCache;

let mut cache = SieveCache::new(100).unwrap();

// Insert a new entry
let is_new = cache.insert("key1".to_string(), "value1".to_string());
assert!(is_new); // Returns true for new entries

// Update an existing entry
let is_new = cache.insert("key1".to_string(), "updated".to_string());
assert!(!is_new); // Returns false for updates

assert_eq!(cache.get("key1"), Some(&"updated".to_string()));

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

where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes the cache entry mapped to by key.

This method explicitly removes an entry from the cache regardless of its “visited” status.

Return Value

Returns the value removed from the cache. If key did not map to any value, then this returns None.

Examples

use sieve_cache::SieveCache;

let mut cache = SieveCache::new(100).unwrap();
cache.insert("key1".to_string(), "value1".to_string());
cache.insert("key2".to_string(), "value2".to_string());

// Remove an existing entry
let removed = cache.remove("key1");
assert_eq!(removed, Some("value1".to_string()));

// Try to remove a non-existent entry
let removed = cache.remove("key1");
assert_eq!(removed, None);

assert_eq!(cache.len(), 1); // Only one entry remains

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

Removes and returns a value from the cache that was not recently accessed.

This method implements the SIEVE eviction algorithm:

1. Starting from the “hand” pointer (or tail if no hand), look for an entry that hasn’t been visited since the last scan
2. Mark all visited entries as non-visited during the scan
3. If a non-visited entry is found, evict it
4. Update the hand to point to the previous node

Return Value

If a suitable entry is found, it is removed from the cache and its value is returned. If all entries have been recently accessed or the cache is empty, this returns None.

Note

This method is automatically called by insert when the cache is at capacity, but it can also be called manually to proactively free space.

Examples

use sieve_cache::SieveCache;

let mut cache = SieveCache::new(3).unwrap();
cache.insert("key1".to_string(), "value1".to_string());
cache.insert("key2".to_string(), "value2".to_string());
cache.insert("key3".to_string(), "value3".to_string());

// Access key1 and key2 to mark them as visited
cache.get("key1");
cache.get("key2");

// key3 hasn't been accessed, so it should be evicted
let evicted = cache.evict();
assert!(evicted.is_some());
assert!(!cache.contains_key("key3")); // key3 was evicted

Trait Implementations

impl<K: Eq + Hash + Clone, V> Send for SieveCache<K, V>