open_vaf/data_structures/
work_queue.rs

1/*
2
3 * ******************************************************************************************
4 * Copyright (c) 2019 Pascal Kuthe. This file is part of the OpenVAF project.
5 * It is subject to the license terms in the LICENSE file found in the top-level directory
6 *  of this distribution and at  https://gitlab.com/DSPOM/OpenVAF/blob/master/LICENSE.
7 *  No part of OpenVAF, including this file, may be copied, modified, propagated, or
8 *  distributed except according to the terms contained in the LICENSE file.
9 * *****************************************************************************************
10
11 Adapted from https://github.com/rust-lang/rust src/librustc_data_structures/work_queue.rs under MIT-License
12
13    Permission is hereby granted, free of charge, to any person obtaining a copy
14    of this software and associated documentation files (the "Software"), to deal
15    in the Software without restriction, including without limitation the rights
16    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17    copies of the Software, and to permit persons to whom the Software is
18    furnished to do so, subject to the following conditions:
19
20    The above copyright notice and this permission notice shall be included in all
21    copies or substantial portions of the Software.
22
23    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
24    ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
25    TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
26    PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
27    SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
28    CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29    OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
30    IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
31    DEALINGS IN THE SOFTWARE.
32*/
33
34use crate::data_structures::BitSet;
35use bitflags::_core::fmt::Formatter;
36use index_vec::Idx;
37use std::collections::VecDeque;
38use std::fmt::Debug;
39use std::iter::FromIterator;
40
41/// A work queue is a handy data structure for tracking work left to
42/// do. (For example, basic blocks left to process.) It is basically a
43/// de-duplicating queue; so attempting to insert X if X is already
44/// enqueued has no effect. This implementation assumes that the
45/// elements are dense indices, so it can allocate the queue to size
46/// and also use a bit set to track occupancy.
47pub struct WorkQueue<T: Idx + From<usize>> {
48    pub deque: VecDeque<T>,
49    pub set: BitSet<T>,
50}
51
52impl<T: Idx + From<usize>> WorkQueue<T> {
53    /// Creates a new work queue with all the elements from (0..len).
54    #[inline]
55    pub fn with_all(len_idx: T) -> Self {
56        WorkQueue {
57            deque: (0..len_idx.index()).map(T::from_usize).collect(),
58            set: BitSet::new_filled(len_idx),
59        }
60    }
61
62    /// Creates a new work queue that starts empty, where elements range from (0..len).
63    #[inline]
64    pub fn with_none(len_idx: T) -> Self {
65        WorkQueue {
66            deque: VecDeque::with_capacity(len_idx.index()),
67            set: BitSet::new_empty(len_idx),
68        }
69    }
70
71    /// Attempt to enqueue `element` in the work queue. Returns false if it was already present.
72    #[inline]
73    pub fn insert(&mut self, element: T) -> bool {
74        if self.set.put(element) {
75            false
76        } else {
77            self.deque.push_back(element);
78            true
79        }
80    }
81
82    /// Attempt to pop an element from the work queue.
83    #[inline]
84    pub fn pop(&mut self) -> Option<T> {
85        if let Some(element) = self.deque.pop_front() {
86            self.set.set(element, false);
87            Some(element)
88        } else {
89            None
90        }
91    }
92
93    /// Attempt to take an element from from the work queue
94    /// This function does not remove the item from the iternal set
95    /// As such any element removed using `take` can never be inserted again.
96    /// For must use cases [`pop`]should be used
97    ///
98    /// This is useful when you want to write a worklist based algorithm
99    /// that processes every element exactly one
100    #[inline]
101    pub fn take(&mut self) -> Option<T> {
102        if let Some(element) = self.deque.pop_front() {
103            Some(element)
104        } else {
105            None
106        }
107    }
108
109    /// Returns `true` if nothing is enqueued.
110    #[inline]
111    pub fn is_empty(&self) -> bool {
112        self.deque.is_empty()
113    }
114}
115
116impl<I: Idx + From<usize>> From<BitSet<I>> for WorkQueue<I> {
117    fn from(set: BitSet<I>) -> Self {
118        Self {
119            deque: VecDeque::from_iter(set.ones()),
120            set,
121        }
122    }
123}
124
125impl<I: Idx + From<usize> + Debug> Debug for WorkQueue<I> {
126    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
127        f.write_str("[")?;
128        for item in self.deque.iter() {
129            Debug::fmt(item, f)?;
130            f.write_str(" , ")?;
131        }
132        f.write_str("]")
133    }
134}
open_vaf/data_structures/work_queue.rs

open_vaf/data_structures/
work_queue.rs
