Nothing to see here, move along meow
1use lancer_core::header::NONE_SENTINEL;
2use lancer_core::intrusive_list::ListLinks;
3use lancer_core::run_queue::{RunQueue, RunQueueTag};
4use proptest::prelude::*;
5
6const MAX_ENTRIES: usize = 512;
7
8struct TestStorage {
9 rq_next: [u32; MAX_ENTRIES],
10 rq_prev: [u32; MAX_ENTRIES],
11}
12
13impl TestStorage {
14 fn new() -> Self {
15 Self {
16 rq_next: [NONE_SENTINEL; MAX_ENTRIES],
17 rq_prev: [NONE_SENTINEL; MAX_ENTRIES],
18 }
19 }
20}
21
22impl ListLinks<RunQueueTag> for TestStorage {
23 fn link_next(&self, id: u32) -> u32 {
24 self.rq_next[id as usize]
25 }
26 fn link_prev(&self, id: u32) -> u32 {
27 self.rq_prev[id as usize]
28 }
29 fn set_link_next(&mut self, id: u32, next: u32) {
30 self.rq_next[id as usize] = next;
31 }
32 fn set_link_prev(&mut self, id: u32, prev: u32) {
33 self.rq_prev[id as usize] = prev;
34 }
35}
36
37#[test]
38fn priority_ordering_descending() {
39 let mut rq = RunQueue::new();
40 let mut store = TestStorage::new();
41
42 rq.enqueue(0, 10, &mut store);
43 rq.enqueue(1, 50, &mut store);
44 rq.enqueue(2, 200, &mut store);
45 rq.enqueue(3, 1, &mut store);
46
47 let (id, prio) = rq.dequeue_highest(&mut store).unwrap();
48 assert_eq!((id, prio), (2, 200));
49
50 let (id, prio) = rq.dequeue_highest(&mut store).unwrap();
51 assert_eq!((id, prio), (1, 50));
52
53 let (id, prio) = rq.dequeue_highest(&mut store).unwrap();
54 assert_eq!((id, prio), (0, 10));
55
56 let (id, prio) = rq.dequeue_highest(&mut store).unwrap();
57 assert_eq!((id, prio), (3, 1));
58
59 assert!(rq.dequeue_highest(&mut store).is_none());
60}
61
62#[test]
63fn fifo_within_same_priority() {
64 let mut rq = RunQueue::new();
65 let mut store = TestStorage::new();
66
67 rq.enqueue(10, 5, &mut store);
68 rq.enqueue(20, 5, &mut store);
69 rq.enqueue(30, 5, &mut store);
70
71 assert_eq!(rq.dequeue_highest(&mut store).unwrap().0, 10);
72 assert_eq!(rq.dequeue_highest(&mut store).unwrap().0, 20);
73 assert_eq!(rq.dequeue_highest(&mut store).unwrap().0, 30);
74 assert!(rq.dequeue_highest(&mut store).is_none());
75}
76
77#[test]
78fn remove_from_middle() {
79 let mut rq = RunQueue::new();
80 let mut store = TestStorage::new();
81
82 rq.enqueue(0, 5, &mut store);
83 rq.enqueue(1, 5, &mut store);
84 rq.enqueue(2, 5, &mut store);
85
86 rq.remove(1, 5, &mut store);
87
88 assert_eq!(rq.dequeue_highest(&mut store).unwrap().0, 0);
89 assert_eq!(rq.dequeue_highest(&mut store).unwrap().0, 2);
90 assert!(rq.dequeue_highest(&mut store).is_none());
91}
92
93#[test]
94fn remove_head() {
95 let mut rq = RunQueue::new();
96 let mut store = TestStorage::new();
97
98 rq.enqueue(0, 5, &mut store);
99 rq.enqueue(1, 5, &mut store);
100
101 rq.remove(0, 5, &mut store);
102
103 assert_eq!(rq.dequeue_highest(&mut store).unwrap().0, 1);
104 assert!(rq.dequeue_highest(&mut store).is_none());
105}
106
107#[test]
108fn remove_tail() {
109 let mut rq = RunQueue::new();
110 let mut store = TestStorage::new();
111
112 rq.enqueue(0, 5, &mut store);
113 rq.enqueue(1, 5, &mut store);
114
115 rq.remove(1, 5, &mut store);
116
117 assert_eq!(rq.dequeue_highest(&mut store).unwrap().0, 0);
118 assert!(rq.dequeue_highest(&mut store).is_none());
119}
120
121#[test]
122fn remove_only_element() {
123 let mut rq = RunQueue::new();
124 let mut store = TestStorage::new();
125
126 rq.enqueue(42, 100, &mut store);
127 rq.remove(42, 100, &mut store);
128
129 assert!(rq.is_empty());
130 assert!(rq.dequeue_highest(&mut store).is_none());
131}
132
133#[test]
134fn all_256_priorities() {
135 let mut rq = RunQueue::new();
136 let mut store = TestStorage::new();
137
138 (0..=255u8).for_each(|p| {
139 rq.enqueue(p as u32, p, &mut store);
140 });
141
142 let mut last_prio = 255u8;
143 (0..256).for_each(|_| {
144 let (id, prio) = rq.dequeue_highest(&mut store).unwrap();
145 assert_eq!(prio, last_prio);
146 assert_eq!(id, last_prio as u32);
147 last_prio = last_prio.wrapping_sub(1);
148 });
149
150 assert!(rq.is_empty());
151}
152
153#[test]
154fn empty_after_full_drain() {
155 let mut rq = RunQueue::new();
156 let mut store = TestStorage::new();
157
158 (0..100u32).for_each(|i| {
159 rq.enqueue(i, (i % 10) as u8, &mut store);
160 });
161
162 let mut count = 0u32;
163 while rq.dequeue_highest(&mut store).is_some() {
164 count += 1;
165 }
166 assert_eq!(count, 100);
167 assert!(rq.is_empty());
168}
169
170proptest! {
171 #[test]
172 fn random_enqueue_dequeue_consistency(
173 ops in proptest::collection::vec(
174 (0u32..256, 0u8..=255),
175 1..200
176 )
177 ) {
178 let mut rq = RunQueue::new();
179 let mut store = TestStorage::new();
180 let mut enqueued: Vec<(u32, u8)> = Vec::new();
181
182 ops.iter().for_each(|&(id, prio)| {
183 let actual_id = id % MAX_ENTRIES as u32;
184 if !enqueued.iter().any(|&(eid, _)| eid == actual_id) {
185 rq.enqueue(actual_id, prio, &mut store);
186 enqueued.push((actual_id, prio));
187 }
188 });
189
190 let mut dequeued = Vec::new();
191 while let Some((id, prio)) = rq.dequeue_highest(&mut store) {
192 dequeued.push((id, prio));
193 }
194
195 assert_eq!(dequeued.len(), enqueued.len());
196
197 dequeued.windows(2).for_each(|w| {
198 assert!(w[0].1 >= w[1].1);
199 });
200
201 assert!(rq.is_empty());
202 }
203
204 #[test]
205 fn interleaved_enqueue_remove_dequeue(
206 entries in proptest::collection::vec(
207 (0u32..128, 0u8..64),
208 1..50
209 ),
210 remove_indices in proptest::collection::vec(0usize..50, 0..20)
211 ) {
212 let mut rq = RunQueue::new();
213 let mut store = TestStorage::new();
214 let mut active: Vec<(u32, u8)> = Vec::new();
215
216 entries.iter().for_each(|&(id, prio)| {
217 if !active.iter().any(|&(eid, _)| eid == id) {
218 rq.enqueue(id, prio, &mut store);
219 active.push((id, prio));
220 }
221 });
222
223 remove_indices.iter().for_each(|&idx| {
224 if !active.is_empty() {
225 let rm_idx = idx % active.len();
226 let (id, prio) = active.remove(rm_idx);
227 rq.remove(id, prio, &mut store);
228 }
229 });
230
231 let mut dequeued = Vec::new();
232 while let Some((id, prio)) = rq.dequeue_highest(&mut store) {
233 dequeued.push((id, prio));
234 }
235
236 assert_eq!(dequeued.len(), active.len());
237
238 dequeued.windows(2).for_each(|w| {
239 assert!(w[0].1 >= w[1].1);
240 });
241
242 assert!(rq.is_empty());
243 }
244}