src/librustc_data_structures/work_queue.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use bit_set::BitSet;
  12 use indexed_vec::Idx;
  13 use std::collections::VecDeque;
  14
  15 /// A work queue is a handy data structure for tracking work left to
  16 /// do. (For example, basic blocks left to process.) It is basically a
  17 /// de-duplicating queue; so attempting to insert X if X is already
  18 /// enqueued has no effect. This implementation assumes that the
  19 /// elements are dense indices, so it can allocate the queue to size
  20 /// and also use a bit set to track occupancy.
  21 pub struct WorkQueue<T: Idx> {
  22     deque: VecDeque<T>,
  23     set: BitSet<T>,
  24 }
  25
  26 impl<T: Idx> WorkQueue<T> {
  27     /// Create a new work queue with all the elements from (0..len).
  28     #[inline]
  29     pub fn with_all(len: usize) -> Self {
  30         WorkQueue {
  31             deque: (0..len).map(T::new).collect(),
  32             set: BitSet::new_filled(len),
  33         }
  34     }
  35
  36     /// Create a new work queue that starts empty, where elements range from (0..len).
  37     #[inline]
  38     pub fn with_none(len: usize) -> Self {
  39         WorkQueue {
  40             deque: VecDeque::with_capacity(len),
  41             set: BitSet::new_empty(len),
  42         }
  43     }
  44
  45     /// Attempt to enqueue `element` in the work queue. Returns false if it was already present.
  46     #[inline]
  47     pub fn insert(&mut self, element: T) -> bool {
  48         if self.set.insert(element) {
  49             self.deque.push_back(element);
  50             true
  51         } else {
  52             false
  53         }
  54     }
  55
  56     /// Attempt to pop an element from the work queue.
  57     #[inline]
  58     pub fn pop(&mut self) -> Option<T> {
  59         if let Some(element) = self.deque.pop_front() {
  60             self.set.remove(element);
  61             Some(element)
  62         } else {
  63             None
  64         }
  65     }
  66
  67     /// True if nothing is enqueued.
  68     #[inline]
  69     pub fn is_empty(&self) -> bool {
  70         self.deque.is_empty()
  71     }
  72 }