rust_examples/
list_seventh.rs1struct 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 assert_eq!(list.pop(), None);
118
119 list.push(1);
121 list.push(2);
122 list.push(3);
123
124 assert_eq!(list.pop(), Some(1));
126 assert_eq!(list.pop(), Some(2));
127
128 list.push(4);
130 list.push(5);
131
132 assert_eq!(list.pop(), Some(3));
134 assert_eq!(list.pop(), Some(4));
135
136 assert_eq!(list.pop(), Some(5));
138 assert_eq!(list.pop(), None);
139
140 list.push(6);
142 list.push(7);
143
144 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 }
228}