]>
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 | //! |
60c5eb7d | 10 | //! [`Vec`]: ../../vec/struct.Vec.html |
32a655c1 | 11 | //! [`VecDeque`]: ../vec_deque/struct.VecDeque.html |
1a4d82fc | 12 | |
85aaf69f | 13 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 14 | |
1a4d82fc | 15 | use core::cmp::Ordering; |
1a4d82fc | 16 | use core::fmt; |
85aaf69f | 17 | use core::hash::{Hasher, Hash}; |
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 | |
9fa01778 | 23 | use crate::boxed::Box; |
a7813a04 XL |
24 | use super::SpecExtend; |
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 SL |
37 | #[stable(feature = "rust1", since = "1.0.0")] |
38 | pub struct LinkedList<T> { | |
2c00a5a8 XL |
39 | head: Option<NonNull<Node<T>>>, |
40 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e SL |
41 | len: usize, |
42 | marker: PhantomData<Box<Node<T>>>, | |
1a4d82fc JJ |
43 | } |
44 | ||
1a4d82fc | 45 | struct Node<T> { |
2c00a5a8 XL |
46 | next: Option<NonNull<Node<T>>>, |
47 | prev: Option<NonNull<Node<T>>>, | |
5bcae85e | 48 | element: T, |
1a4d82fc JJ |
49 | } |
50 | ||
cc61c64b XL |
51 | /// An iterator over the elements of a `LinkedList`. |
52 | /// | |
53 | /// This `struct` is created by the [`iter`] method on [`LinkedList`]. See its | |
54 | /// documentation for more. | |
55 | /// | |
56 | /// [`iter`]: struct.LinkedList.html#method.iter | |
57 | /// [`LinkedList`]: struct.LinkedList.html | |
85aaf69f | 58 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 59 | pub struct Iter<'a, T: 'a> { |
2c00a5a8 XL |
60 | head: Option<NonNull<Node<T>>>, |
61 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e SL |
62 | len: usize, |
63 | marker: PhantomData<&'a Node<T>>, | |
1a4d82fc JJ |
64 | } |
65 | ||
8bb4bdeb | 66 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
67 | impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { |
68 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
8bb4bdeb | 69 | f.debug_tuple("Iter") |
cc61c64b | 70 | .field(&self.len) |
8bb4bdeb XL |
71 | .finish() |
72 | } | |
73 | } | |
74 | ||
ea8adc8c | 75 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
85aaf69f | 76 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 77 | impl<T> Clone for Iter<'_, T> { |
5bcae85e SL |
78 | fn clone(&self) -> Self { |
79 | Iter { ..*self } | |
1a4d82fc JJ |
80 | } |
81 | } | |
82 | ||
cc61c64b XL |
83 | /// A mutable iterator over the elements of a `LinkedList`. |
84 | /// | |
85 | /// This `struct` is created by the [`iter_mut`] method on [`LinkedList`]. See its | |
86 | /// documentation for more. | |
87 | /// | |
88 | /// [`iter_mut`]: struct.LinkedList.html#method.iter_mut | |
89 | /// [`LinkedList`]: struct.LinkedList.html | |
85aaf69f | 90 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 91 | pub struct IterMut<'a, T: 'a> { |
48663c56 | 92 | // We do *not* exclusively own the entire list here, references to node's `element` |
60c5eb7d | 93 | // have been handed out by the iterator! So be careful when using this; the methods |
48663c56 | 94 | // called must be aware that there can be aliasing pointers to `element`. |
85aaf69f | 95 | list: &'a mut LinkedList<T>, |
2c00a5a8 XL |
96 | head: Option<NonNull<Node<T>>>, |
97 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e | 98 | len: usize, |
1a4d82fc JJ |
99 | } |
100 | ||
8bb4bdeb | 101 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
102 | impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { |
103 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
8bb4bdeb | 104 | f.debug_tuple("IterMut") |
cc61c64b XL |
105 | .field(&self.list) |
106 | .field(&self.len) | |
8bb4bdeb XL |
107 | .finish() |
108 | } | |
109 | } | |
110 | ||
cc61c64b XL |
111 | /// An owning iterator over the elements of a `LinkedList`. |
112 | /// | |
113 | /// This `struct` is created by the [`into_iter`] method on [`LinkedList`][`LinkedList`] | |
114 | /// (provided by the `IntoIterator` trait). See its documentation for more. | |
115 | /// | |
116 | /// [`into_iter`]: struct.LinkedList.html#method.into_iter | |
117 | /// [`LinkedList`]: struct.LinkedList.html | |
1a4d82fc | 118 | #[derive(Clone)] |
85aaf69f | 119 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 120 | pub struct IntoIter<T> { |
92a42be0 | 121 | list: LinkedList<T>, |
1a4d82fc JJ |
122 | } |
123 | ||
8bb4bdeb XL |
124 | #[stable(feature = "collection_debug", since = "1.17.0")] |
125 | impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { | |
9fa01778 | 126 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
8bb4bdeb | 127 | f.debug_tuple("IntoIter") |
cc61c64b | 128 | .field(&self.list) |
8bb4bdeb XL |
129 | .finish() |
130 | } | |
131 | } | |
132 | ||
1a4d82fc | 133 | impl<T> Node<T> { |
5bcae85e | 134 | fn new(element: T) -> Self { |
92a42be0 | 135 | Node { |
92a42be0 | 136 | next: None, |
5bcae85e | 137 | prev: None, |
3b2f2976 | 138 | element, |
92a42be0 | 139 | } |
1a4d82fc | 140 | } |
62682a34 | 141 | |
5bcae85e SL |
142 | fn into_element(self: Box<Self>) -> T { |
143 | self.element | |
62682a34 | 144 | } |
1a4d82fc JJ |
145 | } |
146 | ||
1a4d82fc | 147 | // private methods |
85aaf69f | 148 | impl<T> LinkedList<T> { |
5bcae85e | 149 | /// Adds the given node to the front of the list. |
1a4d82fc | 150 | #[inline] |
5bcae85e | 151 | fn push_front_node(&mut self, mut node: Box<Node<T>>) { |
48663c56 XL |
152 | // This method takes care not to create mutable references to whole nodes, |
153 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e SL |
154 | unsafe { |
155 | node.next = self.head; | |
156 | node.prev = None; | |
2c00a5a8 | 157 | let node = Some(Box::into_raw_non_null(node)); |
5bcae85e SL |
158 | |
159 | match self.head { | |
160 | None => self.tail = node, | |
48663c56 XL |
161 | // Not creating new mutable (unique!) references overlapping `element`. |
162 | Some(head) => (*head.as_ptr()).prev = node, | |
1a4d82fc | 163 | } |
5bcae85e SL |
164 | |
165 | self.head = node; | |
166 | self.len += 1; | |
1a4d82fc | 167 | } |
1a4d82fc JJ |
168 | } |
169 | ||
5bcae85e | 170 | /// Removes and returns the node at the front of the list. |
1a4d82fc JJ |
171 | #[inline] |
172 | fn pop_front_node(&mut self) -> Option<Box<Node<T>>> { | |
48663c56 XL |
173 | // This method takes care not to create mutable references to whole nodes, |
174 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e | 175 | self.head.map(|node| unsafe { |
7cac9316 | 176 | let node = Box::from_raw(node.as_ptr()); |
5bcae85e SL |
177 | self.head = node.next; |
178 | ||
179 | match self.head { | |
180 | None => self.tail = None, | |
48663c56 XL |
181 | // Not creating new mutable (unique!) references overlapping `element`. |
182 | Some(head) => (*head.as_ptr()).prev = None, | |
1a4d82fc | 183 | } |
5bcae85e SL |
184 | |
185 | self.len -= 1; | |
186 | node | |
1a4d82fc JJ |
187 | }) |
188 | } | |
189 | ||
5bcae85e | 190 | /// Adds the given node to the back of the list. |
1a4d82fc | 191 | #[inline] |
5bcae85e | 192 | fn push_back_node(&mut self, mut node: Box<Node<T>>) { |
48663c56 XL |
193 | // This method takes care not to create mutable references to whole nodes, |
194 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e SL |
195 | unsafe { |
196 | node.next = None; | |
197 | node.prev = self.tail; | |
2c00a5a8 | 198 | let node = Some(Box::into_raw_non_null(node)); |
5bcae85e SL |
199 | |
200 | match self.tail { | |
201 | None => self.head = node, | |
48663c56 XL |
202 | // Not creating new mutable (unique!) references overlapping `element`. |
203 | Some(tail) => (*tail.as_ptr()).next = node, | |
1a4d82fc | 204 | } |
5bcae85e SL |
205 | |
206 | self.tail = node; | |
207 | self.len += 1; | |
1a4d82fc | 208 | } |
1a4d82fc JJ |
209 | } |
210 | ||
5bcae85e | 211 | /// Removes and returns the node at the back of the list. |
1a4d82fc JJ |
212 | #[inline] |
213 | fn pop_back_node(&mut self) -> Option<Box<Node<T>>> { | |
48663c56 XL |
214 | // This method takes care not to create mutable references to whole nodes, |
215 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e | 216 | self.tail.map(|node| unsafe { |
7cac9316 | 217 | let node = Box::from_raw(node.as_ptr()); |
5bcae85e SL |
218 | self.tail = node.prev; |
219 | ||
220 | match self.tail { | |
221 | None => self.head = None, | |
48663c56 XL |
222 | // Not creating new mutable (unique!) references overlapping `element`. |
223 | Some(tail) => (*tail.as_ptr()).next = None, | |
5bcae85e SL |
224 | } |
225 | ||
226 | self.len -= 1; | |
227 | node | |
228 | }) | |
1a4d82fc | 229 | } |
ff7c6d11 XL |
230 | |
231 | /// Unlinks the specified node from the current list. | |
232 | /// | |
233 | /// Warning: this will not check that the provided node belongs to the current list. | |
48663c56 XL |
234 | /// |
235 | /// This method takes care not to create mutable references to `element`, to | |
236 | /// maintain validity of aliasing pointers. | |
ff7c6d11 | 237 | #[inline] |
2c00a5a8 | 238 | unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) { |
48663c56 | 239 | let node = node.as_mut(); // this one is ours now, we can create an &mut. |
ff7c6d11 | 240 | |
48663c56 | 241 | // Not creating new mutable (unique!) references overlapping `element`. |
ff7c6d11 | 242 | match node.prev { |
416331ca | 243 | Some(prev) => (*prev.as_ptr()).next = node.next, |
ff7c6d11 | 244 | // this node is the head node |
416331ca | 245 | None => self.head = node.next, |
ff7c6d11 XL |
246 | }; |
247 | ||
248 | match node.next { | |
416331ca | 249 | Some(next) => (*next.as_ptr()).prev = node.prev, |
ff7c6d11 | 250 | // this node is the tail node |
416331ca | 251 | None => self.tail = node.prev, |
ff7c6d11 XL |
252 | }; |
253 | ||
254 | self.len -= 1; | |
255 | } | |
1a4d82fc JJ |
256 | } |
257 | ||
85aaf69f SL |
258 | #[stable(feature = "rust1", since = "1.0.0")] |
259 | impl<T> Default for LinkedList<T> { | |
9e0c209e | 260 | /// Creates an empty `LinkedList<T>`. |
1a4d82fc | 261 | #[inline] |
5bcae85e SL |
262 | fn default() -> Self { |
263 | Self::new() | |
92a42be0 | 264 | } |
1a4d82fc JJ |
265 | } |
266 | ||
85aaf69f SL |
267 | impl<T> LinkedList<T> { |
268 | /// Creates an empty `LinkedList`. | |
5bcae85e SL |
269 | /// |
270 | /// # Examples | |
271 | /// | |
272 | /// ``` | |
273 | /// use std::collections::LinkedList; | |
274 | /// | |
275 | /// let list: LinkedList<u32> = LinkedList::new(); | |
276 | /// ``` | |
1a4d82fc | 277 | #[inline] |
60c5eb7d XL |
278 | #[cfg_attr( |
279 | not(bootstrap), | |
280 | rustc_const_stable(feature = "const_linked_list_new", since = "1.32.0"), | |
281 | )] | |
85aaf69f | 282 | #[stable(feature = "rust1", since = "1.0.0")] |
e1599b0c | 283 | pub const fn new() -> Self { |
92a42be0 | 284 | LinkedList { |
5bcae85e SL |
285 | head: None, |
286 | tail: None, | |
287 | len: 0, | |
288 | marker: PhantomData, | |
92a42be0 | 289 | } |
1a4d82fc JJ |
290 | } |
291 | ||
85aaf69f | 292 | /// Moves all elements from `other` to the end of the list. |
1a4d82fc | 293 | /// |
85aaf69f SL |
294 | /// This reuses all the nodes from `other` and moves them into `self`. After |
295 | /// this operation, `other` becomes empty. | |
296 | /// | |
297 | /// This operation should compute in O(1) time and O(1) memory. | |
1a4d82fc JJ |
298 | /// |
299 | /// # Examples | |
300 | /// | |
85aaf69f SL |
301 | /// ``` |
302 | /// use std::collections::LinkedList; | |
1a4d82fc | 303 | /// |
5bcae85e SL |
304 | /// let mut list1 = LinkedList::new(); |
305 | /// list1.push_back('a'); | |
1a4d82fc | 306 | /// |
5bcae85e SL |
307 | /// let mut list2 = LinkedList::new(); |
308 | /// list2.push_back('b'); | |
309 | /// list2.push_back('c'); | |
1a4d82fc | 310 | /// |
5bcae85e SL |
311 | /// list1.append(&mut list2); |
312 | /// | |
313 | /// let mut iter = list1.iter(); | |
314 | /// assert_eq!(iter.next(), Some(&'a')); | |
315 | /// assert_eq!(iter.next(), Some(&'b')); | |
316 | /// assert_eq!(iter.next(), Some(&'c')); | |
317 | /// assert!(iter.next().is_none()); | |
318 | /// | |
319 | /// assert!(list2.is_empty()); | |
1a4d82fc | 320 | /// ``` |
c34b1796 | 321 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
322 | pub fn append(&mut self, other: &mut Self) { |
323 | match self.tail { | |
324 | None => mem::swap(self, other), | |
7cac9316 | 325 | Some(mut tail) => { |
48663c56 XL |
326 | // `as_mut` is okay here because we have exclusive access to the entirety |
327 | // of both lists. | |
7cac9316 | 328 | if let Some(mut other_head) = other.head.take() { |
32a655c1 | 329 | unsafe { |
7cac9316 XL |
330 | tail.as_mut().next = Some(other_head); |
331 | other_head.as_mut().prev = Some(tail); | |
32a655c1 | 332 | } |
5bcae85e | 333 | |
32a655c1 SL |
334 | self.tail = other.tail.take(); |
335 | self.len += mem::replace(&mut other.len, 0); | |
336 | } | |
337 | } | |
1a4d82fc JJ |
338 | } |
339 | } | |
340 | ||
341 | /// Provides a forward iterator. | |
5bcae85e SL |
342 | /// |
343 | /// # Examples | |
344 | /// | |
345 | /// ``` | |
346 | /// use std::collections::LinkedList; | |
347 | /// | |
348 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
349 | /// | |
350 | /// list.push_back(0); | |
351 | /// list.push_back(1); | |
352 | /// list.push_back(2); | |
353 | /// | |
354 | /// let mut iter = list.iter(); | |
355 | /// assert_eq!(iter.next(), Some(&0)); | |
356 | /// assert_eq!(iter.next(), Some(&1)); | |
357 | /// assert_eq!(iter.next(), Some(&2)); | |
358 | /// assert_eq!(iter.next(), None); | |
359 | /// ``` | |
1a4d82fc | 360 | #[inline] |
85aaf69f | 361 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 362 | pub fn iter(&self) -> Iter<'_, T> { |
92a42be0 | 363 | Iter { |
5bcae85e SL |
364 | head: self.head, |
365 | tail: self.tail, | |
366 | len: self.len, | |
367 | marker: PhantomData, | |
92a42be0 | 368 | } |
1a4d82fc JJ |
369 | } |
370 | ||
371 | /// Provides a forward iterator with mutable references. | |
5bcae85e SL |
372 | /// |
373 | /// # Examples | |
374 | /// | |
375 | /// ``` | |
376 | /// use std::collections::LinkedList; | |
377 | /// | |
378 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
379 | /// | |
380 | /// list.push_back(0); | |
381 | /// list.push_back(1); | |
382 | /// list.push_back(2); | |
383 | /// | |
384 | /// for element in list.iter_mut() { | |
385 | /// *element += 10; | |
386 | /// } | |
387 | /// | |
388 | /// let mut iter = list.iter(); | |
389 | /// assert_eq!(iter.next(), Some(&10)); | |
390 | /// assert_eq!(iter.next(), Some(&11)); | |
391 | /// assert_eq!(iter.next(), Some(&12)); | |
392 | /// assert_eq!(iter.next(), None); | |
393 | /// ``` | |
1a4d82fc | 394 | #[inline] |
85aaf69f | 395 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 396 | pub fn iter_mut(&mut self) -> IterMut<'_, T> { |
62682a34 | 397 | IterMut { |
5bcae85e SL |
398 | head: self.head, |
399 | tail: self.tail, | |
400 | len: self.len, | |
92a42be0 | 401 | list: self, |
1a4d82fc JJ |
402 | } |
403 | } | |
404 | ||
85aaf69f | 405 | /// Returns `true` if the `LinkedList` is empty. |
1a4d82fc JJ |
406 | /// |
407 | /// This operation should compute in O(1) time. | |
85aaf69f SL |
408 | /// |
409 | /// # Examples | |
410 | /// | |
411 | /// ``` | |
412 | /// use std::collections::LinkedList; | |
413 | /// | |
414 | /// let mut dl = LinkedList::new(); | |
415 | /// assert!(dl.is_empty()); | |
416 | /// | |
417 | /// dl.push_front("foo"); | |
418 | /// assert!(!dl.is_empty()); | |
419 | /// ``` | |
1a4d82fc | 420 | #[inline] |
85aaf69f | 421 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 422 | pub fn is_empty(&self) -> bool { |
5bcae85e | 423 | self.head.is_none() |
1a4d82fc JJ |
424 | } |
425 | ||
85aaf69f | 426 | /// Returns the length of the `LinkedList`. |
1a4d82fc JJ |
427 | /// |
428 | /// This operation should compute in O(1) time. | |
85aaf69f SL |
429 | /// |
430 | /// # Examples | |
431 | /// | |
432 | /// ``` | |
433 | /// use std::collections::LinkedList; | |
434 | /// | |
435 | /// let mut dl = LinkedList::new(); | |
436 | /// | |
437 | /// dl.push_front(2); | |
438 | /// assert_eq!(dl.len(), 1); | |
439 | /// | |
440 | /// dl.push_front(1); | |
441 | /// assert_eq!(dl.len(), 2); | |
442 | /// | |
443 | /// dl.push_back(3); | |
444 | /// assert_eq!(dl.len(), 3); | |
85aaf69f | 445 | /// ``` |
1a4d82fc | 446 | #[inline] |
85aaf69f SL |
447 | #[stable(feature = "rust1", since = "1.0.0")] |
448 | pub fn len(&self) -> usize { | |
5bcae85e | 449 | self.len |
1a4d82fc JJ |
450 | } |
451 | ||
85aaf69f | 452 | /// Removes all elements from the `LinkedList`. |
1a4d82fc JJ |
453 | /// |
454 | /// This operation should compute in O(n) time. | |
85aaf69f SL |
455 | /// |
456 | /// # Examples | |
457 | /// | |
458 | /// ``` | |
459 | /// use std::collections::LinkedList; | |
460 | /// | |
461 | /// let mut dl = LinkedList::new(); | |
462 | /// | |
463 | /// dl.push_front(2); | |
464 | /// dl.push_front(1); | |
465 | /// assert_eq!(dl.len(), 2); | |
466 | /// assert_eq!(dl.front(), Some(&1)); | |
467 | /// | |
468 | /// dl.clear(); | |
469 | /// assert_eq!(dl.len(), 0); | |
470 | /// assert_eq!(dl.front(), None); | |
85aaf69f | 471 | /// ``` |
1a4d82fc | 472 | #[inline] |
85aaf69f | 473 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 474 | pub fn clear(&mut self) { |
5bcae85e | 475 | *self = Self::new(); |
1a4d82fc JJ |
476 | } |
477 | ||
a7813a04 XL |
478 | /// Returns `true` if the `LinkedList` contains an element equal to the |
479 | /// given value. | |
5bcae85e SL |
480 | /// |
481 | /// # Examples | |
482 | /// | |
483 | /// ``` | |
484 | /// use std::collections::LinkedList; | |
485 | /// | |
486 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
487 | /// | |
488 | /// list.push_back(0); | |
489 | /// list.push_back(1); | |
490 | /// list.push_back(2); | |
491 | /// | |
492 | /// assert_eq!(list.contains(&0), true); | |
493 | /// assert_eq!(list.contains(&10), false); | |
494 | /// ``` | |
495 | #[stable(feature = "linked_list_contains", since = "1.12.0")] | |
a7813a04 XL |
496 | pub fn contains(&self, x: &T) -> bool |
497 | where T: PartialEq<T> | |
498 | { | |
499 | self.iter().any(|e| e == x) | |
500 | } | |
501 | ||
1a4d82fc JJ |
502 | /// Provides a reference to the front element, or `None` if the list is |
503 | /// empty. | |
85aaf69f SL |
504 | /// |
505 | /// # Examples | |
506 | /// | |
507 | /// ``` | |
508 | /// use std::collections::LinkedList; | |
509 | /// | |
510 | /// let mut dl = LinkedList::new(); | |
511 | /// assert_eq!(dl.front(), None); | |
512 | /// | |
513 | /// dl.push_front(1); | |
514 | /// assert_eq!(dl.front(), Some(&1)); | |
85aaf69f | 515 | /// ``` |
1a4d82fc | 516 | #[inline] |
85aaf69f | 517 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 518 | pub fn front(&self) -> Option<&T> { |
7cac9316 XL |
519 | unsafe { |
520 | self.head.as_ref().map(|node| &node.as_ref().element) | |
521 | } | |
1a4d82fc JJ |
522 | } |
523 | ||
524 | /// Provides a mutable reference to the front element, or `None` if the list | |
525 | /// is empty. | |
85aaf69f SL |
526 | /// |
527 | /// # Examples | |
528 | /// | |
529 | /// ``` | |
530 | /// use std::collections::LinkedList; | |
531 | /// | |
532 | /// let mut dl = LinkedList::new(); | |
533 | /// assert_eq!(dl.front(), None); | |
534 | /// | |
535 | /// dl.push_front(1); | |
536 | /// assert_eq!(dl.front(), Some(&1)); | |
537 | /// | |
538 | /// match dl.front_mut() { | |
539 | /// None => {}, | |
540 | /// Some(x) => *x = 5, | |
541 | /// } | |
542 | /// assert_eq!(dl.front(), Some(&5)); | |
85aaf69f | 543 | /// ``` |
1a4d82fc | 544 | #[inline] |
85aaf69f | 545 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 546 | pub fn front_mut(&mut self) -> Option<&mut T> { |
7cac9316 XL |
547 | unsafe { |
548 | self.head.as_mut().map(|node| &mut node.as_mut().element) | |
549 | } | |
1a4d82fc JJ |
550 | } |
551 | ||
552 | /// Provides a reference to the back element, or `None` if the list is | |
553 | /// empty. | |
85aaf69f SL |
554 | /// |
555 | /// # Examples | |
556 | /// | |
557 | /// ``` | |
558 | /// use std::collections::LinkedList; | |
559 | /// | |
560 | /// let mut dl = LinkedList::new(); | |
561 | /// assert_eq!(dl.back(), None); | |
562 | /// | |
563 | /// dl.push_back(1); | |
564 | /// assert_eq!(dl.back(), Some(&1)); | |
85aaf69f | 565 | /// ``` |
1a4d82fc | 566 | #[inline] |
85aaf69f | 567 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 568 | pub fn back(&self) -> Option<&T> { |
7cac9316 XL |
569 | unsafe { |
570 | self.tail.as_ref().map(|node| &node.as_ref().element) | |
571 | } | |
1a4d82fc JJ |
572 | } |
573 | ||
574 | /// Provides a mutable reference to the back element, or `None` if the list | |
575 | /// is empty. | |
85aaf69f SL |
576 | /// |
577 | /// # Examples | |
578 | /// | |
579 | /// ``` | |
580 | /// use std::collections::LinkedList; | |
581 | /// | |
582 | /// let mut dl = LinkedList::new(); | |
583 | /// assert_eq!(dl.back(), None); | |
584 | /// | |
585 | /// dl.push_back(1); | |
586 | /// assert_eq!(dl.back(), Some(&1)); | |
587 | /// | |
588 | /// match dl.back_mut() { | |
589 | /// None => {}, | |
590 | /// Some(x) => *x = 5, | |
591 | /// } | |
592 | /// assert_eq!(dl.back(), Some(&5)); | |
85aaf69f | 593 | /// ``` |
1a4d82fc | 594 | #[inline] |
85aaf69f | 595 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 596 | pub fn back_mut(&mut self) -> Option<&mut T> { |
7cac9316 XL |
597 | unsafe { |
598 | self.tail.as_mut().map(|node| &mut node.as_mut().element) | |
599 | } | |
1a4d82fc JJ |
600 | } |
601 | ||
602 | /// Adds an element first in the list. | |
603 | /// | |
604 | /// This operation should compute in O(1) time. | |
85aaf69f SL |
605 | /// |
606 | /// # Examples | |
607 | /// | |
608 | /// ``` | |
609 | /// use std::collections::LinkedList; | |
610 | /// | |
611 | /// let mut dl = LinkedList::new(); | |
612 | /// | |
613 | /// dl.push_front(2); | |
614 | /// assert_eq!(dl.front().unwrap(), &2); | |
615 | /// | |
616 | /// dl.push_front(1); | |
617 | /// assert_eq!(dl.front().unwrap(), &1); | |
85aaf69f SL |
618 | /// ``` |
619 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 620 | pub fn push_front(&mut self, elt: T) { |
5bcae85e | 621 | self.push_front_node(box Node::new(elt)); |
1a4d82fc JJ |
622 | } |
623 | ||
624 | /// Removes the first element and returns it, or `None` if the list is | |
625 | /// empty. | |
626 | /// | |
627 | /// This operation should compute in O(1) time. | |
85aaf69f SL |
628 | /// |
629 | /// # Examples | |
630 | /// | |
631 | /// ``` | |
632 | /// use std::collections::LinkedList; | |
633 | /// | |
634 | /// let mut d = LinkedList::new(); | |
635 | /// assert_eq!(d.pop_front(), None); | |
636 | /// | |
637 | /// d.push_front(1); | |
638 | /// d.push_front(3); | |
639 | /// assert_eq!(d.pop_front(), Some(3)); | |
640 | /// assert_eq!(d.pop_front(), Some(1)); | |
641 | /// assert_eq!(d.pop_front(), None); | |
85aaf69f | 642 | /// ``` |
85aaf69f | 643 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 644 | pub fn pop_front(&mut self) -> Option<T> { |
5bcae85e | 645 | self.pop_front_node().map(Node::into_element) |
1a4d82fc JJ |
646 | } |
647 | ||
0731742a XL |
648 | /// Appends an element to the back of a list. |
649 | /// | |
650 | /// This operation should compute in O(1) time. | |
1a4d82fc JJ |
651 | /// |
652 | /// # Examples | |
653 | /// | |
85aaf69f SL |
654 | /// ``` |
655 | /// use std::collections::LinkedList; | |
1a4d82fc | 656 | /// |
85aaf69f SL |
657 | /// let mut d = LinkedList::new(); |
658 | /// d.push_back(1); | |
1a4d82fc JJ |
659 | /// d.push_back(3); |
660 | /// assert_eq!(3, *d.back().unwrap()); | |
661 | /// ``` | |
85aaf69f | 662 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 663 | pub fn push_back(&mut self, elt: T) { |
5bcae85e | 664 | self.push_back_node(box Node::new(elt)); |
1a4d82fc JJ |
665 | } |
666 | ||
667 | /// Removes the last element from a list and returns it, or `None` if | |
668 | /// it is empty. | |
669 | /// | |
0731742a XL |
670 | /// This operation should compute in O(1) time. |
671 | /// | |
1a4d82fc JJ |
672 | /// # Examples |
673 | /// | |
85aaf69f SL |
674 | /// ``` |
675 | /// use std::collections::LinkedList; | |
1a4d82fc | 676 | /// |
85aaf69f | 677 | /// let mut d = LinkedList::new(); |
1a4d82fc | 678 | /// assert_eq!(d.pop_back(), None); |
85aaf69f | 679 | /// d.push_back(1); |
1a4d82fc JJ |
680 | /// d.push_back(3); |
681 | /// assert_eq!(d.pop_back(), Some(3)); | |
682 | /// ``` | |
85aaf69f | 683 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 684 | pub fn pop_back(&mut self) -> Option<T> { |
5bcae85e | 685 | self.pop_back_node().map(Node::into_element) |
1a4d82fc | 686 | } |
85aaf69f SL |
687 | |
688 | /// Splits the list into two at the given index. Returns everything after the given index, | |
689 | /// including the index. | |
690 | /// | |
cc61c64b XL |
691 | /// This operation should compute in O(n) time. |
692 | /// | |
85aaf69f SL |
693 | /// # Panics |
694 | /// | |
695 | /// Panics if `at > len`. | |
696 | /// | |
85aaf69f SL |
697 | /// # Examples |
698 | /// | |
699 | /// ``` | |
700 | /// use std::collections::LinkedList; | |
701 | /// | |
702 | /// let mut d = LinkedList::new(); | |
703 | /// | |
704 | /// d.push_front(1); | |
705 | /// d.push_front(2); | |
706 | /// d.push_front(3); | |
707 | /// | |
708 | /// let mut splitted = d.split_off(2); | |
709 | /// | |
710 | /// assert_eq!(splitted.pop_front(), Some(1)); | |
711 | /// assert_eq!(splitted.pop_front(), None); | |
712 | /// ``` | |
713 | #[stable(feature = "rust1", since = "1.0.0")] | |
714 | pub fn split_off(&mut self, at: usize) -> LinkedList<T> { | |
715 | let len = self.len(); | |
716 | assert!(at <= len, "Cannot split off at a nonexistent index"); | |
717 | if at == 0 { | |
416331ca | 718 | return mem::take(self); |
85aaf69f | 719 | } else if at == len { |
5bcae85e | 720 | return Self::new(); |
85aaf69f SL |
721 | } |
722 | ||
723 | // Below, we iterate towards the `i-1`th node, either from the start or the end, | |
724 | // depending on which would be faster. | |
5bcae85e | 725 | let split_node = if at - 1 <= len - 1 - (at - 1) { |
85aaf69f SL |
726 | let mut iter = self.iter_mut(); |
727 | // instead of skipping using .skip() (which creates a new struct), | |
728 | // we skip manually so we can access the head field without | |
729 | // depending on implementation details of Skip | |
730 | for _ in 0..at - 1 { | |
731 | iter.next(); | |
732 | } | |
733 | iter.head | |
92a42be0 | 734 | } else { |
85aaf69f SL |
735 | // better off starting from the end |
736 | let mut iter = self.iter_mut(); | |
737 | for _ in 0..len - 1 - (at - 1) { | |
738 | iter.next_back(); | |
739 | } | |
740 | iter.tail | |
741 | }; | |
742 | ||
62682a34 SL |
743 | // The split node is the new tail node of the first part and owns |
744 | // the head of the second part. | |
5bcae85e | 745 | let second_part_head; |
62682a34 SL |
746 | |
747 | unsafe { | |
7cac9316 XL |
748 | second_part_head = split_node.unwrap().as_mut().next.take(); |
749 | if let Some(mut head) = second_part_head { | |
750 | head.as_mut().prev = None; | |
62682a34 SL |
751 | } |
752 | } | |
753 | ||
754 | let second_part = LinkedList { | |
5bcae85e SL |
755 | head: second_part_head, |
756 | tail: self.tail, | |
757 | len: len - at, | |
758 | marker: PhantomData, | |
85aaf69f SL |
759 | }; |
760 | ||
62682a34 | 761 | // Fix the tail ptr of the first part |
5bcae85e SL |
762 | self.tail = split_node; |
763 | self.len = at; | |
85aaf69f | 764 | |
62682a34 | 765 | second_part |
85aaf69f | 766 | } |
7453a54e | 767 | |
ff7c6d11 XL |
768 | /// Creates an iterator which uses a closure to determine if an element should be removed. |
769 | /// | |
770 | /// If the closure returns true, then the element is removed and yielded. | |
0531ce1d XL |
771 | /// If the closure returns false, the element will remain in the list and will not be yielded |
772 | /// by the iterator. | |
ff7c6d11 XL |
773 | /// |
774 | /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of | |
775 | /// whether you choose to keep or remove it. | |
776 | /// | |
777 | /// # Examples | |
778 | /// | |
779 | /// Splitting a list into evens and odds, reusing the original list: | |
780 | /// | |
781 | /// ``` | |
782 | /// #![feature(drain_filter)] | |
783 | /// use std::collections::LinkedList; | |
784 | /// | |
785 | /// let mut numbers: LinkedList<u32> = LinkedList::new(); | |
786 | /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]); | |
787 | /// | |
788 | /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>(); | |
789 | /// let odds = numbers; | |
790 | /// | |
791 | /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]); | |
792 | /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]); | |
793 | /// ``` | |
794 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 795 | pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F> |
ff7c6d11 XL |
796 | where F: FnMut(&mut T) -> bool |
797 | { | |
798 | // avoid borrow issues. | |
799 | let it = self.head; | |
800 | let old_len = self.len; | |
801 | ||
802 | DrainFilter { | |
803 | list: self, | |
804 | it: it, | |
805 | pred: filter, | |
806 | idx: 0, | |
807 | old_len: old_len, | |
808 | } | |
809 | } | |
1a4d82fc JJ |
810 | } |
811 | ||
85aaf69f | 812 | #[stable(feature = "rust1", since = "1.0.0")] |
32a655c1 | 813 | unsafe impl<#[may_dangle] T> Drop for LinkedList<T> { |
1a4d82fc | 814 | fn drop(&mut self) { |
60c5eb7d XL |
815 | struct DropGuard<'a, T>(&'a mut LinkedList<T>); |
816 | ||
817 | impl<'a, T> Drop for DropGuard<'a, T> { | |
818 | fn drop(&mut self) { | |
819 | // Continue the same loop we do below. This only runs when a destructor has | |
820 | // panicked. If another one panics this will abort. | |
821 | while let Some(_) = self.0.pop_front_node() {} | |
822 | } | |
823 | } | |
824 | ||
825 | while let Some(node) = self.pop_front_node() { | |
826 | let guard = DropGuard(self); | |
827 | drop(node); | |
828 | mem::forget(guard); | |
829 | } | |
1a4d82fc JJ |
830 | } |
831 | } | |
832 | ||
85aaf69f | 833 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
834 | impl<'a, T> Iterator for Iter<'a, T> { |
835 | type Item = &'a T; | |
1a4d82fc JJ |
836 | |
837 | #[inline] | |
5bcae85e SL |
838 | fn next(&mut self) -> Option<&'a T> { |
839 | if self.len == 0 { | |
840 | None | |
841 | } else { | |
842 | self.head.map(|node| unsafe { | |
7cac9316 XL |
843 | // Need an unbound lifetime to get 'a |
844 | let node = &*node.as_ptr(); | |
5bcae85e SL |
845 | self.len -= 1; |
846 | self.head = node.next; | |
847 | &node.element | |
848 | }) | |
1a4d82fc | 849 | } |
1a4d82fc JJ |
850 | } |
851 | ||
852 | #[inline] | |
85aaf69f | 853 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 854 | (self.len, Some(self.len)) |
1a4d82fc | 855 | } |
416331ca XL |
856 | |
857 | #[inline] | |
858 | fn last(mut self) -> Option<&'a T> { | |
859 | self.next_back() | |
860 | } | |
1a4d82fc JJ |
861 | } |
862 | ||
85aaf69f | 863 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 864 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
1a4d82fc | 865 | #[inline] |
5bcae85e SL |
866 | fn next_back(&mut self) -> Option<&'a T> { |
867 | if self.len == 0 { | |
868 | None | |
869 | } else { | |
870 | self.tail.map(|node| unsafe { | |
7cac9316 XL |
871 | // Need an unbound lifetime to get 'a |
872 | let node = &*node.as_ptr(); | |
5bcae85e SL |
873 | self.len -= 1; |
874 | self.tail = node.prev; | |
875 | &node.element | |
62682a34 SL |
876 | }) |
877 | } | |
1a4d82fc JJ |
878 | } |
879 | } | |
880 | ||
85aaf69f | 881 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 882 | impl<T> ExactSizeIterator for Iter<'_, T> {} |
1a4d82fc | 883 | |
0531ce1d | 884 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 885 | impl<T> FusedIterator for Iter<'_, T> {} |
9e0c209e | 886 | |
85aaf69f | 887 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
888 | impl<'a, T> Iterator for IterMut<'a, T> { |
889 | type Item = &'a mut T; | |
890 | ||
1a4d82fc | 891 | #[inline] |
5bcae85e SL |
892 | fn next(&mut self) -> Option<&'a mut T> { |
893 | if self.len == 0 { | |
894 | None | |
895 | } else { | |
896 | self.head.map(|node| unsafe { | |
7cac9316 XL |
897 | // Need an unbound lifetime to get 'a |
898 | let node = &mut *node.as_ptr(); | |
5bcae85e SL |
899 | self.len -= 1; |
900 | self.head = node.next; | |
901 | &mut node.element | |
62682a34 SL |
902 | }) |
903 | } | |
1a4d82fc JJ |
904 | } |
905 | ||
906 | #[inline] | |
85aaf69f | 907 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 908 | (self.len, Some(self.len)) |
1a4d82fc | 909 | } |
416331ca XL |
910 | |
911 | #[inline] | |
912 | fn last(mut self) -> Option<&'a mut T> { | |
913 | self.next_back() | |
914 | } | |
1a4d82fc JJ |
915 | } |
916 | ||
85aaf69f | 917 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 918 | impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { |
1a4d82fc | 919 | #[inline] |
5bcae85e SL |
920 | fn next_back(&mut self) -> Option<&'a mut T> { |
921 | if self.len == 0 { | |
922 | None | |
923 | } else { | |
924 | self.tail.map(|node| unsafe { | |
7cac9316 XL |
925 | // Need an unbound lifetime to get 'a |
926 | let node = &mut *node.as_ptr(); | |
5bcae85e SL |
927 | self.len -= 1; |
928 | self.tail = node.prev; | |
929 | &mut node.element | |
62682a34 SL |
930 | }) |
931 | } | |
1a4d82fc JJ |
932 | } |
933 | } | |
934 | ||
85aaf69f | 935 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 936 | impl<T> ExactSizeIterator for IterMut<'_, T> {} |
1a4d82fc | 937 | |
0531ce1d | 938 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 939 | impl<T> FusedIterator for IterMut<'_, T> {} |
9e0c209e | 940 | |
9fa01778 | 941 | impl<T> IterMut<'_, T> { |
5bcae85e | 942 | /// Inserts the given element just after the element most recently returned by `.next()`. |
1a4d82fc JJ |
943 | /// The inserted element does not appear in the iteration. |
944 | /// | |
945 | /// # Examples | |
946 | /// | |
85aaf69f | 947 | /// ``` |
c1a9b12d SL |
948 | /// #![feature(linked_list_extras)] |
949 | /// | |
85aaf69f | 950 | /// use std::collections::LinkedList; |
1a4d82fc | 951 | /// |
85aaf69f | 952 | /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect(); |
1a4d82fc JJ |
953 | /// |
954 | /// { | |
955 | /// let mut it = list.iter_mut(); | |
956 | /// assert_eq!(it.next().unwrap(), &1); | |
957 | /// // insert `2` after `1` | |
958 | /// it.insert_next(2); | |
959 | /// } | |
960 | /// { | |
85aaf69f | 961 | /// let vec: Vec<_> = list.into_iter().collect(); |
c34b1796 | 962 | /// assert_eq!(vec, [1, 2, 3, 4]); |
1a4d82fc JJ |
963 | /// } |
964 | /// ``` | |
965 | #[inline] | |
62682a34 | 966 | #[unstable(feature = "linked_list_extras", |
e9174d1e SL |
967 | reason = "this is probably better handled by a cursor type -- we'll see", |
968 | issue = "27794")] | |
5bcae85e SL |
969 | pub fn insert_next(&mut self, element: T) { |
970 | match self.head { | |
48663c56 | 971 | // `push_back` is okay with aliasing `element` references |
5bcae85e | 972 | None => self.list.push_back(element), |
48663c56 XL |
973 | Some(head) => unsafe { |
974 | let prev = match head.as_ref().prev { | |
975 | // `push_front` is okay with aliasing nodes | |
5bcae85e SL |
976 | None => return self.list.push_front(element), |
977 | Some(prev) => prev, | |
978 | }; | |
979 | ||
2c00a5a8 | 980 | let node = Some(Box::into_raw_non_null(box Node { |
5bcae85e SL |
981 | next: Some(head), |
982 | prev: Some(prev), | |
3b2f2976 | 983 | element, |
2c00a5a8 | 984 | })); |
5bcae85e | 985 | |
48663c56 XL |
986 | // Not creating references to entire nodes to not invalidate the |
987 | // reference to `element` we handed to the user. | |
988 | (*prev.as_ptr()).next = node; | |
989 | (*head.as_ptr()).prev = node; | |
5bcae85e SL |
990 | |
991 | self.list.len += 1; | |
32a655c1 | 992 | }, |
5bcae85e | 993 | } |
1a4d82fc JJ |
994 | } |
995 | ||
996 | /// Provides a reference to the next element, without changing the iterator. | |
997 | /// | |
998 | /// # Examples | |
999 | /// | |
85aaf69f | 1000 | /// ``` |
c1a9b12d SL |
1001 | /// #![feature(linked_list_extras)] |
1002 | /// | |
85aaf69f | 1003 | /// use std::collections::LinkedList; |
1a4d82fc | 1004 | /// |
85aaf69f | 1005 | /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect(); |
1a4d82fc JJ |
1006 | /// |
1007 | /// let mut it = list.iter_mut(); | |
1008 | /// assert_eq!(it.next().unwrap(), &1); | |
1009 | /// assert_eq!(it.peek_next().unwrap(), &2); | |
1010 | /// // We just peeked at 2, so it was not consumed from the iterator. | |
1011 | /// assert_eq!(it.next().unwrap(), &2); | |
1012 | /// ``` | |
1013 | #[inline] | |
62682a34 | 1014 | #[unstable(feature = "linked_list_extras", |
e9174d1e SL |
1015 | reason = "this is probably better handled by a cursor type -- we'll see", |
1016 | issue = "27794")] | |
5bcae85e SL |
1017 | pub fn peek_next(&mut self) -> Option<&mut T> { |
1018 | if self.len == 0 { | |
1019 | None | |
1020 | } else { | |
7cac9316 XL |
1021 | unsafe { |
1022 | self.head.as_mut().map(|node| &mut node.as_mut().element) | |
1023 | } | |
62682a34 | 1024 | } |
1a4d82fc JJ |
1025 | } |
1026 | } | |
1027 | ||
ff7c6d11 XL |
1028 | /// An iterator produced by calling `drain_filter` on LinkedList. |
1029 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
1030 | pub struct DrainFilter<'a, T: 'a, F: 'a> | |
1031 | where F: FnMut(&mut T) -> bool, | |
1032 | { | |
1033 | list: &'a mut LinkedList<T>, | |
2c00a5a8 | 1034 | it: Option<NonNull<Node<T>>>, |
ff7c6d11 XL |
1035 | pred: F, |
1036 | idx: usize, | |
1037 | old_len: usize, | |
1038 | } | |
1039 | ||
1040 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1041 | impl<T, F> Iterator for DrainFilter<'_, T, F> |
ff7c6d11 XL |
1042 | where F: FnMut(&mut T) -> bool, |
1043 | { | |
1044 | type Item = T; | |
1045 | ||
1046 | fn next(&mut self) -> Option<T> { | |
1047 | while let Some(mut node) = self.it { | |
1048 | unsafe { | |
1049 | self.it = node.as_ref().next; | |
1050 | self.idx += 1; | |
1051 | ||
1052 | if (self.pred)(&mut node.as_mut().element) { | |
48663c56 | 1053 | // `unlink_node` is okay with aliasing `element` references. |
ff7c6d11 XL |
1054 | self.list.unlink_node(node); |
1055 | return Some(Box::from_raw(node.as_ptr()).element); | |
1056 | } | |
1057 | } | |
1058 | } | |
1059 | ||
1060 | None | |
1061 | } | |
1062 | ||
1063 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1064 | (0, Some(self.old_len - self.idx)) | |
1065 | } | |
1066 | } | |
1067 | ||
1068 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1069 | impl<T, F> Drop for DrainFilter<'_, T, F> |
ff7c6d11 XL |
1070 | where F: FnMut(&mut T) -> bool, |
1071 | { | |
1072 | fn drop(&mut self) { | |
83c7162d | 1073 | self.for_each(drop); |
ff7c6d11 XL |
1074 | } |
1075 | } | |
1076 | ||
1077 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1078 | impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F> |
ff7c6d11 XL |
1079 | where F: FnMut(&mut T) -> bool |
1080 | { | |
9fa01778 | 1081 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
ff7c6d11 XL |
1082 | f.debug_tuple("DrainFilter") |
1083 | .field(&self.list) | |
1084 | .finish() | |
1085 | } | |
1086 | } | |
1087 | ||
85aaf69f | 1088 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1089 | impl<T> Iterator for IntoIter<T> { |
1090 | type Item = T; | |
1a4d82fc JJ |
1091 | |
1092 | #[inline] | |
5bcae85e | 1093 | fn next(&mut self) -> Option<T> { |
92a42be0 SL |
1094 | self.list.pop_front() |
1095 | } | |
1a4d82fc JJ |
1096 | |
1097 | #[inline] | |
85aaf69f | 1098 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 1099 | (self.list.len, Some(self.list.len)) |
1a4d82fc JJ |
1100 | } |
1101 | } | |
1102 | ||
85aaf69f | 1103 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1104 | impl<T> DoubleEndedIterator for IntoIter<T> { |
1a4d82fc | 1105 | #[inline] |
5bcae85e | 1106 | fn next_back(&mut self) -> Option<T> { |
92a42be0 SL |
1107 | self.list.pop_back() |
1108 | } | |
1a4d82fc JJ |
1109 | } |
1110 | ||
92a42be0 | 1111 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1112 | impl<T> ExactSizeIterator for IntoIter<T> {} |
c34b1796 | 1113 | |
0531ce1d | 1114 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e SL |
1115 | impl<T> FusedIterator for IntoIter<T> {} |
1116 | ||
85aaf69f | 1117 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1118 | impl<T> FromIterator<T> for LinkedList<T> { |
1119 | fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { | |
1120 | let mut list = Self::new(); | |
1121 | list.extend(iter); | |
1122 | list | |
1a4d82fc JJ |
1123 | } |
1124 | } | |
1125 | ||
85aaf69f SL |
1126 | #[stable(feature = "rust1", since = "1.0.0")] |
1127 | impl<T> IntoIterator for LinkedList<T> { | |
1128 | type Item = T; | |
1129 | type IntoIter = IntoIter<T>; | |
1130 | ||
9346a6ac AL |
1131 | /// Consumes the list into an iterator yielding elements by value. |
1132 | #[inline] | |
85aaf69f | 1133 | fn into_iter(self) -> IntoIter<T> { |
92a42be0 | 1134 | IntoIter { list: self } |
85aaf69f SL |
1135 | } |
1136 | } | |
1137 | ||
1138 | #[stable(feature = "rust1", since = "1.0.0")] | |
1139 | impl<'a, T> IntoIterator for &'a LinkedList<T> { | |
1140 | type Item = &'a T; | |
1141 | type IntoIter = Iter<'a, T>; | |
1142 | ||
1143 | fn into_iter(self) -> Iter<'a, T> { | |
1144 | self.iter() | |
1145 | } | |
1146 | } | |
1147 | ||
92a42be0 | 1148 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
1149 | impl<'a, T> IntoIterator for &'a mut LinkedList<T> { |
1150 | type Item = &'a mut T; | |
1151 | type IntoIter = IterMut<'a, T>; | |
1152 | ||
5bcae85e | 1153 | fn into_iter(self) -> IterMut<'a, T> { |
85aaf69f | 1154 | self.iter_mut() |
1a4d82fc JJ |
1155 | } |
1156 | } | |
1157 | ||
85aaf69f | 1158 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1159 | impl<T> Extend<T> for LinkedList<T> { |
1160 | fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { | |
1161 | <Self as SpecExtend<I>>::spec_extend(self, iter); | |
a7813a04 XL |
1162 | } |
1163 | } | |
1164 | ||
1165 | impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> { | |
1166 | default fn spec_extend(&mut self, iter: I) { | |
532ac7d7 | 1167 | iter.into_iter().for_each(move |elt| self.push_back(elt)); |
85aaf69f SL |
1168 | } |
1169 | } | |
1170 | ||
a7813a04 XL |
1171 | impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> { |
1172 | fn spec_extend(&mut self, ref mut other: LinkedList<T>) { | |
1173 | self.append(other); | |
1174 | } | |
1175 | } | |
1176 | ||
62682a34 SL |
1177 | #[stable(feature = "extend_ref", since = "1.2.0")] |
1178 | impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> { | |
92a42be0 | 1179 | fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { |
62682a34 SL |
1180 | self.extend(iter.into_iter().cloned()); |
1181 | } | |
1182 | } | |
1183 | ||
85aaf69f | 1184 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1185 | impl<T: PartialEq> PartialEq for LinkedList<T> { |
1186 | fn eq(&self, other: &Self) -> bool { | |
1187 | self.len() == other.len() && self.iter().eq(other) | |
1a4d82fc JJ |
1188 | } |
1189 | ||
5bcae85e SL |
1190 | fn ne(&self, other: &Self) -> bool { |
1191 | self.len() != other.len() || self.iter().ne(other) | |
1a4d82fc JJ |
1192 | } |
1193 | } | |
1194 | ||
85aaf69f | 1195 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1196 | impl<T: Eq> Eq for LinkedList<T> {} |
1a4d82fc | 1197 | |
85aaf69f | 1198 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1199 | impl<T: PartialOrd> PartialOrd for LinkedList<T> { |
1200 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { | |
1201 | self.iter().partial_cmp(other) | |
1a4d82fc JJ |
1202 | } |
1203 | } | |
1204 | ||
85aaf69f | 1205 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1206 | impl<T: Ord> Ord for LinkedList<T> { |
1a4d82fc | 1207 | #[inline] |
5bcae85e SL |
1208 | fn cmp(&self, other: &Self) -> Ordering { |
1209 | self.iter().cmp(other) | |
1a4d82fc JJ |
1210 | } |
1211 | } | |
1212 | ||
85aaf69f | 1213 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1214 | impl<T: Clone> Clone for LinkedList<T> { |
1215 | fn clone(&self) -> Self { | |
85aaf69f | 1216 | self.iter().cloned().collect() |
1a4d82fc | 1217 | } |
e74abb32 XL |
1218 | |
1219 | fn clone_from(&mut self, other: &Self) { | |
1220 | let mut iter_other = other.iter(); | |
1221 | if self.len() > other.len() { | |
1222 | self.split_off(other.len()); | |
1223 | } | |
1224 | for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) { | |
1225 | elem.clone_from(elem_other); | |
1226 | } | |
1227 | if !iter_other.is_empty() { | |
1228 | self.extend(iter_other.cloned()); | |
1229 | } | |
1230 | } | |
1a4d82fc JJ |
1231 | } |
1232 | ||
85aaf69f | 1233 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1234 | impl<T: fmt::Debug> fmt::Debug for LinkedList<T> { |
9fa01778 | 1235 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
5bcae85e | 1236 | f.debug_list().entries(self).finish() |
1a4d82fc JJ |
1237 | } |
1238 | } | |
1239 | ||
85aaf69f | 1240 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1241 | impl<T: Hash> Hash for LinkedList<T> { |
85aaf69f SL |
1242 | fn hash<H: Hasher>(&self, state: &mut H) { |
1243 | self.len().hash(state); | |
1244 | for elt in self { | |
1a4d82fc JJ |
1245 | elt.hash(state); |
1246 | } | |
1247 | } | |
1248 | } | |
1249 | ||
9cc50fc6 SL |
1250 | // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters. |
1251 | #[allow(dead_code)] | |
1252 | fn assert_covariance() { | |
32a655c1 SL |
1253 | fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> { |
1254 | x | |
1255 | } | |
1256 | fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> { | |
1257 | x | |
1258 | } | |
1259 | fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> { | |
1260 | x | |
1261 | } | |
9cc50fc6 SL |
1262 | } |
1263 | ||
5bcae85e SL |
1264 | #[stable(feature = "rust1", since = "1.0.0")] |
1265 | unsafe impl<T: Send> Send for LinkedList<T> {} | |
1266 | ||
1267 | #[stable(feature = "rust1", since = "1.0.0")] | |
1268 | unsafe impl<T: Sync> Sync for LinkedList<T> {} | |
1269 | ||
1270 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1271 | unsafe impl<T: Sync> Send for Iter<'_, T> {} |
5bcae85e SL |
1272 | |
1273 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1274 | unsafe impl<T: Sync> Sync for Iter<'_, T> {} |
5bcae85e SL |
1275 | |
1276 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1277 | unsafe impl<T: Send> Send for IterMut<'_, T> {} |
5bcae85e SL |
1278 | |
1279 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1280 | unsafe impl<T: Sync> Sync for IterMut<'_, T> {} |