]>
Commit | Line | Data |
---|---|---|
416331ca XL |
1 | use super::*; |
2 | ||
ba9703b0 | 3 | use test; |
416331ca XL |
4 | |
5 | #[bench] | |
60c5eb7d | 6 | #[cfg_attr(miri, ignore)] // Miri does not support benchmarks |
416331ca XL |
7 | fn bench_push_back_100(b: &mut test::Bencher) { |
8 | let mut deq = VecDeque::with_capacity(101); | |
9 | b.iter(|| { | |
10 | for i in 0..100 { | |
11 | deq.push_back(i); | |
12 | } | |
13 | deq.head = 0; | |
14 | deq.tail = 0; | |
15 | }) | |
16 | } | |
17 | ||
18 | #[bench] | |
60c5eb7d | 19 | #[cfg_attr(miri, ignore)] // Miri does not support benchmarks |
416331ca XL |
20 | fn bench_push_front_100(b: &mut test::Bencher) { |
21 | let mut deq = VecDeque::with_capacity(101); | |
22 | b.iter(|| { | |
23 | for i in 0..100 { | |
24 | deq.push_front(i); | |
25 | } | |
26 | deq.head = 0; | |
27 | deq.tail = 0; | |
28 | }) | |
29 | } | |
30 | ||
31 | #[bench] | |
60c5eb7d | 32 | #[cfg_attr(miri, ignore)] // Miri does not support benchmarks |
416331ca XL |
33 | fn bench_pop_back_100(b: &mut test::Bencher) { |
34 | let mut deq = VecDeque::<i32>::with_capacity(101); | |
35 | ||
36 | b.iter(|| { | |
37 | deq.head = 100; | |
38 | deq.tail = 0; | |
39 | while !deq.is_empty() { | |
40 | test::black_box(deq.pop_back()); | |
41 | } | |
42 | }) | |
43 | } | |
44 | ||
45 | #[bench] | |
60c5eb7d | 46 | #[cfg_attr(miri, ignore)] // Miri does not support benchmarks |
416331ca XL |
47 | fn bench_pop_front_100(b: &mut test::Bencher) { |
48 | let mut deq = VecDeque::<i32>::with_capacity(101); | |
49 | ||
50 | b.iter(|| { | |
51 | deq.head = 100; | |
52 | deq.tail = 0; | |
53 | while !deq.is_empty() { | |
54 | test::black_box(deq.pop_front()); | |
55 | } | |
56 | }) | |
57 | } | |
58 | ||
59 | #[test] | |
60 | fn test_swap_front_back_remove() { | |
61 | fn test(back: bool) { | |
62 | // This test checks that every single combination of tail position and length is tested. | |
63 | // Capacity 15 should be large enough to cover every case. | |
64 | let mut tester = VecDeque::with_capacity(15); | |
65 | let usable_cap = tester.capacity(); | |
66 | let final_len = usable_cap / 2; | |
67 | ||
68 | for len in 0..final_len { | |
60c5eb7d XL |
69 | let expected: VecDeque<_> = |
70 | if back { (0..len).collect() } else { (0..len).rev().collect() }; | |
416331ca XL |
71 | for tail_pos in 0..usable_cap { |
72 | tester.tail = tail_pos; | |
73 | tester.head = tail_pos; | |
74 | if back { | |
75 | for i in 0..len * 2 { | |
76 | tester.push_front(i); | |
77 | } | |
78 | for i in 0..len { | |
79 | assert_eq!(tester.swap_remove_back(i), Some(len * 2 - 1 - i)); | |
80 | } | |
81 | } else { | |
82 | for i in 0..len * 2 { | |
83 | tester.push_back(i); | |
84 | } | |
85 | for i in 0..len { | |
86 | let idx = tester.len() - 1 - i; | |
87 | assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i)); | |
88 | } | |
89 | } | |
90 | assert!(tester.tail < tester.cap()); | |
91 | assert!(tester.head < tester.cap()); | |
92 | assert_eq!(tester, expected); | |
93 | } | |
94 | } | |
95 | } | |
96 | test(true); | |
97 | test(false); | |
98 | } | |
99 | ||
100 | #[test] | |
101 | fn test_insert() { | |
102 | // This test checks that every single combination of tail position, length, and | |
103 | // insertion position is tested. Capacity 15 should be large enough to cover every case. | |
104 | ||
105 | let mut tester = VecDeque::with_capacity(15); | |
106 | // can't guarantee we got 15, so have to get what we got. | |
107 | // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else | |
108 | // this test isn't covering what it wants to | |
109 | let cap = tester.capacity(); | |
110 | ||
416331ca XL |
111 | // len is the length *after* insertion |
112 | for len in 1..cap { | |
113 | // 0, 1, 2, .., len - 1 | |
114 | let expected = (0..).take(len).collect::<VecDeque<_>>(); | |
115 | for tail_pos in 0..cap { | |
116 | for to_insert in 0..len { | |
117 | tester.tail = tail_pos; | |
118 | tester.head = tail_pos; | |
119 | for i in 0..len { | |
120 | if i != to_insert { | |
121 | tester.push_back(i); | |
122 | } | |
123 | } | |
124 | tester.insert(to_insert, to_insert); | |
125 | assert!(tester.tail < tester.cap()); | |
126 | assert!(tester.head < tester.cap()); | |
127 | assert_eq!(tester, expected); | |
128 | } | |
129 | } | |
130 | } | |
131 | } | |
132 | ||
ba9703b0 XL |
133 | #[test] |
134 | fn make_contiguous_big_tail() { | |
135 | let mut tester = VecDeque::with_capacity(15); | |
136 | ||
137 | for i in 0..3 { | |
138 | tester.push_back(i); | |
139 | } | |
140 | ||
141 | for i in 3..10 { | |
142 | tester.push_front(i); | |
143 | } | |
144 | ||
145 | // 012......9876543 | |
146 | assert_eq!(tester.capacity(), 15); | |
147 | assert_eq!((&[9, 8, 7, 6, 5, 4, 3] as &[_], &[0, 1, 2] as &[_]), tester.as_slices()); | |
148 | ||
149 | let expected_start = tester.head; | |
150 | tester.make_contiguous(); | |
151 | assert_eq!(tester.tail, expected_start); | |
152 | assert_eq!((&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_], &[] as &[_]), tester.as_slices()); | |
153 | } | |
154 | ||
155 | #[test] | |
156 | fn make_contiguous_big_head() { | |
157 | let mut tester = VecDeque::with_capacity(15); | |
158 | ||
159 | for i in 0..8 { | |
160 | tester.push_back(i); | |
161 | } | |
162 | ||
163 | for i in 8..10 { | |
164 | tester.push_front(i); | |
165 | } | |
166 | ||
167 | // 01234567......98 | |
168 | let expected_start = 0; | |
169 | tester.make_contiguous(); | |
170 | assert_eq!(tester.tail, expected_start); | |
171 | assert_eq!((&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_], &[] as &[_]), tester.as_slices()); | |
172 | } | |
173 | ||
174 | #[test] | |
175 | fn make_contiguous_small_free() { | |
176 | let mut tester = VecDeque::with_capacity(15); | |
177 | ||
178 | for i in 'A' as u8..'I' as u8 { | |
179 | tester.push_back(i as char); | |
180 | } | |
181 | ||
182 | for i in 'I' as u8..'N' as u8 { | |
183 | tester.push_front(i as char); | |
184 | } | |
185 | ||
186 | // ABCDEFGH...MLKJI | |
187 | let expected_start = 0; | |
188 | tester.make_contiguous(); | |
189 | assert_eq!(tester.tail, expected_start); | |
190 | assert_eq!( | |
191 | (&['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] as &[_], &[] as &[_]), | |
192 | tester.as_slices() | |
193 | ); | |
194 | ||
195 | tester.clear(); | |
196 | for i in 'I' as u8..'N' as u8 { | |
197 | tester.push_back(i as char); | |
198 | } | |
199 | ||
200 | for i in 'A' as u8..'I' as u8 { | |
201 | tester.push_front(i as char); | |
202 | } | |
203 | ||
204 | // IJKLM...HGFEDCBA | |
205 | let expected_start = 0; | |
206 | tester.make_contiguous(); | |
207 | assert_eq!(tester.tail, expected_start); | |
208 | assert_eq!( | |
209 | (&['H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'J', 'K', 'L', 'M'] as &[_], &[] as &[_]), | |
210 | tester.as_slices() | |
211 | ); | |
212 | } | |
213 | ||
416331ca XL |
214 | #[test] |
215 | fn test_remove() { | |
216 | // This test checks that every single combination of tail position, length, and | |
217 | // removal position is tested. Capacity 15 should be large enough to cover every case. | |
218 | ||
219 | let mut tester = VecDeque::with_capacity(15); | |
220 | // can't guarantee we got 15, so have to get what we got. | |
221 | // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else | |
222 | // this test isn't covering what it wants to | |
223 | let cap = tester.capacity(); | |
224 | ||
225 | // len is the length *after* removal | |
226 | for len in 0..cap - 1 { | |
227 | // 0, 1, 2, .., len - 1 | |
228 | let expected = (0..).take(len).collect::<VecDeque<_>>(); | |
229 | for tail_pos in 0..cap { | |
230 | for to_remove in 0..=len { | |
231 | tester.tail = tail_pos; | |
232 | tester.head = tail_pos; | |
233 | for i in 0..len { | |
234 | if i == to_remove { | |
235 | tester.push_back(1234); | |
236 | } | |
237 | tester.push_back(i); | |
238 | } | |
239 | if to_remove == len { | |
240 | tester.push_back(1234); | |
241 | } | |
242 | tester.remove(to_remove); | |
243 | assert!(tester.tail < tester.cap()); | |
244 | assert!(tester.head < tester.cap()); | |
245 | assert_eq!(tester, expected); | |
246 | } | |
247 | } | |
248 | } | |
249 | } | |
250 | ||
251 | #[test] | |
252 | fn test_drain() { | |
253 | let mut tester: VecDeque<usize> = VecDeque::with_capacity(7); | |
254 | ||
255 | let cap = tester.capacity(); | |
256 | for len in 0..=cap { | |
257 | for tail in 0..=cap { | |
258 | for drain_start in 0..=len { | |
259 | for drain_end in drain_start..=len { | |
260 | tester.tail = tail; | |
261 | tester.head = tail; | |
262 | for i in 0..len { | |
263 | tester.push_back(i); | |
264 | } | |
265 | ||
266 | // Check that we drain the correct values | |
267 | let drained: VecDeque<_> = tester.drain(drain_start..drain_end).collect(); | |
268 | let drained_expected: VecDeque<_> = (drain_start..drain_end).collect(); | |
269 | assert_eq!(drained, drained_expected); | |
270 | ||
271 | // We shouldn't have changed the capacity or made the | |
272 | // head or tail out of bounds | |
273 | assert_eq!(tester.capacity(), cap); | |
274 | assert!(tester.tail < tester.cap()); | |
275 | assert!(tester.head < tester.cap()); | |
276 | ||
277 | // We should see the correct values in the VecDeque | |
60c5eb7d | 278 | let expected: VecDeque<_> = (0..drain_start).chain(drain_end..len).collect(); |
416331ca XL |
279 | assert_eq!(expected, tester); |
280 | } | |
281 | } | |
282 | } | |
283 | } | |
284 | } | |
285 | ||
286 | #[test] | |
287 | fn test_shrink_to_fit() { | |
288 | // This test checks that every single combination of head and tail position, | |
289 | // is tested. Capacity 15 should be large enough to cover every case. | |
290 | ||
291 | let mut tester = VecDeque::with_capacity(15); | |
292 | // can't guarantee we got 15, so have to get what we got. | |
293 | // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else | |
294 | // this test isn't covering what it wants to | |
295 | let cap = tester.capacity(); | |
296 | tester.reserve(63); | |
297 | let max_cap = tester.capacity(); | |
298 | ||
299 | for len in 0..=cap { | |
300 | // 0, 1, 2, .., len - 1 | |
301 | let expected = (0..).take(len).collect::<VecDeque<_>>(); | |
302 | for tail_pos in 0..=max_cap { | |
303 | tester.tail = tail_pos; | |
304 | tester.head = tail_pos; | |
305 | tester.reserve(63); | |
306 | for i in 0..len { | |
307 | tester.push_back(i); | |
308 | } | |
309 | tester.shrink_to_fit(); | |
310 | assert!(tester.capacity() <= cap); | |
311 | assert!(tester.tail < tester.cap()); | |
312 | assert!(tester.head < tester.cap()); | |
313 | assert_eq!(tester, expected); | |
314 | } | |
315 | } | |
316 | } | |
317 | ||
318 | #[test] | |
319 | fn test_split_off() { | |
320 | // This test checks that every single combination of tail position, length, and | |
321 | // split position is tested. Capacity 15 should be large enough to cover every case. | |
322 | ||
323 | let mut tester = VecDeque::with_capacity(15); | |
324 | // can't guarantee we got 15, so have to get what we got. | |
325 | // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else | |
326 | // this test isn't covering what it wants to | |
327 | let cap = tester.capacity(); | |
328 | ||
329 | // len is the length *before* splitting | |
330 | for len in 0..cap { | |
331 | // index to split at | |
332 | for at in 0..=len { | |
333 | // 0, 1, 2, .., at - 1 (may be empty) | |
334 | let expected_self = (0..).take(at).collect::<VecDeque<_>>(); | |
335 | // at, at + 1, .., len - 1 (may be empty) | |
336 | let expected_other = (at..).take(len - at).collect::<VecDeque<_>>(); | |
337 | ||
338 | for tail_pos in 0..cap { | |
339 | tester.tail = tail_pos; | |
340 | tester.head = tail_pos; | |
341 | for i in 0..len { | |
342 | tester.push_back(i); | |
343 | } | |
344 | let result = tester.split_off(at); | |
345 | assert!(tester.tail < tester.cap()); | |
346 | assert!(tester.head < tester.cap()); | |
347 | assert!(result.tail < result.cap()); | |
348 | assert!(result.head < result.cap()); | |
349 | assert_eq!(tester, expected_self); | |
350 | assert_eq!(result, expected_other); | |
351 | } | |
352 | } | |
353 | } | |
354 | } | |
355 | ||
356 | #[test] | |
357 | fn test_from_vec() { | |
358 | use crate::vec::Vec; | |
359 | for cap in 0..35 { | |
360 | for len in 0..=cap { | |
361 | let mut vec = Vec::with_capacity(cap); | |
362 | vec.extend(0..len); | |
363 | ||
364 | let vd = VecDeque::from(vec.clone()); | |
365 | assert!(vd.cap().is_power_of_two()); | |
366 | assert_eq!(vd.len(), vec.len()); | |
367 | assert!(vd.into_iter().eq(vec)); | |
368 | } | |
369 | } | |
370 | } | |
371 | ||
372 | #[test] | |
373 | fn test_vec_from_vecdeque() { | |
374 | use crate::vec::Vec; | |
375 | ||
376 | fn create_vec_and_test_convert(capacity: usize, offset: usize, len: usize) { | |
377 | let mut vd = VecDeque::with_capacity(capacity); | |
378 | for _ in 0..offset { | |
379 | vd.push_back(0); | |
380 | vd.pop_front(); | |
381 | } | |
382 | vd.extend(0..len); | |
383 | ||
384 | let vec: Vec<_> = Vec::from(vd.clone()); | |
385 | assert_eq!(vec.len(), vd.len()); | |
386 | assert!(vec.into_iter().eq(vd)); | |
387 | } | |
388 | ||
389 | #[cfg(not(miri))] // Miri is too slow | |
390 | let max_pwr = 7; | |
391 | #[cfg(miri)] | |
392 | let max_pwr = 5; | |
393 | ||
394 | for cap_pwr in 0..max_pwr { | |
395 | // Make capacity as a (2^x)-1, so that the ring size is 2^x | |
396 | let cap = (2i32.pow(cap_pwr) - 1) as usize; | |
397 | ||
398 | // In these cases there is enough free space to solve it with copies | |
399 | for len in 0..((cap + 1) / 2) { | |
400 | // Test contiguous cases | |
401 | for offset in 0..(cap - len) { | |
402 | create_vec_and_test_convert(cap, offset, len) | |
403 | } | |
404 | ||
405 | // Test cases where block at end of buffer is bigger than block at start | |
406 | for offset in (cap - len)..(cap - (len / 2)) { | |
407 | create_vec_and_test_convert(cap, offset, len) | |
408 | } | |
409 | ||
410 | // Test cases where block at start of buffer is bigger than block at end | |
411 | for offset in (cap - (len / 2))..cap { | |
412 | create_vec_and_test_convert(cap, offset, len) | |
413 | } | |
414 | } | |
415 | ||
416 | // Now there's not (necessarily) space to straighten the ring with simple copies, | |
417 | // the ring will use swapping when: | |
418 | // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len)) | |
419 | // right block size > free space && left block size > free space | |
420 | for len in ((cap + 1) / 2)..cap { | |
421 | // Test contiguous cases | |
422 | for offset in 0..(cap - len) { | |
423 | create_vec_and_test_convert(cap, offset, len) | |
424 | } | |
425 | ||
426 | // Test cases where block at end of buffer is bigger than block at start | |
427 | for offset in (cap - len)..(cap - (len / 2)) { | |
428 | create_vec_and_test_convert(cap, offset, len) | |
429 | } | |
430 | ||
431 | // Test cases where block at start of buffer is bigger than block at end | |
432 | for offset in (cap - (len / 2))..cap { | |
433 | create_vec_and_test_convert(cap, offset, len) | |
434 | } | |
435 | } | |
436 | } | |
437 | } | |
438 | ||
e74abb32 XL |
439 | #[test] |
440 | fn test_clone_from() { | |
441 | let m = vec![1; 8]; | |
442 | let n = vec![2; 12]; | |
443 | for pfv in 0..8 { | |
444 | for pfu in 0..8 { | |
445 | for longer in 0..2 { | |
446 | let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) }; | |
447 | let mut v = VecDeque::from(vr.clone()); | |
448 | for _ in 0..pfv { | |
449 | v.push_front(1); | |
450 | } | |
451 | let mut u = VecDeque::from(ur.clone()); | |
452 | for _ in 0..pfu { | |
453 | u.push_front(2); | |
454 | } | |
455 | v.clone_from(&u); | |
456 | assert_eq!(&v, &u); | |
457 | } | |
458 | } | |
459 | } | |
460 | } | |
461 | ||
60c5eb7d XL |
462 | #[test] |
463 | fn test_vec_deque_truncate_drop() { | |
464 | static mut DROPS: u32 = 0; | |
465 | #[derive(Clone)] | |
466 | struct Elem(i32); | |
467 | impl Drop for Elem { | |
468 | fn drop(&mut self) { | |
469 | unsafe { | |
470 | DROPS += 1; | |
471 | } | |
472 | } | |
473 | } | |
474 | ||
475 | let v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)]; | |
476 | for push_front in 0..=v.len() { | |
477 | let v = v.clone(); | |
478 | let mut tester = VecDeque::with_capacity(5); | |
479 | for (index, elem) in v.into_iter().enumerate() { | |
480 | if index < push_front { | |
481 | tester.push_front(elem); | |
482 | } else { | |
483 | tester.push_back(elem); | |
484 | } | |
485 | } | |
486 | assert_eq!(unsafe { DROPS }, 0); | |
487 | tester.truncate(3); | |
488 | assert_eq!(unsafe { DROPS }, 2); | |
489 | tester.truncate(0); | |
490 | assert_eq!(unsafe { DROPS }, 5); | |
491 | unsafe { | |
492 | DROPS = 0; | |
493 | } | |
494 | } | |
495 | } | |
496 | ||
416331ca XL |
497 | #[test] |
498 | fn issue_53529() { | |
499 | use crate::boxed::Box; | |
500 | ||
501 | let mut dst = VecDeque::new(); | |
502 | dst.push_front(Box::new(1)); | |
503 | dst.push_front(Box::new(2)); | |
504 | assert_eq!(*dst.pop_back().unwrap(), 1); | |
505 | ||
506 | let mut src = VecDeque::new(); | |
507 | src.push_front(Box::new(2)); | |
508 | dst.append(&mut src); | |
509 | for a in dst { | |
510 | assert_eq!(*a, 2); | |
511 | } | |
512 | } |