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