concache 0.2.1

use cx::epoch::{self, Atomic, Owned};
use std::fmt;
use std::sync::atomic::AtomicBool;
use std::sync::atomic::Ordering;

struct Node<K, V> {
    kv: (K, Atomic<V>),
    active: AtomicBool,
    next: Atomic<Node<K, V>>,
    prev: Atomic<Node<K, V>>,
}

impl<K, V> Node<K, V> {
    fn new(k: K, v: V) -> Self {
        Node {
            kv: (k, Atomic::new(v)),
            active: AtomicBool::new(true),
            next: Atomic::null(),
            prev: Atomic::null(),
        }
    }
}

pub(super) struct LinkedList<K, V> {
    first: Atomic<Node<K, V>>,
}

impl<K, V> Default for LinkedList<K, V> {
    fn default() -> Self {
        LinkedList {
            first: Atomic::null(),
        }
    }
}

impl<K, V> LinkedList<K, V>
where
    K: Eq,
    V: Copy,
{
    pub(super) fn insert(&self, kv: (K, V)) -> bool {
        let guard = epoch::pin();

        let mut node = &self.first;
        loop {
            let l = node.load(Ordering::SeqCst, &guard);
            match l {
                Some(k) => {
                    let mut raw = k.as_raw();
                    let mut cur = unsafe { &*raw };
                    if &cur.kv.0 == &kv.0 && cur.active.load(Ordering::SeqCst) {
                        // if let Some(old) = cur.kv.1.load(Ordering::SeqCst, &guard) {
                        //     unsafe { guard.unlinked(old); }
                        // }
                        let mut ins = Owned::new(kv.1);
                        cur.kv.1.store_and_ref(ins, Ordering::SeqCst, &guard);
                        return false;
                    }
                    node = &k.next;

                    // key does not exist
                    if cur.next.load(Ordering::SeqCst, &guard).is_none() {
                        let mut ins = Owned::new(Node::new(kv.0, kv.1));
                        ins.prev.store_shared(l, Ordering::SeqCst);
                        cur.next.store_and_ref(ins, Ordering::SeqCst, &guard);
                        return true;
                    }
                }
                None => {
                    // first is null
                    let mut ins = Owned::new(Node::new(kv.0, kv.1));
                    self.first.store_and_ref(ins, Ordering::SeqCst, &guard);
                    return true;
                }
            };
        }
    }

    pub(super) fn get(&self, key: &K) -> Option<V> {
        let guard = epoch::pin();

        let mut node = &self.first;
        loop {
            match node.load(Ordering::SeqCst, &guard) {
                Some(k) => {
                    let mut raw = k.as_raw();
                    let mut cur = unsafe { &*raw };
                    if &cur.kv.0 == key && cur.active.load(Ordering::SeqCst) {
                        let value = cur.kv.1.load(Ordering::SeqCst, &guard).unwrap();
                        return Some(**value);
                    }
                    node = &k.next;
                }
                None => {
                    return None;
                }
            };
        }
    }

    pub(super) fn remove(&self, key: &K) -> bool {
        let guard = epoch::pin();

        let mut node = &self.first;
        loop {
            match node.load(Ordering::SeqCst, &guard) {
                Some(k) => {
                    let mut raw = k.as_raw();
                    let mut cur = unsafe { &*raw };
                    if &cur.kv.0 == key && cur.active.load(Ordering::SeqCst) {
                        cur.active.store(false, Ordering::SeqCst);

                        let next = k.next.load(Ordering::SeqCst, &guard);
                        let prev = k.prev.load(Ordering::SeqCst, &guard);

                        node.cas_shared(Some(k), next, Ordering::Release);

                        let mut new_node = match node.load(Ordering::SeqCst, &guard) {
                            Some(k) => k,
                            None => {
                                continue;
                            }
                        };
                        let mut new_node_raw_cur = unsafe { &*new_node.as_raw() };

                        if new_node_raw_cur
                            .prev
                            .cas_shared(Some(k), prev, Ordering::Release)
                        {
                            unsafe { guard.unlinked(k) };
                            return true;
                        }
                    }
                    node = &k.next;
                }
                None => {
                    // the node with key key didn't exist
                    return false;
                }
            };
        }
    }
}

impl<K, V> fmt::Debug for LinkedList<K, V>
where
    K: fmt::Debug,
    V: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        // TODO: use https://doc.rust-lang.org/std/fmt/struct.DebugList.html
        let guard = epoch::pin();

        let mut ret = String::new();
        let mut node = &self.first;
        while let Some(k) = node.load(Ordering::SeqCst, &guard) {
            let mut raw = k.as_raw();
            let mut cur = unsafe { &*raw };
            if cur.active.load(Ordering::SeqCst) {
                let key = &cur.kv.0;
                let value = cur.kv.1.load(Ordering::SeqCst, &guard).unwrap();

                ret.push_str("(");
                ret.push_str(&format!("{:?}", key));
                ret.push_str(", ");
                ret.push_str(&format!("{:?}", value));
                ret.push_str("), ");
            }
            node = &k.next;
        }

        write!(f, "{}", ret)
    }
}