alloc/collections/linked_list.rs
1//! A doubly-linked list with owned nodes.
2//!
3//! The `LinkedList` allows pushing and popping elements at either end
4//! in constant time.
5//!
6//! NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because
7//! array-based containers are generally faster,
8//! more memory efficient, and make better use of CPU cache.
9//!
10//! [`Vec`]: crate::vec::Vec
11//! [`VecDeque`]: super::vec_deque::VecDeque
12
13#![stable(feature = "rust1", since = "1.0.0")]
14
15use core::alloc::AllocatorClone;
16use core::cmp::Ordering;
17use core::hash::{Hash, Hasher};
18use core::iter::{FusedIterator, TrustedLen};
19use core::marker::PhantomData;
20use core::ptr::NonNull;
21use core::{fmt, mem};
22
23use super::SpecExtend;
24use crate::alloc::{Allocator, Global};
25use crate::boxed::Box;
26
27#[cfg(test)]
28mod tests;
29
30/// A doubly-linked list with owned nodes.
31///
32/// The `LinkedList` allows pushing and popping elements at either end
33/// in constant time.
34///
35/// A `LinkedList` with a known list of items can be initialized from an array:
36/// ```
37/// use std::collections::LinkedList;
38///
39/// let list = LinkedList::from([1, 2, 3]);
40/// ```
41///
42/// NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because
43/// array-based containers are generally faster,
44/// more memory efficient, and make better use of CPU cache.
45///
46/// [`Vec`]: crate::vec::Vec
47/// [`VecDeque`]: super::vec_deque::VecDeque
48#[stable(feature = "rust1", since = "1.0.0")]
49#[cfg_attr(not(test), rustc_diagnostic_item = "LinkedList")]
50#[rustc_insignificant_dtor]
51pub struct LinkedList<
52 T,
53 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: Allocator = Global,
54> {
55 head: Option<NonNull<Node<T>>>,
56 tail: Option<NonNull<Node<T>>>,
57 len: usize,
58 alloc: A,
59 marker: PhantomData<Box<Node<T>, A>>,
60}
61
62struct Node<T> {
63 next: Option<NonNull<Node<T>>>,
64 prev: Option<NonNull<Node<T>>>,
65 element: T,
66}
67
68/// An iterator over the elements of a `LinkedList`.
69///
70/// This `struct` is created by [`LinkedList::iter()`]. See its
71/// documentation for more.
72#[must_use = "iterators are lazy and do nothing unless consumed"]
73#[stable(feature = "rust1", since = "1.0.0")]
74pub struct Iter<'a, T: 'a> {
75 head: Option<NonNull<Node<T>>>,
76 tail: Option<NonNull<Node<T>>>,
77 len: usize,
78 marker: PhantomData<&'a Node<T>>,
79}
80
81#[stable(feature = "collection_debug", since = "1.17.0")]
82impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
83 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
84 f.debug_tuple("Iter")
85 .field(&*mem::ManuallyDrop::new(LinkedList {
86 head: self.head,
87 tail: self.tail,
88 len: self.len,
89 alloc: Global,
90 marker: PhantomData,
91 }))
92 .field(&self.len)
93 .finish()
94 }
95}
96
97// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
98#[stable(feature = "rust1", since = "1.0.0")]
99impl<T> Clone for Iter<'_, T> {
100 fn clone(&self) -> Self {
101 Iter { ..*self }
102 }
103}
104
105/// A mutable iterator over the elements of a `LinkedList`.
106///
107/// This `struct` is created by [`LinkedList::iter_mut()`]. See its
108/// documentation for more.
109#[must_use = "iterators are lazy and do nothing unless consumed"]
110#[stable(feature = "rust1", since = "1.0.0")]
111pub struct IterMut<'a, T: 'a> {
112 head: Option<NonNull<Node<T>>>,
113 tail: Option<NonNull<Node<T>>>,
114 len: usize,
115 marker: PhantomData<&'a mut Node<T>>,
116}
117
118#[stable(feature = "collection_debug", since = "1.17.0")]
119impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
120 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
121 f.debug_tuple("IterMut")
122 .field(&*mem::ManuallyDrop::new(LinkedList {
123 head: self.head,
124 tail: self.tail,
125 len: self.len,
126 alloc: Global,
127 marker: PhantomData,
128 }))
129 .field(&self.len)
130 .finish()
131 }
132}
133
134/// An owning iterator over the elements of a `LinkedList`.
135///
136/// This `struct` is created by the [`into_iter`] method on [`LinkedList`]
137/// (provided by the [`IntoIterator`] trait). See its documentation for more.
138///
139/// [`into_iter`]: LinkedList::into_iter
140#[derive(Clone)]
141#[stable(feature = "rust1", since = "1.0.0")]
142pub struct IntoIter<
143 T,
144 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: Allocator = Global,
145> {
146 list: LinkedList<T, A>,
147}
148
149#[stable(feature = "collection_debug", since = "1.17.0")]
150impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
151 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
152 f.debug_tuple("IntoIter").field(&self.list).finish()
153 }
154}
155
156impl<T> Node<T> {
157 fn new(element: T) -> Self {
158 Node { next: None, prev: None, element }
159 }
160
161 fn into_element<A: Allocator>(self: Box<Self, A>) -> T {
162 self.element
163 }
164}
165
166// private methods
167impl<T, A: Allocator> LinkedList<T, A> {
168 /// Adds the given node to the front of the list.
169 ///
170 /// # Safety
171 ///
172 /// `node` must point to a valid owned node in the list's allocator.
173 #[inline]
174 unsafe fn push_front_node(&mut self, node: NonNull<Node<T>>) {
175 // SAFETY: This method takes care not to create mutable references to
176 // whole nodes, to maintain validity of aliasing pointers into `element`.
177 unsafe {
178 (*node.as_ptr()).next = self.head;
179 (*node.as_ptr()).prev = None;
180 let node = Some(node);
181
182 match self.head {
183 None => self.tail = node,
184 // Not creating new mutable (unique!) references overlapping `element`.
185 Some(head) => (*head.as_ptr()).prev = node,
186 }
187
188 self.head = node;
189 self.len += 1;
190 }
191 }
192
193 /// Removes and returns the node at the front of the list.
194 #[inline]
195 fn pop_front_node(&mut self) -> Option<Box<Node<T>, &A>> {
196 // SAFETY: This method takes care not to create mutable references to
197 // whole nodes, to maintain validity of aliasing pointers into `element`.
198 self.head.map(|node| unsafe {
199 let node = Box::from_raw_in(node.as_ptr(), &self.alloc);
200 self.head = node.next;
201
202 match self.head {
203 None => self.tail = None,
204 // Not creating new mutable (unique!) references overlapping `element`.
205 Some(head) => (*head.as_ptr()).prev = None,
206 }
207
208 self.len -= 1;
209 node
210 })
211 }
212
213 /// Adds the given node to the back of the list.
214 ///
215 /// # Safety
216 ///
217 /// `node` must point to a valid owned node in the list's allocator.
218 #[inline]
219 unsafe fn push_back_node(&mut self, node: NonNull<Node<T>>) {
220 // SAFETY: This method takes care not to create mutable references to
221 // whole nodes, to maintain validity of aliasing pointers into `element`.
222 unsafe {
223 (*node.as_ptr()).next = None;
224 (*node.as_ptr()).prev = self.tail;
225 let node = Some(node);
226
227 match self.tail {
228 None => self.head = node,
229 // Not creating new mutable (unique!) references overlapping `element`.
230 Some(tail) => (*tail.as_ptr()).next = node,
231 }
232
233 self.tail = node;
234 self.len += 1;
235 }
236 }
237
238 /// Removes and returns the node at the back of the list.
239 #[inline]
240 fn pop_back_node(&mut self) -> Option<Box<Node<T>, &A>> {
241 // SAFETY: This method takes care not to create mutable references to
242 // whole nodes, to maintain validity of aliasing pointers into `element`.
243 self.tail.map(|node| unsafe {
244 let node = Box::from_raw_in(node.as_ptr(), &self.alloc);
245 self.tail = node.prev;
246
247 match self.tail {
248 None => self.head = None,
249 // Not creating new mutable (unique!) references overlapping `element`.
250 Some(tail) => (*tail.as_ptr()).next = None,
251 }
252
253 self.len -= 1;
254 node
255 })
256 }
257
258 /// Unlinks the specified node from the current list.
259 ///
260 /// This method takes care not to create mutable references to `element`, to
261 /// maintain validity of aliasing pointers.
262 ///
263 /// # Safety
264 ///
265 /// The provided node must belong to the current list.
266 #[inline]
267 unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
268 // SAFETY: This is ours now, we can create a &mut.
269 let node = unsafe { node.as_mut() };
270
271 // Not creating new mutable (unique!) references overlapping `element`.
272 match node.prev {
273 // SAFETY: `prev` is a live node in this list.
274 Some(prev) => unsafe { (*prev.as_ptr()).next = node.next },
275 // this node is the head node
276 None => self.head = node.next,
277 };
278
279 match node.next {
280 // SAFETY: `next` is a live node in this list.
281 Some(next) => unsafe { (*next.as_ptr()).prev = node.prev },
282 // this node is the tail node
283 None => self.tail = node.prev,
284 };
285
286 self.len -= 1;
287 }
288
289 /// Splices a series of nodes between two existing nodes.
290 ///
291 /// # Safety
292 ///
293 /// * The provided nodes must belong to the two existing lists.
294 /// * `splice_length` must be exactly the number of nodes between `splice_start` and `splice_end`, inclusive.
295 /// * `splice_start` and `splice_end` must be in the same list, and `splice_start` must precede `splice_end`.
296 /// * If `existing_prev` is `None`, then `existing_next` must be the head node in `self`.
297 /// If `existing_next` is `None`, then `existing_prev` must be the end node in `self`.
298 /// In other case, `existing_prev` must be the predecessor of `existing_next` in `self`.
299 #[inline]
300 unsafe fn splice_nodes(
301 &mut self,
302 existing_prev: Option<NonNull<Node<T>>>,
303 existing_next: Option<NonNull<Node<T>>>,
304 mut splice_start: NonNull<Node<T>>,
305 mut splice_end: NonNull<Node<T>>,
306 splice_length: usize,
307 ) {
308 // This method takes care not to create multiple mutable references to whole nodes at the same time,
309 // to maintain validity of aliasing pointers into `element`.
310 if let Some(mut existing_prev) = existing_prev {
311 // SAFETY: `existing_prev` points to a live node owned by `self`, which don't have any other mutable references.
312 unsafe {
313 existing_prev.as_mut().next = Some(splice_start);
314 }
315 } else {
316 self.head = Some(splice_start);
317 }
318 if let Some(mut existing_next) = existing_next {
319 // SAFETY: `existing_next` points to a live node owned by `self`, which don't have any other mutable references.
320 unsafe {
321 existing_next.as_mut().prev = Some(splice_end);
322 }
323 } else {
324 self.tail = Some(splice_end);
325 }
326 // SAFETY: This method takes care not to create multiple mutable references to whole nodes at the same time,
327 // to maintain validity of aliasing pointers into `element`.
328 unsafe {
329 splice_start.as_mut().prev = existing_prev;
330 splice_end.as_mut().next = existing_next;
331 }
332
333 self.len += splice_length;
334 }
335
336 /// Detaches all nodes from a linked list as a series of nodes.
337 #[inline]
338 fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> {
339 let head = self.head.take();
340 let tail = self.tail.take();
341 let len = mem::replace(&mut self.len, 0);
342 if let Some(head) = head {
343 // SAFETY: In a LinkedList, either both the head and tail are None because
344 // the list is empty, or both head and tail are Some because the list is populated.
345 // Since we have verified the head is Some, we are sure the tail is Some too.
346 let tail = unsafe { tail.unwrap_unchecked() };
347 Some((head, tail, len))
348 } else {
349 None
350 }
351 }
352
353 /// Splits this list before `split_node`.
354 ///
355 /// `self` retains `split_node` and all nodes after it, while the returned list contains all
356 /// nodes before `split_node`. If `split_node` is `None`, all nodes are moved into the returned
357 /// list and `self` is left empty.
358 ///
359 /// # Safety
360 ///
361 /// * If `split_node` is `Some`, it must point to a node in `self`.
362 /// * If `split_node` is `Some`, `at` must equal its zero-based index in `self`.
363 #[inline]
364 unsafe fn split_off_before_node(
365 &mut self,
366 split_node: Option<NonNull<Node<T>>>,
367 at: usize,
368 ) -> Self
369 where
370 A: AllocatorClone,
371 {
372 // The split node is the new head node of the second part
373 if let Some(mut split_node) = split_node {
374 let first_part_head;
375 let first_part_tail;
376 // SAFETY: `split_node` points to a live node in `self`, which don't have any other mutable references.
377 unsafe {
378 first_part_tail = split_node.as_mut().prev.take();
379 }
380 if let Some(mut tail) = first_part_tail {
381 // SAFETY: `tail` is the live predecessor of `split_node`, which don't have any other mutable references.
382 unsafe {
383 tail.as_mut().next = None;
384 }
385 first_part_head = self.head;
386 } else {
387 first_part_head = None;
388 }
389
390 let first_part = LinkedList {
391 head: first_part_head,
392 tail: first_part_tail,
393 len: at,
394 alloc: self.alloc.clone(),
395 marker: PhantomData,
396 };
397
398 // Fix the head ptr of the second part
399 self.head = Some(split_node);
400 self.len -= at;
401
402 first_part
403 } else {
404 mem::replace(self, LinkedList::new_in(self.alloc.clone()))
405 }
406 }
407
408 /// Splits this list after `split_node`.
409 ///
410 /// `self` retains `split_node` and all nodes before it, while the returned list contains all
411 /// nodes after `split_node`. If `split_node` is `None`, all nodes are moved into the returned
412 /// list and `self` is left empty.
413 ///
414 /// # Safety
415 ///
416 /// * If `split_node` is `Some`, it must point to a node in `self`.
417 /// * If `split_node` is `Some`, `at` must equal its zero-based index in `self` plus one.
418 #[inline]
419 unsafe fn split_off_after_node(
420 &mut self,
421 split_node: Option<NonNull<Node<T>>>,
422 at: usize,
423 ) -> Self
424 where
425 A: AllocatorClone,
426 {
427 // The split node is the new tail node of the first part and owns
428 // the head of the second part.
429 if let Some(mut split_node) = split_node {
430 let second_part_head;
431 let second_part_tail;
432 // SAFETY: `split_node` points to a live node in `self`, which don't have any other mutable references.
433 unsafe {
434 second_part_head = split_node.as_mut().next.take();
435 }
436 if let Some(mut head) = second_part_head {
437 // SAFETY: `head` is the live successor of `split_node`, which don't have any other mutable references.
438 unsafe {
439 head.as_mut().prev = None;
440 }
441 second_part_tail = self.tail;
442 } else {
443 second_part_tail = None;
444 }
445
446 let second_part = LinkedList {
447 head: second_part_head,
448 tail: second_part_tail,
449 len: self.len - at,
450 alloc: self.alloc.clone(),
451 marker: PhantomData,
452 };
453
454 // Fix the tail ptr of the first part
455 self.tail = Some(split_node);
456 self.len = at;
457
458 second_part
459 } else {
460 mem::replace(self, LinkedList::new_in(self.alloc.clone()))
461 }
462 }
463}
464
465#[stable(feature = "rust1", since = "1.0.0")]
466impl<T> Default for LinkedList<T> {
467 /// Creates an empty `LinkedList<T>`.
468 #[inline]
469 fn default() -> Self {
470 Self::new()
471 }
472}
473
474impl<T> LinkedList<T> {
475 /// Creates an empty `LinkedList`.
476 ///
477 /// # Examples
478 ///
479 /// ```
480 /// use std::collections::LinkedList;
481 ///
482 /// let list: LinkedList<u32> = LinkedList::new();
483 /// ```
484 #[inline]
485 #[rustc_const_stable(feature = "const_linked_list_new", since = "1.39.0")]
486 #[stable(feature = "rust1", since = "1.0.0")]
487 #[must_use]
488 pub const fn new() -> Self {
489 LinkedList { head: None, tail: None, len: 0, alloc: Global, marker: PhantomData }
490 }
491
492 /// Moves all elements from `other` to the end of the list.
493 ///
494 /// This reuses all the nodes from `other` and moves them into `self`. After
495 /// this operation, `other` becomes empty.
496 ///
497 /// This operation should compute in *O*(1) time and *O*(1) memory.
498 ///
499 /// # Examples
500 ///
501 /// ```
502 /// use std::collections::LinkedList;
503 ///
504 /// let mut list1 = LinkedList::new();
505 /// list1.push_back('a');
506 ///
507 /// let mut list2 = LinkedList::new();
508 /// list2.push_back('b');
509 /// list2.push_back('c');
510 ///
511 /// list1.append(&mut list2);
512 ///
513 /// let mut iter = list1.iter();
514 /// assert_eq!(iter.next(), Some(&'a'));
515 /// assert_eq!(iter.next(), Some(&'b'));
516 /// assert_eq!(iter.next(), Some(&'c'));
517 /// assert!(iter.next().is_none());
518 ///
519 /// assert!(list2.is_empty());
520 /// ```
521 #[stable(feature = "rust1", since = "1.0.0")]
522 pub fn append(&mut self, other: &mut Self) {
523 match self.tail {
524 None => mem::swap(self, other),
525 Some(mut tail) => {
526 if let Some(mut other_head) = other.head.take() {
527 // SAFETY: `as_mut` is okay here because we have exclusive
528 // access to the entirety of both lists.
529 unsafe {
530 tail.as_mut().next = Some(other_head);
531 other_head.as_mut().prev = Some(tail);
532 }
533
534 self.tail = other.tail.take();
535 self.len += mem::replace(&mut other.len, 0);
536 }
537 }
538 }
539 }
540}
541
542impl<T, A: Allocator> LinkedList<T, A> {
543 /// Constructs an empty `LinkedList<T, A>`.
544 ///
545 /// # Examples
546 ///
547 /// ```
548 /// #![feature(allocator_ext)]
549 ///
550 /// use std::alloc::System;
551 /// use std::collections::LinkedList;
552 ///
553 /// let list: LinkedList<i32, System> = LinkedList::new_in(System);
554 /// ```
555 #[inline]
556 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")]
557 pub const fn new_in(alloc: A) -> Self {
558 LinkedList { head: None, tail: None, len: 0, alloc, marker: PhantomData }
559 }
560
561 /// Returns a reference to the underlying allocator.
562 ///
563 /// # Examples
564 ///
565 /// ```
566 /// #![feature(allocator_ext)]
567 ///
568 /// use std::alloc::System;
569 /// use std::collections::LinkedList;
570 ///
571 /// let list: LinkedList<i32, System> = LinkedList::new_in(System);
572 /// let _alloc: &System = list.allocator();
573 /// ```
574 #[inline]
575 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")]
576 pub const fn allocator(&self) -> &A {
577 &self.alloc
578 }
579
580 /// Provides a forward iterator.
581 ///
582 /// # Examples
583 ///
584 /// ```
585 /// use std::collections::LinkedList;
586 ///
587 /// let mut list: LinkedList<u32> = LinkedList::new();
588 ///
589 /// list.push_back(0);
590 /// list.push_back(1);
591 /// list.push_back(2);
592 ///
593 /// let mut iter = list.iter();
594 /// assert_eq!(iter.next(), Some(&0));
595 /// assert_eq!(iter.next(), Some(&1));
596 /// assert_eq!(iter.next(), Some(&2));
597 /// assert_eq!(iter.next(), None);
598 /// ```
599 #[inline]
600 #[stable(feature = "rust1", since = "1.0.0")]
601 pub fn iter(&self) -> Iter<'_, T> {
602 Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
603 }
604
605 /// Provides a forward iterator with mutable references.
606 ///
607 /// # Examples
608 ///
609 /// ```
610 /// use std::collections::LinkedList;
611 ///
612 /// let mut list: LinkedList<u32> = LinkedList::new();
613 ///
614 /// list.push_back(0);
615 /// list.push_back(1);
616 /// list.push_back(2);
617 ///
618 /// for element in list.iter_mut() {
619 /// *element += 10;
620 /// }
621 ///
622 /// let mut iter = list.iter();
623 /// assert_eq!(iter.next(), Some(&10));
624 /// assert_eq!(iter.next(), Some(&11));
625 /// assert_eq!(iter.next(), Some(&12));
626 /// assert_eq!(iter.next(), None);
627 /// ```
628 #[inline]
629 #[stable(feature = "rust1", since = "1.0.0")]
630 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
631 IterMut { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
632 }
633
634 /// Provides a cursor at the front element.
635 ///
636 /// The cursor is pointing to the "ghost" non-element if the list is empty.
637 #[inline]
638 #[must_use]
639 #[unstable(feature = "linked_list_cursors", issue = "58533")]
640 pub fn cursor_front(&self) -> Cursor<'_, T, A> {
641 Cursor { index: 0, current: self.head, list: self }
642 }
643
644 /// Provides a cursor with editing operations at the front element.
645 ///
646 /// The cursor is pointing to the "ghost" non-element if the list is empty.
647 #[inline]
648 #[must_use]
649 #[unstable(feature = "linked_list_cursors", issue = "58533")]
650 pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T, A> {
651 CursorMut { index: 0, current: self.head, list: self }
652 }
653
654 /// Provides a cursor at the back element.
655 ///
656 /// The cursor is pointing to the "ghost" non-element if the list is empty.
657 #[inline]
658 #[must_use]
659 #[unstable(feature = "linked_list_cursors", issue = "58533")]
660 pub fn cursor_back(&self) -> Cursor<'_, T, A> {
661 Cursor { index: self.len.saturating_sub(1), current: self.tail, list: self }
662 }
663
664 /// Provides a cursor with editing operations at the back element.
665 ///
666 /// The cursor is pointing to the "ghost" non-element if the list is empty.
667 #[inline]
668 #[must_use]
669 #[unstable(feature = "linked_list_cursors", issue = "58533")]
670 pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T, A> {
671 CursorMut { index: self.len.saturating_sub(1), current: self.tail, list: self }
672 }
673
674 /// Returns `true` if the `LinkedList` is empty.
675 ///
676 /// This operation should compute in *O*(1) time.
677 ///
678 /// # Examples
679 ///
680 /// ```
681 /// use std::collections::LinkedList;
682 ///
683 /// let mut dl = LinkedList::new();
684 /// assert!(dl.is_empty());
685 ///
686 /// dl.push_front("foo");
687 /// assert!(!dl.is_empty());
688 /// ```
689 #[inline]
690 #[must_use]
691 #[stable(feature = "rust1", since = "1.0.0")]
692 #[rustc_const_stable(feature = "const_linked_list_len", since = "1.101.0")]
693 pub const fn is_empty(&self) -> bool {
694 self.head.is_none()
695 }
696
697 /// Returns the length of the `LinkedList`.
698 ///
699 /// This operation should compute in *O*(1) time.
700 ///
701 /// # Examples
702 ///
703 /// ```
704 /// use std::collections::LinkedList;
705 ///
706 /// let mut dl = LinkedList::new();
707 ///
708 /// dl.push_front(2);
709 /// assert_eq!(dl.len(), 1);
710 ///
711 /// dl.push_front(1);
712 /// assert_eq!(dl.len(), 2);
713 ///
714 /// dl.push_back(3);
715 /// assert_eq!(dl.len(), 3);
716 /// ```
717 #[inline]
718 #[must_use]
719 #[stable(feature = "rust1", since = "1.0.0")]
720 #[rustc_const_stable(feature = "const_linked_list_len", since = "1.101.0")]
721 #[rustc_confusables("length", "size")]
722 pub const fn len(&self) -> usize {
723 self.len
724 }
725
726 /// Removes all elements from the `LinkedList`.
727 ///
728 /// This operation should compute in *O*(*n*) time.
729 ///
730 /// # Examples
731 ///
732 /// ```
733 /// use std::collections::LinkedList;
734 ///
735 /// let mut dl = LinkedList::new();
736 ///
737 /// dl.push_front(2);
738 /// dl.push_front(1);
739 /// assert_eq!(dl.len(), 2);
740 /// assert_eq!(dl.front(), Some(&1));
741 ///
742 /// dl.clear();
743 /// assert_eq!(dl.len(), 0);
744 /// assert_eq!(dl.front(), None);
745 /// ```
746 #[inline]
747 #[stable(feature = "rust1", since = "1.0.0")]
748 pub fn clear(&mut self) {
749 // We need to drop the nodes while keeping self.alloc
750 // We can do this by moving (head, tail, len) into a new list that borrows self.alloc
751 drop(LinkedList {
752 head: self.head.take(),
753 tail: self.tail.take(),
754 len: mem::take(&mut self.len),
755 alloc: &self.alloc,
756 marker: PhantomData,
757 });
758 }
759
760 /// Returns `true` if the `LinkedList` contains an element equal to the
761 /// given value.
762 ///
763 /// This operation should compute linearly in *O*(*n*) time.
764 ///
765 /// # Examples
766 ///
767 /// ```
768 /// use std::collections::LinkedList;
769 ///
770 /// let mut list: LinkedList<u32> = LinkedList::new();
771 ///
772 /// list.push_back(0);
773 /// list.push_back(1);
774 /// list.push_back(2);
775 ///
776 /// assert_eq!(list.contains(&0), true);
777 /// assert_eq!(list.contains(&10), false);
778 /// ```
779 #[stable(feature = "linked_list_contains", since = "1.12.0")]
780 pub fn contains(&self, x: &T) -> bool
781 where
782 T: PartialEq<T>,
783 {
784 self.iter().any(|e| e == x)
785 }
786
787 /// Provides a reference to the front element, or `None` if the list is
788 /// empty.
789 ///
790 /// This operation should compute in *O*(1) time.
791 ///
792 /// # Examples
793 ///
794 /// ```
795 /// use std::collections::LinkedList;
796 ///
797 /// let mut dl = LinkedList::new();
798 /// assert_eq!(dl.front(), None);
799 ///
800 /// dl.push_front(1);
801 /// assert_eq!(dl.front(), Some(&1));
802 /// ```
803 #[inline]
804 #[must_use]
805 #[stable(feature = "rust1", since = "1.0.0")]
806 #[rustc_confusables("first")]
807 pub fn front(&self) -> Option<&T> {
808 // SAFETY: `self` is immutable borrowed, so the head node can be immutable borrowed as well.
809 unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
810 }
811
812 /// Provides a mutable reference to the front element, or `None` if the list
813 /// is empty.
814 ///
815 /// This operation should compute in *O*(1) time.
816 ///
817 /// # Examples
818 ///
819 /// ```
820 /// use std::collections::LinkedList;
821 ///
822 /// let mut dl = LinkedList::new();
823 /// assert_eq!(dl.front(), None);
824 ///
825 /// dl.push_front(1);
826 /// assert_eq!(dl.front(), Some(&1));
827 ///
828 /// match dl.front_mut() {
829 /// None => {},
830 /// Some(x) => *x = 5,
831 /// }
832 /// assert_eq!(dl.front(), Some(&5));
833 /// ```
834 #[inline]
835 #[must_use]
836 #[stable(feature = "rust1", since = "1.0.0")]
837 pub fn front_mut(&mut self) -> Option<&mut T> {
838 // SAFETY: `self` is mutable borrowed, so the head node can be mutable borrowed as well.
839 unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
840 }
841
842 /// Provides a reference to the back element, or `None` if the list is
843 /// empty.
844 ///
845 /// This operation should compute in *O*(1) time.
846 ///
847 /// # Examples
848 ///
849 /// ```
850 /// use std::collections::LinkedList;
851 ///
852 /// let mut dl = LinkedList::new();
853 /// assert_eq!(dl.back(), None);
854 ///
855 /// dl.push_back(1);
856 /// assert_eq!(dl.back(), Some(&1));
857 /// ```
858 #[inline]
859 #[must_use]
860 #[stable(feature = "rust1", since = "1.0.0")]
861 pub fn back(&self) -> Option<&T> {
862 // SAFETY: `self` is immutable borrowed, so the tail node can be immutable borrowed as well.
863 unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
864 }
865
866 /// Provides a mutable reference to the back element, or `None` if the list
867 /// is empty.
868 ///
869 /// This operation should compute in *O*(1) time.
870 ///
871 /// # Examples
872 ///
873 /// ```
874 /// use std::collections::LinkedList;
875 ///
876 /// let mut dl = LinkedList::new();
877 /// assert_eq!(dl.back(), None);
878 ///
879 /// dl.push_back(1);
880 /// assert_eq!(dl.back(), Some(&1));
881 ///
882 /// match dl.back_mut() {
883 /// None => {},
884 /// Some(x) => *x = 5,
885 /// }
886 /// assert_eq!(dl.back(), Some(&5));
887 /// ```
888 #[inline]
889 #[stable(feature = "rust1", since = "1.0.0")]
890 pub fn back_mut(&mut self) -> Option<&mut T> {
891 // SAFETY: `self` is mutable borrowed, so the tail node can be mutable borrowed as well.
892 unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
893 }
894
895 /// Adds an element to the front of the list.
896 ///
897 /// This operation should compute in *O*(1) time.
898 ///
899 /// # Examples
900 ///
901 /// ```
902 /// use std::collections::LinkedList;
903 ///
904 /// let mut dl = LinkedList::new();
905 ///
906 /// dl.push_front(2);
907 /// assert_eq!(dl.front().unwrap(), &2);
908 ///
909 /// dl.push_front(1);
910 /// assert_eq!(dl.front().unwrap(), &1);
911 /// ```
912 #[stable(feature = "rust1", since = "1.0.0")]
913 pub fn push_front(&mut self, elt: T) {
914 let _ = self.push_front_mut(elt);
915 }
916
917 /// Adds an element to the front of the list, returning a reference to it.
918 ///
919 /// This operation should compute in *O*(1) time.
920 ///
921 /// # Examples
922 ///
923 /// ```
924 /// use std::collections::LinkedList;
925 ///
926 /// let mut dl = LinkedList::from([1, 2, 3]);
927 ///
928 /// let ptr = dl.push_front_mut(2);
929 /// *ptr += 4;
930 /// assert_eq!(dl.front().unwrap(), &6);
931 /// ```
932 #[stable(feature = "push_mut", since = "1.95.0")]
933 #[must_use = "if you don't need a reference to the value, use `LinkedList::push_front` instead"]
934 pub fn push_front_mut(&mut self, elt: T) -> &mut T {
935 let mut node =
936 Box::into_non_null_with_allocator(Box::new_in(Node::new(elt), &self.alloc)).0;
937 // SAFETY: node is a unique pointer to a node in self.alloc
938 unsafe {
939 self.push_front_node(node);
940 &mut node.as_mut().element
941 }
942 }
943
944 /// Removes the first element and returns it, or `None` if the list is
945 /// empty.
946 ///
947 /// This operation should compute in *O*(1) time.
948 ///
949 /// # Examples
950 ///
951 /// ```
952 /// use std::collections::LinkedList;
953 ///
954 /// let mut d = LinkedList::new();
955 /// assert_eq!(d.pop_front(), None);
956 ///
957 /// d.push_front(1);
958 /// d.push_front(3);
959 /// assert_eq!(d.pop_front(), Some(3));
960 /// assert_eq!(d.pop_front(), Some(1));
961 /// assert_eq!(d.pop_front(), None);
962 /// ```
963 #[stable(feature = "rust1", since = "1.0.0")]
964 pub fn pop_front(&mut self) -> Option<T> {
965 self.pop_front_node().map(Node::into_element)
966 }
967
968 /// Adds an element to the back of the list.
969 ///
970 /// This operation should compute in *O*(1) time.
971 ///
972 /// # Examples
973 ///
974 /// ```
975 /// use std::collections::LinkedList;
976 ///
977 /// let mut d = LinkedList::new();
978 /// d.push_back(1);
979 /// d.push_back(3);
980 /// assert_eq!(3, *d.back().unwrap());
981 /// ```
982 #[stable(feature = "rust1", since = "1.0.0")]
983 #[rustc_confusables("push", "append")]
984 pub fn push_back(&mut self, elt: T) {
985 let _ = self.push_back_mut(elt);
986 }
987
988 /// Adds an element to the back of the list, returning a reference to it.
989 ///
990 /// This operation should compute in *O*(1) time.
991 ///
992 /// # Examples
993 ///
994 /// ```
995 /// use std::collections::LinkedList;
996 ///
997 /// let mut dl = LinkedList::from([1, 2, 3]);
998 ///
999 /// let ptr = dl.push_back_mut(2);
1000 /// *ptr += 4;
1001 /// assert_eq!(dl.back().unwrap(), &6);
1002 /// ```
1003 #[stable(feature = "push_mut", since = "1.95.0")]
1004 #[must_use = "if you don't need a reference to the value, use `LinkedList::push_back` instead"]
1005 pub fn push_back_mut(&mut self, elt: T) -> &mut T {
1006 let mut node =
1007 Box::into_non_null_with_allocator(Box::new_in(Node::new(elt), &self.alloc)).0;
1008 // SAFETY: node is a unique pointer to a node in self.alloc
1009 unsafe {
1010 self.push_back_node(node);
1011 &mut node.as_mut().element
1012 }
1013 }
1014
1015 /// Removes the last element from a list and returns it, or `None` if
1016 /// it is empty.
1017 ///
1018 /// This operation should compute in *O*(1) time.
1019 ///
1020 /// # Examples
1021 ///
1022 /// ```
1023 /// use std::collections::LinkedList;
1024 ///
1025 /// let mut d = LinkedList::new();
1026 /// assert_eq!(d.pop_back(), None);
1027 /// d.push_back(1);
1028 /// d.push_back(3);
1029 /// assert_eq!(d.pop_back(), Some(3));
1030 /// ```
1031 #[stable(feature = "rust1", since = "1.0.0")]
1032 pub fn pop_back(&mut self) -> Option<T> {
1033 self.pop_back_node().map(Node::into_element)
1034 }
1035
1036 /// Splits the list into two at the given index. Returns everything after the given index,
1037 /// including the index.
1038 ///
1039 /// This operation should compute in *O*(*n*) time.
1040 ///
1041 /// # Panics
1042 ///
1043 /// Panics if `at > len`.
1044 ///
1045 /// # Examples
1046 ///
1047 /// ```
1048 /// use std::collections::LinkedList;
1049 ///
1050 /// let mut d = LinkedList::new();
1051 ///
1052 /// d.push_front(1);
1053 /// d.push_front(2);
1054 /// d.push_front(3);
1055 ///
1056 /// let mut split = d.split_off(2);
1057 ///
1058 /// assert_eq!(split.pop_front(), Some(1));
1059 /// assert_eq!(split.pop_front(), None);
1060 /// ```
1061 #[stable(feature = "rust1", since = "1.0.0")]
1062 pub fn split_off(&mut self, at: usize) -> LinkedList<T, A>
1063 where
1064 A: AllocatorClone,
1065 {
1066 let len = self.len();
1067 assert!(at <= len, "Cannot split off at a nonexistent index");
1068 if at == 0 {
1069 return mem::replace(self, Self::new_in(self.alloc.clone()));
1070 } else if at == len {
1071 return Self::new_in(self.alloc.clone());
1072 }
1073
1074 // Below, we iterate towards the `i-1`th node, either from the start or the end,
1075 // depending on which would be faster.
1076 let split_node = if at - 1 <= len - 1 - (at - 1) {
1077 let mut iter = self.iter_mut();
1078 // instead of skipping using .skip() (which creates a new struct),
1079 // we skip manually so we can access the head field without
1080 // depending on implementation details of Skip
1081 for _ in 0..at - 1 {
1082 iter.next();
1083 }
1084 iter.head
1085 } else {
1086 // better off starting from the end
1087 let mut iter = self.iter_mut();
1088 for _ in 0..len - 1 - (at - 1) {
1089 iter.next_back();
1090 }
1091 iter.tail
1092 };
1093 // SAFETY: `split_node` is a valid node in `self`, and `at` is `index_of(split_node) + 1`.
1094 unsafe { self.split_off_after_node(split_node, at) }
1095 }
1096
1097 /// Removes the element at the given index and returns it.
1098 ///
1099 /// This operation should compute in *O*(*n*) time.
1100 ///
1101 /// # Panics
1102 /// Panics if at >= len
1103 ///
1104 /// # Examples
1105 ///
1106 /// ```
1107 /// #![feature(linked_list_remove)]
1108 /// use std::collections::LinkedList;
1109 ///
1110 /// let mut d = LinkedList::new();
1111 ///
1112 /// d.push_front(1);
1113 /// d.push_front(2);
1114 /// d.push_front(3);
1115 ///
1116 /// assert_eq!(d.remove(1), 2);
1117 /// assert_eq!(d.remove(0), 3);
1118 /// assert_eq!(d.remove(0), 1);
1119 /// ```
1120 #[unstable(feature = "linked_list_remove", issue = "69210")]
1121 #[rustc_confusables("delete", "take")]
1122 pub fn remove(&mut self, at: usize) -> T {
1123 let len = self.len();
1124 assert!(at < len, "Cannot remove at an index outside of the list bounds");
1125
1126 // Below, we iterate towards the node at the given index, either from
1127 // the start or the end, depending on which would be faster.
1128 let offset_from_end = len - at - 1;
1129 if at <= offset_from_end {
1130 let mut cursor = self.cursor_front_mut();
1131 for _ in 0..at {
1132 cursor.move_next();
1133 }
1134 cursor.remove_current().unwrap()
1135 } else {
1136 let mut cursor = self.cursor_back_mut();
1137 for _ in 0..offset_from_end {
1138 cursor.move_prev();
1139 }
1140 cursor.remove_current().unwrap()
1141 }
1142 }
1143
1144 /// Retains only the elements specified by the predicate.
1145 ///
1146 /// In other words, remove all elements `e` for which `f(&mut e)` returns false.
1147 /// This method operates in place, visiting each element exactly once in the
1148 /// original order, and preserves the order of the retained elements.
1149 ///
1150 /// # Examples
1151 ///
1152 /// ```
1153 /// #![feature(linked_list_retain)]
1154 /// use std::collections::LinkedList;
1155 ///
1156 /// let mut d = LinkedList::new();
1157 ///
1158 /// d.push_front(1);
1159 /// d.push_front(2);
1160 /// d.push_front(3);
1161 ///
1162 /// d.retain(|&mut x| x % 2 == 0);
1163 ///
1164 /// assert_eq!(d.pop_front(), Some(2));
1165 /// assert_eq!(d.pop_front(), None);
1166 /// ```
1167 ///
1168 /// Because the elements are visited exactly once in the original order,
1169 /// external state may be used to decide which elements to keep.
1170 ///
1171 /// ```
1172 /// #![feature(linked_list_retain)]
1173 /// use std::collections::LinkedList;
1174 ///
1175 /// let mut d = LinkedList::new();
1176 ///
1177 /// d.push_front(1);
1178 /// d.push_front(2);
1179 /// d.push_front(3);
1180 ///
1181 /// let keep = [false, true, false];
1182 /// let mut iter = keep.iter();
1183 /// d.retain(|_| *iter.next().unwrap());
1184 /// assert_eq!(d.pop_front(), Some(2));
1185 /// assert_eq!(d.pop_front(), None);
1186 /// ```
1187 #[unstable(feature = "linked_list_retain", issue = "114135")]
1188 pub fn retain<F>(&mut self, mut f: F)
1189 where
1190 F: FnMut(&mut T) -> bool,
1191 {
1192 let mut cursor = self.cursor_front_mut();
1193 while let Some(node) = cursor.current() {
1194 if !f(node) {
1195 cursor.remove_current().unwrap();
1196 } else {
1197 cursor.move_next();
1198 }
1199 }
1200 }
1201
1202 /// Creates an iterator which uses a closure to determine if an element should be removed.
1203 ///
1204 /// If the closure returns `true`, the element is removed from the list and
1205 /// yielded. If the closure returns `false`, or panics, the element remains
1206 /// in the list and will not be yielded.
1207 ///
1208 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1209 /// or the iteration short-circuits, then the remaining elements will be retained.
1210 /// Use `extract_if().for_each(drop)` if you do not need the returned iterator.
1211 ///
1212 /// The iterator also lets you mutate the value of each element in the
1213 /// closure, regardless of whether you choose to keep or remove it.
1214 ///
1215 /// # Examples
1216 ///
1217 /// Splitting a list into even and odd values, reusing the original list:
1218 ///
1219 /// ```
1220 /// use std::collections::LinkedList;
1221 ///
1222 /// let mut numbers: LinkedList<u32> = LinkedList::new();
1223 /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
1224 ///
1225 /// let evens = numbers.extract_if(|x| *x % 2 == 0).collect::<LinkedList<_>>();
1226 /// let odds = numbers;
1227 ///
1228 /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
1229 /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]);
1230 /// ```
1231 #[stable(feature = "extract_if", since = "1.87.0")]
1232 pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>
1233 where
1234 F: FnMut(&mut T) -> bool,
1235 {
1236 // avoid borrow issues.
1237 let it = self.head;
1238 let old_len = self.len;
1239
1240 ExtractIf { list: self, it, pred: filter, idx: 0, old_len }
1241 }
1242}
1243
1244#[stable(feature = "rust1", since = "1.0.0")]
1245unsafe impl<#[may_dangle] T, A: Allocator> Drop for LinkedList<T, A> {
1246 fn drop(&mut self) {
1247 struct DropGuard<'a, T, A: Allocator>(&'a mut LinkedList<T, A>);
1248
1249 impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
1250 fn drop(&mut self) {
1251 // Continue the same loop we do below. This only runs when a destructor has
1252 // panicked. If another one panics this will abort.
1253 while self.0.pop_front_node().is_some() {}
1254 }
1255 }
1256
1257 // Wrap self so that if a destructor panics, we can try to keep looping
1258 let guard = DropGuard(self);
1259 while guard.0.pop_front_node().is_some() {}
1260 mem::forget(guard);
1261 }
1262}
1263
1264#[stable(feature = "rust1", since = "1.0.0")]
1265impl<'a, T> Iterator for Iter<'a, T> {
1266 type Item = &'a T;
1267
1268 #[inline]
1269 fn next(&mut self) -> Option<&'a T> {
1270 if self.len == 0 {
1271 return None;
1272 }
1273 // SAFETY: When `len > 0`, `head` and `tail` are guaranteed to be `Some`.
1274 // The lifetime of the returned reference is bound to the lifetime of the iterator,
1275 // which is valid because the iterator holds a reference to the list.
1276 Some(unsafe {
1277 // Need an unbound lifetime to get 'a
1278 let node = &*self.head.unwrap_unchecked().as_ptr();
1279 self.len -= 1;
1280 self.head = node.next;
1281 &node.element
1282 })
1283 }
1284
1285 #[inline]
1286 fn size_hint(&self) -> (usize, Option<usize>) {
1287 (self.len, Some(self.len))
1288 }
1289
1290 #[inline]
1291 fn last(mut self) -> Option<&'a T> {
1292 self.next_back()
1293 }
1294}
1295
1296#[stable(feature = "rust1", since = "1.0.0")]
1297impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1298 #[inline]
1299 fn next_back(&mut self) -> Option<&'a T> {
1300 if self.len == 0 {
1301 return None;
1302 }
1303 // SAFETY: When `len > 0`, `head` and `tail` are guaranteed to be `Some`.
1304 // The lifetime of the returned reference is bound to the lifetime of the iterator,
1305 // which is valid because the iterator holds a reference to the list.
1306 Some(unsafe {
1307 // Need an unbound lifetime to get 'a
1308 let node = &*self.tail.unwrap_unchecked().as_ptr();
1309 self.len -= 1;
1310 self.tail = node.prev;
1311 &node.element
1312 })
1313 }
1314}
1315
1316#[stable(feature = "rust1", since = "1.0.0")]
1317impl<T> ExactSizeIterator for Iter<'_, T> {}
1318
1319#[stable(feature = "fused", since = "1.26.0")]
1320impl<T> FusedIterator for Iter<'_, T> {}
1321
1322#[unstable(feature = "trusted_len", issue = "37572")]
1323unsafe impl<T> TrustedLen for Iter<'_, T> {}
1324
1325#[stable(feature = "default_iters", since = "1.70.0")]
1326impl<T> Default for Iter<'_, T> {
1327 /// Creates an empty `linked_list::Iter`.
1328 ///
1329 /// ```
1330 /// # use std::collections::linked_list;
1331 /// let iter: linked_list::Iter<'_, u8> = Default::default();
1332 /// assert_eq!(iter.len(), 0);
1333 /// ```
1334 fn default() -> Self {
1335 Iter { head: None, tail: None, len: 0, marker: Default::default() }
1336 }
1337}
1338
1339#[stable(feature = "rust1", since = "1.0.0")]
1340impl<'a, T> Iterator for IterMut<'a, T> {
1341 type Item = &'a mut T;
1342
1343 #[inline]
1344 fn next(&mut self) -> Option<&'a mut T> {
1345 if self.len == 0 {
1346 return None;
1347 }
1348 // SAFETY: When `len > 0`, `head` and `tail` are guaranteed to be `Some`.
1349 // The lifetime of the returned reference is bound to the lifetime of the iterator,
1350 // which is valid because the iterator holds a reference to the list.
1351 Some(unsafe {
1352 // Need an unbound lifetime to get 'a
1353 let node = &mut *self.head.unwrap_unchecked().as_ptr();
1354 self.len -= 1;
1355 self.head = node.next;
1356 &mut node.element
1357 })
1358 }
1359
1360 #[inline]
1361 fn size_hint(&self) -> (usize, Option<usize>) {
1362 (self.len, Some(self.len))
1363 }
1364
1365 #[inline]
1366 fn last(mut self) -> Option<&'a mut T> {
1367 self.next_back()
1368 }
1369}
1370
1371#[stable(feature = "rust1", since = "1.0.0")]
1372impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1373 #[inline]
1374 fn next_back(&mut self) -> Option<&'a mut T> {
1375 if self.len == 0 {
1376 return None;
1377 }
1378 // SAFETY: When `len > 0`, `head` and `tail` are guaranteed to be `Some`.
1379 // The lifetime of the returned reference is bound to the lifetime of the iterator,
1380 // which is valid because the iterator holds a reference to the list.
1381 Some(unsafe {
1382 // Need an unbound lifetime to get 'a
1383 let node = &mut *self.tail.unwrap_unchecked().as_ptr();
1384 self.len -= 1;
1385 self.tail = node.prev;
1386 &mut node.element
1387 })
1388 }
1389}
1390
1391#[stable(feature = "rust1", since = "1.0.0")]
1392impl<T> ExactSizeIterator for IterMut<'_, T> {}
1393
1394#[stable(feature = "fused", since = "1.26.0")]
1395impl<T> FusedIterator for IterMut<'_, T> {}
1396
1397#[unstable(feature = "trusted_len", issue = "37572")]
1398unsafe impl<T> TrustedLen for IterMut<'_, T> {}
1399
1400#[stable(feature = "default_iters", since = "1.70.0")]
1401impl<T> Default for IterMut<'_, T> {
1402 fn default() -> Self {
1403 IterMut { head: None, tail: None, len: 0, marker: Default::default() }
1404 }
1405}
1406
1407/// A cursor over a `LinkedList`.
1408///
1409/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
1410///
1411/// Cursors always rest between two elements in the list, and index in a logically circular way.
1412/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1413/// tail of the list.
1414///
1415/// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty.
1416#[unstable(feature = "linked_list_cursors", issue = "58533")]
1417pub struct Cursor<
1418 'a,
1419 T: 'a,
1420 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: Allocator = Global,
1421> {
1422 index: usize,
1423 current: Option<NonNull<Node<T>>>,
1424 list: &'a LinkedList<T, A>,
1425}
1426
1427#[unstable(feature = "linked_list_cursors", issue = "58533")]
1428impl<T, A: Allocator> Clone for Cursor<'_, T, A> {
1429 fn clone(&self) -> Self {
1430 let Cursor { index, current, list } = *self;
1431 Cursor { index, current, list }
1432 }
1433}
1434
1435#[unstable(feature = "linked_list_cursors", issue = "58533")]
1436impl<T: fmt::Debug, A: Allocator> fmt::Debug for Cursor<'_, T, A> {
1437 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1438 f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
1439 }
1440}
1441
1442/// A cursor over a `LinkedList` with editing operations.
1443///
1444/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
1445/// safely mutate the list during iteration. This is because the lifetime of its yielded
1446/// references is tied to its own lifetime, instead of just the underlying list. This means
1447/// cursors cannot yield multiple elements at once.
1448///
1449/// Cursors always rest between two elements in the list, and index in a logically circular way.
1450/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
1451/// tail of the list.
1452#[unstable(feature = "linked_list_cursors", issue = "58533")]
1453pub struct CursorMut<
1454 'a,
1455 T: 'a,
1456 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: Allocator = Global,
1457> {
1458 index: usize,
1459 current: Option<NonNull<Node<T>>>,
1460 list: &'a mut LinkedList<T, A>,
1461}
1462
1463#[unstable(feature = "linked_list_cursors", issue = "58533")]
1464impl<T: fmt::Debug, A: Allocator> fmt::Debug for CursorMut<'_, T, A> {
1465 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1466 f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
1467 }
1468}
1469
1470impl<'a, T, A: Allocator> Cursor<'a, T, A> {
1471 /// Returns the cursor position index within the `LinkedList`.
1472 ///
1473 /// This returns `None` if the cursor is currently pointing to the
1474 /// "ghost" non-element.
1475 #[must_use]
1476 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1477 pub fn index(&self) -> Option<usize> {
1478 let _ = self.current?;
1479 Some(self.index)
1480 }
1481
1482 /// Moves the cursor to the next element of the `LinkedList`.
1483 ///
1484 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1485 /// the first element of the `LinkedList`. If it is pointing to the last
1486 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1487 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1488 pub fn move_next(&mut self) {
1489 match self.current.take() {
1490 // We had no current element; the cursor was sitting at the start position
1491 // Next element should be the head of the list
1492 None => {
1493 self.current = self.list.head;
1494 self.index = 0;
1495 }
1496 // We had a previous element, so let's go to its next
1497 // SAFETY: `current` is a pointer to a live node in `list`, which don't have mutable reference.
1498 Some(current) => unsafe {
1499 self.current = current.as_ref().next;
1500 self.index += 1;
1501 },
1502 }
1503 }
1504
1505 /// Moves the cursor to the previous element of the `LinkedList`.
1506 ///
1507 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1508 /// the last element of the `LinkedList`. If it is pointing to the first
1509 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1510 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1511 pub fn move_prev(&mut self) {
1512 match self.current.take() {
1513 // No current. We're at the start of the list. Yield None and jump to the end.
1514 None => {
1515 self.current = self.list.tail;
1516 self.index = self.list.len().saturating_sub(1);
1517 }
1518 // Have a prev. Yield it and go to the previous element.
1519 // SAFETY: `current` is a pointer to a live node in `list`, which don't have mutable reference.
1520 Some(current) => unsafe {
1521 self.current = current.as_ref().prev;
1522 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1523 },
1524 }
1525 }
1526
1527 /// Returns a reference to the element that the cursor is currently
1528 /// pointing to.
1529 ///
1530 /// This returns `None` if the cursor is currently pointing to the
1531 /// "ghost" non-element.
1532 #[must_use]
1533 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1534 pub fn current(&self) -> Option<&'a T> {
1535 // SAFETY: If `self.current` is `Some`, then `current` is a pointer to a live node in `list`.
1536 unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
1537 }
1538
1539 /// Returns a reference to the next element.
1540 ///
1541 /// If the cursor is pointing to the "ghost" non-element then this returns
1542 /// the first element of the `LinkedList`. If it is pointing to the last
1543 /// element of the `LinkedList` then this returns `None`.
1544 #[must_use]
1545 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1546 pub fn peek_next(&self) -> Option<&'a T> {
1547 // SAFETY: If `self.current` is `Some`, then `current` is a pointer to a live node in `list`,
1548 // and `current` does not have mutable reference.
1549 // If `next` is `Some`, then we can get inner pointer which points at a live node in `list`.
1550 unsafe {
1551 let next = match self.current {
1552 None => self.list.head,
1553 Some(current) => current.as_ref().next,
1554 };
1555 next.map(|next| &(*next.as_ptr()).element)
1556 }
1557 }
1558
1559 /// Returns a reference to the previous element.
1560 ///
1561 /// If the cursor is pointing to the "ghost" non-element then this returns
1562 /// the last element of the `LinkedList`. If it is pointing to the first
1563 /// element of the `LinkedList` then this returns `None`.
1564 #[must_use]
1565 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1566 pub fn peek_prev(&self) -> Option<&'a T> {
1567 // SAFETY: If `self.current` is `Some`, then `current` is a pointer to a live node in `list`,
1568 // and `current` does not have mutable reference.
1569 // If `prev` is `Some`, then we can get inner pointer which points at a live node in `list`.
1570 unsafe {
1571 let prev = match self.current {
1572 None => self.list.tail,
1573 Some(current) => current.as_ref().prev,
1574 };
1575 prev.map(|prev| &(*prev.as_ptr()).element)
1576 }
1577 }
1578
1579 /// Provides a reference to the front element of the cursor's parent list,
1580 /// or None if the list is empty.
1581 #[must_use]
1582 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1583 #[rustc_confusables("first")]
1584 pub fn front(&self) -> Option<&'a T> {
1585 self.list.front()
1586 }
1587
1588 /// Provides a reference to the back element of the cursor's parent list,
1589 /// or None if the list is empty.
1590 #[must_use]
1591 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1592 #[rustc_confusables("last")]
1593 pub fn back(&self) -> Option<&'a T> {
1594 self.list.back()
1595 }
1596
1597 /// Provides a reference to the cursor's parent list.
1598 #[must_use]
1599 #[inline(always)]
1600 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1601 pub fn as_list(&self) -> &'a LinkedList<T, A> {
1602 self.list
1603 }
1604}
1605
1606impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
1607 /// Returns the cursor position index within the `LinkedList`.
1608 ///
1609 /// This returns `None` if the cursor is currently pointing to the
1610 /// "ghost" non-element.
1611 #[must_use]
1612 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1613 pub fn index(&self) -> Option<usize> {
1614 let _ = self.current?;
1615 Some(self.index)
1616 }
1617
1618 /// Moves the cursor to the next element of the `LinkedList`.
1619 ///
1620 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1621 /// the first element of the `LinkedList`. If it is pointing to the last
1622 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1623 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1624 pub fn move_next(&mut self) {
1625 match self.current.take() {
1626 // We had no current element; the cursor was sitting at the start position
1627 // Next element should be the head of the list
1628 None => {
1629 self.current = self.list.head;
1630 self.index = 0;
1631 }
1632 // We had a previous element, so let's go to its next
1633 // SAFETY: `current` is a pointer to a live node in `list`, which don't have mutable reference.
1634 Some(current) => unsafe {
1635 self.current = current.as_ref().next;
1636 self.index += 1;
1637 },
1638 }
1639 }
1640
1641 /// Moves the cursor to the previous element of the `LinkedList`.
1642 ///
1643 /// If the cursor is pointing to the "ghost" non-element then this will move it to
1644 /// the last element of the `LinkedList`. If it is pointing to the first
1645 /// element of the `LinkedList` then this will move it to the "ghost" non-element.
1646 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1647 pub fn move_prev(&mut self) {
1648 match self.current.take() {
1649 // No current. We're at the start of the list. Yield None and jump to the end.
1650 None => {
1651 self.current = self.list.tail;
1652 self.index = self.list.len().saturating_sub(1);
1653 }
1654 // Have a prev. Yield it and go to the previous element.
1655 // SAFETY: `current` is a pointer to a live node in `list`, which don't have mutable reference.
1656 Some(current) => unsafe {
1657 self.current = current.as_ref().prev;
1658 self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
1659 },
1660 }
1661 }
1662
1663 /// Returns a reference to the element that the cursor is currently
1664 /// pointing to.
1665 ///
1666 /// This returns `None` if the cursor is currently pointing to the
1667 /// "ghost" non-element.
1668 #[must_use]
1669 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1670 pub fn current(&mut self) -> Option<&mut T> {
1671 // SAFETY: If `self.current` is `Some`, then `current` is a pointer to a live node in `list`.
1672 unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
1673 }
1674
1675 /// Returns a reference to the next element.
1676 ///
1677 /// If the cursor is pointing to the "ghost" non-element then this returns
1678 /// the first element of the `LinkedList`. If it is pointing to the last
1679 /// element of the `LinkedList` then this returns `None`.
1680 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1681 pub fn peek_next(&mut self) -> Option<&mut T> {
1682 // SAFETY: If `self.current` is `Some`, then `current` is a pointer to a live node in `list`,
1683 // and `current` does not have mutable reference.
1684 // If `next` is `Some`, then we can get inner pointer which points at a live node in `list`.
1685 unsafe {
1686 let next = match self.current {
1687 None => self.list.head,
1688 Some(current) => current.as_ref().next,
1689 };
1690 next.map(|next| &mut (*next.as_ptr()).element)
1691 }
1692 }
1693
1694 /// Returns a reference to the previous element.
1695 ///
1696 /// If the cursor is pointing to the "ghost" non-element then this returns
1697 /// the last element of the `LinkedList`. If it is pointing to the first
1698 /// element of the `LinkedList` then this returns `None`.
1699 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1700 pub fn peek_prev(&mut self) -> Option<&mut T> {
1701 // SAFETY: If `self.current` is `Some`, then `current` is a pointer to a live node in `list`,
1702 // and `current` does not have mutable reference.
1703 // If `prev` is `Some`, then we can get inner pointer which points at a live node in `list`.
1704 unsafe {
1705 let prev = match self.current {
1706 None => self.list.tail,
1707 Some(current) => current.as_ref().prev,
1708 };
1709 prev.map(|prev| &mut (*prev.as_ptr()).element)
1710 }
1711 }
1712
1713 /// Returns a read-only cursor pointing to the current element.
1714 ///
1715 /// The lifetime of the returned `Cursor` is bound to that of the
1716 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
1717 /// `CursorMut` is frozen for the lifetime of the `Cursor`.
1718 #[must_use]
1719 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1720 pub fn as_cursor(&self) -> Cursor<'_, T, A> {
1721 Cursor { list: self.list, current: self.current, index: self.index }
1722 }
1723
1724 /// Provides a read-only reference to the cursor's parent list.
1725 ///
1726 /// The lifetime of the returned reference is bound to that of the
1727 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
1728 /// `CursorMut` is frozen for the lifetime of the reference.
1729 #[must_use]
1730 #[inline(always)]
1731 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1732 pub fn as_list(&self) -> &LinkedList<T, A> {
1733 self.list
1734 }
1735}
1736
1737// Now the list editing operations
1738
1739impl<'a, T> CursorMut<'a, T> {
1740 /// Inserts the elements from the given `LinkedList` after the current one.
1741 ///
1742 /// If the cursor is pointing at the "ghost" non-element then the new elements are
1743 /// inserted at the start of the `LinkedList`.
1744 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1745 pub fn splice_after(&mut self, list: LinkedList<T>) {
1746 let Some((splice_head, splice_tail, splice_len)) = list.detach_all_nodes() else {
1747 return;
1748 };
1749 // SAFETY:
1750 // * If `self.current` is `Some`, then `node` is a pointer to a live node in `list`
1751 // and don't have mutable reference.
1752 // * `self.current` (possible `None`) and `node_next` belong to `self.list`,
1753 // while `splice_head` and `splice_tail` belong to `list`.
1754 // * `splice_len` is the length of the new nodes to be spliced in.
1755 // * `splice_head` and `splice_tail` are the head and tail of the new nodes to be spliced in.
1756 // * If `self.current` is `None`, then `node_next` is the head of the list.
1757 // If `self.current` is `Some`, then `node_next` is the next node after `self.current`.
1758 unsafe {
1759 let node_next = match self.current {
1760 None => self.list.head,
1761 Some(node) => node.as_ref().next,
1762 };
1763 self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
1764 }
1765 if self.current.is_none() {
1766 // The "ghost" non-element's index has changed.
1767 self.index = self.list.len;
1768 }
1769 }
1770
1771 /// Inserts the elements from the given `LinkedList` before the current one.
1772 ///
1773 /// If the cursor is pointing at the "ghost" non-element then the new elements are
1774 /// inserted at the end of the `LinkedList`.
1775 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1776 pub fn splice_before(&mut self, list: LinkedList<T>) {
1777 let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
1778 Some(parts) => parts,
1779 _ => return,
1780 };
1781 // SAFETY:
1782 // * If `self.current` is `Some`, then `node` is a pointer to a live node in `list`
1783 // and don't have mutable reference.
1784 // * `self.current` (possible `None`) and `node_prev` belong to `self.list`,
1785 // while `splice_head` and `splice_tail` belong to `list`.
1786 // * `splice_len` is the length of the new nodes to be spliced in.
1787 // * `splice_head` and `splice_tail` are the head and tail of the new nodes to be spliced in.
1788 // * If `self.current` is `None`, then `node_prev` is the tail of the list.
1789 // If `self.current` is `Some`, then `node_prev` is the previous node before `self.current`.
1790 unsafe {
1791 let node_prev = match self.current {
1792 None => self.list.tail,
1793 Some(node) => node.as_ref().prev,
1794 };
1795 self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
1796 }
1797 self.index += splice_len;
1798 }
1799}
1800
1801impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
1802 /// Inserts a new element into the `LinkedList` after the current one.
1803 ///
1804 /// If the cursor is pointing at the "ghost" non-element then the new element is
1805 /// inserted at the front of the `LinkedList`.
1806 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1807 pub fn insert_after(&mut self, item: T) {
1808 let spliced_node =
1809 Box::into_non_null_with_allocator(Box::new_in(Node::new(item), &self.list.alloc)).0;
1810 // SAFETY:
1811 // * If `self.current` is `Some`, then `node` is a pointer to a live node in `list`
1812 // and don't have mutable reference.
1813 // * `self.current` (possible `None`) and `node_next` belong to `self.list`,
1814 // while `spliced_node` does not belong to any list.
1815 // * This method only inserts one node, so `spliced_node` is both the head and tail of the new nodes to be spliced in.
1816 // * The length of the new nodes to be spliced in is 1.
1817 // * If `self.current` is `None`, then `node_next` is the head of the list.
1818 // If `self.current` is `Some`, then `node_next` is the next node after `self.current`.
1819 unsafe {
1820 let node_next = match self.current {
1821 None => self.list.head,
1822 Some(node) => node.as_ref().next,
1823 };
1824 self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
1825 }
1826 if self.current.is_none() {
1827 // The "ghost" non-element's index has changed.
1828 self.index = self.list.len;
1829 }
1830 }
1831
1832 /// Inserts a new element into the `LinkedList` before the current one.
1833 ///
1834 /// If the cursor is pointing at the "ghost" non-element then the new element is
1835 /// inserted at the end of the `LinkedList`.
1836 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1837 pub fn insert_before(&mut self, item: T) {
1838 let spliced_node =
1839 Box::into_non_null_with_allocator(Box::new_in(Node::new(item), &self.list.alloc)).0;
1840 // SAFETY:
1841 // * If `self.current` is `Some`, then `node` is a pointer to a live node in `list`
1842 // and don't have mutable reference.
1843 // * `self.current` (possible `None`) and `node_prev` belong to `self.list`,
1844 // while `spliced_node` does not belong to any list.
1845 // * This method only inserts one node, so `spliced_node` is both the head and tail of the new nodes to be spliced in.
1846 // * The length of the new nodes to be spliced in is 1.
1847 // * If `self.current` is `None`, then `node_prev` is the tail of the list.
1848 // If `self.current` is `Some`, then `node_prev` is the previous node before `self.current`.
1849 unsafe {
1850 let node_prev = match self.current {
1851 None => self.list.tail,
1852 Some(node) => node.as_ref().prev,
1853 };
1854 self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
1855 }
1856 self.index += 1;
1857 }
1858
1859 /// Removes the current element from the `LinkedList`.
1860 ///
1861 /// The element that was removed is returned, and the cursor is
1862 /// moved to point to the next element in the `LinkedList`.
1863 ///
1864 /// If the cursor is currently pointing to the "ghost" non-element then no element
1865 /// is removed and `None` is returned.
1866 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1867 pub fn remove_current(&mut self) -> Option<T> {
1868 let unlinked_node = self.current?;
1869 // SAFETY: `unlinked_node` is a pointer to a live node owned by `self.list`.
1870 // It is safe to unlink it and construct a `Box` from it.
1871 unsafe {
1872 self.current = unlinked_node.as_ref().next;
1873 self.list.unlink_node(unlinked_node);
1874 let unlinked_node = Box::from_raw_in(unlinked_node.as_ptr(), &self.list.alloc);
1875 Some(unlinked_node.element)
1876 }
1877 }
1878
1879 /// Removes the current element from the `LinkedList` without deallocating the list node.
1880 ///
1881 /// The node that was removed is returned as a new `LinkedList` containing only this node.
1882 /// The cursor is moved to point to the next element in the current `LinkedList`.
1883 ///
1884 /// If the cursor is currently pointing to the "ghost" non-element then no element
1885 /// is removed and `None` is returned.
1886 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1887 pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T, A>>
1888 where
1889 A: AllocatorClone,
1890 {
1891 let mut unlinked_node = self.current?;
1892 // SAFETY: `unlinked_node` is a pointer to a live node owned by `self.list`.
1893 // It is safe to unlink it. Also, `unlinked_node` does not have any mutable reference.
1894 unsafe {
1895 self.current = unlinked_node.as_ref().next;
1896 self.list.unlink_node(unlinked_node);
1897
1898 unlinked_node.as_mut().prev = None;
1899 unlinked_node.as_mut().next = None;
1900 }
1901 Some(LinkedList {
1902 head: Some(unlinked_node),
1903 tail: Some(unlinked_node),
1904 len: 1,
1905 alloc: self.list.alloc.clone(),
1906 marker: PhantomData,
1907 })
1908 }
1909
1910 /// Splits the list into two after the current element. This will return a
1911 /// new list consisting of everything after the cursor, with the original
1912 /// list retaining everything before.
1913 ///
1914 /// If the cursor is pointing at the "ghost" non-element then the entire contents
1915 /// of the `LinkedList` are moved.
1916 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1917 pub fn split_after(&mut self) -> LinkedList<T, A>
1918 where
1919 A: AllocatorClone,
1920 {
1921 let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
1922 if self.index == self.list.len {
1923 // The "ghost" non-element's index has changed to 0.
1924 self.index = 0;
1925 }
1926 // SAFETY: If `self.current` is `Some`, it contains a pointer to a live node in `list`,
1927 // and `split_off_idx` is `self.index + 1`.
1928 unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
1929 }
1930
1931 /// Splits the list into two before the current element. This will return a
1932 /// new list consisting of everything before the cursor, with the original
1933 /// list retaining everything after.
1934 ///
1935 /// If the cursor is pointing at the "ghost" non-element then the entire contents
1936 /// of the `LinkedList` are moved.
1937 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1938 pub fn split_before(&mut self) -> LinkedList<T, A>
1939 where
1940 A: AllocatorClone,
1941 {
1942 let split_off_idx = self.index;
1943 self.index = 0;
1944 // SAFETY: If `self.current` is `Some`, it contains a pointer to a live node in `list`,
1945 // and `split_off_idx` is the index of `self.current`.
1946 unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
1947 }
1948
1949 /// Appends an element to the front of the cursor's parent list. The node
1950 /// that the cursor points to is unchanged, even if it is the "ghost" node.
1951 ///
1952 /// This operation should compute in *O*(1) time.
1953 // `push_front` continues to point to "ghost" when it adds a node to mimic
1954 // the behavior of `insert_before` on an empty list.
1955 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1956 pub fn push_front(&mut self, elt: T) {
1957 // Safety: We know that `push_front` does not change the position in
1958 // memory of other nodes. This ensures that `self.current` remains
1959 // valid.
1960 self.list.push_front(elt);
1961 self.index += 1;
1962 }
1963
1964 /// Appends an element to the back of the cursor's parent list. The node
1965 /// that the cursor points to is unchanged, even if it is the "ghost" node.
1966 ///
1967 /// This operation should compute in *O*(1) time.
1968 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1969 #[rustc_confusables("push", "append")]
1970 pub fn push_back(&mut self, elt: T) {
1971 // Safety: We know that `push_back` does not change the position in
1972 // memory of other nodes. This ensures that `self.current` remains
1973 // valid.
1974 self.list.push_back(elt);
1975 if self.current().is_none() {
1976 // The index of "ghost" is the length of the list, so we just need
1977 // to increment self.index to reflect the new length of the list.
1978 self.index += 1;
1979 }
1980 }
1981
1982 /// Removes the first element from the cursor's parent list and returns it,
1983 /// or None if the list is empty. The element the cursor points to remains
1984 /// unchanged, unless it was pointing to the front element. In that case, it
1985 /// points to the new front element.
1986 ///
1987 /// This operation should compute in *O*(1) time.
1988 #[unstable(feature = "linked_list_cursors", issue = "58533")]
1989 pub fn pop_front(&mut self) -> Option<T> {
1990 // We can't check if current is empty, we must check the list directly.
1991 // It is possible for `self.current == None` and the list to be
1992 // non-empty.
1993 if self.list.is_empty() {
1994 None
1995 } else {
1996 // We can't point to the node that we pop. Copying the behavior of
1997 // `remove_current`, we move on to the next node in the sequence.
1998 // If the list is of length 1 then we end pointing to the "ghost"
1999 // node at index 0, which is expected.
2000 if self.list.head == self.current {
2001 self.move_next();
2002 }
2003 // An element was removed before (or at) our current position, so
2004 // the index must be decremented. `saturating_sub` handles the
2005 // ghost node case where index could be 0.
2006 self.index = self.index.saturating_sub(1);
2007 self.list.pop_front()
2008 }
2009 }
2010
2011 /// Removes the last element from the cursor's parent list and returns it,
2012 /// or None if the list is empty. The element the cursor points to remains
2013 /// unchanged, unless it was pointing to the back element. In that case, it
2014 /// points to the "ghost" element.
2015 ///
2016 /// This operation should compute in *O*(1) time.
2017 #[unstable(feature = "linked_list_cursors", issue = "58533")]
2018 #[rustc_confusables("pop")]
2019 pub fn pop_back(&mut self) -> Option<T> {
2020 if self.list.is_empty() {
2021 None
2022 } else {
2023 if self.list.tail == self.current {
2024 // The index now reflects the length of the list. It was the
2025 // length of the list minus 1, but now the list is 1 smaller. No
2026 // change is needed for `index`.
2027 self.current = None;
2028 } else if self.current.is_none() {
2029 self.index = self.list.len - 1;
2030 }
2031 self.list.pop_back()
2032 }
2033 }
2034
2035 /// Provides a reference to the front element of the cursor's parent list,
2036 /// or None if the list is empty.
2037 #[must_use]
2038 #[unstable(feature = "linked_list_cursors", issue = "58533")]
2039 #[rustc_confusables("first")]
2040 pub fn front(&self) -> Option<&T> {
2041 self.list.front()
2042 }
2043
2044 /// Provides a mutable reference to the front element of the cursor's
2045 /// parent list, or None if the list is empty.
2046 #[must_use]
2047 #[unstable(feature = "linked_list_cursors", issue = "58533")]
2048 pub fn front_mut(&mut self) -> Option<&mut T> {
2049 self.list.front_mut()
2050 }
2051
2052 /// Provides a reference to the back element of the cursor's parent list,
2053 /// or None if the list is empty.
2054 #[must_use]
2055 #[unstable(feature = "linked_list_cursors", issue = "58533")]
2056 #[rustc_confusables("last")]
2057 pub fn back(&self) -> Option<&T> {
2058 self.list.back()
2059 }
2060
2061 /// Provides a mutable reference to back element of the cursor's parent
2062 /// list, or `None` if the list is empty.
2063 ///
2064 /// # Examples
2065 /// Building and mutating a list with a cursor, then getting the back element:
2066 /// ```
2067 /// #![feature(linked_list_cursors)]
2068 /// use std::collections::LinkedList;
2069 /// let mut dl = LinkedList::new();
2070 /// dl.push_front(3);
2071 /// dl.push_front(2);
2072 /// dl.push_front(1);
2073 /// let mut cursor = dl.cursor_front_mut();
2074 /// *cursor.current().unwrap() = 99;
2075 /// *cursor.back_mut().unwrap() = 0;
2076 /// let mut contents = dl.into_iter();
2077 /// assert_eq!(contents.next(), Some(99));
2078 /// assert_eq!(contents.next(), Some(2));
2079 /// assert_eq!(contents.next(), Some(0));
2080 /// assert_eq!(contents.next(), None);
2081 /// ```
2082 #[must_use]
2083 #[unstable(feature = "linked_list_cursors", issue = "58533")]
2084 pub fn back_mut(&mut self) -> Option<&mut T> {
2085 self.list.back_mut()
2086 }
2087}
2088
2089/// This `struct` is created by the [`extract_if`] method on [`LinkedList`].
2090///
2091/// [`extract_if`]: LinkedList::extract_if
2092#[stable(feature = "extract_if", since = "1.87.0")]
2093#[must_use = "iterators are lazy and do nothing unless consumed; \
2094 use `extract_if().for_each(drop)` to remove and discard elements"]
2095pub struct ExtractIf<
2096 'a,
2097 T: 'a,
2098 F: 'a,
2099 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: Allocator = Global,
2100> {
2101 list: &'a mut LinkedList<T, A>,
2102 it: Option<NonNull<Node<T>>>,
2103 pred: F,
2104 idx: usize,
2105 old_len: usize,
2106}
2107
2108#[stable(feature = "extract_if", since = "1.87.0")]
2109impl<T, F, A: Allocator> Iterator for ExtractIf<'_, T, F, A>
2110where
2111 F: FnMut(&mut T) -> bool,
2112{
2113 type Item = T;
2114
2115 fn next(&mut self) -> Option<T> {
2116 while let Some(mut node) = self.it {
2117 // SAFETY: `node` is a pointer to a live node in `list`, which don't have mutable reference.
2118 unsafe {
2119 self.it = node.as_ref().next;
2120 self.idx += 1;
2121
2122 if (self.pred)(&mut node.as_mut().element) {
2123 // `unlink_node` is okay with aliasing `element` references.
2124 self.list.unlink_node(node);
2125 return Some(Box::from_raw_in(node.as_ptr(), &self.list.alloc).element);
2126 }
2127 }
2128 }
2129
2130 None
2131 }
2132
2133 fn size_hint(&self) -> (usize, Option<usize>) {
2134 (0, Some(self.old_len - self.idx))
2135 }
2136}
2137
2138#[stable(feature = "extract_if", since = "1.87.0")]
2139impl<T, F, A> fmt::Debug for ExtractIf<'_, T, F, A>
2140where
2141 T: fmt::Debug,
2142 A: Allocator,
2143{
2144 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2145 // SAFETY: If `node` is `Some`, then `node` is a pointer to a live node in `list`.
2146 let peek = self.it.map(|node| unsafe { &node.as_ref().element });
2147 f.debug_struct("ExtractIf").field("peek", &peek).finish_non_exhaustive()
2148 }
2149}
2150
2151#[stable(feature = "rust1", since = "1.0.0")]
2152impl<T, A: Allocator> Iterator for IntoIter<T, A> {
2153 type Item = T;
2154
2155 #[inline]
2156 fn next(&mut self) -> Option<T> {
2157 self.list.pop_front()
2158 }
2159
2160 #[inline]
2161 fn size_hint(&self) -> (usize, Option<usize>) {
2162 (self.list.len, Some(self.list.len))
2163 }
2164}
2165
2166#[stable(feature = "rust1", since = "1.0.0")]
2167impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
2168 #[inline]
2169 fn next_back(&mut self) -> Option<T> {
2170 self.list.pop_back()
2171 }
2172}
2173
2174#[stable(feature = "rust1", since = "1.0.0")]
2175impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {}
2176
2177#[stable(feature = "fused", since = "1.26.0")]
2178impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
2179
2180#[unstable(feature = "trusted_len", issue = "37572")]
2181unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {}
2182
2183#[stable(feature = "default_iters", since = "1.70.0")]
2184impl<T> Default for IntoIter<T> {
2185 /// Creates an empty `linked_list::IntoIter`.
2186 ///
2187 /// ```
2188 /// # use std::collections::linked_list;
2189 /// let iter: linked_list::IntoIter<u8> = Default::default();
2190 /// assert_eq!(iter.len(), 0);
2191 /// ```
2192 fn default() -> Self {
2193 LinkedList::new().into_iter()
2194 }
2195}
2196
2197#[stable(feature = "rust1", since = "1.0.0")]
2198impl<T> FromIterator<T> for LinkedList<T> {
2199 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
2200 let mut list = Self::new();
2201 list.extend(iter);
2202 list
2203 }
2204}
2205
2206#[stable(feature = "rust1", since = "1.0.0")]
2207impl<T, A: Allocator> IntoIterator for LinkedList<T, A> {
2208 type Item = T;
2209 type IntoIter = IntoIter<T, A>;
2210
2211 /// Consumes the list into an iterator yielding elements by value.
2212 #[inline]
2213 fn into_iter(self) -> IntoIter<T, A> {
2214 IntoIter { list: self }
2215 }
2216}
2217
2218#[stable(feature = "rust1", since = "1.0.0")]
2219impl<'a, T, A: Allocator> IntoIterator for &'a LinkedList<T, A> {
2220 type Item = &'a T;
2221 type IntoIter = Iter<'a, T>;
2222
2223 fn into_iter(self) -> Iter<'a, T> {
2224 self.iter()
2225 }
2226}
2227
2228#[stable(feature = "rust1", since = "1.0.0")]
2229impl<'a, T, A: Allocator> IntoIterator for &'a mut LinkedList<T, A> {
2230 type Item = &'a mut T;
2231 type IntoIter = IterMut<'a, T>;
2232
2233 fn into_iter(self) -> IterMut<'a, T> {
2234 self.iter_mut()
2235 }
2236}
2237
2238#[stable(feature = "rust1", since = "1.0.0")]
2239impl<T, A: Allocator> Extend<T> for LinkedList<T, A> {
2240 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
2241 <Self as SpecExtend<I>>::spec_extend(self, iter);
2242 }
2243
2244 #[inline]
2245 fn extend_one(&mut self, elem: T) {
2246 self.push_back(elem);
2247 }
2248}
2249
2250impl<I: IntoIterator, A: Allocator> SpecExtend<I> for LinkedList<I::Item, A> {
2251 default fn spec_extend(&mut self, iter: I) {
2252 iter.into_iter().for_each(move |elt| self.push_back(elt));
2253 }
2254}
2255
2256impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> {
2257 fn spec_extend(&mut self, ref mut other: LinkedList<T>) {
2258 self.append(other);
2259 }
2260}
2261
2262#[stable(feature = "extend_ref", since = "1.2.0")]
2263impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for LinkedList<T, A> {
2264 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
2265 self.extend(iter.into_iter().cloned());
2266 }
2267
2268 #[inline]
2269 fn extend_one(&mut self, &elem: &'a T) {
2270 self.push_back(elem);
2271 }
2272}
2273
2274#[stable(feature = "rust1", since = "1.0.0")]
2275impl<T: PartialEq, A: Allocator> PartialEq for LinkedList<T, A> {
2276 fn eq(&self, other: &Self) -> bool {
2277 self.len() == other.len() && self.iter().eq(other)
2278 }
2279
2280 fn ne(&self, other: &Self) -> bool {
2281 self.len() != other.len() || self.iter().ne(other)
2282 }
2283}
2284
2285#[stable(feature = "rust1", since = "1.0.0")]
2286impl<T: Eq, A: Allocator> Eq for LinkedList<T, A> {}
2287
2288#[stable(feature = "rust1", since = "1.0.0")]
2289impl<T: PartialOrd, A: Allocator> PartialOrd for LinkedList<T, A> {
2290 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2291 self.iter().partial_cmp(other)
2292 }
2293}
2294
2295#[stable(feature = "rust1", since = "1.0.0")]
2296impl<T: Ord, A: Allocator> Ord for LinkedList<T, A> {
2297 #[inline]
2298 fn cmp(&self, other: &Self) -> Ordering {
2299 self.iter().cmp(other)
2300 }
2301}
2302
2303#[stable(feature = "rust1", since = "1.0.0")]
2304impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A> {
2305 fn clone(&self) -> Self {
2306 let mut list = Self::new_in(self.alloc.clone());
2307 list.extend(self.iter().cloned());
2308 list
2309 }
2310
2311 /// Overwrites the contents of `self` with a clone of the contents of `source`.
2312 ///
2313 /// This method is preferred over simply assigning `source.clone()` to `self`,
2314 /// as it avoids reallocation of the nodes of the linked list. Additionally,
2315 /// if the element type `T` overrides `clone_from()`, this will reuse the
2316 /// resources of `self`'s elements as well.
2317 fn clone_from(&mut self, source: &Self) {
2318 let mut source_iter = source.iter();
2319 for elem in self.iter_mut() {
2320 let Some(source_elem) = source_iter.next() else {
2321 break;
2322 };
2323 elem.clone_from(source_elem);
2324 }
2325 while self.len() > source.len() {
2326 self.pop_back();
2327 }
2328 if !source_iter.is_empty() {
2329 self.extend(source_iter.cloned());
2330 }
2331 }
2332}
2333
2334#[stable(feature = "rust1", since = "1.0.0")]
2335impl<T: fmt::Debug, A: Allocator> fmt::Debug for LinkedList<T, A> {
2336 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2337 f.debug_list().entries(self).finish()
2338 }
2339}
2340
2341#[stable(feature = "rust1", since = "1.0.0")]
2342impl<T: Hash, A: Allocator> Hash for LinkedList<T, A> {
2343 fn hash<H: Hasher>(&self, state: &mut H) {
2344 state.write_length_prefix(self.len());
2345 for elt in self {
2346 elt.hash(state);
2347 }
2348 }
2349}
2350
2351#[stable(feature = "std_collections_from_array", since = "1.56.0")]
2352impl<T, const N: usize> From<[T; N]> for LinkedList<T> {
2353 /// Converts a `[T; N]` into a `LinkedList<T>`.
2354 ///
2355 /// ```
2356 /// use std::collections::LinkedList;
2357 ///
2358 /// let list1 = LinkedList::from([1, 2, 3, 4]);
2359 /// let list2: LinkedList<_> = [1, 2, 3, 4].into();
2360 /// assert_eq!(list1, list2);
2361 /// ```
2362 fn from(arr: [T; N]) -> Self {
2363 Self::from_iter(arr)
2364 }
2365}
2366
2367// Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
2368#[allow(dead_code)]
2369fn assert_covariance() {
2370 fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> {
2371 x
2372 }
2373 fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> {
2374 x
2375 }
2376 fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> {
2377 x
2378 }
2379}
2380
2381#[stable(feature = "rust1", since = "1.0.0")]
2382unsafe impl<T: Send, A: Allocator + Send> Send for LinkedList<T, A> {}
2383
2384#[stable(feature = "rust1", since = "1.0.0")]
2385unsafe impl<T: Sync, A: Allocator + Sync> Sync for LinkedList<T, A> {}
2386
2387#[stable(feature = "rust1", since = "1.0.0")]
2388unsafe impl<T: Sync> Send for Iter<'_, T> {}
2389
2390#[stable(feature = "rust1", since = "1.0.0")]
2391unsafe impl<T: Sync> Sync for Iter<'_, T> {}
2392
2393#[stable(feature = "rust1", since = "1.0.0")]
2394unsafe impl<T: Send> Send for IterMut<'_, T> {}
2395
2396#[stable(feature = "rust1", since = "1.0.0")]
2397unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
2398
2399#[unstable(feature = "linked_list_cursors", issue = "58533")]
2400unsafe impl<T: Sync, A: Allocator + Sync> Send for Cursor<'_, T, A> {}
2401
2402#[unstable(feature = "linked_list_cursors", issue = "58533")]
2403unsafe impl<T: Sync, A: Allocator + Sync> Sync for Cursor<'_, T, A> {}
2404
2405#[unstable(feature = "linked_list_cursors", issue = "58533")]
2406unsafe impl<T: Send, A: Allocator + Send> Send for CursorMut<'_, T, A> {}
2407
2408#[unstable(feature = "linked_list_cursors", issue = "58533")]
2409unsafe impl<T: Sync, A: Allocator + Sync> Sync for CursorMut<'_, T, A> {}