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