]>
git.proxmox.com Git - rustc.git/blob - library/alloc/src/collections/linked_list/tests.rs
6 use rand
::{thread_rng, RngCore}
;
8 fn list_from
<T
: Clone
>(v
: &[T
]) -> LinkedList
<T
> {
9 v
.iter().cloned().collect()
12 pub fn check_links
<T
>(list
: &LinkedList
<T
>) {
15 let mut last_ptr
: Option
<&Node
<T
>> = None
;
16 let mut node_ptr
: &Node
<T
>;
19 // tail node should also be None.
20 assert
!(list
.tail
.is_none());
21 assert_eq
!(0, list
.len
);
24 Some(node
) => node_ptr
= &*node
.as_ptr(),
27 match (last_ptr
, node_ptr
.prev
) {
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
>);
33 _
=> panic
!("prev link is none, not good"),
37 last_ptr
= Some(node_ptr
);
38 node_ptr
= &*next
.as_ptr();
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
);
60 let mut m
= LinkedList
::<i32>::new();
61 let mut n
= LinkedList
::new();
64 assert_eq
!(m
.len(), 0);
65 assert_eq
!(n
.len(), 0);
69 let mut m
= LinkedList
::new();
70 let mut n
= LinkedList
::new();
74 assert_eq
!(m
.len(), 1);
75 assert_eq
!(m
.pop_back(), Some(2));
76 assert_eq
!(n
.len(), 0);
81 let mut m
= LinkedList
::new();
82 let mut n
= LinkedList
::new();
86 assert_eq
!(m
.len(), 1);
87 assert_eq
!(m
.pop_back(), Some(2));
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
);
99 sum
.extend_from_slice(&u
);
100 assert_eq
!(sum
.len(), m
.len());
102 assert_eq
!(m
.pop_front(), Some(elt
))
104 assert_eq
!(n
.len(), 0);
105 // Let's make sure it's working properly, since we
106 // did some direct changes to private members.
108 assert_eq
!(n
.len(), 1);
109 assert_eq
!(n
.pop_front(), Some(3));
114 fn test_clone_from() {
115 // Short cloned from long
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
);
125 assert_eq
!(m
.pop_front(), Some(elt
))
128 // Long cloned from short
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
);
138 assert_eq
!(m
.pop_front(), Some(elt
))
141 // Two equal length lists
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
);
151 assert_eq
!(m
.pop_front(), Some(elt
))
157 #[cfg_attr(target_os = "emscripten", ignore)]
159 let n
= list_from(&[1, 2, 3]);
160 thread
::spawn(move || {
162 let a
: &[_
] = &[&1, &2, &3];
163 assert_eq
!(a
, &*n
.iter().collect
::<Vec
<_
>>());
175 #[cfg(not(miri))] // Miri is too slow
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
186 // https://github.com/rust-lang/rust/issues/26021
187 let mut v1
= LinkedList
::new();
192 let _
= v1
.split_off(3); // Dropping this now should not cause laundry consumption
193 assert_eq
!(v1
.len(), 3);
195 assert_eq
!(v1
.iter().len(), 3);
196 assert_eq
!(v1
.iter().collect
::<Vec
<_
>>().len(), 3);
200 fn test_split_off() {
201 let mut v1
= LinkedList
::new();
208 for ix
in 0..1 + v1
.len() {
209 let mut a
= v1
.clone();
210 let b
= a
.split_off(ix
);
218 fn fuzz_test(sz
: i32) {
219 let mut m
: LinkedList
<_
> = LinkedList
::new();
223 let r
: u8 = thread_rng().next_u32() as u8;
249 for (a
, &b
) in m
.into_iter().zip(&v
) {
253 assert_eq
!(i
, v
.len());
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
<_
>>();
264 assert_eq
!(deleted
, &[1, 2, 3]);
265 assert_eq
!(m
.into_iter().collect
::<Vec
<_
>>(), &[4, 5, 6]);
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
<_
>>();
276 assert_eq
!(deleted
, &[1, 2, 3, 4, 5, 6]);
277 assert_eq
!(m
.into_iter().collect
::<Vec
<_
>>(), &[]);
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));
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
);
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));
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));
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
);
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));
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));
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
);
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));
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));
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));
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
);
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));
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));
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);
381 assert_eq
!(m
.iter().cloned().collect
::<Vec
<_
>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
382 let mut cursor
= m
.cursor_front_mut();
384 cursor
.insert_before(9);
385 cursor
.insert_after(10);
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();
390 assert_eq
!(cursor
.remove_current(), None
);
393 assert_eq
!(cursor
.remove_current(), Some(7));
397 assert_eq
!(cursor
.remove_current(), Some(9));
399 assert_eq
!(cursor
.remove_current(), Some(10));
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
);
411 m
.iter().cloned().collect
::<Vec
<_
>>(),
412 &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
414 let mut cursor
= m
.cursor_front_mut();
416 let tmp
= cursor
.split_before();
417 assert_eq
!(m
.into_iter().collect
::<Vec
<_
>>(), &[]);
419 let mut cursor
= m
.cursor_front_mut();
426 let tmp
= cursor
.split_after();
427 assert_eq
!(tmp
.into_iter().collect
::<Vec
<_
>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
429 assert_eq
!(m
.iter().cloned().collect
::<Vec
<_
>>(), &[200, 201, 202, 203, 1, 100, 101]);
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));
440 assert_eq
!(c
.current(), Some(&mut 1));
441 assert_eq
!(c
.peek_prev(), Some(&mut 0));
442 assert_eq
!(c
.index(), Some(1));
445 let p
= ll
.cursor_back().front().unwrap();
447 assert_eq
!(ll
, (0..12).collect());
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));
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));
466 assert_eq
!(ll
, (2..6).collect());
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);