segmented_vector/
lib.rs

1#![cfg_attr(not(test), no_std)]
2
3#![warn(clippy::std_instead_of_alloc, clippy::std_instead_of_core)]
4
5extern crate alloc;
6
7mod iterator;
8mod ref_set;
9mod segment;
10mod segmented_vector;
11mod scalar_set;
12pub use ref_set::SizedRefSet;
13pub use segmented_vector::SizedSegmentedVector;
14pub use scalar_set::SizedScalarSet;
15
16pub type RefSet16<A> = SizedRefSet<16, A>;
17pub type RefSet32<A> = SizedRefSet<32, A>;
18
19pub type SegmentedVector16<A> = SizedSegmentedVector<16, A>;
20pub type SegmentedVector32<A> = SizedSegmentedVector<32, A>;
21
22
23// generate a good 128-byte default segment size per arch
24#[cfg(target_pointer_width = "64")]
25pub type RefSet<A> = RefSet16<A>;
26
27#[cfg(target_pointer_width = "32")]
28pub type RefSet<A> = RefSet32<A>;
29
30#[cfg(target_pointer_width = "64")]
31pub type ScalarSet<A> = SizedScalarSet<16, A>;
32
33#[cfg(target_pointer_width = "32")]
34pub type ScalarSet<A> = SizedScalarSet<32, A>;
35
36#[cfg(target_pointer_width = "64")]
37pub type SegmentedVector<A> = SegmentedVector16<A>;
38
39#[cfg(target_pointer_width = "32")]
40pub type SegmentedVector<A> = SegmentedVector32<A>;
41
42
43#[cfg(test)]
44mod test {
45    use super::*;
46
47    // enough to fill up head, tail, an entire branch, and start a 2-height tree
48    const WIDTH: usize = 16;
49    const TEST_SIZE: usize = (WIDTH + 2) * WIDTH + 2;
50
51
52    #[test]
53    fn basic() {
54        let mut v1 = SizedSegmentedVector::<WIDTH, u32>::new();
55        assert_eq!(v1.len(), 0);
56        assert_eq!(v1.as_vec(), vec![]);
57        v1.push(10);
58        assert_eq!(v1.len(), 1);
59        assert_eq!(v1.as_vec(), vec![ 10 ]);
60        assert_eq!(v1.pop(), Some(10));
61        assert_eq!(v1.len(), 0);
62        assert_eq!(v1.as_vec(), vec![]);
63    }
64
65    #[test]
66    fn push_and_grow_tree() {
67        let mut v1 = SizedSegmentedVector::<WIDTH, u32>::new();
68        for i in 0 .. TEST_SIZE {
69            v1.push(i as u32);
70            assert_eq!(v1.len(), i + 1);
71            assert_eq!(v1.as_vec(), (0u32 .. (i + 1) as u32).collect::<Vec<_>>());
72        }
73    }
74
75    #[test]
76    fn slices() {
77        let numbers = (0u32 .. TEST_SIZE as u32).collect::<Vec<_>>();
78        let v1 = SizedSegmentedVector::<WIDTH, u32>::from_slice(&numbers);
79        for i in 0 .. TEST_SIZE {
80            let v2 = v1.slice_as_vec(i, v1.len());
81            assert_eq!(v2, numbers[i..]);
82            for j in i + 1 .. TEST_SIZE {
83                let v3 = v1.slice_as_vec(i, j);
84                assert_eq!(v3, numbers[i..j]);
85            }
86        }
87    }
88
89    #[test]
90    fn pop_and_shrink_tree() {
91        let mut v1 = SizedSegmentedVector::<WIDTH, u32>::new();
92        for i in 0 .. TEST_SIZE {
93            v1.push(i as u32);
94        }
95        for i in 0 .. TEST_SIZE {
96            let j = TEST_SIZE - i - 1;
97            assert_eq!(v1.pop(), Some(j as u32));
98            assert_eq!(v1.len(), j);
99            assert_eq!(v1.as_vec(), (0u32 .. (j as u32)).collect::<Vec<_>>());
100        }
101        assert!(v1.get_head().is_none());
102        assert!(v1.get_root().is_none());
103        assert!(v1.get_tail().is_none());
104    }
105
106    #[test]
107    fn shift_and_unshift() {
108        let mut v1 = SizedSegmentedVector::<WIDTH, u32>::new();
109        for i in 0 .. TEST_SIZE {
110            v1.unshift(i as u32);
111            assert_eq!(v1.len(), i + 1);
112            assert_eq!(v1.as_vec(), (0u32 .. ((i + 1) as u32)).rev().collect::<Vec<_>>());
113        }
114        v1.push(1000u32);
115        v1.push(1001u32);
116        let mut expected = (0u32 .. (TEST_SIZE as u32)).rev().collect::<Vec<_>>();
117        expected.extend_from_slice(&[ 1000u32, 1001u32 ]);
118        assert_eq!(v1.as_vec(), expected);
119
120        let mut v2 = SizedSegmentedVector::<WIDTH, u32>::new();
121        for i in 0 .. TEST_SIZE {
122            v2.unshift(i as u32);
123        }
124        // sneaky: add 2 items on the right to ensure they can be shifted from the left
125        v2.push(1000u32);
126        v2.push(1001u32);
127        expected = (0u32 .. (TEST_SIZE as u32)).rev().collect::<Vec<_>>();
128        expected.extend_from_slice(&[ 1000u32, 1001u32 ]);
129        for i in 0 .. TEST_SIZE {
130            assert_eq!(v2.shift(), Some((TEST_SIZE - i - 1) as u32));
131            assert_eq!(v2.len(), TEST_SIZE - i + 1);
132            expected.remove(0);
133            assert_eq!(v2.as_vec(), expected);
134        }
135        assert_eq!(v2.shift(), Some(1000u32));
136        assert_eq!(v2.shift(), Some(1001u32));
137        assert_eq!(v2.len(), 0);
138        assert!(v2.get_head().is_none());
139        assert!(v2.get_root().is_none());
140        assert!(v2.get_tail().is_none());
141    }
142
143    #[test]
144    fn build_from_iter() {
145        let numbers = (0u32 .. TEST_SIZE as u32).collect::<Vec<_>>();
146        for i in 0 .. TEST_SIZE {
147            let v1 = SizedSegmentedVector::<WIDTH, u32>::from_iter(numbers[..i].iter().cloned());
148            assert_eq!(v1.len(), i);
149            assert_eq!(v1.iter().cloned().collect::<Vec<_>>(), (0u32 .. (i as u32)).collect::<Vec<_>>());
150        }
151    }
152
153    #[test]
154    fn build_from_slice_get_pop() {
155        let numbers = (0u32 .. TEST_SIZE as u32).collect::<Vec<_>>();
156        for i in 0 .. TEST_SIZE {
157            let mut v1 = SizedSegmentedVector::<WIDTH, u32>::from_slice(&numbers[..i]);
158            assert_eq!(v1.len(), i);
159            assert_eq!(v1.as_vec(), (0u32 .. i as u32).collect::<Vec<_>>());
160
161            for j in 0..i {
162                let r = v1.pop();
163                assert_eq!(r, Some((i - j - 1) as u32));
164            }
165            assert_eq!(v1.len(), 0);
166        }
167    }
168
169    #[test]
170    fn build_from_slice_get_set() {
171        let numbers = (0u32 .. TEST_SIZE as u32).collect::<Vec<_>>();
172        for i in 0 .. TEST_SIZE {
173            let mut v1 = SizedSegmentedVector::<WIDTH, u32>::from_slice(&numbers[..i]);
174            assert_eq!(v1.len(), i);
175            assert_eq!(v1.as_vec(), (0u32 .. i as u32).collect::<Vec<_>>());
176
177            for j in 0..i {
178                assert_eq!(v1.get(j), Some(&(j as u32)));
179                v1.set(j, (1000 + j) as u32);
180                assert_eq!(v1[j], (1000 + j) as u32);
181                v1[j] = (2000 + j) as u32;
182                assert_eq!(v1.get(j), Some(&((2000 + j) as u32)));
183            }
184
185            assert_eq!(v1.len(), i);
186        }
187    }
188
189    #[test]
190    fn insert() {
191        let numbers = (0u32 .. TEST_SIZE as u32).collect::<Vec<_>>();
192        for i in 0 .. TEST_SIZE {
193            for j in 0 .. i + 1 {
194                let mut v1 = SizedSegmentedVector::<WIDTH, u32>::new();
195                // fill head with the first WIDTH, to exercise all paths.
196                for k in 0 .. i.min(WIDTH) { v1.unshift(numbers[i.min(WIDTH) - k - 1]); }
197                numbers.iter().take(i).skip(i.min(WIDTH)).for_each(|n| v1.push(*n));
198                assert_eq!(v1.len(), i);
199
200                v1.insert(j, 999u32);
201                assert_eq!(v1.as_vec(), [ &numbers[..(j.min(i))], &[ 999u32 ], &numbers[(j.min(i))..i] ].concat());
202            }
203        }
204    }
205
206    #[test]
207    fn delete() {
208        let numbers = (0u32 .. TEST_SIZE as u32).collect::<Vec<_>>();
209        for i in 0 .. TEST_SIZE {
210            for j in 0 .. i + 1 {
211                let mut v1 = SizedSegmentedVector::<WIDTH, u32>::new();
212                // fill head with the first WIDTH, to exercise all paths.
213                for k in 0 .. i.min(WIDTH) { v1.unshift(numbers[i.min(WIDTH) - k - 1]); }
214                numbers.iter().take(i).skip(i.min(WIDTH)).for_each(|n| v1.push(*n));
215                assert_eq!(v1.len(), i);
216
217                assert_eq!(v1.delete(j), if j < i { Some(j as u32) } else { None });
218                let k = j.min(i);
219                assert_eq!(v1.as_vec(), [ &numbers[..k], &numbers[i.min(k + 1)..i] ].concat());
220            }
221        }
222    }
223
224    #[test]
225    fn splice() {
226        let numbers = (0u32 .. TEST_SIZE as u32).collect::<Vec<_>>();
227        let insert_list = (1000u32 .. 1100u32).collect::<Vec<_>>();
228
229        let mut v1 = SizedSegmentedVector::<WIDTH, u32>::new();
230        // fill head with the first WIDTH, to exercise all paths.
231        for k in 0 .. WIDTH { v1.unshift(numbers[WIDTH - k - 1]); }
232        numbers.iter().skip(WIDTH).for_each(|n| v1.push(*n));
233        assert_eq!(v1.len(), TEST_SIZE);
234
235        for i in 0 .. TEST_SIZE {
236            for del_count in 0 .. WIDTH + 2 {
237                for ins_count in 0 .. WIDTH + 2 {
238                    let mut v2 = v1.clone();
239                    v2.splice(i, del_count, &insert_list[..ins_count]);
240                    let real_del_count = del_count.min(v1.len() - i);
241                    assert_eq!(
242                        v2.as_vec(),
243                        [ &numbers[..i], &insert_list[..ins_count], &numbers[(i + real_del_count)..] ].concat()
244                    );
245                }
246            }
247        }
248    }
249}
segmented_vector/lib.rs

segmented_vector/
lib.rs
