]>
Commit | Line | Data |
---|---|---|
416331ca XL |
1 | use super::*; |
2 | ||
3 | use std::thread; | |
4 | use std::vec::Vec; | |
5 | ||
6 | use rand::{thread_rng, RngCore}; | |
7 | ||
8 | fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> { | |
9 | v.iter().cloned().collect() | |
10 | } | |
11 | ||
12 | pub fn check_links<T>(list: &LinkedList<T>) { | |
13 | unsafe { | |
14 | let mut len = 0; | |
15 | let mut last_ptr: Option<&Node<T>> = None; | |
16 | let mut node_ptr: &Node<T>; | |
17 | match list.head { | |
18 | None => { | |
19 | // tail node should also be None. | |
20 | assert!(list.tail.is_none()); | |
21 | assert_eq!(0, list.len); | |
22 | return; | |
23 | } | |
24 | Some(node) => node_ptr = &*node.as_ptr(), | |
25 | } | |
26 | loop { | |
27 | match (last_ptr, node_ptr.prev) { | |
28 | (None, None) => {} | |
29 | (None, _) => panic!("prev link for head"), | |
30 | (Some(p), Some(pptr)) => { | |
31 | assert_eq!(p as *const Node<T>, pptr.as_ptr() as *const Node<T>); | |
32 | } | |
33 | _ => panic!("prev link is none, not good"), | |
34 | } | |
35 | match node_ptr.next { | |
36 | Some(next) => { | |
37 | last_ptr = Some(node_ptr); | |
38 | node_ptr = &*next.as_ptr(); | |
39 | len += 1; | |
40 | } | |
41 | None => { | |
42 | len += 1; | |
43 | break; | |
44 | } | |
45 | } | |
46 | } | |
47 | ||
48 | // verify that the tail node points to the last node. | |
49 | let tail = list.tail.as_ref().expect("some tail node").as_ref(); | |
50 | assert_eq!(tail as *const Node<T>, node_ptr as *const Node<T>); | |
51 | // check that len matches interior links. | |
52 | assert_eq!(len, list.len); | |
53 | } | |
54 | } | |
55 | ||
56 | #[test] | |
57 | fn test_append() { | |
58 | // Empty to empty | |
59 | { | |
60 | let mut m = LinkedList::<i32>::new(); | |
61 | let mut n = LinkedList::new(); | |
62 | m.append(&mut n); | |
63 | check_links(&m); | |
64 | assert_eq!(m.len(), 0); | |
65 | assert_eq!(n.len(), 0); | |
66 | } | |
67 | // Non-empty to empty | |
68 | { | |
69 | let mut m = LinkedList::new(); | |
70 | let mut n = LinkedList::new(); | |
71 | n.push_back(2); | |
72 | m.append(&mut n); | |
73 | check_links(&m); | |
74 | assert_eq!(m.len(), 1); | |
75 | assert_eq!(m.pop_back(), Some(2)); | |
76 | assert_eq!(n.len(), 0); | |
77 | check_links(&m); | |
78 | } | |
79 | // Empty to non-empty | |
80 | { | |
81 | let mut m = LinkedList::new(); | |
82 | let mut n = LinkedList::new(); | |
83 | m.push_back(2); | |
84 | m.append(&mut n); | |
85 | check_links(&m); | |
86 | assert_eq!(m.len(), 1); | |
87 | assert_eq!(m.pop_back(), Some(2)); | |
88 | check_links(&m); | |
89 | } | |
90 | ||
91 | // Non-empty to non-empty | |
92 | let v = vec![1, 2, 3, 4, 5]; | |
93 | let u = vec![9, 8, 1, 2, 3, 4, 5]; | |
94 | let mut m = list_from(&v); | |
95 | let mut n = list_from(&u); | |
96 | m.append(&mut n); | |
97 | check_links(&m); | |
98 | let mut sum = v; | |
99 | sum.extend_from_slice(&u); | |
100 | assert_eq!(sum.len(), m.len()); | |
101 | for elt in sum { | |
102 | assert_eq!(m.pop_front(), Some(elt)) | |
103 | } | |
104 | assert_eq!(n.len(), 0); | |
e1599b0c XL |
105 | // Let's make sure it's working properly, since we |
106 | // did some direct changes to private members. | |
416331ca XL |
107 | n.push_back(3); |
108 | assert_eq!(n.len(), 1); | |
109 | assert_eq!(n.pop_front(), Some(3)); | |
110 | check_links(&n); | |
111 | } | |
112 | ||
e74abb32 XL |
113 | #[test] |
114 | fn test_clone_from() { | |
115 | // Short cloned from long | |
116 | { | |
117 | let v = vec![1, 2, 3, 4, 5]; | |
118 | let u = vec![8, 7, 6, 2, 3, 4, 5]; | |
119 | let mut m = list_from(&v); | |
120 | let n = list_from(&u); | |
121 | m.clone_from(&n); | |
122 | check_links(&m); | |
123 | assert_eq!(m, n); | |
124 | for elt in u { | |
125 | assert_eq!(m.pop_front(), Some(elt)) | |
126 | } | |
127 | } | |
128 | // Long cloned from short | |
129 | { | |
130 | let v = vec![1, 2, 3, 4, 5]; | |
131 | let u = vec![6, 7, 8]; | |
132 | let mut m = list_from(&v); | |
133 | let n = list_from(&u); | |
134 | m.clone_from(&n); | |
135 | check_links(&m); | |
136 | assert_eq!(m, n); | |
137 | for elt in u { | |
138 | assert_eq!(m.pop_front(), Some(elt)) | |
139 | } | |
140 | } | |
141 | // Two equal length lists | |
142 | { | |
143 | let v = vec![1, 2, 3, 4, 5]; | |
144 | let u = vec![9, 8, 1, 2, 3]; | |
145 | let mut m = list_from(&v); | |
146 | let n = list_from(&u); | |
147 | m.clone_from(&n); | |
148 | check_links(&m); | |
149 | assert_eq!(m, n); | |
150 | for elt in u { | |
151 | assert_eq!(m.pop_front(), Some(elt)) | |
152 | } | |
153 | } | |
154 | } | |
155 | ||
416331ca XL |
156 | #[test] |
157 | #[cfg_attr(target_os = "emscripten", ignore)] | |
416331ca XL |
158 | fn test_send() { |
159 | let n = list_from(&[1, 2, 3]); | |
160 | thread::spawn(move || { | |
60c5eb7d XL |
161 | check_links(&n); |
162 | let a: &[_] = &[&1, &2, &3]; | |
163 | assert_eq!(a, &*n.iter().collect::<Vec<_>>()); | |
164 | }) | |
165 | .join() | |
166 | .ok() | |
167 | .unwrap(); | |
416331ca XL |
168 | } |
169 | ||
170 | #[test] | |
171 | fn test_fuzz() { | |
172 | for _ in 0..25 { | |
173 | fuzz_test(3); | |
174 | fuzz_test(16); | |
175 | #[cfg(not(miri))] // Miri is too slow | |
176 | fuzz_test(189); | |
177 | } | |
178 | } | |
179 | ||
180 | #[test] | |
181 | fn test_26021() { | |
182 | // There was a bug in split_off that failed to null out the RHS's head's prev ptr. | |
183 | // This caused the RHS's dtor to walk up into the LHS at drop and delete all of | |
184 | // its nodes. | |
185 | // | |
186 | // https://github.com/rust-lang/rust/issues/26021 | |
187 | let mut v1 = LinkedList::new(); | |
188 | v1.push_front(1); | |
189 | v1.push_front(1); | |
190 | v1.push_front(1); | |
191 | v1.push_front(1); | |
192 | let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption | |
193 | assert_eq!(v1.len(), 3); | |
194 | ||
195 | assert_eq!(v1.iter().len(), 3); | |
196 | assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3); | |
197 | } | |
198 | ||
199 | #[test] | |
200 | fn test_split_off() { | |
201 | let mut v1 = LinkedList::new(); | |
202 | v1.push_front(1); | |
203 | v1.push_front(1); | |
204 | v1.push_front(1); | |
205 | v1.push_front(1); | |
206 | ||
207 | // test all splits | |
208 | for ix in 0..1 + v1.len() { | |
209 | let mut a = v1.clone(); | |
210 | let b = a.split_off(ix); | |
211 | check_links(&a); | |
212 | check_links(&b); | |
213 | a.extend(b); | |
214 | assert_eq!(v1, a); | |
215 | } | |
216 | } | |
217 | ||
218 | fn fuzz_test(sz: i32) { | |
219 | let mut m: LinkedList<_> = LinkedList::new(); | |
220 | let mut v = vec![]; | |
221 | for i in 0..sz { | |
222 | check_links(&m); | |
223 | let r: u8 = thread_rng().next_u32() as u8; | |
224 | match r % 6 { | |
225 | 0 => { | |
226 | m.pop_back(); | |
227 | v.pop(); | |
228 | } | |
229 | 1 => { | |
230 | if !v.is_empty() { | |
231 | m.pop_front(); | |
232 | v.remove(0); | |
233 | } | |
234 | } | |
235 | 2 | 4 => { | |
236 | m.push_front(-i); | |
237 | v.insert(0, -i); | |
238 | } | |
239 | 3 | 5 | _ => { | |
240 | m.push_back(i); | |
241 | v.push(i); | |
242 | } | |
243 | } | |
244 | } | |
245 | ||
246 | check_links(&m); | |
247 | ||
248 | let mut i = 0; | |
249 | for (a, &b) in m.into_iter().zip(&v) { | |
250 | i += 1; | |
251 | assert_eq!(a, b); | |
252 | } | |
253 | assert_eq!(i, v.len()); | |
254 | } | |
255 | ||
256 | #[test] | |
257 | fn drain_filter_test() { | |
258 | let mut m: LinkedList<u32> = LinkedList::new(); | |
259 | m.extend(&[1, 2, 3, 4, 5, 6]); | |
260 | let deleted = m.drain_filter(|v| *v < 4).collect::<Vec<_>>(); | |
261 | ||
262 | check_links(&m); | |
263 | ||
264 | assert_eq!(deleted, &[1, 2, 3]); | |
265 | assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]); | |
266 | } | |
267 | ||
268 | #[test] | |
269 | fn drain_to_empty_test() { | |
270 | let mut m: LinkedList<u32> = LinkedList::new(); | |
271 | m.extend(&[1, 2, 3, 4, 5, 6]); | |
272 | let deleted = m.drain_filter(|_| true).collect::<Vec<_>>(); | |
273 | ||
274 | check_links(&m); | |
275 | ||
276 | assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]); | |
277 | assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]); | |
278 | } | |
dfeec247 XL |
279 | |
280 | #[test] | |
281 | fn test_cursor_move_peek() { | |
282 | let mut m: LinkedList<u32> = LinkedList::new(); | |
283 | m.extend(&[1, 2, 3, 4, 5, 6]); | |
284 | let mut cursor = m.cursor_front(); | |
285 | assert_eq!(cursor.current(), Some(&1)); | |
286 | assert_eq!(cursor.peek_next(), Some(&2)); | |
287 | assert_eq!(cursor.peek_prev(), None); | |
288 | assert_eq!(cursor.index(), Some(0)); | |
289 | cursor.move_prev(); | |
290 | assert_eq!(cursor.current(), None); | |
291 | assert_eq!(cursor.peek_next(), Some(&1)); | |
292 | assert_eq!(cursor.peek_prev(), Some(&6)); | |
293 | assert_eq!(cursor.index(), None); | |
294 | cursor.move_next(); | |
295 | cursor.move_next(); | |
296 | assert_eq!(cursor.current(), Some(&2)); | |
297 | assert_eq!(cursor.peek_next(), Some(&3)); | |
298 | assert_eq!(cursor.peek_prev(), Some(&1)); | |
299 | assert_eq!(cursor.index(), Some(1)); | |
300 | ||
301 | let mut cursor = m.cursor_back(); | |
302 | assert_eq!(cursor.current(), Some(&6)); | |
303 | assert_eq!(cursor.peek_next(), None); | |
304 | assert_eq!(cursor.peek_prev(), Some(&5)); | |
305 | assert_eq!(cursor.index(), Some(5)); | |
306 | cursor.move_next(); | |
307 | assert_eq!(cursor.current(), None); | |
308 | assert_eq!(cursor.peek_next(), Some(&1)); | |
309 | assert_eq!(cursor.peek_prev(), Some(&6)); | |
310 | assert_eq!(cursor.index(), None); | |
311 | cursor.move_prev(); | |
312 | cursor.move_prev(); | |
313 | assert_eq!(cursor.current(), Some(&5)); | |
314 | assert_eq!(cursor.peek_next(), Some(&6)); | |
315 | assert_eq!(cursor.peek_prev(), Some(&4)); | |
316 | assert_eq!(cursor.index(), Some(4)); | |
317 | ||
318 | let mut m: LinkedList<u32> = LinkedList::new(); | |
319 | m.extend(&[1, 2, 3, 4, 5, 6]); | |
320 | let mut cursor = m.cursor_front_mut(); | |
321 | assert_eq!(cursor.current(), Some(&mut 1)); | |
322 | assert_eq!(cursor.peek_next(), Some(&mut 2)); | |
323 | assert_eq!(cursor.peek_prev(), None); | |
324 | assert_eq!(cursor.index(), Some(0)); | |
325 | cursor.move_prev(); | |
326 | assert_eq!(cursor.current(), None); | |
327 | assert_eq!(cursor.peek_next(), Some(&mut 1)); | |
328 | assert_eq!(cursor.peek_prev(), Some(&mut 6)); | |
329 | assert_eq!(cursor.index(), None); | |
330 | cursor.move_next(); | |
331 | cursor.move_next(); | |
332 | assert_eq!(cursor.current(), Some(&mut 2)); | |
333 | assert_eq!(cursor.peek_next(), Some(&mut 3)); | |
334 | assert_eq!(cursor.peek_prev(), Some(&mut 1)); | |
335 | assert_eq!(cursor.index(), Some(1)); | |
336 | let mut cursor2 = cursor.as_cursor(); | |
337 | assert_eq!(cursor2.current(), Some(&2)); | |
338 | assert_eq!(cursor2.index(), Some(1)); | |
339 | cursor2.move_next(); | |
340 | assert_eq!(cursor2.current(), Some(&3)); | |
341 | assert_eq!(cursor2.index(), Some(2)); | |
342 | assert_eq!(cursor.current(), Some(&mut 2)); | |
343 | assert_eq!(cursor.index(), Some(1)); | |
344 | ||
345 | let mut m: LinkedList<u32> = LinkedList::new(); | |
346 | m.extend(&[1, 2, 3, 4, 5, 6]); | |
347 | let mut cursor = m.cursor_back_mut(); | |
348 | assert_eq!(cursor.current(), Some(&mut 6)); | |
349 | assert_eq!(cursor.peek_next(), None); | |
350 | assert_eq!(cursor.peek_prev(), Some(&mut 5)); | |
351 | assert_eq!(cursor.index(), Some(5)); | |
352 | cursor.move_next(); | |
353 | assert_eq!(cursor.current(), None); | |
354 | assert_eq!(cursor.peek_next(), Some(&mut 1)); | |
355 | assert_eq!(cursor.peek_prev(), Some(&mut 6)); | |
356 | assert_eq!(cursor.index(), None); | |
357 | cursor.move_prev(); | |
358 | cursor.move_prev(); | |
359 | assert_eq!(cursor.current(), Some(&mut 5)); | |
360 | assert_eq!(cursor.peek_next(), Some(&mut 6)); | |
361 | assert_eq!(cursor.peek_prev(), Some(&mut 4)); | |
362 | assert_eq!(cursor.index(), Some(4)); | |
363 | let mut cursor2 = cursor.as_cursor(); | |
364 | assert_eq!(cursor2.current(), Some(&5)); | |
365 | assert_eq!(cursor2.index(), Some(4)); | |
366 | cursor2.move_prev(); | |
367 | assert_eq!(cursor2.current(), Some(&4)); | |
368 | assert_eq!(cursor2.index(), Some(3)); | |
369 | assert_eq!(cursor.current(), Some(&mut 5)); | |
370 | assert_eq!(cursor.index(), Some(4)); | |
371 | } | |
372 | ||
373 | #[test] | |
374 | fn test_cursor_mut_insert() { | |
375 | let mut m: LinkedList<u32> = LinkedList::new(); | |
376 | m.extend(&[1, 2, 3, 4, 5, 6]); | |
377 | let mut cursor = m.cursor_front_mut(); | |
378 | cursor.insert_before(7); | |
379 | cursor.insert_after(8); | |
380 | check_links(&m); | |
381 | assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]); | |
382 | let mut cursor = m.cursor_front_mut(); | |
383 | cursor.move_prev(); | |
384 | cursor.insert_before(9); | |
385 | cursor.insert_after(10); | |
386 | check_links(&m); | |
387 | assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]); | |
388 | let mut cursor = m.cursor_front_mut(); | |
389 | cursor.move_prev(); | |
390 | assert_eq!(cursor.remove_current(), None); | |
391 | cursor.move_next(); | |
392 | cursor.move_next(); | |
393 | assert_eq!(cursor.remove_current(), Some(7)); | |
394 | cursor.move_prev(); | |
395 | cursor.move_prev(); | |
396 | cursor.move_prev(); | |
397 | assert_eq!(cursor.remove_current(), Some(9)); | |
398 | cursor.move_next(); | |
399 | assert_eq!(cursor.remove_current(), Some(10)); | |
400 | check_links(&m); | |
401 | assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]); | |
402 | let mut cursor = m.cursor_front_mut(); | |
403 | let mut p: LinkedList<u32> = LinkedList::new(); | |
404 | p.extend(&[100, 101, 102, 103]); | |
405 | let mut q: LinkedList<u32> = LinkedList::new(); | |
406 | q.extend(&[200, 201, 202, 203]); | |
407 | cursor.splice_after(p); | |
408 | cursor.splice_before(q); | |
409 | check_links(&m); | |
410 | assert_eq!( | |
411 | m.iter().cloned().collect::<Vec<_>>(), | |
412 | &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6] | |
413 | ); | |
414 | let mut cursor = m.cursor_front_mut(); | |
415 | cursor.move_prev(); | |
416 | let tmp = cursor.split_before(); | |
417 | assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]); | |
418 | m = tmp; | |
419 | let mut cursor = m.cursor_front_mut(); | |
420 | cursor.move_next(); | |
421 | cursor.move_next(); | |
422 | cursor.move_next(); | |
423 | cursor.move_next(); | |
424 | cursor.move_next(); | |
425 | cursor.move_next(); | |
426 | let tmp = cursor.split_after(); | |
427 | assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]); | |
428 | check_links(&m); | |
429 | assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]); | |
430 | } | |
136023e0 XL |
431 | |
432 | #[test] | |
433 | fn test_cursor_push_front_back() { | |
434 | let mut ll: LinkedList<u32> = LinkedList::new(); | |
435 | ll.extend(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); | |
436 | let mut c = ll.cursor_front_mut(); | |
437 | assert_eq!(c.current(), Some(&mut 1)); | |
438 | assert_eq!(c.index(), Some(0)); | |
439 | c.push_front(0); | |
440 | assert_eq!(c.current(), Some(&mut 1)); | |
441 | assert_eq!(c.peek_prev(), Some(&mut 0)); | |
442 | assert_eq!(c.index(), Some(1)); | |
443 | c.push_back(11); | |
444 | drop(c); | |
445 | let p = ll.cursor_back().front().unwrap(); | |
446 | assert_eq!(p, &0); | |
447 | assert_eq!(ll, (0..12).collect()); | |
448 | check_links(&ll); | |
449 | } | |
450 | ||
451 | #[test] | |
452 | fn test_cursor_pop_front_back() { | |
453 | let mut ll: LinkedList<u32> = LinkedList::new(); | |
454 | ll.extend(&[1, 2, 3, 4, 5, 6]); | |
455 | let mut c = ll.cursor_back_mut(); | |
456 | assert_eq!(c.pop_front(), Some(1)); | |
457 | c.move_prev(); | |
458 | c.move_prev(); | |
459 | c.move_prev(); | |
460 | assert_eq!(c.pop_back(), Some(6)); | |
461 | let c = c.as_cursor(); | |
462 | assert_eq!(c.front(), Some(&2)); | |
463 | assert_eq!(c.back(), Some(&5)); | |
464 | assert_eq!(c.index(), Some(1)); | |
465 | drop(c); | |
466 | assert_eq!(ll, (2..6).collect()); | |
467 | check_links(&ll); | |
468 | let mut c = ll.cursor_back_mut(); | |
469 | assert_eq!(c.current(), Some(&mut 5)); | |
470 | assert_eq!(c.index, 3); | |
471 | assert_eq!(c.pop_back(), Some(5)); | |
472 | assert_eq!(c.current(), None); | |
473 | assert_eq!(c.index, 3); | |
474 | assert_eq!(c.pop_back(), Some(4)); | |
475 | assert_eq!(c.current(), None); | |
476 | assert_eq!(c.index, 2); | |
477 | } |