fwdlist 0.3.0

A simply linked (forward) list
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

use crate::{Link, List};
use std::ptr;

mod access;
mod cmp;
mod core;
mod extra;
mod stdtraits;

impl<T> List<T> {
    fn last_link(&mut self) -> &mut Link<T> {
        let mut head_link = &mut self.head;
        loop {
            match *{ head_link } {
                Some(ref mut node) => {
                    head_link = &mut node.next;
                }
                ref mut nil_link @ None => {
                    return nil_link;
                }
            }
        }
    }

    #[allow(dead_code)]
    //#[inline(never)] // <- if testing with callgrind.
    fn penultimate_link_with_unsafe(&mut self) -> Option<&mut Link<T>> {
        let mut prev_link = ptr::null_mut();
        let mut head_link: *mut _ = &mut self.head;
        unsafe {
            while let Some(ref mut node) = *head_link {
                prev_link = head_link;
                head_link = &mut node.next;
            }
            if !prev_link.is_null() {
                Some(&mut *prev_link)
            } else {
                None
            }
        }
    }

    //#[inline(never)] // <- if testing with callgrind.
    fn penultimate_link(&mut self) -> Option<&mut Link<T>> {
        let mut head_link = &mut self.head;
        while let Some(ref mut node) = *{ head_link } {
            let found_last_node = {
                if let Some(ref next_node) = node.next {
                    next_node.next.is_none()
                } else {
                    false
                }
            };
            if found_last_node {
                return Some(&mut node.next);
            } else {
                head_link = &mut node.next;
            }
        }
        None
    }
}

#[cfg(feature = "bench")]
mod benchs {
    extern crate test;
    use test::{black_box, Bencher};
    use crate::List;

    static BIGLIST_SIZE: usize = 1024 * 1024;

    fn make_biglist() -> List<i64> {
        let mut l = List::new();
        for i in (0..BIGLIST_SIZE).rev() {
            l.push_front(i as i64);
        }
        return l;
    }

    #[test]
    fn biglist() {
        let l = make_biglist();
        assert_eq!(l.len(), BIGLIST_SIZE);
    }

    #[test]
    fn one_penultimate_safe() {
        let mut l = make_biglist();
        let link = l.penultimate_link().unwrap();
        let node = link.as_ref().unwrap();
        assert_eq!(node.value, BIGLIST_SIZE as i64 - 1);
    }

    #[test]
    fn one_penultimate_with_unsafe() {
        let mut l = make_biglist();
        let link = l.penultimate_link_with_unsafe().unwrap();
        let node = link.as_ref().unwrap();
        assert_eq!(node.value, BIGLIST_SIZE as i64 - 1);
    }

    #[bench]
    fn penultimate_safe(b: &mut Bencher) {
        let mut l = make_biglist();
        b.iter(|| {
            black_box(l.penultimate_link());
        });
    }

    #[bench]
    fn penultimate_with_unsafe(b: &mut Bencher) {
        let mut l = make_biglist();
        b.iter(|| {
            black_box(l.penultimate_link_with_unsafe());
        });
    }

}