diff options
Diffstat (limited to 'compiler/rustc_data_structures/src/work_queue.rs')
-rw-r--r-- | compiler/rustc_data_structures/src/work_queue.rs | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/compiler/rustc_data_structures/src/work_queue.rs b/compiler/rustc_data_structures/src/work_queue.rs new file mode 100644 index 000000000..10317f1af --- /dev/null +++ b/compiler/rustc_data_structures/src/work_queue.rs @@ -0,0 +1,44 @@ +use rustc_index::bit_set::BitSet; +use rustc_index::vec::Idx; +use std::collections::VecDeque; + +/// A work queue is a handy data structure for tracking work left to +/// do. (For example, basic blocks left to process.) It is basically a +/// de-duplicating queue; so attempting to insert X if X is already +/// enqueued has no effect. This implementation assumes that the +/// elements are dense indices, so it can allocate the queue to size +/// and also use a bit set to track occupancy. +pub struct WorkQueue<T: Idx> { + deque: VecDeque<T>, + set: BitSet<T>, +} + +impl<T: Idx> WorkQueue<T> { + /// Creates a new work queue that starts empty, where elements range from (0..len). + #[inline] + pub fn with_none(len: usize) -> Self { + WorkQueue { deque: VecDeque::with_capacity(len), set: BitSet::new_empty(len) } + } + + /// Attempt to enqueue `element` in the work queue. Returns false if it was already present. + #[inline] + pub fn insert(&mut self, element: T) -> bool { + if self.set.insert(element) { + self.deque.push_back(element); + true + } else { + false + } + } + + /// Attempt to pop an element from the work queue. + #[inline] + pub fn pop(&mut self) -> Option<T> { + if let Some(element) = self.deque.pop_front() { + self.set.remove(element); + Some(element) + } else { + None + } + } +} |