Skip to main content

gpui/
queue.rs

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            // Synchronize with the empty/disconnected check before a receiver
163            // waits, so closing the queue cannot lose its wakeup.
164            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    /// Returns whether the queue currently contains no elements.
230    pub fn is_empty(&self) -> bool {
231        self.state.queues.lock().is_empty()
232    }
233
234    /// Tries to pop one element from the priority queue without blocking.
235    ///
236    /// This will early return if there are no elements in the queue.
237    ///
238    /// This method is best suited if you only intend to pop one element, for better performance
239    /// on large queues see [`Self::try_iter`]
240    ///
241    /// # Errors
242    ///
243    /// If the sender was dropped
244    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    /// Pops an element from the priority queue blocking if necessary.
287    ///
288    /// This method is best suited if you only intend to pop one element, for better performance
289    /// on large queues see [`Self::iter`]
290    ///
291    /// # Errors
292    ///
293    /// If the sender was dropped
294    pub fn pop(&mut self) -> Result<T, RecvError> {
295        self.pop_inner(true).map(|e| e.unwrap())
296    }
297
298    /// Returns an iterator over the elements of the queue
299    /// this iterator will end when all elements have been consumed and will not wait for new ones.
300    pub fn try_iter(self) -> TryIter<T> {
301        TryIter {
302            receiver: self,
303            ended: false,
304        }
305    }
306
307    /// Returns an iterator over the elements of the queue
308    /// this iterator will wait for new elements if the queue is empty.
309    pub fn iter(self) -> Iter<T> {
310        Iter(self)
311    }
312
313    #[inline(always)]
314    // algorithm is the loaded die from biased coin from
315    // https://www.keithschwarz.com/darts-dice-coins/
316    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; //%
332
333        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        // Wait until both receivers have entered the condition variable. The
425        // wakeups also exercise rechecking disconnection after a spurious wake.
426        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}