Type Alias Sieve 

pub type Sieve<Key, Value> = Cache<Key, Value, SievePolicy>;

A Sieve cache implementing the algorithm outlined in the paper Sieve is Simpler than Lru.

Sieve uses a “visited” bit per entry and a hand pointer that scans for eviction candidates, giving recently accessed items a “second chance” before eviction.

Algorithm Overview

Sieve maintains:

• A visited bit for each cache entry (initially false)
• A hand pointer that moves through entries looking for eviction candidates
• A doubly-linked list structure for efficient traversal

Key Operations

Access (get/get_mut)

When an entry is accessed:

1. The visited bit is set to true
2. The entry position in eviction order may be updated

Eviction

When space is needed:

1. The hand pointer scans entries starting from its current position
2. For each entry with visited = true: reset to false and continue scanning
3. The first entry with visited = false is evicted
4. The hand pointer advances to the next position

This gives recently accessed entries a “second chance” - they’re skipped once during eviction scanning, but evicted if accessed again without being used.

Time Complexity

• Insert/Get/Remove: O(1) average, O(n) worst case
• Peek/Contains: O(1) average, O(n) worst case
• Pop/Clear: O(1) average, O(n) worst case

Examples

Basic Usage

use std::num::NonZeroUsize;

use evictor::Sieve;

let mut cache = Sieve::new(NonZeroUsize::new(3).unwrap());
cache.insert(1, "one");
cache.insert(2, "two");
cache.insert(3, "three");

// Access entry 1 to set its visited bit
cache.get(&1);

// This will evict entry 2 (unvisited), not entry 1
cache.insert(4, "four");
assert!(cache.contains_key(&1)); // Still present (second chance)
assert!(!cache.contains_key(&2)); // Evicted

Second Chance Behavior

use std::num::NonZeroUsize;

use evictor::Sieve;

let mut cache = Sieve::new(NonZeroUsize::new(2).unwrap());
cache.insert("A", 1);
cache.insert("B", 2);

// Access A to mark it as visited
cache.get(&"A");

// Insert C - will scan and find A visited, reset its bit, continue to B
cache.insert("C", 3);
assert!(cache.contains_key(&"A")); // A got second chance
assert!(!cache.contains_key(&"B")); // B was evicted

// Now A's visited bit is false, so next eviction will remove A
cache.insert("D", 4);
assert!(!cache.contains_key(&"A")); // A evicted (used its second chance)
assert!(cache.contains_key(&"C"));
assert!(cache.contains_key(&"D"));

Comparison with peek() vs get()

use std::num::NonZeroUsize;

use evictor::Sieve;

let mut cache = Sieve::new(NonZeroUsize::new(2).unwrap());
cache.insert(1, "one");
cache.insert(2, "two");

// peek() does NOT set visited bit
cache.peek(&1);
cache.insert(3, "three"); // Evicts 1 (not visited)
assert!(!cache.contains_key(&1));

// get() DOES set visited bit
cache.get(&2);
cache.insert(4, "four"); // Evicts 3 (2 gets second chance)
assert!(cache.contains_key(&2));
assert!(!cache.contains_key(&3));

Iteration Order

use std::num::NonZeroUsize;

use evictor::Sieve;

let mut cache = Sieve::new(NonZeroUsize::new(3).unwrap());
cache.insert("A", 1);
cache.insert("B", 2);
cache.insert("C", 3);

// Iteration follows eviction order (starting from hand position)
let items: Vec<_> = cache.iter().collect();
// Order depends on hand position and visited bits
assert_eq!(items.len(), 3);

// First item should match tail() (next eviction candidate)
assert_eq!(cache.tail().unwrap(), cache.iter().next().unwrap());

Aliased Type

pub struct Sieve<Key, Value> { /* private fields */ }