flux_refineck/
queue.rs

1use std::collections::BinaryHeap;
2
3use rustc_index::{IndexVec, bit_set::DenseBitSet};
4use rustc_middle::mir::BasicBlock;
5
6struct Item<'a> {
7    bb: BasicBlock,
8    dominator_order_rank: &'a IndexVec<BasicBlock, u32>,
9}
10
11pub(crate) struct WorkQueue<'a> {
12    heap: BinaryHeap<Item<'a>>,
13    set: DenseBitSet<BasicBlock>,
14    dominator_order_rank: &'a IndexVec<BasicBlock, u32>,
15}
16
17impl<'a> WorkQueue<'a> {
18    pub(crate) fn empty(len: usize, dominator_order_rank: &'a IndexVec<BasicBlock, u32>) -> Self {
19        Self {
20            heap: BinaryHeap::with_capacity(len),
21            set: DenseBitSet::new_empty(len),
22            dominator_order_rank,
23        }
24    }
25
26    pub(crate) fn insert(&mut self, bb: BasicBlock) -> bool {
27        if self.set.insert(bb) {
28            self.heap
29                .push(Item { bb, dominator_order_rank: self.dominator_order_rank });
30            true
31        } else {
32            false
33        }
34    }
35
36    pub(crate) fn pop(&mut self) -> Option<BasicBlock> {
37        if let Some(Item { bb, .. }) = self.heap.pop() {
38            self.set.remove(bb);
39            Some(bb)
40        } else {
41            None
42        }
43    }
44}
45
46impl PartialEq for Item<'_> {
47    fn eq(&self, other: &Self) -> bool {
48        self.bb == other.bb
49    }
50}
51
52impl PartialOrd for Item<'_> {
53    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
54        Some(self.cmp(other))
55    }
56}
57
58impl Eq for Item<'_> {}
59
60impl Ord for Item<'_> {
61    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
62        self.dominator_order_rank[other.bb].cmp(&self.dominator_order_rank[self.bb])
63    }
64}
flux_refineck/queue.rs

flux_refineck/
queue.rs
