lru2 0.1.0

use std::ptr;
use std::mem;

#[cfg(test)]
mod test;

pub struct Link<K:PartialEq, P>(*mut Entry<K, P>);

impl<K:PartialEq, P> Copy for Link<K, P> {}

impl<K:PartialEq, P> Clone for Link<K, P> {
    fn clone(&self) -> Self { Link(self.0) }
}

impl<K:PartialEq, P> Link<K, P> {
    fn some(entry: &mut Entry<K, P>) -> Link<K, P> { Link(&mut *entry) }
    fn none() -> Link<K, P> { Link(ptr::null_mut()) }

    fn next_mut<'a>(&mut self) -> Option<&'a mut Entry<K, P>> {
        if self.0.is_null() {
            None
        } else {
            Some(unsafe { mem::transmute(self.0) })
        }
    }
}

pub struct Entry<K:PartialEq, P> {
    key: K,
    pub payload: P,
    next: Link<K, P>
}

pub struct Register<K:PartialEq, P> {
    pub entries: Box<[Entry<K, P>]>,
    head: Link<K, P>,
    max_size: usize,
    pub cur_size: usize
}

impl<'a, K:PartialEq, P> Register<K, P> {
    pub fn new(size: usize) -> Register<K, P> {
        if size < 2 { panic!("Register must have at least two entries"); }

        let mut entries = Vec::with_capacity(size);
        unsafe {
            entries.set_len(size);
        }

        Register{
            entries: entries.into_boxed_slice(),
            max_size: size,
            cur_size: 0,
            head: Link::none()
        }
    }

    #[inline]
    fn get_entry(&mut self, key: &K, set_op: &bool) -> (bool, Option<*mut Entry<K, P>>) {
        let mut prev = self.head.next_mut();
        let mut next = None;
        let mut found;

        if match prev {
            Some(ref mut entry) => {
                next = entry.next.next_mut();
                entry.key == *key
            },
            None => false
        } {
            return (true, prev.map(|entry| entry as *mut Entry<K, P>))
        }

        loop {
            found = match next {
                Some(ref entry) => entry.key == *key,
                None => false
            };
            if found { break; }

            let tmp = match next {
                Some(ref mut entry) => entry.next.next_mut(),
                None => { break; }
            };
            if tmp.is_none() { break; }
            prev = next;
            next = tmp;
        }

        if found || *set_op {
            match next {
                Some(ref mut entry) => {
                    prev.unwrap().next = entry.next;
                    entry.next = self.head;
                    self.head = Link::some(entry);
                },
                None => unreachable!()
            }
        }

        (found, next.map(|entry| entry as *mut Entry<K, P>))


    }

    #[inline]
    pub fn set(&'a mut self, key: K, payload: Option<P>) -> bool {
        if self.cur_size == 0 {
            self.entries[0].key = key;
            self.entries[0].next = Link::none();
            if payload.is_some() { self.entries[0].payload = payload.unwrap(); }
            self.head = Link::some(&mut self.entries[0]);
            self.cur_size = 1;
            false
        } else {
            let set_op = self.cur_size == self.max_size;
            let (found, pentry) = self.get_entry(&key, &set_op);

            if found {
            // Entry already exists
                let entry: &mut Entry<K, P> = unsafe{ &mut *pentry.unwrap() };
                if payload.is_some() { entry.payload = payload.unwrap(); }
                true
            } else {
            // Entry does not exist
                if self.cur_size < self.max_size {
                    let size = self.cur_size;
                    self.entries[size].key = key;
                    if payload.is_some() { self.entries[size].payload = payload.unwrap() }
                    self.entries[size].next = self.head;
                    self.head = Link::some(&mut self.entries[size]);
                    self.cur_size += 1;
                } else {
                    let entry: &mut Entry<K, P> = unsafe{ &mut *pentry.unwrap() };
                    entry.key = key;
                    if payload.is_some() { entry.payload = payload.unwrap(); }
                }
                false
            }
        }
    }

    #[inline]
    pub fn get(&mut self, key: K) -> Option<&P> {
        if self.cur_size == 0 { return None; }

        let (found, pentry) = self.get_entry(&key, &false);
        if found {
            let entry: &Entry<K, P> = unsafe{ &mut *pentry.unwrap() };
            Some(&entry.payload)
        } else {
            None
        }
    }

    #[inline]
    pub fn reset(&mut self) {
        self.cur_size = 0;
        self.head = Link::none();
    }
}

#[test]
#[should_panic]
fn initialize_with_0() {
    let _ = Register::<u8, u8>::new(0);
}

#[test]
#[should_panic]
fn initialize_with_1() {
    let _ = Register::<u8, u8>::new(1);
}

#[test]
fn initialize_2() {
    let register = Register::<u8, u8>::new(2);
    let entries = register.entries.into_vec();
    assert!(entries.len() == 2);
}

#[test]
fn initialize_100() {
    let register = Register::<u8, u8>::new(100);
    let entries = register.entries.into_vec();
    assert!(entries.len() == 100);
}