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