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