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