LRU impl by Rust.

LRU.rs

mod test;

use std::{
    cell::RefCell,
    collections::{hash_map::Entry, HashMap},
    fmt::{self, Debug},
    rc::Rc,
};

#[derive(Debug)]
pub struct Node<T: Debug> {
    key: String,
    val: T,
    pre: Option<Rc<RefCell<Node<T>>>>,
    next: Option<Rc<RefCell<Node<T>>>>,
}

impl<T: Debug> Node<T> {
    fn new(key: String, val: T) -> Self {
        Node {
            key,
            val,
            pre: None,
            next: None,
        }
    }
}

#[derive(Debug)]
pub struct DuplexLink<T: Debug + Clone> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
}

impl<T: Debug + Clone> DuplexLink<T> {
    fn new() -> Self {
        DuplexLink {
            head: None,
            tail: None,
        }
    }

    fn create_node(&mut self, key: String, val: T) -> (Rc<RefCell<Node<T>>>, bool) {
        let new_node = Rc::new(RefCell::new(Node::new(key, val)));

        if self.head.is_none() || self.tail.is_none() {
            self.head = Some(Rc::clone(&new_node));
            self.tail = Some(Rc::clone(&new_node));

            return (new_node, true);
        }

        (new_node, false)
    }

    #[allow(dead_code)]
    fn push(&mut self, key: String, val: T) -> Rc<RefCell<Node<T>>> {
        let (node, init) = self.create_node(key, val);

        if !init {
            node.borrow_mut().pre = Some(Rc::clone(self.tail.as_ref().unwrap()));
            self.tail.as_ref().unwrap().borrow_mut().next = Some(Rc::clone(&node));
            self.tail = Some(Rc::clone(&node));
        }

        node
    }

    /// Add an item to the head
    fn unshift(&mut self, key: String, val: T) -> Rc<RefCell<Node<T>>> {
        let (node, init) = self.create_node(key, val);

        if !init {
            node.borrow_mut().next = Some(Rc::clone(self.head.as_ref().unwrap()));
            self.head.as_ref().unwrap().borrow_mut().pre = Some(Rc::clone(&node));
            self.head = Some(Rc::clone(&node));
        }

        node
    }

    #[allow(dead_code)]
    fn move_to_tail(&mut self, node: &Rc<RefCell<Node<T>>>) {
        if self.tail.is_none() || node.borrow().next.is_none() {
            return;
        }

        if let Some(pre_node) = node.borrow().pre.as_ref() {
            node.borrow().next.as_ref().unwrap().borrow_mut().pre = Some(Rc::clone(pre_node));
            pre_node.borrow_mut().next = Some(Rc::clone(node.borrow().next.as_ref().unwrap()));
        } else {
            node.borrow().next.as_ref().unwrap().borrow_mut().pre = None;
            self.head = Some(Rc::clone(node.borrow().next.as_ref().unwrap()));
        }

        node.borrow_mut().next = None;
        node.borrow_mut().pre = Some(Rc::clone(self.tail.as_ref().unwrap()));
        self.tail.as_ref().unwrap().borrow_mut().next = Some(Rc::clone(node));
        self.tail = Some(Rc::clone(&node));
    }

    fn move_to_head(&mut self, node: &Rc<RefCell<Node<T>>>) {
        if self.head.is_none() || node.borrow().pre.is_none() {
            return;
        }

        if let Some(next_node) = node.borrow().next.as_ref() {
            node.borrow().pre.as_ref().unwrap().borrow_mut().next = Some(Rc::clone(next_node));
            next_node.borrow_mut().pre = Some(Rc::clone(node.borrow().pre.as_ref().unwrap()));
        } else {
            node.borrow().pre.as_ref().unwrap().borrow_mut().next = None;
            self.tail = Some(Rc::clone(node.borrow().pre.as_ref().unwrap()));
        }

        node.borrow_mut().pre = None;
        node.borrow_mut().next = Some(Rc::clone(self.head.as_ref().unwrap()));
        self.head.as_ref().unwrap().borrow_mut().pre = Some(Rc::clone(node));
        self.head = Some(Rc::clone(&node));
    }

    fn pop(&mut self) -> Option<Rc<RefCell<Node<T>>>> {
        if let Some(tail_node) = self.tail.clone() {
            self.tail = if let Some(tail_pre_node) = tail_node.borrow().pre.as_ref() {
                tail_pre_node.borrow_mut().next = None;
                Some(Rc::clone(tail_pre_node))
            } else {
                None
            };

            return Some(tail_node);
        }

        None
    }

    pub fn to_vec(&self) -> Vec<(String, T)> {
        let mut current_node = self.head.clone();
        let mut res = Vec::new();

        while let Some(node) = current_node {
            res.push((node.borrow().key.clone(), node.borrow().val.clone()));
            current_node = node.borrow().next.clone();
        }

        res
    }
}

impl<T: Debug + fmt::Display + Clone> fmt::Display for DuplexLink<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}",
            if self.head.is_none() || self.tail.is_none() {
                "[empty~]".into()
            } else {
                self.to_vec()
                    .iter()
                    .map(|n| format!("[{}, {}]", n.0, n.1))
                    .collect::<Vec<String>>()
                    .join(" <-> ")
            }
        )
    }
}

pub struct LRU<T: Debug + Clone> {
    pub cap: usize,
    pub size: usize,
    pub link: DuplexLink<T>,
    pub map: HashMap<String, Rc<RefCell<Node<T>>>>,
}

impl<T: Debug + fmt::Display + Clone> LRU<T> {
    pub fn new(cap: usize) -> Self {
        LRU {
            cap,
            size: 0,
            link: DuplexLink::<T>::new(),
            map: HashMap::<String, Rc<RefCell<Node<T>>>>::new(),
        }
    }

    pub fn put(&mut self, key: String, item: T) {
        if self.size == self.cap {
            if let Some(removed_node) = self.link.pop() {
                self.map.remove(&removed_node.borrow().key);
                self.size -= 1;
            }
        }

        match self.map.entry(key.clone()) {
            Entry::Occupied(o) => {
                let node = o.get();

                // Update to newset value
                node.borrow_mut().val = item.clone();
                self.link.move_to_head(node)
            }
            Entry::Vacant(v) => {
                let node = self.link.unshift(key, item);

                v.insert(node);
                self.size += 1;
            }
        }
    }

    pub fn get(&mut self, key: String) -> Option<T> {
        match self.map.entry(key) {
            Entry::Occupied(o) => {
                self.link.move_to_head(o.get());

                return Some(o.get().borrow().val.clone());
            }
            _ => None,
        }
    }

    #[allow(dead_code)]
    pub fn size(&self) -> usize {
        return self.map.len();
    }
}

impl<T: Debug + fmt::Display + Clone> fmt::Display for LRU<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.link)
    }
}

test.rs

use super::*;

#[derive(Debug, Clone)]
struct TestDater {
    key: String,
    item: i32,
}

impl fmt::Display for TestDater {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{{{}: {}}}", self.key, self.item)
    }
}

#[test]
fn lru_create() {
    let lru = LRU::<TestDater>::new(3);

    assert_eq!(lru.to_string(), "[empty~]");
    assert_eq!(lru.cap, 3);
    assert_eq!(lru.size(), 0);
    assert_eq!(lru.map.len(), 0);
}

#[test]
fn lru_put() {
    let mut lru = LRU::<TestDater>::new(3);

    lru.put(
        "a".into(),
        TestDater {
            key: "page-1".into(),
            item: 1,
        },
    );

    assert_eq!(lru.to_string(), "[a, {page-1: 1}]");
    assert_eq!(lru.size(), 1);

    lru.put(
        "b".into(),
        TestDater {
            key: "page-2".into(),
            item: 10,
        },
    );

    assert_eq!(lru.to_string(), "[b, {page-2: 10}] <-> [a, {page-1: 1}]");
    assert_eq!(lru.size(), 2);

    lru.put(
        "c".into(),
        TestDater {
            key: "page-3".into(),
            item: 100,
        },
    );

    assert_eq!(lru.size(), 3);

    lru.put(
        "d".into(),
        TestDater {
            key: "page-4".into(),
            item: 101,
        },
    );

    assert_eq!(
        lru.to_string(),
        "[d, {page-4: 101}] <-> [c, {page-3: 100}] <-> [b, {page-2: 10}]"
    );
    assert_eq!(lru.size(), 3);
}

#[test]
fn lru_get() {
    let mut lru = LRU::<TestDater>::new(3);

    lru.put(
        "a".into(),
        TestDater {
            key: "page-1".into(),
            item: 1,
        },
    );
    lru.put(
        "b".into(),
        TestDater {
            key: "page-2".into(),
            item: 10,
        },
    );
    lru.put(
        "c".into(),
        TestDater {
            key: "page-3".into(),
            item: 100,
        },
    );
    lru.put(
        "d".into(),
        TestDater {
            key: "page-4".into(),
            item: 101,
        },
    );

    // Get a non-existent key
    assert!(
        lru.get("a".into()).is_none(),
        "Get a non-existent key should return None"
    );
    assert_eq!(
        lru.to_string(),
        "[d, {page-4: 101}] <-> [c, {page-3: 100}] <-> [b, {page-2: 10}]"
    );
    assert_eq!(lru.size(), 3);

    // Get a existent key
    assert!(lru.get("b".into()).is_some());
    assert_eq!(
        lru.to_string(),
        "[b, {page-2: 10}] <-> [d, {page-4: 101}] <-> [c, {page-3: 100}]"
    );
    assert_eq!(lru.size(), 3);
}

Usage:

#[derive(Debug, Clone)]
#[allow(dead_code)]
struct TestDater {
    key: String,
    item: i32,
}

impl fmt::Display for TestDater {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{{{}: {}}}", self.key, self.item)
    }
}

fn main() {
    let mut d = LRU::<TestDater>::new(3);

    d.put(
        "a".into(),
        TestDater {
            key: "page-1".into(),
            item: 1,
        },
    );
    d.put(
        "b".into(),
        TestDater {
            key: "page-2".into(),
            item: 10,
        },
    );
    d.put(
        "c".into(),
        TestDater {
            key: "page-3".into(),
            item: 10,
        },
    );
    d.put(
        "d".into(),
        TestDater {
            key: "page-4".into(),
            item: 10,
        },
    );

    println!("{}", d.link);
    println!("{}", d.get("b".into()).unwrap());
    println!("{}", d.link);

    // [d, {page-4: 10}] <-> [c, {page-3: 10}] <-> [b, {page-2: 10}]
    // {page-2: 10}
    // [b, {page-2: 10}] <-> [d, {page-4: 10}] <-> [c, {page-3: 10}]
}