Module fixed_history 

Fixed-size access history ring buffer.

Stores the last K timestamps in a ring buffer, providing O(1) record and O(1) access to the k-th most recent entry. Essential for LRU-K policies where eviction decisions depend on the K-th most recent access time.

Architecture

┌─────────────────────────────────────────────────────────────────────────────┐
│                      FixedHistory<K=4> Layout                               │
│                                                                             │
│   Ring Buffer                                                               │
│   ────────────                                                              │
│                                                                             │
│   data: [u64; K]              cursor: next write position                   │
│   len: valid entries          (wraps around when full)                      │
│                                                                             │
│   After recording: 10, 20, 30, 40, 50                                       │
│                                                                             │
│   Index:     0     1     2     3                                            │
│            ┌─────┬─────┬─────┬─────┐                                        │
│   data:    │ 50  │ 20  │ 30  │ 40  │                                        │
│            └─────┴─────┴─────┴─────┘                                        │
│              ▲                                                              │
│              │                                                              │
│           cursor = 1 (next write goes here)                                 │
│                                                                             │
│   Access Pattern                                                            │
│   ──────────────                                                            │
│                                                                             │
│   kth_most_recent(k) = data[(cursor + K - k) % K]                           │
│                                                                             │
│   k=1 (most recent):  data[(1 + 4 - 1) % 4] = data[0] = 50                  │
│   k=2:                data[(1 + 4 - 2) % 4] = data[3] = 40                  │
│   k=3:                data[(1 + 4 - 3) % 4] = data[2] = 30                  │
│   k=4 (oldest):       data[(1 + 4 - 4) % 4] = data[1] = 20                  │
│                                                                             │
│   Record Flow                                                               │
│   ───────────                                                               │
│                                                                             │
│   record(60):                                                               │
│     1. data[cursor] = 60         → data[1] = 60                             │
│     2. cursor = (cursor + 1) % K → cursor = 2                               │
│     3. len stays at K (already full)                                        │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

Key Components

• FixedHistory: Fixed-size ring buffer for timestamp history

Operations

Operation	Description	Complexity
record	Add timestamp (overwrites oldest)	O(1)
most_recent	Get most recent timestamp	O(1)
kth_most_recent	Get k-th most recent timestamp	O(1)
to_vec_mru	Get all in MRU order	O(K)

Use Cases

• LRU-K policy: Track last K access times per entry for eviction decisions
• Access frequency: Count accesses within a time window
• Temporal patterns: Detect periodic access patterns

Example Usage

use cachekit::ds::FixedHistory;

// Track last 3 access times
let mut history = FixedHistory::<3>::new();

// Record access timestamps
history.record(100);
history.record(200);
history.record(300);

// Most recent access
assert_eq!(history.most_recent(), Some(300));

// LRU-K: Get K-th most recent for eviction comparison
assert_eq!(history.kth_most_recent(3), Some(100));  // Oldest of K

// Overwrites oldest when full
history.record(400);
assert_eq!(history.to_vec_mru(), vec![400, 300, 200]);  // 100 is gone

Use Case: LRU-2 Eviction

use cachekit::ds::FixedHistory;

// LRU-2: Evict based on 2nd most recent access time
struct CacheEntry {
    value: String,
    history: FixedHistory<2>,
}

impl CacheEntry {
    fn new(value: String, timestamp: u64) -> Self {
        let mut entry = CacheEntry {
            value,
            history: FixedHistory::new(),
        };
        entry.history.record(timestamp);
        entry
    }

    fn access(&mut self, timestamp: u64) {
        self.history.record(timestamp);
    }

    // LRU-2 uses the 2nd most recent access for comparison
    fn eviction_priority(&self) -> u64 {
        // If only 1 access, use that; otherwise use 2nd most recent
        self.history.kth_most_recent(2)
            .or(self.history.most_recent())
            .unwrap_or(0)
    }
}

let mut entry = CacheEntry::new("data".into(), 100);
assert_eq!(entry.eviction_priority(), 100);  // Only 1 access

entry.access(200);
assert_eq!(entry.eviction_priority(), 100);  // 2nd most recent = 100

entry.access(300);
assert_eq!(entry.eviction_priority(), 200);  // 2nd most recent = 200

Thread Safety

FixedHistory is not thread-safe. It is typically embedded within cache entries and protected by the cache’s synchronization.

Implementation Notes

• Uses a fixed-size array (no heap allocation)
• Const generic K determines history depth at compile time
• Zero-size history (K=0) is a no-op
• debug_validate_invariants() available in debug/test builds

Structs

FixedHistory

Fixed-size ring buffer of the last K timestamps.