Nothing to see here, move along meow
1use lancer_core::slot_map::{SlotEntry, SlotMap};
2use proptest::prelude::*;
3
4type TestMap = SlotMap<u64, 16, 64>;
5
6fn make_leaf() -> Box<[SlotEntry<u64>; 16]> {
7 unsafe {
8 let layout = core::alloc::Layout::new::<[SlotEntry<u64>; 16]>();
9 let ptr = std::alloc::alloc_zeroed(layout) as *mut [SlotEntry<u64>; 16];
10 Box::from_raw(ptr)
11 }
12}
13
14fn setup_map(leaf_count: usize) -> (TestMap, Vec<Box<[SlotEntry<u64>; 16]>>) {
15 let mut map = TestMap::new();
16 let leaves: Vec<_> = (0..leaf_count).map(|_| make_leaf()).collect();
17 leaves.iter().for_each(|leaf| {
18 let ptr = &**leaf as *const _ as *mut [SlotEntry<u64>; 16];
19 unsafe { map.expand(ptr) };
20 });
21 (map, leaves)
22}
23
24#[test]
25fn allocate_returns_unique_indices() {
26 let (mut map, _leaves) = setup_map(2);
27 let results: Vec<_> = (0..32u64)
28 .map(|i| map.allocate(i).expect("should allocate"))
29 .collect();
30
31 let indices: std::collections::HashSet<u32> = results.iter().map(|&(idx, _)| idx).collect();
32 assert_eq!(indices.len(), results.len());
33}
34
35#[test]
36fn free_all_then_reallocate_bumps_generation() {
37 let (mut map, _leaves) = setup_map(1);
38 let first_pass: Vec<_> = (0..16u64)
39 .map(|i| map.allocate(i).expect("alloc"))
40 .collect();
41
42 first_pass.iter().for_each(|&(idx, gn)| {
43 let _ = map.free(idx, gn).expect("free");
44 });
45 assert_eq!(map.active_count(), 0);
46
47 let second_pass: Vec<_> = (0..16u64)
48 .map(|i| map.allocate(100 + i).expect("realloc"))
49 .collect();
50
51 second_pass.iter().for_each(|&(_idx, gn)| {
52 assert!(gn >= 1);
53 });
54}
55
56#[test]
57fn stale_generation_lookup_returns_none() {
58 let (mut map, _leaves) = setup_map(1);
59 let (idx, gn) = map.allocate(42).expect("alloc");
60 let _ = map.free(idx, gn).expect("free");
61
62 assert!(map.get_checked(idx, gn).is_none());
63}
64
65#[test]
66fn expand_under_pressure() {
67 let mut map = TestMap::new();
68 let leaf1 = make_leaf();
69 unsafe { map.expand(&*leaf1 as *const _ as *mut _) };
70
71 let first: Vec<_> = (0..16u64)
72 .map(|i| map.allocate(i).expect("alloc from leaf1"))
73 .collect();
74 assert_eq!(map.active_count(), 16);
75 assert!(map.allocate(999).is_none());
76
77 let leaf2 = make_leaf();
78 unsafe { map.expand(&*leaf2 as *const _ as *mut _) };
79
80 let second: Vec<_> = (0..16u64)
81 .map(|i| map.allocate(100 + i).expect("alloc from leaf2"))
82 .collect();
83 assert_eq!(map.active_count(), 32);
84
85 first.iter().chain(second.iter()).for_each(|&(idx, gn)| {
86 assert!(map.get_checked(idx, gn).is_some());
87 });
88
89 std::mem::forget(leaf1);
90 std::mem::forget(leaf2);
91}
92
93#[test]
94fn magazine_fast_path_coverage() {
95 let (mut map, _leaves) = setup_map(2);
96
97 let batch: Vec<_> = (0..32u64)
98 .map(|i| map.allocate(i).expect("alloc"))
99 .collect();
100
101 batch.iter().for_each(|&(idx, gn)| {
102 let _ = map.free(idx, gn).expect("free");
103 });
104
105 let rebatch: Vec<_> = (0..32u64)
106 .map(|i| map.allocate(1000 + i).expect("realloc"))
107 .collect();
108
109 rebatch.iter().for_each(|&(idx, gn)| {
110 assert!(map.get_checked(idx, gn).is_some());
111 });
112}
113
114#[test]
115fn for_each_active_visits_all() {
116 let (mut map, _leaves) = setup_map(2);
117 let allocated: Vec<_> = (0..20u64)
118 .map(|i| map.allocate(i * 10).expect("alloc"))
119 .collect();
120
121 let mut visited = Vec::new();
122 map.for_each_active(|idx, val| visited.push((idx, *val)));
123
124 assert_eq!(visited.len(), 20);
125 allocated.iter().for_each(|&(idx, _gn)| {
126 assert!(visited.iter().any(|&(vi, _)| vi == idx));
127 });
128}
129
130#[test]
131fn get_mut_modifies_payload() {
132 let (mut map, _leaves) = setup_map(1);
133 let (idx, gn) = map.allocate(100u64).expect("alloc");
134
135 *map.get_mut(idx).unwrap() = 200;
136 assert_eq!(*map.get_checked(idx, gn).unwrap(), 200);
137}
138
139proptest! {
140 #[test]
141 fn interleaved_alloc_free_no_corruption(ops in proptest::collection::vec(prop::bool::ANY, 1..200)) {
142 let (mut map, _leaves) = setup_map(4);
143 let mut live: Vec<(u32, u32, u64)> = Vec::new();
144 let mut counter = 0u64;
145
146 ops.iter().for_each(|&do_alloc| {
147 match do_alloc || live.is_empty() {
148 true => {
149 match map.allocate(counter) {
150 Some((idx, gn)) => {
151 live.push((idx, gn, counter));
152 counter += 1;
153 }
154 None => {}
155 }
156 }
157 false => {
158 let i = (counter as usize) % live.len();
159 let (idx, gn, expected_val) = live.swap_remove(i);
160 let val = map.free(idx, gn).unwrap();
161 assert_eq!(val, expected_val);
162 }
163 }
164 });
165
166 assert_eq!(map.active_count(), live.len() as u32);
167
168 live.iter().for_each(|&(idx, gn, expected)| {
169 let val = map.get_checked(idx, gn).unwrap();
170 assert_eq!(*val, expected);
171 });
172 }
173
174 #[test]
175 fn generation_increments_on_free(alloc_count in 1usize..16) {
176 let (mut map, _leaves) = setup_map(1);
177
178 let slots: Vec<_> = (0..alloc_count)
179 .map(|i| map.allocate(i as u64).expect("alloc"))
180 .collect();
181
182 let first_idx = slots[0].0;
183 let first_gen = slots[0].1;
184
185 let _ = map.free(first_idx, first_gen).expect("free");
186 let (re_idx, re_gen) = map.allocate(999).expect("realloc");
187
188 prop_assert!(re_gen > first_gen || re_idx != first_idx);
189 }
190}