]>
Commit | Line | Data |
---|---|---|
85aaf69f | 1 | // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT |
1a4d82fc JJ |
2 | // file at the top-level directory of this distribution and at |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! A doubly-linked list with owned nodes. | |
12 | //! | |
32a655c1 SL |
13 | //! The `LinkedList` allows pushing and popping elements at either end |
14 | //! in constant time. | |
15 | //! | |
16 | //! Almost always it is better to use `Vec` or [`VecDeque`] instead of | |
17 | //! [`LinkedList`]. In general, array-based containers are faster, | |
18 | //! more memory efficient and make better use of CPU cache. | |
19 | //! | |
20 | //! [`LinkedList`]: ../linked_list/struct.LinkedList.html | |
21 | //! [`VecDeque`]: ../vec_deque/struct.VecDeque.html | |
1a4d82fc | 22 | |
85aaf69f | 23 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 24 | |
1a4d82fc | 25 | use core::cmp::Ordering; |
1a4d82fc | 26 | use core::fmt; |
85aaf69f | 27 | use core::hash::{Hasher, Hash}; |
9e0c209e | 28 | use core::iter::{FromIterator, FusedIterator}; |
5bcae85e | 29 | use core::marker::PhantomData; |
1a4d82fc | 30 | use core::mem; |
7453a54e | 31 | use core::ops::{BoxPlace, InPlace, Place, Placer}; |
2c00a5a8 | 32 | use core::ptr::{self, NonNull}; |
1a4d82fc | 33 | |
041b39d2 | 34 | use boxed::{Box, IntermediateBox}; |
a7813a04 XL |
35 | use super::SpecExtend; |
36 | ||
32a655c1 SL |
37 | /// A doubly-linked list with owned nodes. |
38 | /// | |
39 | /// The `LinkedList` allows pushing and popping elements at either end | |
40 | /// in constant time. | |
41 | /// | |
42 | /// Almost always it is better to use `Vec` or `VecDeque` instead of | |
43 | /// `LinkedList`. In general, array-based containers are faster, | |
44 | /// more memory efficient and make better use of CPU cache. | |
85aaf69f SL |
45 | #[stable(feature = "rust1", since = "1.0.0")] |
46 | pub struct LinkedList<T> { | |
2c00a5a8 XL |
47 | head: Option<NonNull<Node<T>>>, |
48 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e SL |
49 | len: usize, |
50 | marker: PhantomData<Box<Node<T>>>, | |
1a4d82fc JJ |
51 | } |
52 | ||
1a4d82fc | 53 | struct Node<T> { |
2c00a5a8 XL |
54 | next: Option<NonNull<Node<T>>>, |
55 | prev: Option<NonNull<Node<T>>>, | |
5bcae85e | 56 | element: T, |
1a4d82fc JJ |
57 | } |
58 | ||
cc61c64b XL |
59 | /// An iterator over the elements of a `LinkedList`. |
60 | /// | |
61 | /// This `struct` is created by the [`iter`] method on [`LinkedList`]. See its | |
62 | /// documentation for more. | |
63 | /// | |
64 | /// [`iter`]: struct.LinkedList.html#method.iter | |
65 | /// [`LinkedList`]: struct.LinkedList.html | |
85aaf69f | 66 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 67 | pub struct Iter<'a, T: 'a> { |
2c00a5a8 XL |
68 | head: Option<NonNull<Node<T>>>, |
69 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e SL |
70 | len: usize, |
71 | marker: PhantomData<&'a Node<T>>, | |
1a4d82fc JJ |
72 | } |
73 | ||
8bb4bdeb XL |
74 | #[stable(feature = "collection_debug", since = "1.17.0")] |
75 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> { | |
76 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
77 | f.debug_tuple("Iter") | |
cc61c64b | 78 | .field(&self.len) |
8bb4bdeb XL |
79 | .finish() |
80 | } | |
81 | } | |
82 | ||
ea8adc8c | 83 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
85aaf69f | 84 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 85 | impl<'a, T> Clone for Iter<'a, T> { |
5bcae85e SL |
86 | fn clone(&self) -> Self { |
87 | Iter { ..*self } | |
1a4d82fc JJ |
88 | } |
89 | } | |
90 | ||
cc61c64b XL |
91 | /// A mutable iterator over the elements of a `LinkedList`. |
92 | /// | |
93 | /// This `struct` is created by the [`iter_mut`] method on [`LinkedList`]. See its | |
94 | /// documentation for more. | |
95 | /// | |
96 | /// [`iter_mut`]: struct.LinkedList.html#method.iter_mut | |
97 | /// [`LinkedList`]: struct.LinkedList.html | |
85aaf69f | 98 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 99 | pub struct IterMut<'a, T: 'a> { |
85aaf69f | 100 | list: &'a mut LinkedList<T>, |
2c00a5a8 XL |
101 | head: Option<NonNull<Node<T>>>, |
102 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e | 103 | len: usize, |
1a4d82fc JJ |
104 | } |
105 | ||
8bb4bdeb XL |
106 | #[stable(feature = "collection_debug", since = "1.17.0")] |
107 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for IterMut<'a, T> { | |
108 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
109 | f.debug_tuple("IterMut") | |
cc61c64b XL |
110 | .field(&self.list) |
111 | .field(&self.len) | |
8bb4bdeb XL |
112 | .finish() |
113 | } | |
114 | } | |
115 | ||
cc61c64b XL |
116 | /// An owning iterator over the elements of a `LinkedList`. |
117 | /// | |
118 | /// This `struct` is created by the [`into_iter`] method on [`LinkedList`][`LinkedList`] | |
119 | /// (provided by the `IntoIterator` trait). See its documentation for more. | |
120 | /// | |
121 | /// [`into_iter`]: struct.LinkedList.html#method.into_iter | |
122 | /// [`LinkedList`]: struct.LinkedList.html | |
1a4d82fc | 123 | #[derive(Clone)] |
85aaf69f | 124 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 125 | pub struct IntoIter<T> { |
92a42be0 | 126 | list: LinkedList<T>, |
1a4d82fc JJ |
127 | } |
128 | ||
8bb4bdeb XL |
129 | #[stable(feature = "collection_debug", since = "1.17.0")] |
130 | impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { | |
131 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
132 | f.debug_tuple("IntoIter") | |
cc61c64b | 133 | .field(&self.list) |
8bb4bdeb XL |
134 | .finish() |
135 | } | |
136 | } | |
137 | ||
1a4d82fc | 138 | impl<T> Node<T> { |
5bcae85e | 139 | fn new(element: T) -> Self { |
92a42be0 | 140 | Node { |
92a42be0 | 141 | next: None, |
5bcae85e | 142 | prev: None, |
3b2f2976 | 143 | element, |
92a42be0 | 144 | } |
1a4d82fc | 145 | } |
62682a34 | 146 | |
5bcae85e SL |
147 | fn into_element(self: Box<Self>) -> T { |
148 | self.element | |
62682a34 | 149 | } |
1a4d82fc JJ |
150 | } |
151 | ||
1a4d82fc | 152 | // private methods |
85aaf69f | 153 | impl<T> LinkedList<T> { |
5bcae85e | 154 | /// Adds the given node to the front of the list. |
1a4d82fc | 155 | #[inline] |
5bcae85e SL |
156 | fn push_front_node(&mut self, mut node: Box<Node<T>>) { |
157 | unsafe { | |
158 | node.next = self.head; | |
159 | node.prev = None; | |
2c00a5a8 | 160 | let node = Some(Box::into_raw_non_null(node)); |
5bcae85e SL |
161 | |
162 | match self.head { | |
163 | None => self.tail = node, | |
7cac9316 | 164 | Some(mut head) => head.as_mut().prev = node, |
1a4d82fc | 165 | } |
5bcae85e SL |
166 | |
167 | self.head = node; | |
168 | self.len += 1; | |
1a4d82fc | 169 | } |
1a4d82fc JJ |
170 | } |
171 | ||
5bcae85e | 172 | /// Removes and returns the node at the front of the list. |
1a4d82fc JJ |
173 | #[inline] |
174 | fn pop_front_node(&mut self) -> Option<Box<Node<T>>> { | |
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, | |
7cac9316 | 181 | Some(mut head) => head.as_mut().prev = None, |
1a4d82fc | 182 | } |
5bcae85e SL |
183 | |
184 | self.len -= 1; | |
185 | node | |
1a4d82fc JJ |
186 | }) |
187 | } | |
188 | ||
5bcae85e | 189 | /// Adds the given node to the back of the list. |
1a4d82fc | 190 | #[inline] |
5bcae85e SL |
191 | fn push_back_node(&mut self, mut node: Box<Node<T>>) { |
192 | unsafe { | |
193 | node.next = None; | |
194 | node.prev = self.tail; | |
2c00a5a8 | 195 | let node = Some(Box::into_raw_non_null(node)); |
5bcae85e SL |
196 | |
197 | match self.tail { | |
198 | None => self.head = node, | |
7cac9316 | 199 | Some(mut tail) => tail.as_mut().next = node, |
1a4d82fc | 200 | } |
5bcae85e SL |
201 | |
202 | self.tail = node; | |
203 | self.len += 1; | |
1a4d82fc | 204 | } |
1a4d82fc JJ |
205 | } |
206 | ||
5bcae85e | 207 | /// Removes and returns the node at the back of the list. |
1a4d82fc JJ |
208 | #[inline] |
209 | fn pop_back_node(&mut self) -> Option<Box<Node<T>>> { | |
5bcae85e | 210 | self.tail.map(|node| unsafe { |
7cac9316 | 211 | let node = Box::from_raw(node.as_ptr()); |
5bcae85e SL |
212 | self.tail = node.prev; |
213 | ||
214 | match self.tail { | |
215 | None => self.head = None, | |
7cac9316 | 216 | Some(mut tail) => tail.as_mut().next = None, |
5bcae85e SL |
217 | } |
218 | ||
219 | self.len -= 1; | |
220 | node | |
221 | }) | |
1a4d82fc | 222 | } |
ff7c6d11 XL |
223 | |
224 | /// Unlinks the specified node from the current list. | |
225 | /// | |
226 | /// Warning: this will not check that the provided node belongs to the current list. | |
227 | #[inline] | |
2c00a5a8 | 228 | unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) { |
ff7c6d11 XL |
229 | let node = node.as_mut(); |
230 | ||
231 | match node.prev { | |
232 | Some(mut prev) => prev.as_mut().next = node.next.clone(), | |
233 | // this node is the head node | |
234 | None => self.head = node.next.clone(), | |
235 | }; | |
236 | ||
237 | match node.next { | |
238 | Some(mut next) => next.as_mut().prev = node.prev.clone(), | |
239 | // this node is the tail node | |
240 | None => self.tail = node.prev.clone(), | |
241 | }; | |
242 | ||
243 | self.len -= 1; | |
244 | } | |
1a4d82fc JJ |
245 | } |
246 | ||
85aaf69f SL |
247 | #[stable(feature = "rust1", since = "1.0.0")] |
248 | impl<T> Default for LinkedList<T> { | |
9e0c209e | 249 | /// Creates an empty `LinkedList<T>`. |
1a4d82fc | 250 | #[inline] |
5bcae85e SL |
251 | fn default() -> Self { |
252 | Self::new() | |
92a42be0 | 253 | } |
1a4d82fc JJ |
254 | } |
255 | ||
85aaf69f SL |
256 | impl<T> LinkedList<T> { |
257 | /// Creates an empty `LinkedList`. | |
5bcae85e SL |
258 | /// |
259 | /// # Examples | |
260 | /// | |
261 | /// ``` | |
262 | /// use std::collections::LinkedList; | |
263 | /// | |
264 | /// let list: LinkedList<u32> = LinkedList::new(); | |
265 | /// ``` | |
1a4d82fc | 266 | #[inline] |
85aaf69f | 267 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 268 | pub fn new() -> Self { |
92a42be0 | 269 | LinkedList { |
5bcae85e SL |
270 | head: None, |
271 | tail: None, | |
272 | len: 0, | |
273 | marker: PhantomData, | |
92a42be0 | 274 | } |
1a4d82fc JJ |
275 | } |
276 | ||
85aaf69f | 277 | /// Moves all elements from `other` to the end of the list. |
1a4d82fc | 278 | /// |
85aaf69f SL |
279 | /// This reuses all the nodes from `other` and moves them into `self`. After |
280 | /// this operation, `other` becomes empty. | |
281 | /// | |
282 | /// This operation should compute in O(1) time and O(1) memory. | |
1a4d82fc JJ |
283 | /// |
284 | /// # Examples | |
285 | /// | |
85aaf69f SL |
286 | /// ``` |
287 | /// use std::collections::LinkedList; | |
1a4d82fc | 288 | /// |
5bcae85e SL |
289 | /// let mut list1 = LinkedList::new(); |
290 | /// list1.push_back('a'); | |
1a4d82fc | 291 | /// |
5bcae85e SL |
292 | /// let mut list2 = LinkedList::new(); |
293 | /// list2.push_back('b'); | |
294 | /// list2.push_back('c'); | |
1a4d82fc | 295 | /// |
5bcae85e SL |
296 | /// list1.append(&mut list2); |
297 | /// | |
298 | /// let mut iter = list1.iter(); | |
299 | /// assert_eq!(iter.next(), Some(&'a')); | |
300 | /// assert_eq!(iter.next(), Some(&'b')); | |
301 | /// assert_eq!(iter.next(), Some(&'c')); | |
302 | /// assert!(iter.next().is_none()); | |
303 | /// | |
304 | /// assert!(list2.is_empty()); | |
1a4d82fc | 305 | /// ``` |
c34b1796 | 306 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
307 | pub fn append(&mut self, other: &mut Self) { |
308 | match self.tail { | |
309 | None => mem::swap(self, other), | |
7cac9316 XL |
310 | Some(mut tail) => { |
311 | if let Some(mut other_head) = other.head.take() { | |
32a655c1 | 312 | unsafe { |
7cac9316 XL |
313 | tail.as_mut().next = Some(other_head); |
314 | other_head.as_mut().prev = Some(tail); | |
32a655c1 | 315 | } |
5bcae85e | 316 | |
32a655c1 SL |
317 | self.tail = other.tail.take(); |
318 | self.len += mem::replace(&mut other.len, 0); | |
319 | } | |
320 | } | |
1a4d82fc JJ |
321 | } |
322 | } | |
323 | ||
324 | /// Provides a forward iterator. | |
5bcae85e SL |
325 | /// |
326 | /// # Examples | |
327 | /// | |
328 | /// ``` | |
329 | /// use std::collections::LinkedList; | |
330 | /// | |
331 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
332 | /// | |
333 | /// list.push_back(0); | |
334 | /// list.push_back(1); | |
335 | /// list.push_back(2); | |
336 | /// | |
337 | /// let mut iter = list.iter(); | |
338 | /// assert_eq!(iter.next(), Some(&0)); | |
339 | /// assert_eq!(iter.next(), Some(&1)); | |
340 | /// assert_eq!(iter.next(), Some(&2)); | |
341 | /// assert_eq!(iter.next(), None); | |
342 | /// ``` | |
1a4d82fc | 343 | #[inline] |
85aaf69f | 344 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 345 | pub fn iter(&self) -> Iter<T> { |
92a42be0 | 346 | Iter { |
5bcae85e SL |
347 | head: self.head, |
348 | tail: self.tail, | |
349 | len: self.len, | |
350 | marker: PhantomData, | |
92a42be0 | 351 | } |
1a4d82fc JJ |
352 | } |
353 | ||
354 | /// Provides a forward iterator with mutable references. | |
5bcae85e SL |
355 | /// |
356 | /// # Examples | |
357 | /// | |
358 | /// ``` | |
359 | /// use std::collections::LinkedList; | |
360 | /// | |
361 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
362 | /// | |
363 | /// list.push_back(0); | |
364 | /// list.push_back(1); | |
365 | /// list.push_back(2); | |
366 | /// | |
367 | /// for element in list.iter_mut() { | |
368 | /// *element += 10; | |
369 | /// } | |
370 | /// | |
371 | /// let mut iter = list.iter(); | |
372 | /// assert_eq!(iter.next(), Some(&10)); | |
373 | /// assert_eq!(iter.next(), Some(&11)); | |
374 | /// assert_eq!(iter.next(), Some(&12)); | |
375 | /// assert_eq!(iter.next(), None); | |
376 | /// ``` | |
1a4d82fc | 377 | #[inline] |
85aaf69f | 378 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 379 | pub fn iter_mut(&mut self) -> IterMut<T> { |
62682a34 | 380 | IterMut { |
5bcae85e SL |
381 | head: self.head, |
382 | tail: self.tail, | |
383 | len: self.len, | |
92a42be0 | 384 | list: self, |
1a4d82fc JJ |
385 | } |
386 | } | |
387 | ||
85aaf69f | 388 | /// Returns `true` if the `LinkedList` is empty. |
1a4d82fc JJ |
389 | /// |
390 | /// This operation should compute in O(1) time. | |
85aaf69f SL |
391 | /// |
392 | /// # Examples | |
393 | /// | |
394 | /// ``` | |
395 | /// use std::collections::LinkedList; | |
396 | /// | |
397 | /// let mut dl = LinkedList::new(); | |
398 | /// assert!(dl.is_empty()); | |
399 | /// | |
400 | /// dl.push_front("foo"); | |
401 | /// assert!(!dl.is_empty()); | |
402 | /// ``` | |
1a4d82fc | 403 | #[inline] |
85aaf69f | 404 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 405 | pub fn is_empty(&self) -> bool { |
5bcae85e | 406 | self.head.is_none() |
1a4d82fc JJ |
407 | } |
408 | ||
85aaf69f | 409 | /// Returns the length of the `LinkedList`. |
1a4d82fc JJ |
410 | /// |
411 | /// This operation should compute in O(1) time. | |
85aaf69f SL |
412 | /// |
413 | /// # Examples | |
414 | /// | |
415 | /// ``` | |
416 | /// use std::collections::LinkedList; | |
417 | /// | |
418 | /// let mut dl = LinkedList::new(); | |
419 | /// | |
420 | /// dl.push_front(2); | |
421 | /// assert_eq!(dl.len(), 1); | |
422 | /// | |
423 | /// dl.push_front(1); | |
424 | /// assert_eq!(dl.len(), 2); | |
425 | /// | |
426 | /// dl.push_back(3); | |
427 | /// assert_eq!(dl.len(), 3); | |
85aaf69f | 428 | /// ``` |
1a4d82fc | 429 | #[inline] |
85aaf69f SL |
430 | #[stable(feature = "rust1", since = "1.0.0")] |
431 | pub fn len(&self) -> usize { | |
5bcae85e | 432 | self.len |
1a4d82fc JJ |
433 | } |
434 | ||
85aaf69f | 435 | /// Removes all elements from the `LinkedList`. |
1a4d82fc JJ |
436 | /// |
437 | /// This operation should compute in O(n) time. | |
85aaf69f SL |
438 | /// |
439 | /// # Examples | |
440 | /// | |
441 | /// ``` | |
442 | /// use std::collections::LinkedList; | |
443 | /// | |
444 | /// let mut dl = LinkedList::new(); | |
445 | /// | |
446 | /// dl.push_front(2); | |
447 | /// dl.push_front(1); | |
448 | /// assert_eq!(dl.len(), 2); | |
449 | /// assert_eq!(dl.front(), Some(&1)); | |
450 | /// | |
451 | /// dl.clear(); | |
452 | /// assert_eq!(dl.len(), 0); | |
453 | /// assert_eq!(dl.front(), None); | |
85aaf69f | 454 | /// ``` |
1a4d82fc | 455 | #[inline] |
85aaf69f | 456 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 457 | pub fn clear(&mut self) { |
5bcae85e | 458 | *self = Self::new(); |
1a4d82fc JJ |
459 | } |
460 | ||
a7813a04 XL |
461 | /// Returns `true` if the `LinkedList` contains an element equal to the |
462 | /// given value. | |
5bcae85e SL |
463 | /// |
464 | /// # Examples | |
465 | /// | |
466 | /// ``` | |
467 | /// use std::collections::LinkedList; | |
468 | /// | |
469 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
470 | /// | |
471 | /// list.push_back(0); | |
472 | /// list.push_back(1); | |
473 | /// list.push_back(2); | |
474 | /// | |
475 | /// assert_eq!(list.contains(&0), true); | |
476 | /// assert_eq!(list.contains(&10), false); | |
477 | /// ``` | |
478 | #[stable(feature = "linked_list_contains", since = "1.12.0")] | |
a7813a04 XL |
479 | pub fn contains(&self, x: &T) -> bool |
480 | where T: PartialEq<T> | |
481 | { | |
482 | self.iter().any(|e| e == x) | |
483 | } | |
484 | ||
1a4d82fc JJ |
485 | /// Provides a reference to the front element, or `None` if the list is |
486 | /// empty. | |
85aaf69f SL |
487 | /// |
488 | /// # Examples | |
489 | /// | |
490 | /// ``` | |
491 | /// use std::collections::LinkedList; | |
492 | /// | |
493 | /// let mut dl = LinkedList::new(); | |
494 | /// assert_eq!(dl.front(), None); | |
495 | /// | |
496 | /// dl.push_front(1); | |
497 | /// assert_eq!(dl.front(), Some(&1)); | |
85aaf69f | 498 | /// ``` |
1a4d82fc | 499 | #[inline] |
85aaf69f | 500 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 501 | pub fn front(&self) -> Option<&T> { |
7cac9316 XL |
502 | unsafe { |
503 | self.head.as_ref().map(|node| &node.as_ref().element) | |
504 | } | |
1a4d82fc JJ |
505 | } |
506 | ||
507 | /// Provides a mutable reference to the front element, or `None` if the list | |
508 | /// is empty. | |
85aaf69f SL |
509 | /// |
510 | /// # Examples | |
511 | /// | |
512 | /// ``` | |
513 | /// use std::collections::LinkedList; | |
514 | /// | |
515 | /// let mut dl = LinkedList::new(); | |
516 | /// assert_eq!(dl.front(), None); | |
517 | /// | |
518 | /// dl.push_front(1); | |
519 | /// assert_eq!(dl.front(), Some(&1)); | |
520 | /// | |
521 | /// match dl.front_mut() { | |
522 | /// None => {}, | |
523 | /// Some(x) => *x = 5, | |
524 | /// } | |
525 | /// assert_eq!(dl.front(), Some(&5)); | |
85aaf69f | 526 | /// ``` |
1a4d82fc | 527 | #[inline] |
85aaf69f | 528 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 529 | pub fn front_mut(&mut self) -> Option<&mut T> { |
7cac9316 XL |
530 | unsafe { |
531 | self.head.as_mut().map(|node| &mut node.as_mut().element) | |
532 | } | |
1a4d82fc JJ |
533 | } |
534 | ||
535 | /// Provides a reference to the back element, or `None` if the list is | |
536 | /// empty. | |
85aaf69f SL |
537 | /// |
538 | /// # Examples | |
539 | /// | |
540 | /// ``` | |
541 | /// use std::collections::LinkedList; | |
542 | /// | |
543 | /// let mut dl = LinkedList::new(); | |
544 | /// assert_eq!(dl.back(), None); | |
545 | /// | |
546 | /// dl.push_back(1); | |
547 | /// assert_eq!(dl.back(), Some(&1)); | |
85aaf69f | 548 | /// ``` |
1a4d82fc | 549 | #[inline] |
85aaf69f | 550 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 551 | pub fn back(&self) -> Option<&T> { |
7cac9316 XL |
552 | unsafe { |
553 | self.tail.as_ref().map(|node| &node.as_ref().element) | |
554 | } | |
1a4d82fc JJ |
555 | } |
556 | ||
557 | /// Provides a mutable reference to the back element, or `None` if the list | |
558 | /// is empty. | |
85aaf69f SL |
559 | /// |
560 | /// # Examples | |
561 | /// | |
562 | /// ``` | |
563 | /// use std::collections::LinkedList; | |
564 | /// | |
565 | /// let mut dl = LinkedList::new(); | |
566 | /// assert_eq!(dl.back(), None); | |
567 | /// | |
568 | /// dl.push_back(1); | |
569 | /// assert_eq!(dl.back(), Some(&1)); | |
570 | /// | |
571 | /// match dl.back_mut() { | |
572 | /// None => {}, | |
573 | /// Some(x) => *x = 5, | |
574 | /// } | |
575 | /// assert_eq!(dl.back(), Some(&5)); | |
85aaf69f | 576 | /// ``` |
1a4d82fc | 577 | #[inline] |
85aaf69f | 578 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 579 | pub fn back_mut(&mut self) -> Option<&mut T> { |
7cac9316 XL |
580 | unsafe { |
581 | self.tail.as_mut().map(|node| &mut node.as_mut().element) | |
582 | } | |
1a4d82fc JJ |
583 | } |
584 | ||
585 | /// Adds an element first in the list. | |
586 | /// | |
587 | /// This operation should compute in O(1) time. | |
85aaf69f SL |
588 | /// |
589 | /// # Examples | |
590 | /// | |
591 | /// ``` | |
592 | /// use std::collections::LinkedList; | |
593 | /// | |
594 | /// let mut dl = LinkedList::new(); | |
595 | /// | |
596 | /// dl.push_front(2); | |
597 | /// assert_eq!(dl.front().unwrap(), &2); | |
598 | /// | |
599 | /// dl.push_front(1); | |
600 | /// assert_eq!(dl.front().unwrap(), &1); | |
85aaf69f SL |
601 | /// ``` |
602 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 603 | pub fn push_front(&mut self, elt: T) { |
5bcae85e | 604 | self.push_front_node(box Node::new(elt)); |
1a4d82fc JJ |
605 | } |
606 | ||
607 | /// Removes the first element and returns it, or `None` if the list is | |
608 | /// empty. | |
609 | /// | |
610 | /// This operation should compute in O(1) time. | |
85aaf69f SL |
611 | /// |
612 | /// # Examples | |
613 | /// | |
614 | /// ``` | |
615 | /// use std::collections::LinkedList; | |
616 | /// | |
617 | /// let mut d = LinkedList::new(); | |
618 | /// assert_eq!(d.pop_front(), None); | |
619 | /// | |
620 | /// d.push_front(1); | |
621 | /// d.push_front(3); | |
622 | /// assert_eq!(d.pop_front(), Some(3)); | |
623 | /// assert_eq!(d.pop_front(), Some(1)); | |
624 | /// assert_eq!(d.pop_front(), None); | |
85aaf69f | 625 | /// ``` |
85aaf69f | 626 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 627 | pub fn pop_front(&mut self) -> Option<T> { |
5bcae85e | 628 | self.pop_front_node().map(Node::into_element) |
1a4d82fc JJ |
629 | } |
630 | ||
631 | /// Appends an element to the back of a list | |
632 | /// | |
633 | /// # Examples | |
634 | /// | |
85aaf69f SL |
635 | /// ``` |
636 | /// use std::collections::LinkedList; | |
1a4d82fc | 637 | /// |
85aaf69f SL |
638 | /// let mut d = LinkedList::new(); |
639 | /// d.push_back(1); | |
1a4d82fc JJ |
640 | /// d.push_back(3); |
641 | /// assert_eq!(3, *d.back().unwrap()); | |
642 | /// ``` | |
85aaf69f | 643 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 644 | pub fn push_back(&mut self, elt: T) { |
5bcae85e | 645 | self.push_back_node(box Node::new(elt)); |
1a4d82fc JJ |
646 | } |
647 | ||
648 | /// Removes the last element from a list and returns it, or `None` if | |
649 | /// it is empty. | |
650 | /// | |
651 | /// # Examples | |
652 | /// | |
85aaf69f SL |
653 | /// ``` |
654 | /// use std::collections::LinkedList; | |
1a4d82fc | 655 | /// |
85aaf69f | 656 | /// let mut d = LinkedList::new(); |
1a4d82fc | 657 | /// assert_eq!(d.pop_back(), None); |
85aaf69f | 658 | /// d.push_back(1); |
1a4d82fc JJ |
659 | /// d.push_back(3); |
660 | /// assert_eq!(d.pop_back(), Some(3)); | |
661 | /// ``` | |
85aaf69f | 662 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 663 | pub fn pop_back(&mut self) -> Option<T> { |
5bcae85e | 664 | self.pop_back_node().map(Node::into_element) |
1a4d82fc | 665 | } |
85aaf69f SL |
666 | |
667 | /// Splits the list into two at the given index. Returns everything after the given index, | |
668 | /// including the index. | |
669 | /// | |
cc61c64b XL |
670 | /// This operation should compute in O(n) time. |
671 | /// | |
85aaf69f SL |
672 | /// # Panics |
673 | /// | |
674 | /// Panics if `at > len`. | |
675 | /// | |
85aaf69f SL |
676 | /// # Examples |
677 | /// | |
678 | /// ``` | |
679 | /// use std::collections::LinkedList; | |
680 | /// | |
681 | /// let mut d = LinkedList::new(); | |
682 | /// | |
683 | /// d.push_front(1); | |
684 | /// d.push_front(2); | |
685 | /// d.push_front(3); | |
686 | /// | |
687 | /// let mut splitted = d.split_off(2); | |
688 | /// | |
689 | /// assert_eq!(splitted.pop_front(), Some(1)); | |
690 | /// assert_eq!(splitted.pop_front(), None); | |
691 | /// ``` | |
692 | #[stable(feature = "rust1", since = "1.0.0")] | |
693 | pub fn split_off(&mut self, at: usize) -> LinkedList<T> { | |
694 | let len = self.len(); | |
695 | assert!(at <= len, "Cannot split off at a nonexistent index"); | |
696 | if at == 0 { | |
5bcae85e | 697 | return mem::replace(self, Self::new()); |
85aaf69f | 698 | } else if at == len { |
5bcae85e | 699 | return Self::new(); |
85aaf69f SL |
700 | } |
701 | ||
702 | // Below, we iterate towards the `i-1`th node, either from the start or the end, | |
703 | // depending on which would be faster. | |
5bcae85e | 704 | let split_node = if at - 1 <= len - 1 - (at - 1) { |
85aaf69f SL |
705 | let mut iter = self.iter_mut(); |
706 | // instead of skipping using .skip() (which creates a new struct), | |
707 | // we skip manually so we can access the head field without | |
708 | // depending on implementation details of Skip | |
709 | for _ in 0..at - 1 { | |
710 | iter.next(); | |
711 | } | |
712 | iter.head | |
92a42be0 | 713 | } else { |
85aaf69f SL |
714 | // better off starting from the end |
715 | let mut iter = self.iter_mut(); | |
716 | for _ in 0..len - 1 - (at - 1) { | |
717 | iter.next_back(); | |
718 | } | |
719 | iter.tail | |
720 | }; | |
721 | ||
62682a34 SL |
722 | // The split node is the new tail node of the first part and owns |
723 | // the head of the second part. | |
5bcae85e | 724 | let second_part_head; |
62682a34 SL |
725 | |
726 | unsafe { | |
7cac9316 XL |
727 | second_part_head = split_node.unwrap().as_mut().next.take(); |
728 | if let Some(mut head) = second_part_head { | |
729 | head.as_mut().prev = None; | |
62682a34 SL |
730 | } |
731 | } | |
732 | ||
733 | let second_part = LinkedList { | |
5bcae85e SL |
734 | head: second_part_head, |
735 | tail: self.tail, | |
736 | len: len - at, | |
737 | marker: PhantomData, | |
85aaf69f SL |
738 | }; |
739 | ||
62682a34 | 740 | // Fix the tail ptr of the first part |
5bcae85e SL |
741 | self.tail = split_node; |
742 | self.len = at; | |
85aaf69f | 743 | |
62682a34 | 744 | second_part |
85aaf69f | 745 | } |
7453a54e | 746 | |
ff7c6d11 XL |
747 | /// Creates an iterator which uses a closure to determine if an element should be removed. |
748 | /// | |
749 | /// If the closure returns true, then the element is removed and yielded. | |
0531ce1d XL |
750 | /// If the closure returns false, the element will remain in the list and will not be yielded |
751 | /// by the iterator. | |
ff7c6d11 XL |
752 | /// |
753 | /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of | |
754 | /// whether you choose to keep or remove it. | |
755 | /// | |
756 | /// # Examples | |
757 | /// | |
758 | /// Splitting a list into evens and odds, reusing the original list: | |
759 | /// | |
760 | /// ``` | |
761 | /// #![feature(drain_filter)] | |
762 | /// use std::collections::LinkedList; | |
763 | /// | |
764 | /// let mut numbers: LinkedList<u32> = LinkedList::new(); | |
765 | /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]); | |
766 | /// | |
767 | /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>(); | |
768 | /// let odds = numbers; | |
769 | /// | |
770 | /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]); | |
771 | /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]); | |
772 | /// ``` | |
773 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
774 | pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<T, F> | |
775 | where F: FnMut(&mut T) -> bool | |
776 | { | |
777 | // avoid borrow issues. | |
778 | let it = self.head; | |
779 | let old_len = self.len; | |
780 | ||
781 | DrainFilter { | |
782 | list: self, | |
783 | it: it, | |
784 | pred: filter, | |
785 | idx: 0, | |
786 | old_len: old_len, | |
787 | } | |
788 | } | |
789 | ||
7453a54e SL |
790 | /// Returns a place for insertion at the front of the list. |
791 | /// | |
cc61c64b XL |
792 | /// Using this method with placement syntax is equivalent to |
793 | /// [`push_front`](#method.push_front), but may be more efficient. | |
7453a54e SL |
794 | /// |
795 | /// # Examples | |
796 | /// | |
797 | /// ``` | |
798 | /// #![feature(collection_placement)] | |
799 | /// #![feature(placement_in_syntax)] | |
800 | /// | |
801 | /// use std::collections::LinkedList; | |
802 | /// | |
803 | /// let mut list = LinkedList::new(); | |
804 | /// list.front_place() <- 2; | |
805 | /// list.front_place() <- 4; | |
806 | /// assert!(list.iter().eq(&[4, 2])); | |
807 | /// ``` | |
808 | #[unstable(feature = "collection_placement", | |
809 | reason = "method name and placement protocol are subject to change", | |
810 | issue = "30172")] | |
811 | pub fn front_place(&mut self) -> FrontPlace<T> { | |
32a655c1 SL |
812 | FrontPlace { |
813 | list: self, | |
814 | node: IntermediateBox::make_place(), | |
815 | } | |
7453a54e SL |
816 | } |
817 | ||
818 | /// Returns a place for insertion at the back of the list. | |
819 | /// | |
820 | /// Using this method with placement syntax is equivalent to [`push_back`](#method.push_back), | |
821 | /// but may be more efficient. | |
822 | /// | |
823 | /// # Examples | |
824 | /// | |
825 | /// ``` | |
826 | /// #![feature(collection_placement)] | |
827 | /// #![feature(placement_in_syntax)] | |
828 | /// | |
829 | /// use std::collections::LinkedList; | |
830 | /// | |
831 | /// let mut list = LinkedList::new(); | |
832 | /// list.back_place() <- 2; | |
833 | /// list.back_place() <- 4; | |
834 | /// assert!(list.iter().eq(&[2, 4])); | |
835 | /// ``` | |
836 | #[unstable(feature = "collection_placement", | |
837 | reason = "method name and placement protocol are subject to change", | |
838 | issue = "30172")] | |
839 | pub fn back_place(&mut self) -> BackPlace<T> { | |
32a655c1 SL |
840 | BackPlace { |
841 | list: self, | |
842 | node: IntermediateBox::make_place(), | |
843 | } | |
7453a54e | 844 | } |
1a4d82fc JJ |
845 | } |
846 | ||
85aaf69f | 847 | #[stable(feature = "rust1", since = "1.0.0")] |
32a655c1 | 848 | unsafe impl<#[may_dangle] T> Drop for LinkedList<T> { |
1a4d82fc | 849 | fn drop(&mut self) { |
5bcae85e | 850 | while let Some(_) = self.pop_front_node() {} |
1a4d82fc JJ |
851 | } |
852 | } | |
853 | ||
85aaf69f | 854 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
855 | impl<'a, T> Iterator for Iter<'a, T> { |
856 | type Item = &'a T; | |
1a4d82fc JJ |
857 | |
858 | #[inline] | |
5bcae85e SL |
859 | fn next(&mut self) -> Option<&'a T> { |
860 | if self.len == 0 { | |
861 | None | |
862 | } else { | |
863 | self.head.map(|node| unsafe { | |
7cac9316 XL |
864 | // Need an unbound lifetime to get 'a |
865 | let node = &*node.as_ptr(); | |
5bcae85e SL |
866 | self.len -= 1; |
867 | self.head = node.next; | |
868 | &node.element | |
869 | }) | |
1a4d82fc | 870 | } |
1a4d82fc JJ |
871 | } |
872 | ||
873 | #[inline] | |
85aaf69f | 874 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 875 | (self.len, Some(self.len)) |
1a4d82fc JJ |
876 | } |
877 | } | |
878 | ||
85aaf69f | 879 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 880 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
1a4d82fc | 881 | #[inline] |
5bcae85e SL |
882 | fn next_back(&mut self) -> Option<&'a T> { |
883 | if self.len == 0 { | |
884 | None | |
885 | } else { | |
886 | self.tail.map(|node| unsafe { | |
7cac9316 XL |
887 | // Need an unbound lifetime to get 'a |
888 | let node = &*node.as_ptr(); | |
5bcae85e SL |
889 | self.len -= 1; |
890 | self.tail = node.prev; | |
891 | &node.element | |
62682a34 SL |
892 | }) |
893 | } | |
1a4d82fc JJ |
894 | } |
895 | } | |
896 | ||
85aaf69f | 897 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 898 | impl<'a, T> ExactSizeIterator for Iter<'a, T> {} |
1a4d82fc | 899 | |
0531ce1d | 900 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e SL |
901 | impl<'a, T> FusedIterator for Iter<'a, T> {} |
902 | ||
85aaf69f | 903 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
904 | impl<'a, T> Iterator for IterMut<'a, T> { |
905 | type Item = &'a mut T; | |
906 | ||
1a4d82fc | 907 | #[inline] |
5bcae85e SL |
908 | fn next(&mut self) -> Option<&'a mut T> { |
909 | if self.len == 0 { | |
910 | None | |
911 | } else { | |
912 | self.head.map(|node| unsafe { | |
7cac9316 XL |
913 | // Need an unbound lifetime to get 'a |
914 | let node = &mut *node.as_ptr(); | |
5bcae85e SL |
915 | self.len -= 1; |
916 | self.head = node.next; | |
917 | &mut node.element | |
62682a34 SL |
918 | }) |
919 | } | |
1a4d82fc JJ |
920 | } |
921 | ||
922 | #[inline] | |
85aaf69f | 923 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 924 | (self.len, Some(self.len)) |
1a4d82fc JJ |
925 | } |
926 | } | |
927 | ||
85aaf69f | 928 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 929 | impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { |
1a4d82fc | 930 | #[inline] |
5bcae85e SL |
931 | fn next_back(&mut self) -> Option<&'a mut T> { |
932 | if self.len == 0 { | |
933 | None | |
934 | } else { | |
935 | self.tail.map(|node| unsafe { | |
7cac9316 XL |
936 | // Need an unbound lifetime to get 'a |
937 | let node = &mut *node.as_ptr(); | |
5bcae85e SL |
938 | self.len -= 1; |
939 | self.tail = node.prev; | |
940 | &mut node.element | |
62682a34 SL |
941 | }) |
942 | } | |
1a4d82fc JJ |
943 | } |
944 | } | |
945 | ||
85aaf69f | 946 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 947 | impl<'a, T> ExactSizeIterator for IterMut<'a, T> {} |
1a4d82fc | 948 | |
0531ce1d | 949 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e SL |
950 | impl<'a, T> FusedIterator for IterMut<'a, T> {} |
951 | ||
5bcae85e SL |
952 | impl<'a, T> IterMut<'a, T> { |
953 | /// Inserts the given element just after the element most recently returned by `.next()`. | |
1a4d82fc JJ |
954 | /// The inserted element does not appear in the iteration. |
955 | /// | |
956 | /// # Examples | |
957 | /// | |
85aaf69f | 958 | /// ``` |
c1a9b12d SL |
959 | /// #![feature(linked_list_extras)] |
960 | /// | |
85aaf69f | 961 | /// use std::collections::LinkedList; |
1a4d82fc | 962 | /// |
85aaf69f | 963 | /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect(); |
1a4d82fc JJ |
964 | /// |
965 | /// { | |
966 | /// let mut it = list.iter_mut(); | |
967 | /// assert_eq!(it.next().unwrap(), &1); | |
968 | /// // insert `2` after `1` | |
969 | /// it.insert_next(2); | |
970 | /// } | |
971 | /// { | |
85aaf69f | 972 | /// let vec: Vec<_> = list.into_iter().collect(); |
c34b1796 | 973 | /// assert_eq!(vec, [1, 2, 3, 4]); |
1a4d82fc JJ |
974 | /// } |
975 | /// ``` | |
976 | #[inline] | |
62682a34 | 977 | #[unstable(feature = "linked_list_extras", |
e9174d1e SL |
978 | reason = "this is probably better handled by a cursor type -- we'll see", |
979 | issue = "27794")] | |
5bcae85e SL |
980 | pub fn insert_next(&mut self, element: T) { |
981 | match self.head { | |
982 | None => self.list.push_back(element), | |
7cac9316 XL |
983 | Some(mut head) => unsafe { |
984 | let mut prev = match head.as_ref().prev { | |
5bcae85e SL |
985 | None => return self.list.push_front(element), |
986 | Some(prev) => prev, | |
987 | }; | |
988 | ||
2c00a5a8 | 989 | let node = Some(Box::into_raw_non_null(box Node { |
5bcae85e SL |
990 | next: Some(head), |
991 | prev: Some(prev), | |
3b2f2976 | 992 | element, |
2c00a5a8 | 993 | })); |
5bcae85e | 994 | |
7cac9316 XL |
995 | prev.as_mut().next = node; |
996 | head.as_mut().prev = node; | |
5bcae85e SL |
997 | |
998 | self.list.len += 1; | |
32a655c1 | 999 | }, |
5bcae85e | 1000 | } |
1a4d82fc JJ |
1001 | } |
1002 | ||
1003 | /// Provides a reference to the next element, without changing the iterator. | |
1004 | /// | |
1005 | /// # Examples | |
1006 | /// | |
85aaf69f | 1007 | /// ``` |
c1a9b12d SL |
1008 | /// #![feature(linked_list_extras)] |
1009 | /// | |
85aaf69f | 1010 | /// use std::collections::LinkedList; |
1a4d82fc | 1011 | /// |
85aaf69f | 1012 | /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect(); |
1a4d82fc JJ |
1013 | /// |
1014 | /// let mut it = list.iter_mut(); | |
1015 | /// assert_eq!(it.next().unwrap(), &1); | |
1016 | /// assert_eq!(it.peek_next().unwrap(), &2); | |
1017 | /// // We just peeked at 2, so it was not consumed from the iterator. | |
1018 | /// assert_eq!(it.next().unwrap(), &2); | |
1019 | /// ``` | |
1020 | #[inline] | |
62682a34 | 1021 | #[unstable(feature = "linked_list_extras", |
e9174d1e SL |
1022 | reason = "this is probably better handled by a cursor type -- we'll see", |
1023 | issue = "27794")] | |
5bcae85e SL |
1024 | pub fn peek_next(&mut self) -> Option<&mut T> { |
1025 | if self.len == 0 { | |
1026 | None | |
1027 | } else { | |
7cac9316 XL |
1028 | unsafe { |
1029 | self.head.as_mut().map(|node| &mut node.as_mut().element) | |
1030 | } | |
62682a34 | 1031 | } |
1a4d82fc JJ |
1032 | } |
1033 | } | |
1034 | ||
ff7c6d11 XL |
1035 | /// An iterator produced by calling `drain_filter` on LinkedList. |
1036 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
1037 | pub struct DrainFilter<'a, T: 'a, F: 'a> | |
1038 | where F: FnMut(&mut T) -> bool, | |
1039 | { | |
1040 | list: &'a mut LinkedList<T>, | |
2c00a5a8 | 1041 | it: Option<NonNull<Node<T>>>, |
ff7c6d11 XL |
1042 | pred: F, |
1043 | idx: usize, | |
1044 | old_len: usize, | |
1045 | } | |
1046 | ||
1047 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
1048 | impl<'a, T, F> Iterator for DrainFilter<'a, T, F> | |
1049 | where F: FnMut(&mut T) -> bool, | |
1050 | { | |
1051 | type Item = T; | |
1052 | ||
1053 | fn next(&mut self) -> Option<T> { | |
1054 | while let Some(mut node) = self.it { | |
1055 | unsafe { | |
1056 | self.it = node.as_ref().next; | |
1057 | self.idx += 1; | |
1058 | ||
1059 | if (self.pred)(&mut node.as_mut().element) { | |
1060 | self.list.unlink_node(node); | |
1061 | return Some(Box::from_raw(node.as_ptr()).element); | |
1062 | } | |
1063 | } | |
1064 | } | |
1065 | ||
1066 | None | |
1067 | } | |
1068 | ||
1069 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1070 | (0, Some(self.old_len - self.idx)) | |
1071 | } | |
1072 | } | |
1073 | ||
1074 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
1075 | impl<'a, T, F> Drop for DrainFilter<'a, T, F> | |
1076 | where F: FnMut(&mut T) -> bool, | |
1077 | { | |
1078 | fn drop(&mut self) { | |
1079 | for _ in self { } | |
1080 | } | |
1081 | } | |
1082 | ||
1083 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
1084 | impl<'a, T: 'a + fmt::Debug, F> fmt::Debug for DrainFilter<'a, T, F> | |
1085 | where F: FnMut(&mut T) -> bool | |
1086 | { | |
1087 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1088 | f.debug_tuple("DrainFilter") | |
1089 | .field(&self.list) | |
1090 | .finish() | |
1091 | } | |
1092 | } | |
1093 | ||
85aaf69f | 1094 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1095 | impl<T> Iterator for IntoIter<T> { |
1096 | type Item = T; | |
1a4d82fc JJ |
1097 | |
1098 | #[inline] | |
5bcae85e | 1099 | fn next(&mut self) -> Option<T> { |
92a42be0 SL |
1100 | self.list.pop_front() |
1101 | } | |
1a4d82fc JJ |
1102 | |
1103 | #[inline] | |
85aaf69f | 1104 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 1105 | (self.list.len, Some(self.list.len)) |
1a4d82fc JJ |
1106 | } |
1107 | } | |
1108 | ||
85aaf69f | 1109 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1110 | impl<T> DoubleEndedIterator for IntoIter<T> { |
1a4d82fc | 1111 | #[inline] |
5bcae85e | 1112 | fn next_back(&mut self) -> Option<T> { |
92a42be0 SL |
1113 | self.list.pop_back() |
1114 | } | |
1a4d82fc JJ |
1115 | } |
1116 | ||
92a42be0 | 1117 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1118 | impl<T> ExactSizeIterator for IntoIter<T> {} |
c34b1796 | 1119 | |
0531ce1d | 1120 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e SL |
1121 | impl<T> FusedIterator for IntoIter<T> {} |
1122 | ||
85aaf69f | 1123 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1124 | impl<T> FromIterator<T> for LinkedList<T> { |
1125 | fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { | |
1126 | let mut list = Self::new(); | |
1127 | list.extend(iter); | |
1128 | list | |
1a4d82fc JJ |
1129 | } |
1130 | } | |
1131 | ||
85aaf69f SL |
1132 | #[stable(feature = "rust1", since = "1.0.0")] |
1133 | impl<T> IntoIterator for LinkedList<T> { | |
1134 | type Item = T; | |
1135 | type IntoIter = IntoIter<T>; | |
1136 | ||
9346a6ac AL |
1137 | /// Consumes the list into an iterator yielding elements by value. |
1138 | #[inline] | |
85aaf69f | 1139 | fn into_iter(self) -> IntoIter<T> { |
92a42be0 | 1140 | IntoIter { list: self } |
85aaf69f SL |
1141 | } |
1142 | } | |
1143 | ||
1144 | #[stable(feature = "rust1", since = "1.0.0")] | |
1145 | impl<'a, T> IntoIterator for &'a LinkedList<T> { | |
1146 | type Item = &'a T; | |
1147 | type IntoIter = Iter<'a, T>; | |
1148 | ||
1149 | fn into_iter(self) -> Iter<'a, T> { | |
1150 | self.iter() | |
1151 | } | |
1152 | } | |
1153 | ||
92a42be0 | 1154 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
1155 | impl<'a, T> IntoIterator for &'a mut LinkedList<T> { |
1156 | type Item = &'a mut T; | |
1157 | type IntoIter = IterMut<'a, T>; | |
1158 | ||
5bcae85e | 1159 | fn into_iter(self) -> IterMut<'a, T> { |
85aaf69f | 1160 | self.iter_mut() |
1a4d82fc JJ |
1161 | } |
1162 | } | |
1163 | ||
85aaf69f | 1164 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1165 | impl<T> Extend<T> for LinkedList<T> { |
1166 | fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { | |
1167 | <Self as SpecExtend<I>>::spec_extend(self, iter); | |
a7813a04 XL |
1168 | } |
1169 | } | |
1170 | ||
1171 | impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> { | |
1172 | default fn spec_extend(&mut self, iter: I) { | |
92a42be0 SL |
1173 | for elt in iter { |
1174 | self.push_back(elt); | |
1175 | } | |
85aaf69f SL |
1176 | } |
1177 | } | |
1178 | ||
a7813a04 XL |
1179 | impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> { |
1180 | fn spec_extend(&mut self, ref mut other: LinkedList<T>) { | |
1181 | self.append(other); | |
1182 | } | |
1183 | } | |
1184 | ||
62682a34 SL |
1185 | #[stable(feature = "extend_ref", since = "1.2.0")] |
1186 | impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> { | |
92a42be0 | 1187 | fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { |
62682a34 SL |
1188 | self.extend(iter.into_iter().cloned()); |
1189 | } | |
1190 | } | |
1191 | ||
85aaf69f | 1192 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1193 | impl<T: PartialEq> PartialEq for LinkedList<T> { |
1194 | fn eq(&self, other: &Self) -> bool { | |
1195 | self.len() == other.len() && self.iter().eq(other) | |
1a4d82fc JJ |
1196 | } |
1197 | ||
5bcae85e SL |
1198 | fn ne(&self, other: &Self) -> bool { |
1199 | self.len() != other.len() || self.iter().ne(other) | |
1a4d82fc JJ |
1200 | } |
1201 | } | |
1202 | ||
85aaf69f | 1203 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1204 | impl<T: Eq> Eq for LinkedList<T> {} |
1a4d82fc | 1205 | |
85aaf69f | 1206 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1207 | impl<T: PartialOrd> PartialOrd for LinkedList<T> { |
1208 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { | |
1209 | self.iter().partial_cmp(other) | |
1a4d82fc JJ |
1210 | } |
1211 | } | |
1212 | ||
85aaf69f | 1213 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1214 | impl<T: Ord> Ord for LinkedList<T> { |
1a4d82fc | 1215 | #[inline] |
5bcae85e SL |
1216 | fn cmp(&self, other: &Self) -> Ordering { |
1217 | self.iter().cmp(other) | |
1a4d82fc JJ |
1218 | } |
1219 | } | |
1220 | ||
85aaf69f | 1221 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1222 | impl<T: Clone> Clone for LinkedList<T> { |
1223 | fn clone(&self) -> Self { | |
85aaf69f | 1224 | self.iter().cloned().collect() |
1a4d82fc JJ |
1225 | } |
1226 | } | |
1227 | ||
85aaf69f | 1228 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1229 | impl<T: fmt::Debug> fmt::Debug for LinkedList<T> { |
1a4d82fc | 1230 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
5bcae85e | 1231 | f.debug_list().entries(self).finish() |
1a4d82fc JJ |
1232 | } |
1233 | } | |
1234 | ||
85aaf69f | 1235 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1236 | impl<T: Hash> Hash for LinkedList<T> { |
85aaf69f SL |
1237 | fn hash<H: Hasher>(&self, state: &mut H) { |
1238 | self.len().hash(state); | |
1239 | for elt in self { | |
1a4d82fc JJ |
1240 | elt.hash(state); |
1241 | } | |
1242 | } | |
1243 | } | |
1244 | ||
7453a54e SL |
1245 | unsafe fn finalize<T>(node: IntermediateBox<Node<T>>) -> Box<Node<T>> { |
1246 | let mut node = node.finalize(); | |
1247 | ptr::write(&mut node.next, None); | |
5bcae85e | 1248 | ptr::write(&mut node.prev, None); |
7453a54e SL |
1249 | node |
1250 | } | |
1251 | ||
1252 | /// A place for insertion at the front of a `LinkedList`. | |
1253 | /// | |
1254 | /// See [`LinkedList::front_place`](struct.LinkedList.html#method.front_place) for details. | |
1255 | #[must_use = "places do nothing unless written to with `<-` syntax"] | |
1256 | #[unstable(feature = "collection_placement", | |
1257 | reason = "struct name and placement protocol are subject to change", | |
1258 | issue = "30172")] | |
1259 | pub struct FrontPlace<'a, T: 'a> { | |
1260 | list: &'a mut LinkedList<T>, | |
1261 | node: IntermediateBox<Node<T>>, | |
1262 | } | |
1263 | ||
8bb4bdeb XL |
1264 | #[unstable(feature = "collection_placement", |
1265 | reason = "struct name and placement protocol are subject to change", | |
1266 | issue = "30172")] | |
1267 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for FrontPlace<'a, T> { | |
1268 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1269 | f.debug_tuple("FrontPlace") | |
cc61c64b | 1270 | .field(&self.list) |
8bb4bdeb XL |
1271 | .finish() |
1272 | } | |
1273 | } | |
1274 | ||
7453a54e SL |
1275 | #[unstable(feature = "collection_placement", |
1276 | reason = "placement protocol is subject to change", | |
1277 | issue = "30172")] | |
1278 | impl<'a, T> Placer<T> for FrontPlace<'a, T> { | |
1279 | type Place = Self; | |
1280 | ||
1281 | fn make_place(self) -> Self { | |
1282 | self | |
1283 | } | |
1284 | } | |
1285 | ||
1286 | #[unstable(feature = "collection_placement", | |
1287 | reason = "placement protocol is subject to change", | |
1288 | issue = "30172")] | |
2c00a5a8 | 1289 | unsafe impl<'a, T> Place<T> for FrontPlace<'a, T> { |
7453a54e | 1290 | fn pointer(&mut self) -> *mut T { |
5bcae85e | 1291 | unsafe { &mut (*self.node.pointer()).element } |
7453a54e SL |
1292 | } |
1293 | } | |
1294 | ||
1295 | #[unstable(feature = "collection_placement", | |
1296 | reason = "placement protocol is subject to change", | |
1297 | issue = "30172")] | |
1298 | impl<'a, T> InPlace<T> for FrontPlace<'a, T> { | |
1299 | type Owner = (); | |
1300 | ||
1301 | unsafe fn finalize(self) { | |
1302 | let FrontPlace { list, node } = self; | |
1303 | list.push_front_node(finalize(node)); | |
1304 | } | |
1305 | } | |
1306 | ||
1307 | /// A place for insertion at the back of a `LinkedList`. | |
1308 | /// | |
1309 | /// See [`LinkedList::back_place`](struct.LinkedList.html#method.back_place) for details. | |
1310 | #[must_use = "places do nothing unless written to with `<-` syntax"] | |
1311 | #[unstable(feature = "collection_placement", | |
1312 | reason = "struct name and placement protocol are subject to change", | |
1313 | issue = "30172")] | |
1314 | pub struct BackPlace<'a, T: 'a> { | |
1315 | list: &'a mut LinkedList<T>, | |
1316 | node: IntermediateBox<Node<T>>, | |
1317 | } | |
1318 | ||
8bb4bdeb XL |
1319 | #[unstable(feature = "collection_placement", |
1320 | reason = "struct name and placement protocol are subject to change", | |
1321 | issue = "30172")] | |
1322 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for BackPlace<'a, T> { | |
1323 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1324 | f.debug_tuple("BackPlace") | |
cc61c64b | 1325 | .field(&self.list) |
8bb4bdeb XL |
1326 | .finish() |
1327 | } | |
1328 | } | |
1329 | ||
7453a54e SL |
1330 | #[unstable(feature = "collection_placement", |
1331 | reason = "placement protocol is subject to change", | |
1332 | issue = "30172")] | |
1333 | impl<'a, T> Placer<T> for BackPlace<'a, T> { | |
1334 | type Place = Self; | |
1335 | ||
1336 | fn make_place(self) -> Self { | |
1337 | self | |
1338 | } | |
1339 | } | |
1340 | ||
1341 | #[unstable(feature = "collection_placement", | |
1342 | reason = "placement protocol is subject to change", | |
1343 | issue = "30172")] | |
2c00a5a8 | 1344 | unsafe impl<'a, T> Place<T> for BackPlace<'a, T> { |
7453a54e | 1345 | fn pointer(&mut self) -> *mut T { |
5bcae85e | 1346 | unsafe { &mut (*self.node.pointer()).element } |
7453a54e SL |
1347 | } |
1348 | } | |
1349 | ||
1350 | #[unstable(feature = "collection_placement", | |
1351 | reason = "placement protocol is subject to change", | |
1352 | issue = "30172")] | |
1353 | impl<'a, T> InPlace<T> for BackPlace<'a, T> { | |
1354 | type Owner = (); | |
1355 | ||
1356 | unsafe fn finalize(self) { | |
1357 | let BackPlace { list, node } = self; | |
1358 | list.push_back_node(finalize(node)); | |
1359 | } | |
1360 | } | |
1361 | ||
9cc50fc6 SL |
1362 | // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters. |
1363 | #[allow(dead_code)] | |
1364 | fn assert_covariance() { | |
32a655c1 SL |
1365 | fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> { |
1366 | x | |
1367 | } | |
1368 | fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> { | |
1369 | x | |
1370 | } | |
1371 | fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> { | |
1372 | x | |
1373 | } | |
9cc50fc6 SL |
1374 | } |
1375 | ||
5bcae85e SL |
1376 | #[stable(feature = "rust1", since = "1.0.0")] |
1377 | unsafe impl<T: Send> Send for LinkedList<T> {} | |
1378 | ||
1379 | #[stable(feature = "rust1", since = "1.0.0")] | |
1380 | unsafe impl<T: Sync> Sync for LinkedList<T> {} | |
1381 | ||
1382 | #[stable(feature = "rust1", since = "1.0.0")] | |
1383 | unsafe impl<'a, T: Sync> Send for Iter<'a, T> {} | |
1384 | ||
1385 | #[stable(feature = "rust1", since = "1.0.0")] | |
1386 | unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {} | |
1387 | ||
1388 | #[stable(feature = "rust1", since = "1.0.0")] | |
1389 | unsafe impl<'a, T: Send> Send for IterMut<'a, T> {} | |
1390 | ||
1391 | #[stable(feature = "rust1", since = "1.0.0")] | |
1392 | unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {} | |
1393 | ||
1a4d82fc | 1394 | #[cfg(test)] |
d9579d0f | 1395 | mod tests { |
85aaf69f | 1396 | use std::thread; |
c34b1796 | 1397 | use std::vec::Vec; |
1a4d82fc | 1398 | |
abe05a73 XL |
1399 | use rand::{thread_rng, Rng}; |
1400 | ||
85aaf69f | 1401 | use super::{LinkedList, Node}; |
1a4d82fc | 1402 | |
c34b1796 AL |
1403 | #[cfg(test)] |
1404 | fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> { | |
1405 | v.iter().cloned().collect() | |
1406 | } | |
1407 | ||
85aaf69f | 1408 | pub fn check_links<T>(list: &LinkedList<T>) { |
5bcae85e SL |
1409 | unsafe { |
1410 | let mut len = 0; | |
1411 | let mut last_ptr: Option<&Node<T>> = None; | |
1412 | let mut node_ptr: &Node<T>; | |
1413 | match list.head { | |
1414 | None => { | |
ff7c6d11 XL |
1415 | // tail node should also be None. |
1416 | assert!(list.tail.is_none()); | |
5bcae85e SL |
1417 | assert_eq!(0, list.len); |
1418 | return; | |
1a4d82fc | 1419 | } |
7cac9316 | 1420 | Some(node) => node_ptr = &*node.as_ptr(), |
1a4d82fc | 1421 | } |
5bcae85e SL |
1422 | loop { |
1423 | match (last_ptr, node_ptr.prev) { | |
1424 | (None, None) => {} | |
1425 | (None, _) => panic!("prev link for head"), | |
1426 | (Some(p), Some(pptr)) => { | |
7cac9316 | 1427 | assert_eq!(p as *const Node<T>, pptr.as_ptr() as *const Node<T>); |
5bcae85e SL |
1428 | } |
1429 | _ => panic!("prev link is none, not good"), | |
1a4d82fc | 1430 | } |
5bcae85e SL |
1431 | match node_ptr.next { |
1432 | Some(next) => { | |
1433 | last_ptr = Some(node_ptr); | |
7cac9316 | 1434 | node_ptr = &*next.as_ptr(); |
5bcae85e SL |
1435 | len += 1; |
1436 | } | |
1437 | None => { | |
1438 | len += 1; | |
1439 | break; | |
1440 | } | |
1a4d82fc JJ |
1441 | } |
1442 | } | |
ff7c6d11 XL |
1443 | |
1444 | // verify that the tail node points to the last node. | |
1445 | let tail = list.tail.as_ref().expect("some tail node").as_ref(); | |
1446 | assert_eq!(tail as *const Node<T>, node_ptr as *const Node<T>); | |
1447 | // check that len matches interior links. | |
5bcae85e | 1448 | assert_eq!(len, list.len); |
1a4d82fc | 1449 | } |
1a4d82fc JJ |
1450 | } |
1451 | ||
85aaf69f SL |
1452 | #[test] |
1453 | fn test_append() { | |
1454 | // Empty to empty | |
1455 | { | |
1456 | let mut m = LinkedList::<i32>::new(); | |
1457 | let mut n = LinkedList::new(); | |
1458 | m.append(&mut n); | |
1459 | check_links(&m); | |
1460 | assert_eq!(m.len(), 0); | |
1461 | assert_eq!(n.len(), 0); | |
1462 | } | |
1463 | // Non-empty to empty | |
1464 | { | |
1465 | let mut m = LinkedList::new(); | |
1466 | let mut n = LinkedList::new(); | |
1467 | n.push_back(2); | |
1468 | m.append(&mut n); | |
1469 | check_links(&m); | |
1470 | assert_eq!(m.len(), 1); | |
1471 | assert_eq!(m.pop_back(), Some(2)); | |
1472 | assert_eq!(n.len(), 0); | |
1473 | check_links(&m); | |
1474 | } | |
1475 | // Empty to non-empty | |
1476 | { | |
1477 | let mut m = LinkedList::new(); | |
1478 | let mut n = LinkedList::new(); | |
1479 | m.push_back(2); | |
1480 | m.append(&mut n); | |
1481 | check_links(&m); | |
1482 | assert_eq!(m.len(), 1); | |
1483 | assert_eq!(m.pop_back(), Some(2)); | |
1484 | check_links(&m); | |
1485 | } | |
1486 | ||
1487 | // Non-empty to non-empty | |
92a42be0 SL |
1488 | let v = vec![1, 2, 3, 4, 5]; |
1489 | let u = vec![9, 8, 1, 2, 3, 4, 5]; | |
85aaf69f SL |
1490 | let mut m = list_from(&v); |
1491 | let mut n = list_from(&u); | |
1492 | m.append(&mut n); | |
1493 | check_links(&m); | |
1494 | let mut sum = v; | |
54a0048b | 1495 | sum.extend_from_slice(&u); |
85aaf69f SL |
1496 | assert_eq!(sum.len(), m.len()); |
1497 | for elt in sum { | |
1498 | assert_eq!(m.pop_front(), Some(elt)) | |
1499 | } | |
1500 | assert_eq!(n.len(), 0); | |
1501 | // let's make sure it's working properly, since we | |
1502 | // did some direct changes to private members | |
1503 | n.push_back(3); | |
1504 | assert_eq!(n.len(), 1); | |
1505 | assert_eq!(n.pop_front(), Some(3)); | |
1506 | check_links(&n); | |
1507 | } | |
1508 | ||
1a4d82fc JJ |
1509 | #[test] |
1510 | fn test_insert_prev() { | |
92a42be0 | 1511 | let mut m = list_from(&[0, 2, 4, 6, 8]); |
1a4d82fc JJ |
1512 | let len = m.len(); |
1513 | { | |
1514 | let mut it = m.iter_mut(); | |
1515 | it.insert_next(-2); | |
1516 | loop { | |
1517 | match it.next() { | |
1518 | None => break, | |
1519 | Some(elt) => { | |
1520 | it.insert_next(*elt + 1); | |
1521 | match it.peek_next() { | |
1522 | Some(x) => assert_eq!(*x, *elt + 2), | |
1523 | None => assert_eq!(8, *elt), | |
1524 | } | |
1525 | } | |
1526 | } | |
1527 | } | |
1528 | it.insert_next(0); | |
1529 | it.insert_next(1); | |
1530 | } | |
1531 | check_links(&m); | |
1532 | assert_eq!(m.len(), 3 + len * 2); | |
92a42be0 SL |
1533 | assert_eq!(m.into_iter().collect::<Vec<_>>(), |
1534 | [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]); | |
1a4d82fc JJ |
1535 | } |
1536 | ||
1537 | #[test] | |
c30ab7b3 | 1538 | #[cfg_attr(target_os = "emscripten", ignore)] |
1a4d82fc | 1539 | fn test_send() { |
92a42be0 | 1540 | let n = list_from(&[1, 2, 3]); |
85aaf69f | 1541 | thread::spawn(move || { |
32a655c1 SL |
1542 | check_links(&n); |
1543 | let a: &[_] = &[&1, &2, &3]; | |
cc61c64b | 1544 | assert_eq!(a, &*n.iter().collect::<Vec<_>>()); |
32a655c1 | 1545 | }) |
92a42be0 SL |
1546 | .join() |
1547 | .ok() | |
1548 | .unwrap(); | |
1a4d82fc JJ |
1549 | } |
1550 | ||
1a4d82fc JJ |
1551 | #[test] |
1552 | fn test_fuzz() { | |
85aaf69f | 1553 | for _ in 0..25 { |
1a4d82fc JJ |
1554 | fuzz_test(3); |
1555 | fuzz_test(16); | |
1556 | fuzz_test(189); | |
1557 | } | |
1558 | } | |
1559 | ||
d9579d0f AL |
1560 | #[test] |
1561 | fn test_26021() { | |
d9579d0f AL |
1562 | // There was a bug in split_off that failed to null out the RHS's head's prev ptr. |
1563 | // This caused the RHS's dtor to walk up into the LHS at drop and delete all of | |
1564 | // its nodes. | |
1565 | // | |
1566 | // https://github.com/rust-lang/rust/issues/26021 | |
1567 | let mut v1 = LinkedList::new(); | |
54a0048b SL |
1568 | v1.push_front(1); |
1569 | v1.push_front(1); | |
1570 | v1.push_front(1); | |
1571 | v1.push_front(1); | |
d9579d0f AL |
1572 | let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption |
1573 | assert_eq!(v1.len(), 3); | |
1574 | ||
1575 | assert_eq!(v1.iter().len(), 3); | |
1576 | assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3); | |
1577 | } | |
1578 | ||
62682a34 SL |
1579 | #[test] |
1580 | fn test_split_off() { | |
1581 | let mut v1 = LinkedList::new(); | |
54a0048b SL |
1582 | v1.push_front(1); |
1583 | v1.push_front(1); | |
1584 | v1.push_front(1); | |
1585 | v1.push_front(1); | |
62682a34 SL |
1586 | |
1587 | // test all splits | |
1588 | for ix in 0..1 + v1.len() { | |
1589 | let mut a = v1.clone(); | |
1590 | let b = a.split_off(ix); | |
1591 | check_links(&a); | |
1592 | check_links(&b); | |
1593 | a.extend(b); | |
1594 | assert_eq!(v1, a); | |
1595 | } | |
1596 | } | |
1597 | ||
1a4d82fc | 1598 | #[cfg(test)] |
85aaf69f SL |
1599 | fn fuzz_test(sz: i32) { |
1600 | let mut m: LinkedList<_> = LinkedList::new(); | |
1a4d82fc | 1601 | let mut v = vec![]; |
85aaf69f | 1602 | for i in 0..sz { |
1a4d82fc | 1603 | check_links(&m); |
9346a6ac | 1604 | let r: u8 = thread_rng().next_u32() as u8; |
1a4d82fc JJ |
1605 | match r % 6 { |
1606 | 0 => { | |
1607 | m.pop_back(); | |
1608 | v.pop(); | |
1609 | } | |
1610 | 1 => { | |
1611 | if !v.is_empty() { | |
1612 | m.pop_front(); | |
1613 | v.remove(0); | |
1614 | } | |
1615 | } | |
92a42be0 | 1616 | 2 | 4 => { |
1a4d82fc JJ |
1617 | m.push_front(-i); |
1618 | v.insert(0, -i); | |
1619 | } | |
1620 | 3 | 5 | _ => { | |
1621 | m.push_back(i); | |
1622 | v.push(i); | |
1623 | } | |
1624 | } | |
1625 | } | |
1626 | ||
1627 | check_links(&m); | |
1628 | ||
85aaf69f | 1629 | let mut i = 0; |
62682a34 | 1630 | for (a, &b) in m.into_iter().zip(&v) { |
1a4d82fc JJ |
1631 | i += 1; |
1632 | assert_eq!(a, b); | |
1633 | } | |
1634 | assert_eq!(i, v.len()); | |
1635 | } | |
ff7c6d11 XL |
1636 | |
1637 | #[test] | |
1638 | fn drain_filter_test() { | |
1639 | let mut m: LinkedList<u32> = LinkedList::new(); | |
1640 | m.extend(&[1, 2, 3, 4, 5, 6]); | |
1641 | let deleted = m.drain_filter(|v| *v < 4).collect::<Vec<_>>(); | |
1642 | ||
1643 | check_links(&m); | |
1644 | ||
1645 | assert_eq!(deleted, &[1, 2, 3]); | |
1646 | assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]); | |
1647 | } | |
1648 | ||
1649 | #[test] | |
1650 | fn drain_to_empty_test() { | |
1651 | let mut m: LinkedList<u32> = LinkedList::new(); | |
1652 | m.extend(&[1, 2, 3, 4, 5, 6]); | |
1653 | let deleted = m.drain_filter(|_| true).collect::<Vec<_>>(); | |
1654 | ||
1655 | check_links(&m); | |
1656 | ||
1657 | assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]); | |
1658 | assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]); | |
1659 | } | |
1a4d82fc | 1660 | } |