rustc_data_structures/
work_queue.rs

Help
1use std::collections::VecDeque;
2
3use rustc_index::Idx;
4use rustc_index::bit_set::DenseBitSet;
5
6/// A work queue is a handy data structure for tracking work left to
7/// do. (For example, basic blocks left to process.) It is basically a
8/// de-duplicating queue; so attempting to insert X if X is already
9/// enqueued has no effect. This implementation assumes that the
10/// elements are dense indices, so it can allocate the queue to size
11/// and also use a bit set to track occupancy.
12pub struct WorkQueue<T: Idx> {
13    deque: VecDeque<T>,
14    set: DenseBitSet<T>,
15}
16
17impl<T: Idx> WorkQueue<T> {
18    /// Creates a new work queue that starts empty, where elements range from (0..len).
19    #[inline]
20    pub fn with_none(len: usize) -> Self {
21        WorkQueue { deque: VecDeque::with_capacity(len), set: DenseBitSet::new_empty(len) }
22    }
23
24    /// Attempt to enqueue `element` in the work queue. Returns false if it was already present.
25    #[inline]
26    pub fn insert(&mut self, element: T) -> bool {
27        if self.set.insert(element) {
28            self.deque.push_back(element);
29            true
30        } else {
31            false
32        }
33    }
34
35    /// Attempt to pop an element from the work queue.
36    #[inline]
37    pub fn pop(&mut self) -> Option<T> {
38        if let Some(element) = self.deque.pop_front() {
39            self.set.remove(element);
40            Some(element)
41        } else {
42            None
43        }
44    }
45}
rustc_data_structures/work_queue.rs

rustc_data_structures/
work_queue.rs
