1 #![warn(rust_2018_idioms)]
2
3 use slab::*;
4
5 use std::panic::{catch_unwind, resume_unwind, AssertUnwindSafe};
6
7 #[test]
insert_get_remove_one()8 fn insert_get_remove_one() {
9 let mut slab = Slab::new();
10 assert!(slab.is_empty());
11
12 let key = slab.insert(10);
13
14 assert_eq!(slab[key], 10);
15 assert_eq!(slab.get(key), Some(&10));
16 assert!(!slab.is_empty());
17 assert!(slab.contains(key));
18
19 assert_eq!(slab.remove(key), 10);
20 assert!(!slab.contains(key));
21 assert!(slab.get(key).is_none());
22 }
23
24 #[test]
insert_get_many()25 fn insert_get_many() {
26 let mut slab = Slab::with_capacity(10);
27
28 for i in 0..10 {
29 let key = slab.insert(i + 10);
30 assert_eq!(slab[key], i + 10);
31 }
32
33 assert_eq!(slab.capacity(), 10);
34
35 // Storing another one grows the slab
36 let key = slab.insert(20);
37 assert_eq!(slab[key], 20);
38
39 // Capacity grows by 2x
40 assert_eq!(slab.capacity(), 20);
41 }
42
43 #[test]
insert_get_remove_many()44 fn insert_get_remove_many() {
45 let mut slab = Slab::with_capacity(10);
46 let mut keys = vec![];
47
48 for i in 0..10 {
49 for j in 0..10 {
50 let val = (i * 10) + j;
51
52 let key = slab.insert(val);
53 keys.push((key, val));
54 assert_eq!(slab[key], val);
55 }
56
57 for (key, val) in keys.drain(..) {
58 assert_eq!(val, slab.remove(key));
59 }
60 }
61
62 assert_eq!(10, slab.capacity());
63 }
64
65 #[test]
insert_with_vacant_entry()66 fn insert_with_vacant_entry() {
67 let mut slab = Slab::with_capacity(1);
68 let key;
69
70 {
71 let entry = slab.vacant_entry();
72 key = entry.key();
73 entry.insert(123);
74 }
75
76 assert_eq!(123, slab[key]);
77 }
78
79 #[test]
get_vacant_entry_without_using()80 fn get_vacant_entry_without_using() {
81 let mut slab = Slab::<usize>::with_capacity(1);
82 let key = slab.vacant_entry().key();
83 assert_eq!(key, slab.vacant_entry().key());
84 }
85
86 #[test]
87 #[should_panic(expected = "invalid key")]
invalid_get_panics()88 fn invalid_get_panics() {
89 let slab = Slab::<usize>::with_capacity(1);
90 let _ = &slab[0];
91 }
92
93 #[test]
94 #[should_panic(expected = "invalid key")]
invalid_get_mut_panics()95 fn invalid_get_mut_panics() {
96 let mut slab = Slab::<usize>::new();
97 let _ = &mut slab[0];
98 }
99
100 #[test]
101 #[should_panic(expected = "invalid key")]
double_remove_panics()102 fn double_remove_panics() {
103 let mut slab = Slab::<usize>::with_capacity(1);
104 let key = slab.insert(123);
105 slab.remove(key);
106 slab.remove(key);
107 }
108
109 #[test]
110 #[should_panic(expected = "invalid key")]
invalid_remove_panics()111 fn invalid_remove_panics() {
112 let mut slab = Slab::<usize>::with_capacity(1);
113 slab.remove(0);
114 }
115
116 #[test]
slab_get_mut()117 fn slab_get_mut() {
118 let mut slab = Slab::new();
119 let key = slab.insert(1);
120
121 slab[key] = 2;
122 assert_eq!(slab[key], 2);
123
124 *slab.get_mut(key).unwrap() = 3;
125 assert_eq!(slab[key], 3);
126 }
127
128 #[test]
key_of_tagged()129 fn key_of_tagged() {
130 let mut slab = Slab::new();
131 slab.insert(0);
132 assert_eq!(slab.key_of(&slab[0]), 0);
133 }
134
135 #[test]
key_of_layout_optimizable()136 fn key_of_layout_optimizable() {
137 // Entry<&str> doesn't need a discriminant tag because it can use the
138 // nonzero-ness of ptr and store Vacant's next at the same offset as len
139 let mut slab = Slab::new();
140 slab.insert("foo");
141 slab.insert("bar");
142 let third = slab.insert("baz");
143 slab.insert("quux");
144 assert_eq!(slab.key_of(&slab[third]), third);
145 }
146
147 #[test]
key_of_zst()148 fn key_of_zst() {
149 let mut slab = Slab::new();
150 slab.insert(());
151 let second = slab.insert(());
152 slab.insert(());
153 assert_eq!(slab.key_of(&slab[second]), second);
154 }
155
156 #[test]
reserve_does_not_allocate_if_available()157 fn reserve_does_not_allocate_if_available() {
158 let mut slab = Slab::with_capacity(10);
159 let mut keys = vec![];
160
161 for i in 0..6 {
162 keys.push(slab.insert(i));
163 }
164
165 for key in 0..4 {
166 slab.remove(key);
167 }
168
169 assert!(slab.capacity() - slab.len() == 8);
170
171 slab.reserve(8);
172 assert_eq!(10, slab.capacity());
173 }
174
175 #[test]
reserve_exact_does_not_allocate_if_available()176 fn reserve_exact_does_not_allocate_if_available() {
177 let mut slab = Slab::with_capacity(10);
178 let mut keys = vec![];
179
180 for i in 0..6 {
181 keys.push(slab.insert(i));
182 }
183
184 for key in 0..4 {
185 slab.remove(key);
186 }
187
188 assert!(slab.capacity() - slab.len() == 8);
189
190 slab.reserve_exact(8);
191 assert_eq!(10, slab.capacity());
192 }
193
194 #[test]
195 #[should_panic(expected = "capacity overflow")]
reserve_does_panic_with_capacity_overflow()196 fn reserve_does_panic_with_capacity_overflow() {
197 let mut slab = Slab::with_capacity(10);
198 slab.insert(true);
199 slab.reserve(std::isize::MAX as usize);
200 }
201
202 #[test]
203 #[should_panic(expected = "capacity overflow")]
reserve_does_panic_with_capacity_overflow_bytes()204 fn reserve_does_panic_with_capacity_overflow_bytes() {
205 let mut slab = Slab::with_capacity(10);
206 slab.insert(1u16);
207 slab.reserve((std::isize::MAX as usize) / 2);
208 }
209
210 #[test]
211 #[should_panic(expected = "capacity overflow")]
reserve_exact_does_panic_with_capacity_overflow()212 fn reserve_exact_does_panic_with_capacity_overflow() {
213 let mut slab = Slab::with_capacity(10);
214 slab.insert(true);
215 slab.reserve_exact(std::isize::MAX as usize);
216 }
217
218 #[test]
retain()219 fn retain() {
220 let mut slab = Slab::with_capacity(2);
221
222 let key1 = slab.insert(0);
223 let key2 = slab.insert(1);
224
225 slab.retain(|key, x| {
226 assert_eq!(key, *x);
227 *x % 2 == 0
228 });
229
230 assert_eq!(slab.len(), 1);
231 assert_eq!(slab[key1], 0);
232 assert!(!slab.contains(key2));
233
234 // Ensure consistency is retained
235 let key = slab.insert(123);
236 assert_eq!(key, key2);
237
238 assert_eq!(2, slab.len());
239 assert_eq!(2, slab.capacity());
240
241 // Inserting another element grows
242 let key = slab.insert(345);
243 assert_eq!(key, 2);
244
245 assert_eq!(4, slab.capacity());
246 }
247
248 #[test]
into_iter()249 fn into_iter() {
250 let mut slab = Slab::new();
251
252 for i in 0..8 {
253 slab.insert(i);
254 }
255 slab.remove(0);
256 slab.remove(4);
257 slab.remove(5);
258 slab.remove(7);
259
260 let vals: Vec<_> = slab
261 .into_iter()
262 .inspect(|&(key, val)| assert_eq!(key, val))
263 .map(|(_, val)| val)
264 .collect();
265 assert_eq!(vals, vec![1, 2, 3, 6]);
266 }
267
268 #[test]
into_iter_rev()269 fn into_iter_rev() {
270 let mut slab = Slab::new();
271
272 for i in 0..4 {
273 slab.insert(i);
274 }
275
276 let mut iter = slab.into_iter();
277 assert_eq!(iter.next_back(), Some((3, 3)));
278 assert_eq!(iter.next_back(), Some((2, 2)));
279 assert_eq!(iter.next(), Some((0, 0)));
280 assert_eq!(iter.next_back(), Some((1, 1)));
281 assert_eq!(iter.next_back(), None);
282 assert_eq!(iter.next(), None);
283 }
284
285 #[test]
iter()286 fn iter() {
287 let mut slab = Slab::new();
288
289 for i in 0..4 {
290 slab.insert(i);
291 }
292
293 let vals: Vec<_> = slab
294 .iter()
295 .enumerate()
296 .map(|(i, (key, val))| {
297 assert_eq!(i, key);
298 *val
299 })
300 .collect();
301 assert_eq!(vals, vec![0, 1, 2, 3]);
302
303 slab.remove(1);
304
305 let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
306 assert_eq!(vals, vec![0, 2, 3]);
307 }
308
309 #[test]
iter_rev()310 fn iter_rev() {
311 let mut slab = Slab::new();
312
313 for i in 0..4 {
314 slab.insert(i);
315 }
316 slab.remove(0);
317
318 let vals = slab.iter().rev().collect::<Vec<_>>();
319 assert_eq!(vals, vec![(3, &3), (2, &2), (1, &1)]);
320 }
321
322 #[test]
iter_mut()323 fn iter_mut() {
324 let mut slab = Slab::new();
325
326 for i in 0..4 {
327 slab.insert(i);
328 }
329
330 for (i, (key, e)) in slab.iter_mut().enumerate() {
331 assert_eq!(i, key);
332 *e += 1;
333 }
334
335 let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
336 assert_eq!(vals, vec![1, 2, 3, 4]);
337
338 slab.remove(2);
339
340 for (_, e) in slab.iter_mut() {
341 *e += 1;
342 }
343
344 let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
345 assert_eq!(vals, vec![2, 3, 5]);
346 }
347
348 #[test]
iter_mut_rev()349 fn iter_mut_rev() {
350 let mut slab = Slab::new();
351
352 for i in 0..4 {
353 slab.insert(i);
354 }
355 slab.remove(2);
356
357 {
358 let mut iter = slab.iter_mut();
359 assert_eq!(iter.next(), Some((0, &mut 0)));
360 let mut prev_key = !0;
361 for (key, e) in iter.rev() {
362 *e += 10;
363 assert!(prev_key > key);
364 prev_key = key;
365 }
366 }
367
368 assert_eq!(slab[0], 0);
369 assert_eq!(slab[1], 11);
370 assert_eq!(slab[3], 13);
371 assert!(!slab.contains(2));
372 }
373
374 #[test]
from_iterator_sorted()375 fn from_iterator_sorted() {
376 let mut slab = (0..5).map(|i| (i, i)).collect::<Slab<_>>();
377 assert_eq!(slab.len(), 5);
378 assert_eq!(slab[0], 0);
379 assert_eq!(slab[2], 2);
380 assert_eq!(slab[4], 4);
381 assert_eq!(slab.vacant_entry().key(), 5);
382 }
383
384 #[test]
from_iterator_new_in_order()385 fn from_iterator_new_in_order() {
386 // all new keys come in increasing order, but existing keys are overwritten
387 let mut slab = [(0, 'a'), (1, 'a'), (1, 'b'), (0, 'b'), (9, 'a'), (0, 'c')]
388 .iter()
389 .cloned()
390 .collect::<Slab<_>>();
391 assert_eq!(slab.len(), 3);
392 assert_eq!(slab[0], 'c');
393 assert_eq!(slab[1], 'b');
394 assert_eq!(slab[9], 'a');
395 assert_eq!(slab.get(5), None);
396 assert_eq!(slab.vacant_entry().key(), 8);
397 }
398
399 #[test]
from_iterator_unordered()400 fn from_iterator_unordered() {
401 let mut slab = vec![(1, "one"), (50, "fifty"), (3, "three"), (20, "twenty")]
402 .into_iter()
403 .collect::<Slab<_>>();
404 assert_eq!(slab.len(), 4);
405 assert_eq!(slab.vacant_entry().key(), 0);
406 let mut iter = slab.iter();
407 assert_eq!(iter.next(), Some((1, &"one")));
408 assert_eq!(iter.next(), Some((3, &"three")));
409 assert_eq!(iter.next(), Some((20, &"twenty")));
410 assert_eq!(iter.next(), Some((50, &"fifty")));
411 assert_eq!(iter.next(), None);
412 }
413
414 // https://github.com/tokio-rs/slab/issues/100
415 #[test]
from_iterator_issue_100()416 fn from_iterator_issue_100() {
417 let mut slab: slab::Slab<()> = vec![(1, ())].into_iter().collect();
418 assert_eq!(slab.len(), 1);
419 assert_eq!(slab.insert(()), 0);
420 assert_eq!(slab.insert(()), 2);
421 assert_eq!(slab.insert(()), 3);
422
423 let mut slab: slab::Slab<()> = vec![(1, ()), (2, ())].into_iter().collect();
424 assert_eq!(slab.len(), 2);
425 assert_eq!(slab.insert(()), 0);
426 assert_eq!(slab.insert(()), 3);
427 assert_eq!(slab.insert(()), 4);
428
429 let mut slab: slab::Slab<()> = vec![(1, ()), (3, ())].into_iter().collect();
430 assert_eq!(slab.len(), 2);
431 assert_eq!(slab.insert(()), 2);
432 assert_eq!(slab.insert(()), 0);
433 assert_eq!(slab.insert(()), 4);
434
435 let mut slab: slab::Slab<()> = vec![(0, ()), (2, ()), (3, ()), (5, ())]
436 .into_iter()
437 .collect();
438 assert_eq!(slab.len(), 4);
439 assert_eq!(slab.insert(()), 4);
440 assert_eq!(slab.insert(()), 1);
441 assert_eq!(slab.insert(()), 6);
442 }
443
444 #[test]
clear()445 fn clear() {
446 let mut slab = Slab::new();
447
448 for i in 0..4 {
449 slab.insert(i);
450 }
451
452 // clear full
453 slab.clear();
454 assert!(slab.is_empty());
455
456 assert_eq!(0, slab.len());
457 assert_eq!(4, slab.capacity());
458
459 for i in 0..2 {
460 slab.insert(i);
461 }
462
463 let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
464 assert_eq!(vals, vec![0, 1]);
465
466 // clear half-filled
467 slab.clear();
468 assert!(slab.is_empty());
469 }
470
471 #[test]
shrink_to_fit_empty()472 fn shrink_to_fit_empty() {
473 let mut slab = Slab::<bool>::with_capacity(20);
474 slab.shrink_to_fit();
475 assert_eq!(slab.capacity(), 0);
476 }
477
478 #[test]
shrink_to_fit_no_vacant()479 fn shrink_to_fit_no_vacant() {
480 let mut slab = Slab::with_capacity(20);
481 slab.insert(String::new());
482 slab.shrink_to_fit();
483 assert!(slab.capacity() < 10);
484 }
485
486 #[test]
shrink_to_fit_doesnt_move()487 fn shrink_to_fit_doesnt_move() {
488 let mut slab = Slab::with_capacity(8);
489 slab.insert("foo");
490 let bar = slab.insert("bar");
491 slab.insert("baz");
492 let quux = slab.insert("quux");
493 slab.remove(quux);
494 slab.remove(bar);
495 slab.shrink_to_fit();
496 assert_eq!(slab.len(), 2);
497 assert!(slab.capacity() >= 3);
498 assert_eq!(slab.get(0), Some(&"foo"));
499 assert_eq!(slab.get(2), Some(&"baz"));
500 assert_eq!(slab.vacant_entry().key(), bar);
501 }
502
503 #[test]
shrink_to_fit_doesnt_recreate_list_when_nothing_can_be_done()504 fn shrink_to_fit_doesnt_recreate_list_when_nothing_can_be_done() {
505 let mut slab = Slab::with_capacity(16);
506 for i in 0..4 {
507 slab.insert(Box::new(i));
508 }
509 slab.remove(0);
510 slab.remove(2);
511 slab.remove(1);
512 assert_eq!(slab.vacant_entry().key(), 1);
513 slab.shrink_to_fit();
514 assert_eq!(slab.len(), 1);
515 assert!(slab.capacity() >= 4);
516 assert_eq!(slab.vacant_entry().key(), 1);
517 }
518
519 #[test]
compact_empty()520 fn compact_empty() {
521 let mut slab = Slab::new();
522 slab.compact(|_, _, _| panic!());
523 assert_eq!(slab.len(), 0);
524 assert_eq!(slab.capacity(), 0);
525 slab.reserve(20);
526 slab.compact(|_, _, _| panic!());
527 assert_eq!(slab.len(), 0);
528 assert_eq!(slab.capacity(), 0);
529 slab.insert(0);
530 slab.insert(1);
531 slab.insert(2);
532 slab.remove(1);
533 slab.remove(2);
534 slab.remove(0);
535 slab.compact(|_, _, _| panic!());
536 assert_eq!(slab.len(), 0);
537 assert_eq!(slab.capacity(), 0);
538 }
539
540 #[test]
compact_no_moves_needed()541 fn compact_no_moves_needed() {
542 let mut slab = Slab::new();
543 for i in 0..10 {
544 slab.insert(i);
545 }
546 slab.remove(8);
547 slab.remove(9);
548 slab.remove(6);
549 slab.remove(7);
550 slab.compact(|_, _, _| panic!());
551 assert_eq!(slab.len(), 6);
552 for ((index, &value), want) in slab.iter().zip(0..6) {
553 assert!(index == value);
554 assert_eq!(index, want);
555 }
556 assert!(slab.capacity() >= 6 && slab.capacity() < 10);
557 }
558
559 #[test]
compact_moves_successfully()560 fn compact_moves_successfully() {
561 let mut slab = Slab::with_capacity(20);
562 for i in 0..10 {
563 slab.insert(i);
564 }
565 for &i in &[0, 5, 9, 6, 3] {
566 slab.remove(i);
567 }
568 let mut moved = 0;
569 slab.compact(|&mut v, from, to| {
570 assert!(from > to);
571 assert!(from >= 5);
572 assert!(to < 5);
573 assert_eq!(from, v);
574 moved += 1;
575 true
576 });
577 assert_eq!(slab.len(), 5);
578 assert_eq!(moved, 2);
579 assert_eq!(slab.vacant_entry().key(), 5);
580 assert!(slab.capacity() >= 5 && slab.capacity() < 20);
581 let mut iter = slab.iter();
582 assert_eq!(iter.next(), Some((0, &8)));
583 assert_eq!(iter.next(), Some((1, &1)));
584 assert_eq!(iter.next(), Some((2, &2)));
585 assert_eq!(iter.next(), Some((3, &7)));
586 assert_eq!(iter.next(), Some((4, &4)));
587 assert_eq!(iter.next(), None);
588 }
589
590 #[test]
compact_doesnt_move_if_closure_errors()591 fn compact_doesnt_move_if_closure_errors() {
592 let mut slab = Slab::with_capacity(20);
593 for i in 0..10 {
594 slab.insert(i);
595 }
596 for &i in &[9, 3, 1, 4, 0] {
597 slab.remove(i);
598 }
599 slab.compact(|&mut v, from, to| {
600 assert!(from > to);
601 assert_eq!(from, v);
602 v != 6
603 });
604 assert_eq!(slab.len(), 5);
605 assert!(slab.capacity() >= 7 && slab.capacity() < 20);
606 assert_eq!(slab.vacant_entry().key(), 3);
607 let mut iter = slab.iter();
608 assert_eq!(iter.next(), Some((0, &8)));
609 assert_eq!(iter.next(), Some((1, &7)));
610 assert_eq!(iter.next(), Some((2, &2)));
611 assert_eq!(iter.next(), Some((5, &5)));
612 assert_eq!(iter.next(), Some((6, &6)));
613 assert_eq!(iter.next(), None);
614 }
615
616 #[test]
617 // Android aborts on panic and this test relies on stack unwinding.
618 #[cfg(not(target_os = "android"))]
compact_handles_closure_panic()619 fn compact_handles_closure_panic() {
620 let mut slab = Slab::new();
621 for i in 0..10 {
622 slab.insert(i);
623 }
624 for i in 1..6 {
625 slab.remove(i);
626 }
627 let result = catch_unwind(AssertUnwindSafe(|| {
628 slab.compact(|&mut v, from, to| {
629 assert!(from > to);
630 assert_eq!(from, v);
631 if v == 7 {
632 panic!("test");
633 }
634 true
635 })
636 }));
637 match result {
638 Err(ref payload) if payload.downcast_ref() == Some(&"test") => {}
639 Err(bug) => resume_unwind(bug),
640 Ok(()) => unreachable!(),
641 }
642 assert_eq!(slab.len(), 5 - 1);
643 assert_eq!(slab.vacant_entry().key(), 3);
644 let mut iter = slab.iter();
645 assert_eq!(iter.next(), Some((0, &0)));
646 assert_eq!(iter.next(), Some((1, &9)));
647 assert_eq!(iter.next(), Some((2, &8)));
648 assert_eq!(iter.next(), Some((6, &6)));
649 assert_eq!(iter.next(), None);
650 }
651
652 #[test]
fully_consumed_drain()653 fn fully_consumed_drain() {
654 let mut slab = Slab::new();
655
656 for i in 0..3 {
657 slab.insert(i);
658 }
659
660 {
661 let mut drain = slab.drain();
662 assert_eq!(Some(0), drain.next());
663 assert_eq!(Some(1), drain.next());
664 assert_eq!(Some(2), drain.next());
665 assert_eq!(None, drain.next());
666 }
667
668 assert!(slab.is_empty());
669 }
670
671 #[test]
partially_consumed_drain()672 fn partially_consumed_drain() {
673 let mut slab = Slab::new();
674
675 for i in 0..3 {
676 slab.insert(i);
677 }
678
679 {
680 let mut drain = slab.drain();
681 assert_eq!(Some(0), drain.next());
682 }
683
684 assert!(slab.is_empty())
685 }
686
687 #[test]
drain_rev()688 fn drain_rev() {
689 let mut slab = Slab::new();
690 for i in 0..10 {
691 slab.insert(i);
692 }
693 slab.remove(9);
694
695 let vals: Vec<u64> = slab.drain().rev().collect();
696 assert_eq!(vals, (0..9).rev().collect::<Vec<u64>>());
697 }
698
699 #[test]
try_remove()700 fn try_remove() {
701 let mut slab = Slab::new();
702
703 let key = slab.insert(1);
704
705 assert_eq!(slab.try_remove(key), Some(1));
706 assert_eq!(slab.try_remove(key), None);
707 assert_eq!(slab.get(key), None);
708 }
709
710 #[rustversion::since(1.39)]
711 #[test]
const_new()712 fn const_new() {
713 static _SLAB: Slab<()> = Slab::new();
714 }
715
716 #[test]
clone_from()717 fn clone_from() {
718 let mut slab1 = Slab::new();
719 let mut slab2 = Slab::new();
720 for i in 0..5 {
721 slab1.insert(i);
722 slab2.insert(2 * i);
723 slab2.insert(2 * i + 1);
724 }
725 slab1.remove(1);
726 slab1.remove(3);
727 slab2.clone_from(&slab1);
728
729 let mut iter2 = slab2.iter();
730 assert_eq!(iter2.next(), Some((0, &0)));
731 assert_eq!(iter2.next(), Some((2, &2)));
732 assert_eq!(iter2.next(), Some((4, &4)));
733 assert_eq!(iter2.next(), None);
734 assert!(slab2.capacity() >= 10);
735 }
736