27. Terminal project: an LRU cache, and why linked lists are hard in Rust

Go §26 builds an LRU cache from a map plus container/list, a doubly linked list. In Rust, a doubly linked list with plain references does not compile: every node would be pointed to by two others (prev and next), which gives it two owners and mutable aliasing. The three real options are:

1. Rc<RefCell<Node>> plus Weak back-pointers. It works, but it is verbose, has runtime overhead, and can panic.
2. Raw pointers with unsafe, which is what std::collections::LinkedList does internally.
3. An arena: store nodes in a Vec and link them by index. This is safe, fast, and cache-friendly. The lru crate and many ECS game engines use this approach.

Option 3 is idiomatic. Indices are "pointers" the borrow checker does not track. You give up some static checking (a stale index can point to the wrong node) but never memory safety (a bad index panics, it never reads freed memory).

// src/bin/lru.rs
use std::collections::HashMap;
use std::hash::Hash;

const NIL: usize = usize::MAX;

struct Node<K, V> { key: K, val: V, prev: usize, next: usize }

pub struct Lru<K, V> {
    map: HashMap<K, usize>,   // key -> index into `nodes`
    nodes: Vec<Node<K, V>>,   // the arena; slots are reused when entries are evicted
    head: usize,              // most recently used
    tail: usize,              // least recently used
    cap: usize,
}

impl<K: Hash + Eq + Clone, V> Lru<K, V> {
    pub fn new(cap: usize) -> Self {
        assert!(cap > 0, "capacity must be positive");
        Self { map: HashMap::with_capacity(cap), nodes: Vec::with_capacity(cap), head: NIL, tail: NIL, cap }
    }

    fn unlink(&mut self, i: usize) {
        let (p, n) = (self.nodes[i].prev, self.nodes[i].next);
        if p != NIL { self.nodes[p].next = n } else { self.head = n }
        if n != NIL { self.nodes[n].prev = p } else { self.tail = p }
    }

    fn push_front(&mut self, i: usize) {
        self.nodes[i].prev = NIL;
        self.nodes[i].next = self.head;
        if self.head != NIL { self.nodes[self.head].prev = i }
        self.head = i;
        if self.tail == NIL { self.tail = i }
    }

    pub fn get(&mut self, key: &K) -> Option<&V> {
        let i = *self.map.get(key)?;
        self.unlink(i);
        self.push_front(i);
        Some(&self.nodes[i].val)
    }

    /// Inserts or updates; returns the evicted (key, value), if any.
    pub fn put(&mut self, key: K, val: V) -> Option<(K, V)> {
        if let Some(&i) = self.map.get(&key) {
            self.nodes[i].val = val;
            self.unlink(i);
            self.push_front(i);
            return None;
        }
        if self.nodes.len() < self.cap {
            let i = self.nodes.len();
            self.nodes.push(Node { key: key.clone(), val, prev: NIL, next: NIL });
            self.map.insert(key, i);
            self.push_front(i);
            return None;
        }
        // Full: reuse the tail slot for the new entry.
        let i = self.tail;
        self.unlink(i);
        let old_key = std::mem::replace(&mut self.nodes[i].key, key.clone());
        let old_val = std::mem::replace(&mut self.nodes[i].val, val);
        self.map.remove(&old_key);
        self.map.insert(key, i);
        self.push_front(i);
        Some((old_key, old_val))
    }

    pub fn len(&self) -> usize { self.map.len() }

    /// Keys from most to least recently used.
    pub fn keys(&self) -> Vec<&K> {
        let mut out = Vec::with_capacity(self.len());
        let mut i = self.head;
        while i != NIL { out.push(&self.nodes[i].key); i = self.nodes[i].next; }
        out
    }
}

fn main() {
    let mut c = Lru::new(2);
    c.put("a", 1);
    c.put("b", 2);
    c.get(&"a");                               // a is now most recent
    let evicted = c.put("c", 3);               // evicts b
    println!("evicted={evicted:?} keys={:?}", c.keys()); // evicted=Some(("b", 2)) keys=["c", "a"]
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn evicts_least_recent() {
        let mut c = Lru::new(3);
        for (k, v) in [(1, "one"), (2, "two"), (3, "three")] { c.put(k, v); }
        assert_eq!(c.get(&1), Some(&"one"));
        assert_eq!(c.put(4, "four"), Some((2, "two")));
        assert_eq!(c.keys(), vec![&4, &1, &3]);
        assert_eq!(c.get(&2), None);
        assert_eq!(c.put(1, "uno"), None);        // update does not evict
        assert_eq!(c.len(), 3);
    }

    #[test]
    fn capacity_one() {
        let mut c = Lru::new(1);
        c.put('x', 0);
        assert_eq!(c.put('y', 1), Some(('x', 0)));
        assert_eq!(c.keys(), vec![&'y']);
    }
}

get takes &mut self, because reading an LRU cache changes its recency order. To share the cache between threads, wrap it in Mutex<Lru<K, V>> (Ch 29). A read-write lock gives no benefit here, because every read is also a write. A Go version has the same constraint, but nothing stops a Go caller from forgetting the lock. In Rust, sharing an Lru across threads without the Mutex does not compile.

Stretch goals: add a TTL per entry. Shard the cache into N Mutex<Lru> by key hash to reduce lock contention. Benchmark it against the lru crate with criterion (Ch 36).