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 cached values.

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(), "value".to_string());
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(), "value".to_string());
assert!(!cache.is_empty());

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

pub fn contains_key<Q>(&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 the end of the vector, 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

pub fn clear(&mut self)

Removes all entries from the cache.

This operation clears all stored values and resets the cache to an empty state, while maintaining the original capacity.

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());

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

cache.clear();
assert_eq!(cache.len(), 0);
assert!(cache.is_empty());

pub fn keys(&self) -> impl Iterator<Item = &K>

Returns an iterator over all keys in the cache.

The order of keys is not specified and should not be relied upon.

Examples

use sieve_cache::SieveCache;
use std::collections::HashSet;

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

let keys: HashSet<_> = cache.keys().collect();
assert_eq!(keys.len(), 2);
assert!(keys.contains(&"key1".to_string()));
assert!(keys.contains(&"key2".to_string()));

pub fn values(&self) -> impl Iterator<Item = &V>

Returns an iterator over all values in the cache.

The order of values is not specified and should not be relied upon.

Examples

use sieve_cache::SieveCache;
use std::collections::HashSet;

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

let values: HashSet<_> = cache.values().collect();
assert_eq!(values.len(), 2);
assert!(values.contains(&"value1".to_string()));
assert!(values.contains(&"value2".to_string()));

pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V>

Returns an iterator over all mutable values in the cache.

The order of values is not specified and should not be relied upon. Note that iterating through this will mark all entries as visited.

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());

// Update all values by appending text
for value in cache.values_mut() {
    *value = format!("{}_updated", value);
}

assert_eq!(cache.get("key1"), Some(&"value1_updated".to_string()));
assert_eq!(cache.get("key2"), Some(&"value2_updated".to_string()));

pub fn iter(&self) -> impl Iterator<Item = (&K, &V)>

Returns an iterator over all key-value pairs in the cache.

The order of pairs is not specified and should not be relied upon.

Examples

use sieve_cache::SieveCache;
use std::collections::HashMap;

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

let entries: HashMap<_, _> = cache.iter().collect();
assert_eq!(entries.len(), 2);
assert_eq!(entries.get(&"key1".to_string()), Some(&&"value1".to_string()));
assert_eq!(entries.get(&"key2".to_string()), Some(&&"value2".to_string()));

pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)>

Returns an iterator over all key-value pairs in the cache, with mutable references to values.

The order of pairs is not specified and should not be relied upon. Note that iterating through this will mark all entries as visited.

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());

// Update all values associated with keys containing '1'
for (key, value) in cache.iter_mut() {
    if key.contains('1') {
        *value = format!("{}_special", value);
    }
}

assert_eq!(cache.get("key1"), Some(&"value1_special".to_string()));
assert_eq!(cache.get("key2"), Some(&"value2".to_string()));

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&K, &V) -> bool,

Retains only the elements specified by the predicate.

Removes all entries for which the provided function returns false. The elements are visited in arbitrary, unspecified order.

Examples

use sieve_cache::SieveCache;

let mut cache = SieveCache::new(100).unwrap();
cache.insert("key1".to_string(), 100);
cache.insert("key2".to_string(), 200);
cache.insert("key3".to_string(), 300);

// Keep only entries with values greater than 150
cache.retain(|_, value| *value > 150);

assert_eq!(cache.len(), 2);
assert!(!cache.contains_key("key1"));
assert!(cache.contains_key("key2"));
assert!(cache.contains_key("key3"));

pub fn recommended_capacity( &self, min_factor: f64, max_factor: f64, low_threshold: f64, high_threshold: f64, ) -> usize

Returns a recommended cache capacity based on current utilization.

This method analyzes the current cache utilization and recommends a new capacity based on:

• The fill ratio (how much of the capacity is actually being used)
• The number of entries with the ‘visited’ flag set
• A target utilization range

The recommendation aims to keep the cache size optimal:

• If the cache is significantly underfilled (fill ratio < 10%), it suggests decreasing capacity regardless of other factors to avoid wasting memory
• If many entries are frequently accessed (high utilization), it suggests increasing capacity
• If few entries are accessed frequently (low utilization), it suggests decreasing capacity
• Within a normal utilization range, it keeps the capacity stable

Arguments

• min_factor - Minimum scaling factor (e.g., 0.5 means never recommend less than 50% of current capacity)
• max_factor - Maximum scaling factor (e.g., 2.0 means never recommend more than 200% of current capacity)
• low_threshold - Utilization threshold below which capacity is reduced (e.g., 0.3 means 30% utilization)
• high_threshold - Utilization threshold above which capacity is increased (e.g., 0.7 means 70% utilization)

Examples

// Get a recommended capacity with default parameters
let recommended = cache.recommended_capacity(0.5, 2.0, 0.3, 0.7);
println!("Recommended capacity: {}", recommended);

Default Recommendation Parameters

If you’re unsure what parameters to use, these values provide a reasonable starting point:

• min_factor: 0.5 (never recommend less than half current capacity)
• max_factor: 2.0 (never recommend more than twice current capacity)
• low_threshold: 0.3 (reduce capacity if utilization below 30%)
• high_threshold: 0.7 (increase capacity if utilization above 70%)

Trait Implementations

impl<K, V> From<SieveCache<K, V>> for SyncSieveCache<K, V>

where K: Eq + Hash + Clone + Send + Sync, V: Send + Sync,

fn from(cache: SieveCache<K, V>) -> Self

Creates a new thread-safe cache from an existing SieveCache.

This allows for easily converting a single-threaded cache to a thread-safe version.

Examples

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

// Convert to thread-safe version
let thread_safe = SyncSieveCache::from(single_threaded);
assert_eq!(thread_safe.get(&"key".to_string()), Some("value".to_string()));