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