Movatterモバイル変換

[0]ホーム
URL:

LLVM 20.0.0git
PriorityWorklist.h
Go to the documentation of this file.
1//===- PriorityWorklist.h - Worklist with insertion priority ----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10///
11/// This file provides a priority worklist. See the class comments for details.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_PRIORITYWORKLIST_H
16#define LLVM_ADT_PRIORITYWORKLIST_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/Support/Compiler.h"
22#include <cassert>
23#include <cstddef>
24#include <iterator>
25#include <type_traits>
26#include <vector>
27
28namespacellvm {
29
30/// A FILO worklist that prioritizes on re-insertion without duplication.
31///
32/// This is very similar to a \c SetVector with the primary difference that
33/// while re-insertion does not create a duplicate, it does adjust the
34/// visitation order to respect the last insertion point. This can be useful
35/// when the visit order needs to be prioritized based on insertion point
36/// without actually having duplicate visits.
37///
38/// Note that this doesn't prevent re-insertion of elements which have been
39/// visited -- if you need to break cycles, a set will still be necessary.
40///
41/// The type \c T must be default constructable to a null value that will be
42/// ignored. It is an error to insert such a value, and popping elements will
43/// never produce such a value. It is expected to be used with common nullable
44/// types like pointers or optionals.
45///
46/// Internally this uses a vector to store the worklist and a map to identify
47/// existing elements in the worklist. Both of these may be customized, but the
48/// map must support the basic DenseMap API for mapping from a T to an integer
49/// index into the vector.
50///
51/// A partial specialization is provided to automatically select a SmallVector
52/// and a SmallDenseMap if custom data structures are not provided.
53template <typename T,typename VectorT = std::vector<T>,
54typename MapT = DenseMap<T, ptrdiff_t>>
55classPriorityWorklist {
56public:
57usingvalue_type =T;
58usingkey_type =T;
59usingreference =T&;
60usingconst_reference =constT&;
61usingsize_type =typename MapT::size_type;
62
63 /// Construct an empty PriorityWorklist
64PriorityWorklist() =default;
65
66 /// Determine if the PriorityWorklist is empty or not.
67boolempty() const{
68return V.empty();
69 }
70
71 /// Returns the number of elements in the worklist.
72size_typesize() const{
73return M.size();
74 }
75
76 /// Count the number of elements of a given key in the PriorityWorklist.
77 /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is.
78size_typecount(constkey_type &key) const{
79return M.count(key);
80 }
81
82 /// Return the last element of the PriorityWorklist.
83constT &back() const{
84assert(!empty() &&"Cannot call back() on empty PriorityWorklist!");
85return V.back();
86 }
87
88 /// Insert a new element into the PriorityWorklist.
89 /// \returns true if the element was inserted into the PriorityWorklist.
90boolinsert(constT &X) {
91assert(X !=T() &&"Cannot insert a null (default constructed) value!");
92auto InsertResult = M.insert({X, V.size()});
93if (InsertResult.second) {
94// Fresh value, just append it to the vector.
95 V.push_back(X);
96returntrue;
97 }
98
99auto &Index = InsertResult.first->second;
100assert(V[Index] ==X &&"Value not actually at index in map!");
101if (Index != (ptrdiff_t)(V.size() - 1)) {
102// If the element isn't at the back, null it out and append a fresh one.
103 V[Index] =T();
104Index = (ptrdiff_t)V.size();
105 V.push_back(X);
106 }
107returnfalse;
108 }
109
110 /// Insert a sequence of new elements into the PriorityWorklist.
111template <typename SequenceT>
112 std::enable_if_t<!std::is_convertible<SequenceT, T>::value>
113insert(SequenceT &&Input) {
114if (std::begin(Input) == std::end(Input))
115// Nothing to do for an empty input sequence.
116return;
117
118// First pull the input sequence into the vector as a bulk append
119// operation.
120ptrdiff_t StartIndex = V.size();
121 V.insert(V.end(), std::begin(Input), std::end(Input));
122// Now walk backwards fixing up the index map and deleting any duplicates.
123for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
124auto InsertResult = M.insert({V[i], i});
125if (InsertResult.second)
126continue;
127
128// If the existing index is before this insert's start, nuke that one and
129// move it up.
130ptrdiff_t &Index = InsertResult.first->second;
131if (Index < StartIndex) {
132 V[Index] =T();
133Index = i;
134continue;
135 }
136
137// Otherwise the existing one comes first so just clear out the value in
138// this slot.
139 V[i] =T();
140 }
141 }
142
143 /// Remove the last element of the PriorityWorklist.
144voidpop_back() {
145assert(!empty() &&"Cannot remove an element when empty!");
146assert(back() !=T() &&"Cannot have a null element at the back!");
147 M.erase(back());
148do {
149 V.pop_back();
150 }while (!V.empty() && V.back() ==T());
151 }
152
153 [[nodiscard]]Tpop_back_val() {
154T Ret =back();
155pop_back();
156return Ret;
157 }
158
159 /// Erase an item from the worklist.
160 ///
161 /// Note that this is constant time due to the nature of the worklist implementation.
162boolerase(constT&X) {
163autoI = M.find(X);
164if (I == M.end())
165returnfalse;
166
167assert(V[I->second] ==X &&"Value not actually at index in map!");
168if (I->second == (ptrdiff_t)(V.size() - 1)) {
169do {
170 V.pop_back();
171 }while (!V.empty() && V.back() ==T());
172 }else {
173 V[I->second] =T();
174 }
175 M.erase(I);
176returntrue;
177 }
178
179 /// Erase items from the set vector based on a predicate function.
180 ///
181 /// This is intended to be equivalent to the following code, if we could
182 /// write it:
183 ///
184 /// \code
185 /// V.erase(remove_if(V, P), V.end());
186 /// \endcode
187 ///
188 /// However, PriorityWorklist doesn't expose non-const iterators, making any
189 /// algorithm like remove_if impossible to use.
190 ///
191 /// \returns true if any element is removed.
192template <typename UnaryPredicate>
193boolerase_if(UnaryPredicateP) {
194typename VectorT::iteratorE =
195remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M));
196if (E == V.end())
197returnfalse;
198for (autoI = V.begin();I !=E; ++I)
199if (*I !=T())
200 M[*I] =I - V.begin();
201 V.erase(E, V.end());
202returntrue;
203 }
204
205 /// Reverse the items in the PriorityWorklist.
206 ///
207 /// This does an in-place reversal. Other kinds of reverse aren't easy to
208 /// support in the face of the worklist semantics.
209
210 /// Completely clear the PriorityWorklist
211voidclear() {
212 M.clear();
213 V.clear();
214 }
215
216private:
217 /// A wrapper predicate designed for use with std::remove_if.
218 ///
219 /// This predicate wraps a predicate suitable for use with std::remove_if to
220 /// call M.erase(x) on each element which is slated for removal. This just
221 /// allows the predicate to be move only which we can't do with lambdas
222 /// today.
223template <typename UnaryPredicateT>
224classTestAndEraseFromMap {
225 UnaryPredicateTP;
226MapT &M;
227
228public:
229 TestAndEraseFromMap(UnaryPredicateT P,MapT &M)
230 :P(std::move(P)), M(M) {}
231
232bool operator()(constT &Arg) {
233if (Arg ==T())
234// Skip null values in the PriorityWorklist.
235returnfalse;
236
237if (P(Arg)) {
238 M.erase(Arg);
239returntrue;
240 }
241returnfalse;
242 }
243 };
244
245 /// The map from value to index in the vector.
246MapTM;
247
248 /// The vector of elements in insertion order.
249 VectorT V;
250};
251
252/// A version of \c PriorityWorklist that selects small size optimized data
253/// structures for the vector and map.
254template <typename T,unsigned N>
255classSmallPriorityWorklist
256 :publicPriorityWorklist<T, SmallVector<T, N>,
257 SmallDenseMap<T, ptrdiff_t>> {
258public:
259SmallPriorityWorklist() =default;
260};
261
262}// end namespace llvm
263
264#endif// LLVM_ADT_PRIORITYWORKLIST_H
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Compiler.h
DenseMap.h
This file defines the DenseMap class.
Index
uint32_t Index
Definition:ELFObjHandler.cpp:83
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
I
#define I(x, y, z)
Definition:MD5.cpp:58
T
#define T
Definition:Mips16ISelLowering.cpp:341
P
#define P(N)
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
STLExtras.h
This file contains some templates that are useful if you are working with the STL at all.
SmallVector.h
This file defines the SmallVector class.
MapT
T
llvm::PriorityWorklist
A FILO worklist that prioritizes on re-insertion without duplication.
Definition:PriorityWorklist.h:55
llvm::PriorityWorklist::back
const T & back() const
Return the last element of the PriorityWorklist.
Definition:PriorityWorklist.h:83
llvm::PriorityWorklist::PriorityWorklist
PriorityWorklist()=default
Construct an empty PriorityWorklist.
llvm::PriorityWorklist::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the PriorityWorklist.
Definition:PriorityWorklist.h:78
llvm::PriorityWorklist::clear
void clear()
Reverse the items in the PriorityWorklist.
Definition:PriorityWorklist.h:211
llvm::PriorityWorklist::size_type
typename MapT::size_type size_type
Definition:PriorityWorklist.h:61
llvm::PriorityWorklist::size
size_type size() const
Returns the number of elements in the worklist.
Definition:PriorityWorklist.h:72
llvm::PriorityWorklist::erase_if
bool erase_if(UnaryPredicate P)
Erase items from the set vector based on a predicate function.
Definition:PriorityWorklist.h:193
llvm::PriorityWorklist::erase
bool erase(const T &X)
Erase an item from the worklist.
Definition:PriorityWorklist.h:162
llvm::PriorityWorklist::pop_back_val
T pop_back_val()
Definition:PriorityWorklist.h:153
llvm::PriorityWorklist::pop_back
void pop_back()
Remove the last element of the PriorityWorklist.
Definition:PriorityWorklist.h:144
llvm::PriorityWorklist::empty
bool empty() const
Determine if the PriorityWorklist is empty or not.
Definition:PriorityWorklist.h:67
llvm::PriorityWorklist::insert
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
Definition:PriorityWorklist.h:90
llvm::PriorityWorklist::insert
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
llvm::SmallPriorityWorklist
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
Definition:PriorityWorklist.h:257
llvm::SmallPriorityWorklist::SmallPriorityWorklist
SmallPriorityWorklist()=default
ptrdiff_t
llvm::ARM::ProfileKind::M
@ M
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition:AddressRanges.h:18
llvm::remove_if
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition:STLExtras.h:1778
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition:STLExtras.h:1873
std
Implement std::hash so that hash_code can be used in STL containers.
Definition:BitVector.h:858
Generated on Thu Jul 17 2025 04:45:49 for LLVM by doxygen 1.9.6
[8]ページ先頭
©2009-2025 Movatter.jp