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::usize::MAX);
200 }
201
202 #[test]
203 #[should_panic(expected = "capacity overflow")]
reserve_exact_does_panic_with_capacity_overflow()204 fn reserve_exact_does_panic_with_capacity_overflow() {
205 let mut slab = Slab::with_capacity(10);
206 slab.insert(true);
207 slab.reserve_exact(std::usize::MAX);
208 }
209
210 #[test]
retain()211 fn retain() {
212 let mut slab = Slab::with_capacity(2);
213
214 let key1 = slab.insert(0);
215 let key2 = slab.insert(1);
216
217 slab.retain(|key, x| {
218 assert_eq!(key, *x);
219 *x % 2 == 0
220 });
221
222 assert_eq!(slab.len(), 1);
223 assert_eq!(slab[key1], 0);
224 assert!(!slab.contains(key2));
225
226 // Ensure consistency is retained
227 let key = slab.insert(123);
228 assert_eq!(key, key2);
229
230 assert_eq!(2, slab.len());
231 assert_eq!(2, slab.capacity());
232
233 // Inserting another element grows
234 let key = slab.insert(345);
235 assert_eq!(key, 2);
236
237 assert_eq!(4, slab.capacity());
238 }
239
240 #[test]
into_iter()241 fn into_iter() {
242 let mut slab = Slab::new();
243
244 for i in 0..8 {
245 slab.insert(i);
246 }
247 slab.remove(0);
248 slab.remove(4);
249 slab.remove(5);
250 slab.remove(7);
251
252 let vals: Vec<_> = slab
253 .into_iter()
254 .inspect(|&(key, val)| assert_eq!(key, val))
255 .map(|(_, val)| val)
256 .collect();
257 assert_eq!(vals, vec![1, 2, 3, 6]);
258 }
259
260 #[test]
into_iter_rev()261 fn into_iter_rev() {
262 let mut slab = Slab::new();
263
264 for i in 0..4 {
265 slab.insert(i);
266 }
267
268 let mut iter = slab.into_iter();
269 assert_eq!(iter.next_back(), Some((3, 3)));
270 assert_eq!(iter.next_back(), Some((2, 2)));
271 assert_eq!(iter.next(), Some((0, 0)));
272 assert_eq!(iter.next_back(), Some((1, 1)));
273 assert_eq!(iter.next_back(), None);
274 assert_eq!(iter.next(), None);
275 }
276
277 #[test]
iter()278 fn iter() {
279 let mut slab = Slab::new();
280
281 for i in 0..4 {
282 slab.insert(i);
283 }
284
285 let vals: Vec<_> = slab
286 .iter()
287 .enumerate()
288 .map(|(i, (key, val))| {
289 assert_eq!(i, key);
290 *val
291 })
292 .collect();
293 assert_eq!(vals, vec![0, 1, 2, 3]);
294
295 slab.remove(1);
296
297 let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
298 assert_eq!(vals, vec![0, 2, 3]);
299 }
300
301 #[test]
iter_rev()302 fn iter_rev() {
303 let mut slab = Slab::new();
304
305 for i in 0..4 {
306 slab.insert(i);
307 }
308 slab.remove(0);
309
310 let vals = slab.iter().rev().collect::<Vec<_>>();
311 assert_eq!(vals, vec![(3, &3), (2, &2), (1, &1)]);
312 }
313
314 #[test]
iter_mut()315 fn iter_mut() {
316 let mut slab = Slab::new();
317
318 for i in 0..4 {
319 slab.insert(i);
320 }
321
322 for (i, (key, e)) in slab.iter_mut().enumerate() {
323 assert_eq!(i, key);
324 *e += 1;
325 }
326
327 let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
328 assert_eq!(vals, vec![1, 2, 3, 4]);
329
330 slab.remove(2);
331
332 for (_, e) in slab.iter_mut() {
333 *e += 1;
334 }
335
336 let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
337 assert_eq!(vals, vec![2, 3, 5]);
338 }
339
340 #[test]
iter_mut_rev()341 fn iter_mut_rev() {
342 let mut slab = Slab::new();
343
344 for i in 0..4 {
345 slab.insert(i);
346 }
347 slab.remove(2);
348
349 {
350 let mut iter = slab.iter_mut();
351 assert_eq!(iter.next(), Some((0, &mut 0)));
352 let mut prev_key = !0;
353 for (key, e) in iter.rev() {
354 *e += 10;
355 assert!(prev_key > key);
356 prev_key = key;
357 }
358 }
359
360 assert_eq!(slab[0], 0);
361 assert_eq!(slab[1], 11);
362 assert_eq!(slab[3], 13);
363 assert!(!slab.contains(2));
364 }
365
366 #[test]
from_iterator_sorted()367 fn from_iterator_sorted() {
368 let mut slab = (0..5).map(|i| (i, i)).collect::<Slab<_>>();
369 assert_eq!(slab.len(), 5);
370 assert_eq!(slab[0], 0);
371 assert_eq!(slab[2], 2);
372 assert_eq!(slab[4], 4);
373 assert_eq!(slab.vacant_entry().key(), 5);
374 }
375
376 #[test]
from_iterator_new_in_order()377 fn from_iterator_new_in_order() {
378 // all new keys come in increasing order, but existing keys are overwritten
379 let mut slab = [(0, 'a'), (1, 'a'), (1, 'b'), (0, 'b'), (9, 'a'), (0, 'c')]
380 .iter()
381 .cloned()
382 .collect::<Slab<_>>();
383 assert_eq!(slab.len(), 3);
384 assert_eq!(slab[0], 'c');
385 assert_eq!(slab[1], 'b');
386 assert_eq!(slab[9], 'a');
387 assert_eq!(slab.get(5), None);
388 assert_eq!(slab.vacant_entry().key(), 8);
389 }
390
391 #[test]
from_iterator_unordered()392 fn from_iterator_unordered() {
393 let mut slab = vec![(1, "one"), (50, "fifty"), (3, "three"), (20, "twenty")]
394 .into_iter()
395 .collect::<Slab<_>>();
396 assert_eq!(slab.len(), 4);
397 assert_eq!(slab.vacant_entry().key(), 0);
398 let mut iter = slab.iter();
399 assert_eq!(iter.next(), Some((1, &"one")));
400 assert_eq!(iter.next(), Some((3, &"three")));
401 assert_eq!(iter.next(), Some((20, &"twenty")));
402 assert_eq!(iter.next(), Some((50, &"fifty")));
403 assert_eq!(iter.next(), None);
404 }
405
406 // https://github.com/tokio-rs/slab/issues/100
407 #[test]
from_iterator_issue_100()408 fn from_iterator_issue_100() {
409 let mut slab: slab::Slab<()> = vec![(1, ())].into_iter().collect();
410 assert_eq!(slab.len(), 1);
411 assert_eq!(slab.insert(()), 0);
412 assert_eq!(slab.insert(()), 2);
413 assert_eq!(slab.insert(()), 3);
414
415 let mut slab: slab::Slab<()> = vec![(1, ()), (2, ())].into_iter().collect();
416 assert_eq!(slab.len(), 2);
417 assert_eq!(slab.insert(()), 0);
418 assert_eq!(slab.insert(()), 3);
419 assert_eq!(slab.insert(()), 4);
420
421 let mut slab: slab::Slab<()> = vec![(1, ()), (3, ())].into_iter().collect();
422 assert_eq!(slab.len(), 2);
423 assert_eq!(slab.insert(()), 2);
424 assert_eq!(slab.insert(()), 0);
425 assert_eq!(slab.insert(()), 4);
426
427 let mut slab: slab::Slab<()> = vec![(0, ()), (2, ()), (3, ()), (5, ())]
428 .into_iter()
429 .collect();
430 assert_eq!(slab.len(), 4);
431 assert_eq!(slab.insert(()), 4);
432 assert_eq!(slab.insert(()), 1);
433 assert_eq!(slab.insert(()), 6);
434 }
435
436 #[test]
clear()437 fn clear() {
438 let mut slab = Slab::new();
439
440 for i in 0..4 {
441 slab.insert(i);
442 }
443
444 // clear full
445 slab.clear();
446 assert!(slab.is_empty());
447
448 assert_eq!(0, slab.len());
449 assert_eq!(4, slab.capacity());
450
451 for i in 0..2 {
452 slab.insert(i);
453 }
454
455 let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
456 assert_eq!(vals, vec![0, 1]);
457
458 // clear half-filled
459 slab.clear();
460 assert!(slab.is_empty());
461 }
462
463 #[test]
shrink_to_fit_empty()464 fn shrink_to_fit_empty() {
465 let mut slab = Slab::<bool>::with_capacity(20);
466 slab.shrink_to_fit();
467 assert_eq!(slab.capacity(), 0);
468 }
469
470 #[test]
shrink_to_fit_no_vacant()471 fn shrink_to_fit_no_vacant() {
472 let mut slab = Slab::with_capacity(20);
473 slab.insert(String::new());
474 slab.shrink_to_fit();
475 assert!(slab.capacity() < 10);
476 }
477
478 #[test]
shrink_to_fit_doesnt_move()479 fn shrink_to_fit_doesnt_move() {
480 let mut slab = Slab::with_capacity(8);
481 slab.insert("foo");
482 let bar = slab.insert("bar");
483 slab.insert("baz");
484 let quux = slab.insert("quux");
485 slab.remove(quux);
486 slab.remove(bar);
487 slab.shrink_to_fit();
488 assert_eq!(slab.len(), 2);
489 assert!(slab.capacity() >= 3);
490 assert_eq!(slab.get(0), Some(&"foo"));
491 assert_eq!(slab.get(2), Some(&"baz"));
492 assert_eq!(slab.vacant_entry().key(), bar);
493 }
494
495 #[test]
shrink_to_fit_doesnt_recreate_list_when_nothing_can_be_done()496 fn shrink_to_fit_doesnt_recreate_list_when_nothing_can_be_done() {
497 let mut slab = Slab::with_capacity(16);
498 for i in 0..4 {
499 slab.insert(Box::new(i));
500 }
501 slab.remove(0);
502 slab.remove(2);
503 slab.remove(1);
504 assert_eq!(slab.vacant_entry().key(), 1);
505 slab.shrink_to_fit();
506 assert_eq!(slab.len(), 1);
507 assert!(slab.capacity() >= 4);
508 assert_eq!(slab.vacant_entry().key(), 1);
509 }
510
511 #[test]
compact_empty()512 fn compact_empty() {
513 let mut slab = Slab::new();
514 slab.compact(|_, _, _| panic!());
515 assert_eq!(slab.len(), 0);
516 assert_eq!(slab.capacity(), 0);
517 slab.reserve(20);
518 slab.compact(|_, _, _| panic!());
519 assert_eq!(slab.len(), 0);
520 assert_eq!(slab.capacity(), 0);
521 slab.insert(0);
522 slab.insert(1);
523 slab.insert(2);
524 slab.remove(1);
525 slab.remove(2);
526 slab.remove(0);
527 slab.compact(|_, _, _| panic!());
528 assert_eq!(slab.len(), 0);
529 assert_eq!(slab.capacity(), 0);
530 }
531
532 #[test]
compact_no_moves_needed()533 fn compact_no_moves_needed() {
534 let mut slab = Slab::new();
535 for i in 0..10 {
536 slab.insert(i);
537 }
538 slab.remove(8);
539 slab.remove(9);
540 slab.remove(6);
541 slab.remove(7);
542 slab.compact(|_, _, _| panic!());
543 assert_eq!(slab.len(), 6);
544 for ((index, &value), want) in slab.iter().zip(0..6) {
545 assert!(index == value);
546 assert_eq!(index, want);
547 }
548 assert!(slab.capacity() >= 6 && slab.capacity() < 10);
549 }
550
551 #[test]
compact_moves_successfully()552 fn compact_moves_successfully() {
553 let mut slab = Slab::with_capacity(20);
554 for i in 0..10 {
555 slab.insert(i);
556 }
557 for &i in &[0, 5, 9, 6, 3] {
558 slab.remove(i);
559 }
560 let mut moved = 0;
561 slab.compact(|&mut v, from, to| {
562 assert!(from > to);
563 assert!(from >= 5);
564 assert!(to < 5);
565 assert_eq!(from, v);
566 moved += 1;
567 true
568 });
569 assert_eq!(slab.len(), 5);
570 assert_eq!(moved, 2);
571 assert_eq!(slab.vacant_entry().key(), 5);
572 assert!(slab.capacity() >= 5 && slab.capacity() < 20);
573 let mut iter = slab.iter();
574 assert_eq!(iter.next(), Some((0, &8)));
575 assert_eq!(iter.next(), Some((1, &1)));
576 assert_eq!(iter.next(), Some((2, &2)));
577 assert_eq!(iter.next(), Some((3, &7)));
578 assert_eq!(iter.next(), Some((4, &4)));
579 assert_eq!(iter.next(), None);
580 }
581
582 #[test]
compact_doesnt_move_if_closure_errors()583 fn compact_doesnt_move_if_closure_errors() {
584 let mut slab = Slab::with_capacity(20);
585 for i in 0..10 {
586 slab.insert(i);
587 }
588 for &i in &[9, 3, 1, 4, 0] {
589 slab.remove(i);
590 }
591 slab.compact(|&mut v, from, to| {
592 assert!(from > to);
593 assert_eq!(from, v);
594 v != 6
595 });
596 assert_eq!(slab.len(), 5);
597 assert!(slab.capacity() >= 7 && slab.capacity() < 20);
598 assert_eq!(slab.vacant_entry().key(), 3);
599 let mut iter = slab.iter();
600 assert_eq!(iter.next(), Some((0, &8)));
601 assert_eq!(iter.next(), Some((1, &7)));
602 assert_eq!(iter.next(), Some((2, &2)));
603 assert_eq!(iter.next(), Some((5, &5)));
604 assert_eq!(iter.next(), Some((6, &6)));
605 assert_eq!(iter.next(), None);
606 }
607
608 #[test]
compact_handles_closure_panic()609 fn compact_handles_closure_panic() {
610 let mut slab = Slab::new();
611 for i in 0..10 {
612 slab.insert(i);
613 }
614 for i in 1..6 {
615 slab.remove(i);
616 }
617 let result = catch_unwind(AssertUnwindSafe(|| {
618 slab.compact(|&mut v, from, to| {
619 assert!(from > to);
620 assert_eq!(from, v);
621 if v == 7 {
622 panic!("test");
623 }
624 true
625 })
626 }));
627 match result {
628 Err(ref payload) if payload.downcast_ref() == Some(&"test") => {}
629 Err(bug) => resume_unwind(bug),
630 Ok(()) => unreachable!(),
631 }
632 assert_eq!(slab.len(), 5 - 1);
633 assert_eq!(slab.vacant_entry().key(), 3);
634 let mut iter = slab.iter();
635 assert_eq!(iter.next(), Some((0, &0)));
636 assert_eq!(iter.next(), Some((1, &9)));
637 assert_eq!(iter.next(), Some((2, &8)));
638 assert_eq!(iter.next(), Some((6, &6)));
639 assert_eq!(iter.next(), None);
640 }
641
642 #[test]
fully_consumed_drain()643 fn fully_consumed_drain() {
644 let mut slab = Slab::new();
645
646 for i in 0..3 {
647 slab.insert(i);
648 }
649
650 {
651 let mut drain = slab.drain();
652 assert_eq!(Some(0), drain.next());
653 assert_eq!(Some(1), drain.next());
654 assert_eq!(Some(2), drain.next());
655 assert_eq!(None, drain.next());
656 }
657
658 assert!(slab.is_empty());
659 }
660
661 #[test]
partially_consumed_drain()662 fn partially_consumed_drain() {
663 let mut slab = Slab::new();
664
665 for i in 0..3 {
666 slab.insert(i);
667 }
668
669 {
670 let mut drain = slab.drain();
671 assert_eq!(Some(0), drain.next());
672 }
673
674 assert!(slab.is_empty())
675 }
676
677 #[test]
drain_rev()678 fn drain_rev() {
679 let mut slab = Slab::new();
680 for i in 0..10 {
681 slab.insert(i);
682 }
683 slab.remove(9);
684
685 let vals: Vec<u64> = slab.drain().rev().collect();
686 assert_eq!(vals, (0..9).rev().collect::<Vec<u64>>());
687 }
688
689 #[test]
try_remove()690 fn try_remove() {
691 let mut slab = Slab::new();
692
693 let key = slab.insert(1);
694
695 assert_eq!(slab.try_remove(key), Some(1));
696 assert_eq!(slab.try_remove(key), None);
697 assert_eq!(slab.get(key), None);
698 }
699