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