]> git.proxmox.com Git - rustc.git/blame - src/libcollections/linked_list.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / libcollections / linked_list.rs
CommitLineData
85aaf69f 1// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
1a4d82fc
JJ
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! A doubly-linked list with owned nodes.
12//!
85aaf69f 13//! The `LinkedList` allows pushing and popping elements at either end and is thus
1a4d82fc
JJ
14//! efficiently usable as a double-ended queue.
15
85aaf69f 16// LinkedList is constructed like a singly-linked list over the field `next`.
1a4d82fc
JJ
17// including the last link being None; each Node owns its `next` field.
18//
85aaf69f 19// Backlinks over LinkedList::prev are raw pointers that form a full chain in
1a4d82fc
JJ
20// the reverse direction.
21
85aaf69f 22#![stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 23
7453a54e 24use alloc::boxed::{Box, IntermediateBox};
1a4d82fc 25use core::cmp::Ordering;
1a4d82fc 26use core::fmt;
85aaf69f 27use core::hash::{Hasher, Hash};
e9174d1e 28use core::iter::FromIterator;
1a4d82fc 29use core::mem;
7453a54e
SL
30use core::ops::{BoxPlace, InPlace, Place, Placer};
31use core::ptr::{self, Shared};
1a4d82fc
JJ
32
33/// A doubly-linked list.
85aaf69f
SL
34#[stable(feature = "rust1", since = "1.0.0")]
35pub struct LinkedList<T> {
36 length: usize,
1a4d82fc
JJ
37 list_head: Link<T>,
38 list_tail: Rawlink<Node<T>>,
39}
40
41type Link<T> = Option<Box<Node<T>>>;
42
43struct Rawlink<T> {
9cc50fc6 44 p: Option<Shared<T>>,
1a4d82fc
JJ
45}
46
47impl<T> Copy for Rawlink<T> {}
92a42be0
SL
48unsafe impl<T: Send> Send for Rawlink<T> {}
49unsafe impl<T: Sync> Sync for Rawlink<T> {}
1a4d82fc
JJ
50
51struct Node<T> {
52 next: Link<T>,
53 prev: Rawlink<Node<T>>,
54 value: T,
55}
56
85aaf69f
SL
57/// An iterator over references to the items of a `LinkedList`.
58#[stable(feature = "rust1", since = "1.0.0")]
92a42be0 59pub struct Iter<'a, T: 'a> {
1a4d82fc
JJ
60 head: &'a Link<T>,
61 tail: Rawlink<Node<T>>,
85aaf69f 62 nelem: usize,
1a4d82fc
JJ
63}
64
65// FIXME #19839: deriving is too aggressive on the bounds (T doesn't need to be Clone).
85aaf69f 66#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
67impl<'a, T> Clone for Iter<'a, T> {
68 fn clone(&self) -> Iter<'a, T> {
69 Iter {
70 head: self.head.clone(),
71 tail: self.tail,
72 nelem: self.nelem,
73 }
74 }
75}
76
85aaf69f
SL
77/// An iterator over mutable references to the items of a `LinkedList`.
78#[stable(feature = "rust1", since = "1.0.0")]
92a42be0 79pub struct IterMut<'a, T: 'a> {
85aaf69f 80 list: &'a mut LinkedList<T>,
1a4d82fc
JJ
81 head: Rawlink<Node<T>>,
82 tail: Rawlink<Node<T>>,
85aaf69f 83 nelem: usize,
1a4d82fc
JJ
84}
85
7453a54e 86/// An iterator over the items of a `LinkedList`.
1a4d82fc 87#[derive(Clone)]
85aaf69f 88#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 89pub struct IntoIter<T> {
92a42be0 90 list: LinkedList<T>,
1a4d82fc
JJ
91}
92
93/// Rawlink is a type like Option<T> but for holding a raw pointer
94impl<T> Rawlink<T> {
95 /// Like Option::None for Rawlink
96 fn none() -> Rawlink<T> {
9cc50fc6 97 Rawlink { p: None }
1a4d82fc
JJ
98 }
99
100 /// Like Option::Some for Rawlink
101 fn some(n: &mut T) -> Rawlink<T> {
9cc50fc6 102 unsafe { Rawlink { p: Some(Shared::new(n)) } }
1a4d82fc
JJ
103 }
104
105 /// Convert the `Rawlink` into an Option value
62682a34
SL
106 ///
107 /// **unsafe** because:
108 ///
109 /// - Dereference of raw pointer.
110 /// - Returns reference of arbitrary lifetime.
111 unsafe fn resolve<'a>(&self) -> Option<&'a T> {
9cc50fc6 112 self.p.map(|p| &**p)
1a4d82fc
JJ
113 }
114
115 /// Convert the `Rawlink` into an Option value
62682a34
SL
116 ///
117 /// **unsafe** because:
118 ///
119 /// - Dereference of raw pointer.
120 /// - Returns reference of arbitrary lifetime.
121 unsafe fn resolve_mut<'a>(&mut self) -> Option<&'a mut T> {
9cc50fc6 122 self.p.map(|p| &mut **p)
1a4d82fc
JJ
123 }
124
125 /// Return the `Rawlink` and replace with `Rawlink::none()`
126 fn take(&mut self) -> Rawlink<T> {
127 mem::replace(self, Rawlink::none())
128 }
129}
130
62682a34
SL
131impl<'a, T> From<&'a mut Link<T>> for Rawlink<Node<T>> {
132 fn from(node: &'a mut Link<T>) -> Self {
133 match node.as_mut() {
134 None => Rawlink::none(),
135 Some(ptr) => Rawlink::some(ptr),
136 }
137 }
138}
139
1a4d82fc
JJ
140impl<T> Clone for Rawlink<T> {
141 #[inline]
142 fn clone(&self) -> Rawlink<T> {
92a42be0 143 Rawlink { p: self.p }
1a4d82fc
JJ
144 }
145}
146
147impl<T> Node<T> {
148 fn new(v: T) -> Node<T> {
92a42be0
SL
149 Node {
150 value: v,
151 next: None,
152 prev: Rawlink::none(),
153 }
1a4d82fc 154 }
62682a34
SL
155
156 /// Update the `prev` link on `next`, then set self's next pointer.
157 ///
158 /// `self.next` should be `None` when you call this
159 /// (otherwise a Node is probably being dropped by mistake).
160 fn set_next(&mut self, mut next: Box<Node<T>>) {
161 debug_assert!(self.next.is_none());
162 next.prev = Rawlink::some(self);
163 self.next = Some(next);
164 }
1a4d82fc
JJ
165}
166
62682a34
SL
167/// Clear the .prev field on `next`, then return `Some(next)`
168fn link_no_prev<T>(mut next: Box<Node<T>>) -> Link<T> {
169 next.prev = Rawlink::none();
1a4d82fc
JJ
170 Some(next)
171}
172
173// private methods
85aaf69f 174impl<T> LinkedList<T> {
1a4d82fc
JJ
175 /// Add a Node first in the list
176 #[inline]
177 fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
178 match self.list_head {
179 None => {
62682a34
SL
180 self.list_head = link_no_prev(new_head);
181 self.list_tail = Rawlink::from(&mut self.list_head);
1a4d82fc
JJ
182 }
183 Some(ref mut head) => {
184 new_head.prev = Rawlink::none();
185 head.prev = Rawlink::some(&mut *new_head);
186 mem::swap(head, &mut new_head);
187 head.next = Some(new_head);
188 }
189 }
190 self.length += 1;
191 }
192
193 /// Remove the first Node and return it, or None if the list is empty
194 #[inline]
195 fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
196 self.list_head.take().map(|mut front_node| {
197 self.length -= 1;
198 match front_node.next.take() {
62682a34 199 Some(node) => self.list_head = link_no_prev(node),
92a42be0 200 None => self.list_tail = Rawlink::none(),
1a4d82fc
JJ
201 }
202 front_node
203 })
204 }
205
206 /// Add a Node last in the list
207 #[inline]
62682a34
SL
208 fn push_back_node(&mut self, new_tail: Box<Node<T>>) {
209 match unsafe { self.list_tail.resolve_mut() } {
1a4d82fc
JJ
210 None => return self.push_front_node(new_tail),
211 Some(tail) => {
62682a34
SL
212 tail.set_next(new_tail);
213 self.list_tail = Rawlink::from(&mut tail.next);
1a4d82fc
JJ
214 }
215 }
216 self.length += 1;
217 }
218
219 /// Remove the last Node and return it, or None if the list is empty
220 #[inline]
221 fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
62682a34
SL
222 unsafe {
223 self.list_tail.resolve_mut().and_then(|tail| {
224 self.length -= 1;
225 self.list_tail = tail.prev;
226 match tail.prev.resolve_mut() {
227 None => self.list_head.take(),
92a42be0 228 Some(tail_prev) => tail_prev.next.take(),
62682a34
SL
229 }
230 })
231 }
1a4d82fc
JJ
232 }
233}
234
85aaf69f
SL
235#[stable(feature = "rust1", since = "1.0.0")]
236impl<T> Default for LinkedList<T> {
1a4d82fc 237 #[inline]
92a42be0
SL
238 fn default() -> LinkedList<T> {
239 LinkedList::new()
240 }
1a4d82fc
JJ
241}
242
85aaf69f
SL
243impl<T> LinkedList<T> {
244 /// Creates an empty `LinkedList`.
1a4d82fc 245 #[inline]
85aaf69f
SL
246 #[stable(feature = "rust1", since = "1.0.0")]
247 pub fn new() -> LinkedList<T> {
92a42be0
SL
248 LinkedList {
249 list_head: None,
250 list_tail: Rawlink::none(),
251 length: 0,
252 }
1a4d82fc
JJ
253 }
254
85aaf69f 255 /// Moves all elements from `other` to the end of the list.
1a4d82fc 256 ///
85aaf69f
SL
257 /// This reuses all the nodes from `other` and moves them into `self`. After
258 /// this operation, `other` becomes empty.
259 ///
260 /// This operation should compute in O(1) time and O(1) memory.
1a4d82fc
JJ
261 ///
262 /// # Examples
263 ///
85aaf69f
SL
264 /// ```
265 /// use std::collections::LinkedList;
1a4d82fc 266 ///
85aaf69f
SL
267 /// let mut a = LinkedList::new();
268 /// let mut b = LinkedList::new();
269 /// a.push_back(1);
1a4d82fc 270 /// a.push_back(2);
85aaf69f 271 /// b.push_back(3);
1a4d82fc
JJ
272 /// b.push_back(4);
273 ///
85aaf69f 274 /// a.append(&mut b);
1a4d82fc 275 ///
62682a34 276 /// for e in &a {
1a4d82fc
JJ
277 /// println!("{}", e); // prints 1, then 2, then 3, then 4
278 /// }
85aaf69f 279 /// println!("{}", b.len()); // prints 0
1a4d82fc 280 /// ```
c34b1796 281 #[stable(feature = "rust1", since = "1.0.0")]
85aaf69f 282 pub fn append(&mut self, other: &mut LinkedList<T>) {
62682a34 283 match unsafe { self.list_tail.resolve_mut() } {
85aaf69f
SL
284 None => {
285 self.length = other.length;
286 self.list_head = other.list_head.take();
287 self.list_tail = other.list_tail.take();
92a42be0 288 }
1a4d82fc
JJ
289 Some(tail) => {
290 // Carefully empty `other`.
291 let o_tail = other.list_tail.take();
292 let o_length = other.length;
293 match other.list_head.take() {
294 None => return,
295 Some(node) => {
62682a34 296 tail.set_next(node);
1a4d82fc
JJ
297 self.list_tail = o_tail;
298 self.length += o_length;
299 }
300 }
301 }
302 }
85aaf69f 303 other.length = 0;
1a4d82fc
JJ
304 }
305
306 /// Provides a forward iterator.
307 #[inline]
85aaf69f 308 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 309 pub fn iter(&self) -> Iter<T> {
92a42be0
SL
310 Iter {
311 nelem: self.len(),
312 head: &self.list_head,
313 tail: self.list_tail,
314 }
1a4d82fc
JJ
315 }
316
317 /// Provides a forward iterator with mutable references.
318 #[inline]
85aaf69f 319 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 320 pub fn iter_mut(&mut self) -> IterMut<T> {
62682a34 321 IterMut {
1a4d82fc 322 nelem: self.len(),
62682a34 323 head: Rawlink::from(&mut self.list_head),
1a4d82fc 324 tail: self.list_tail,
92a42be0 325 list: self,
1a4d82fc
JJ
326 }
327 }
328
85aaf69f 329 /// Returns `true` if the `LinkedList` is empty.
1a4d82fc
JJ
330 ///
331 /// This operation should compute in O(1) time.
85aaf69f
SL
332 ///
333 /// # Examples
334 ///
335 /// ```
336 /// use std::collections::LinkedList;
337 ///
338 /// let mut dl = LinkedList::new();
339 /// assert!(dl.is_empty());
340 ///
341 /// dl.push_front("foo");
342 /// assert!(!dl.is_empty());
343 /// ```
1a4d82fc 344 #[inline]
85aaf69f 345 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
346 pub fn is_empty(&self) -> bool {
347 self.list_head.is_none()
348 }
349
85aaf69f 350 /// Returns the length of the `LinkedList`.
1a4d82fc
JJ
351 ///
352 /// This operation should compute in O(1) time.
85aaf69f
SL
353 ///
354 /// # Examples
355 ///
356 /// ```
357 /// use std::collections::LinkedList;
358 ///
359 /// let mut dl = LinkedList::new();
360 ///
361 /// dl.push_front(2);
362 /// assert_eq!(dl.len(), 1);
363 ///
364 /// dl.push_front(1);
365 /// assert_eq!(dl.len(), 2);
366 ///
367 /// dl.push_back(3);
368 /// assert_eq!(dl.len(), 3);
369 ///
370 /// ```
1a4d82fc 371 #[inline]
85aaf69f
SL
372 #[stable(feature = "rust1", since = "1.0.0")]
373 pub fn len(&self) -> usize {
1a4d82fc
JJ
374 self.length
375 }
376
85aaf69f 377 /// Removes all elements from the `LinkedList`.
1a4d82fc
JJ
378 ///
379 /// This operation should compute in O(n) time.
85aaf69f
SL
380 ///
381 /// # Examples
382 ///
383 /// ```
384 /// use std::collections::LinkedList;
385 ///
386 /// let mut dl = LinkedList::new();
387 ///
388 /// dl.push_front(2);
389 /// dl.push_front(1);
390 /// assert_eq!(dl.len(), 2);
391 /// assert_eq!(dl.front(), Some(&1));
392 ///
393 /// dl.clear();
394 /// assert_eq!(dl.len(), 0);
395 /// assert_eq!(dl.front(), None);
396 ///
397 /// ```
1a4d82fc 398 #[inline]
85aaf69f 399 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 400 pub fn clear(&mut self) {
85aaf69f 401 *self = LinkedList::new()
1a4d82fc
JJ
402 }
403
404 /// Provides a reference to the front element, or `None` if the list is
405 /// empty.
85aaf69f
SL
406 ///
407 /// # Examples
408 ///
409 /// ```
410 /// use std::collections::LinkedList;
411 ///
412 /// let mut dl = LinkedList::new();
413 /// assert_eq!(dl.front(), None);
414 ///
415 /// dl.push_front(1);
416 /// assert_eq!(dl.front(), Some(&1));
417 ///
418 /// ```
1a4d82fc 419 #[inline]
85aaf69f 420 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
421 pub fn front(&self) -> Option<&T> {
422 self.list_head.as_ref().map(|head| &head.value)
423 }
424
425 /// Provides a mutable reference to the front element, or `None` if the list
426 /// is empty.
85aaf69f
SL
427 ///
428 /// # Examples
429 ///
430 /// ```
431 /// use std::collections::LinkedList;
432 ///
433 /// let mut dl = LinkedList::new();
434 /// assert_eq!(dl.front(), None);
435 ///
436 /// dl.push_front(1);
437 /// assert_eq!(dl.front(), Some(&1));
438 ///
439 /// match dl.front_mut() {
440 /// None => {},
441 /// Some(x) => *x = 5,
442 /// }
443 /// assert_eq!(dl.front(), Some(&5));
444 ///
445 /// ```
1a4d82fc 446 #[inline]
85aaf69f 447 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
448 pub fn front_mut(&mut self) -> Option<&mut T> {
449 self.list_head.as_mut().map(|head| &mut head.value)
450 }
451
452 /// Provides a reference to the back element, or `None` if the list is
453 /// empty.
85aaf69f
SL
454 ///
455 /// # Examples
456 ///
457 /// ```
458 /// use std::collections::LinkedList;
459 ///
460 /// let mut dl = LinkedList::new();
461 /// assert_eq!(dl.back(), None);
462 ///
463 /// dl.push_back(1);
464 /// assert_eq!(dl.back(), Some(&1));
465 ///
466 /// ```
1a4d82fc 467 #[inline]
85aaf69f 468 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 469 pub fn back(&self) -> Option<&T> {
92a42be0 470 unsafe { self.list_tail.resolve().map(|tail| &tail.value) }
1a4d82fc
JJ
471 }
472
473 /// Provides a mutable reference to the back element, or `None` if the list
474 /// is empty.
85aaf69f
SL
475 ///
476 /// # Examples
477 ///
478 /// ```
479 /// use std::collections::LinkedList;
480 ///
481 /// let mut dl = LinkedList::new();
482 /// assert_eq!(dl.back(), None);
483 ///
484 /// dl.push_back(1);
485 /// assert_eq!(dl.back(), Some(&1));
486 ///
487 /// match dl.back_mut() {
488 /// None => {},
489 /// Some(x) => *x = 5,
490 /// }
491 /// assert_eq!(dl.back(), Some(&5));
492 ///
493 /// ```
1a4d82fc 494 #[inline]
85aaf69f 495 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 496 pub fn back_mut(&mut self) -> Option<&mut T> {
92a42be0 497 unsafe { self.list_tail.resolve_mut().map(|tail| &mut tail.value) }
1a4d82fc
JJ
498 }
499
500 /// Adds an element first in the list.
501 ///
502 /// This operation should compute in O(1) time.
85aaf69f
SL
503 ///
504 /// # Examples
505 ///
506 /// ```
507 /// use std::collections::LinkedList;
508 ///
509 /// let mut dl = LinkedList::new();
510 ///
511 /// dl.push_front(2);
512 /// assert_eq!(dl.front().unwrap(), &2);
513 ///
514 /// dl.push_front(1);
515 /// assert_eq!(dl.front().unwrap(), &1);
516 ///
517 /// ```
518 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
519 pub fn push_front(&mut self, elt: T) {
520 self.push_front_node(box Node::new(elt))
521 }
522
523 /// Removes the first element and returns it, or `None` if the list is
524 /// empty.
525 ///
526 /// This operation should compute in O(1) time.
85aaf69f
SL
527 ///
528 /// # Examples
529 ///
530 /// ```
531 /// use std::collections::LinkedList;
532 ///
533 /// let mut d = LinkedList::new();
534 /// assert_eq!(d.pop_front(), None);
535 ///
536 /// d.push_front(1);
537 /// d.push_front(3);
538 /// assert_eq!(d.pop_front(), Some(3));
539 /// assert_eq!(d.pop_front(), Some(1));
540 /// assert_eq!(d.pop_front(), None);
541 ///
542 /// ```
543 ///
544 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 545 pub fn pop_front(&mut self) -> Option<T> {
92a42be0 546 self.pop_front_node().map(|box Node { value, .. }| value)
1a4d82fc
JJ
547 }
548
549 /// Appends an element to the back of a list
550 ///
551 /// # Examples
552 ///
85aaf69f
SL
553 /// ```
554 /// use std::collections::LinkedList;
1a4d82fc 555 ///
85aaf69f
SL
556 /// let mut d = LinkedList::new();
557 /// d.push_back(1);
1a4d82fc
JJ
558 /// d.push_back(3);
559 /// assert_eq!(3, *d.back().unwrap());
560 /// ```
85aaf69f 561 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
562 pub fn push_back(&mut self, elt: T) {
563 self.push_back_node(box Node::new(elt))
564 }
565
566 /// Removes the last element from a list and returns it, or `None` if
567 /// it is empty.
568 ///
569 /// # Examples
570 ///
85aaf69f
SL
571 /// ```
572 /// use std::collections::LinkedList;
1a4d82fc 573 ///
85aaf69f 574 /// let mut d = LinkedList::new();
1a4d82fc 575 /// assert_eq!(d.pop_back(), None);
85aaf69f 576 /// d.push_back(1);
1a4d82fc
JJ
577 /// d.push_back(3);
578 /// assert_eq!(d.pop_back(), Some(3));
579 /// ```
85aaf69f 580 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 581 pub fn pop_back(&mut self) -> Option<T> {
92a42be0 582 self.pop_back_node().map(|box Node { value, .. }| value)
1a4d82fc 583 }
85aaf69f
SL
584
585 /// Splits the list into two at the given index. Returns everything after the given index,
586 /// including the index.
587 ///
588 /// # Panics
589 ///
590 /// Panics if `at > len`.
591 ///
592 /// This operation should compute in O(n) time.
593 ///
594 /// # Examples
595 ///
596 /// ```
597 /// use std::collections::LinkedList;
598 ///
599 /// let mut d = LinkedList::new();
600 ///
601 /// d.push_front(1);
602 /// d.push_front(2);
603 /// d.push_front(3);
604 ///
605 /// let mut splitted = d.split_off(2);
606 ///
607 /// assert_eq!(splitted.pop_front(), Some(1));
608 /// assert_eq!(splitted.pop_front(), None);
609 /// ```
610 #[stable(feature = "rust1", since = "1.0.0")]
611 pub fn split_off(&mut self, at: usize) -> LinkedList<T> {
612 let len = self.len();
613 assert!(at <= len, "Cannot split off at a nonexistent index");
614 if at == 0 {
615 return mem::replace(self, LinkedList::new());
616 } else if at == len {
617 return LinkedList::new();
618 }
619
620 // Below, we iterate towards the `i-1`th node, either from the start or the end,
621 // depending on which would be faster.
622 let mut split_node = if at - 1 <= len - 1 - (at - 1) {
623 let mut iter = self.iter_mut();
624 // instead of skipping using .skip() (which creates a new struct),
625 // we skip manually so we can access the head field without
626 // depending on implementation details of Skip
627 for _ in 0..at - 1 {
628 iter.next();
629 }
630 iter.head
92a42be0 631 } else {
85aaf69f
SL
632 // better off starting from the end
633 let mut iter = self.iter_mut();
634 for _ in 0..len - 1 - (at - 1) {
635 iter.next_back();
636 }
637 iter.tail
638 };
639
62682a34
SL
640 // The split node is the new tail node of the first part and owns
641 // the head of the second part.
642 let mut second_part_head;
643
644 unsafe {
645 second_part_head = split_node.resolve_mut().unwrap().next.take();
646 match second_part_head {
647 None => {}
648 Some(ref mut head) => head.prev = Rawlink::none(),
649 }
650 }
651
652 let second_part = LinkedList {
653 list_head: second_part_head,
85aaf69f 654 list_tail: self.list_tail,
92a42be0 655 length: len - at,
85aaf69f
SL
656 };
657
62682a34 658 // Fix the tail ptr of the first part
85aaf69f
SL
659 self.list_tail = split_node;
660 self.length = at;
661
62682a34 662 second_part
85aaf69f 663 }
7453a54e
SL
664
665 /// Returns a place for insertion at the front of the list.
666 ///
667 /// Using this method with placement syntax is equivalent to [`push_front`]
668 /// (#method.push_front), but may be more efficient.
669 ///
670 /// # Examples
671 ///
672 /// ```
673 /// #![feature(collection_placement)]
674 /// #![feature(placement_in_syntax)]
675 ///
676 /// use std::collections::LinkedList;
677 ///
678 /// let mut list = LinkedList::new();
679 /// list.front_place() <- 2;
680 /// list.front_place() <- 4;
681 /// assert!(list.iter().eq(&[4, 2]));
682 /// ```
683 #[unstable(feature = "collection_placement",
684 reason = "method name and placement protocol are subject to change",
685 issue = "30172")]
686 pub fn front_place(&mut self) -> FrontPlace<T> {
687 FrontPlace { list: self, node: IntermediateBox::make_place() }
688 }
689
690 /// Returns a place for insertion at the back of the list.
691 ///
692 /// Using this method with placement syntax is equivalent to [`push_back`](#method.push_back),
693 /// but may be more efficient.
694 ///
695 /// # Examples
696 ///
697 /// ```
698 /// #![feature(collection_placement)]
699 /// #![feature(placement_in_syntax)]
700 ///
701 /// use std::collections::LinkedList;
702 ///
703 /// let mut list = LinkedList::new();
704 /// list.back_place() <- 2;
705 /// list.back_place() <- 4;
706 /// assert!(list.iter().eq(&[2, 4]));
707 /// ```
708 #[unstable(feature = "collection_placement",
709 reason = "method name and placement protocol are subject to change",
710 issue = "30172")]
711 pub fn back_place(&mut self) -> BackPlace<T> {
712 BackPlace { list: self, node: IntermediateBox::make_place() }
713 }
1a4d82fc
JJ
714}
715
85aaf69f
SL
716#[stable(feature = "rust1", since = "1.0.0")]
717impl<T> Drop for LinkedList<T> {
b039eaaf 718 #[unsafe_destructor_blind_to_params]
1a4d82fc 719 fn drop(&mut self) {
62682a34 720 // Dissolve the linked_list in a loop.
1a4d82fc
JJ
721 // Just dropping the list_head can lead to stack exhaustion
722 // when length is >> 1_000_000
62682a34
SL
723 while let Some(mut head_) = self.list_head.take() {
724 self.list_head = head_.next.take();
1a4d82fc
JJ
725 }
726 self.length = 0;
1a4d82fc
JJ
727 self.list_tail = Rawlink::none();
728 }
729}
730
85aaf69f 731#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
732impl<'a, A> Iterator for Iter<'a, A> {
733 type Item = &'a A;
734
735 #[inline]
736 fn next(&mut self) -> Option<&'a A> {
737 if self.nelem == 0 {
738 return None;
739 }
740 self.head.as_ref().map(|head| {
741 self.nelem -= 1;
742 self.head = &head.next;
743 &head.value
744 })
745 }
746
747 #[inline]
85aaf69f 748 fn size_hint(&self) -> (usize, Option<usize>) {
1a4d82fc
JJ
749 (self.nelem, Some(self.nelem))
750 }
751}
752
85aaf69f 753#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
754impl<'a, A> DoubleEndedIterator for Iter<'a, A> {
755 #[inline]
756 fn next_back(&mut self) -> Option<&'a A> {
757 if self.nelem == 0 {
758 return None;
759 }
62682a34
SL
760 unsafe {
761 self.tail.resolve().map(|prev| {
762 self.nelem -= 1;
763 self.tail = prev.prev;
764 &prev.value
765 })
766 }
1a4d82fc
JJ
767 }
768}
769
85aaf69f 770#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
771impl<'a, A> ExactSizeIterator for Iter<'a, A> {}
772
85aaf69f 773#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
774impl<'a, A> Iterator for IterMut<'a, A> {
775 type Item = &'a mut A;
776 #[inline]
777 fn next(&mut self) -> Option<&'a mut A> {
778 if self.nelem == 0 {
779 return None;
780 }
62682a34
SL
781 unsafe {
782 self.head.resolve_mut().map(|next| {
783 self.nelem -= 1;
784 self.head = Rawlink::from(&mut next.next);
785 &mut next.value
786 })
787 }
1a4d82fc
JJ
788 }
789
790 #[inline]
85aaf69f 791 fn size_hint(&self) -> (usize, Option<usize>) {
1a4d82fc
JJ
792 (self.nelem, Some(self.nelem))
793 }
794}
795
85aaf69f 796#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
797impl<'a, A> DoubleEndedIterator for IterMut<'a, A> {
798 #[inline]
799 fn next_back(&mut self) -> Option<&'a mut A> {
800 if self.nelem == 0 {
801 return None;
802 }
62682a34
SL
803 unsafe {
804 self.tail.resolve_mut().map(|prev| {
805 self.nelem -= 1;
806 self.tail = prev.prev;
807 &mut prev.value
808 })
809 }
1a4d82fc
JJ
810 }
811}
812
85aaf69f 813#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
814impl<'a, A> ExactSizeIterator for IterMut<'a, A> {}
815
816// private methods for IterMut
817impl<'a, A> IterMut<'a, A> {
818 fn insert_next_node(&mut self, mut ins_node: Box<Node<A>>) {
819 // Insert before `self.head` so that it is between the
820 // previously yielded element and self.head.
821 //
822 // The inserted node will not appear in further iteration.
62682a34 823 match unsafe { self.head.resolve_mut() } {
92a42be0
SL
824 None => {
825 self.list.push_back_node(ins_node);
826 }
1a4d82fc 827 Some(node) => {
62682a34 828 let prev_node = match unsafe { node.prev.resolve_mut() } {
1a4d82fc
JJ
829 None => return self.list.push_front_node(ins_node),
830 Some(prev) => prev,
831 };
832 let node_own = prev_node.next.take().unwrap();
62682a34
SL
833 ins_node.set_next(node_own);
834 prev_node.set_next(ins_node);
1a4d82fc
JJ
835 self.list.length += 1;
836 }
837 }
838 }
839}
840
841impl<'a, A> IterMut<'a, A> {
842 /// Inserts `elt` just after the element most recently returned by `.next()`.
843 /// The inserted element does not appear in the iteration.
844 ///
845 /// # Examples
846 ///
85aaf69f 847 /// ```
c1a9b12d
SL
848 /// #![feature(linked_list_extras)]
849 ///
85aaf69f 850 /// use std::collections::LinkedList;
1a4d82fc 851 ///
85aaf69f 852 /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
1a4d82fc
JJ
853 ///
854 /// {
855 /// let mut it = list.iter_mut();
856 /// assert_eq!(it.next().unwrap(), &1);
857 /// // insert `2` after `1`
858 /// it.insert_next(2);
859 /// }
860 /// {
85aaf69f 861 /// let vec: Vec<_> = list.into_iter().collect();
c34b1796 862 /// assert_eq!(vec, [1, 2, 3, 4]);
1a4d82fc
JJ
863 /// }
864 /// ```
865 #[inline]
62682a34 866 #[unstable(feature = "linked_list_extras",
e9174d1e
SL
867 reason = "this is probably better handled by a cursor type -- we'll see",
868 issue = "27794")]
1a4d82fc
JJ
869 pub fn insert_next(&mut self, elt: A) {
870 self.insert_next_node(box Node::new(elt))
871 }
872
873 /// Provides a reference to the next element, without changing the iterator.
874 ///
875 /// # Examples
876 ///
85aaf69f 877 /// ```
c1a9b12d
SL
878 /// #![feature(linked_list_extras)]
879 ///
85aaf69f 880 /// use std::collections::LinkedList;
1a4d82fc 881 ///
85aaf69f 882 /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
1a4d82fc
JJ
883 ///
884 /// let mut it = list.iter_mut();
885 /// assert_eq!(it.next().unwrap(), &1);
886 /// assert_eq!(it.peek_next().unwrap(), &2);
887 /// // We just peeked at 2, so it was not consumed from the iterator.
888 /// assert_eq!(it.next().unwrap(), &2);
889 /// ```
890 #[inline]
62682a34 891 #[unstable(feature = "linked_list_extras",
e9174d1e
SL
892 reason = "this is probably better handled by a cursor type -- we'll see",
893 issue = "27794")]
1a4d82fc
JJ
894 pub fn peek_next(&mut self) -> Option<&mut A> {
895 if self.nelem == 0 {
92a42be0 896 return None;
62682a34 897 }
92a42be0 898 unsafe { self.head.resolve_mut().map(|head| &mut head.value) }
1a4d82fc
JJ
899 }
900}
901
85aaf69f 902#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
903impl<A> Iterator for IntoIter<A> {
904 type Item = A;
905
906 #[inline]
92a42be0
SL
907 fn next(&mut self) -> Option<A> {
908 self.list.pop_front()
909 }
1a4d82fc
JJ
910
911 #[inline]
85aaf69f 912 fn size_hint(&self) -> (usize, Option<usize>) {
1a4d82fc
JJ
913 (self.list.length, Some(self.list.length))
914 }
915}
916
85aaf69f 917#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
918impl<A> DoubleEndedIterator for IntoIter<A> {
919 #[inline]
92a42be0
SL
920 fn next_back(&mut self) -> Option<A> {
921 self.list.pop_back()
922 }
1a4d82fc
JJ
923}
924
92a42be0 925#[stable(feature = "rust1", since = "1.0.0")]
c34b1796
AL
926impl<A> ExactSizeIterator for IntoIter<A> {}
927
85aaf69f
SL
928#[stable(feature = "rust1", since = "1.0.0")]
929impl<A> FromIterator<A> for LinkedList<A> {
92a42be0 930 fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> LinkedList<A> {
c34b1796 931 let mut ret = LinkedList::new();
85aaf69f 932 ret.extend(iter);
1a4d82fc
JJ
933 ret
934 }
935}
936
85aaf69f
SL
937#[stable(feature = "rust1", since = "1.0.0")]
938impl<T> IntoIterator for LinkedList<T> {
939 type Item = T;
940 type IntoIter = IntoIter<T>;
941
9346a6ac
AL
942 /// Consumes the list into an iterator yielding elements by value.
943 #[inline]
85aaf69f 944 fn into_iter(self) -> IntoIter<T> {
92a42be0 945 IntoIter { list: self }
85aaf69f
SL
946 }
947}
948
949#[stable(feature = "rust1", since = "1.0.0")]
950impl<'a, T> IntoIterator for &'a LinkedList<T> {
951 type Item = &'a T;
952 type IntoIter = Iter<'a, T>;
953
954 fn into_iter(self) -> Iter<'a, T> {
955 self.iter()
956 }
957}
958
92a42be0 959#[stable(feature = "rust1", since = "1.0.0")]
85aaf69f
SL
960impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
961 type Item = &'a mut T;
962 type IntoIter = IterMut<'a, T>;
963
964 fn into_iter(mut self) -> IterMut<'a, T> {
965 self.iter_mut()
1a4d82fc
JJ
966 }
967}
968
85aaf69f
SL
969#[stable(feature = "rust1", since = "1.0.0")]
970impl<A> Extend<A> for LinkedList<A> {
92a42be0
SL
971 fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
972 for elt in iter {
973 self.push_back(elt);
974 }
85aaf69f
SL
975 }
976}
977
62682a34
SL
978#[stable(feature = "extend_ref", since = "1.2.0")]
979impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> {
92a42be0 980 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
62682a34
SL
981 self.extend(iter.into_iter().cloned());
982 }
983}
984
85aaf69f
SL
985#[stable(feature = "rust1", since = "1.0.0")]
986impl<A: PartialEq> PartialEq for LinkedList<A> {
987 fn eq(&self, other: &LinkedList<A>) -> bool {
92a42be0 988 self.len() == other.len() && self.iter().eq(other.iter())
1a4d82fc
JJ
989 }
990
85aaf69f 991 fn ne(&self, other: &LinkedList<A>) -> bool {
92a42be0 992 self.len() != other.len() || self.iter().ne(other.iter())
1a4d82fc
JJ
993 }
994}
995
85aaf69f
SL
996#[stable(feature = "rust1", since = "1.0.0")]
997impl<A: Eq> Eq for LinkedList<A> {}
1a4d82fc 998
85aaf69f
SL
999#[stable(feature = "rust1", since = "1.0.0")]
1000impl<A: PartialOrd> PartialOrd for LinkedList<A> {
1001 fn partial_cmp(&self, other: &LinkedList<A>) -> Option<Ordering> {
e9174d1e 1002 self.iter().partial_cmp(other.iter())
1a4d82fc
JJ
1003 }
1004}
1005
85aaf69f
SL
1006#[stable(feature = "rust1", since = "1.0.0")]
1007impl<A: Ord> Ord for LinkedList<A> {
1a4d82fc 1008 #[inline]
85aaf69f 1009 fn cmp(&self, other: &LinkedList<A>) -> Ordering {
e9174d1e 1010 self.iter().cmp(other.iter())
1a4d82fc
JJ
1011 }
1012}
1013
85aaf69f
SL
1014#[stable(feature = "rust1", since = "1.0.0")]
1015impl<A: Clone> Clone for LinkedList<A> {
1016 fn clone(&self) -> LinkedList<A> {
1017 self.iter().cloned().collect()
1a4d82fc
JJ
1018 }
1019}
1020
85aaf69f
SL
1021#[stable(feature = "rust1", since = "1.0.0")]
1022impl<A: fmt::Debug> fmt::Debug for LinkedList<A> {
1a4d82fc 1023 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
62682a34 1024 f.debug_list().entries(self.iter()).finish()
1a4d82fc
JJ
1025 }
1026}
1027
85aaf69f 1028#[stable(feature = "rust1", since = "1.0.0")]
85aaf69f
SL
1029impl<A: Hash> Hash for LinkedList<A> {
1030 fn hash<H: Hasher>(&self, state: &mut H) {
1031 self.len().hash(state);
1032 for elt in self {
1a4d82fc
JJ
1033 elt.hash(state);
1034 }
1035 }
1036}
1037
7453a54e
SL
1038unsafe fn finalize<T>(node: IntermediateBox<Node<T>>) -> Box<Node<T>> {
1039 let mut node = node.finalize();
1040 ptr::write(&mut node.next, None);
1041 ptr::write(&mut node.prev, Rawlink::none());
1042 node
1043}
1044
1045/// A place for insertion at the front of a `LinkedList`.
1046///
1047/// See [`LinkedList::front_place`](struct.LinkedList.html#method.front_place) for details.
1048#[must_use = "places do nothing unless written to with `<-` syntax"]
1049#[unstable(feature = "collection_placement",
1050 reason = "struct name and placement protocol are subject to change",
1051 issue = "30172")]
1052pub struct FrontPlace<'a, T: 'a> {
1053 list: &'a mut LinkedList<T>,
1054 node: IntermediateBox<Node<T>>,
1055}
1056
1057#[unstable(feature = "collection_placement",
1058 reason = "placement protocol is subject to change",
1059 issue = "30172")]
1060impl<'a, T> Placer<T> for FrontPlace<'a, T> {
1061 type Place = Self;
1062
1063 fn make_place(self) -> Self {
1064 self
1065 }
1066}
1067
1068#[unstable(feature = "collection_placement",
1069 reason = "placement protocol is subject to change",
1070 issue = "30172")]
1071impl<'a, T> Place<T> for FrontPlace<'a, T> {
1072 fn pointer(&mut self) -> *mut T {
1073 unsafe { &mut (*self.node.pointer()).value }
1074 }
1075}
1076
1077#[unstable(feature = "collection_placement",
1078 reason = "placement protocol is subject to change",
1079 issue = "30172")]
1080impl<'a, T> InPlace<T> for FrontPlace<'a, T> {
1081 type Owner = ();
1082
1083 unsafe fn finalize(self) {
1084 let FrontPlace { list, node } = self;
1085 list.push_front_node(finalize(node));
1086 }
1087}
1088
1089/// A place for insertion at the back of a `LinkedList`.
1090///
1091/// See [`LinkedList::back_place`](struct.LinkedList.html#method.back_place) for details.
1092#[must_use = "places do nothing unless written to with `<-` syntax"]
1093#[unstable(feature = "collection_placement",
1094 reason = "struct name and placement protocol are subject to change",
1095 issue = "30172")]
1096pub struct BackPlace<'a, T: 'a> {
1097 list: &'a mut LinkedList<T>,
1098 node: IntermediateBox<Node<T>>,
1099}
1100
1101#[unstable(feature = "collection_placement",
1102 reason = "placement protocol is subject to change",
1103 issue = "30172")]
1104impl<'a, T> Placer<T> for BackPlace<'a, T> {
1105 type Place = Self;
1106
1107 fn make_place(self) -> Self {
1108 self
1109 }
1110}
1111
1112#[unstable(feature = "collection_placement",
1113 reason = "placement protocol is subject to change",
1114 issue = "30172")]
1115impl<'a, T> Place<T> for BackPlace<'a, T> {
1116 fn pointer(&mut self) -> *mut T {
1117 unsafe { &mut (*self.node.pointer()).value }
1118 }
1119}
1120
1121#[unstable(feature = "collection_placement",
1122 reason = "placement protocol is subject to change",
1123 issue = "30172")]
1124impl<'a, T> InPlace<T> for BackPlace<'a, T> {
1125 type Owner = ();
1126
1127 unsafe fn finalize(self) {
1128 let BackPlace { list, node } = self;
1129 list.push_back_node(finalize(node));
1130 }
1131}
1132
9cc50fc6
SL
1133// Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
1134#[allow(dead_code)]
1135fn assert_covariance() {
1136 fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> { x }
1137 fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> { x }
1138 fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> { x }
1139}
1140
1a4d82fc 1141#[cfg(test)]
d9579d0f 1142mod tests {
c34b1796 1143 use std::clone::Clone;
62682a34 1144 use std::iter::{Iterator, IntoIterator, Extend};
92a42be0 1145 use std::option::Option::{self, Some, None};
9346a6ac 1146 use std::__rand::{thread_rng, Rng};
85aaf69f 1147 use std::thread;
c34b1796 1148 use std::vec::Vec;
1a4d82fc 1149
85aaf69f 1150 use super::{LinkedList, Node};
1a4d82fc 1151
c34b1796
AL
1152 #[cfg(test)]
1153 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
1154 v.iter().cloned().collect()
1155 }
1156
85aaf69f
SL
1157 pub fn check_links<T>(list: &LinkedList<T>) {
1158 let mut len = 0;
1a4d82fc
JJ
1159 let mut last_ptr: Option<&Node<T>> = None;
1160 let mut node_ptr: &Node<T>;
1161 match list.list_head {
92a42be0
SL
1162 None => {
1163 assert_eq!(0, list.length);
1164 return;
1165 }
1a4d82fc
JJ
1166 Some(ref node) => node_ptr = &**node,
1167 }
1168 loop {
62682a34 1169 match unsafe { (last_ptr, node_ptr.prev.resolve()) } {
92a42be0
SL
1170 (None, None) => {}
1171 (None, _) => panic!("prev link for list_head"),
1a4d82fc
JJ
1172 (Some(p), Some(pptr)) => {
1173 assert_eq!(p as *const Node<T>, pptr as *const Node<T>);
1174 }
1175 _ => panic!("prev link is none, not good"),
1176 }
1177 match node_ptr.next {
1178 Some(ref next) => {
1179 last_ptr = Some(node_ptr);
1180 node_ptr = &**next;
1181 len += 1;
1182 }
1183 None => {
1184 len += 1;
1185 break;
1186 }
1187 }
1188 }
1189 assert_eq!(len, list.length);
1190 }
1191
85aaf69f
SL
1192 #[test]
1193 fn test_append() {
1194 // Empty to empty
1195 {
1196 let mut m = LinkedList::<i32>::new();
1197 let mut n = LinkedList::new();
1198 m.append(&mut n);
1199 check_links(&m);
1200 assert_eq!(m.len(), 0);
1201 assert_eq!(n.len(), 0);
1202 }
1203 // Non-empty to empty
1204 {
1205 let mut m = LinkedList::new();
1206 let mut n = LinkedList::new();
1207 n.push_back(2);
1208 m.append(&mut n);
1209 check_links(&m);
1210 assert_eq!(m.len(), 1);
1211 assert_eq!(m.pop_back(), Some(2));
1212 assert_eq!(n.len(), 0);
1213 check_links(&m);
1214 }
1215 // Empty to non-empty
1216 {
1217 let mut m = LinkedList::new();
1218 let mut n = LinkedList::new();
1219 m.push_back(2);
1220 m.append(&mut n);
1221 check_links(&m);
1222 assert_eq!(m.len(), 1);
1223 assert_eq!(m.pop_back(), Some(2));
1224 check_links(&m);
1225 }
1226
1227 // Non-empty to non-empty
92a42be0
SL
1228 let v = vec![1, 2, 3, 4, 5];
1229 let u = vec![9, 8, 1, 2, 3, 4, 5];
85aaf69f
SL
1230 let mut m = list_from(&v);
1231 let mut n = list_from(&u);
1232 m.append(&mut n);
1233 check_links(&m);
1234 let mut sum = v;
54a0048b 1235 sum.extend_from_slice(&u);
85aaf69f
SL
1236 assert_eq!(sum.len(), m.len());
1237 for elt in sum {
1238 assert_eq!(m.pop_front(), Some(elt))
1239 }
1240 assert_eq!(n.len(), 0);
1241 // let's make sure it's working properly, since we
1242 // did some direct changes to private members
1243 n.push_back(3);
1244 assert_eq!(n.len(), 1);
1245 assert_eq!(n.pop_front(), Some(3));
1246 check_links(&n);
1247 }
1248
1a4d82fc
JJ
1249 #[test]
1250 fn test_insert_prev() {
92a42be0 1251 let mut m = list_from(&[0, 2, 4, 6, 8]);
1a4d82fc
JJ
1252 let len = m.len();
1253 {
1254 let mut it = m.iter_mut();
1255 it.insert_next(-2);
1256 loop {
1257 match it.next() {
1258 None => break,
1259 Some(elt) => {
1260 it.insert_next(*elt + 1);
1261 match it.peek_next() {
1262 Some(x) => assert_eq!(*x, *elt + 2),
1263 None => assert_eq!(8, *elt),
1264 }
1265 }
1266 }
1267 }
1268 it.insert_next(0);
1269 it.insert_next(1);
1270 }
1271 check_links(&m);
1272 assert_eq!(m.len(), 3 + len * 2);
92a42be0
SL
1273 assert_eq!(m.into_iter().collect::<Vec<_>>(),
1274 [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]);
1a4d82fc
JJ
1275 }
1276
1277 #[test]
1278 fn test_send() {
92a42be0 1279 let n = list_from(&[1, 2, 3]);
85aaf69f 1280 thread::spawn(move || {
1a4d82fc 1281 check_links(&n);
92a42be0 1282 let a: &[_] = &[&1, &2, &3];
c34b1796 1283 assert_eq!(a, &n.iter().collect::<Vec<_>>()[..]);
92a42be0
SL
1284 })
1285 .join()
1286 .ok()
1287 .unwrap();
1a4d82fc
JJ
1288 }
1289
1a4d82fc
JJ
1290 #[test]
1291 fn test_fuzz() {
85aaf69f 1292 for _ in 0..25 {
1a4d82fc
JJ
1293 fuzz_test(3);
1294 fuzz_test(16);
1295 fuzz_test(189);
1296 }
1297 }
1298
d9579d0f
AL
1299 #[test]
1300 fn test_26021() {
1301 use std::iter::ExactSizeIterator;
1302 // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
1303 // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
1304 // its nodes.
1305 //
1306 // https://github.com/rust-lang/rust/issues/26021
1307 let mut v1 = LinkedList::new();
54a0048b
SL
1308 v1.push_front(1);
1309 v1.push_front(1);
1310 v1.push_front(1);
1311 v1.push_front(1);
d9579d0f
AL
1312 let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
1313 assert_eq!(v1.len(), 3);
1314
1315 assert_eq!(v1.iter().len(), 3);
1316 assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
1317 }
1318
62682a34
SL
1319 #[test]
1320 fn test_split_off() {
1321 let mut v1 = LinkedList::new();
54a0048b
SL
1322 v1.push_front(1);
1323 v1.push_front(1);
1324 v1.push_front(1);
1325 v1.push_front(1);
62682a34
SL
1326
1327 // test all splits
1328 for ix in 0..1 + v1.len() {
1329 let mut a = v1.clone();
1330 let b = a.split_off(ix);
1331 check_links(&a);
1332 check_links(&b);
1333 a.extend(b);
1334 assert_eq!(v1, a);
1335 }
1336 }
1337
1338
1a4d82fc 1339 #[cfg(test)]
85aaf69f
SL
1340 fn fuzz_test(sz: i32) {
1341 let mut m: LinkedList<_> = LinkedList::new();
1a4d82fc 1342 let mut v = vec![];
85aaf69f 1343 for i in 0..sz {
1a4d82fc 1344 check_links(&m);
9346a6ac 1345 let r: u8 = thread_rng().next_u32() as u8;
1a4d82fc
JJ
1346 match r % 6 {
1347 0 => {
1348 m.pop_back();
1349 v.pop();
1350 }
1351 1 => {
1352 if !v.is_empty() {
1353 m.pop_front();
1354 v.remove(0);
1355 }
1356 }
92a42be0 1357 2 | 4 => {
1a4d82fc
JJ
1358 m.push_front(-i);
1359 v.insert(0, -i);
1360 }
1361 3 | 5 | _ => {
1362 m.push_back(i);
1363 v.push(i);
1364 }
1365 }
1366 }
1367
1368 check_links(&m);
1369
85aaf69f 1370 let mut i = 0;
62682a34 1371 for (a, &b) in m.into_iter().zip(&v) {
1a4d82fc
JJ
1372 i += 1;
1373 assert_eq!(a, b);
1374 }
1375 assert_eq!(i, v.len());
1376 }
1a4d82fc 1377}