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