]>
Commit | Line | Data |
---|---|---|
e74abb32 XL |
1 | use rustc_index::bit_set::BitSet; |
2 | use rustc_index::vec::Idx; | |
8faf50e0 XL |
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>, | |
0bf4aa26 | 13 | set: BitSet<T>, |
8faf50e0 XL |
14 | } |
15 | ||
16 | impl<T: Idx> WorkQueue<T> { | |
9fa01778 | 17 | /// Creates a new work queue with all the elements from (0..len). |
8faf50e0 XL |
18 | #[inline] |
19 | pub fn with_all(len: usize) -> Self { | |
dfeec247 | 20 | WorkQueue { deque: (0..len).map(T::new).collect(), set: BitSet::new_filled(len) } |
8faf50e0 XL |
21 | } |
22 | ||
9fa01778 | 23 | /// Creates a new work queue that starts empty, where elements range from (0..len). |
8faf50e0 XL |
24 | #[inline] |
25 | pub fn with_none(len: usize) -> Self { | |
dfeec247 | 26 | WorkQueue { deque: VecDeque::with_capacity(len), set: BitSet::new_empty(len) } |
8faf50e0 XL |
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 { | |
0bf4aa26 | 32 | if self.set.insert(element) { |
8faf50e0 XL |
33 | self.deque.push_back(element); |
34 | true | |
35 | } else { | |
36 | false | |
37 | } | |
38 | } | |
39 | ||
0bf4aa26 | 40 | /// Attempt to pop an element from the work queue. |
8faf50e0 XL |
41 | #[inline] |
42 | pub fn pop(&mut self) -> Option<T> { | |
43 | if let Some(element) = self.deque.pop_front() { | |
0bf4aa26 | 44 | self.set.remove(element); |
8faf50e0 XL |
45 | Some(element) |
46 | } else { | |
47 | None | |
48 | } | |
49 | } | |
50 | ||
9fa01778 | 51 | /// Returns `true` if nothing is enqueued. |
8faf50e0 XL |
52 | #[inline] |
53 | pub fn is_empty(&self) -> bool { | |
54 | self.deque.is_empty() | |
55 | } | |
56 | } |