1#![warn(rust_2018_idioms)]
2
3use slab::*;
4
5use std::panic::{catch_unwind, resume_unwind, AssertUnwindSafe};
6
7#[test]
8fn 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]
25fn 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]
44fn 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]
66fn 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]
80fn 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")]
88fn 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")]
95fn 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")]
102fn 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")]
111fn invalid_remove_panics() {
112 let mut slab = Slab::<usize>::with_capacity(1);
113 slab.remove(0);
114}
115
116#[test]
117fn 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]
129fn 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]
136fn 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]
148fn 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]
157fn 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]
176fn 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")]
196fn 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")]
204fn 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")]
212fn 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]
219fn 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]
249fn 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]
269fn 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]
286fn 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]
310fn 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]
323fn 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]
349fn 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]
375fn 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]
385fn 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]
400fn 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]
416fn 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]
445fn 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]
472fn 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]
479fn 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]
487fn 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]
504fn 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]
520fn 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]
541fn 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]
560fn 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]
591fn 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]
617fn compact_handles_closure_panic() {
618 let mut slab = Slab::new();
619 for i in 0..10 {
620 slab.insert(i);
621 }
622 for i in 1..6 {
623 slab.remove(i);
624 }
625 let result = catch_unwind(AssertUnwindSafe(|| {
626 slab.compact(|&mut v, from, to| {
627 assert!(from > to);
628 assert_eq!(from, v);
629 if v == 7 {
630 panic!("test");
631 }
632 true
633 })
634 }));
635 match result {
636 Err(ref payload) if payload.downcast_ref() == Some(&"test") => {}
637 Err(bug) => resume_unwind(bug),
638 Ok(()) => unreachable!(),
639 }
640 assert_eq!(slab.len(), 5 - 1);
641 assert_eq!(slab.vacant_entry().key(), 3);
642 let mut iter = slab.iter();
643 assert_eq!(iter.next(), Some((0, &0)));
644 assert_eq!(iter.next(), Some((1, &9)));
645 assert_eq!(iter.next(), Some((2, &8)));
646 assert_eq!(iter.next(), Some((6, &6)));
647 assert_eq!(iter.next(), None);
648}
649
650#[test]
651fn fully_consumed_drain() {
652 let mut slab = Slab::new();
653
654 for i in 0..3 {
655 slab.insert(i);
656 }
657
658 {
659 let mut drain = slab.drain();
660 assert_eq!(Some(0), drain.next());
661 assert_eq!(Some(1), drain.next());
662 assert_eq!(Some(2), drain.next());
663 assert_eq!(None, drain.next());
664 }
665
666 assert!(slab.is_empty());
667}
668
669#[test]
670fn partially_consumed_drain() {
671 let mut slab = Slab::new();
672
673 for i in 0..3 {
674 slab.insert(i);
675 }
676
677 {
678 let mut drain = slab.drain();
679 assert_eq!(Some(0), drain.next());
680 }
681
682 assert!(slab.is_empty())
683}
684
685#[test]
686fn drain_rev() {
687 let mut slab = Slab::new();
688 for i in 0..10 {
689 slab.insert(i);
690 }
691 slab.remove(9);
692
693 let vals: Vec<u64> = slab.drain().rev().collect();
694 assert_eq!(vals, (0..9).rev().collect::<Vec<u64>>());
695}
696
697#[test]
698fn try_remove() {
699 let mut slab = Slab::new();
700
701 let key = slab.insert(1);
702
703 assert_eq!(slab.try_remove(key), Some(1));
704 assert_eq!(slab.try_remove(key), None);
705 assert_eq!(slab.get(key), None);
706}
707
708#[rustversion::since(1.39)]
709#[test]
710fn const_new() {
711 static _SLAB: Slab<()> = Slab::new();
712}
713
714#[test]
715fn clone_from() {
716 let mut slab1 = Slab::new();
717 let mut slab2 = Slab::new();
718 for i in 0..5 {
719 slab1.insert(i);
720 slab2.insert(2 * i);
721 slab2.insert(2 * i + 1);
722 }
723 slab1.remove(1);
724 slab1.remove(3);
725 slab2.clone_from(&slab1);
726
727 let mut iter2 = slab2.iter();
728 assert_eq!(iter2.next(), Some((0, &0)));
729 assert_eq!(iter2.next(), Some((2, &2)));
730 assert_eq!(iter2.next(), Some((4, &4)));
731 assert_eq!(iter2.next(), None);
732 assert!(slab2.capacity() >= 10);
733}
734