LLVM: include/llvm/ADT/PriorityWorklist.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#ifndef LLVM_ADT_PRIORITYWORKLIST_H
16#define LLVM_ADT_PRIORITYWORKLIST_H
17
22#include
23#include
24#include
25#include <type_traits>
26#include
27
28namespace llvm {
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53template <typename T, typename VectorT = std::vector,
54 typename MapT = DenseMap<T, ptrdiff_t>>
56public:
61 using size_type = typename MapT::size_type;
62
63
65
66
68 return V.empty();
69 }
70
71
75
76
77
79 return M.count(key);
80 }
81
82
84 assert(() && "Cannot call back() on empty PriorityWorklist!");
85 return V.back();
86 }
87
88
89
91 assert(X != T() && "Cannot insert a null (default constructed) value!");
92 auto InsertResult = M.insert({X, V.size()});
93 if (InsertResult.second) {
94
95 V.push_back(X);
96 return true;
97 }
98
99 auto &Index = InsertResult.first->second;
100 assert(V[Index] == X && "Value not actually at index in map!");
101 if (Index != (ptrdiff_t)(V.size() - 1)) {
102
103 V[Index] = T();
105 V.push_back(X);
106 }
107 return false;
108 }
109
110
111 template
112 std::enable_if_t<!std::is_convertible<SequenceT, T>::value>
114 if (std::begin(Input) == std::end(Input))
115
116 return;
117
118
119
121 V.insert(V.end(), std::begin(Input), std::end(Input));
122
123 for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
124 auto InsertResult = M.insert({V[i], i});
125 if (InsertResult.second)
126 continue;
127
128
129
130 ptrdiff_t &Index = InsertResult.first->second;
131 if (Index < StartIndex) {
132 V[Index] = T();
133 Index = i;
134 continue;
135 }
136
137
138
139 V[i] = T();
140 }
141 }
142
143
145 assert(() && "Cannot remove an element when empty!");
146 assert(back() != T() && "Cannot have a null element at the back!");
147 M.erase(back());
148 do {
149 V.pop_back();
150 } while (!V.empty() && V.back() == T());
151 }
152
158
159
160
161
164 if (I == M.end())
165 return false;
166
167 assert(V[I->second] == X && "Value not actually at index in map!");
168 if (I->second == (ptrdiff_t)(V.size() - 1)) {
169 do {
170 V.pop_back();
171 } while (!V.empty() && V.back() == T());
172 } else {
174 }
175 M.erase(I);
176 return true;
177 }
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192 template
194 typename VectorT::iterator E = remove_if(V, [&](const T &Arg) {
195 if (Arg == T())
196
197 return false;
198
199 if (P(Arg)) {
200 M.erase(Arg);
201 return true;
202 }
203 return false;
204 });
205 if (E == V.end())
206 return false;
207 for (auto I = V.begin(); I != E; ++I)
210 V.erase(E, V.end());
211 return true;
212 }
213
214
215
216
217
218
219
221 M.clear();
222 V.clear();
223 }
224
225private:
226
228
229
230 VectorT V;
231};
232
233
234
235template <typename T, unsigned N>
238 SmallDenseMap<T, ptrdiff_t>> {
239public:
241};
242
243}
244
245#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file defines the SmallVector class.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
The Input class is used to parse a yaml document into in-memory structs and vectors.
const T & back() const
Return the last element of the PriorityWorklist.
Definition PriorityWorklist.h:83
const T & const_reference
Definition PriorityWorklist.h:60
PriorityWorklist()=default
Construct an empty PriorityWorklist.
T value_type
Definition PriorityWorklist.h:57
size_type count(const key_type &key) const
Count the number of elements of a given key in the PriorityWorklist.
Definition PriorityWorklist.h:78
void clear()
Reverse the items in the PriorityWorklist.
Definition PriorityWorklist.h:220
typename MapT::size_type size_type
Definition PriorityWorklist.h:61
size_type size() const
Returns the number of elements in the worklist.
Definition PriorityWorklist.h:72
bool erase_if(UnaryPredicate P)
Erase items from the set vector based on a predicate function.
Definition PriorityWorklist.h:193
bool erase(const T &X)
Erase an item from the worklist.
Definition PriorityWorklist.h:162
T & reference
Definition PriorityWorklist.h:59
T key_type
Definition PriorityWorklist.h:58
T pop_back_val()
Definition PriorityWorklist.h:153
void pop_back()
Remove the last element of the PriorityWorklist.
Definition PriorityWorklist.h:144
bool empty() const
Determine if the PriorityWorklist is empty or not.
Definition PriorityWorklist.h:67
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
Definition PriorityWorklist.h:90
std::enable_if_t<!std::is_convertible< SequenceT, T >::value > insert(SequenceT &&Input)
Insert a sequence of new elements into the PriorityWorklist.
Definition PriorityWorklist.h:113
SmallPriorityWorklist()=default
This is an optimization pass for GlobalISel generic memory operations.
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.