/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/PriorityWorklist.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- PriorityWorklist.h - Worklist with insertion priority ----*- C++ -*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | /// |
10 | | /// \file |
11 | | /// |
12 | | /// This file provides a priority worklist. See the class comments for details. |
13 | | /// |
14 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #ifndef LLVM_ADT_PRIORITYWORKLIST_H |
17 | | #define LLVM_ADT_PRIORITYWORKLIST_H |
18 | | |
19 | | #include "llvm/ADT/DenseMap.h" |
20 | | #include "llvm/ADT/STLExtras.h" |
21 | | #include "llvm/ADT/SmallVector.h" |
22 | | #include "llvm/Support/Compiler.h" |
23 | | #include <algorithm> |
24 | | #include <cassert> |
25 | | #include <cstddef> |
26 | | #include <iterator> |
27 | | #include <type_traits> |
28 | | #include <vector> |
29 | | |
30 | | namespace llvm { |
31 | | |
32 | | /// A FILO worklist that prioritizes on re-insertion without duplication. |
33 | | /// |
34 | | /// This is very similar to a \c SetVector with the primary difference that |
35 | | /// while re-insertion does not create a duplicate, it does adjust the |
36 | | /// visitation order to respect the last insertion point. This can be useful |
37 | | /// when the visit order needs to be prioritized based on insertion point |
38 | | /// without actually having duplicate visits. |
39 | | /// |
40 | | /// Note that this doesn't prevent re-insertion of elements which have been |
41 | | /// visited -- if you need to break cycles, a set will still be necessary. |
42 | | /// |
43 | | /// The type \c T must be default constructable to a null value that will be |
44 | | /// ignored. It is an error to insert such a value, and popping elements will |
45 | | /// never produce such a value. It is expected to be used with common nullable |
46 | | /// types like pointers or optionals. |
47 | | /// |
48 | | /// Internally this uses a vector to store the worklist and a map to identify |
49 | | /// existing elements in the worklist. Both of these may be customized, but the |
50 | | /// map must support the basic DenseMap API for mapping from a T to an integer |
51 | | /// index into the vector. |
52 | | /// |
53 | | /// A partial specialization is provided to automatically select a SmallVector |
54 | | /// and a SmallDenseMap if custom data structures are not provided. |
55 | | template <typename T, typename VectorT = std::vector<T>, |
56 | | typename MapT = DenseMap<T, ptrdiff_t>> |
57 | | class PriorityWorklist { |
58 | | public: |
59 | | using value_type = T; |
60 | | using key_type = T; |
61 | | using reference = T&; |
62 | | using const_reference = const T&; |
63 | | using size_type = typename MapT::size_type; |
64 | | |
65 | | /// Construct an empty PriorityWorklist |
66 | 976 | PriorityWorklist() = default; llvm::PriorityWorklist<llvm::LazyCallGraph::RefSCC*, llvm::SmallVector<llvm::LazyCallGraph::RefSCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::RefSCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::RefSCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::RefSCC*, long> > >::PriorityWorklist() Line | Count | Source | 66 | 239 | PriorityWorklist() = default; |
llvm::PriorityWorklist<llvm::LazyCallGraph::SCC*, llvm::SmallVector<llvm::LazyCallGraph::SCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::SCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::SCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::SCC*, long> > >::PriorityWorklist() Line | Count | Source | 66 | 239 | PriorityWorklist() = default; |
llvm::PriorityWorklist<llvm::Loop*, llvm::SmallVector<llvm::Loop*, 4u>, llvm::SmallDenseMap<llvm::Loop*, long, 4u, llvm::DenseMapInfo<llvm::Loop*>, llvm::detail::DenseMapPair<llvm::Loop*, long> > >::PriorityWorklist() Line | Count | Source | 66 | 498 | PriorityWorklist() = default; |
Unexecuted instantiation: llvm::PriorityWorklist<llvm::Region*, llvm::SmallVector<llvm::Region*, 4u>, llvm::SmallDenseMap<llvm::Region*, long, 4u, llvm::DenseMapInfo<llvm::Region*>, llvm::detail::DenseMapPair<llvm::Region*, long> > >::PriorityWorklist() |
67 | | |
68 | | /// Determine if the PriorityWorklist is empty or not. |
69 | 2.34k | bool empty() const { |
70 | 2.34k | return V.empty(); |
71 | 2.34k | } Unexecuted instantiation: llvm::PriorityWorklist<llvm::Region*, llvm::SmallVector<llvm::Region*, 4u>, llvm::SmallDenseMap<llvm::Region*, long, 4u, llvm::DenseMapInfo<llvm::Region*>, llvm::detail::DenseMapPair<llvm::Region*, long> > >::empty() const llvm::PriorityWorklist<llvm::Loop*, llvm::SmallVector<llvm::Loop*, 4u>, llvm::SmallDenseMap<llvm::Loop*, long, 4u, llvm::DenseMapInfo<llvm::Loop*>, llvm::detail::DenseMapPair<llvm::Loop*, long> > >::empty() const Line | Count | Source | 69 | 644 | bool empty() const { | 70 | 644 | return V.empty(); | 71 | 644 | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::SCC*, llvm::SmallVector<llvm::LazyCallGraph::SCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::SCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::SCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::SCC*, long> > >::empty() const Line | Count | Source | 69 | 882 | bool empty() const { | 70 | 882 | return V.empty(); | 71 | 882 | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::RefSCC*, llvm::SmallVector<llvm::LazyCallGraph::RefSCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::RefSCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::RefSCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::RefSCC*, long> > >::empty() const Line | Count | Source | 69 | 814 | bool empty() const { | 70 | 814 | return V.empty(); | 71 | 814 | } |
|
72 | | |
73 | | /// Returns the number of elements in the worklist. |
74 | | size_type size() const { |
75 | | return M.size(); |
76 | | } |
77 | | |
78 | | /// Count the number of elements of a given key in the PriorityWorklist. |
79 | | /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is. |
80 | | size_type count(const key_type &key) const { |
81 | | return M.count(key); |
82 | | } |
83 | | |
84 | | /// Return the last element of the PriorityWorklist. |
85 | 4.68k | const T &back() const { |
86 | 4.68k | assert(!empty() && "Cannot call back() on empty PriorityWorklist!"); |
87 | 4.68k | return V.back(); |
88 | 4.68k | } Unexecuted instantiation: llvm::PriorityWorklist<llvm::Region*, llvm::SmallVector<llvm::Region*, 4u>, llvm::SmallDenseMap<llvm::Region*, long, 4u, llvm::DenseMapInfo<llvm::Region*>, llvm::detail::DenseMapPair<llvm::Region*, long> > >::back() const llvm::PriorityWorklist<llvm::Loop*, llvm::SmallVector<llvm::Loop*, 4u>, llvm::SmallDenseMap<llvm::Loop*, long, 4u, llvm::DenseMapInfo<llvm::Loop*>, llvm::detail::DenseMapPair<llvm::Loop*, long> > >::back() const Line | Count | Source | 85 | 1.28k | const T &back() const { | 86 | 1.28k | assert(!empty() && "Cannot call back() on empty PriorityWorklist!"); | 87 | 1.28k | return V.back(); | 88 | 1.28k | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::RefSCC*, llvm::SmallVector<llvm::LazyCallGraph::RefSCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::RefSCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::RefSCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::RefSCC*, long> > >::back() const Line | Count | Source | 85 | 1.62k | const T &back() const { | 86 | 1.62k | assert(!empty() && "Cannot call back() on empty PriorityWorklist!"); | 87 | 1.62k | return V.back(); | 88 | 1.62k | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::SCC*, llvm::SmallVector<llvm::LazyCallGraph::SCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::SCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::SCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::SCC*, long> > >::back() const Line | Count | Source | 85 | 1.76k | const T &back() const { | 86 | 1.76k | assert(!empty() && "Cannot call back() on empty PriorityWorklist!"); | 87 | 1.76k | return V.back(); | 88 | 1.76k | } |
|
89 | | |
90 | | /// Insert a new element into the PriorityWorklist. |
91 | | /// \returns true if the element was inserted into the PriorityWorklist. |
92 | 1.71k | bool insert(const T &X) { |
93 | 1.71k | assert(X != T() && "Cannot insert a null (default constructed) value!"); |
94 | 1.71k | auto InsertResult = M.insert({X, V.size()}); |
95 | 1.71k | if (InsertResult.second1.71k ) { |
96 | 1.69k | // Fresh value, just append it to the vector. |
97 | 1.69k | V.push_back(X); |
98 | 1.69k | return true; |
99 | 1.69k | } |
100 | 1.71k | |
101 | 12 | auto &Index = InsertResult.first->second; |
102 | 12 | assert(V[Index] == X && "Value not actually at index in map!"); |
103 | 12 | if (Index != (ptrdiff_t)(V.size() - 1)12 ) { |
104 | 4 | // If the element isn't at the back, null it out and append a fresh one. |
105 | 4 | V[Index] = T(); |
106 | 4 | Index = (ptrdiff_t)V.size(); |
107 | 4 | V.push_back(X); |
108 | 4 | } |
109 | 12 | return false; |
110 | 1.71k | } Unexecuted instantiation: llvm::PriorityWorklist<llvm::Region*, llvm::SmallVector<llvm::Region*, 4u>, llvm::SmallDenseMap<llvm::Region*, long, 4u, llvm::DenseMapInfo<llvm::Region*>, llvm::detail::DenseMapPair<llvm::Region*, long> > >::insert(llvm::Region* const&) llvm::PriorityWorklist<llvm::Loop*, llvm::SmallVector<llvm::Loop*, 4u>, llvm::SmallDenseMap<llvm::Loop*, long, 4u, llvm::DenseMapInfo<llvm::Loop*>, llvm::detail::DenseMapPair<llvm::Loop*, long> > >::insert(llvm::Loop* const&) Line | Count | Source | 92 | 3 | bool insert(const T &X) { | 93 | 3 | assert(X != T() && "Cannot insert a null (default constructed) value!"); | 94 | 3 | auto InsertResult = M.insert({X, V.size()}); | 95 | 3 | if (InsertResult.second3 ) { | 96 | 3 | // Fresh value, just append it to the vector. | 97 | 3 | V.push_back(X); | 98 | 3 | return true; | 99 | 3 | } | 100 | 3 | | 101 | 0 | auto &Index = InsertResult.first->second; | 102 | 0 | assert(V[Index] == X && "Value not actually at index in map!"); | 103 | 0 | if (Index != (ptrdiff_t)(V.size() - 1)0 ) { | 104 | 0 | // If the element isn't at the back, null it out and append a fresh one. | 105 | 0 | V[Index] = T(); | 106 | 0 | Index = (ptrdiff_t)V.size(); | 107 | 0 | V.push_back(X); | 108 | 0 | } | 109 | 0 | return false; | 110 | 3 | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::RefSCC*, llvm::SmallVector<llvm::LazyCallGraph::RefSCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::RefSCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::RefSCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::RefSCC*, long> > >::insert(llvm::LazyCallGraph::RefSCC* const&) Line | Count | Source | 92 | 814 | bool insert(const T &X) { | 93 | 814 | assert(X != T() && "Cannot insert a null (default constructed) value!"); | 94 | 814 | auto InsertResult = M.insert({X, V.size()}); | 95 | 814 | if (InsertResult.second814 ) { | 96 | 814 | // Fresh value, just append it to the vector. | 97 | 814 | V.push_back(X); | 98 | 814 | return true; | 99 | 814 | } | 100 | 814 | | 101 | 0 | auto &Index = InsertResult.first->second; | 102 | 0 | assert(V[Index] == X && "Value not actually at index in map!"); | 103 | 0 | if (Index != (ptrdiff_t)(V.size() - 1)0 ) { | 104 | 0 | // If the element isn't at the back, null it out and append a fresh one. | 105 | 0 | V[Index] = T(); | 106 | 0 | Index = (ptrdiff_t)V.size(); | 107 | 0 | V.push_back(X); | 108 | 0 | } | 109 | 0 | return false; | 110 | 814 | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::SCC*, llvm::SmallVector<llvm::LazyCallGraph::SCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::SCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::SCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::SCC*, long> > >::insert(llvm::LazyCallGraph::SCC* const&) Line | Count | Source | 92 | 894 | bool insert(const T &X) { | 93 | 894 | assert(X != T() && "Cannot insert a null (default constructed) value!"); | 94 | 894 | auto InsertResult = M.insert({X, V.size()}); | 95 | 894 | if (InsertResult.second894 ) { | 96 | 882 | // Fresh value, just append it to the vector. | 97 | 882 | V.push_back(X); | 98 | 882 | return true; | 99 | 882 | } | 100 | 894 | | 101 | 12 | auto &Index = InsertResult.first->second; | 102 | 12 | assert(V[Index] == X && "Value not actually at index in map!"); | 103 | 12 | if (Index != (ptrdiff_t)(V.size() - 1)12 ) { | 104 | 4 | // If the element isn't at the back, null it out and append a fresh one. | 105 | 4 | V[Index] = T(); | 106 | 4 | Index = (ptrdiff_t)V.size(); | 107 | 4 | V.push_back(X); | 108 | 4 | } | 109 | 12 | return false; | 110 | 894 | } |
|
111 | | |
112 | | /// Insert a sequence of new elements into the PriorityWorklist. |
113 | | template <typename SequenceT> |
114 | | typename std::enable_if<!std::is_convertible<SequenceT, T>::value>::type |
115 | 525 | insert(SequenceT &&Input) { |
116 | 525 | if (std::begin(Input) == std::end(Input)) |
117 | 525 | // Nothing to do for an empty input sequence. |
118 | 0 | return; |
119 | 525 | |
120 | 525 | // First pull the input sequence into the vector as a bulk append |
121 | 525 | // operation. |
122 | 525 | ptrdiff_t StartIndex = V.size(); |
123 | 525 | V.insert(V.end(), std::begin(Input), std::end(Input)); |
124 | 525 | // Now walk backwards fixing up the index map and deleting any duplicates. |
125 | 1.16k | for (ptrdiff_t i = V.size() - 1; i >= StartIndex1.16k ; --i641 ) { |
126 | 641 | auto InsertResult = M.insert({V[i], i}); |
127 | 641 | if (InsertResult.second) |
128 | 641 | continue; |
129 | 641 | |
130 | 641 | // If the existing index is before this insert's start, nuke that one and |
131 | 641 | // move it up. |
132 | 0 | ptrdiff_t &Index = InsertResult.first->second; |
133 | 0 | if (Index < StartIndex0 ) { |
134 | 0 | V[Index] = T(); |
135 | 0 | Index = i; |
136 | 0 | continue; |
137 | 0 | } |
138 | 0 |
|
139 | 0 | // Otherwise the existing one comes first so just clear out the value in |
140 | 0 | // this slot. |
141 | 0 | V[i] = T(); |
142 | 0 | } |
143 | 525 | } |
144 | | |
145 | | /// Remove the last element of the PriorityWorklist. |
146 | 2.34k | void pop_back() { |
147 | 2.34k | assert(!empty() && "Cannot remove an element when empty!"); |
148 | 2.34k | assert(back() != T() && "Cannot have a null element at the back!"); |
149 | 2.34k | M.erase(back()); |
150 | 2.34k | do { |
151 | 2.34k | V.pop_back(); |
152 | 2.34k | } while (!V.empty() && 2.34k V.back() == T()208 ); |
153 | 2.34k | } llvm::PriorityWorklist<llvm::LazyCallGraph::SCC*, llvm::SmallVector<llvm::LazyCallGraph::SCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::SCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::SCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::SCC*, long> > >::pop_back() Line | Count | Source | 146 | 882 | void pop_back() { | 147 | 882 | assert(!empty() && "Cannot remove an element when empty!"); | 148 | 882 | assert(back() != T() && "Cannot have a null element at the back!"); | 149 | 882 | M.erase(back()); | 150 | 886 | do { | 151 | 886 | V.pop_back(); | 152 | 886 | } while (!V.empty() && 886 V.back() == T()55 ); | 153 | 882 | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::RefSCC*, llvm::SmallVector<llvm::LazyCallGraph::RefSCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::RefSCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::RefSCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::RefSCC*, long> > >::pop_back() Line | Count | Source | 146 | 814 | void pop_back() { | 147 | 814 | assert(!empty() && "Cannot remove an element when empty!"); | 148 | 814 | assert(back() != T() && "Cannot have a null element at the back!"); | 149 | 814 | M.erase(back()); | 150 | 814 | do { | 151 | 814 | V.pop_back(); | 152 | 814 | } while (!V.empty() && 814 V.back() == T()7 ); | 153 | 814 | } |
llvm::PriorityWorklist<llvm::Loop*, llvm::SmallVector<llvm::Loop*, 4u>, llvm::SmallDenseMap<llvm::Loop*, long, 4u, llvm::DenseMapInfo<llvm::Loop*>, llvm::detail::DenseMapPair<llvm::Loop*, long> > >::pop_back() Line | Count | Source | 146 | 644 | void pop_back() { | 147 | 644 | assert(!empty() && "Cannot remove an element when empty!"); | 148 | 644 | assert(back() != T() && "Cannot have a null element at the back!"); | 149 | 644 | M.erase(back()); | 150 | 644 | do { | 151 | 644 | V.pop_back(); | 152 | 644 | } while (!V.empty() && 644 V.back() == T()146 ); | 153 | 644 | } |
Unexecuted instantiation: llvm::PriorityWorklist<llvm::Region*, llvm::SmallVector<llvm::Region*, 4u>, llvm::SmallDenseMap<llvm::Region*, long, 4u, llvm::DenseMapInfo<llvm::Region*>, llvm::detail::DenseMapPair<llvm::Region*, long> > >::pop_back() |
154 | | |
155 | 2.34k | LLVM_NODISCARD T pop_back_val() { |
156 | 2.34k | T Ret = back(); |
157 | 2.34k | pop_back(); |
158 | 2.34k | return Ret; |
159 | 2.34k | } Unexecuted instantiation: llvm::PriorityWorklist<llvm::Region*, llvm::SmallVector<llvm::Region*, 4u>, llvm::SmallDenseMap<llvm::Region*, long, 4u, llvm::DenseMapInfo<llvm::Region*>, llvm::detail::DenseMapPair<llvm::Region*, long> > >::pop_back_val() llvm::PriorityWorklist<llvm::Loop*, llvm::SmallVector<llvm::Loop*, 4u>, llvm::SmallDenseMap<llvm::Loop*, long, 4u, llvm::DenseMapInfo<llvm::Loop*>, llvm::detail::DenseMapPair<llvm::Loop*, long> > >::pop_back_val() Line | Count | Source | 155 | 644 | LLVM_NODISCARD T pop_back_val() { | 156 | 644 | T Ret = back(); | 157 | 644 | pop_back(); | 158 | 644 | return Ret; | 159 | 644 | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::RefSCC*, llvm::SmallVector<llvm::LazyCallGraph::RefSCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::RefSCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::RefSCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::RefSCC*, long> > >::pop_back_val() Line | Count | Source | 155 | 814 | LLVM_NODISCARD T pop_back_val() { | 156 | 814 | T Ret = back(); | 157 | 814 | pop_back(); | 158 | 814 | return Ret; | 159 | 814 | } |
llvm::PriorityWorklist<llvm::LazyCallGraph::SCC*, llvm::SmallVector<llvm::LazyCallGraph::SCC*, 1u>, llvm::SmallDenseMap<llvm::LazyCallGraph::SCC*, long, 4u, llvm::DenseMapInfo<llvm::LazyCallGraph::SCC*>, llvm::detail::DenseMapPair<llvm::LazyCallGraph::SCC*, long> > >::pop_back_val() Line | Count | Source | 155 | 882 | LLVM_NODISCARD T pop_back_val() { | 156 | 882 | T Ret = back(); | 157 | 882 | pop_back(); | 158 | 882 | return Ret; | 159 | 882 | } |
|
160 | | |
161 | | /// Erase an item from the worklist. |
162 | | /// |
163 | | /// Note that this is constant time due to the nature of the worklist implementation. |
164 | 0 | bool erase(const T& X) { |
165 | 0 | auto I = M.find(X); |
166 | 0 | if (I == M.end()) |
167 | 0 | return false; |
168 | 0 |
|
169 | 0 | assert(V[I->second] == X && "Value not actually at index in map!"); |
170 | 0 | if (I->second == (ptrdiff_t)(V.size() - 1)0 ) { |
171 | 0 | do { |
172 | 0 | V.pop_back(); |
173 | 0 | } while (!V.empty() && 0 V.back() == T()0 ); |
174 | 0 | } else { |
175 | 0 | V[I->second] = T(); |
176 | 0 | } |
177 | 0 | M.erase(I); |
178 | 0 | return true; |
179 | 0 | } |
180 | | |
181 | | /// Erase items from the set vector based on a predicate function. |
182 | | /// |
183 | | /// This is intended to be equivalent to the following code, if we could |
184 | | /// write it: |
185 | | /// |
186 | | /// \code |
187 | | /// V.erase(remove_if(V, P), V.end()); |
188 | | /// \endcode |
189 | | /// |
190 | | /// However, PriorityWorklist doesn't expose non-const iterators, making any |
191 | | /// algorithm like remove_if impossible to use. |
192 | | /// |
193 | | /// \returns true if any element is removed. |
194 | | template <typename UnaryPredicate> |
195 | | bool erase_if(UnaryPredicate P) { |
196 | | typename VectorT::iterator E = |
197 | | remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M)); |
198 | | if (E == V.end()) |
199 | | return false; |
200 | | for (auto I = V.begin(); I != E; ++I) |
201 | | if (*I != T()) |
202 | | M[*I] = I - V.begin(); |
203 | | V.erase(E, V.end()); |
204 | | return true; |
205 | | } |
206 | | |
207 | | /// Reverse the items in the PriorityWorklist. |
208 | | /// |
209 | | /// This does an in-place reversal. Other kinds of reverse aren't easy to |
210 | | /// support in the face of the worklist semantics. |
211 | | |
212 | | /// Completely clear the PriorityWorklist |
213 | | void clear() { |
214 | | M.clear(); |
215 | | V.clear(); |
216 | | } |
217 | | |
218 | | private: |
219 | | /// A wrapper predicate designed for use with std::remove_if. |
220 | | /// |
221 | | /// This predicate wraps a predicate suitable for use with std::remove_if to |
222 | | /// call M.erase(x) on each element which is slated for removal. This just |
223 | | /// allows the predicate to be move only which we can't do with lambdas |
224 | | /// today. |
225 | | template <typename UnaryPredicateT> |
226 | | class TestAndEraseFromMap { |
227 | | UnaryPredicateT P; |
228 | | MapT &M; |
229 | | |
230 | | public: |
231 | | TestAndEraseFromMap(UnaryPredicateT P, MapT &M) |
232 | | : P(std::move(P)), M(M) {} |
233 | | |
234 | | bool operator()(const T &Arg) { |
235 | | if (Arg == T()) |
236 | | // Skip null values in the PriorityWorklist. |
237 | | return false; |
238 | | |
239 | | if (P(Arg)) { |
240 | | M.erase(Arg); |
241 | | return true; |
242 | | } |
243 | | return false; |
244 | | } |
245 | | }; |
246 | | |
247 | | /// The map from value to index in the vector. |
248 | | MapT M; |
249 | | |
250 | | /// The vector of elements in insertion order. |
251 | | VectorT V; |
252 | | }; |
253 | | |
254 | | /// A version of \c PriorityWorklist that selects small size optimized data |
255 | | /// structures for the vector and map. |
256 | | template <typename T, unsigned N> |
257 | | class SmallPriorityWorklist |
258 | | : public PriorityWorklist<T, SmallVector<T, N>, |
259 | | SmallDenseMap<T, ptrdiff_t>> { |
260 | | public: |
261 | 976 | SmallPriorityWorklist() = default; llvm::SmallPriorityWorklist<llvm::LazyCallGraph::SCC*, 1u>::SmallPriorityWorklist() Line | Count | Source | 261 | 239 | SmallPriorityWorklist() = default; |
llvm::SmallPriorityWorklist<llvm::LazyCallGraph::RefSCC*, 1u>::SmallPriorityWorklist() Line | Count | Source | 261 | 239 | SmallPriorityWorklist() = default; |
Unexecuted instantiation: llvm::SmallPriorityWorklist<llvm::Region*, 4u>::SmallPriorityWorklist() llvm::SmallPriorityWorklist<llvm::Loop*, 4u>::SmallPriorityWorklist() Line | Count | Source | 261 | 498 | SmallPriorityWorklist() = default; |
|
262 | | }; |
263 | | |
264 | | } // end namespace llvm |
265 | | |
266 | | #endif // LLVM_ADT_PRIORITYWORKLIST_H |