slab/
builder.rs

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}
slab/builder.rs

slab/
builder.rs
