]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //! A doubly-linked list with owned nodes. |
2 | //! | |
32a655c1 SL |
3 | //! The `LinkedList` allows pushing and popping elements at either end |
4 | //! in constant time. | |
5 | //! | |
60c5eb7d XL |
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. | |
32a655c1 | 9 | //! |
3dfed10e XL |
10 | //! [`Vec`]: crate::vec::Vec |
11 | //! [`VecDeque`]: super::vec_deque::VecDeque | |
1a4d82fc | 12 | |
85aaf69f | 13 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 14 | |
1a4d82fc | 15 | use core::cmp::Ordering; |
1a4d82fc | 16 | use core::fmt; |
dfeec247 | 17 | use core::hash::{Hash, Hasher}; |
9e0c209e | 18 | use core::iter::{FromIterator, FusedIterator}; |
5bcae85e | 19 | use core::marker::PhantomData; |
1a4d82fc | 20 | use core::mem; |
83c7162d | 21 | use core::ptr::NonNull; |
1a4d82fc | 22 | |
a7813a04 | 23 | use super::SpecExtend; |
dfeec247 | 24 | use crate::boxed::Box; |
a7813a04 | 25 | |
416331ca XL |
26 | #[cfg(test)] |
27 | mod tests; | |
28 | ||
32a655c1 SL |
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 | /// | |
60c5eb7d XL |
34 | /// NOTE: It is almost always better to use `Vec` or `VecDeque` because |
35 | /// array-based containers are generally faster, | |
36 | /// more memory efficient, and make better use of CPU cache. | |
85aaf69f | 37 | #[stable(feature = "rust1", since = "1.0.0")] |
6a06907d | 38 | #[cfg_attr(not(test), rustc_diagnostic_item = "LinkedList")] |
85aaf69f | 39 | pub struct LinkedList<T> { |
2c00a5a8 XL |
40 | head: Option<NonNull<Node<T>>>, |
41 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e SL |
42 | len: usize, |
43 | marker: PhantomData<Box<Node<T>>>, | |
1a4d82fc JJ |
44 | } |
45 | ||
1a4d82fc | 46 | struct Node<T> { |
2c00a5a8 XL |
47 | next: Option<NonNull<Node<T>>>, |
48 | prev: Option<NonNull<Node<T>>>, | |
5bcae85e | 49 | element: T, |
1a4d82fc JJ |
50 | } |
51 | ||
cc61c64b XL |
52 | /// An iterator over the elements of a `LinkedList`. |
53 | /// | |
3dfed10e | 54 | /// This `struct` is created by [`LinkedList::iter()`]. See its |
cc61c64b | 55 | /// documentation for more. |
85aaf69f | 56 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 57 | pub struct Iter<'a, T: 'a> { |
2c00a5a8 XL |
58 | head: Option<NonNull<Node<T>>>, |
59 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e SL |
60 | len: usize, |
61 | marker: PhantomData<&'a Node<T>>, | |
1a4d82fc JJ |
62 | } |
63 | ||
8bb4bdeb | 64 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
65 | impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { |
66 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
dfeec247 | 67 | f.debug_tuple("Iter").field(&self.len).finish() |
8bb4bdeb XL |
68 | } |
69 | } | |
70 | ||
ea8adc8c | 71 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
85aaf69f | 72 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 73 | impl<T> Clone for Iter<'_, T> { |
5bcae85e SL |
74 | fn clone(&self) -> Self { |
75 | Iter { ..*self } | |
1a4d82fc JJ |
76 | } |
77 | } | |
78 | ||
cc61c64b XL |
79 | /// A mutable iterator over the elements of a `LinkedList`. |
80 | /// | |
3dfed10e | 81 | /// This `struct` is created by [`LinkedList::iter_mut()`]. See its |
cc61c64b | 82 | /// documentation for more. |
85aaf69f | 83 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 84 | pub struct IterMut<'a, T: 'a> { |
48663c56 | 85 | // We do *not* exclusively own the entire list here, references to node's `element` |
60c5eb7d | 86 | // have been handed out by the iterator! So be careful when using this; the methods |
48663c56 | 87 | // called must be aware that there can be aliasing pointers to `element`. |
85aaf69f | 88 | list: &'a mut LinkedList<T>, |
2c00a5a8 XL |
89 | head: Option<NonNull<Node<T>>>, |
90 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e | 91 | len: usize, |
1a4d82fc JJ |
92 | } |
93 | ||
8bb4bdeb | 94 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
95 | impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { |
96 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
dfeec247 | 97 | f.debug_tuple("IterMut").field(&self.list).field(&self.len).finish() |
8bb4bdeb XL |
98 | } |
99 | } | |
100 | ||
cc61c64b XL |
101 | /// An owning iterator over the elements of a `LinkedList`. |
102 | /// | |
dfeec247 | 103 | /// This `struct` is created by the [`into_iter`] method on [`LinkedList`] |
cc61c64b XL |
104 | /// (provided by the `IntoIterator` trait). See its documentation for more. |
105 | /// | |
1b1a35ee | 106 | /// [`into_iter`]: LinkedList::into_iter |
1a4d82fc | 107 | #[derive(Clone)] |
85aaf69f | 108 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 109 | pub struct IntoIter<T> { |
92a42be0 | 110 | list: LinkedList<T>, |
1a4d82fc JJ |
111 | } |
112 | ||
8bb4bdeb XL |
113 | #[stable(feature = "collection_debug", since = "1.17.0")] |
114 | impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { | |
9fa01778 | 115 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
dfeec247 | 116 | f.debug_tuple("IntoIter").field(&self.list).finish() |
8bb4bdeb XL |
117 | } |
118 | } | |
119 | ||
1a4d82fc | 120 | impl<T> Node<T> { |
5bcae85e | 121 | fn new(element: T) -> Self { |
dfeec247 | 122 | Node { next: None, prev: None, element } |
1a4d82fc | 123 | } |
62682a34 | 124 | |
5bcae85e SL |
125 | fn into_element(self: Box<Self>) -> T { |
126 | self.element | |
62682a34 | 127 | } |
1a4d82fc JJ |
128 | } |
129 | ||
1a4d82fc | 130 | // private methods |
85aaf69f | 131 | impl<T> LinkedList<T> { |
5bcae85e | 132 | /// Adds the given node to the front of the list. |
1a4d82fc | 133 | #[inline] |
5bcae85e | 134 | fn push_front_node(&mut self, mut node: Box<Node<T>>) { |
48663c56 XL |
135 | // This method takes care not to create mutable references to whole nodes, |
136 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e SL |
137 | unsafe { |
138 | node.next = self.head; | |
139 | node.prev = None; | |
f9f354fc | 140 | let node = Some(Box::leak(node).into()); |
5bcae85e SL |
141 | |
142 | match self.head { | |
143 | None => self.tail = node, | |
48663c56 XL |
144 | // Not creating new mutable (unique!) references overlapping `element`. |
145 | Some(head) => (*head.as_ptr()).prev = node, | |
1a4d82fc | 146 | } |
5bcae85e SL |
147 | |
148 | self.head = node; | |
149 | self.len += 1; | |
1a4d82fc | 150 | } |
1a4d82fc JJ |
151 | } |
152 | ||
5bcae85e | 153 | /// Removes and returns the node at the front of the list. |
1a4d82fc JJ |
154 | #[inline] |
155 | fn pop_front_node(&mut self) -> Option<Box<Node<T>>> { | |
48663c56 XL |
156 | // This method takes care not to create mutable references to whole nodes, |
157 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e | 158 | self.head.map(|node| unsafe { |
7cac9316 | 159 | let node = Box::from_raw(node.as_ptr()); |
5bcae85e SL |
160 | self.head = node.next; |
161 | ||
162 | match self.head { | |
163 | None => self.tail = None, | |
48663c56 XL |
164 | // Not creating new mutable (unique!) references overlapping `element`. |
165 | Some(head) => (*head.as_ptr()).prev = None, | |
1a4d82fc | 166 | } |
5bcae85e SL |
167 | |
168 | self.len -= 1; | |
169 | node | |
1a4d82fc JJ |
170 | }) |
171 | } | |
172 | ||
5bcae85e | 173 | /// Adds the given node to the back of the list. |
1a4d82fc | 174 | #[inline] |
5bcae85e | 175 | fn push_back_node(&mut self, mut node: Box<Node<T>>) { |
48663c56 XL |
176 | // This method takes care not to create mutable references to whole nodes, |
177 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e SL |
178 | unsafe { |
179 | node.next = None; | |
180 | node.prev = self.tail; | |
f9f354fc | 181 | let node = Some(Box::leak(node).into()); |
5bcae85e SL |
182 | |
183 | match self.tail { | |
184 | None => self.head = node, | |
48663c56 XL |
185 | // Not creating new mutable (unique!) references overlapping `element`. |
186 | Some(tail) => (*tail.as_ptr()).next = node, | |
1a4d82fc | 187 | } |
5bcae85e SL |
188 | |
189 | self.tail = node; | |
190 | self.len += 1; | |
1a4d82fc | 191 | } |
1a4d82fc JJ |
192 | } |
193 | ||
5bcae85e | 194 | /// Removes and returns the node at the back of the list. |
1a4d82fc JJ |
195 | #[inline] |
196 | fn pop_back_node(&mut self) -> Option<Box<Node<T>>> { | |
48663c56 XL |
197 | // This method takes care not to create mutable references to whole nodes, |
198 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e | 199 | self.tail.map(|node| unsafe { |
7cac9316 | 200 | let node = Box::from_raw(node.as_ptr()); |
5bcae85e SL |
201 | self.tail = node.prev; |
202 | ||
203 | match self.tail { | |
204 | None => self.head = None, | |
48663c56 XL |
205 | // Not creating new mutable (unique!) references overlapping `element`. |
206 | Some(tail) => (*tail.as_ptr()).next = None, | |
5bcae85e SL |
207 | } |
208 | ||
209 | self.len -= 1; | |
210 | node | |
211 | }) | |
1a4d82fc | 212 | } |
ff7c6d11 XL |
213 | |
214 | /// Unlinks the specified node from the current list. | |
215 | /// | |
216 | /// Warning: this will not check that the provided node belongs to the current list. | |
48663c56 XL |
217 | /// |
218 | /// This method takes care not to create mutable references to `element`, to | |
219 | /// maintain validity of aliasing pointers. | |
ff7c6d11 | 220 | #[inline] |
2c00a5a8 | 221 | unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) { |
f035d41b | 222 | let node = unsafe { node.as_mut() }; // this one is ours now, we can create an &mut. |
ff7c6d11 | 223 | |
48663c56 | 224 | // Not creating new mutable (unique!) references overlapping `element`. |
ff7c6d11 | 225 | match node.prev { |
f035d41b | 226 | Some(prev) => unsafe { (*prev.as_ptr()).next = node.next }, |
ff7c6d11 | 227 | // this node is the head node |
416331ca | 228 | None => self.head = node.next, |
ff7c6d11 XL |
229 | }; |
230 | ||
231 | match node.next { | |
f035d41b | 232 | Some(next) => unsafe { (*next.as_ptr()).prev = node.prev }, |
ff7c6d11 | 233 | // this node is the tail node |
416331ca | 234 | None => self.tail = node.prev, |
ff7c6d11 XL |
235 | }; |
236 | ||
237 | self.len -= 1; | |
238 | } | |
dfeec247 XL |
239 | |
240 | /// Splices a series of nodes between two existing nodes. | |
241 | /// | |
242 | /// Warning: this will not check that the provided node belongs to the two existing lists. | |
243 | #[inline] | |
244 | unsafe fn splice_nodes( | |
245 | &mut self, | |
246 | existing_prev: Option<NonNull<Node<T>>>, | |
247 | existing_next: Option<NonNull<Node<T>>>, | |
248 | mut splice_start: NonNull<Node<T>>, | |
249 | mut splice_end: NonNull<Node<T>>, | |
250 | splice_length: usize, | |
251 | ) { | |
252 | // This method takes care not to create multiple mutable references to whole nodes at the same time, | |
253 | // to maintain validity of aliasing pointers into `element`. | |
254 | if let Some(mut existing_prev) = existing_prev { | |
f035d41b XL |
255 | unsafe { |
256 | existing_prev.as_mut().next = Some(splice_start); | |
257 | } | |
dfeec247 XL |
258 | } else { |
259 | self.head = Some(splice_start); | |
260 | } | |
261 | if let Some(mut existing_next) = existing_next { | |
f035d41b XL |
262 | unsafe { |
263 | existing_next.as_mut().prev = Some(splice_end); | |
264 | } | |
dfeec247 XL |
265 | } else { |
266 | self.tail = Some(splice_end); | |
267 | } | |
f035d41b XL |
268 | unsafe { |
269 | splice_start.as_mut().prev = existing_prev; | |
270 | splice_end.as_mut().next = existing_next; | |
271 | } | |
dfeec247 XL |
272 | |
273 | self.len += splice_length; | |
274 | } | |
275 | ||
276 | /// Detaches all nodes from a linked list as a series of nodes. | |
277 | #[inline] | |
278 | fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> { | |
279 | let head = self.head.take(); | |
280 | let tail = self.tail.take(); | |
281 | let len = mem::replace(&mut self.len, 0); | |
282 | if let Some(head) = head { | |
283 | let tail = tail.unwrap_or_else(|| unsafe { core::hint::unreachable_unchecked() }); | |
284 | Some((head, tail, len)) | |
285 | } else { | |
286 | None | |
287 | } | |
288 | } | |
289 | ||
290 | #[inline] | |
291 | unsafe fn split_off_before_node( | |
292 | &mut self, | |
293 | split_node: Option<NonNull<Node<T>>>, | |
294 | at: usize, | |
295 | ) -> Self { | |
296 | // The split node is the new head node of the second part | |
297 | if let Some(mut split_node) = split_node { | |
298 | let first_part_head; | |
299 | let first_part_tail; | |
f035d41b XL |
300 | unsafe { |
301 | first_part_tail = split_node.as_mut().prev.take(); | |
302 | } | |
dfeec247 | 303 | if let Some(mut tail) = first_part_tail { |
f035d41b XL |
304 | unsafe { |
305 | tail.as_mut().next = None; | |
306 | } | |
dfeec247 XL |
307 | first_part_head = self.head; |
308 | } else { | |
309 | first_part_head = None; | |
310 | } | |
311 | ||
312 | let first_part = LinkedList { | |
313 | head: first_part_head, | |
314 | tail: first_part_tail, | |
315 | len: at, | |
316 | marker: PhantomData, | |
317 | }; | |
318 | ||
319 | // Fix the head ptr of the second part | |
320 | self.head = Some(split_node); | |
321 | self.len = self.len - at; | |
322 | ||
323 | first_part | |
324 | } else { | |
325 | mem::replace(self, LinkedList::new()) | |
326 | } | |
327 | } | |
328 | ||
329 | #[inline] | |
330 | unsafe fn split_off_after_node( | |
331 | &mut self, | |
332 | split_node: Option<NonNull<Node<T>>>, | |
333 | at: usize, | |
334 | ) -> Self { | |
335 | // The split node is the new tail node of the first part and owns | |
336 | // the head of the second part. | |
337 | if let Some(mut split_node) = split_node { | |
338 | let second_part_head; | |
339 | let second_part_tail; | |
f035d41b XL |
340 | unsafe { |
341 | second_part_head = split_node.as_mut().next.take(); | |
342 | } | |
dfeec247 | 343 | if let Some(mut head) = second_part_head { |
f035d41b XL |
344 | unsafe { |
345 | head.as_mut().prev = None; | |
346 | } | |
dfeec247 XL |
347 | second_part_tail = self.tail; |
348 | } else { | |
349 | second_part_tail = None; | |
350 | } | |
351 | ||
352 | let second_part = LinkedList { | |
353 | head: second_part_head, | |
354 | tail: second_part_tail, | |
355 | len: self.len - at, | |
356 | marker: PhantomData, | |
357 | }; | |
358 | ||
359 | // Fix the tail ptr of the first part | |
360 | self.tail = Some(split_node); | |
361 | self.len = at; | |
362 | ||
363 | second_part | |
364 | } else { | |
365 | mem::replace(self, LinkedList::new()) | |
366 | } | |
367 | } | |
1a4d82fc JJ |
368 | } |
369 | ||
85aaf69f SL |
370 | #[stable(feature = "rust1", since = "1.0.0")] |
371 | impl<T> Default for LinkedList<T> { | |
9e0c209e | 372 | /// Creates an empty `LinkedList<T>`. |
1a4d82fc | 373 | #[inline] |
5bcae85e SL |
374 | fn default() -> Self { |
375 | Self::new() | |
92a42be0 | 376 | } |
1a4d82fc JJ |
377 | } |
378 | ||
85aaf69f SL |
379 | impl<T> LinkedList<T> { |
380 | /// Creates an empty `LinkedList`. | |
5bcae85e SL |
381 | /// |
382 | /// # Examples | |
383 | /// | |
384 | /// ``` | |
385 | /// use std::collections::LinkedList; | |
386 | /// | |
387 | /// let list: LinkedList<u32> = LinkedList::new(); | |
388 | /// ``` | |
1a4d82fc | 389 | #[inline] |
dfeec247 | 390 | #[rustc_const_stable(feature = "const_linked_list_new", since = "1.32.0")] |
85aaf69f | 391 | #[stable(feature = "rust1", since = "1.0.0")] |
e1599b0c | 392 | pub const fn new() -> Self { |
dfeec247 | 393 | LinkedList { head: None, tail: None, len: 0, marker: PhantomData } |
1a4d82fc JJ |
394 | } |
395 | ||
85aaf69f | 396 | /// Moves all elements from `other` to the end of the list. |
1a4d82fc | 397 | /// |
85aaf69f SL |
398 | /// This reuses all the nodes from `other` and moves them into `self`. After |
399 | /// this operation, `other` becomes empty. | |
400 | /// | |
3dfed10e | 401 | /// This operation should compute in *O*(1) time and *O*(1) memory. |
1a4d82fc JJ |
402 | /// |
403 | /// # Examples | |
404 | /// | |
85aaf69f SL |
405 | /// ``` |
406 | /// use std::collections::LinkedList; | |
1a4d82fc | 407 | /// |
5bcae85e SL |
408 | /// let mut list1 = LinkedList::new(); |
409 | /// list1.push_back('a'); | |
1a4d82fc | 410 | /// |
5bcae85e SL |
411 | /// let mut list2 = LinkedList::new(); |
412 | /// list2.push_back('b'); | |
413 | /// list2.push_back('c'); | |
1a4d82fc | 414 | /// |
5bcae85e SL |
415 | /// list1.append(&mut list2); |
416 | /// | |
417 | /// let mut iter = list1.iter(); | |
418 | /// assert_eq!(iter.next(), Some(&'a')); | |
419 | /// assert_eq!(iter.next(), Some(&'b')); | |
420 | /// assert_eq!(iter.next(), Some(&'c')); | |
421 | /// assert!(iter.next().is_none()); | |
422 | /// | |
423 | /// assert!(list2.is_empty()); | |
1a4d82fc | 424 | /// ``` |
c34b1796 | 425 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
426 | pub fn append(&mut self, other: &mut Self) { |
427 | match self.tail { | |
428 | None => mem::swap(self, other), | |
7cac9316 | 429 | Some(mut tail) => { |
48663c56 XL |
430 | // `as_mut` is okay here because we have exclusive access to the entirety |
431 | // of both lists. | |
7cac9316 | 432 | if let Some(mut other_head) = other.head.take() { |
32a655c1 | 433 | unsafe { |
7cac9316 XL |
434 | tail.as_mut().next = Some(other_head); |
435 | other_head.as_mut().prev = Some(tail); | |
32a655c1 | 436 | } |
5bcae85e | 437 | |
32a655c1 SL |
438 | self.tail = other.tail.take(); |
439 | self.len += mem::replace(&mut other.len, 0); | |
440 | } | |
441 | } | |
1a4d82fc JJ |
442 | } |
443 | } | |
444 | ||
dfeec247 XL |
445 | /// Moves all elements from `other` to the begin of the list. |
446 | #[unstable(feature = "linked_list_prepend", issue = "none")] | |
447 | pub fn prepend(&mut self, other: &mut Self) { | |
448 | match self.head { | |
449 | None => mem::swap(self, other), | |
450 | Some(mut head) => { | |
451 | // `as_mut` is okay here because we have exclusive access to the entirety | |
452 | // of both lists. | |
453 | if let Some(mut other_tail) = other.tail.take() { | |
454 | unsafe { | |
455 | head.as_mut().prev = Some(other_tail); | |
456 | other_tail.as_mut().next = Some(head); | |
457 | } | |
458 | ||
459 | self.head = other.head.take(); | |
460 | self.len += mem::replace(&mut other.len, 0); | |
461 | } | |
462 | } | |
463 | } | |
464 | } | |
465 | ||
1a4d82fc | 466 | /// Provides a forward iterator. |
5bcae85e SL |
467 | /// |
468 | /// # Examples | |
469 | /// | |
470 | /// ``` | |
471 | /// use std::collections::LinkedList; | |
472 | /// | |
473 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
474 | /// | |
475 | /// list.push_back(0); | |
476 | /// list.push_back(1); | |
477 | /// list.push_back(2); | |
478 | /// | |
479 | /// let mut iter = list.iter(); | |
480 | /// assert_eq!(iter.next(), Some(&0)); | |
481 | /// assert_eq!(iter.next(), Some(&1)); | |
482 | /// assert_eq!(iter.next(), Some(&2)); | |
483 | /// assert_eq!(iter.next(), None); | |
484 | /// ``` | |
1a4d82fc | 485 | #[inline] |
85aaf69f | 486 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 487 | pub fn iter(&self) -> Iter<'_, T> { |
dfeec247 | 488 | Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData } |
1a4d82fc JJ |
489 | } |
490 | ||
491 | /// Provides a forward iterator with mutable references. | |
5bcae85e SL |
492 | /// |
493 | /// # Examples | |
494 | /// | |
495 | /// ``` | |
496 | /// use std::collections::LinkedList; | |
497 | /// | |
498 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
499 | /// | |
500 | /// list.push_back(0); | |
501 | /// list.push_back(1); | |
502 | /// list.push_back(2); | |
503 | /// | |
504 | /// for element in list.iter_mut() { | |
505 | /// *element += 10; | |
506 | /// } | |
507 | /// | |
508 | /// let mut iter = list.iter(); | |
509 | /// assert_eq!(iter.next(), Some(&10)); | |
510 | /// assert_eq!(iter.next(), Some(&11)); | |
511 | /// assert_eq!(iter.next(), Some(&12)); | |
512 | /// assert_eq!(iter.next(), None); | |
513 | /// ``` | |
1a4d82fc | 514 | #[inline] |
85aaf69f | 515 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 516 | pub fn iter_mut(&mut self) -> IterMut<'_, T> { |
dfeec247 XL |
517 | IterMut { head: self.head, tail: self.tail, len: self.len, list: self } |
518 | } | |
519 | ||
520 | /// Provides a cursor at the front element. | |
521 | /// | |
522 | /// The cursor is pointing to the "ghost" non-element if the list is empty. | |
523 | #[inline] | |
524 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
525 | pub fn cursor_front(&self) -> Cursor<'_, T> { | |
526 | Cursor { index: 0, current: self.head, list: self } | |
527 | } | |
528 | ||
529 | /// Provides a cursor with editing operations at the front element. | |
530 | /// | |
531 | /// The cursor is pointing to the "ghost" non-element if the list is empty. | |
532 | #[inline] | |
533 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
534 | pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> { | |
535 | CursorMut { index: 0, current: self.head, list: self } | |
536 | } | |
537 | ||
538 | /// Provides a cursor at the back element. | |
539 | /// | |
540 | /// The cursor is pointing to the "ghost" non-element if the list is empty. | |
541 | #[inline] | |
542 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
543 | pub fn cursor_back(&self) -> Cursor<'_, T> { | |
544 | Cursor { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self } | |
545 | } | |
546 | ||
547 | /// Provides a cursor with editing operations at the back element. | |
548 | /// | |
549 | /// The cursor is pointing to the "ghost" non-element if the list is empty. | |
550 | #[inline] | |
551 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
552 | pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> { | |
553 | CursorMut { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self } | |
1a4d82fc JJ |
554 | } |
555 | ||
85aaf69f | 556 | /// Returns `true` if the `LinkedList` is empty. |
1a4d82fc | 557 | /// |
3dfed10e | 558 | /// This operation should compute in *O*(1) time. |
85aaf69f SL |
559 | /// |
560 | /// # Examples | |
561 | /// | |
562 | /// ``` | |
563 | /// use std::collections::LinkedList; | |
564 | /// | |
565 | /// let mut dl = LinkedList::new(); | |
566 | /// assert!(dl.is_empty()); | |
567 | /// | |
568 | /// dl.push_front("foo"); | |
569 | /// assert!(!dl.is_empty()); | |
570 | /// ``` | |
1a4d82fc | 571 | #[inline] |
85aaf69f | 572 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 573 | pub fn is_empty(&self) -> bool { |
5bcae85e | 574 | self.head.is_none() |
1a4d82fc JJ |
575 | } |
576 | ||
85aaf69f | 577 | /// Returns the length of the `LinkedList`. |
1a4d82fc | 578 | /// |
3dfed10e | 579 | /// This operation should compute in *O*(1) time. |
85aaf69f SL |
580 | /// |
581 | /// # Examples | |
582 | /// | |
583 | /// ``` | |
584 | /// use std::collections::LinkedList; | |
585 | /// | |
586 | /// let mut dl = LinkedList::new(); | |
587 | /// | |
588 | /// dl.push_front(2); | |
589 | /// assert_eq!(dl.len(), 1); | |
590 | /// | |
591 | /// dl.push_front(1); | |
592 | /// assert_eq!(dl.len(), 2); | |
593 | /// | |
594 | /// dl.push_back(3); | |
595 | /// assert_eq!(dl.len(), 3); | |
85aaf69f | 596 | /// ``` |
5869c6ff | 597 | #[doc(alias = "length")] |
1a4d82fc | 598 | #[inline] |
85aaf69f SL |
599 | #[stable(feature = "rust1", since = "1.0.0")] |
600 | pub fn len(&self) -> usize { | |
5bcae85e | 601 | self.len |
1a4d82fc JJ |
602 | } |
603 | ||
85aaf69f | 604 | /// Removes all elements from the `LinkedList`. |
1a4d82fc | 605 | /// |
3dfed10e | 606 | /// This operation should compute in *O*(*n*) time. |
85aaf69f SL |
607 | /// |
608 | /// # Examples | |
609 | /// | |
610 | /// ``` | |
611 | /// use std::collections::LinkedList; | |
612 | /// | |
613 | /// let mut dl = LinkedList::new(); | |
614 | /// | |
615 | /// dl.push_front(2); | |
616 | /// dl.push_front(1); | |
617 | /// assert_eq!(dl.len(), 2); | |
618 | /// assert_eq!(dl.front(), Some(&1)); | |
619 | /// | |
620 | /// dl.clear(); | |
621 | /// assert_eq!(dl.len(), 0); | |
622 | /// assert_eq!(dl.front(), None); | |
85aaf69f | 623 | /// ``` |
1a4d82fc | 624 | #[inline] |
85aaf69f | 625 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 626 | pub fn clear(&mut self) { |
5bcae85e | 627 | *self = Self::new(); |
1a4d82fc JJ |
628 | } |
629 | ||
a7813a04 XL |
630 | /// Returns `true` if the `LinkedList` contains an element equal to the |
631 | /// given value. | |
5bcae85e SL |
632 | /// |
633 | /// # Examples | |
634 | /// | |
635 | /// ``` | |
636 | /// use std::collections::LinkedList; | |
637 | /// | |
638 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
639 | /// | |
640 | /// list.push_back(0); | |
641 | /// list.push_back(1); | |
642 | /// list.push_back(2); | |
643 | /// | |
644 | /// assert_eq!(list.contains(&0), true); | |
645 | /// assert_eq!(list.contains(&10), false); | |
646 | /// ``` | |
647 | #[stable(feature = "linked_list_contains", since = "1.12.0")] | |
a7813a04 | 648 | pub fn contains(&self, x: &T) -> bool |
dfeec247 XL |
649 | where |
650 | T: PartialEq<T>, | |
a7813a04 XL |
651 | { |
652 | self.iter().any(|e| e == x) | |
653 | } | |
654 | ||
1a4d82fc JJ |
655 | /// Provides a reference to the front element, or `None` if the list is |
656 | /// empty. | |
85aaf69f SL |
657 | /// |
658 | /// # Examples | |
659 | /// | |
660 | /// ``` | |
661 | /// use std::collections::LinkedList; | |
662 | /// | |
663 | /// let mut dl = LinkedList::new(); | |
664 | /// assert_eq!(dl.front(), None); | |
665 | /// | |
666 | /// dl.push_front(1); | |
667 | /// assert_eq!(dl.front(), Some(&1)); | |
85aaf69f | 668 | /// ``` |
1a4d82fc | 669 | #[inline] |
85aaf69f | 670 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 671 | pub fn front(&self) -> Option<&T> { |
dfeec247 | 672 | unsafe { self.head.as_ref().map(|node| &node.as_ref().element) } |
1a4d82fc JJ |
673 | } |
674 | ||
675 | /// Provides a mutable reference to the front element, or `None` if the list | |
676 | /// is empty. | |
85aaf69f SL |
677 | /// |
678 | /// # Examples | |
679 | /// | |
680 | /// ``` | |
681 | /// use std::collections::LinkedList; | |
682 | /// | |
683 | /// let mut dl = LinkedList::new(); | |
684 | /// assert_eq!(dl.front(), None); | |
685 | /// | |
686 | /// dl.push_front(1); | |
687 | /// assert_eq!(dl.front(), Some(&1)); | |
688 | /// | |
689 | /// match dl.front_mut() { | |
690 | /// None => {}, | |
691 | /// Some(x) => *x = 5, | |
692 | /// } | |
693 | /// assert_eq!(dl.front(), Some(&5)); | |
85aaf69f | 694 | /// ``` |
1a4d82fc | 695 | #[inline] |
85aaf69f | 696 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 697 | pub fn front_mut(&mut self) -> Option<&mut T> { |
dfeec247 | 698 | unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) } |
1a4d82fc JJ |
699 | } |
700 | ||
701 | /// Provides a reference to the back element, or `None` if the list is | |
702 | /// empty. | |
85aaf69f SL |
703 | /// |
704 | /// # Examples | |
705 | /// | |
706 | /// ``` | |
707 | /// use std::collections::LinkedList; | |
708 | /// | |
709 | /// let mut dl = LinkedList::new(); | |
710 | /// assert_eq!(dl.back(), None); | |
711 | /// | |
712 | /// dl.push_back(1); | |
713 | /// assert_eq!(dl.back(), Some(&1)); | |
85aaf69f | 714 | /// ``` |
1a4d82fc | 715 | #[inline] |
85aaf69f | 716 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 717 | pub fn back(&self) -> Option<&T> { |
dfeec247 | 718 | unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) } |
1a4d82fc JJ |
719 | } |
720 | ||
721 | /// Provides a mutable reference to the back element, or `None` if the list | |
722 | /// is empty. | |
85aaf69f SL |
723 | /// |
724 | /// # Examples | |
725 | /// | |
726 | /// ``` | |
727 | /// use std::collections::LinkedList; | |
728 | /// | |
729 | /// let mut dl = LinkedList::new(); | |
730 | /// assert_eq!(dl.back(), None); | |
731 | /// | |
732 | /// dl.push_back(1); | |
733 | /// assert_eq!(dl.back(), Some(&1)); | |
734 | /// | |
735 | /// match dl.back_mut() { | |
736 | /// None => {}, | |
737 | /// Some(x) => *x = 5, | |
738 | /// } | |
739 | /// assert_eq!(dl.back(), Some(&5)); | |
85aaf69f | 740 | /// ``` |
1a4d82fc | 741 | #[inline] |
85aaf69f | 742 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 743 | pub fn back_mut(&mut self) -> Option<&mut T> { |
dfeec247 | 744 | unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) } |
1a4d82fc JJ |
745 | } |
746 | ||
747 | /// Adds an element first in the list. | |
748 | /// | |
3dfed10e | 749 | /// This operation should compute in *O*(1) time. |
85aaf69f SL |
750 | /// |
751 | /// # Examples | |
752 | /// | |
753 | /// ``` | |
754 | /// use std::collections::LinkedList; | |
755 | /// | |
756 | /// let mut dl = LinkedList::new(); | |
757 | /// | |
758 | /// dl.push_front(2); | |
759 | /// assert_eq!(dl.front().unwrap(), &2); | |
760 | /// | |
761 | /// dl.push_front(1); | |
762 | /// assert_eq!(dl.front().unwrap(), &1); | |
85aaf69f SL |
763 | /// ``` |
764 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 765 | pub fn push_front(&mut self, elt: T) { |
5bcae85e | 766 | self.push_front_node(box Node::new(elt)); |
1a4d82fc JJ |
767 | } |
768 | ||
769 | /// Removes the first element and returns it, or `None` if the list is | |
770 | /// empty. | |
771 | /// | |
3dfed10e | 772 | /// This operation should compute in *O*(1) time. |
85aaf69f SL |
773 | /// |
774 | /// # Examples | |
775 | /// | |
776 | /// ``` | |
777 | /// use std::collections::LinkedList; | |
778 | /// | |
779 | /// let mut d = LinkedList::new(); | |
780 | /// assert_eq!(d.pop_front(), None); | |
781 | /// | |
782 | /// d.push_front(1); | |
783 | /// d.push_front(3); | |
784 | /// assert_eq!(d.pop_front(), Some(3)); | |
785 | /// assert_eq!(d.pop_front(), Some(1)); | |
786 | /// assert_eq!(d.pop_front(), None); | |
85aaf69f | 787 | /// ``` |
85aaf69f | 788 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 789 | pub fn pop_front(&mut self) -> Option<T> { |
5bcae85e | 790 | self.pop_front_node().map(Node::into_element) |
1a4d82fc JJ |
791 | } |
792 | ||
0731742a XL |
793 | /// Appends an element to the back of a list. |
794 | /// | |
3dfed10e | 795 | /// This operation should compute in *O*(1) time. |
1a4d82fc JJ |
796 | /// |
797 | /// # Examples | |
798 | /// | |
85aaf69f SL |
799 | /// ``` |
800 | /// use std::collections::LinkedList; | |
1a4d82fc | 801 | /// |
85aaf69f SL |
802 | /// let mut d = LinkedList::new(); |
803 | /// d.push_back(1); | |
1a4d82fc JJ |
804 | /// d.push_back(3); |
805 | /// assert_eq!(3, *d.back().unwrap()); | |
806 | /// ``` | |
85aaf69f | 807 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 808 | pub fn push_back(&mut self, elt: T) { |
5bcae85e | 809 | self.push_back_node(box Node::new(elt)); |
1a4d82fc JJ |
810 | } |
811 | ||
812 | /// Removes the last element from a list and returns it, or `None` if | |
813 | /// it is empty. | |
814 | /// | |
3dfed10e | 815 | /// This operation should compute in *O*(1) time. |
0731742a | 816 | /// |
1a4d82fc JJ |
817 | /// # Examples |
818 | /// | |
85aaf69f SL |
819 | /// ``` |
820 | /// use std::collections::LinkedList; | |
1a4d82fc | 821 | /// |
85aaf69f | 822 | /// let mut d = LinkedList::new(); |
1a4d82fc | 823 | /// assert_eq!(d.pop_back(), None); |
85aaf69f | 824 | /// d.push_back(1); |
1a4d82fc JJ |
825 | /// d.push_back(3); |
826 | /// assert_eq!(d.pop_back(), Some(3)); | |
827 | /// ``` | |
85aaf69f | 828 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 829 | pub fn pop_back(&mut self) -> Option<T> { |
5bcae85e | 830 | self.pop_back_node().map(Node::into_element) |
1a4d82fc | 831 | } |
85aaf69f SL |
832 | |
833 | /// Splits the list into two at the given index. Returns everything after the given index, | |
834 | /// including the index. | |
835 | /// | |
3dfed10e | 836 | /// This operation should compute in *O*(*n*) time. |
cc61c64b | 837 | /// |
85aaf69f SL |
838 | /// # Panics |
839 | /// | |
840 | /// Panics if `at > len`. | |
841 | /// | |
85aaf69f SL |
842 | /// # Examples |
843 | /// | |
844 | /// ``` | |
845 | /// use std::collections::LinkedList; | |
846 | /// | |
847 | /// let mut d = LinkedList::new(); | |
848 | /// | |
849 | /// d.push_front(1); | |
850 | /// d.push_front(2); | |
851 | /// d.push_front(3); | |
852 | /// | |
74b04a01 | 853 | /// let mut split = d.split_off(2); |
85aaf69f | 854 | /// |
74b04a01 XL |
855 | /// assert_eq!(split.pop_front(), Some(1)); |
856 | /// assert_eq!(split.pop_front(), None); | |
85aaf69f SL |
857 | /// ``` |
858 | #[stable(feature = "rust1", since = "1.0.0")] | |
859 | pub fn split_off(&mut self, at: usize) -> LinkedList<T> { | |
860 | let len = self.len(); | |
861 | assert!(at <= len, "Cannot split off at a nonexistent index"); | |
862 | if at == 0 { | |
416331ca | 863 | return mem::take(self); |
85aaf69f | 864 | } else if at == len { |
5bcae85e | 865 | return Self::new(); |
85aaf69f SL |
866 | } |
867 | ||
868 | // Below, we iterate towards the `i-1`th node, either from the start or the end, | |
869 | // depending on which would be faster. | |
5bcae85e | 870 | let split_node = if at - 1 <= len - 1 - (at - 1) { |
85aaf69f SL |
871 | let mut iter = self.iter_mut(); |
872 | // instead of skipping using .skip() (which creates a new struct), | |
873 | // we skip manually so we can access the head field without | |
874 | // depending on implementation details of Skip | |
875 | for _ in 0..at - 1 { | |
876 | iter.next(); | |
877 | } | |
878 | iter.head | |
92a42be0 | 879 | } else { |
85aaf69f SL |
880 | // better off starting from the end |
881 | let mut iter = self.iter_mut(); | |
882 | for _ in 0..len - 1 - (at - 1) { | |
883 | iter.next_back(); | |
884 | } | |
885 | iter.tail | |
886 | }; | |
dfeec247 | 887 | unsafe { self.split_off_after_node(split_node, at) } |
85aaf69f | 888 | } |
7453a54e | 889 | |
74b04a01 XL |
890 | /// Removes the element at the given index and returns it. |
891 | /// | |
3dfed10e | 892 | /// This operation should compute in *O*(*n*) time. |
74b04a01 XL |
893 | /// |
894 | /// # Panics | |
895 | /// Panics if at >= len | |
896 | /// | |
897 | /// # Examples | |
898 | /// | |
899 | /// ``` | |
900 | /// #![feature(linked_list_remove)] | |
901 | /// use std::collections::LinkedList; | |
902 | /// | |
903 | /// let mut d = LinkedList::new(); | |
904 | /// | |
905 | /// d.push_front(1); | |
906 | /// d.push_front(2); | |
907 | /// d.push_front(3); | |
908 | /// | |
909 | /// assert_eq!(d.remove(1), 2); | |
910 | /// assert_eq!(d.remove(0), 3); | |
911 | /// assert_eq!(d.remove(0), 1); | |
912 | /// ``` | |
913 | #[unstable(feature = "linked_list_remove", issue = "69210")] | |
914 | pub fn remove(&mut self, at: usize) -> T { | |
915 | let len = self.len(); | |
916 | assert!(at < len, "Cannot remove at an index outside of the list bounds"); | |
917 | ||
918 | // Below, we iterate towards the node at the given index, either from | |
919 | // the start or the end, depending on which would be faster. | |
920 | let offset_from_end = len - at - 1; | |
921 | if at <= offset_from_end { | |
922 | let mut cursor = self.cursor_front_mut(); | |
923 | for _ in 0..at { | |
924 | cursor.move_next(); | |
925 | } | |
926 | cursor.remove_current().unwrap() | |
927 | } else { | |
928 | let mut cursor = self.cursor_back_mut(); | |
929 | for _ in 0..offset_from_end { | |
930 | cursor.move_prev(); | |
931 | } | |
932 | cursor.remove_current().unwrap() | |
933 | } | |
934 | } | |
935 | ||
ff7c6d11 XL |
936 | /// Creates an iterator which uses a closure to determine if an element should be removed. |
937 | /// | |
938 | /// If the closure returns true, then the element is removed and yielded. | |
0531ce1d XL |
939 | /// If the closure returns false, the element will remain in the list and will not be yielded |
940 | /// by the iterator. | |
ff7c6d11 XL |
941 | /// |
942 | /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of | |
943 | /// whether you choose to keep or remove it. | |
944 | /// | |
945 | /// # Examples | |
946 | /// | |
947 | /// Splitting a list into evens and odds, reusing the original list: | |
948 | /// | |
949 | /// ``` | |
950 | /// #![feature(drain_filter)] | |
951 | /// use std::collections::LinkedList; | |
952 | /// | |
953 | /// let mut numbers: LinkedList<u32> = LinkedList::new(); | |
954 | /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]); | |
955 | /// | |
956 | /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>(); | |
957 | /// let odds = numbers; | |
958 | /// | |
959 | /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]); | |
960 | /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]); | |
961 | /// ``` | |
962 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 963 | pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F> |
dfeec247 XL |
964 | where |
965 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 XL |
966 | { |
967 | // avoid borrow issues. | |
968 | let it = self.head; | |
969 | let old_len = self.len; | |
970 | ||
74b04a01 | 971 | DrainFilter { list: self, it, pred: filter, idx: 0, old_len } |
ff7c6d11 | 972 | } |
1a4d82fc JJ |
973 | } |
974 | ||
85aaf69f | 975 | #[stable(feature = "rust1", since = "1.0.0")] |
32a655c1 | 976 | unsafe impl<#[may_dangle] T> Drop for LinkedList<T> { |
1a4d82fc | 977 | fn drop(&mut self) { |
60c5eb7d XL |
978 | struct DropGuard<'a, T>(&'a mut LinkedList<T>); |
979 | ||
980 | impl<'a, T> Drop for DropGuard<'a, T> { | |
981 | fn drop(&mut self) { | |
982 | // Continue the same loop we do below. This only runs when a destructor has | |
983 | // panicked. If another one panics this will abort. | |
f9f354fc | 984 | while self.0.pop_front_node().is_some() {} |
60c5eb7d XL |
985 | } |
986 | } | |
987 | ||
988 | while let Some(node) = self.pop_front_node() { | |
989 | let guard = DropGuard(self); | |
990 | drop(node); | |
991 | mem::forget(guard); | |
992 | } | |
1a4d82fc JJ |
993 | } |
994 | } | |
995 | ||
85aaf69f | 996 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
997 | impl<'a, T> Iterator for Iter<'a, T> { |
998 | type Item = &'a T; | |
1a4d82fc JJ |
999 | |
1000 | #[inline] | |
5bcae85e SL |
1001 | fn next(&mut self) -> Option<&'a T> { |
1002 | if self.len == 0 { | |
1003 | None | |
1004 | } else { | |
1005 | self.head.map(|node| unsafe { | |
7cac9316 XL |
1006 | // Need an unbound lifetime to get 'a |
1007 | let node = &*node.as_ptr(); | |
5bcae85e SL |
1008 | self.len -= 1; |
1009 | self.head = node.next; | |
1010 | &node.element | |
1011 | }) | |
1a4d82fc | 1012 | } |
1a4d82fc JJ |
1013 | } |
1014 | ||
1015 | #[inline] | |
85aaf69f | 1016 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 1017 | (self.len, Some(self.len)) |
1a4d82fc | 1018 | } |
416331ca XL |
1019 | |
1020 | #[inline] | |
1021 | fn last(mut self) -> Option<&'a T> { | |
1022 | self.next_back() | |
1023 | } | |
1a4d82fc JJ |
1024 | } |
1025 | ||
85aaf69f | 1026 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1027 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
1a4d82fc | 1028 | #[inline] |
5bcae85e SL |
1029 | fn next_back(&mut self) -> Option<&'a T> { |
1030 | if self.len == 0 { | |
1031 | None | |
1032 | } else { | |
1033 | self.tail.map(|node| unsafe { | |
7cac9316 XL |
1034 | // Need an unbound lifetime to get 'a |
1035 | let node = &*node.as_ptr(); | |
5bcae85e SL |
1036 | self.len -= 1; |
1037 | self.tail = node.prev; | |
1038 | &node.element | |
62682a34 SL |
1039 | }) |
1040 | } | |
1a4d82fc JJ |
1041 | } |
1042 | } | |
1043 | ||
85aaf69f | 1044 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1045 | impl<T> ExactSizeIterator for Iter<'_, T> {} |
1a4d82fc | 1046 | |
0531ce1d | 1047 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1048 | impl<T> FusedIterator for Iter<'_, T> {} |
9e0c209e | 1049 | |
85aaf69f | 1050 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1051 | impl<'a, T> Iterator for IterMut<'a, T> { |
1052 | type Item = &'a mut T; | |
1053 | ||
1a4d82fc | 1054 | #[inline] |
5bcae85e SL |
1055 | fn next(&mut self) -> Option<&'a mut T> { |
1056 | if self.len == 0 { | |
1057 | None | |
1058 | } else { | |
1059 | self.head.map(|node| unsafe { | |
7cac9316 XL |
1060 | // Need an unbound lifetime to get 'a |
1061 | let node = &mut *node.as_ptr(); | |
5bcae85e SL |
1062 | self.len -= 1; |
1063 | self.head = node.next; | |
1064 | &mut node.element | |
62682a34 SL |
1065 | }) |
1066 | } | |
1a4d82fc JJ |
1067 | } |
1068 | ||
1069 | #[inline] | |
85aaf69f | 1070 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 1071 | (self.len, Some(self.len)) |
1a4d82fc | 1072 | } |
416331ca XL |
1073 | |
1074 | #[inline] | |
1075 | fn last(mut self) -> Option<&'a mut T> { | |
1076 | self.next_back() | |
1077 | } | |
1a4d82fc JJ |
1078 | } |
1079 | ||
85aaf69f | 1080 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1081 | impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { |
1a4d82fc | 1082 | #[inline] |
5bcae85e SL |
1083 | fn next_back(&mut self) -> Option<&'a mut T> { |
1084 | if self.len == 0 { | |
1085 | None | |
1086 | } else { | |
1087 | self.tail.map(|node| unsafe { | |
7cac9316 XL |
1088 | // Need an unbound lifetime to get 'a |
1089 | let node = &mut *node.as_ptr(); | |
5bcae85e SL |
1090 | self.len -= 1; |
1091 | self.tail = node.prev; | |
1092 | &mut node.element | |
62682a34 SL |
1093 | }) |
1094 | } | |
1a4d82fc JJ |
1095 | } |
1096 | } | |
1097 | ||
85aaf69f | 1098 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1099 | impl<T> ExactSizeIterator for IterMut<'_, T> {} |
1a4d82fc | 1100 | |
0531ce1d | 1101 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1102 | impl<T> FusedIterator for IterMut<'_, T> {} |
9e0c209e | 1103 | |
dfeec247 XL |
1104 | /// A cursor over a `LinkedList`. |
1105 | /// | |
1106 | /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth. | |
1107 | /// | |
1108 | /// Cursors always rest between two elements in the list, and index in a logically circular way. | |
1109 | /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and | |
1110 | /// tail of the list. | |
1111 | /// | |
1112 | /// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty. | |
1113 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1114 | pub struct Cursor<'a, T: 'a> { | |
1115 | index: usize, | |
1116 | current: Option<NonNull<Node<T>>>, | |
1117 | list: &'a LinkedList<T>, | |
1118 | } | |
1119 | ||
ba9703b0 XL |
1120 | #[unstable(feature = "linked_list_cursors", issue = "58533")] |
1121 | impl<T> Clone for Cursor<'_, T> { | |
1122 | fn clone(&self) -> Self { | |
1123 | let Cursor { index, current, list } = *self; | |
1124 | Cursor { index, current, list } | |
1125 | } | |
1126 | } | |
1127 | ||
dfeec247 XL |
1128 | #[unstable(feature = "linked_list_cursors", issue = "58533")] |
1129 | impl<T: fmt::Debug> fmt::Debug for Cursor<'_, T> { | |
1130 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1131 | f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish() | |
1132 | } | |
1133 | } | |
1134 | ||
1135 | /// A cursor over a `LinkedList` with editing operations. | |
1136 | /// | |
1137 | /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can | |
1138 | /// safely mutate the list during iteration. This is because the lifetime of its yielded | |
1139 | /// references is tied to its own lifetime, instead of just the underlying list. This means | |
1140 | /// cursors cannot yield multiple elements at once. | |
1141 | /// | |
1142 | /// Cursors always rest between two elements in the list, and index in a logically circular way. | |
1143 | /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and | |
1144 | /// tail of the list. | |
1145 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1146 | pub struct CursorMut<'a, T: 'a> { | |
1147 | index: usize, | |
1148 | current: Option<NonNull<Node<T>>>, | |
1149 | list: &'a mut LinkedList<T>, | |
1150 | } | |
1151 | ||
1152 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1153 | impl<T: fmt::Debug> fmt::Debug for CursorMut<'_, T> { | |
1154 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1155 | f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish() | |
1156 | } | |
1157 | } | |
1158 | ||
1159 | impl<'a, T> Cursor<'a, T> { | |
1160 | /// Returns the cursor position index within the `LinkedList`. | |
1161 | /// | |
1162 | /// This returns `None` if the cursor is currently pointing to the | |
1163 | /// "ghost" non-element. | |
1164 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1165 | pub fn index(&self) -> Option<usize> { | |
1166 | let _ = self.current?; | |
1167 | Some(self.index) | |
1168 | } | |
1169 | ||
1170 | /// Moves the cursor to the next element of the `LinkedList`. | |
1171 | /// | |
1172 | /// If the cursor is pointing to the "ghost" non-element then this will move it to | |
1173 | /// the first element of the `LinkedList`. If it is pointing to the last | |
1174 | /// element of the `LinkedList` then this will move it to the "ghost" non-element. | |
1175 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1176 | pub fn move_next(&mut self) { | |
1177 | match self.current.take() { | |
1178 | // We had no current element; the cursor was sitting at the start position | |
1179 | // Next element should be the head of the list | |
1180 | None => { | |
1181 | self.current = self.list.head; | |
1182 | self.index = 0; | |
1183 | } | |
1184 | // We had a previous element, so let's go to its next | |
1185 | Some(current) => unsafe { | |
1186 | self.current = current.as_ref().next; | |
1187 | self.index += 1; | |
1188 | }, | |
1189 | } | |
1190 | } | |
1191 | ||
1192 | /// Moves the cursor to the previous element of the `LinkedList`. | |
1193 | /// | |
1194 | /// If the cursor is pointing to the "ghost" non-element then this will move it to | |
1195 | /// the last element of the `LinkedList`. If it is pointing to the first | |
1196 | /// element of the `LinkedList` then this will move it to the "ghost" non-element. | |
1197 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1198 | pub fn move_prev(&mut self) { | |
1199 | match self.current.take() { | |
1200 | // No current. We're at the start of the list. Yield None and jump to the end. | |
1201 | None => { | |
1202 | self.current = self.list.tail; | |
1203 | self.index = self.list.len().checked_sub(1).unwrap_or(0); | |
1204 | } | |
1205 | // Have a prev. Yield it and go to the previous element. | |
1206 | Some(current) => unsafe { | |
1207 | self.current = current.as_ref().prev; | |
1208 | self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len()); | |
1209 | }, | |
1210 | } | |
1211 | } | |
1212 | ||
1213 | /// Returns a reference to the element that the cursor is currently | |
1214 | /// pointing to. | |
1215 | /// | |
1216 | /// This returns `None` if the cursor is currently pointing to the | |
1217 | /// "ghost" non-element. | |
1218 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1219 | pub fn current(&self) -> Option<&'a T> { | |
1220 | unsafe { self.current.map(|current| &(*current.as_ptr()).element) } | |
1221 | } | |
1222 | ||
1223 | /// Returns a reference to the next element. | |
1224 | /// | |
1225 | /// If the cursor is pointing to the "ghost" non-element then this returns | |
1226 | /// the first element of the `LinkedList`. If it is pointing to the last | |
1227 | /// element of the `LinkedList` then this returns `None`. | |
1228 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1229 | pub fn peek_next(&self) -> Option<&'a T> { | |
1230 | unsafe { | |
1231 | let next = match self.current { | |
1232 | None => self.list.head, | |
1233 | Some(current) => current.as_ref().next, | |
1234 | }; | |
1235 | next.map(|next| &(*next.as_ptr()).element) | |
1236 | } | |
1237 | } | |
1238 | ||
1239 | /// Returns a reference to the previous element. | |
1240 | /// | |
1241 | /// If the cursor is pointing to the "ghost" non-element then this returns | |
1242 | /// the last element of the `LinkedList`. If it is pointing to the first | |
1243 | /// element of the `LinkedList` then this returns `None`. | |
1244 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1245 | pub fn peek_prev(&self) -> Option<&'a T> { | |
1246 | unsafe { | |
1247 | let prev = match self.current { | |
1248 | None => self.list.tail, | |
1249 | Some(current) => current.as_ref().prev, | |
1250 | }; | |
1251 | prev.map(|prev| &(*prev.as_ptr()).element) | |
1252 | } | |
1253 | } | |
1254 | } | |
1255 | ||
1256 | impl<'a, T> CursorMut<'a, T> { | |
1257 | /// Returns the cursor position index within the `LinkedList`. | |
1258 | /// | |
1259 | /// This returns `None` if the cursor is currently pointing to the | |
1260 | /// "ghost" non-element. | |
1261 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1262 | pub fn index(&self) -> Option<usize> { | |
1263 | let _ = self.current?; | |
1264 | Some(self.index) | |
1265 | } | |
1266 | ||
1267 | /// Moves the cursor to the next element of the `LinkedList`. | |
1268 | /// | |
1269 | /// If the cursor is pointing to the "ghost" non-element then this will move it to | |
1270 | /// the first element of the `LinkedList`. If it is pointing to the last | |
1271 | /// element of the `LinkedList` then this will move it to the "ghost" non-element. | |
1272 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1273 | pub fn move_next(&mut self) { | |
1274 | match self.current.take() { | |
1275 | // We had no current element; the cursor was sitting at the start position | |
1276 | // Next element should be the head of the list | |
1277 | None => { | |
1278 | self.current = self.list.head; | |
1279 | self.index = 0; | |
1280 | } | |
1281 | // We had a previous element, so let's go to its next | |
1282 | Some(current) => unsafe { | |
1283 | self.current = current.as_ref().next; | |
1284 | self.index += 1; | |
1285 | }, | |
1286 | } | |
1287 | } | |
1288 | ||
1289 | /// Moves the cursor to the previous element of the `LinkedList`. | |
1290 | /// | |
1291 | /// If the cursor is pointing to the "ghost" non-element then this will move it to | |
1292 | /// the last element of the `LinkedList`. If it is pointing to the first | |
1293 | /// element of the `LinkedList` then this will move it to the "ghost" non-element. | |
1294 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1295 | pub fn move_prev(&mut self) { | |
1296 | match self.current.take() { | |
1297 | // No current. We're at the start of the list. Yield None and jump to the end. | |
1298 | None => { | |
1299 | self.current = self.list.tail; | |
1300 | self.index = self.list.len().checked_sub(1).unwrap_or(0); | |
1301 | } | |
1302 | // Have a prev. Yield it and go to the previous element. | |
1303 | Some(current) => unsafe { | |
1304 | self.current = current.as_ref().prev; | |
1305 | self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len()); | |
1306 | }, | |
1307 | } | |
1308 | } | |
1309 | ||
1310 | /// Returns a reference to the element that the cursor is currently | |
1311 | /// pointing to. | |
1312 | /// | |
1313 | /// This returns `None` if the cursor is currently pointing to the | |
1314 | /// "ghost" non-element. | |
1315 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1316 | pub fn current(&mut self) -> Option<&mut T> { | |
1317 | unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) } | |
1318 | } | |
1319 | ||
1320 | /// Returns a reference to the next element. | |
1321 | /// | |
1322 | /// If the cursor is pointing to the "ghost" non-element then this returns | |
1323 | /// the first element of the `LinkedList`. If it is pointing to the last | |
1324 | /// element of the `LinkedList` then this returns `None`. | |
1325 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1326 | pub fn peek_next(&mut self) -> Option<&mut T> { | |
1327 | unsafe { | |
1328 | let next = match self.current { | |
1329 | None => self.list.head, | |
1330 | Some(current) => current.as_ref().next, | |
1331 | }; | |
1332 | next.map(|next| &mut (*next.as_ptr()).element) | |
1333 | } | |
1334 | } | |
1335 | ||
1336 | /// Returns a reference to the previous element. | |
1337 | /// | |
1338 | /// If the cursor is pointing to the "ghost" non-element then this returns | |
1339 | /// the last element of the `LinkedList`. If it is pointing to the first | |
1340 | /// element of the `LinkedList` then this returns `None`. | |
1341 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1342 | pub fn peek_prev(&mut self) -> Option<&mut T> { | |
1343 | unsafe { | |
1344 | let prev = match self.current { | |
1345 | None => self.list.tail, | |
1346 | Some(current) => current.as_ref().prev, | |
1347 | }; | |
1348 | prev.map(|prev| &mut (*prev.as_ptr()).element) | |
1349 | } | |
1350 | } | |
1351 | ||
1352 | /// Returns a read-only cursor pointing to the current element. | |
1353 | /// | |
1354 | /// The lifetime of the returned `Cursor` is bound to that of the | |
1355 | /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the | |
1356 | /// `CursorMut` is frozen for the lifetime of the `Cursor`. | |
1357 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
ba9703b0 | 1358 | pub fn as_cursor(&self) -> Cursor<'_, T> { |
dfeec247 XL |
1359 | Cursor { list: self.list, current: self.current, index: self.index } |
1360 | } | |
1361 | } | |
1362 | ||
1363 | // Now the list editing operations | |
1364 | ||
1365 | impl<'a, T> CursorMut<'a, T> { | |
1366 | /// Inserts a new element into the `LinkedList` after the current one. | |
1367 | /// | |
1368 | /// If the cursor is pointing at the "ghost" non-element then the new element is | |
1369 | /// inserted at the front of the `LinkedList`. | |
1370 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1371 | pub fn insert_after(&mut self, item: T) { | |
1372 | unsafe { | |
f9f354fc | 1373 | let spliced_node = Box::leak(Box::new(Node::new(item))).into(); |
dfeec247 XL |
1374 | let node_next = match self.current { |
1375 | None => self.list.head, | |
1376 | Some(node) => node.as_ref().next, | |
1377 | }; | |
1378 | self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1); | |
1379 | if self.current.is_none() { | |
1380 | // The "ghost" non-element's index has changed. | |
1381 | self.index = self.list.len; | |
1382 | } | |
1383 | } | |
1384 | } | |
1385 | ||
1386 | /// Inserts a new element into the `LinkedList` before the current one. | |
1387 | /// | |
1388 | /// If the cursor is pointing at the "ghost" non-element then the new element is | |
1389 | /// inserted at the end of the `LinkedList`. | |
1390 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1391 | pub fn insert_before(&mut self, item: T) { | |
1392 | unsafe { | |
f9f354fc | 1393 | let spliced_node = Box::leak(Box::new(Node::new(item))).into(); |
dfeec247 XL |
1394 | let node_prev = match self.current { |
1395 | None => self.list.tail, | |
1396 | Some(node) => node.as_ref().prev, | |
1397 | }; | |
1398 | self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1); | |
1399 | self.index += 1; | |
1400 | } | |
1401 | } | |
1402 | ||
1403 | /// Removes the current element from the `LinkedList`. | |
1404 | /// | |
1405 | /// The element that was removed is returned, and the cursor is | |
1406 | /// moved to point to the next element in the `LinkedList`. | |
1407 | /// | |
1408 | /// If the cursor is currently pointing to the "ghost" non-element then no element | |
1409 | /// is removed and `None` is returned. | |
1410 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1411 | pub fn remove_current(&mut self) -> Option<T> { | |
1412 | let unlinked_node = self.current?; | |
1413 | unsafe { | |
1414 | self.current = unlinked_node.as_ref().next; | |
1415 | self.list.unlink_node(unlinked_node); | |
1416 | let unlinked_node = Box::from_raw(unlinked_node.as_ptr()); | |
1417 | Some(unlinked_node.element) | |
1418 | } | |
1419 | } | |
1420 | ||
f9f354fc XL |
1421 | /// Removes the current element from the `LinkedList` without deallocating the list node. |
1422 | /// | |
1423 | /// The node that was removed is returned as a new `LinkedList` containing only this node. | |
1424 | /// The cursor is moved to point to the next element in the current `LinkedList`. | |
1425 | /// | |
1426 | /// If the cursor is currently pointing to the "ghost" non-element then no element | |
1427 | /// is removed and `None` is returned. | |
1428 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1429 | pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T>> { | |
1430 | let mut unlinked_node = self.current?; | |
1431 | unsafe { | |
1432 | self.current = unlinked_node.as_ref().next; | |
1433 | self.list.unlink_node(unlinked_node); | |
1434 | ||
1435 | unlinked_node.as_mut().prev = None; | |
1436 | unlinked_node.as_mut().next = None; | |
1437 | Some(LinkedList { | |
1438 | head: Some(unlinked_node), | |
1439 | tail: Some(unlinked_node), | |
1440 | len: 1, | |
1441 | marker: PhantomData, | |
1442 | }) | |
1443 | } | |
1444 | } | |
1445 | ||
dfeec247 XL |
1446 | /// Inserts the elements from the given `LinkedList` after the current one. |
1447 | /// | |
1448 | /// If the cursor is pointing at the "ghost" non-element then the new elements are | |
1449 | /// inserted at the start of the `LinkedList`. | |
1450 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1451 | pub fn splice_after(&mut self, list: LinkedList<T>) { | |
1452 | unsafe { | |
1453 | let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() { | |
1454 | Some(parts) => parts, | |
1455 | _ => return, | |
1456 | }; | |
1457 | let node_next = match self.current { | |
1458 | None => self.list.head, | |
1459 | Some(node) => node.as_ref().next, | |
1460 | }; | |
1461 | self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len); | |
1462 | if self.current.is_none() { | |
1463 | // The "ghost" non-element's index has changed. | |
1464 | self.index = self.list.len; | |
7cac9316 | 1465 | } |
62682a34 | 1466 | } |
1a4d82fc | 1467 | } |
dfeec247 XL |
1468 | |
1469 | /// Inserts the elements from the given `LinkedList` before the current one. | |
1470 | /// | |
1471 | /// If the cursor is pointing at the "ghost" non-element then the new elements are | |
1472 | /// inserted at the end of the `LinkedList`. | |
1473 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1474 | pub fn splice_before(&mut self, list: LinkedList<T>) { | |
1475 | unsafe { | |
1476 | let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() { | |
1477 | Some(parts) => parts, | |
1478 | _ => return, | |
1479 | }; | |
1480 | let node_prev = match self.current { | |
1481 | None => self.list.tail, | |
1482 | Some(node) => node.as_ref().prev, | |
1483 | }; | |
1484 | self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len); | |
1485 | self.index += splice_len; | |
1486 | } | |
1487 | } | |
1488 | ||
1489 | /// Splits the list into two after the current element. This will return a | |
1490 | /// new list consisting of everything after the cursor, with the original | |
1491 | /// list retaining everything before. | |
1492 | /// | |
1493 | /// If the cursor is pointing at the "ghost" non-element then the entire contents | |
1494 | /// of the `LinkedList` are moved. | |
1495 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1496 | pub fn split_after(&mut self) -> LinkedList<T> { | |
1497 | let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 }; | |
1498 | if self.index == self.list.len { | |
1499 | // The "ghost" non-element's index has changed to 0. | |
1500 | self.index = 0; | |
1501 | } | |
1502 | unsafe { self.list.split_off_after_node(self.current, split_off_idx) } | |
1503 | } | |
1504 | ||
1505 | /// Splits the list into two before the current element. This will return a | |
1506 | /// new list consisting of everything before the cursor, with the original | |
1507 | /// list retaining everything after. | |
1508 | /// | |
1509 | /// If the cursor is pointing at the "ghost" non-element then the entire contents | |
1510 | /// of the `LinkedList` are moved. | |
1511 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1512 | pub fn split_before(&mut self) -> LinkedList<T> { | |
1513 | let split_off_idx = self.index; | |
1514 | self.index = 0; | |
1515 | unsafe { self.list.split_off_before_node(self.current, split_off_idx) } | |
1516 | } | |
1a4d82fc JJ |
1517 | } |
1518 | ||
ff7c6d11 XL |
1519 | /// An iterator produced by calling `drain_filter` on LinkedList. |
1520 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
1521 | pub struct DrainFilter<'a, T: 'a, F: 'a> | |
dfeec247 XL |
1522 | where |
1523 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 XL |
1524 | { |
1525 | list: &'a mut LinkedList<T>, | |
2c00a5a8 | 1526 | it: Option<NonNull<Node<T>>>, |
ff7c6d11 XL |
1527 | pred: F, |
1528 | idx: usize, | |
1529 | old_len: usize, | |
1530 | } | |
1531 | ||
1532 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1533 | impl<T, F> Iterator for DrainFilter<'_, T, F> |
dfeec247 XL |
1534 | where |
1535 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 XL |
1536 | { |
1537 | type Item = T; | |
1538 | ||
1539 | fn next(&mut self) -> Option<T> { | |
1540 | while let Some(mut node) = self.it { | |
1541 | unsafe { | |
1542 | self.it = node.as_ref().next; | |
1543 | self.idx += 1; | |
1544 | ||
1545 | if (self.pred)(&mut node.as_mut().element) { | |
48663c56 | 1546 | // `unlink_node` is okay with aliasing `element` references. |
ff7c6d11 XL |
1547 | self.list.unlink_node(node); |
1548 | return Some(Box::from_raw(node.as_ptr()).element); | |
1549 | } | |
1550 | } | |
1551 | } | |
1552 | ||
1553 | None | |
1554 | } | |
1555 | ||
1556 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1557 | (0, Some(self.old_len - self.idx)) | |
1558 | } | |
1559 | } | |
1560 | ||
1561 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1562 | impl<T, F> Drop for DrainFilter<'_, T, F> |
dfeec247 XL |
1563 | where |
1564 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 XL |
1565 | { |
1566 | fn drop(&mut self) { | |
74b04a01 XL |
1567 | struct DropGuard<'r, 'a, T, F>(&'r mut DrainFilter<'a, T, F>) |
1568 | where | |
1569 | F: FnMut(&mut T) -> bool; | |
1570 | ||
1571 | impl<'r, 'a, T, F> Drop for DropGuard<'r, 'a, T, F> | |
1572 | where | |
1573 | F: FnMut(&mut T) -> bool, | |
1574 | { | |
1575 | fn drop(&mut self) { | |
1576 | self.0.for_each(drop); | |
1577 | } | |
1578 | } | |
1579 | ||
1580 | while let Some(item) = self.next() { | |
1581 | let guard = DropGuard(self); | |
1582 | drop(item); | |
1583 | mem::forget(guard); | |
1584 | } | |
ff7c6d11 XL |
1585 | } |
1586 | } | |
1587 | ||
1588 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1589 | impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F> |
dfeec247 XL |
1590 | where |
1591 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 | 1592 | { |
9fa01778 | 1593 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
dfeec247 | 1594 | f.debug_tuple("DrainFilter").field(&self.list).finish() |
ff7c6d11 XL |
1595 | } |
1596 | } | |
1597 | ||
85aaf69f | 1598 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1599 | impl<T> Iterator for IntoIter<T> { |
1600 | type Item = T; | |
1a4d82fc JJ |
1601 | |
1602 | #[inline] | |
5bcae85e | 1603 | fn next(&mut self) -> Option<T> { |
92a42be0 SL |
1604 | self.list.pop_front() |
1605 | } | |
1a4d82fc JJ |
1606 | |
1607 | #[inline] | |
85aaf69f | 1608 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 1609 | (self.list.len, Some(self.list.len)) |
1a4d82fc JJ |
1610 | } |
1611 | } | |
1612 | ||
85aaf69f | 1613 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1614 | impl<T> DoubleEndedIterator for IntoIter<T> { |
1a4d82fc | 1615 | #[inline] |
5bcae85e | 1616 | fn next_back(&mut self) -> Option<T> { |
92a42be0 SL |
1617 | self.list.pop_back() |
1618 | } | |
1a4d82fc JJ |
1619 | } |
1620 | ||
92a42be0 | 1621 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1622 | impl<T> ExactSizeIterator for IntoIter<T> {} |
c34b1796 | 1623 | |
0531ce1d | 1624 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e SL |
1625 | impl<T> FusedIterator for IntoIter<T> {} |
1626 | ||
85aaf69f | 1627 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1628 | impl<T> FromIterator<T> for LinkedList<T> { |
1629 | fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { | |
1630 | let mut list = Self::new(); | |
1631 | list.extend(iter); | |
1632 | list | |
1a4d82fc JJ |
1633 | } |
1634 | } | |
1635 | ||
85aaf69f SL |
1636 | #[stable(feature = "rust1", since = "1.0.0")] |
1637 | impl<T> IntoIterator for LinkedList<T> { | |
1638 | type Item = T; | |
1639 | type IntoIter = IntoIter<T>; | |
1640 | ||
9346a6ac AL |
1641 | /// Consumes the list into an iterator yielding elements by value. |
1642 | #[inline] | |
85aaf69f | 1643 | fn into_iter(self) -> IntoIter<T> { |
92a42be0 | 1644 | IntoIter { list: self } |
85aaf69f SL |
1645 | } |
1646 | } | |
1647 | ||
1648 | #[stable(feature = "rust1", since = "1.0.0")] | |
1649 | impl<'a, T> IntoIterator for &'a LinkedList<T> { | |
1650 | type Item = &'a T; | |
1651 | type IntoIter = Iter<'a, T>; | |
1652 | ||
1653 | fn into_iter(self) -> Iter<'a, T> { | |
1654 | self.iter() | |
1655 | } | |
1656 | } | |
1657 | ||
92a42be0 | 1658 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
1659 | impl<'a, T> IntoIterator for &'a mut LinkedList<T> { |
1660 | type Item = &'a mut T; | |
1661 | type IntoIter = IterMut<'a, T>; | |
1662 | ||
5bcae85e | 1663 | fn into_iter(self) -> IterMut<'a, T> { |
85aaf69f | 1664 | self.iter_mut() |
1a4d82fc JJ |
1665 | } |
1666 | } | |
1667 | ||
85aaf69f | 1668 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1669 | impl<T> Extend<T> for LinkedList<T> { |
1670 | fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { | |
1671 | <Self as SpecExtend<I>>::spec_extend(self, iter); | |
a7813a04 | 1672 | } |
f9f354fc XL |
1673 | |
1674 | #[inline] | |
1675 | fn extend_one(&mut self, elem: T) { | |
1676 | self.push_back(elem); | |
1677 | } | |
a7813a04 XL |
1678 | } |
1679 | ||
1680 | impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> { | |
1681 | default fn spec_extend(&mut self, iter: I) { | |
532ac7d7 | 1682 | iter.into_iter().for_each(move |elt| self.push_back(elt)); |
85aaf69f SL |
1683 | } |
1684 | } | |
1685 | ||
a7813a04 XL |
1686 | impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> { |
1687 | fn spec_extend(&mut self, ref mut other: LinkedList<T>) { | |
1688 | self.append(other); | |
1689 | } | |
1690 | } | |
1691 | ||
62682a34 SL |
1692 | #[stable(feature = "extend_ref", since = "1.2.0")] |
1693 | impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> { | |
92a42be0 | 1694 | fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { |
62682a34 SL |
1695 | self.extend(iter.into_iter().cloned()); |
1696 | } | |
f9f354fc XL |
1697 | |
1698 | #[inline] | |
1699 | fn extend_one(&mut self, &elem: &'a T) { | |
1700 | self.push_back(elem); | |
1701 | } | |
62682a34 SL |
1702 | } |
1703 | ||
85aaf69f | 1704 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1705 | impl<T: PartialEq> PartialEq for LinkedList<T> { |
1706 | fn eq(&self, other: &Self) -> bool { | |
1707 | self.len() == other.len() && self.iter().eq(other) | |
1a4d82fc JJ |
1708 | } |
1709 | ||
5bcae85e SL |
1710 | fn ne(&self, other: &Self) -> bool { |
1711 | self.len() != other.len() || self.iter().ne(other) | |
1a4d82fc JJ |
1712 | } |
1713 | } | |
1714 | ||
85aaf69f | 1715 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1716 | impl<T: Eq> Eq for LinkedList<T> {} |
1a4d82fc | 1717 | |
85aaf69f | 1718 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1719 | impl<T: PartialOrd> PartialOrd for LinkedList<T> { |
1720 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { | |
1721 | self.iter().partial_cmp(other) | |
1a4d82fc JJ |
1722 | } |
1723 | } | |
1724 | ||
85aaf69f | 1725 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1726 | impl<T: Ord> Ord for LinkedList<T> { |
1a4d82fc | 1727 | #[inline] |
5bcae85e SL |
1728 | fn cmp(&self, other: &Self) -> Ordering { |
1729 | self.iter().cmp(other) | |
1a4d82fc JJ |
1730 | } |
1731 | } | |
1732 | ||
85aaf69f | 1733 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1734 | impl<T: Clone> Clone for LinkedList<T> { |
1735 | fn clone(&self) -> Self { | |
85aaf69f | 1736 | self.iter().cloned().collect() |
1a4d82fc | 1737 | } |
e74abb32 XL |
1738 | |
1739 | fn clone_from(&mut self, other: &Self) { | |
1740 | let mut iter_other = other.iter(); | |
1741 | if self.len() > other.len() { | |
1742 | self.split_off(other.len()); | |
1743 | } | |
1744 | for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) { | |
1745 | elem.clone_from(elem_other); | |
1746 | } | |
1747 | if !iter_other.is_empty() { | |
1748 | self.extend(iter_other.cloned()); | |
1749 | } | |
1750 | } | |
1a4d82fc JJ |
1751 | } |
1752 | ||
85aaf69f | 1753 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1754 | impl<T: fmt::Debug> fmt::Debug for LinkedList<T> { |
9fa01778 | 1755 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
5bcae85e | 1756 | f.debug_list().entries(self).finish() |
1a4d82fc JJ |
1757 | } |
1758 | } | |
1759 | ||
85aaf69f | 1760 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1761 | impl<T: Hash> Hash for LinkedList<T> { |
85aaf69f SL |
1762 | fn hash<H: Hasher>(&self, state: &mut H) { |
1763 | self.len().hash(state); | |
1764 | for elt in self { | |
1a4d82fc JJ |
1765 | elt.hash(state); |
1766 | } | |
1767 | } | |
1768 | } | |
1769 | ||
9cc50fc6 SL |
1770 | // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters. |
1771 | #[allow(dead_code)] | |
1772 | fn assert_covariance() { | |
32a655c1 SL |
1773 | fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> { |
1774 | x | |
1775 | } | |
1776 | fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> { | |
1777 | x | |
1778 | } | |
1779 | fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> { | |
1780 | x | |
1781 | } | |
9cc50fc6 SL |
1782 | } |
1783 | ||
5bcae85e SL |
1784 | #[stable(feature = "rust1", since = "1.0.0")] |
1785 | unsafe impl<T: Send> Send for LinkedList<T> {} | |
1786 | ||
1787 | #[stable(feature = "rust1", since = "1.0.0")] | |
1788 | unsafe impl<T: Sync> Sync for LinkedList<T> {} | |
1789 | ||
1790 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1791 | unsafe impl<T: Sync> Send for Iter<'_, T> {} |
5bcae85e SL |
1792 | |
1793 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1794 | unsafe impl<T: Sync> Sync for Iter<'_, T> {} |
5bcae85e SL |
1795 | |
1796 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1797 | unsafe impl<T: Send> Send for IterMut<'_, T> {} |
5bcae85e SL |
1798 | |
1799 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1800 | unsafe impl<T: Sync> Sync for IterMut<'_, T> {} |
f9f354fc XL |
1801 | |
1802 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1803 | unsafe impl<T: Sync> Send for Cursor<'_, T> {} | |
1804 | ||
1805 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1806 | unsafe impl<T: Sync> Sync for Cursor<'_, T> {} | |
1807 | ||
1808 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1809 | unsafe impl<T: Send> Send for CursorMut<'_, T> {} | |
1810 | ||
1811 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1812 | unsafe impl<T: Sync> Sync for CursorMut<'_, T> {} |