1 use {crate::unreachable_unchecked, alloc::vec::Vec, core::mem::replace}; 2 3 #[derive(Debug)] 4 enum Entry<T> { 5 Vacant(usize), 6 Occupied(T), 7 } 8 #[derive(Debug)] 9 pub(crate) struct Slab<T> { 10 next_vacant: usize, 11 entries: Vec<Entry<T>>, 12 } 13 14 impl<T> Slab<T> { new() -> Self15 pub fn new() -> Self { 16 Slab { 17 next_vacant: !0, 18 entries: Vec::new(), 19 } 20 } 21 22 /// Inserts value into this linked vec and returns index 23 /// at which value can be accessed in constant time. insert(&mut self, value: T) -> usize24 pub fn insert(&mut self, value: T) -> usize { 25 if self.next_vacant >= self.entries.len() { 26 self.entries.push(Entry::Occupied(value)); 27 self.entries.len() - 1 28 } else { 29 match *unsafe { self.entries.get_unchecked(self.next_vacant) } { 30 Entry::Vacant(next_vacant) => { 31 unsafe { 32 *self.entries.get_unchecked_mut(self.next_vacant) = Entry::Occupied(value); 33 } 34 replace(&mut self.next_vacant, next_vacant) 35 } 36 _ => unsafe { unreachable_unchecked() }, 37 } 38 } 39 } 40 len(&self) -> usize41 pub fn len(&self) -> usize { 42 self.entries.len() 43 } 44 get_unchecked(&self, index: usize) -> &T45 pub unsafe fn get_unchecked(&self, index: usize) -> &T { 46 debug_assert!(index < self.len()); 47 48 match self.entries.get_unchecked(index) { 49 Entry::Occupied(value) => value, 50 _ => unreachable_unchecked(), 51 } 52 } 53 get_unchecked_mut(&mut self, index: usize) -> &mut T54 pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T { 55 debug_assert!(index < self.len()); 56 57 match self.entries.get_unchecked_mut(index) { 58 Entry::Occupied(value) => value, 59 _ => unreachable_unchecked(), 60 } 61 } 62 get(&self, index: usize) -> &T63 pub fn get(&self, index: usize) -> &T { 64 match self.entries.get(index) { 65 Some(Entry::Occupied(value)) => value, 66 _ => panic!("Invalid index"), 67 } 68 } 69 get_mut(&mut self, index: usize) -> &mut T70 pub fn get_mut(&mut self, index: usize) -> &mut T { 71 match self.entries.get_mut(index) { 72 Some(Entry::Occupied(value)) => value, 73 _ => panic!("Invalid index"), 74 } 75 } 76 remove_unchecked(&mut self, index: usize) -> T77 pub unsafe fn remove_unchecked(&mut self, index: usize) -> T { 78 let entry = replace( 79 self.entries.get_unchecked_mut(index), 80 Entry::Vacant(self.next_vacant), 81 ); 82 83 self.next_vacant = index; 84 85 match entry { 86 Entry::Occupied(value) => value, 87 _ => unreachable_unchecked(), 88 } 89 } 90 remove(&mut self, index: usize) -> T91 pub fn remove(&mut self, index: usize) -> T { 92 match self.entries.get_mut(index) { 93 Some(Entry::Occupied(_)) => unsafe { self.remove_unchecked(index) }, 94 _ => panic!("Invalid index"), 95 } 96 } 97 } 98