rust_examples/
list_seventh.rs

1struct List<T> {
2    head: Link<T>,
3    tail: *mut Node<T>,
4}
5type Link<T> = *mut Node<T>;
6struct Node<T> {
7    element: T,
8    next: Link<T>,
9}
10struct IntoIter<T>(List<T>);
11struct Iter<'a, T> {
12    next: Option<&'a Node<T>>,
13}
14struct IterMut<'a, T> {
15    next: Option<&'a mut Node<T>>,
16}
17impl<T> List<T> {
18    pub fn new() -> Self {
19        List {
20            head: std::ptr::null_mut(),
21            tail: std::ptr::null_mut(),
22        }
23    }
24    pub fn push(&mut self, element: T) {
25        unsafe {
26            let new_tail = Box::new(Node {
27                element,
28                next: std::ptr::null_mut(),
29            });
30            let new_tail = Box::into_raw(new_tail);
31            if self.tail.is_null() {
32                self.head = new_tail;
33            } else {
34                (*self.tail).next = new_tail;
35            }
36            self.tail = new_tail;
37        }
38    }
39    pub fn pop(&mut self) -> Option<T> {
40        unsafe {
41            if self.head.is_null() {
42                None
43            } else {
44                let head = Box::from_raw(self.head);
45                self.head = head.next;
46                if self.head.is_null() {
47                    self.tail = std::ptr::null_mut();
48                }
49                Some(head.element)
50            }
51        }
52    }
53    pub fn into_iter(self) -> IntoIter<T> {
54        IntoIter(self)
55    }
56    pub fn iter(&mut self) -> Iter<T> {
57        unsafe {
58            Iter {
59                next: self.head.as_ref(),
60            }
61        }
62    }
63    pub fn iter_mut(&mut self) -> IterMut<T> {
64        unsafe {
65            IterMut {
66                next: self.head.as_mut(),
67            }
68        }
69    }
70    pub fn peek(&self) -> Option<&T> {
71        unsafe { self.head.as_ref().map(|node| &node.element) }
72    }
73    pub fn peek_mut(&mut self) -> Option<&mut T> {
74        unsafe { self.head.as_mut().map(|node| &mut node.element) }
75    }
76}
77impl<T> Drop for List<T> {
78    fn drop(&mut self) {
79        while self.pop().is_some() {}
80    }
81}
82impl<T> Iterator for IntoIter<T> {
83    type Item = T;
84
85    fn next(&mut self) -> Option<Self::Item> {
86        self.0.pop()
87    }
88}
89impl<'a, T> Iterator for Iter<'a, T> {
90    type Item = &'a T;
91
92    fn next(&mut self) -> Option<Self::Item> {
93        self.next.map(|node| {
94            self.next = unsafe { node.next.as_ref() };
95            &node.element
96        })
97    }
98}
99impl<'a, T> Iterator for IterMut<'a, T> {
100    type Item = &'a mut T;
101
102    fn next(&mut self) -> Option<Self::Item> {
103        self.next.take().map(|node| {
104            self.next = unsafe { node.next.as_mut() };
105            &mut node.element
106        })
107    }
108}
109#[cfg(test)]
110mod test {
111    use super::List;
112    #[test]
113    fn basics() {
114        let mut list = List::new();
115
116        // Check empty list behaves right
117        assert_eq!(list.pop(), None);
118
119        // Populate list
120        list.push(1);
121        list.push(2);
122        list.push(3);
123
124        // Check normal removal
125        assert_eq!(list.pop(), Some(1));
126        assert_eq!(list.pop(), Some(2));
127
128        // Push some more just to make sure nothing's corrupted
129        list.push(4);
130        list.push(5);
131
132        // Check normal removal
133        assert_eq!(list.pop(), Some(3));
134        assert_eq!(list.pop(), Some(4));
135
136        // Check exhaustion
137        assert_eq!(list.pop(), Some(5));
138        assert_eq!(list.pop(), None);
139
140        // Check the exhaustion case fixed the pointer right
141        list.push(6);
142        list.push(7);
143
144        // Check normal removal
145        assert_eq!(list.pop(), Some(6));
146        assert_eq!(list.pop(), Some(7));
147        assert_eq!(list.pop(), None);
148    }
149    #[test]
150    fn into_iter() {
151        let mut list = List::new();
152        list.push(1);
153        list.push(2);
154        list.push(3);
155
156        let mut iter = list.into_iter();
157        assert_eq!(iter.next(), Some(1));
158        assert_eq!(iter.next(), Some(2));
159        assert_eq!(iter.next(), Some(3));
160        assert_eq!(iter.next(), None);
161    }
162
163    #[test]
164    fn iter() {
165        let mut list = List::new();
166        list.push(1);
167        list.push(2);
168        list.push(3);
169
170        let mut iter = list.iter();
171        assert_eq!(iter.next(), Some(&1));
172        assert_eq!(iter.next(), Some(&2));
173        assert_eq!(iter.next(), Some(&3));
174        assert_eq!(iter.next(), None);
175    }
176
177    #[test]
178    fn iter_mut() {
179        let mut list = List::new();
180        list.push(1);
181        list.push(2);
182        list.push(3);
183
184        let mut iter = list.iter_mut();
185        assert_eq!(iter.next(), Some(&mut 1));
186        assert_eq!(iter.next(), Some(&mut 2));
187        assert_eq!(iter.next(), Some(&mut 3));
188        assert_eq!(iter.next(), None);
189    }
190
191    #[test]
192    fn miri_food() {
193        let mut list = List::new();
194
195        list.push(1);
196        list.push(2);
197        list.push(3);
198
199        assert!(list.pop() == Some(1));
200        list.push(4);
201        assert!(list.pop() == Some(2));
202        list.push(5);
203
204        assert!(list.peek() == Some(&3));
205        list.push(6);
206        list.peek_mut().map(|x| *x *= 10);
207        assert!(list.peek() == Some(&30));
208        assert!(list.pop() == Some(30));
209
210        for elem in list.iter_mut() {
211            *elem *= 100;
212        }
213
214        let mut iter = list.iter();
215        assert_eq!(iter.next(), Some(&400));
216        assert_eq!(iter.next(), Some(&500));
217        assert_eq!(iter.next(), Some(&600));
218        assert_eq!(iter.next(), None);
219        assert_eq!(iter.next(), None);
220
221        assert!(list.pop() == Some(400));
222        list.peek_mut().map(|x| *x *= 10);
223        assert!(list.peek() == Some(&5000));
224        list.push(7);
225
226        // Drop it on the ground and let the dtor exercise itself
227    }
228}
rust_examples/list_seventh.rs

rust_examples/
list_seventh.rs
