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> { |
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 | |