1use std::{
2 collections::VecDeque,
3 fmt,
4 iter::FusedIterator,
5 sync::{Arc, atomic::AtomicUsize},
6};
7
8use rand::{Rng, SeedableRng, rngs::SmallRng};
9
10use crate::Priority;
11
12struct PriorityQueues<T> {
13 high_priority: VecDeque<T>,
14 medium_priority: VecDeque<T>,
15 low_priority: VecDeque<T>,
16}
17
18impl<T> PriorityQueues<T> {
19 fn is_empty(&self) -> bool {
20 self.high_priority.is_empty()
21 && self.medium_priority.is_empty()
22 && self.low_priority.is_empty()
23 }
24}
25
26struct PriorityQueueState<T> {
27 queues: parking_lot::Mutex<PriorityQueues<T>>,
28 condvar: parking_lot::Condvar,
29 receiver_count: AtomicUsize,
30 sender_count: AtomicUsize,
31}
32
33impl<T> PriorityQueueState<T> {
34 fn send(&self, priority: Priority, item: T) -> Result<(), SendError<T>> {
35 if self
36 .receiver_count
37 .load(std::sync::atomic::Ordering::Relaxed)
38 == 0
39 {
40 return Err(SendError(item));
41 }
42
43 let mut queues = self.queues.lock();
44 Self::push(&mut queues, priority, item);
45 self.condvar.notify_one();
46 Ok(())
47 }
48
49 fn spin_send(&self, priority: Priority, item: T) -> Result<(), SendError<T>> {
50 if self
51 .receiver_count
52 .load(std::sync::atomic::Ordering::Relaxed)
53 == 0
54 {
55 return Err(SendError(item));
56 }
57
58 let mut queues = loop {
59 if let Some(guard) = self.queues.try_lock() {
60 break guard;
61 }
62 std::hint::spin_loop();
63 };
64 Self::push(&mut queues, priority, item);
65 self.condvar.notify_one();
66 Ok(())
67 }
68
69 fn push(queues: &mut PriorityQueues<T>, priority: Priority, item: T) {
70 match priority {
71 Priority::RealtimeAudio => unreachable!(
72 "Realtime audio priority runs on a dedicated thread and is never queued"
73 ),
74 Priority::High => queues.high_priority.push_back(item),
75 Priority::Medium => queues.medium_priority.push_back(item),
76 Priority::Low => queues.low_priority.push_back(item),
77 };
78 }
79
80 fn recv<'a>(&'a self) -> Result<parking_lot::MutexGuard<'a, PriorityQueues<T>>, RecvError> {
81 let mut queues = self.queues.lock();
82
83 while queues.is_empty() {
84 if self.sender_count.load(std::sync::atomic::Ordering::Acquire) == 0 {
85 return Err(RecvError);
86 }
87 self.condvar.wait(&mut queues);
88 }
89
90 Ok(queues)
91 }
92
93 fn try_recv<'a>(
94 &'a self,
95 ) -> Result<Option<parking_lot::MutexGuard<'a, PriorityQueues<T>>>, RecvError> {
96 let mut queues = self.queues.lock();
97
98 let sender_count = self.sender_count.load(std::sync::atomic::Ordering::Relaxed);
99 if queues.is_empty() && sender_count == 0 {
100 return Err(crate::queue::RecvError);
101 }
102
103 if queues.is_empty() {
104 Ok(None)
105 } else {
106 Ok(Some(queues))
107 }
108 }
109
110 fn spin_try_recv<'a>(
111 &'a self,
112 ) -> Result<Option<parking_lot::MutexGuard<'a, PriorityQueues<T>>>, RecvError> {
113 let queues = loop {
114 if let Some(guard) = self.queues.try_lock() {
115 break guard;
116 }
117 std::hint::spin_loop();
118 };
119
120 let sender_count = self.sender_count.load(std::sync::atomic::Ordering::Relaxed);
121 if queues.is_empty() && sender_count == 0 {
122 return Err(crate::queue::RecvError);
123 }
124
125 if queues.is_empty() {
126 Ok(None)
127 } else {
128 Ok(Some(queues))
129 }
130 }
131}
132
133#[doc(hidden)]
134pub struct PriorityQueueSender<T> {
135 state: Arc<PriorityQueueState<T>>,
136}
137
138impl<T> PriorityQueueSender<T> {
139 fn new(state: Arc<PriorityQueueState<T>>) -> Self {
140 Self { state }
141 }
142
143 pub fn send(&self, priority: Priority, item: T) -> Result<(), SendError<T>> {
144 self.state.send(priority, item)?;
145 Ok(())
146 }
147
148 pub fn spin_send(&self, priority: Priority, item: T) -> Result<(), SendError<T>> {
149 self.state.spin_send(priority, item)?;
150 Ok(())
151 }
152}
153
154impl<T> Drop for PriorityQueueSender<T> {
155 fn drop(&mut self) {
156 if self
157 .state
158 .sender_count
159 .fetch_sub(1, std::sync::atomic::Ordering::AcqRel)
160 == 1
161 {
162 let _queues = self.state.queues.lock();
165 self.state.condvar.notify_all();
166 }
167 }
168}
169
170#[doc(hidden)]
171pub struct PriorityQueueReceiver<T> {
172 state: Arc<PriorityQueueState<T>>,
173 rand: SmallRng,
174 disconnected: bool,
175}
176
177impl<T> Clone for PriorityQueueReceiver<T> {
178 fn clone(&self) -> Self {
179 self.state
180 .receiver_count
181 .fetch_add(1, std::sync::atomic::Ordering::AcqRel);
182 Self {
183 state: Arc::clone(&self.state),
184 rand: SmallRng::seed_from_u64(0),
185 disconnected: self.disconnected,
186 }
187 }
188}
189
190#[doc(hidden)]
191pub struct SendError<T>(pub T);
192
193impl<T: fmt::Debug> fmt::Debug for SendError<T> {
194 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
195 f.debug_tuple("SendError").field(&self.0).finish()
196 }
197}
198
199#[derive(Debug)]
200#[doc(hidden)]
201pub struct RecvError;
202
203#[allow(dead_code)]
204impl<T> PriorityQueueReceiver<T> {
205 pub fn new() -> (PriorityQueueSender<T>, Self) {
206 let state = PriorityQueueState {
207 queues: parking_lot::Mutex::new(PriorityQueues {
208 high_priority: VecDeque::new(),
209 medium_priority: VecDeque::new(),
210 low_priority: VecDeque::new(),
211 }),
212 condvar: parking_lot::Condvar::new(),
213 receiver_count: AtomicUsize::new(1),
214 sender_count: AtomicUsize::new(1),
215 };
216 let state = Arc::new(state);
217
218 let sender = PriorityQueueSender::new(Arc::clone(&state));
219
220 let receiver = PriorityQueueReceiver {
221 state,
222 rand: SmallRng::seed_from_u64(0),
223 disconnected: false,
224 };
225
226 (sender, receiver)
227 }
228
229 pub fn is_empty(&self) -> bool {
231 self.state.queues.lock().is_empty()
232 }
233
234 pub fn try_pop(&mut self) -> Result<Option<T>, RecvError> {
245 self.pop_inner(false)
246 }
247
248 pub fn spin_try_pop(&mut self) -> Result<Option<T>, RecvError> {
249 use Priority as P;
250
251 let Some(mut queues) = self.state.spin_try_recv()? else {
252 return Ok(None);
253 };
254
255 let high = P::High.weight() * !queues.high_priority.is_empty() as u32;
256 let medium = P::Medium.weight() * !queues.medium_priority.is_empty() as u32;
257 let low = P::Low.weight() * !queues.low_priority.is_empty() as u32;
258 let mut mass = high + medium + low;
259
260 if !queues.high_priority.is_empty() {
261 let flip = self.rand.random_ratio(P::High.weight(), mass);
262 if flip {
263 return Ok(queues.high_priority.pop_front());
264 }
265 mass -= P::High.weight();
266 }
267
268 if !queues.medium_priority.is_empty() {
269 let flip = self.rand.random_ratio(P::Medium.weight(), mass);
270 if flip {
271 return Ok(queues.medium_priority.pop_front());
272 }
273 mass -= P::Medium.weight();
274 }
275
276 if !queues.low_priority.is_empty() {
277 let flip = self.rand.random_ratio(P::Low.weight(), mass);
278 if flip {
279 return Ok(queues.low_priority.pop_front());
280 }
281 }
282
283 Ok(None)
284 }
285
286 pub fn pop(&mut self) -> Result<T, RecvError> {
295 self.pop_inner(true).map(|e| e.unwrap())
296 }
297
298 pub fn try_iter(self) -> TryIter<T> {
301 TryIter {
302 receiver: self,
303 ended: false,
304 }
305 }
306
307 pub fn iter(self) -> Iter<T> {
310 Iter(self)
311 }
312
313 #[inline(always)]
314 fn pop_inner(&mut self, block: bool) -> Result<Option<T>, RecvError> {
317 use Priority as P;
318
319 let mut queues = if !block {
320 let Some(queues) = self.state.try_recv()? else {
321 return Ok(None);
322 };
323 queues
324 } else {
325 self.state.recv()?
326 };
327
328 let high = P::High.weight() * !queues.high_priority.is_empty() as u32;
329 let medium = P::Medium.weight() * !queues.medium_priority.is_empty() as u32;
330 let low = P::Low.weight() * !queues.low_priority.is_empty() as u32;
331 let mut mass = high + medium + low; if !queues.high_priority.is_empty() {
334 let flip = self.rand.random_ratio(P::High.weight(), mass);
335 if flip {
336 return Ok(queues.high_priority.pop_front());
337 }
338 mass -= P::High.weight();
339 }
340
341 if !queues.medium_priority.is_empty() {
342 let flip = self.rand.random_ratio(P::Medium.weight(), mass);
343 if flip {
344 return Ok(queues.medium_priority.pop_front());
345 }
346 mass -= P::Medium.weight();
347 }
348
349 if !queues.low_priority.is_empty() {
350 let flip = self.rand.random_ratio(P::Low.weight(), mass);
351 if flip {
352 return Ok(queues.low_priority.pop_front());
353 }
354 }
355
356 Ok(None)
357 }
358}
359
360impl<T> Drop for PriorityQueueReceiver<T> {
361 fn drop(&mut self) {
362 self.state
363 .receiver_count
364 .fetch_sub(1, std::sync::atomic::Ordering::AcqRel);
365 }
366}
367
368#[doc(hidden)]
369pub struct Iter<T>(PriorityQueueReceiver<T>);
370impl<T> Iterator for Iter<T> {
371 type Item = T;
372
373 fn next(&mut self) -> Option<Self::Item> {
374 self.0.pop().ok()
375 }
376}
377impl<T> FusedIterator for Iter<T> {}
378
379#[doc(hidden)]
380pub struct TryIter<T> {
381 receiver: PriorityQueueReceiver<T>,
382 ended: bool,
383}
384impl<T> Iterator for TryIter<T> {
385 type Item = Result<T, RecvError>;
386
387 fn next(&mut self) -> Option<Self::Item> {
388 if self.ended {
389 return None;
390 }
391
392 let res = self.receiver.try_pop();
393 self.ended = !matches!(res, Ok(Some(_)));
394
395 res.transpose()
396 }
397}
398impl<T> FusedIterator for TryIter<T> {}
399
400#[cfg(test)]
401mod tests {
402 use collections::HashSet;
403
404 use super::*;
405
406 #[test]
407 fn dropping_sender_wakes_all_blocked_receivers() {
408 use std::{
409 sync::mpsc,
410 thread,
411 time::{Duration, Instant},
412 };
413
414 let (tx, rx) = PriorityQueueReceiver::<usize>::new();
415 let state = Arc::clone(&rx.state);
416 let (completed, completion) = mpsc::channel();
417 let threads: Vec<_> = [rx.clone(), rx]
418 .into_iter()
419 .map(|mut rx| {
420 let completed = completed.clone();
421 thread::spawn(move || completed.send(rx.pop().is_err()).unwrap())
422 })
423 .collect();
424 let deadline = Instant::now() + Duration::from_secs(5);
427 loop {
428 if state.condvar.notify_all() == 2 {
429 break;
430 }
431 assert!(Instant::now() < deadline, "receivers did not start waiting");
432 thread::sleep(Duration::from_millis(1));
433 }
434 drop(tx);
435 for _ in 0..2 {
436 assert!(
437 completion
438 .recv_timeout(Duration::from_secs(5))
439 .expect("receiver did not wake")
440 );
441 }
442 for thread in threads {
443 thread.join().unwrap();
444 }
445 }
446
447 #[test]
448 fn try_iterator_stays_exhausted_after_empty_queue() {
449 let (tx, rx) = PriorityQueueReceiver::new();
450 let mut iter = rx.try_iter();
451 assert!(iter.next().is_none());
452 tx.send(Priority::Medium, 1).unwrap();
453 assert!(iter.next().is_none());
454 }
455
456 #[test]
457 fn all_tasks_get_yielded() {
458 let (tx, mut rx) = PriorityQueueReceiver::new();
459 tx.send(Priority::Medium, 20).unwrap();
460 tx.send(Priority::High, 30).unwrap();
461 tx.send(Priority::Low, 10).unwrap();
462 tx.send(Priority::Medium, 21).unwrap();
463 tx.send(Priority::High, 31).unwrap();
464
465 drop(tx);
466
467 assert_eq!(
468 rx.iter().collect::<HashSet<_>>(),
469 [30, 31, 20, 21, 10].into_iter().collect::<HashSet<_>>()
470 )
471 }
472
473 #[test]
474 fn new_high_prio_task_get_scheduled_quickly() {
475 let (tx, mut rx) = PriorityQueueReceiver::new();
476 for _ in 0..100 {
477 tx.send(Priority::Low, 1).unwrap();
478 }
479
480 assert_eq!(rx.pop().unwrap(), 1);
481 tx.send(Priority::High, 3).unwrap();
482 assert_eq!(rx.pop().unwrap(), 3);
483 assert_eq!(rx.pop().unwrap(), 1);
484 }
485}