1use crate::{Entry, Slab};
2
3// Building `Slab` from pairs (usize, T).
4pub(crate) struct Builder<T> {
5 slab: Slab<T>,
6 vacant_list_broken: bool,
7 first_vacant_index: Option<usize>,
8}
9
10impl<T> Builder<T> {
11 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 }
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
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