Safe Doubly-Linked List with O(1) remove

linkedlist.rs

#![allow(dead_code)]

use std::cell::RefCell;
use std::rc::{Rc, Weak};

/// LinkedList with O(1) element removal using a handle returned from `push`.
/// Motivation: Learning to build O(1) removal LinkedList in safe rust using
/// interior mutability. Useful in building asymptotically optimal LRU cache.
/// Unfortunately std::collections::LinkedList doesn't allow O(1) removal.
/// Of course this implementation would have to be weighed against more
/// cache-friendly solutions like std BTreeMap and even Vec, but this is all
/// just for educational purposes.
#[derive(Default)]
struct LinkedList<T> {
    head: Option<NodePtr<T>>,
    tail: Option<NodePtr<T>>,
}

struct Node<T> {
    value: T,
    next: Option<NodePtr<T>>,
    //  prevent strong ref cycle
    prev: Option<WeakNodePtr<T>>,
}
type NodePtr<T> = Rc<RefCell<Node<T>>>;
type WeakNodePtr<T> = Weak<RefCell<Node<T>>>;

// Pointer to the created node, wrapped so that the caller cannot borrow into the RefCell
struct Handle<T>(T);

impl<T: Clone> LinkedList<T> {
    pub fn push_back(&mut self, value: T) -> Handle<NodePtr<T>> {
        let node = Rc::new(RefCell::new(Node {
            value,
            next: None,
            prev: self.tail.as_ref().map(Rc::downgrade),
        }));

        if let Some(tail) = self.tail.as_ref() {
            tail.borrow_mut().next = Some(node.clone());
        }
        self.tail = Some(node.clone());

        if self.head.is_none() {
            self.head = Some(node.clone());
        }

        Handle(node)
    }

    //  XXX: possible for node to belong to another LinkedList :(
    //  Options:
    //  1) generate random list id at runtime, tag all returned Handles with
    //      this id, check on entry to this function and panic/error if node is from another list
    //  2) store map of all active pointers, check node.as_ptr() is a part of this map
    pub fn remove(&mut self, Handle(ref node): Handle<NodePtr<T>>) {
        if let Some(head) = self.head.as_ref() {
            if Rc::ptr_eq(head, &node) {
                self.head = node.borrow().next.clone();
            }
        }
        if let Some(tail) = self.tail.as_ref() {
            if Rc::ptr_eq(tail, &node) {
                self.tail = node
                    .borrow()
                    .prev
                    .clone()
                    .map(|weak| weak.upgrade().unwrap());
            }
        }

        let mut node = node.borrow_mut();
        node.next
            .as_ref()
            .map(|next| next.borrow_mut().prev = node.prev.clone());
        node.prev
            .as_ref()
            .map(|prev| prev.upgrade().unwrap().borrow_mut().next = node.next.clone());

        // remove references to prevent leak
        node.next = None;
        node.prev = None;
    }

    pub fn pop_front(&mut self) -> Option<T> {
        if let Some(old_head) = self.head.clone() {
            let ret = old_head.borrow().value.clone();
            self.remove(Handle(old_head));
            Some(ret)
        } else {
            None
        }
    }

    pub fn peek_front(&self) -> Option<T> {
        self.head.as_ref().map(|head| head.borrow().value.clone())
    }
}

#[test]
fn it_works() {
    let mut list = LinkedList::default();

    list.push_back(0);
    let node1 = list.push_back(1);
    list.push_back(2);

    list.remove(node1);

    assert_eq!(list.pop_front(), Some(0));
    assert_eq!(list.pop_front(), Some(2));
    assert_eq!(list.pop_front(), None);
    assert!(list.head.is_none());
    assert!(list.tail.is_none());
}