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 with all the elements from (0..len).
  18     #[inline]
  19     pub fn with_all(len: usize) -> Self {
  20         WorkQueue { deque: (0..len).map(T::new).collect(), set: BitSet::new_filled(len) }
  21     }
  22
  23     /// Creates a new work queue that starts empty, where elements range from (0..len).
  24     #[inline]
  25     pub fn with_none(len: usize) -> Self {
  26         WorkQueue { deque: VecDeque::with_capacity(len), set: BitSet::new_empty(len) }
  27     }
  28
  29     /// Attempt to enqueue `element` in the work queue. Returns false if it was already present.
  30     #[inline]
  31     pub fn insert(&mut self, element: T) -> bool {
  32         if self.set.insert(element) {
  33             self.deque.push_back(element);
  34             true
  35         } else {
  36             false
  37         }
  38     }
  39
  40     /// Attempt to pop an element from the work queue.
  41     #[inline]
  42     pub fn pop(&mut self) -> Option<T> {
  43         if let Some(element) = self.deque.pop_front() {
  44             self.set.remove(element);
  45             Some(element)
  46         } else {
  47             None
  48         }
  49     }
  50
  51     /// Returns `true` if nothing is enqueued.
  52     #[inline]
  53     pub fn is_empty(&self) -> bool {
  54         self.deque.is_empty()
  55     }
  56 }