lockfree 0.2.0

This crate provides concurrent data structures and a solution to the ABA problem as an alternative of hazard pointers
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
119
120
121
122
123
124
125
126
127
128

use super::table::{Node, Table};
use incinerator;
use std::{collections::VecDeque, fmt, sync::atomic::Ordering::*};

/// An iterator over `Map`. As in the `Map`'s `get` method, we cannot return a
/// reference to the elements. Therefore, the iterator has a reader which reads
/// a temporary reference and returns the actual iterator `Item`.
pub struct Iter<'map, K, V, R>
where
    K: 'map,
    V: 'map,
    R: IterReader<K, V>,
{
    tables: VecDeque<&'map Table<K, V>>,
    index: usize,
    cache: Vec<R::Out>,
    reader: R,
}

impl<'map, K, V, R> Iter<'map, K, V, R>
where
    R: IterReader<K, V>,
{
    pub(crate) fn with_table(table: &'map Table<K, V>, reader: R) -> Self {
        Self {
            tables: {
                let mut deque = VecDeque::with_capacity(1);
                deque.push_back(table);
                deque
            },
            index: 0,
            cache: Vec::new(),
            reader,
        }
    }
}

impl<'map, K, V, R> Iterator for Iter<'map, K, V, R>
where
    R: IterReader<K, V>,
{
    type Item = R::Out;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(val) = self.cache.pop() {
            return Some(val);
        }

        let mut table = *self.tables.front()?;
        let mut stop = false;
        loop {
            incinerator::pause(|| match table.nodes().get(self.index) {
                Some(node) => {
                    self.index += 1;
                    match unsafe { node.load(Relaxed).as_ref() } {
                        Some(Node::Leaf(bucket)) => {
                            for (k, v) in unsafe { bucket.collect() } {
                                let elem = self.reader.read(k, v);
                                self.cache.push(elem);
                            }
                        },

                        Some(Node::Branch(ptr)) => {
                            self.tables.push_back(unsafe { &*ptr.as_ptr() })
                        },

                        None => (),
                    }
                },

                None => {
                    self.index = 0;
                    self.tables.pop_front();
                    match self.tables.front() {
                        Some(x) => table = *x,
                        None => stop = true,
                    };
                },
            });

            if stop {
                break None;
            }

            if let Some(val) = self.cache.pop() {
                break Some(val);
            }
        }
    }
}

/// A reader on map's iterator's temporary references.
pub trait IterReader<K, V> {
    /// The actual item of the iterator which is coupled with this reader.
    type Out;

    /// Transforms the temporary references into the iterator item.
    fn read(&mut self, key: &K, val: &V) -> Self::Out;
}

impl<K, V, F, T> IterReader<K, V> for F
where
    F: FnMut(&K, &V) -> T,
{
    type Out = T;

    fn read(&mut self, key: &K, val: &V) -> Self::Out {
        self(key, val)
    }
}

impl<'map, K, V, R> fmt::Debug for Iter<'map, K, V, R>
where
    R: IterReader<K, V>,
    R::Out: fmt::Debug,
{
    fn fmt(&self, fmtr: &mut fmt::Formatter) -> fmt::Result {
        write!(
            fmtr,
            "Iter {} cache: {:?}, tables.len(): {}, index: {} {}",
            '{',
            self.cache,
            self.tables.len(),
            self.index,
            '}'
        )
    }
}