src/liballoc/linked_list.rs

   1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
   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 //!
  13 //! The `LinkedList` allows pushing and popping elements at either end
  14 //! in constant time.
  15 //!
  16 //! Almost always it is better to use `Vec` or [`VecDeque`] instead of
  17 //! [`LinkedList`]. In general, array-based containers are faster,
  18 //! more memory efficient and make better use of CPU cache.
  19 //!
  20 //! [`LinkedList`]: ../linked_list/struct.LinkedList.html
  21 //! [`VecDeque`]: ../vec_deque/struct.VecDeque.html
  22
  23 #![stable(feature = "rust1", since = "1.0.0")]
  24
  25 use core::cmp::Ordering;
  26 use core::fmt;
  27 use core::hash::{Hasher, Hash};
  28 use core::iter::{FromIterator, FusedIterator};
  29 use core::marker::PhantomData;
  30 use core::mem;
  31 use core::ops::{BoxPlace, InPlace, Place, Placer};
  32 use core::ptr::{self, NonNull};
  33
  34 use boxed::{Box, IntermediateBox};
  35 use super::SpecExtend;
  36
  37 /// A doubly-linked list with owned nodes.
  38 ///
  39 /// The `LinkedList` allows pushing and popping elements at either end
  40 /// in constant time.
  41 ///
  42 /// Almost always it is better to use `Vec` or `VecDeque` instead of
  43 /// `LinkedList`. In general, array-based containers are faster,
  44 /// more memory efficient and make better use of CPU cache.
  45 #[stable(feature = "rust1", since = "1.0.0")]
  46 pub struct LinkedList<T> {
  47     head: Option<NonNull<Node<T>>>,
  48     tail: Option<NonNull<Node<T>>>,
  49     len: usize,
  50     marker: PhantomData<Box<Node<T>>>,
  51 }
  52
  53 struct Node<T> {
  54     next: Option<NonNull<Node<T>>>,
  55     prev: Option<NonNull<Node<T>>>,
  56     element: T,
  57 }
  58
  59 /// An iterator over the elements of a `LinkedList`.
  60 ///
  61 /// This `struct` is created by the [`iter`] method on [`LinkedList`]. See its
  62 /// documentation for more.
  63 ///
  64 /// [`iter`]: struct.LinkedList.html#method.iter
  65 /// [`LinkedList`]: struct.LinkedList.html
  66 #[stable(feature = "rust1", since = "1.0.0")]
  67 pub struct Iter<'a, T: 'a> {
  68     head: Option<NonNull<Node<T>>>,
  69     tail: Option<NonNull<Node<T>>>,
  70     len: usize,
  71     marker: PhantomData<&'a Node<T>>,
  72 }
  73
  74 #[stable(feature = "collection_debug", since = "1.17.0")]
  75 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> {
  76     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  77         f.debug_tuple("Iter")
  78          .field(&self.len)
  79          .finish()
  80     }
  81 }
  82
  83 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
  84 #[stable(feature = "rust1", since = "1.0.0")]
  85 impl<'a, T> Clone for Iter<'a, T> {
  86     fn clone(&self) -> Self {
  87         Iter { ..*self }
  88     }
  89 }
  90
  91 /// A mutable iterator over the elements of a `LinkedList`.
  92 ///
  93 /// This `struct` is created by the [`iter_mut`] method on [`LinkedList`]. See its
  94 /// documentation for more.
  95 ///
  96 /// [`iter_mut`]: struct.LinkedList.html#method.iter_mut
  97 /// [`LinkedList`]: struct.LinkedList.html
  98 #[stable(feature = "rust1", since = "1.0.0")]
  99 pub struct IterMut<'a, T: 'a> {
 100     list: &'a mut LinkedList<T>,
 101     head: Option<NonNull<Node<T>>>,
 102     tail: Option<NonNull<Node<T>>>,
 103     len: usize,
 104 }
 105
 106 #[stable(feature = "collection_debug", since = "1.17.0")]
 107 impl<'a, T: 'a + fmt::Debug> fmt::Debug for IterMut<'a, T> {
 108     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 109         f.debug_tuple("IterMut")
 110          .field(&self.list)
 111          .field(&self.len)
 112          .finish()
 113     }
 114 }
 115
 116 /// An owning iterator over the elements of a `LinkedList`.
 117 ///
 118 /// This `struct` is created by the [`into_iter`] method on [`LinkedList`][`LinkedList`]
 119 /// (provided by the `IntoIterator` trait). See its documentation for more.
 120 ///
 121 /// [`into_iter`]: struct.LinkedList.html#method.into_iter
 122 /// [`LinkedList`]: struct.LinkedList.html
 123 #[derive(Clone)]
 124 #[stable(feature = "rust1", since = "1.0.0")]
 125 pub struct IntoIter<T> {
 126     list: LinkedList<T>,
 127 }
 128
 129 #[stable(feature = "collection_debug", since = "1.17.0")]
 130 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
 131     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 132         f.debug_tuple("IntoIter")
 133          .field(&self.list)
 134          .finish()
 135     }
 136 }
 137
 138 impl<T> Node<T> {
 139     fn new(element: T) -> Self {
 140         Node {
 141             next: None,
 142             prev: None,
 143             element,
 144         }
 145     }
 146
 147     fn into_element(self: Box<Self>) -> T {
 148         self.element
 149     }
 150 }
 151
 152 // private methods
 153 impl<T> LinkedList<T> {
 154     /// Adds the given node to the front of the list.
 155     #[inline]
 156     fn push_front_node(&mut self, mut node: Box<Node<T>>) {
 157         unsafe {
 158             node.next = self.head;
 159             node.prev = None;
 160             let node = Some(Box::into_raw_non_null(node));
 161
 162             match self.head {
 163                 None => self.tail = node,
 164                 Some(mut head) => head.as_mut().prev = node,
 165             }
 166
 167             self.head = node;
 168             self.len += 1;
 169         }
 170     }
 171
 172     /// Removes and returns the node at the front of the list.
 173     #[inline]
 174     fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
 175         self.head.map(|node| unsafe {
 176             let node = Box::from_raw(node.as_ptr());
 177             self.head = node.next;
 178
 179             match self.head {
 180                 None => self.tail = None,
 181                 Some(mut head) => head.as_mut().prev = None,
 182             }
 183
 184             self.len -= 1;
 185             node
 186         })
 187     }
 188
 189     /// Adds the given node to the back of the list.
 190     #[inline]
 191     fn push_back_node(&mut self, mut node: Box<Node<T>>) {
 192         unsafe {
 193             node.next = None;
 194             node.prev = self.tail;
 195             let node = Some(Box::into_raw_non_null(node));
 196
 197             match self.tail {
 198                 None => self.head = node,
 199                 Some(mut tail) => tail.as_mut().next = node,
 200             }
 201
 202             self.tail = node;
 203             self.len += 1;
 204         }
 205     }
 206
 207     /// Removes and returns the node at the back of the list.
 208     #[inline]
 209     fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
 210         self.tail.map(|node| unsafe {
 211             let node = Box::from_raw(node.as_ptr());
 212             self.tail = node.prev;
 213
 214             match self.tail {
 215                 None => self.head = None,
 216                 Some(mut tail) => tail.as_mut().next = None,
 217             }
 218
 219             self.len -= 1;
 220             node
 221         })
 222     }
 223
 224     /// Unlinks the specified node from the current list.
 225     ///
 226     /// Warning: this will not check that the provided node belongs to the current list.
 227     #[inline]
 228     unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
 229         let node = node.as_mut();
 230
 231         match node.prev {
 232             Some(mut prev) => prev.as_mut().next = node.next.clone(),
 233             // this node is the head node
 234             None => self.head = node.next.clone(),
 235         };
 236
 237         match node.next {
 238             Some(mut next) => next.as_mut().prev = node.prev.clone(),
 239             // this node is the tail node
 240             None => self.tail = node.prev.clone(),
 241         };
 242
 243         self.len -= 1;
 244     }
 245 }
 246
 247 #[stable(feature = "rust1", since = "1.0.0")]
 248 impl<T> Default for LinkedList<T> {
 249     /// Creates an empty `LinkedList<T>`.
 250     #[inline]
 251     fn default() -> Self {
 252         Self::new()
 253     }
 254 }
 255
 256 impl<T> LinkedList<T> {
 257     /// Creates an empty `LinkedList`.
 258     ///
 259     /// # Examples
 260     ///
 261     /// ```
 262     /// use std::collections::LinkedList;
 263     ///
 264     /// let list: LinkedList<u32> = LinkedList::new();
 265     /// ```
 266     #[inline]
 267     #[stable(feature = "rust1", since = "1.0.0")]
 268     pub fn new() -> Self {
 269         LinkedList {
 270             head: None,
 271             tail: None,
 272             len: 0,
 273             marker: PhantomData,
 274         }
 275     }
 276
 277     /// Moves all elements from `other` to the end of the list.
 278     ///
 279     /// This reuses all the nodes from `other` and moves them into `self`. After
 280     /// this operation, `other` becomes empty.
 281     ///
 282     /// This operation should compute in O(1) time and O(1) memory.
 283     ///
 284     /// # Examples
 285     ///
 286     /// ```
 287     /// use std::collections::LinkedList;
 288     ///
 289     /// let mut list1 = LinkedList::new();
 290     /// list1.push_back('a');
 291     ///
 292     /// let mut list2 = LinkedList::new();
 293     /// list2.push_back('b');
 294     /// list2.push_back('c');
 295     ///
 296     /// list1.append(&mut list2);
 297     ///
 298     /// let mut iter = list1.iter();
 299     /// assert_eq!(iter.next(), Some(&'a'));
 300     /// assert_eq!(iter.next(), Some(&'b'));
 301     /// assert_eq!(iter.next(), Some(&'c'));
 302     /// assert!(iter.next().is_none());
 303     ///
 304     /// assert!(list2.is_empty());
 305     /// ```
 306     #[stable(feature = "rust1", since = "1.0.0")]
 307     pub fn append(&mut self, other: &mut Self) {
 308         match self.tail {
 309             None => mem::swap(self, other),
 310             Some(mut tail) => {
 311                 if let Some(mut other_head) = other.head.take() {
 312                     unsafe {
 313                         tail.as_mut().next = Some(other_head);
 314                         other_head.as_mut().prev = Some(tail);
 315                     }
 316
 317                     self.tail = other.tail.take();
 318                     self.len += mem::replace(&mut other.len, 0);
 319                 }
 320             }
 321         }
 322     }
 323
 324     /// Provides a forward iterator.
 325     ///
 326     /// # Examples
 327     ///
 328     /// ```
 329     /// use std::collections::LinkedList;
 330     ///
 331     /// let mut list: LinkedList<u32> = LinkedList::new();
 332     ///
 333     /// list.push_back(0);
 334     /// list.push_back(1);
 335     /// list.push_back(2);
 336     ///
 337     /// let mut iter = list.iter();
 338     /// assert_eq!(iter.next(), Some(&0));
 339     /// assert_eq!(iter.next(), Some(&1));
 340     /// assert_eq!(iter.next(), Some(&2));
 341     /// assert_eq!(iter.next(), None);
 342     /// ```
 343     #[inline]
 344     #[stable(feature = "rust1", since = "1.0.0")]
 345     pub fn iter(&self) -> Iter<T> {
 346         Iter {
 347             head: self.head,
 348             tail: self.tail,
 349             len: self.len,
 350             marker: PhantomData,
 351         }
 352     }
 353
 354     /// Provides a forward iterator with mutable references.
 355     ///
 356     /// # Examples
 357     ///
 358     /// ```
 359     /// use std::collections::LinkedList;
 360     ///
 361     /// let mut list: LinkedList<u32> = LinkedList::new();
 362     ///
 363     /// list.push_back(0);
 364     /// list.push_back(1);
 365     /// list.push_back(2);
 366     ///
 367     /// for element in list.iter_mut() {
 368     ///     *element += 10;
 369     /// }
 370     ///
 371     /// let mut iter = list.iter();
 372     /// assert_eq!(iter.next(), Some(&10));
 373     /// assert_eq!(iter.next(), Some(&11));
 374     /// assert_eq!(iter.next(), Some(&12));
 375     /// assert_eq!(iter.next(), None);
 376     /// ```
 377     #[inline]
 378     #[stable(feature = "rust1", since = "1.0.0")]
 379     pub fn iter_mut(&mut self) -> IterMut<T> {
 380         IterMut {
 381             head: self.head,
 382             tail: self.tail,
 383             len: self.len,
 384             list: self,
 385         }
 386     }
 387
 388     /// Returns `true` if the `LinkedList` is empty.
 389     ///
 390     /// This operation should compute in O(1) time.
 391     ///
 392     /// # Examples
 393     ///
 394     /// ```
 395     /// use std::collections::LinkedList;
 396     ///
 397     /// let mut dl = LinkedList::new();
 398     /// assert!(dl.is_empty());
 399     ///
 400     /// dl.push_front("foo");
 401     /// assert!(!dl.is_empty());
 402     /// ```
 403     #[inline]
 404     #[stable(feature = "rust1", since = "1.0.0")]
 405     pub fn is_empty(&self) -> bool {
 406         self.head.is_none()
 407     }
 408
 409     /// Returns the length of the `LinkedList`.
 410     ///
 411     /// This operation should compute in O(1) time.
 412     ///
 413     /// # Examples
 414     ///
 415     /// ```
 416     /// use std::collections::LinkedList;
 417     ///
 418     /// let mut dl = LinkedList::new();
 419     ///
 420     /// dl.push_front(2);
 421     /// assert_eq!(dl.len(), 1);
 422     ///
 423     /// dl.push_front(1);
 424     /// assert_eq!(dl.len(), 2);
 425     ///
 426     /// dl.push_back(3);
 427     /// assert_eq!(dl.len(), 3);
 428     /// ```
 429     #[inline]
 430     #[stable(feature = "rust1", since = "1.0.0")]
 431     pub fn len(&self) -> usize {
 432         self.len
 433     }
 434
 435     /// Removes all elements from the `LinkedList`.
 436     ///
 437     /// This operation should compute in O(n) time.
 438     ///
 439     /// # Examples
 440     ///
 441     /// ```
 442     /// use std::collections::LinkedList;
 443     ///
 444     /// let mut dl = LinkedList::new();
 445     ///
 446     /// dl.push_front(2);
 447     /// dl.push_front(1);
 448     /// assert_eq!(dl.len(), 2);
 449     /// assert_eq!(dl.front(), Some(&1));
 450     ///
 451     /// dl.clear();
 452     /// assert_eq!(dl.len(), 0);
 453     /// assert_eq!(dl.front(), None);
 454     /// ```
 455     #[inline]
 456     #[stable(feature = "rust1", since = "1.0.0")]
 457     pub fn clear(&mut self) {
 458         *self = Self::new();
 459     }
 460
 461     /// Returns `true` if the `LinkedList` contains an element equal to the
 462     /// given value.
 463     ///
 464     /// # Examples
 465     ///
 466     /// ```
 467     /// use std::collections::LinkedList;
 468     ///
 469     /// let mut list: LinkedList<u32> = LinkedList::new();
 470     ///
 471     /// list.push_back(0);
 472     /// list.push_back(1);
 473     /// list.push_back(2);
 474     ///
 475     /// assert_eq!(list.contains(&0), true);
 476     /// assert_eq!(list.contains(&10), false);
 477     /// ```
 478     #[stable(feature = "linked_list_contains", since = "1.12.0")]
 479     pub fn contains(&self, x: &T) -> bool
 480         where T: PartialEq<T>
 481     {
 482         self.iter().any(|e| e == x)
 483     }
 484
 485     /// Provides a reference to the front element, or `None` if the list is
 486     /// empty.
 487     ///
 488     /// # Examples
 489     ///
 490     /// ```
 491     /// use std::collections::LinkedList;
 492     ///
 493     /// let mut dl = LinkedList::new();
 494     /// assert_eq!(dl.front(), None);
 495     ///
 496     /// dl.push_front(1);
 497     /// assert_eq!(dl.front(), Some(&1));
 498     /// ```
 499     #[inline]
 500     #[stable(feature = "rust1", since = "1.0.0")]
 501     pub fn front(&self) -> Option<&T> {
 502         unsafe {
 503             self.head.as_ref().map(|node| &node.as_ref().element)
 504         }
 505     }
 506
 507     /// Provides a mutable reference to the front element, or `None` if the list
 508     /// is empty.
 509     ///
 510     /// # Examples
 511     ///
 512     /// ```
 513     /// use std::collections::LinkedList;
 514     ///
 515     /// let mut dl = LinkedList::new();
 516     /// assert_eq!(dl.front(), None);
 517     ///
 518     /// dl.push_front(1);
 519     /// assert_eq!(dl.front(), Some(&1));
 520     ///
 521     /// match dl.front_mut() {
 522     ///     None => {},
 523     ///     Some(x) => *x = 5,
 524     /// }
 525     /// assert_eq!(dl.front(), Some(&5));
 526     /// ```
 527     #[inline]
 528     #[stable(feature = "rust1", since = "1.0.0")]
 529     pub fn front_mut(&mut self) -> Option<&mut T> {
 530         unsafe {
 531             self.head.as_mut().map(|node| &mut node.as_mut().element)
 532         }
 533     }
 534
 535     /// Provides a reference to the back element, or `None` if the list is
 536     /// empty.
 537     ///
 538     /// # Examples
 539     ///
 540     /// ```
 541     /// use std::collections::LinkedList;
 542     ///
 543     /// let mut dl = LinkedList::new();
 544     /// assert_eq!(dl.back(), None);
 545     ///
 546     /// dl.push_back(1);
 547     /// assert_eq!(dl.back(), Some(&1));
 548     /// ```
 549     #[inline]
 550     #[stable(feature = "rust1", since = "1.0.0")]
 551     pub fn back(&self) -> Option<&T> {
 552         unsafe {
 553             self.tail.as_ref().map(|node| &node.as_ref().element)
 554         }
 555     }
 556
 557     /// Provides a mutable reference to the back element, or `None` if the list
 558     /// is empty.
 559     ///
 560     /// # Examples
 561     ///
 562     /// ```
 563     /// use std::collections::LinkedList;
 564     ///
 565     /// let mut dl = LinkedList::new();
 566     /// assert_eq!(dl.back(), None);
 567     ///
 568     /// dl.push_back(1);
 569     /// assert_eq!(dl.back(), Some(&1));
 570     ///
 571     /// match dl.back_mut() {
 572     ///     None => {},
 573     ///     Some(x) => *x = 5,
 574     /// }
 575     /// assert_eq!(dl.back(), Some(&5));
 576     /// ```
 577     #[inline]
 578     #[stable(feature = "rust1", since = "1.0.0")]
 579     pub fn back_mut(&mut self) -> Option<&mut T> {
 580         unsafe {
 581             self.tail.as_mut().map(|node| &mut node.as_mut().element)
 582         }
 583     }
 584
 585     /// Adds an element first in the list.
 586     ///
 587     /// This operation should compute in O(1) time.
 588     ///
 589     /// # Examples
 590     ///
 591     /// ```
 592     /// use std::collections::LinkedList;
 593     ///
 594     /// let mut dl = LinkedList::new();
 595     ///
 596     /// dl.push_front(2);
 597     /// assert_eq!(dl.front().unwrap(), &2);
 598     ///
 599     /// dl.push_front(1);
 600     /// assert_eq!(dl.front().unwrap(), &1);
 601     /// ```
 602     #[stable(feature = "rust1", since = "1.0.0")]
 603     pub fn push_front(&mut self, elt: T) {
 604         self.push_front_node(box Node::new(elt));
 605     }
 606
 607     /// Removes the first element and returns it, or `None` if the list is
 608     /// empty.
 609     ///
 610     /// This operation should compute in O(1) time.
 611     ///
 612     /// # Examples
 613     ///
 614     /// ```
 615     /// use std::collections::LinkedList;
 616     ///
 617     /// let mut d = LinkedList::new();
 618     /// assert_eq!(d.pop_front(), None);
 619     ///
 620     /// d.push_front(1);
 621     /// d.push_front(3);
 622     /// assert_eq!(d.pop_front(), Some(3));
 623     /// assert_eq!(d.pop_front(), Some(1));
 624     /// assert_eq!(d.pop_front(), None);
 625     /// ```
 626     #[stable(feature = "rust1", since = "1.0.0")]
 627     pub fn pop_front(&mut self) -> Option<T> {
 628         self.pop_front_node().map(Node::into_element)
 629     }
 630
 631     /// Appends an element to the back of a list
 632     ///
 633     /// # Examples
 634     ///
 635     /// ```
 636     /// use std::collections::LinkedList;
 637     ///
 638     /// let mut d = LinkedList::new();
 639     /// d.push_back(1);
 640     /// d.push_back(3);
 641     /// assert_eq!(3, *d.back().unwrap());
 642     /// ```
 643     #[stable(feature = "rust1", since = "1.0.0")]
 644     pub fn push_back(&mut self, elt: T) {
 645         self.push_back_node(box Node::new(elt));
 646     }
 647
 648     /// Removes the last element from a list and returns it, or `None` if
 649     /// it is empty.
 650     ///
 651     /// # Examples
 652     ///
 653     /// ```
 654     /// use std::collections::LinkedList;
 655     ///
 656     /// let mut d = LinkedList::new();
 657     /// assert_eq!(d.pop_back(), None);
 658     /// d.push_back(1);
 659     /// d.push_back(3);
 660     /// assert_eq!(d.pop_back(), Some(3));
 661     /// ```
 662     #[stable(feature = "rust1", since = "1.0.0")]
 663     pub fn pop_back(&mut self) -> Option<T> {
 664         self.pop_back_node().map(Node::into_element)
 665     }
 666
 667     /// Splits the list into two at the given index. Returns everything after the given index,
 668     /// including the index.
 669     ///
 670     /// This operation should compute in O(n) time.
 671     ///
 672     /// # Panics
 673     ///
 674     /// Panics if `at > len`.
 675     ///
 676     /// # Examples
 677     ///
 678     /// ```
 679     /// use std::collections::LinkedList;
 680     ///
 681     /// let mut d = LinkedList::new();
 682     ///
 683     /// d.push_front(1);
 684     /// d.push_front(2);
 685     /// d.push_front(3);
 686     ///
 687     /// let mut splitted = d.split_off(2);
 688     ///
 689     /// assert_eq!(splitted.pop_front(), Some(1));
 690     /// assert_eq!(splitted.pop_front(), None);
 691     /// ```
 692     #[stable(feature = "rust1", since = "1.0.0")]
 693     pub fn split_off(&mut self, at: usize) -> LinkedList<T> {
 694         let len = self.len();
 695         assert!(at <= len, "Cannot split off at a nonexistent index");
 696         if at == 0 {
 697             return mem::replace(self, Self::new());
 698         } else if at == len {
 699             return Self::new();
 700         }
 701
 702         // Below, we iterate towards the `i-1`th node, either from the start or the end,
 703         // depending on which would be faster.
 704         let split_node = if at - 1 <= len - 1 - (at - 1) {
 705             let mut iter = self.iter_mut();
 706             // instead of skipping using .skip() (which creates a new struct),
 707             // we skip manually so we can access the head field without
 708             // depending on implementation details of Skip
 709             for _ in 0..at - 1 {
 710                 iter.next();
 711             }
 712             iter.head
 713         } else {
 714             // better off starting from the end
 715             let mut iter = self.iter_mut();
 716             for _ in 0..len - 1 - (at - 1) {
 717                 iter.next_back();
 718             }
 719             iter.tail
 720         };
 721
 722         // The split node is the new tail node of the first part and owns
 723         // the head of the second part.
 724         let second_part_head;
 725
 726         unsafe {
 727             second_part_head = split_node.unwrap().as_mut().next.take();
 728             if let Some(mut head) = second_part_head {
 729                 head.as_mut().prev = None;
 730             }
 731         }
 732
 733         let second_part = LinkedList {
 734             head: second_part_head,
 735             tail: self.tail,
 736             len: len - at,
 737             marker: PhantomData,
 738         };
 739
 740         // Fix the tail ptr of the first part
 741         self.tail = split_node;
 742         self.len = at;
 743
 744         second_part
 745     }
 746
 747     /// Creates an iterator which uses a closure to determine if an element should be removed.
 748     ///
 749     /// If the closure returns true, then the element is removed and yielded.
 750     /// If the closure returns false, the element will remain in the list and will not be yielded
 751     /// by the iterator.
 752     ///
 753     /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of
 754     /// whether you choose to keep or remove it.
 755     ///
 756     /// # Examples
 757     ///
 758     /// Splitting a list into evens and odds, reusing the original list:
 759     ///
 760     /// ```
 761     /// #![feature(drain_filter)]
 762     /// use std::collections::LinkedList;
 763     ///
 764     /// let mut numbers: LinkedList<u32> = LinkedList::new();
 765     /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
 766     ///
 767     /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>();
 768     /// let odds = numbers;
 769     ///
 770     /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
 771     /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
 772     /// ```
 773     #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 774     pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<T, F>
 775         where F: FnMut(&mut T) -> bool
 776     {
 777         // avoid borrow issues.
 778         let it = self.head;
 779         let old_len = self.len;
 780
 781         DrainFilter {
 782             list: self,
 783             it: it,
 784             pred: filter,
 785             idx: 0,
 786             old_len: old_len,
 787         }
 788     }
 789
 790     /// Returns a place for insertion at the front of the list.
 791     ///
 792     /// Using this method with placement syntax is equivalent to
 793     /// [`push_front`](#method.push_front), but may be more efficient.
 794     ///
 795     /// # Examples
 796     ///
 797     /// ```
 798     /// #![feature(collection_placement)]
 799     /// #![feature(placement_in_syntax)]
 800     ///
 801     /// use std::collections::LinkedList;
 802     ///
 803     /// let mut list = LinkedList::new();
 804     /// list.front_place() <- 2;
 805     /// list.front_place() <- 4;
 806     /// assert!(list.iter().eq(&[4, 2]));
 807     /// ```
 808     #[unstable(feature = "collection_placement",
 809                reason = "method name and placement protocol are subject to change",
 810                issue = "30172")]
 811     pub fn front_place(&mut self) -> FrontPlace<T> {
 812         FrontPlace {
 813             list: self,
 814             node: IntermediateBox::make_place(),
 815         }
 816     }
 817
 818     /// Returns a place for insertion at the back of the list.
 819     ///
 820     /// Using this method with placement syntax is equivalent to [`push_back`](#method.push_back),
 821     /// but may be more efficient.
 822     ///
 823     /// # Examples
 824     ///
 825     /// ```
 826     /// #![feature(collection_placement)]
 827     /// #![feature(placement_in_syntax)]
 828     ///
 829     /// use std::collections::LinkedList;
 830     ///
 831     /// let mut list = LinkedList::new();
 832     /// list.back_place() <- 2;
 833     /// list.back_place() <- 4;
 834     /// assert!(list.iter().eq(&[2, 4]));
 835     /// ```
 836     #[unstable(feature = "collection_placement",
 837                reason = "method name and placement protocol are subject to change",
 838                issue = "30172")]
 839     pub fn back_place(&mut self) -> BackPlace<T> {
 840         BackPlace {
 841             list: self,
 842             node: IntermediateBox::make_place(),
 843         }
 844     }
 845 }
 846
 847 #[stable(feature = "rust1", since = "1.0.0")]
 848 unsafe impl<#[may_dangle] T> Drop for LinkedList<T> {
 849     fn drop(&mut self) {
 850         while let Some(_) = self.pop_front_node() {}
 851     }
 852 }
 853
 854 #[stable(feature = "rust1", since = "1.0.0")]
 855 impl<'a, T> Iterator for Iter<'a, T> {
 856     type Item = &'a T;
 857
 858     #[inline]
 859     fn next(&mut self) -> Option<&'a T> {
 860         if self.len == 0 {
 861             None
 862         } else {
 863             self.head.map(|node| unsafe {
 864                 // Need an unbound lifetime to get 'a
 865                 let node = &*node.as_ptr();
 866                 self.len -= 1;
 867                 self.head = node.next;
 868                 &node.element
 869             })
 870         }
 871     }
 872
 873     #[inline]
 874     fn size_hint(&self) -> (usize, Option<usize>) {
 875         (self.len, Some(self.len))
 876     }
 877 }
 878
 879 #[stable(feature = "rust1", since = "1.0.0")]
 880 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
 881     #[inline]
 882     fn next_back(&mut self) -> Option<&'a T> {
 883         if self.len == 0 {
 884             None
 885         } else {
 886             self.tail.map(|node| unsafe {
 887                 // Need an unbound lifetime to get 'a
 888                 let node = &*node.as_ptr();
 889                 self.len -= 1;
 890                 self.tail = node.prev;
 891                 &node.element
 892             })
 893         }
 894     }
 895 }
 896
 897 #[stable(feature = "rust1", since = "1.0.0")]
 898 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
 899
 900 #[stable(feature = "fused", since = "1.26.0")]
 901 impl<'a, T> FusedIterator for Iter<'a, T> {}
 902
 903 #[stable(feature = "rust1", since = "1.0.0")]
 904 impl<'a, T> Iterator for IterMut<'a, T> {
 905     type Item = &'a mut T;
 906
 907     #[inline]
 908     fn next(&mut self) -> Option<&'a mut T> {
 909         if self.len == 0 {
 910             None
 911         } else {
 912             self.head.map(|node| unsafe {
 913                 // Need an unbound lifetime to get 'a
 914                 let node = &mut *node.as_ptr();
 915                 self.len -= 1;
 916                 self.head = node.next;
 917                 &mut node.element
 918             })
 919         }
 920     }
 921
 922     #[inline]
 923     fn size_hint(&self) -> (usize, Option<usize>) {
 924         (self.len, Some(self.len))
 925     }
 926 }
 927
 928 #[stable(feature = "rust1", since = "1.0.0")]
 929 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
 930     #[inline]
 931     fn next_back(&mut self) -> Option<&'a mut T> {
 932         if self.len == 0 {
 933             None
 934         } else {
 935             self.tail.map(|node| unsafe {
 936                 // Need an unbound lifetime to get 'a
 937                 let node = &mut *node.as_ptr();
 938                 self.len -= 1;
 939                 self.tail = node.prev;
 940                 &mut node.element
 941             })
 942         }
 943     }
 944 }
 945
 946 #[stable(feature = "rust1", since = "1.0.0")]
 947 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
 948
 949 #[stable(feature = "fused", since = "1.26.0")]
 950 impl<'a, T> FusedIterator for IterMut<'a, T> {}
 951
 952 impl<'a, T> IterMut<'a, T> {
 953     /// Inserts the given element just after the element most recently returned by `.next()`.
 954     /// The inserted element does not appear in the iteration.
 955     ///
 956     /// # Examples
 957     ///
 958     /// ```
 959     /// #![feature(linked_list_extras)]
 960     ///
 961     /// use std::collections::LinkedList;
 962     ///
 963     /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
 964     ///
 965     /// {
 966     ///     let mut it = list.iter_mut();
 967     ///     assert_eq!(it.next().unwrap(), &1);
 968     ///     // insert `2` after `1`
 969     ///     it.insert_next(2);
 970     /// }
 971     /// {
 972     ///     let vec: Vec<_> = list.into_iter().collect();
 973     ///     assert_eq!(vec, [1, 2, 3, 4]);
 974     /// }
 975     /// ```
 976     #[inline]
 977     #[unstable(feature = "linked_list_extras",
 978                reason = "this is probably better handled by a cursor type -- we'll see",
 979                issue = "27794")]
 980     pub fn insert_next(&mut self, element: T) {
 981         match self.head {
 982             None => self.list.push_back(element),
 983             Some(mut head) => unsafe {
 984                 let mut prev = match head.as_ref().prev {
 985                     None => return self.list.push_front(element),
 986                     Some(prev) => prev,
 987                 };
 988
 989                 let node = Some(Box::into_raw_non_null(box Node {
 990                     next: Some(head),
 991                     prev: Some(prev),
 992                     element,
 993                 }));
 994
 995                 prev.as_mut().next = node;
 996                 head.as_mut().prev = node;
 997
 998                 self.list.len += 1;
 999             },
1000         }
1001     }
1002
1003     /// Provides a reference to the next element, without changing the iterator.
1004     ///
1005     /// # Examples
1006     ///
1007     /// ```
1008     /// #![feature(linked_list_extras)]
1009     ///
1010     /// use std::collections::LinkedList;
1011     ///
1012     /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
1013     ///
1014     /// let mut it = list.iter_mut();
1015     /// assert_eq!(it.next().unwrap(), &1);
1016     /// assert_eq!(it.peek_next().unwrap(), &2);
1017     /// // We just peeked at 2, so it was not consumed from the iterator.
1018     /// assert_eq!(it.next().unwrap(), &2);
1019     /// ```
1020     #[inline]
1021     #[unstable(feature = "linked_list_extras",
1022                reason = "this is probably better handled by a cursor type -- we'll see",
1023                issue = "27794")]
1024     pub fn peek_next(&mut self) -> Option<&mut T> {
1025         if self.len == 0 {
1026             None
1027         } else {
1028             unsafe {
1029                 self.head.as_mut().map(|node| &mut node.as_mut().element)
1030             }
1031         }
1032     }
1033 }
1034
1035 /// An iterator produced by calling `drain_filter` on LinkedList.
1036 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1037 pub struct DrainFilter<'a, T: 'a, F: 'a>
1038     where F: FnMut(&mut T) -> bool,
1039 {
1040     list: &'a mut LinkedList<T>,
1041     it: Option<NonNull<Node<T>>>,
1042     pred: F,
1043     idx: usize,
1044     old_len: usize,
1045 }
1046
1047 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1048 impl<'a, T, F> Iterator for DrainFilter<'a, T, F>
1049     where F: FnMut(&mut T) -> bool,
1050 {
1051     type Item = T;
1052
1053     fn next(&mut self) -> Option<T> {
1054         while let Some(mut node) = self.it {
1055             unsafe {
1056                 self.it = node.as_ref().next;
1057                 self.idx += 1;
1058
1059                 if (self.pred)(&mut node.as_mut().element) {
1060                     self.list.unlink_node(node);
1061                     return Some(Box::from_raw(node.as_ptr()).element);
1062                 }
1063             }
1064         }
1065
1066         None
1067     }
1068
1069     fn size_hint(&self) -> (usize, Option<usize>) {
1070         (0, Some(self.old_len - self.idx))
1071     }
1072 }
1073
1074 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1075 impl<'a, T, F> Drop for DrainFilter<'a, T, F>
1076     where F: FnMut(&mut T) -> bool,
1077 {
1078     fn drop(&mut self) {
1079         for _ in self { }
1080     }
1081 }
1082
1083 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1084 impl<'a, T: 'a + fmt::Debug, F> fmt::Debug for DrainFilter<'a, T, F>
1085     where F: FnMut(&mut T) -> bool
1086 {
1087     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1088         f.debug_tuple("DrainFilter")
1089          .field(&self.list)
1090          .finish()
1091     }
1092 }
1093
1094 #[stable(feature = "rust1", since = "1.0.0")]
1095 impl<T> Iterator for IntoIter<T> {
1096     type Item = T;
1097
1098     #[inline]
1099     fn next(&mut self) -> Option<T> {
1100         self.list.pop_front()
1101     }
1102
1103     #[inline]
1104     fn size_hint(&self) -> (usize, Option<usize>) {
1105         (self.list.len, Some(self.list.len))
1106     }
1107 }
1108
1109 #[stable(feature = "rust1", since = "1.0.0")]
1110 impl<T> DoubleEndedIterator for IntoIter<T> {
1111     #[inline]
1112     fn next_back(&mut self) -> Option<T> {
1113         self.list.pop_back()
1114     }
1115 }
1116
1117 #[stable(feature = "rust1", since = "1.0.0")]
1118 impl<T> ExactSizeIterator for IntoIter<T> {}
1119
1120 #[stable(feature = "fused", since = "1.26.0")]
1121 impl<T> FusedIterator for IntoIter<T> {}
1122
1123 #[stable(feature = "rust1", since = "1.0.0")]
1124 impl<T> FromIterator<T> for LinkedList<T> {
1125     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1126         let mut list = Self::new();
1127         list.extend(iter);
1128         list
1129     }
1130 }
1131
1132 #[stable(feature = "rust1", since = "1.0.0")]
1133 impl<T> IntoIterator for LinkedList<T> {
1134     type Item = T;
1135     type IntoIter = IntoIter<T>;
1136
1137     /// Consumes the list into an iterator yielding elements by value.
1138     #[inline]
1139     fn into_iter(self) -> IntoIter<T> {
1140         IntoIter { list: self }
1141     }
1142 }
1143
1144 #[stable(feature = "rust1", since = "1.0.0")]
1145 impl<'a, T> IntoIterator for &'a LinkedList<T> {
1146     type Item = &'a T;
1147     type IntoIter = Iter<'a, T>;
1148
1149     fn into_iter(self) -> Iter<'a, T> {
1150         self.iter()
1151     }
1152 }
1153
1154 #[stable(feature = "rust1", since = "1.0.0")]
1155 impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
1156     type Item = &'a mut T;
1157     type IntoIter = IterMut<'a, T>;
1158
1159     fn into_iter(self) -> IterMut<'a, T> {
1160         self.iter_mut()
1161     }
1162 }
1163
1164 #[stable(feature = "rust1", since = "1.0.0")]
1165 impl<T> Extend<T> for LinkedList<T> {
1166     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1167         <Self as SpecExtend<I>>::spec_extend(self, iter);
1168     }
1169 }
1170
1171 impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> {
1172     default fn spec_extend(&mut self, iter: I) {
1173         for elt in iter {
1174             self.push_back(elt);
1175         }
1176     }
1177 }
1178
1179 impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
1180     fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
1181         self.append(other);
1182     }
1183 }
1184
1185 #[stable(feature = "extend_ref", since = "1.2.0")]
1186 impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> {
1187     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1188         self.extend(iter.into_iter().cloned());
1189     }
1190 }
1191
1192 #[stable(feature = "rust1", since = "1.0.0")]
1193 impl<T: PartialEq> PartialEq for LinkedList<T> {
1194     fn eq(&self, other: &Self) -> bool {
1195         self.len() == other.len() && self.iter().eq(other)
1196     }
1197
1198     fn ne(&self, other: &Self) -> bool {
1199         self.len() != other.len() || self.iter().ne(other)
1200     }
1201 }
1202
1203 #[stable(feature = "rust1", since = "1.0.0")]
1204 impl<T: Eq> Eq for LinkedList<T> {}
1205
1206 #[stable(feature = "rust1", since = "1.0.0")]
1207 impl<T: PartialOrd> PartialOrd for LinkedList<T> {
1208     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1209         self.iter().partial_cmp(other)
1210     }
1211 }
1212
1213 #[stable(feature = "rust1", since = "1.0.0")]
1214 impl<T: Ord> Ord for LinkedList<T> {
1215     #[inline]
1216     fn cmp(&self, other: &Self) -> Ordering {
1217         self.iter().cmp(other)
1218     }
1219 }
1220
1221 #[stable(feature = "rust1", since = "1.0.0")]
1222 impl<T: Clone> Clone for LinkedList<T> {
1223     fn clone(&self) -> Self {
1224         self.iter().cloned().collect()
1225     }
1226 }
1227
1228 #[stable(feature = "rust1", since = "1.0.0")]
1229 impl<T: fmt::Debug> fmt::Debug for LinkedList<T> {
1230     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1231         f.debug_list().entries(self).finish()
1232     }
1233 }
1234
1235 #[stable(feature = "rust1", since = "1.0.0")]
1236 impl<T: Hash> Hash for LinkedList<T> {
1237     fn hash<H: Hasher>(&self, state: &mut H) {
1238         self.len().hash(state);
1239         for elt in self {
1240             elt.hash(state);
1241         }
1242     }
1243 }
1244
1245 unsafe fn finalize<T>(node: IntermediateBox<Node<T>>) -> Box<Node<T>> {
1246     let mut node = node.finalize();
1247     ptr::write(&mut node.next, None);
1248     ptr::write(&mut node.prev, None);
1249     node
1250 }
1251
1252 /// A place for insertion at the front of a `LinkedList`.
1253 ///
1254 /// See [`LinkedList::front_place`](struct.LinkedList.html#method.front_place) for details.
1255 #[must_use = "places do nothing unless written to with `<-` syntax"]
1256 #[unstable(feature = "collection_placement",
1257            reason = "struct name and placement protocol are subject to change",
1258            issue = "30172")]
1259 pub struct FrontPlace<'a, T: 'a> {
1260     list: &'a mut LinkedList<T>,
1261     node: IntermediateBox<Node<T>>,
1262 }
1263
1264 #[unstable(feature = "collection_placement",
1265            reason = "struct name and placement protocol are subject to change",
1266            issue = "30172")]
1267 impl<'a, T: 'a + fmt::Debug> fmt::Debug for FrontPlace<'a, T> {
1268     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1269         f.debug_tuple("FrontPlace")
1270          .field(&self.list)
1271          .finish()
1272     }
1273 }
1274
1275 #[unstable(feature = "collection_placement",
1276            reason = "placement protocol is subject to change",
1277            issue = "30172")]
1278 impl<'a, T> Placer<T> for FrontPlace<'a, T> {
1279     type Place = Self;
1280
1281     fn make_place(self) -> Self {
1282         self
1283     }
1284 }
1285
1286 #[unstable(feature = "collection_placement",
1287            reason = "placement protocol is subject to change",
1288            issue = "30172")]
1289 unsafe impl<'a, T> Place<T> for FrontPlace<'a, T> {
1290     fn pointer(&mut self) -> *mut T {
1291         unsafe { &mut (*self.node.pointer()).element }
1292     }
1293 }
1294
1295 #[unstable(feature = "collection_placement",
1296            reason = "placement protocol is subject to change",
1297            issue = "30172")]
1298 impl<'a, T> InPlace<T> for FrontPlace<'a, T> {
1299     type Owner = ();
1300
1301     unsafe fn finalize(self) {
1302         let FrontPlace { list, node } = self;
1303         list.push_front_node(finalize(node));
1304     }
1305 }
1306
1307 /// A place for insertion at the back of a `LinkedList`.
1308 ///
1309 /// See [`LinkedList::back_place`](struct.LinkedList.html#method.back_place) for details.
1310 #[must_use = "places do nothing unless written to with `<-` syntax"]
1311 #[unstable(feature = "collection_placement",
1312            reason = "struct name and placement protocol are subject to change",
1313            issue = "30172")]
1314 pub struct BackPlace<'a, T: 'a> {
1315     list: &'a mut LinkedList<T>,
1316     node: IntermediateBox<Node<T>>,
1317 }
1318
1319 #[unstable(feature = "collection_placement",
1320            reason = "struct name and placement protocol are subject to change",
1321            issue = "30172")]
1322 impl<'a, T: 'a + fmt::Debug> fmt::Debug for BackPlace<'a, T> {
1323     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1324         f.debug_tuple("BackPlace")
1325          .field(&self.list)
1326          .finish()
1327     }
1328 }
1329
1330 #[unstable(feature = "collection_placement",
1331            reason = "placement protocol is subject to change",
1332            issue = "30172")]
1333 impl<'a, T> Placer<T> for BackPlace<'a, T> {
1334     type Place = Self;
1335
1336     fn make_place(self) -> Self {
1337         self
1338     }
1339 }
1340
1341 #[unstable(feature = "collection_placement",
1342            reason = "placement protocol is subject to change",
1343            issue = "30172")]
1344 unsafe impl<'a, T> Place<T> for BackPlace<'a, T> {
1345     fn pointer(&mut self) -> *mut T {
1346         unsafe { &mut (*self.node.pointer()).element }
1347     }
1348 }
1349
1350 #[unstable(feature = "collection_placement",
1351            reason = "placement protocol is subject to change",
1352            issue = "30172")]
1353 impl<'a, T> InPlace<T> for BackPlace<'a, T> {
1354     type Owner = ();
1355
1356     unsafe fn finalize(self) {
1357         let BackPlace { list, node } = self;
1358         list.push_back_node(finalize(node));
1359     }
1360 }
1361
1362 // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
1363 #[allow(dead_code)]
1364 fn assert_covariance() {
1365     fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
1366         x
1367     }
1368     fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
1369         x
1370     }
1371     fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
1372         x
1373     }
1374 }
1375
1376 #[stable(feature = "rust1", since = "1.0.0")]
1377 unsafe impl<T: Send> Send for LinkedList<T> {}
1378
1379 #[stable(feature = "rust1", since = "1.0.0")]
1380 unsafe impl<T: Sync> Sync for LinkedList<T> {}
1381
1382 #[stable(feature = "rust1", since = "1.0.0")]
1383 unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
1384
1385 #[stable(feature = "rust1", since = "1.0.0")]
1386 unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
1387
1388 #[stable(feature = "rust1", since = "1.0.0")]
1389 unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
1390
1391 #[stable(feature = "rust1", since = "1.0.0")]
1392 unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
1393
1394 #[cfg(test)]
1395 mod tests {
1396     use std::thread;
1397     use std::vec::Vec;
1398
1399     use rand::{thread_rng, Rng};
1400
1401     use super::{LinkedList, Node};
1402
1403     #[cfg(test)]
1404     fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
1405         v.iter().cloned().collect()
1406     }
1407
1408     pub fn check_links<T>(list: &LinkedList<T>) {
1409         unsafe {
1410             let mut len = 0;
1411             let mut last_ptr: Option<&Node<T>> = None;
1412             let mut node_ptr: &Node<T>;
1413             match list.head {
1414                 None => {
1415                     // tail node should also be None.
1416                     assert!(list.tail.is_none());
1417                     assert_eq!(0, list.len);
1418                     return;
1419                 }
1420                 Some(node) => node_ptr = &*node.as_ptr(),
1421             }
1422             loop {
1423                 match (last_ptr, node_ptr.prev) {
1424                     (None, None) => {}
1425                     (None, _) => panic!("prev link for head"),
1426                     (Some(p), Some(pptr)) => {
1427                         assert_eq!(p as *const Node<T>, pptr.as_ptr() as *const Node<T>);
1428                     }
1429                     _ => panic!("prev link is none, not good"),
1430                 }
1431                 match node_ptr.next {
1432                     Some(next) => {
1433                         last_ptr = Some(node_ptr);
1434                         node_ptr = &*next.as_ptr();
1435                         len += 1;
1436                     }
1437                     None => {
1438                         len += 1;
1439                         break;
1440                     }
1441                 }
1442             }
1443
1444             // verify that the tail node points to the last node.
1445             let tail = list.tail.as_ref().expect("some tail node").as_ref();
1446             assert_eq!(tail as *const Node<T>, node_ptr as *const Node<T>);
1447             // check that len matches interior links.
1448             assert_eq!(len, list.len);
1449         }
1450     }
1451
1452     #[test]
1453     fn test_append() {
1454         // Empty to empty
1455         {
1456             let mut m = LinkedList::<i32>::new();
1457             let mut n = LinkedList::new();
1458             m.append(&mut n);
1459             check_links(&m);
1460             assert_eq!(m.len(), 0);
1461             assert_eq!(n.len(), 0);
1462         }
1463         // Non-empty to empty
1464         {
1465             let mut m = LinkedList::new();
1466             let mut n = LinkedList::new();
1467             n.push_back(2);
1468             m.append(&mut n);
1469             check_links(&m);
1470             assert_eq!(m.len(), 1);
1471             assert_eq!(m.pop_back(), Some(2));
1472             assert_eq!(n.len(), 0);
1473             check_links(&m);
1474         }
1475         // Empty to non-empty
1476         {
1477             let mut m = LinkedList::new();
1478             let mut n = LinkedList::new();
1479             m.push_back(2);
1480             m.append(&mut n);
1481             check_links(&m);
1482             assert_eq!(m.len(), 1);
1483             assert_eq!(m.pop_back(), Some(2));
1484             check_links(&m);
1485         }
1486
1487         // Non-empty to non-empty
1488         let v = vec![1, 2, 3, 4, 5];
1489         let u = vec![9, 8, 1, 2, 3, 4, 5];
1490         let mut m = list_from(&v);
1491         let mut n = list_from(&u);
1492         m.append(&mut n);
1493         check_links(&m);
1494         let mut sum = v;
1495         sum.extend_from_slice(&u);
1496         assert_eq!(sum.len(), m.len());
1497         for elt in sum {
1498             assert_eq!(m.pop_front(), Some(elt))
1499         }
1500         assert_eq!(n.len(), 0);
1501         // let's make sure it's working properly, since we
1502         // did some direct changes to private members
1503         n.push_back(3);
1504         assert_eq!(n.len(), 1);
1505         assert_eq!(n.pop_front(), Some(3));
1506         check_links(&n);
1507     }
1508
1509     #[test]
1510     fn test_insert_prev() {
1511         let mut m = list_from(&[0, 2, 4, 6, 8]);
1512         let len = m.len();
1513         {
1514             let mut it = m.iter_mut();
1515             it.insert_next(-2);
1516             loop {
1517                 match it.next() {
1518                     None => break,
1519                     Some(elt) => {
1520                         it.insert_next(*elt + 1);
1521                         match it.peek_next() {
1522                             Some(x) => assert_eq!(*x, *elt + 2),
1523                             None => assert_eq!(8, *elt),
1524                         }
1525                     }
1526                 }
1527             }
1528             it.insert_next(0);
1529             it.insert_next(1);
1530         }
1531         check_links(&m);
1532         assert_eq!(m.len(), 3 + len * 2);
1533         assert_eq!(m.into_iter().collect::<Vec<_>>(),
1534                    [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]);
1535     }
1536
1537     #[test]
1538     #[cfg_attr(target_os = "emscripten", ignore)]
1539     fn test_send() {
1540         let n = list_from(&[1, 2, 3]);
1541         thread::spawn(move || {
1542                 check_links(&n);
1543                 let a: &[_] = &[&1, &2, &3];
1544                 assert_eq!(a, &*n.iter().collect::<Vec<_>>());
1545             })
1546             .join()
1547             .ok()
1548             .unwrap();
1549     }
1550
1551     #[test]
1552     fn test_fuzz() {
1553         for _ in 0..25 {
1554             fuzz_test(3);
1555             fuzz_test(16);
1556             fuzz_test(189);
1557         }
1558     }
1559
1560     #[test]
1561     fn test_26021() {
1562         // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
1563         // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
1564         // its nodes.
1565         //
1566         // https://github.com/rust-lang/rust/issues/26021
1567         let mut v1 = LinkedList::new();
1568         v1.push_front(1);
1569         v1.push_front(1);
1570         v1.push_front(1);
1571         v1.push_front(1);
1572         let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
1573         assert_eq!(v1.len(), 3);
1574
1575         assert_eq!(v1.iter().len(), 3);
1576         assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
1577     }
1578
1579     #[test]
1580     fn test_split_off() {
1581         let mut v1 = LinkedList::new();
1582         v1.push_front(1);
1583         v1.push_front(1);
1584         v1.push_front(1);
1585         v1.push_front(1);
1586
1587         // test all splits
1588         for ix in 0..1 + v1.len() {
1589             let mut a = v1.clone();
1590             let b = a.split_off(ix);
1591             check_links(&a);
1592             check_links(&b);
1593             a.extend(b);
1594             assert_eq!(v1, a);
1595         }
1596     }
1597
1598     #[cfg(test)]
1599     fn fuzz_test(sz: i32) {
1600         let mut m: LinkedList<_> = LinkedList::new();
1601         let mut v = vec![];
1602         for i in 0..sz {
1603             check_links(&m);
1604             let r: u8 = thread_rng().next_u32() as u8;
1605             match r % 6 {
1606                 0 => {
1607                     m.pop_back();
1608                     v.pop();
1609                 }
1610                 1 => {
1611                     if !v.is_empty() {
1612                         m.pop_front();
1613                         v.remove(0);
1614                     }
1615                 }
1616                 2 | 4 => {
1617                     m.push_front(-i);
1618                     v.insert(0, -i);
1619                 }
1620                 3 | 5 | _ => {
1621                     m.push_back(i);
1622                     v.push(i);
1623                 }
1624             }
1625         }
1626
1627         check_links(&m);
1628
1629         let mut i = 0;
1630         for (a, &b) in m.into_iter().zip(&v) {
1631             i += 1;
1632             assert_eq!(a, b);
1633         }
1634         assert_eq!(i, v.len());
1635     }
1636
1637     #[test]
1638     fn drain_filter_test() {
1639         let mut m: LinkedList<u32> = LinkedList::new();
1640         m.extend(&[1, 2, 3, 4, 5, 6]);
1641         let deleted = m.drain_filter(|v| *v < 4).collect::<Vec<_>>();
1642
1643         check_links(&m);
1644
1645         assert_eq!(deleted, &[1, 2, 3]);
1646         assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]);
1647     }
1648
1649     #[test]
1650     fn drain_to_empty_test() {
1651         let mut m: LinkedList<u32> = LinkedList::new();
1652         m.extend(&[1, 2, 3, 4, 5, 6]);
1653         let deleted = m.drain_filter(|_| true).collect::<Vec<_>>();
1654
1655         check_links(&m);
1656
1657         assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
1658         assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
1659     }
1660 }