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