compiler/rustc_data_structures/src/work_queue.rs

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