1 use crate::{Entry, Slab}; 2 3 // Building `Slab` from pairs (usize, T). 4 pub(crate) struct Builder<T> { 5 slab: Slab<T>, 6 vacant_list_broken: bool, 7 first_vacant_index: Option<usize>, 8 } 9 10 impl<T> Builder<T> { with_capacity(capacity: usize) -> Self11 pub(crate) fn with_capacity(capacity: usize) -> Self { 12 Self { 13 slab: Slab::with_capacity(capacity), 14 vacant_list_broken: false, 15 first_vacant_index: None, 16 } 17 } pair(&mut self, key: usize, value: T)18 pub(crate) fn pair(&mut self, key: usize, value: T) { 19 let slab = &mut self.slab; 20 if key < slab.entries.len() { 21 // iterator is not sorted, might need to recreate vacant list 22 if let Entry::Vacant(_) = slab.entries[key] { 23 self.vacant_list_broken = true; 24 slab.len += 1; 25 } 26 // if an element with this key already exists, replace it. 27 // This is consistent with HashMap and BtreeMap 28 slab.entries[key] = Entry::Occupied(value); 29 } else { 30 if self.first_vacant_index.is_none() && slab.entries.len() < key { 31 self.first_vacant_index = Some(slab.entries.len()); 32 } 33 // insert holes as necessary 34 while slab.entries.len() < key { 35 // add the entry to the start of the vacant list 36 let next = slab.next; 37 slab.next = slab.entries.len(); 38 slab.entries.push(Entry::Vacant(next)); 39 } 40 slab.entries.push(Entry::Occupied(value)); 41 slab.len += 1; 42 } 43 } 44 build(self) -> Slab<T>45 pub(crate) fn build(self) -> Slab<T> { 46 let mut slab = self.slab; 47 if slab.len == slab.entries.len() { 48 // no vacant entries, so next might not have been updated 49 slab.next = slab.entries.len(); 50 } else if self.vacant_list_broken { 51 slab.recreate_vacant_list(); 52 } else if let Some(first_vacant_index) = self.first_vacant_index { 53 let next = slab.entries.len(); 54 match &mut slab.entries[first_vacant_index] { 55 Entry::Vacant(n) => *n = next, 56 _ => unreachable!(), 57 } 58 } else { 59 unreachable!() 60 } 61 slab 62 } 63 } 64