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.
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.
11 //! A doubly-linked list with owned nodes.
13 //! The `LinkedList` allows pushing and popping elements at either end and is thus
14 //! efficiently usable as a double-ended queue.
16 #![stable(feature = "rust1", since = "1.0.0")]
18 use alloc::boxed::{Box, IntermediateBox};
19 use core::cmp::Ordering;
21 use core::hash::{Hasher, Hash};
22 use core::iter::FromIterator;
23 use core::marker::PhantomData;
25 use core::ops::{BoxPlace, InPlace, Place, Placer};
26 use core::ptr::{self, Shared};
28 use super::SpecExtend;
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>>>,
36 marker: PhantomData<Box<Node<T>>>,
40 next: Option<Shared<Node<T>>>,
41 prev: Option<Shared<Node<T>>>,
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>>>,
51 marker: PhantomData<&'a Node<T>>,
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 {
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>>>,
71 /// An iterator over the elements of a `LinkedList`.
73 #[stable(feature = "rust1", since = "1.0.0")]
74 pub struct IntoIter<T> {
79 fn new(element: T) -> Self {
87 fn into_element(self: Box<Self>) -> T {
93 impl<T> LinkedList<T> {
94 /// Adds the given node to the front of the list.
96 fn push_front_node(&mut self, mut node: Box<Node<T>>) {
98 node.next = self.head;
100 let node = Some(Shared::new(Box::into_raw(node)));
103 None => self.tail = node,
104 Some(head) => (**head).prev = node,
112 /// Removes and returns the node at the front of the list.
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;
120 None => self.tail = None,
121 Some(head) => (**head).prev = None,
129 /// Adds the given node to the back of the list.
131 fn push_back_node(&mut self, mut node: Box<Node<T>>) {
134 node.prev = self.tail;
135 let node = Some(Shared::new(Box::into_raw(node)));
138 None => self.head = node,
139 Some(tail) => (**tail).next = node,
147 /// Removes and returns the node at the back of the list.
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;
155 None => self.head = None,
156 Some(tail) => (**tail).next = None,
165 #[stable(feature = "rust1", since = "1.0.0")]
166 impl<T> Default for LinkedList<T> {
168 fn default() -> Self {
173 impl<T> LinkedList<T> {
174 /// Creates an empty `LinkedList`.
179 /// use std::collections::LinkedList;
181 /// let list: LinkedList<u32> = LinkedList::new();
184 #[stable(feature = "rust1", since = "1.0.0")]
185 pub fn new() -> Self {
194 /// Moves all elements from `other` to the end of the list.
196 /// This reuses all the nodes from `other` and moves them into `self`. After
197 /// this operation, `other` becomes empty.
199 /// This operation should compute in O(1) time and O(1) memory.
204 /// use std::collections::LinkedList;
206 /// let mut list1 = LinkedList::new();
207 /// list1.push_back('a');
209 /// let mut list2 = LinkedList::new();
210 /// list2.push_back('b');
211 /// list2.push_back('c');
213 /// list1.append(&mut list2);
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());
221 /// assert!(list2.is_empty());
223 #[stable(feature = "rust1", since = "1.0.0")]
224 pub fn append(&mut self, other: &mut Self) {
226 None => mem::swap(self, other),
227 Some(tail) => if let Some(other_head) = other.head.take() {
229 (**tail).next = Some(other_head);
230 (**other_head).prev = Some(tail);
233 self.tail = other.tail.take();
234 self.len += mem::replace(&mut other.len, 0);
239 /// Provides a forward iterator.
244 /// use std::collections::LinkedList;
246 /// let mut list: LinkedList<u32> = LinkedList::new();
248 /// list.push_back(0);
249 /// list.push_back(1);
250 /// list.push_back(2);
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);
259 #[stable(feature = "rust1", since = "1.0.0")]
260 pub fn iter(&self) -> Iter<T> {
269 /// Provides a forward iterator with mutable references.
274 /// use std::collections::LinkedList;
276 /// let mut list: LinkedList<u32> = LinkedList::new();
278 /// list.push_back(0);
279 /// list.push_back(1);
280 /// list.push_back(2);
282 /// for element in list.iter_mut() {
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);
293 #[stable(feature = "rust1", since = "1.0.0")]
294 pub fn iter_mut(&mut self) -> IterMut<T> {
303 /// Returns `true` if the `LinkedList` is empty.
305 /// This operation should compute in O(1) time.
310 /// use std::collections::LinkedList;
312 /// let mut dl = LinkedList::new();
313 /// assert!(dl.is_empty());
315 /// dl.push_front("foo");
316 /// assert!(!dl.is_empty());
319 #[stable(feature = "rust1", since = "1.0.0")]
320 pub fn is_empty(&self) -> bool {
324 /// Returns the length of the `LinkedList`.
326 /// This operation should compute in O(1) time.
331 /// use std::collections::LinkedList;
333 /// let mut dl = LinkedList::new();
335 /// dl.push_front(2);
336 /// assert_eq!(dl.len(), 1);
338 /// dl.push_front(1);
339 /// assert_eq!(dl.len(), 2);
342 /// assert_eq!(dl.len(), 3);
345 #[stable(feature = "rust1", since = "1.0.0")]
346 pub fn len(&self) -> usize {
350 /// Removes all elements from the `LinkedList`.
352 /// This operation should compute in O(n) time.
357 /// use std::collections::LinkedList;
359 /// let mut dl = LinkedList::new();
361 /// dl.push_front(2);
362 /// dl.push_front(1);
363 /// assert_eq!(dl.len(), 2);
364 /// assert_eq!(dl.front(), Some(&1));
367 /// assert_eq!(dl.len(), 0);
368 /// assert_eq!(dl.front(), None);
371 #[stable(feature = "rust1", since = "1.0.0")]
372 pub fn clear(&mut self) {
376 /// Returns `true` if the `LinkedList` contains an element equal to the
382 /// #![feature(linked_list_contains)]
384 /// use std::collections::LinkedList;
386 /// let mut list: LinkedList<u32> = LinkedList::new();
388 /// list.push_back(0);
389 /// list.push_back(1);
390 /// list.push_back(2);
392 /// assert_eq!(list.contains(&0), true);
393 /// assert_eq!(list.contains(&10), false);
395 #[unstable(feature = "linked_list_contains", reason = "recently added",
397 pub fn contains(&self, x: &T) -> bool
398 where T: PartialEq<T>
400 self.iter().any(|e| e == x)
403 /// Provides a reference to the front element, or `None` if the list is
409 /// use std::collections::LinkedList;
411 /// let mut dl = LinkedList::new();
412 /// assert_eq!(dl.front(), None);
414 /// dl.push_front(1);
415 /// assert_eq!(dl.front(), Some(&1));
418 #[stable(feature = "rust1", since = "1.0.0")]
419 pub fn front(&self) -> Option<&T> {
420 self.head.map(|node| unsafe { &(**node).element })
423 /// Provides a mutable reference to the front element, or `None` if the list
429 /// use std::collections::LinkedList;
431 /// let mut dl = LinkedList::new();
432 /// assert_eq!(dl.front(), None);
434 /// dl.push_front(1);
435 /// assert_eq!(dl.front(), Some(&1));
437 /// match dl.front_mut() {
439 /// Some(x) => *x = 5,
441 /// assert_eq!(dl.front(), Some(&5));
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 })
449 /// Provides a reference to the back element, or `None` if the list is
455 /// use std::collections::LinkedList;
457 /// let mut dl = LinkedList::new();
458 /// assert_eq!(dl.back(), None);
461 /// assert_eq!(dl.back(), Some(&1));
464 #[stable(feature = "rust1", since = "1.0.0")]
465 pub fn back(&self) -> Option<&T> {
466 self.tail.map(|node| unsafe { &(**node).element })
469 /// Provides a mutable reference to the back element, or `None` if the list
475 /// use std::collections::LinkedList;
477 /// let mut dl = LinkedList::new();
478 /// assert_eq!(dl.back(), None);
481 /// assert_eq!(dl.back(), Some(&1));
483 /// match dl.back_mut() {
485 /// Some(x) => *x = 5,
487 /// assert_eq!(dl.back(), Some(&5));
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 })
495 /// Adds an element first in the list.
497 /// This operation should compute in O(1) time.
502 /// use std::collections::LinkedList;
504 /// let mut dl = LinkedList::new();
506 /// dl.push_front(2);
507 /// assert_eq!(dl.front().unwrap(), &2);
509 /// dl.push_front(1);
510 /// assert_eq!(dl.front().unwrap(), &1);
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));
517 /// Removes the first element and returns it, or `None` if the list is
520 /// This operation should compute in O(1) time.
525 /// use std::collections::LinkedList;
527 /// let mut d = LinkedList::new();
528 /// assert_eq!(d.pop_front(), None);
532 /// assert_eq!(d.pop_front(), Some(3));
533 /// assert_eq!(d.pop_front(), Some(1));
534 /// assert_eq!(d.pop_front(), None);
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)
541 /// Appends an element to the back of a list
546 /// use std::collections::LinkedList;
548 /// let mut d = LinkedList::new();
551 /// assert_eq!(3, *d.back().unwrap());
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));
558 /// Removes the last element from a list and returns it, or `None` if
564 /// use std::collections::LinkedList;
566 /// let mut d = LinkedList::new();
567 /// assert_eq!(d.pop_back(), None);
570 /// assert_eq!(d.pop_back(), Some(3));
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)
577 /// Splits the list into two at the given index. Returns everything after the given index,
578 /// including the index.
582 /// Panics if `at > len`.
584 /// This operation should compute in O(n) time.
589 /// use std::collections::LinkedList;
591 /// let mut d = LinkedList::new();
597 /// let mut splitted = d.split_off(2);
599 /// assert_eq!(splitted.pop_front(), Some(1));
600 /// assert_eq!(splitted.pop_front(), None);
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");
607 return mem::replace(self, Self::new());
608 } else if at == len {
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
624 // better off starting from the end
625 let mut iter = self.iter_mut();
626 for _ in 0..len - 1 - (at - 1) {
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;
637 second_part_head = (**split_node.unwrap()).next.take();
638 if let Some(head) = second_part_head {
639 (**head).prev = None;
643 let second_part = LinkedList {
644 head: second_part_head,
650 // Fix the tail ptr of the first part
651 self.tail = split_node;
657 /// Returns a place for insertion at the front of the list.
659 /// Using this method with placement syntax is equivalent to [`push_front`]
660 /// (#method.push_front), but may be more efficient.
665 /// #![feature(collection_placement)]
666 /// #![feature(placement_in_syntax)]
668 /// use std::collections::LinkedList;
670 /// let mut list = LinkedList::new();
671 /// list.front_place() <- 2;
672 /// list.front_place() <- 4;
673 /// assert!(list.iter().eq(&[4, 2]));
675 #[unstable(feature = "collection_placement",
676 reason = "method name and placement protocol are subject to change",
678 pub fn front_place(&mut self) -> FrontPlace<T> {
679 FrontPlace { list: self, node: IntermediateBox::make_place() }
682 /// Returns a place for insertion at the back of the list.
684 /// Using this method with placement syntax is equivalent to [`push_back`](#method.push_back),
685 /// but may be more efficient.
690 /// #![feature(collection_placement)]
691 /// #![feature(placement_in_syntax)]
693 /// use std::collections::LinkedList;
695 /// let mut list = LinkedList::new();
696 /// list.back_place() <- 2;
697 /// list.back_place() <- 4;
698 /// assert!(list.iter().eq(&[2, 4]));
700 #[unstable(feature = "collection_placement",
701 reason = "method name and placement protocol are subject to change",
703 pub fn back_place(&mut self) -> BackPlace<T> {
704 BackPlace { list: self, node: IntermediateBox::make_place() }
708 #[stable(feature = "rust1", since = "1.0.0")]
709 impl<T> Drop for LinkedList<T> {
710 #[unsafe_destructor_blind_to_params]
712 while let Some(_) = self.pop_front_node() {}
716 #[stable(feature = "rust1", since = "1.0.0")]
717 impl<'a, T> Iterator for Iter<'a, T> {
721 fn next(&mut self) -> Option<&'a T> {
725 self.head.map(|node| unsafe {
728 self.head = node.next;
735 fn size_hint(&self) -> (usize, Option<usize>) {
736 (self.len, Some(self.len))
740 #[stable(feature = "rust1", since = "1.0.0")]
741 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
743 fn next_back(&mut self) -> Option<&'a T> {
747 self.tail.map(|node| unsafe {
750 self.tail = node.prev;
757 #[stable(feature = "rust1", since = "1.0.0")]
758 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
760 #[stable(feature = "rust1", since = "1.0.0")]
761 impl<'a, T> Iterator for IterMut<'a, T> {
762 type Item = &'a mut T;
765 fn next(&mut self) -> Option<&'a mut T> {
769 self.head.map(|node| unsafe {
770 let node = &mut **node;
772 self.head = node.next;
779 fn size_hint(&self) -> (usize, Option<usize>) {
780 (self.len, Some(self.len))
784 #[stable(feature = "rust1", since = "1.0.0")]
785 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
787 fn next_back(&mut self) -> Option<&'a mut T> {
791 self.tail.map(|node| unsafe {
792 let node = &mut **node;
794 self.tail = node.prev;
801 #[stable(feature = "rust1", since = "1.0.0")]
802 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
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.
811 /// #![feature(linked_list_extras)]
813 /// use std::collections::LinkedList;
815 /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
818 /// let mut it = list.iter_mut();
819 /// assert_eq!(it.next().unwrap(), &1);
820 /// // insert `2` after `1`
821 /// it.insert_next(2);
824 /// let vec: Vec<_> = list.into_iter().collect();
825 /// assert_eq!(vec, [1, 2, 3, 4]);
829 #[unstable(feature = "linked_list_extras",
830 reason = "this is probably better handled by a cursor type -- we'll see",
832 pub fn insert_next(&mut self, element: T) {
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),
841 let node = Some(Shared::new(Box::into_raw(box Node {
847 (**prev).next = node;
848 (**head).prev = node;
855 /// Provides a reference to the next element, without changing the iterator.
860 /// #![feature(linked_list_extras)]
862 /// use std::collections::LinkedList;
864 /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
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);
873 #[unstable(feature = "linked_list_extras",
874 reason = "this is probably better handled by a cursor type -- we'll see",
876 pub fn peek_next(&mut self) -> Option<&mut T> {
880 self.head.map(|node| unsafe { &mut (**node).element })
885 #[stable(feature = "rust1", since = "1.0.0")]
886 impl<T> Iterator for IntoIter<T> {
890 fn next(&mut self) -> Option<T> {
891 self.list.pop_front()
895 fn size_hint(&self) -> (usize, Option<usize>) {
896 (self.list.len, Some(self.list.len))
900 #[stable(feature = "rust1", since = "1.0.0")]
901 impl<T> DoubleEndedIterator for IntoIter<T> {
903 fn next_back(&mut self) -> Option<T> {
908 #[stable(feature = "rust1", since = "1.0.0")]
909 impl<T> ExactSizeIterator for IntoIter<T> {}
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();
920 #[stable(feature = "rust1", since = "1.0.0")]
921 impl<T> IntoIterator for LinkedList<T> {
923 type IntoIter = IntoIter<T>;
925 /// Consumes the list into an iterator yielding elements by value.
927 fn into_iter(self) -> IntoIter<T> {
928 IntoIter { list: self }
932 #[stable(feature = "rust1", since = "1.0.0")]
933 impl<'a, T> IntoIterator for &'a LinkedList<T> {
935 type IntoIter = Iter<'a, T>;
937 fn into_iter(self) -> Iter<'a, T> {
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>;
947 fn into_iter(self) -> IterMut<'a, T> {
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);
959 impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> {
960 default fn spec_extend(&mut self, iter: I) {
967 impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
968 fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
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());
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)
986 fn ne(&self, other: &Self) -> bool {
987 self.len() != other.len() || self.iter().ne(other)
991 #[stable(feature = "rust1", since = "1.0.0")]
992 impl<T: Eq> Eq for LinkedList<T> {}
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)
1001 #[stable(feature = "rust1", since = "1.0.0")]
1002 impl<T: Ord> Ord for LinkedList<T> {
1004 fn cmp(&self, other: &Self) -> Ordering {
1005 self.iter().cmp(other)
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()
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()
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);
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);
1040 /// A place for insertion at the front of a `LinkedList`.
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",
1047 pub struct FrontPlace<'a, T: 'a> {
1048 list: &'a mut LinkedList<T>,
1049 node: IntermediateBox<Node<T>>,
1052 #[unstable(feature = "collection_placement",
1053 reason = "placement protocol is subject to change",
1055 impl<'a, T> Placer<T> for FrontPlace<'a, T> {
1058 fn make_place(self) -> Self {
1063 #[unstable(feature = "collection_placement",
1064 reason = "placement protocol is subject to change",
1066 impl<'a, T> Place<T> for FrontPlace<'a, T> {
1067 fn pointer(&mut self) -> *mut T {
1068 unsafe { &mut (*self.node.pointer()).element }
1072 #[unstable(feature = "collection_placement",
1073 reason = "placement protocol is subject to change",
1075 impl<'a, T> InPlace<T> for FrontPlace<'a, T> {
1078 unsafe fn finalize(self) {
1079 let FrontPlace { list, node } = self;
1080 list.push_front_node(finalize(node));
1084 /// A place for insertion at the back of a `LinkedList`.
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",
1091 pub struct BackPlace<'a, T: 'a> {
1092 list: &'a mut LinkedList<T>,
1093 node: IntermediateBox<Node<T>>,
1096 #[unstable(feature = "collection_placement",
1097 reason = "placement protocol is subject to change",
1099 impl<'a, T> Placer<T> for BackPlace<'a, T> {
1102 fn make_place(self) -> Self {
1107 #[unstable(feature = "collection_placement",
1108 reason = "placement protocol is subject to change",
1110 impl<'a, T> Place<T> for BackPlace<'a, T> {
1111 fn pointer(&mut self) -> *mut T {
1112 unsafe { &mut (*self.node.pointer()).element }
1116 #[unstable(feature = "collection_placement",
1117 reason = "placement protocol is subject to change",
1119 impl<'a, T> InPlace<T> for BackPlace<'a, T> {
1122 unsafe fn finalize(self) {
1123 let BackPlace { list, node } = self;
1124 list.push_back_node(finalize(node));
1128 // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
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 }
1136 #[stable(feature = "rust1", since = "1.0.0")]
1137 unsafe impl<T: Send> Send for LinkedList<T> {}
1139 #[stable(feature = "rust1", since = "1.0.0")]
1140 unsafe impl<T: Sync> Sync for LinkedList<T> {}
1142 #[stable(feature = "rust1", since = "1.0.0")]
1143 unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
1145 #[stable(feature = "rust1", since = "1.0.0")]
1146 unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
1148 #[stable(feature = "rust1", since = "1.0.0")]
1149 unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
1151 #[stable(feature = "rust1", since = "1.0.0")]
1152 unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
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};
1163 use super::{LinkedList, Node};
1166 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
1167 v.iter().cloned().collect()
1170 pub fn check_links<T>(list: &LinkedList<T>) {
1173 let mut last_ptr: Option<&Node<T>> = None;
1174 let mut node_ptr: &Node<T>;
1177 assert_eq!(0, list.len);
1180 Some(node) => node_ptr = &**node,
1183 match (last_ptr, node_ptr.prev) {
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>);
1189 _ => panic!("prev link is none, not good"),
1191 match node_ptr.next {
1193 last_ptr = Some(node_ptr);
1203 assert_eq!(len, list.len);
1211 let mut m = LinkedList::<i32>::new();
1212 let mut n = LinkedList::new();
1215 assert_eq!(m.len(), 0);
1216 assert_eq!(n.len(), 0);
1218 // Non-empty to empty
1220 let mut m = LinkedList::new();
1221 let mut n = LinkedList::new();
1225 assert_eq!(m.len(), 1);
1226 assert_eq!(m.pop_back(), Some(2));
1227 assert_eq!(n.len(), 0);
1230 // Empty to non-empty
1232 let mut m = LinkedList::new();
1233 let mut n = LinkedList::new();
1237 assert_eq!(m.len(), 1);
1238 assert_eq!(m.pop_back(), Some(2));
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);
1250 sum.extend_from_slice(&u);
1251 assert_eq!(sum.len(), m.len());
1253 assert_eq!(m.pop_front(), Some(elt))
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
1259 assert_eq!(n.len(), 1);
1260 assert_eq!(n.pop_front(), Some(3));
1265 fn test_insert_prev() {
1266 let mut m = list_from(&[0, 2, 4, 6, 8]);
1269 let mut it = m.iter_mut();
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),
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]);
1294 let n = list_from(&[1, 2, 3]);
1295 thread::spawn(move || {
1297 let a: &[_] = &[&1, &2, &3];
1298 assert_eq!(a, &n.iter().collect::<Vec<_>>()[..]);
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
1321 // https://github.com/rust-lang/rust/issues/26021
1322 let mut v1 = LinkedList::new();
1327 let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
1328 assert_eq!(v1.len(), 3);
1330 assert_eq!(v1.iter().len(), 3);
1331 assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
1335 fn test_split_off() {
1336 let mut v1 = LinkedList::new();
1343 for ix in 0..1 + v1.len() {
1344 let mut a = v1.clone();
1345 let b = a.split_off(ix);
1354 fn fuzz_test(sz: i32) {
1355 let mut m: LinkedList<_> = LinkedList::new();
1359 let r: u8 = thread_rng().next_u32() as u8;
1385 for (a, &b) in m.into_iter().zip(&v) {
1389 assert_eq!(i, v.len());