1/// `Vec` partitioned in half.
2///
3/// This type exists to make `FilterSet` have a smaller footprint and for
4/// `FilterSet::is_match` to generate better code.
5pub(crate) struct SplitVec<T> {
6 items: Vec<T>,
7 split_index: usize,
8}
9
10impl<T> Default for SplitVec<T> {
11 #[inline]
12 fn default() -> Self {
13 Self { items: Vec::default(), split_index: 0 }
14 }
15}
16
17impl<T> SplitVec<T> {
18 /// Inserts an item to the end of either the first or second half.
19 #[inline]
20 pub fn insert(&mut self, value: T, after_split: bool) {
21 unsafe {
22 // Ensure we have at least one slot available.
23 self.items.reserve(1);
24
25 let old_len = self.items.len();
26 let old_split = self.split_index();
27
28 let start_ptr = self.items.as_mut_ptr();
29 let last_ptr = start_ptr.add(old_len);
30 let split_ptr = start_ptr.add(old_split);
31 let value_slot = if after_split { last_ptr } else { split_ptr };
32
33 // If writing to before the split, then increment the split index
34 // and move any value there to the end.
35 //
36 // NOTE: We can't use `copy_to_nonoverlapping` because both pointers
37 // are the same if `old_len` is 0.
38 if !after_split {
39 split_ptr.copy_to(last_ptr, 1);
40 self.set_split_index(old_split + 1);
41 }
42
43 value_slot.write(value);
44 self.items.set_len(old_len + 1);
45 }
46 }
47
48 #[inline]
49 pub fn reserve_exact(&mut self, additional: usize) {
50 self.items.reserve_exact(additional);
51 }
52
53 /// Returns the slice of all items.
54 #[inline]
55 pub fn all(&self) -> &[T] {
56 &self.items
57 }
58
59 /// Returns the split halves.
60 #[inline]
61 #[cfg(test)]
62 pub fn split(&self) -> (&[T], &[T]) {
63 self.items.split_at(self.split_index())
64 }
65
66 /// Returns where the halves are split.
67 #[inline]
68 pub fn split_index(&self) -> usize {
69 let index = self.split_index;
70
71 // Optimization hint to remove bounds checks.
72 let len = self.items.len();
73 unsafe { assert_unchecked!(index <= len, "index {index} out of bounds (len = {len})") }
74
75 index
76 }
77
78 /// Sets where the halves are split.
79 #[inline]
80 pub unsafe fn set_split_index(&mut self, new_index: usize) {
81 self.split_index = new_index;
82 }
83}
84
85#[cfg(test)]
86mod tests {
87 use super::*;
88
89 #[track_caller]
90 fn test(vec: &SplitVec<&str>, before: &[&str], after: &[&str]) {
91 assert_eq!(vec.split(), (before, after));
92 }
93
94 #[test]
95 fn before_split() {
96 let mut vec = SplitVec::<&str>::default();
97
98 vec.insert("abc", false);
99 test(&vec, &["abc"], &[]);
100
101 vec.insert("xyz", false);
102 test(&vec, &["abc", "xyz"], &[]);
103 }
104
105 #[test]
106 fn after_split() {
107 let mut vec = SplitVec::<&str>::default();
108
109 vec.insert("abc", true);
110 test(&vec, &[], &["abc"]);
111
112 vec.insert("xyz", true);
113 test(&vec, &[], &["abc", "xyz"]);
114 }
115
116 #[test]
117 fn mixed() {
118 let mut vec = SplitVec::<&str>::default();
119
120 vec.insert("abc", false);
121 test(&vec, &["abc"], &[]);
122
123 vec.insert("xyz", true);
124 test(&vec, &["abc"], &["xyz"]);
125
126 vec.insert("123", false);
127 test(&vec, &["abc", "123"], &["xyz"]);
128
129 vec.insert("456", true);
130 test(&vec, &["abc", "123"], &["xyz", "456"]);
131
132 vec.insert("789", false);
133 test(&vec, &["abc", "123", "789"], &["456", "xyz"]);
134 }
135}
136