From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_data_structures/src/work_queue.rs | 44 ++++++++++++++++++++++++ 1 file changed, 44 insertions(+) create mode 100644 compiler/rustc_data_structures/src/work_queue.rs (limited to 'compiler/rustc_data_structures/src/work_queue.rs') diff --git a/compiler/rustc_data_structures/src/work_queue.rs b/compiler/rustc_data_structures/src/work_queue.rs new file mode 100644 index 000000000..10317f1af --- /dev/null +++ b/compiler/rustc_data_structures/src/work_queue.rs @@ -0,0 +1,44 @@ +use rustc_index::bit_set::BitSet; +use rustc_index::vec::Idx; +use std::collections::VecDeque; + +/// A work queue is a handy data structure for tracking work left to +/// do. (For example, basic blocks left to process.) It is basically a +/// de-duplicating queue; so attempting to insert X if X is already +/// enqueued has no effect. This implementation assumes that the +/// elements are dense indices, so it can allocate the queue to size +/// and also use a bit set to track occupancy. +pub struct WorkQueue { + deque: VecDeque, + set: BitSet, +} + +impl WorkQueue { + /// Creates a new work queue that starts empty, where elements range from (0..len). + #[inline] + pub fn with_none(len: usize) -> Self { + WorkQueue { deque: VecDeque::with_capacity(len), set: BitSet::new_empty(len) } + } + + /// Attempt to enqueue `element` in the work queue. Returns false if it was already present. + #[inline] + pub fn insert(&mut self, element: T) -> bool { + if self.set.insert(element) { + self.deque.push_back(element); + true + } else { + false + } + } + + /// Attempt to pop an element from the work queue. + #[inline] + pub fn pop(&mut self) -> Option { + if let Some(element) = self.deque.pop_front() { + self.set.remove(element); + Some(element) + } else { + None + } + } +} -- cgit v1.2.3