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