src/liballoc/collections/linked_list.rs

   1 //! A doubly-linked list with owned nodes.
   2 //!
   3 //! The `LinkedList` allows pushing and popping elements at either end
   4 //! in constant time.
   5 //!
   6 //! NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because
   7 //! array-based containers are generally faster,
   8 //! more memory efficient, and make better use of CPU cache.
   9 //!
  10 //! [`Vec`]: ../../vec/struct.Vec.html
  11 //! [`VecDeque`]: ../vec_deque/struct.VecDeque.html
  12
  13 #![stable(feature = "rust1", since = "1.0.0")]
  14
  15 use core::cmp::Ordering;
  16 use core::fmt;
  17 use core::hash::{Hash, Hasher};
  18 use core::iter::{FromIterator, FusedIterator};
  19 use core::marker::PhantomData;
  20 use core::mem;
  21 use core::ptr::NonNull;
  22
  23 use super::SpecExtend;
  24 use crate::boxed::Box;
  25
  26 #[cfg(test)]
  27 mod tests;
  28
  29 /// A doubly-linked list with owned nodes.
  30 ///
  31 /// The `LinkedList` allows pushing and popping elements at either end
  32 /// in constant time.
  33 ///
  34 /// NOTE: It is almost always better to use `Vec` or `VecDeque` because
  35 /// array-based containers are generally faster,
  36 /// more memory efficient, and make better use of CPU cache.
  37 #[stable(feature = "rust1", since = "1.0.0")]
  38 pub struct LinkedList<T> {
  39     head: Option<NonNull<Node<T>>>,
  40     tail: Option<NonNull<Node<T>>>,
  41     len: usize,
  42     marker: PhantomData<Box<Node<T>>>,
  43 }
  44
  45 struct Node<T> {
  46     next: Option<NonNull<Node<T>>>,
  47     prev: Option<NonNull<Node<T>>>,
  48     element: T,
  49 }
  50
  51 /// An iterator over the elements of a `LinkedList`.
  52 ///
  53 /// This `struct` is created by the [`iter`] method on [`LinkedList`]. See its
  54 /// documentation for more.
  55 ///
  56 /// [`iter`]: struct.LinkedList.html#method.iter
  57 /// [`LinkedList`]: struct.LinkedList.html
  58 #[stable(feature = "rust1", since = "1.0.0")]
  59 pub struct Iter<'a, T: 'a> {
  60     head: Option<NonNull<Node<T>>>,
  61     tail: Option<NonNull<Node<T>>>,
  62     len: usize,
  63     marker: PhantomData<&'a Node<T>>,
  64 }
  65
  66 #[stable(feature = "collection_debug", since = "1.17.0")]
  67 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
  68     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  69         f.debug_tuple("Iter").field(&self.len).finish()
  70     }
  71 }
  72
  73 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
  74 #[stable(feature = "rust1", since = "1.0.0")]
  75 impl<T> Clone for Iter<'_, T> {
  76     fn clone(&self) -> Self {
  77         Iter { ..*self }
  78     }
  79 }
  80
  81 /// A mutable iterator over the elements of a `LinkedList`.
  82 ///
  83 /// This `struct` is created by the [`iter_mut`] method on [`LinkedList`]. See its
  84 /// documentation for more.
  85 ///
  86 /// [`iter_mut`]: struct.LinkedList.html#method.iter_mut
  87 /// [`LinkedList`]: struct.LinkedList.html
  88 #[stable(feature = "rust1", since = "1.0.0")]
  89 pub struct IterMut<'a, T: 'a> {
  90     // We do *not* exclusively own the entire list here, references to node's `element`
  91     // have been handed out by the iterator! So be careful when using this; the methods
  92     // called must be aware that there can be aliasing pointers to `element`.
  93     list: &'a mut LinkedList<T>,
  94     head: Option<NonNull<Node<T>>>,
  95     tail: Option<NonNull<Node<T>>>,
  96     len: usize,
  97 }
  98
  99 #[stable(feature = "collection_debug", since = "1.17.0")]
 100 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
 101     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 102         f.debug_tuple("IterMut").field(&self.list).field(&self.len).finish()
 103     }
 104 }
 105
 106 /// An owning iterator over the elements of a `LinkedList`.
 107 ///
 108 /// This `struct` is created by the [`into_iter`] method on [`LinkedList`]
 109 /// (provided by the `IntoIterator` trait). See its documentation for more.
 110 ///
 111 /// [`into_iter`]: struct.LinkedList.html#method.into_iter
 112 /// [`LinkedList`]: struct.LinkedList.html
 113 #[derive(Clone)]
 114 #[stable(feature = "rust1", since = "1.0.0")]
 115 pub struct IntoIter<T> {
 116     list: LinkedList<T>,
 117 }
 118
 119 #[stable(feature = "collection_debug", since = "1.17.0")]
 120 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
 121     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 122         f.debug_tuple("IntoIter").field(&self.list).finish()
 123     }
 124 }
 125
 126 impl<T> Node<T> {
 127     fn new(element: T) -> Self {
 128         Node { next: None, prev: None, element }
 129     }
 130
 131     fn into_element(self: Box<Self>) -> T {
 132         self.element
 133     }
 134 }
 135
 136 // private methods
 137 impl<T> LinkedList<T> {
 138     /// Adds the given node to the front of the list.
 139     #[inline]
 140     fn push_front_node(&mut self, mut node: Box<Node<T>>) {
 141         // This method takes care not to create mutable references to whole nodes,
 142         // to maintain validity of aliasing pointers into `element`.
 143         unsafe {
 144             node.next = self.head;
 145             node.prev = None;
 146             let node = Some(Box::into_raw_non_null(node));
 147
 148             match self.head {
 149                 None => self.tail = node,
 150                 // Not creating new mutable (unique!) references overlapping `element`.
 151                 Some(head) => (*head.as_ptr()).prev = node,
 152             }
 153
 154             self.head = node;
 155             self.len += 1;
 156         }
 157     }
 158
 159     /// Removes and returns the node at the front of the list.
 160     #[inline]
 161     fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
 162         // This method takes care not to create mutable references to whole nodes,
 163         // to maintain validity of aliasing pointers into `element`.
 164         self.head.map(|node| unsafe {
 165             let node = Box::from_raw(node.as_ptr());
 166             self.head = node.next;
 167
 168             match self.head {
 169                 None => self.tail = None,
 170                 // Not creating new mutable (unique!) references overlapping `element`.
 171                 Some(head) => (*head.as_ptr()).prev = None,
 172             }
 173
 174             self.len -= 1;
 175             node
 176         })
 177     }
 178
 179     /// Adds the given node to the back of the list.
 180     #[inline]
 181     fn push_back_node(&mut self, mut node: Box<Node<T>>) {
 182         // This method takes care not to create mutable references to whole nodes,
 183         // to maintain validity of aliasing pointers into `element`.
 184         unsafe {
 185             node.next = None;
 186             node.prev = self.tail;
 187             let node = Some(Box::into_raw_non_null(node));
 188
 189             match self.tail {
 190                 None => self.head = node,
 191                 // Not creating new mutable (unique!) references overlapping `element`.
 192                 Some(tail) => (*tail.as_ptr()).next = node,
 193             }
 194
 195             self.tail = node;
 196             self.len += 1;
 197         }
 198     }
 199
 200     /// Removes and returns the node at the back of the list.
 201     #[inline]
 202     fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
 203         // This method takes care not to create mutable references to whole nodes,
 204         // to maintain validity of aliasing pointers into `element`.
 205         self.tail.map(|node| unsafe {
 206             let node = Box::from_raw(node.as_ptr());
 207             self.tail = node.prev;
 208
 209             match self.tail {
 210                 None => self.head = None,
 211                 // Not creating new mutable (unique!) references overlapping `element`.
 212                 Some(tail) => (*tail.as_ptr()).next = None,
 213             }
 214
 215             self.len -= 1;
 216             node
 217         })
 218     }
 219
 220     /// Unlinks the specified node from the current list.
 221     ///
 222     /// Warning: this will not check that the provided node belongs to the current list.
 223     ///
 224     /// This method takes care not to create mutable references to `element`, to
 225     /// maintain validity of aliasing pointers.
 226     #[inline]
 227     unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
 228         let node = node.as_mut(); // this one is ours now, we can create an &mut.
 229
 230         // Not creating new mutable (unique!) references overlapping `element`.
 231         match node.prev {
 232             Some(prev) => (*prev.as_ptr()).next = node.next,
 233             // this node is the head node
 234             None => self.head = node.next,
 235         };
 236
 237         match node.next {
 238             Some(next) => (*next.as_ptr()).prev = node.prev,
 239             // this node is the tail node
 240             None => self.tail = node.prev,
 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     #[rustc_const_stable(feature = "const_linked_list_new", since = "1.32.0")]
 268     #[stable(feature = "rust1", since = "1.0.0")]
 269     pub const fn new() -> Self {
 270         LinkedList { head: None, tail: None, len: 0, marker: PhantomData }
 271     }
 272
 273     /// Moves all elements from `other` to the end of the list.
 274     ///
 275     /// This reuses all the nodes from `other` and moves them into `self`. After
 276     /// this operation, `other` becomes empty.
 277     ///
 278     /// This operation should compute in O(1) time and O(1) memory.
 279     ///
 280     /// # Examples
 281     ///
 282     /// ```
 283     /// use std::collections::LinkedList;
 284     ///
 285     /// let mut list1 = LinkedList::new();
 286     /// list1.push_back('a');
 287     ///
 288     /// let mut list2 = LinkedList::new();
 289     /// list2.push_back('b');
 290     /// list2.push_back('c');
 291     ///
 292     /// list1.append(&mut list2);
 293     ///
 294     /// let mut iter = list1.iter();
 295     /// assert_eq!(iter.next(), Some(&'a'));
 296     /// assert_eq!(iter.next(), Some(&'b'));
 297     /// assert_eq!(iter.next(), Some(&'c'));
 298     /// assert!(iter.next().is_none());
 299     ///
 300     /// assert!(list2.is_empty());
 301     /// ```
 302     #[stable(feature = "rust1", since = "1.0.0")]
 303     pub fn append(&mut self, other: &mut Self) {
 304         match self.tail {
 305             None => mem::swap(self, other),
 306             Some(mut tail) => {
 307                 // `as_mut` is okay here because we have exclusive access to the entirety
 308                 // of both lists.
 309                 if let Some(mut other_head) = other.head.take() {
 310                     unsafe {
 311                         tail.as_mut().next = Some(other_head);
 312                         other_head.as_mut().prev = Some(tail);
 313                     }
 314
 315                     self.tail = other.tail.take();
 316                     self.len += mem::replace(&mut other.len, 0);
 317                 }
 318             }
 319         }
 320     }
 321
 322     /// Provides a forward iterator.
 323     ///
 324     /// # Examples
 325     ///
 326     /// ```
 327     /// use std::collections::LinkedList;
 328     ///
 329     /// let mut list: LinkedList<u32> = LinkedList::new();
 330     ///
 331     /// list.push_back(0);
 332     /// list.push_back(1);
 333     /// list.push_back(2);
 334     ///
 335     /// let mut iter = list.iter();
 336     /// assert_eq!(iter.next(), Some(&0));
 337     /// assert_eq!(iter.next(), Some(&1));
 338     /// assert_eq!(iter.next(), Some(&2));
 339     /// assert_eq!(iter.next(), None);
 340     /// ```
 341     #[inline]
 342     #[stable(feature = "rust1", since = "1.0.0")]
 343     pub fn iter(&self) -> Iter<'_, T> {
 344         Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
 345     }
 346
 347     /// Provides a forward iterator with mutable references.
 348     ///
 349     /// # Examples
 350     ///
 351     /// ```
 352     /// use std::collections::LinkedList;
 353     ///
 354     /// let mut list: LinkedList<u32> = LinkedList::new();
 355     ///
 356     /// list.push_back(0);
 357     /// list.push_back(1);
 358     /// list.push_back(2);
 359     ///
 360     /// for element in list.iter_mut() {
 361     ///     *element += 10;
 362     /// }
 363     ///
 364     /// let mut iter = list.iter();
 365     /// assert_eq!(iter.next(), Some(&10));
 366     /// assert_eq!(iter.next(), Some(&11));
 367     /// assert_eq!(iter.next(), Some(&12));
 368     /// assert_eq!(iter.next(), None);
 369     /// ```
 370     #[inline]
 371     #[stable(feature = "rust1", since = "1.0.0")]
 372     pub fn iter_mut(&mut self) -> IterMut<'_, T> {
 373         IterMut { head: self.head, tail: self.tail, len: self.len, list: self }
 374     }
 375
 376     /// Returns `true` if the `LinkedList` is empty.
 377     ///
 378     /// This operation should compute in O(1) time.
 379     ///
 380     /// # Examples
 381     ///
 382     /// ```
 383     /// use std::collections::LinkedList;
 384     ///
 385     /// let mut dl = LinkedList::new();
 386     /// assert!(dl.is_empty());
 387     ///
 388     /// dl.push_front("foo");
 389     /// assert!(!dl.is_empty());
 390     /// ```
 391     #[inline]
 392     #[stable(feature = "rust1", since = "1.0.0")]
 393     pub fn is_empty(&self) -> bool {
 394         self.head.is_none()
 395     }
 396
 397     /// Returns the length of the `LinkedList`.
 398     ///
 399     /// This operation should compute in O(1) time.
 400     ///
 401     /// # Examples
 402     ///
 403     /// ```
 404     /// use std::collections::LinkedList;
 405     ///
 406     /// let mut dl = LinkedList::new();
 407     ///
 408     /// dl.push_front(2);
 409     /// assert_eq!(dl.len(), 1);
 410     ///
 411     /// dl.push_front(1);
 412     /// assert_eq!(dl.len(), 2);
 413     ///
 414     /// dl.push_back(3);
 415     /// assert_eq!(dl.len(), 3);
 416     /// ```
 417     #[inline]
 418     #[stable(feature = "rust1", since = "1.0.0")]
 419     pub fn len(&self) -> usize {
 420         self.len
 421     }
 422
 423     /// Removes all elements from the `LinkedList`.
 424     ///
 425     /// This operation should compute in O(n) time.
 426     ///
 427     /// # Examples
 428     ///
 429     /// ```
 430     /// use std::collections::LinkedList;
 431     ///
 432     /// let mut dl = LinkedList::new();
 433     ///
 434     /// dl.push_front(2);
 435     /// dl.push_front(1);
 436     /// assert_eq!(dl.len(), 2);
 437     /// assert_eq!(dl.front(), Some(&1));
 438     ///
 439     /// dl.clear();
 440     /// assert_eq!(dl.len(), 0);
 441     /// assert_eq!(dl.front(), None);
 442     /// ```
 443     #[inline]
 444     #[stable(feature = "rust1", since = "1.0.0")]
 445     pub fn clear(&mut self) {
 446         *self = Self::new();
 447     }
 448
 449     /// Returns `true` if the `LinkedList` contains an element equal to the
 450     /// given value.
 451     ///
 452     /// # Examples
 453     ///
 454     /// ```
 455     /// use std::collections::LinkedList;
 456     ///
 457     /// let mut list: LinkedList<u32> = LinkedList::new();
 458     ///
 459     /// list.push_back(0);
 460     /// list.push_back(1);
 461     /// list.push_back(2);
 462     ///
 463     /// assert_eq!(list.contains(&0), true);
 464     /// assert_eq!(list.contains(&10), false);
 465     /// ```
 466     #[stable(feature = "linked_list_contains", since = "1.12.0")]
 467     pub fn contains(&self, x: &T) -> bool
 468     where
 469         T: PartialEq<T>,
 470     {
 471         self.iter().any(|e| e == x)
 472     }
 473
 474     /// Provides a reference to the front element, or `None` if the list is
 475     /// empty.
 476     ///
 477     /// # Examples
 478     ///
 479     /// ```
 480     /// use std::collections::LinkedList;
 481     ///
 482     /// let mut dl = LinkedList::new();
 483     /// assert_eq!(dl.front(), None);
 484     ///
 485     /// dl.push_front(1);
 486     /// assert_eq!(dl.front(), Some(&1));
 487     /// ```
 488     #[inline]
 489     #[stable(feature = "rust1", since = "1.0.0")]
 490     pub fn front(&self) -> Option<&T> {
 491         unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
 492     }
 493
 494     /// Provides a mutable reference to the front element, or `None` if the list
 495     /// is empty.
 496     ///
 497     /// # Examples
 498     ///
 499     /// ```
 500     /// use std::collections::LinkedList;
 501     ///
 502     /// let mut dl = LinkedList::new();
 503     /// assert_eq!(dl.front(), None);
 504     ///
 505     /// dl.push_front(1);
 506     /// assert_eq!(dl.front(), Some(&1));
 507     ///
 508     /// match dl.front_mut() {
 509     ///     None => {},
 510     ///     Some(x) => *x = 5,
 511     /// }
 512     /// assert_eq!(dl.front(), Some(&5));
 513     /// ```
 514     #[inline]
 515     #[stable(feature = "rust1", since = "1.0.0")]
 516     pub fn front_mut(&mut self) -> Option<&mut T> {
 517         unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
 518     }
 519
 520     /// Provides a reference to the back element, or `None` if the list is
 521     /// empty.
 522     ///
 523     /// # Examples
 524     ///
 525     /// ```
 526     /// use std::collections::LinkedList;
 527     ///
 528     /// let mut dl = LinkedList::new();
 529     /// assert_eq!(dl.back(), None);
 530     ///
 531     /// dl.push_back(1);
 532     /// assert_eq!(dl.back(), Some(&1));
 533     /// ```
 534     #[inline]
 535     #[stable(feature = "rust1", since = "1.0.0")]
 536     pub fn back(&self) -> Option<&T> {
 537         unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
 538     }
 539
 540     /// Provides a mutable reference to the back element, or `None` if the list
 541     /// is empty.
 542     ///
 543     /// # Examples
 544     ///
 545     /// ```
 546     /// use std::collections::LinkedList;
 547     ///
 548     /// let mut dl = LinkedList::new();
 549     /// assert_eq!(dl.back(), None);
 550     ///
 551     /// dl.push_back(1);
 552     /// assert_eq!(dl.back(), Some(&1));
 553     ///
 554     /// match dl.back_mut() {
 555     ///     None => {},
 556     ///     Some(x) => *x = 5,
 557     /// }
 558     /// assert_eq!(dl.back(), Some(&5));
 559     /// ```
 560     #[inline]
 561     #[stable(feature = "rust1", since = "1.0.0")]
 562     pub fn back_mut(&mut self) -> Option<&mut T> {
 563         unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
 564     }
 565
 566     /// Adds an element first in the list.
 567     ///
 568     /// This operation should compute in O(1) time.
 569     ///
 570     /// # Examples
 571     ///
 572     /// ```
 573     /// use std::collections::LinkedList;
 574     ///
 575     /// let mut dl = LinkedList::new();
 576     ///
 577     /// dl.push_front(2);
 578     /// assert_eq!(dl.front().unwrap(), &2);
 579     ///
 580     /// dl.push_front(1);
 581     /// assert_eq!(dl.front().unwrap(), &1);
 582     /// ```
 583     #[stable(feature = "rust1", since = "1.0.0")]
 584     pub fn push_front(&mut self, elt: T) {
 585         self.push_front_node(box Node::new(elt));
 586     }
 587
 588     /// Removes the first element and returns it, or `None` if the list is
 589     /// empty.
 590     ///
 591     /// This operation should compute in O(1) time.
 592     ///
 593     /// # Examples
 594     ///
 595     /// ```
 596     /// use std::collections::LinkedList;
 597     ///
 598     /// let mut d = LinkedList::new();
 599     /// assert_eq!(d.pop_front(), None);
 600     ///
 601     /// d.push_front(1);
 602     /// d.push_front(3);
 603     /// assert_eq!(d.pop_front(), Some(3));
 604     /// assert_eq!(d.pop_front(), Some(1));
 605     /// assert_eq!(d.pop_front(), None);
 606     /// ```
 607     #[stable(feature = "rust1", since = "1.0.0")]
 608     pub fn pop_front(&mut self) -> Option<T> {
 609         self.pop_front_node().map(Node::into_element)
 610     }
 611
 612     /// Appends an element to the back of a list.
 613     ///
 614     /// This operation should compute in O(1) time.
 615     ///
 616     /// # Examples
 617     ///
 618     /// ```
 619     /// use std::collections::LinkedList;
 620     ///
 621     /// let mut d = LinkedList::new();
 622     /// d.push_back(1);
 623     /// d.push_back(3);
 624     /// assert_eq!(3, *d.back().unwrap());
 625     /// ```
 626     #[stable(feature = "rust1", since = "1.0.0")]
 627     pub fn push_back(&mut self, elt: T) {
 628         self.push_back_node(box Node::new(elt));
 629     }
 630
 631     /// Removes the last element from a list and returns it, or `None` if
 632     /// it is empty.
 633     ///
 634     /// This operation should compute in O(1) time.
 635     ///
 636     /// # Examples
 637     ///
 638     /// ```
 639     /// use std::collections::LinkedList;
 640     ///
 641     /// let mut d = LinkedList::new();
 642     /// assert_eq!(d.pop_back(), None);
 643     /// d.push_back(1);
 644     /// d.push_back(3);
 645     /// assert_eq!(d.pop_back(), Some(3));
 646     /// ```
 647     #[stable(feature = "rust1", since = "1.0.0")]
 648     pub fn pop_back(&mut self) -> Option<T> {
 649         self.pop_back_node().map(Node::into_element)
 650     }
 651
 652     /// Splits the list into two at the given index. Returns everything after the given index,
 653     /// including the index.
 654     ///
 655     /// This operation should compute in O(n) time.
 656     ///
 657     /// # Panics
 658     ///
 659     /// Panics if `at > len`.
 660     ///
 661     /// # Examples
 662     ///
 663     /// ```
 664     /// use std::collections::LinkedList;
 665     ///
 666     /// let mut d = LinkedList::new();
 667     ///
 668     /// d.push_front(1);
 669     /// d.push_front(2);
 670     /// d.push_front(3);
 671     ///
 672     /// let mut splitted = d.split_off(2);
 673     ///
 674     /// assert_eq!(splitted.pop_front(), Some(1));
 675     /// assert_eq!(splitted.pop_front(), None);
 676     /// ```
 677     #[stable(feature = "rust1", since = "1.0.0")]
 678     pub fn split_off(&mut self, at: usize) -> LinkedList<T> {
 679         let len = self.len();
 680         assert!(at <= len, "Cannot split off at a nonexistent index");
 681         if at == 0 {
 682             return mem::take(self);
 683         } else if at == len {
 684             return Self::new();
 685         }
 686
 687         // Below, we iterate towards the `i-1`th node, either from the start or the end,
 688         // depending on which would be faster.
 689         let split_node = if at - 1 <= len - 1 - (at - 1) {
 690             let mut iter = self.iter_mut();
 691             // instead of skipping using .skip() (which creates a new struct),
 692             // we skip manually so we can access the head field without
 693             // depending on implementation details of Skip
 694             for _ in 0..at - 1 {
 695                 iter.next();
 696             }
 697             iter.head
 698         } else {
 699             // better off starting from the end
 700             let mut iter = self.iter_mut();
 701             for _ in 0..len - 1 - (at - 1) {
 702                 iter.next_back();
 703             }
 704             iter.tail
 705         };
 706
 707         // The split node is the new tail node of the first part and owns
 708         // the head of the second part.
 709         let second_part_head;
 710
 711         unsafe {
 712             second_part_head = split_node.unwrap().as_mut().next.take();
 713             if let Some(mut head) = second_part_head {
 714                 head.as_mut().prev = None;
 715             }
 716         }
 717
 718         let second_part = LinkedList {
 719             head: second_part_head,
 720             tail: self.tail,
 721             len: len - at,
 722             marker: PhantomData,
 723         };
 724
 725         // Fix the tail ptr of the first part
 726         self.tail = split_node;
 727         self.len = at;
 728
 729         second_part
 730     }
 731
 732     /// Creates an iterator which uses a closure to determine if an element should be removed.
 733     ///
 734     /// If the closure returns true, then the element is removed and yielded.
 735     /// If the closure returns false, the element will remain in the list and will not be yielded
 736     /// by the iterator.
 737     ///
 738     /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of
 739     /// whether you choose to keep or remove it.
 740     ///
 741     /// # Examples
 742     ///
 743     /// Splitting a list into evens and odds, reusing the original list:
 744     ///
 745     /// ```
 746     /// #![feature(drain_filter)]
 747     /// use std::collections::LinkedList;
 748     ///
 749     /// let mut numbers: LinkedList<u32> = LinkedList::new();
 750     /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
 751     ///
 752     /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>();
 753     /// let odds = numbers;
 754     ///
 755     /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
 756     /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
 757     /// ```
 758     #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 759     pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
 760     where
 761         F: FnMut(&mut T) -> bool,
 762     {
 763         // avoid borrow issues.
 764         let it = self.head;
 765         let old_len = self.len;
 766
 767         DrainFilter { list: self, it: it, pred: filter, idx: 0, old_len: old_len }
 768     }
 769 }
 770
 771 #[stable(feature = "rust1", since = "1.0.0")]
 772 unsafe impl<#[may_dangle] T> Drop for LinkedList<T> {
 773     fn drop(&mut self) {
 774         struct DropGuard<'a, T>(&'a mut LinkedList<T>);
 775
 776         impl<'a, T> Drop for DropGuard<'a, T> {
 777             fn drop(&mut self) {
 778                 // Continue the same loop we do below. This only runs when a destructor has
 779                 // panicked. If another one panics this will abort.
 780                 while let Some(_) = self.0.pop_front_node() {}
 781             }
 782         }
 783
 784         while let Some(node) = self.pop_front_node() {
 785             let guard = DropGuard(self);
 786             drop(node);
 787             mem::forget(guard);
 788         }
 789     }
 790 }
 791
 792 #[stable(feature = "rust1", since = "1.0.0")]
 793 impl<'a, T> Iterator for Iter<'a, T> {
 794     type Item = &'a T;
 795
 796     #[inline]
 797     fn next(&mut self) -> Option<&'a T> {
 798         if self.len == 0 {
 799             None
 800         } else {
 801             self.head.map(|node| unsafe {
 802                 // Need an unbound lifetime to get 'a
 803                 let node = &*node.as_ptr();
 804                 self.len -= 1;
 805                 self.head = node.next;
 806                 &node.element
 807             })
 808         }
 809     }
 810
 811     #[inline]
 812     fn size_hint(&self) -> (usize, Option<usize>) {
 813         (self.len, Some(self.len))
 814     }
 815
 816     #[inline]
 817     fn last(mut self) -> Option<&'a T> {
 818         self.next_back()
 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<T> ExactSizeIterator for Iter<'_, T> {}
 842
 843 #[stable(feature = "fused", since = "1.26.0")]
 844 impl<T> FusedIterator for Iter<'_, 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     #[inline]
 871     fn last(mut self) -> Option<&'a mut T> {
 872         self.next_back()
 873     }
 874 }
 875
 876 #[stable(feature = "rust1", since = "1.0.0")]
 877 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
 878     #[inline]
 879     fn next_back(&mut self) -> Option<&'a mut T> {
 880         if self.len == 0 {
 881             None
 882         } else {
 883             self.tail.map(|node| unsafe {
 884                 // Need an unbound lifetime to get 'a
 885                 let node = &mut *node.as_ptr();
 886                 self.len -= 1;
 887                 self.tail = node.prev;
 888                 &mut node.element
 889             })
 890         }
 891     }
 892 }
 893
 894 #[stable(feature = "rust1", since = "1.0.0")]
 895 impl<T> ExactSizeIterator for IterMut<'_, T> {}
 896
 897 #[stable(feature = "fused", since = "1.26.0")]
 898 impl<T> FusedIterator for IterMut<'_, T> {}
 899
 900 impl<T> IterMut<'_, T> {
 901     /// Inserts the given element just after the element most recently returned by `.next()`.
 902     /// The inserted element does not appear in the iteration.
 903     ///
 904     /// # Examples
 905     ///
 906     /// ```
 907     /// #![feature(linked_list_extras)]
 908     ///
 909     /// use std::collections::LinkedList;
 910     ///
 911     /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
 912     ///
 913     /// {
 914     ///     let mut it = list.iter_mut();
 915     ///     assert_eq!(it.next().unwrap(), &1);
 916     ///     // insert `2` after `1`
 917     ///     it.insert_next(2);
 918     /// }
 919     /// {
 920     ///     let vec: Vec<_> = list.into_iter().collect();
 921     ///     assert_eq!(vec, [1, 2, 3, 4]);
 922     /// }
 923     /// ```
 924     #[inline]
 925     #[unstable(
 926         feature = "linked_list_extras",
 927         reason = "this is probably better handled by a cursor type -- we'll see",
 928         issue = "27794"
 929     )]
 930     pub fn insert_next(&mut self, element: T) {
 931         match self.head {
 932             // `push_back` is okay with aliasing `element` references
 933             None => self.list.push_back(element),
 934             Some(head) => unsafe {
 935                 let prev = match head.as_ref().prev {
 936                     // `push_front` is okay with aliasing nodes
 937                     None => return self.list.push_front(element),
 938                     Some(prev) => prev,
 939                 };
 940
 941                 let node = Some(Box::into_raw_non_null(box Node {
 942                     next: Some(head),
 943                     prev: Some(prev),
 944                     element,
 945                 }));
 946
 947                 // Not creating references to entire nodes to not invalidate the
 948                 // reference to `element` we handed to the user.
 949                 (*prev.as_ptr()).next = node;
 950                 (*head.as_ptr()).prev = node;
 951
 952                 self.list.len += 1;
 953             },
 954         }
 955     }
 956
 957     /// Provides a reference to the next element, without changing the iterator.
 958     ///
 959     /// # Examples
 960     ///
 961     /// ```
 962     /// #![feature(linked_list_extras)]
 963     ///
 964     /// use std::collections::LinkedList;
 965     ///
 966     /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
 967     ///
 968     /// let mut it = list.iter_mut();
 969     /// assert_eq!(it.next().unwrap(), &1);
 970     /// assert_eq!(it.peek_next().unwrap(), &2);
 971     /// // We just peeked at 2, so it was not consumed from the iterator.
 972     /// assert_eq!(it.next().unwrap(), &2);
 973     /// ```
 974     #[inline]
 975     #[unstable(
 976         feature = "linked_list_extras",
 977         reason = "this is probably better handled by a cursor type -- we'll see",
 978         issue = "27794"
 979     )]
 980     pub fn peek_next(&mut self) -> Option<&mut T> {
 981         if self.len == 0 {
 982             None
 983         } else {
 984             unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
 985         }
 986     }
 987 }
 988
 989 /// An iterator produced by calling `drain_filter` on LinkedList.
 990 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 991 pub struct DrainFilter<'a, T: 'a, F: 'a>
 992 where
 993     F: FnMut(&mut T) -> bool,
 994 {
 995     list: &'a mut LinkedList<T>,
 996     it: Option<NonNull<Node<T>>>,
 997     pred: F,
 998     idx: usize,
 999     old_len: usize,
1000 }
1001
1002 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1003 impl<T, F> Iterator for DrainFilter<'_, T, F>
1004 where
1005     F: FnMut(&mut T) -> bool,
1006 {
1007     type Item = T;
1008
1009     fn next(&mut self) -> Option<T> {
1010         while let Some(mut node) = self.it {
1011             unsafe {
1012                 self.it = node.as_ref().next;
1013                 self.idx += 1;
1014
1015                 if (self.pred)(&mut node.as_mut().element) {
1016                     // `unlink_node` is okay with aliasing `element` references.
1017                     self.list.unlink_node(node);
1018                     return Some(Box::from_raw(node.as_ptr()).element);
1019                 }
1020             }
1021         }
1022
1023         None
1024     }
1025
1026     fn size_hint(&self) -> (usize, Option<usize>) {
1027         (0, Some(self.old_len - self.idx))
1028     }
1029 }
1030
1031 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1032 impl<T, F> Drop for DrainFilter<'_, T, F>
1033 where
1034     F: FnMut(&mut T) -> bool,
1035 {
1036     fn drop(&mut self) {
1037         self.for_each(drop);
1038     }
1039 }
1040
1041 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
1042 impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F>
1043 where
1044     F: FnMut(&mut T) -> bool,
1045 {
1046     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1047         f.debug_tuple("DrainFilter").field(&self.list).finish()
1048     }
1049 }
1050
1051 #[stable(feature = "rust1", since = "1.0.0")]
1052 impl<T> Iterator for IntoIter<T> {
1053     type Item = T;
1054
1055     #[inline]
1056     fn next(&mut self) -> Option<T> {
1057         self.list.pop_front()
1058     }
1059
1060     #[inline]
1061     fn size_hint(&self) -> (usize, Option<usize>) {
1062         (self.list.len, Some(self.list.len))
1063     }
1064 }
1065
1066 #[stable(feature = "rust1", since = "1.0.0")]
1067 impl<T> DoubleEndedIterator for IntoIter<T> {
1068     #[inline]
1069     fn next_back(&mut self) -> Option<T> {
1070         self.list.pop_back()
1071     }
1072 }
1073
1074 #[stable(feature = "rust1", since = "1.0.0")]
1075 impl<T> ExactSizeIterator for IntoIter<T> {}
1076
1077 #[stable(feature = "fused", since = "1.26.0")]
1078 impl<T> FusedIterator for IntoIter<T> {}
1079
1080 #[stable(feature = "rust1", since = "1.0.0")]
1081 impl<T> FromIterator<T> for LinkedList<T> {
1082     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1083         let mut list = Self::new();
1084         list.extend(iter);
1085         list
1086     }
1087 }
1088
1089 #[stable(feature = "rust1", since = "1.0.0")]
1090 impl<T> IntoIterator for LinkedList<T> {
1091     type Item = T;
1092     type IntoIter = IntoIter<T>;
1093
1094     /// Consumes the list into an iterator yielding elements by value.
1095     #[inline]
1096     fn into_iter(self) -> IntoIter<T> {
1097         IntoIter { list: self }
1098     }
1099 }
1100
1101 #[stable(feature = "rust1", since = "1.0.0")]
1102 impl<'a, T> IntoIterator for &'a LinkedList<T> {
1103     type Item = &'a T;
1104     type IntoIter = Iter<'a, T>;
1105
1106     fn into_iter(self) -> Iter<'a, T> {
1107         self.iter()
1108     }
1109 }
1110
1111 #[stable(feature = "rust1", since = "1.0.0")]
1112 impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
1113     type Item = &'a mut T;
1114     type IntoIter = IterMut<'a, T>;
1115
1116     fn into_iter(self) -> IterMut<'a, T> {
1117         self.iter_mut()
1118     }
1119 }
1120
1121 #[stable(feature = "rust1", since = "1.0.0")]
1122 impl<T> Extend<T> for LinkedList<T> {
1123     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1124         <Self as SpecExtend<I>>::spec_extend(self, iter);
1125     }
1126 }
1127
1128 impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> {
1129     default fn spec_extend(&mut self, iter: I) {
1130         iter.into_iter().for_each(move |elt| self.push_back(elt));
1131     }
1132 }
1133
1134 impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
1135     fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
1136         self.append(other);
1137     }
1138 }
1139
1140 #[stable(feature = "extend_ref", since = "1.2.0")]
1141 impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> {
1142     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1143         self.extend(iter.into_iter().cloned());
1144     }
1145 }
1146
1147 #[stable(feature = "rust1", since = "1.0.0")]
1148 impl<T: PartialEq> PartialEq for LinkedList<T> {
1149     fn eq(&self, other: &Self) -> bool {
1150         self.len() == other.len() && self.iter().eq(other)
1151     }
1152
1153     fn ne(&self, other: &Self) -> bool {
1154         self.len() != other.len() || self.iter().ne(other)
1155     }
1156 }
1157
1158 #[stable(feature = "rust1", since = "1.0.0")]
1159 impl<T: Eq> Eq for LinkedList<T> {}
1160
1161 #[stable(feature = "rust1", since = "1.0.0")]
1162 impl<T: PartialOrd> PartialOrd for LinkedList<T> {
1163     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1164         self.iter().partial_cmp(other)
1165     }
1166 }
1167
1168 #[stable(feature = "rust1", since = "1.0.0")]
1169 impl<T: Ord> Ord for LinkedList<T> {
1170     #[inline]
1171     fn cmp(&self, other: &Self) -> Ordering {
1172         self.iter().cmp(other)
1173     }
1174 }
1175
1176 #[stable(feature = "rust1", since = "1.0.0")]
1177 impl<T: Clone> Clone for LinkedList<T> {
1178     fn clone(&self) -> Self {
1179         self.iter().cloned().collect()
1180     }
1181
1182     fn clone_from(&mut self, other: &Self) {
1183         let mut iter_other = other.iter();
1184         if self.len() > other.len() {
1185             self.split_off(other.len());
1186         }
1187         for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) {
1188             elem.clone_from(elem_other);
1189         }
1190         if !iter_other.is_empty() {
1191             self.extend(iter_other.cloned());
1192         }
1193     }
1194 }
1195
1196 #[stable(feature = "rust1", since = "1.0.0")]
1197 impl<T: fmt::Debug> fmt::Debug for LinkedList<T> {
1198     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1199         f.debug_list().entries(self).finish()
1200     }
1201 }
1202
1203 #[stable(feature = "rust1", since = "1.0.0")]
1204 impl<T: Hash> Hash for LinkedList<T> {
1205     fn hash<H: Hasher>(&self, state: &mut H) {
1206         self.len().hash(state);
1207         for elt in self {
1208             elt.hash(state);
1209         }
1210     }
1211 }
1212
1213 // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
1214 #[allow(dead_code)]
1215 fn assert_covariance() {
1216     fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
1217         x
1218     }
1219     fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
1220         x
1221     }
1222     fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
1223         x
1224     }
1225 }
1226
1227 #[stable(feature = "rust1", since = "1.0.0")]
1228 unsafe impl<T: Send> Send for LinkedList<T> {}
1229
1230 #[stable(feature = "rust1", since = "1.0.0")]
1231 unsafe impl<T: Sync> Sync for LinkedList<T> {}
1232
1233 #[stable(feature = "rust1", since = "1.0.0")]
1234 unsafe impl<T: Sync> Send for Iter<'_, T> {}
1235
1236 #[stable(feature = "rust1", since = "1.0.0")]
1237 unsafe impl<T: Sync> Sync for Iter<'_, T> {}
1238
1239 #[stable(feature = "rust1", since = "1.0.0")]
1240 unsafe impl<T: Send> Send for IterMut<'_, T> {}
1241
1242 #[stable(feature = "rust1", since = "1.0.0")]
1243 unsafe impl<T: Sync> Sync for IterMut<'_, T> {}