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