monolake_services/common/cancel/
linked_list.rs

1/// Vec based linked list.
2pub struct LinkedList<T> {
3    head: usize,
4    tail: usize,
5    vacancy_head: usize,
6    data: Vec<Node<T>>,
7}
8
9pub struct Node<T> {
10    prev: usize,
11    next: usize,
12    data: Option<T>,
13}
14
15pub const NULL: usize = usize::MAX;
16
17impl<T> Default for LinkedList<T> {
18    fn default() -> Self {
19        Self::new()
20    }
21}
22
23impl<T> LinkedList<T> {
24    pub const fn new() -> Self {
25        Self {
26            head: NULL,
27            tail: NULL,
28            vacancy_head: NULL,
29            data: Vec::new(),
30        }
31    }
32
33    pub fn get(&self, idx: usize) -> Option<&T> {
34        self.data.get(idx).and_then(|node| node.data.as_ref())
35    }
36
37    pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
38        self.data.get_mut(idx).and_then(|node| node.data.as_mut())
39    }
40
41    pub fn push_back(&mut self, val: T) -> usize {
42        let idx = if self.vacancy_head != NULL {
43            let idx = self.vacancy_head;
44            let node = &mut self.data[idx];
45            self.vacancy_head = node.next;
46            node.next = NULL;
47            node.data = Some(val);
48            idx
49        } else {
50            let idx = self.data.len();
51            self.data.push(Node {
52                prev: NULL,
53                next: NULL,
54                data: Some(val),
55            });
56            idx
57        };
58
59        if self.tail == NULL {
60            self.head = idx;
61            self.tail = idx;
62        } else {
63            let tail = &mut self.data[self.tail];
64            tail.next = idx;
65            self.data[idx].prev = self.tail;
66            self.tail = idx;
67        }
68
69        idx
70    }
71
72    pub fn remove(&mut self, idx: usize) -> Option<T> {
73        if idx >= self.data.len() {
74            return None;
75        }
76
77        let node = &mut self.data[idx];
78        let val = node.data.take()?;
79        let prev = node.prev;
80        let next = node.next;
81
82        if prev == NULL {
83            self.head = next;
84        } else {
85            self.data[prev].next = next;
86        }
87
88        if next == NULL {
89            self.tail = prev;
90        } else {
91            self.data[next].prev = prev;
92        }
93
94        self.data[idx].next = self.vacancy_head;
95        self.vacancy_head = idx;
96        Some(val)
97    }
98}
99
100impl<T> Drop for LinkedList<T> {
101    // Manually drop the data to make it more efficient.
102    fn drop(&mut self) {
103        let mut head = self.head;
104        while head != NULL {
105            let node = &mut self.data[head];
106            node.data.take();
107            head = node.next;
108        }
109        unsafe { self.data.set_len(0) };
110    }
111}
112
113impl<T> IntoIterator for LinkedList<T> {
114    type Item = T;
115    type IntoIter = LinkedListIter<T>;
116
117    fn into_iter(mut self) -> Self::IntoIter {
118        let head = std::mem::replace(&mut self.head, NULL);
119        let data = std::mem::take(&mut self.data);
120        LinkedListIter { head, data }
121    }
122}
123
124pub struct LinkedListIter<T> {
125    head: usize,
126    data: Vec<Node<T>>,
127}
128
129impl<T> Iterator for LinkedListIter<T> {
130    type Item = T;
131    fn next(&mut self) -> Option<Self::Item> {
132        if self.head == NULL {
133            return None;
134        }
135
136        let node = &mut self.data[self.head];
137        let val = node.data.take();
138        self.head = node.next;
139        val
140    }
141}
142
143impl<T> Drop for LinkedListIter<T> {
144    // Manually drop the data to make it more efficient.
145    fn drop(&mut self) {
146        let mut head = self.head;
147        while head != NULL {
148            let node = &mut self.data[head];
149            node.data.take();
150            head = node.next;
151        }
152        unsafe { self.data.set_len(0) };
153    }
154}
155
156#[cfg(test)]
157mod tests {
158    use super::*;
159    #[test]
160    fn demo() {
161        let mut linked = LinkedList::new();
162        assert_eq!(0, linked.push_back(1));
163        assert_eq!(1, linked.push_back(2));
164        assert_eq!(2, linked.push_back(3));
165        assert_eq!(linked.remove(1).unwrap(), 2);
166        assert!(linked.remove(1).is_none());
167        assert_eq!(linked.push_back(2333), 1);
168
169        let iter = linked.into_iter();
170        assert_eq!(iter.collect::<Vec<_>>(), vec![1, 3, 2333]);
171    }
172}
monolake_services/common/cancel/linked_list.rs

monolake_services/common/cancel/
linked_list.rs
