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 // 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.
19 // Backlinks over LinkedList::prev are raw pointers that form a full chain in
20 // the reverse direction.
22 #![stable(feature = "rust1", since = "1.0.0")]
26 use alloc
::boxed
::Box
;
27 use core
::cmp
::Ordering
;
29 use core
::hash
::{Hasher, Hash}
;
30 use core
::iter
::{self, FromIterator}
;
34 /// A doubly-linked list.
35 #[stable(feature = "rust1", since = "1.0.0")]
36 pub struct LinkedList
<T
> {
39 list_tail
: Rawlink
<Node
<T
>>,
42 type Link
<T
> = Option
<Box
<Node
<T
>>>;
48 impl<T
> Copy
for Rawlink
<T
> {}
49 unsafe impl<T
:Send
> Send
for Rawlink
<T
> {}
50 unsafe impl<T
:Sync
> Sync
for Rawlink
<T
> {}
54 prev
: Rawlink
<Node
<T
>>,
58 /// An iterator over references to the items of a `LinkedList`.
59 #[stable(feature = "rust1", since = "1.0.0")]
60 pub struct Iter
<'a
, T
:'a
> {
62 tail
: Rawlink
<Node
<T
>>,
66 // FIXME #19839: deriving is too aggressive on the bounds (T doesn't need to be Clone).
67 #[stable(feature = "rust1", since = "1.0.0")]
68 impl<'a
, T
> Clone
for Iter
<'a
, T
> {
69 fn clone(&self) -> Iter
<'a
, T
> {
71 head
: self.head
.clone(),
78 /// An iterator over mutable references to the items of a `LinkedList`.
79 #[stable(feature = "rust1", since = "1.0.0")]
80 pub struct IterMut
<'a
, T
:'a
> {
81 list
: &'a
mut LinkedList
<T
>,
82 head
: Rawlink
<Node
<T
>>,
83 tail
: Rawlink
<Node
<T
>>,
87 /// An iterator over mutable references to the items of a `LinkedList`.
89 #[stable(feature = "rust1", since = "1.0.0")]
90 pub struct IntoIter
<T
> {
94 /// Rawlink is a type like Option<T> but for holding a raw pointer
96 /// Like Option::None for Rawlink
97 fn none() -> Rawlink
<T
> {
98 Rawlink{p: ptr::null_mut()}
101 /// Like Option::Some for Rawlink
102 fn some(n
: &mut T
) -> Rawlink
<T
> {
106 /// Convert the `Rawlink` into an Option value
107 fn resolve_immut
<'a
>(&self) -> Option
<&'a T
> {
109 mem
::transmute(self.p
.as_ref())
113 /// Convert the `Rawlink` into an Option value
114 fn resolve
<'a
>(&mut self) -> Option
<&'a
mut T
> {
115 if self.p
.is_null() {
118 Some(unsafe { mem::transmute(self.p) }
)
122 /// Return the `Rawlink` and replace with `Rawlink::none()`
123 fn take(&mut self) -> Rawlink
<T
> {
124 mem
::replace(self, Rawlink
::none())
128 impl<T
> Clone
for Rawlink
<T
> {
130 fn clone(&self) -> Rawlink
<T
> {
136 fn new(v
: T
) -> Node
<T
> {
137 Node{value: v, next: None, prev: Rawlink::none()}
141 /// Set the .prev field on `next`, then return `Some(next)`
142 fn link_with_prev
<T
>(mut next
: Box
<Node
<T
>>, prev
: Rawlink
<Node
<T
>>)
149 impl<T
> LinkedList
<T
> {
150 /// Add a Node first in the list
152 fn push_front_node(&mut self, mut new_head
: Box
<Node
<T
>>) {
153 match self.list_head
{
155 self.list_tail
= Rawlink
::some(&mut *new_head
);
156 self.list_head
= link_with_prev(new_head
, Rawlink
::none());
158 Some(ref mut head
) => {
159 new_head
.prev
= Rawlink
::none();
160 head
.prev
= Rawlink
::some(&mut *new_head
);
161 mem
::swap(head
, &mut new_head
);
162 head
.next
= Some(new_head
);
168 /// Remove the first Node and return it, or None if the list is empty
170 fn pop_front_node(&mut self) -> Option
<Box
<Node
<T
>>> {
171 self.list_head
.take().map(|mut front_node
| {
173 match front_node
.next
.take() {
174 Some(node
) => self.list_head
= link_with_prev(node
, Rawlink
::none()),
175 None
=> self.list_tail
= Rawlink
::none()
181 /// Add a Node last in the list
183 fn push_back_node(&mut self, mut new_tail
: Box
<Node
<T
>>) {
184 match self.list_tail
.resolve() {
185 None
=> return self.push_front_node(new_tail
),
187 self.list_tail
= Rawlink
::some(&mut *new_tail
);
188 tail
.next
= link_with_prev(new_tail
, Rawlink
::some(tail
));
194 /// Remove the last Node and return it, or None if the list is empty
196 fn pop_back_node(&mut self) -> Option
<Box
<Node
<T
>>> {
197 self.list_tail
.resolve().map_or(None
, |tail
| {
199 self.list_tail
= tail
.prev
;
200 match tail
.prev
.resolve() {
201 None
=> self.list_head
.take(),
202 Some(tail_prev
) => tail_prev
.next
.take()
208 #[stable(feature = "rust1", since = "1.0.0")]
209 impl<T
> Default
for LinkedList
<T
> {
211 #[stable(feature = "rust1", since = "1.0.0")]
212 fn default() -> LinkedList
<T
> { LinkedList::new() }
215 impl<T
> LinkedList
<T
> {
216 /// Creates an empty `LinkedList`.
218 #[stable(feature = "rust1", since = "1.0.0")]
219 pub fn new() -> LinkedList
<T
> {
220 LinkedList{list_head: None, list_tail: Rawlink::none(), length: 0}
223 /// Moves all elements from `other` to the end of the list.
225 /// This reuses all the nodes from `other` and moves them into `self`. After
226 /// this operation, `other` becomes empty.
228 /// This operation should compute in O(1) time and O(1) memory.
233 /// # #![feature(collections)]
234 /// use std::collections::LinkedList;
236 /// let mut a = LinkedList::new();
237 /// let mut b = LinkedList::new();
243 /// a.append(&mut b);
245 /// for e in a.iter() {
246 /// println!("{}", e); // prints 1, then 2, then 3, then 4
248 /// println!("{}", b.len()); // prints 0
250 #[stable(feature = "rust1", since = "1.0.0")]
251 pub fn append(&mut self, other
: &mut LinkedList
<T
>) {
252 match self.list_tail
.resolve() {
254 self.length
= other
.length
;
255 self.list_head
= other
.list_head
.take();
256 self.list_tail
= other
.list_tail
.take();
259 // Carefully empty `other`.
260 let o_tail
= other
.list_tail
.take();
261 let o_length
= other
.length
;
262 match other
.list_head
.take() {
265 tail
.next
= link_with_prev(node
, self.list_tail
);
266 self.list_tail
= o_tail
;
267 self.length
+= o_length
;
275 /// Provides a forward iterator.
277 #[stable(feature = "rust1", since = "1.0.0")]
278 pub fn iter(&self) -> Iter
<T
> {
279 Iter{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
282 /// Provides a forward iterator with mutable references.
284 #[stable(feature = "rust1", since = "1.0.0")]
285 pub fn iter_mut(&mut self) -> IterMut
<T
> {
286 let head_raw
= match self.list_head
{
287 Some(ref mut h
) => Rawlink
::some(&mut **h
),
288 None
=> Rawlink
::none(),
293 tail
: self.list_tail
,
298 /// Returns `true` if the `LinkedList` is empty.
300 /// This operation should compute in O(1) time.
305 /// use std::collections::LinkedList;
307 /// let mut dl = LinkedList::new();
308 /// assert!(dl.is_empty());
310 /// dl.push_front("foo");
311 /// assert!(!dl.is_empty());
314 #[stable(feature = "rust1", since = "1.0.0")]
315 pub fn is_empty(&self) -> bool
{
316 self.list_head
.is_none()
319 /// Returns the length of the `LinkedList`.
321 /// This operation should compute in O(1) time.
326 /// use std::collections::LinkedList;
328 /// let mut dl = LinkedList::new();
330 /// dl.push_front(2);
331 /// assert_eq!(dl.len(), 1);
333 /// dl.push_front(1);
334 /// assert_eq!(dl.len(), 2);
337 /// assert_eq!(dl.len(), 3);
341 #[stable(feature = "rust1", since = "1.0.0")]
342 pub fn len(&self) -> usize {
346 /// Removes all elements from the `LinkedList`.
348 /// This operation should compute in O(n) time.
353 /// use std::collections::LinkedList;
355 /// let mut dl = LinkedList::new();
357 /// dl.push_front(2);
358 /// dl.push_front(1);
359 /// assert_eq!(dl.len(), 2);
360 /// assert_eq!(dl.front(), Some(&1));
363 /// assert_eq!(dl.len(), 0);
364 /// assert_eq!(dl.front(), None);
368 #[stable(feature = "rust1", since = "1.0.0")]
369 pub fn clear(&mut self) {
370 *self = LinkedList
::new()
373 /// Provides a reference to the front element, or `None` if the list is
379 /// use std::collections::LinkedList;
381 /// let mut dl = LinkedList::new();
382 /// assert_eq!(dl.front(), None);
384 /// dl.push_front(1);
385 /// assert_eq!(dl.front(), Some(&1));
389 #[stable(feature = "rust1", since = "1.0.0")]
390 pub fn front(&self) -> Option
<&T
> {
391 self.list_head
.as_ref().map(|head
| &head
.value
)
394 /// Provides a mutable reference to the front element, or `None` if the list
400 /// use std::collections::LinkedList;
402 /// let mut dl = LinkedList::new();
403 /// assert_eq!(dl.front(), None);
405 /// dl.push_front(1);
406 /// assert_eq!(dl.front(), Some(&1));
408 /// match dl.front_mut() {
410 /// Some(x) => *x = 5,
412 /// assert_eq!(dl.front(), Some(&5));
416 #[stable(feature = "rust1", since = "1.0.0")]
417 pub fn front_mut(&mut self) -> Option
<&mut T
> {
418 self.list_head
.as_mut().map(|head
| &mut head
.value
)
421 /// Provides a reference to the back element, or `None` if the list is
427 /// use std::collections::LinkedList;
429 /// let mut dl = LinkedList::new();
430 /// assert_eq!(dl.back(), None);
433 /// assert_eq!(dl.back(), Some(&1));
437 #[stable(feature = "rust1", since = "1.0.0")]
438 pub fn back(&self) -> Option
<&T
> {
439 self.list_tail
.resolve_immut().as_ref().map(|tail
| &tail
.value
)
442 /// Provides a mutable reference to the back element, or `None` if the list
448 /// use std::collections::LinkedList;
450 /// let mut dl = LinkedList::new();
451 /// assert_eq!(dl.back(), None);
454 /// assert_eq!(dl.back(), Some(&1));
456 /// match dl.back_mut() {
458 /// Some(x) => *x = 5,
460 /// assert_eq!(dl.back(), Some(&5));
464 #[stable(feature = "rust1", since = "1.0.0")]
465 pub fn back_mut(&mut self) -> Option
<&mut T
> {
466 self.list_tail
.resolve().map(|tail
| &mut tail
.value
)
469 /// Adds an element first in the list.
471 /// This operation should compute in O(1) time.
476 /// # #![feature(collections)]
477 /// use std::collections::LinkedList;
479 /// let mut dl = LinkedList::new();
481 /// dl.push_front(2);
482 /// assert_eq!(dl.front().unwrap(), &2);
484 /// dl.push_front(1);
485 /// assert_eq!(dl.front().unwrap(), &1);
488 #[stable(feature = "rust1", since = "1.0.0")]
489 pub fn push_front(&mut self, elt
: T
) {
490 self.push_front_node(box Node
::new(elt
))
493 /// Removes the first element and returns it, or `None` if the list is
496 /// This operation should compute in O(1) time.
501 /// use std::collections::LinkedList;
503 /// let mut d = LinkedList::new();
504 /// assert_eq!(d.pop_front(), None);
508 /// assert_eq!(d.pop_front(), Some(3));
509 /// assert_eq!(d.pop_front(), Some(1));
510 /// assert_eq!(d.pop_front(), None);
514 #[stable(feature = "rust1", since = "1.0.0")]
515 pub fn pop_front(&mut self) -> Option
<T
> {
516 self.pop_front_node().map(|box Node{value, ..}
| value
)
519 /// Appends an element to the back of a list
524 /// # #![feature(collections)]
525 /// use std::collections::LinkedList;
527 /// let mut d = LinkedList::new();
530 /// assert_eq!(3, *d.back().unwrap());
532 #[stable(feature = "rust1", since = "1.0.0")]
533 pub fn push_back(&mut self, elt
: T
) {
534 self.push_back_node(box Node
::new(elt
))
537 /// Removes the last element from a list and returns it, or `None` if
543 /// # #![feature(collections)]
544 /// use std::collections::LinkedList;
546 /// let mut d = LinkedList::new();
547 /// assert_eq!(d.pop_back(), None);
550 /// assert_eq!(d.pop_back(), Some(3));
552 #[stable(feature = "rust1", since = "1.0.0")]
553 pub fn pop_back(&mut self) -> Option
<T
> {
554 self.pop_back_node().map(|box Node{value, ..}
| value
)
557 /// Splits the list into two at the given index. Returns everything after the given index,
558 /// including the index.
562 /// Panics if `at > len`.
564 /// This operation should compute in O(n) time.
569 /// # #![feature(collections)]
570 /// use std::collections::LinkedList;
572 /// let mut d = LinkedList::new();
578 /// let mut splitted = d.split_off(2);
580 /// assert_eq!(splitted.pop_front(), Some(1));
581 /// assert_eq!(splitted.pop_front(), None);
583 #[stable(feature = "rust1", since = "1.0.0")]
584 pub fn split_off(&mut self, at
: usize) -> LinkedList
<T
> {
585 let len
= self.len();
586 assert
!(at
<= len
, "Cannot split off at a nonexistent index");
588 return mem
::replace(self, LinkedList
::new());
589 } else if at
== len
{
590 return LinkedList
::new();
593 // Below, we iterate towards the `i-1`th node, either from the start or the end,
594 // depending on which would be faster.
595 let mut split_node
= if at
- 1 <= len
- 1 - (at
- 1) {
596 let mut iter
= self.iter_mut();
597 // instead of skipping using .skip() (which creates a new struct),
598 // we skip manually so we can access the head field without
599 // depending on implementation details of Skip
605 // better off starting from the end
606 let mut iter
= self.iter_mut();
607 for _
in 0..len
- 1 - (at
- 1) {
613 let mut splitted_list
= LinkedList
{
615 list_tail
: self.list_tail
,
619 // Swap split_node.next with list_head (which is None), nulling out split_node.next,
620 // as it is the new tail.
621 mem
::swap(&mut split_node
.resolve().unwrap().next
, &mut splitted_list
.list_head
);
622 // Null out list_head.prev. Note this `unwrap` won't fail because if at == len
623 // we already branched out at the top of the fn to return the empty list.
624 splitted_list
.list_head
.as_mut().unwrap().prev
= Rawlink
::none();
626 self.list_tail
= split_node
;
633 #[stable(feature = "rust1", since = "1.0.0")]
634 impl<T
> Drop
for LinkedList
<T
> {
636 // Dissolve the linked_list in backwards direction
637 // Just dropping the list_head can lead to stack exhaustion
638 // when length is >> 1_000_000
639 let mut tail
= self.list_tail
;
641 match tail
.resolve() {
644 prev
.next
.take(); // release Box<Node<T>>
650 self.list_head
= None
;
651 self.list_tail
= Rawlink
::none();
655 #[stable(feature = "rust1", since = "1.0.0")]
656 impl<'a
, A
> Iterator
for Iter
<'a
, A
> {
660 fn next(&mut self) -> Option
<&'a A
> {
664 self.head
.as_ref().map(|head
| {
666 self.head
= &head
.next
;
672 fn size_hint(&self) -> (usize, Option
<usize>) {
673 (self.nelem
, Some(self.nelem
))
677 #[stable(feature = "rust1", since = "1.0.0")]
678 impl<'a
, A
> DoubleEndedIterator
for Iter
<'a
, A
> {
680 fn next_back(&mut self) -> Option
<&'a A
> {
684 self.tail
.resolve_immut().as_ref().map(|prev
| {
686 self.tail
= prev
.prev
;
692 #[stable(feature = "rust1", since = "1.0.0")]
693 impl<'a
, A
> ExactSizeIterator
for Iter
<'a
, A
> {}
695 #[stable(feature = "rust1", since = "1.0.0")]
696 impl<'a
, A
> Iterator
for IterMut
<'a
, A
> {
697 type Item
= &'a
mut A
;
699 fn next(&mut self) -> Option
<&'a
mut A
> {
703 self.head
.resolve().map(|next
| {
705 self.head
= match next
.next
{
706 Some(ref mut node
) => Rawlink
::some(&mut **node
),
707 None
=> Rawlink
::none(),
714 fn size_hint(&self) -> (usize, Option
<usize>) {
715 (self.nelem
, Some(self.nelem
))
719 #[stable(feature = "rust1", since = "1.0.0")]
720 impl<'a
, A
> DoubleEndedIterator
for IterMut
<'a
, A
> {
722 fn next_back(&mut self) -> Option
<&'a
mut A
> {
726 self.tail
.resolve().map(|prev
| {
728 self.tail
= prev
.prev
;
734 #[stable(feature = "rust1", since = "1.0.0")]
735 impl<'a
, A
> ExactSizeIterator
for IterMut
<'a
, A
> {}
737 // private methods for IterMut
738 impl<'a
, A
> IterMut
<'a
, A
> {
739 fn insert_next_node(&mut self, mut ins_node
: Box
<Node
<A
>>) {
740 // Insert before `self.head` so that it is between the
741 // previously yielded element and self.head.
743 // The inserted node will not appear in further iteration.
744 match self.head
.resolve() {
745 None
=> { self.list.push_back_node(ins_node); }
747 let prev_node
= match node
.prev
.resolve() {
748 None
=> return self.list
.push_front_node(ins_node
),
751 let node_own
= prev_node
.next
.take().unwrap();
752 ins_node
.next
= link_with_prev(node_own
, Rawlink
::some(&mut *ins_node
));
753 prev_node
.next
= link_with_prev(ins_node
, Rawlink
::some(prev_node
));
754 self.list
.length
+= 1;
760 impl<'a
, A
> IterMut
<'a
, A
> {
761 /// Inserts `elt` just after the element most recently returned by `.next()`.
762 /// The inserted element does not appear in the iteration.
767 /// # #![feature(collections)]
768 /// use std::collections::LinkedList;
770 /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
773 /// let mut it = list.iter_mut();
774 /// assert_eq!(it.next().unwrap(), &1);
775 /// // insert `2` after `1`
776 /// it.insert_next(2);
779 /// let vec: Vec<_> = list.into_iter().collect();
780 /// assert_eq!(vec, [1, 2, 3, 4]);
784 #[unstable(feature = "collections",
785 reason
= "this is probably better handled by a cursor type -- we'll see")]
786 pub fn insert_next(&mut self, elt
: A
) {
787 self.insert_next_node(box Node
::new(elt
))
790 /// Provides a reference to the next element, without changing the iterator.
795 /// # #![feature(collections)]
796 /// use std::collections::LinkedList;
798 /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
800 /// let mut it = list.iter_mut();
801 /// assert_eq!(it.next().unwrap(), &1);
802 /// assert_eq!(it.peek_next().unwrap(), &2);
803 /// // We just peeked at 2, so it was not consumed from the iterator.
804 /// assert_eq!(it.next().unwrap(), &2);
807 #[unstable(feature = "collections",
808 reason
= "this is probably better handled by a cursor type -- we'll see")]
809 pub fn peek_next(&mut self) -> Option
<&mut A
> {
813 self.head
.resolve().map(|head
| &mut head
.value
)
817 #[stable(feature = "rust1", since = "1.0.0")]
818 impl<A
> Iterator
for IntoIter
<A
> {
822 fn next(&mut self) -> Option
<A
> { self.list.pop_front() }
825 fn size_hint(&self) -> (usize, Option
<usize>) {
826 (self.list
.length
, Some(self.list
.length
))
830 #[stable(feature = "rust1", since = "1.0.0")]
831 impl<A
> DoubleEndedIterator
for IntoIter
<A
> {
833 fn next_back(&mut self) -> Option
<A
> { self.list.pop_back() }
836 impl<A
> ExactSizeIterator
for IntoIter
<A
> {}
838 #[stable(feature = "rust1", since = "1.0.0")]
839 impl<A
> FromIterator
<A
> for LinkedList
<A
> {
840 fn from_iter
<T
: IntoIterator
<Item
=A
>>(iter
: T
) -> LinkedList
<A
> {
841 let mut ret
= LinkedList
::new();
847 #[stable(feature = "rust1", since = "1.0.0")]
848 impl<T
> IntoIterator
for LinkedList
<T
> {
850 type IntoIter
= IntoIter
<T
>;
852 /// Consumes the list into an iterator yielding elements by value.
854 fn into_iter(self) -> IntoIter
<T
> {
859 #[stable(feature = "rust1", since = "1.0.0")]
860 impl<'a
, T
> IntoIterator
for &'a LinkedList
<T
> {
862 type IntoIter
= Iter
<'a
, T
>;
864 fn into_iter(self) -> Iter
<'a
, T
> {
869 impl<'a
, T
> IntoIterator
for &'a
mut LinkedList
<T
> {
870 type Item
= &'a
mut T
;
871 type IntoIter
= IterMut
<'a
, T
>;
873 fn into_iter(mut self) -> IterMut
<'a
, T
> {
878 #[stable(feature = "rust1", since = "1.0.0")]
879 impl<A
> Extend
<A
> for LinkedList
<A
> {
880 fn extend
<T
: IntoIterator
<Item
=A
>>(&mut self, iter
: T
) {
881 for elt
in iter { self.push_back(elt); }
885 #[stable(feature = "rust1", since = "1.0.0")]
886 impl<A
: PartialEq
> PartialEq
for LinkedList
<A
> {
887 fn eq(&self, other
: &LinkedList
<A
>) -> bool
{
888 self.len() == other
.len() &&
889 iter
::order
::eq(self.iter(), other
.iter())
892 fn ne(&self, other
: &LinkedList
<A
>) -> bool
{
893 self.len() != other
.len() ||
894 iter
::order
::ne(self.iter(), other
.iter())
898 #[stable(feature = "rust1", since = "1.0.0")]
899 impl<A
: Eq
> Eq
for LinkedList
<A
> {}
901 #[stable(feature = "rust1", since = "1.0.0")]
902 impl<A
: PartialOrd
> PartialOrd
for LinkedList
<A
> {
903 fn partial_cmp(&self, other
: &LinkedList
<A
>) -> Option
<Ordering
> {
904 iter
::order
::partial_cmp(self.iter(), other
.iter())
908 #[stable(feature = "rust1", since = "1.0.0")]
909 impl<A
: Ord
> Ord
for LinkedList
<A
> {
911 fn cmp(&self, other
: &LinkedList
<A
>) -> Ordering
{
912 iter
::order
::cmp(self.iter(), other
.iter())
916 #[stable(feature = "rust1", since = "1.0.0")]
917 impl<A
: Clone
> Clone
for LinkedList
<A
> {
918 fn clone(&self) -> LinkedList
<A
> {
919 self.iter().cloned().collect()
923 #[stable(feature = "rust1", since = "1.0.0")]
924 impl<A
: fmt
::Debug
> fmt
::Debug
for LinkedList
<A
> {
925 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
926 self.iter().fold(f
.debug_list(), |b
, e
| b
.entry(e
)).finish()
930 #[stable(feature = "rust1", since = "1.0.0")]
931 impl<A
: Hash
> Hash
for LinkedList
<A
> {
932 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
933 self.len().hash(state
);
942 use std
::clone
::Clone
;
943 use std
::iter
::{Iterator, IntoIterator}
;
944 use std
::option
::Option
::{Some, None, self}
;
945 use std
::__rand
::{thread_rng, Rng}
;
949 use super::{LinkedList, Node}
;
952 fn list_from
<T
: Clone
>(v
: &[T
]) -> LinkedList
<T
> {
953 v
.iter().cloned().collect()
956 pub fn check_links
<T
>(list
: &LinkedList
<T
>) {
958 let mut last_ptr
: Option
<&Node
<T
>> = None
;
959 let mut node_ptr
: &Node
<T
>;
960 match list
.list_head
{
961 None
=> { assert_eq!(0, list.length); return }
962 Some(ref node
) => node_ptr
= &**node
,
965 match (last_ptr
, node_ptr
.prev
.resolve_immut()) {
967 (None
, _
) => panic
!("prev link for list_head"),
968 (Some(p
), Some(pptr
)) => {
969 assert_eq
!(p
as *const Node
<T
>, pptr
as *const Node
<T
>);
971 _
=> panic
!("prev link is none, not good"),
973 match node_ptr
.next
{
975 last_ptr
= Some(node_ptr
);
985 assert_eq
!(len
, list
.length
);
992 let mut m
= LinkedList
::<i32>::new();
993 let mut n
= LinkedList
::new();
996 assert_eq
!(m
.len(), 0);
997 assert_eq
!(n
.len(), 0);
999 // Non-empty to empty
1001 let mut m
= LinkedList
::new();
1002 let mut n
= LinkedList
::new();
1006 assert_eq
!(m
.len(), 1);
1007 assert_eq
!(m
.pop_back(), Some(2));
1008 assert_eq
!(n
.len(), 0);
1011 // Empty to non-empty
1013 let mut m
= LinkedList
::new();
1014 let mut n
= LinkedList
::new();
1018 assert_eq
!(m
.len(), 1);
1019 assert_eq
!(m
.pop_back(), Some(2));
1023 // Non-empty to non-empty
1024 let v
= vec
![1,2,3,4,5];
1025 let u
= vec
![9,8,1,2,3,4,5];
1026 let mut m
= list_from(&v
);
1027 let mut n
= list_from(&u
);
1032 assert_eq
!(sum
.len(), m
.len());
1034 assert_eq
!(m
.pop_front(), Some(elt
))
1036 assert_eq
!(n
.len(), 0);
1037 // let's make sure it's working properly, since we
1038 // did some direct changes to private members
1040 assert_eq
!(n
.len(), 1);
1041 assert_eq
!(n
.pop_front(), Some(3));
1046 fn test_insert_prev() {
1047 let mut m
= list_from(&[0,2,4,6,8]);
1050 let mut it
= m
.iter_mut();
1056 it
.insert_next(*elt
+ 1);
1057 match it
.peek_next() {
1058 Some(x
) => assert_eq
!(*x
, *elt
+ 2),
1059 None
=> assert_eq
!(8, *elt
),
1068 assert_eq
!(m
.len(), 3 + len
* 2);
1069 assert_eq
!(m
.into_iter().collect
::<Vec
<_
>>(), [-2,0,1,2,3,4,5,6,7,8,9,0,1]);
1074 let n
= list_from(&[1,2,3]);
1075 thread
::spawn(move || {
1077 let a
: &[_
] = &[&1,&2,&3];
1078 assert_eq
!(a
, &n
.iter().collect
::<Vec
<_
>>()[..]);
1079 }).join().ok().unwrap();
1093 use std
::iter
::ExactSizeIterator
;
1094 // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
1095 // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
1098 // https://github.com/rust-lang/rust/issues/26021
1099 let mut v1
= LinkedList
::new();
1104 let _
= v1
.split_off(3); // Dropping this now should not cause laundry consumption
1105 assert_eq
!(v1
.len(), 3);
1107 assert_eq
!(v1
.iter().len(), 3);
1108 assert_eq
!(v1
.iter().collect
::<Vec
<_
>>().len(), 3);
1112 fn fuzz_test(sz
: i32) {
1113 let mut m
: LinkedList
<_
> = LinkedList
::new();
1117 let r
: u8 = thread_rng().next_u32() as u8;
1143 for (a
, &b
) in m
.into_iter().zip(v
.iter()) {
1147 assert_eq
!(i
, v
.len());