Movatterモバイル変換

Go to the documentation of this file.

1//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- 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/// This file implements a set that has insertion order iteration

11/// characteristics. This is useful for keeping a set of things that need to be

12/// visited later but in a deterministic order (insertion order). The interface

13/// is purposefully minimal.

14///

15/// This file defines SetVector and SmallSetVector, which performs no

16/// allocations if the SetVector has less than a certain number of elements.

17///

18//===----------------------------------------------------------------------===//

20#ifndef LLVM_ADT_SETVECTOR_H

21#define LLVM_ADT_SETVECTOR_H

23#include "llvm/ADT/ArrayRef.h"

24#include "llvm/ADT/DenseSet.h"

25#include "llvm/ADT/STLExtras.h"

26#include "llvm/ADT/SmallVector.h"

27#include "llvm/Support/Compiler.h"

28#include <cassert>

29#include <iterator>

31namespacellvm {

33/// A vector that has set insertion semantics.

34///

35/// This adapter class provides a way to keep a set of things that also has the

36/// property of a deterministic iteration order. The order of iteration is the

37/// order of insertion.

38///

39/// The key and value types are derived from the Set and Vector types

40/// respectively. This allows the vector-type operations and set-type operations

41/// to have different types. In particular, this is useful when storing pointers

42/// as "Foo *" values but looking them up as "const Foo *" keys.

43///

44/// No constraint is placed on the key and value types, although it is assumed

45/// that value_type can be converted into key_type for insertion. Users must be

46/// aware of any loss of information in this conversion. For example, setting

47/// value_type to float and key_type to int can produce very surprising results,

48/// but it is not explicitly disallowed.

49///

50/// The parameter N specifies the "small" size of the container, which is the

51/// number of elements upto which a linear scan over the Vector will be used

52/// when searching for elements instead of checking Set, due to it being better

53/// for performance. A value of 0 means that this mode of operation is not used,

54/// and is the default value.

55template <typename T,typename Vector = SmallVector<T, 0>,

56typename Set = DenseSet<T>,unsigned N = 0>

57classSetVector {

58// Much like in SmallPtrSet, this value should not be too high to prevent

59// excessively long linear scans from occuring.

60static_assert(N <= 32,"Small size should be less than or equal to 32!");

62public:

63usingvalue_type =typename Vector::value_type;

64usingkey_type =typename Set::key_type;

65usingreference =value_type &;

66usingconst_reference =constvalue_type &;

67usingset_type = Set;

68usingvector_type =Vector;

69usingiterator =typename vector_type::const_iterator;

70usingconst_iterator =typename vector_type::const_iterator;

71usingreverse_iterator =typename vector_type::const_reverse_iterator;

72usingconst_reverse_iterator =typename vector_type::const_reverse_iterator;

73usingsize_type =typename vector_type::size_type;

75 /// Construct an empty SetVector

76SetVector() =default;

78 /// Initialize a SetVector with a range of elements

79template<typename It>

80SetVector(It Start, ItEnd) {

81insert(Start,End);

82 }

84ArrayRef<value_type>getArrayRef() const{return vector_; }

86 /// Clear the SetVector and return the underlying vector.

87Vector takeVector() {

88 set_.clear();

89return std::move(vector_);

90 }

92 /// Determine if the SetVector is empty or not.

93boolempty() const{

94return vector_.empty();

95 }

97 /// Determine the number of elements in the SetVector.

98size_type size() const{

99return vector_.size();

100 }

101

102 /// Get an iterator to the beginning of the SetVector.

103iterator begin() {

104return vector_.begin();

105 }

106

107 /// Get a const_iterator to the beginning of the SetVector.

108const_iterator begin() const{

109return vector_.begin();

110 }

111

112 /// Get an iterator to the end of the SetVector.

113iterator end() {

114return vector_.end();

115 }

116

117 /// Get a const_iterator to the end of the SetVector.

118const_iterator end() const{

119return vector_.end();

120 }

121

122 /// Get an reverse_iterator to the end of the SetVector.

123reverse_iterator rbegin() {

124return vector_.rbegin();

125 }

126

127 /// Get a const_reverse_iterator to the end of the SetVector.

128const_reverse_iterator rbegin() const{

129return vector_.rbegin();

130 }

131

132 /// Get a reverse_iterator to the beginning of the SetVector.

133reverse_iterator rend() {

134return vector_.rend();

135 }

136

137 /// Get a const_reverse_iterator to the beginning of the SetVector.

138const_reverse_iterator rend() const{

139return vector_.rend();

140 }

141

142 /// Return the first element of the SetVector.

143constvalue_type &front() const{

144assert(!empty() &&"Cannot call front() on empty SetVector!");

145return vector_.front();

146 }

147

148 /// Return the last element of the SetVector.

149constvalue_type &back() const{

150assert(!empty() &&"Cannot call back() on empty SetVector!");

151return vector_.back();

152 }

153

154 /// Index into the SetVector.

155const_reference operator[](size_type n) const{

156assert(n < vector_.size() &&"SetVector access out of range!");

157return vector_[n];

158 }

159

160 /// Insert a new element into the SetVector.

161 /// \returns true if the element was inserted into the SetVector.

162boolinsert(constvalue_type &X) {

163ifconstexpr (canBeSmall())

164if (isSmall()) {

165if (!llvm::is_contained(vector_,X)) {

166 vector_.push_back(X);

167if (vector_.size() >N)

168 makeBig();

169returntrue;

170 }

171returnfalse;

172 }

173

174bool result = set_.insert(X).second;

175if (result)

176 vector_.push_back(X);

177return result;

178 }

179

180 /// Insert a range of elements into the SetVector.

181template<typename It>

182voidinsert(It Start, ItEnd) {

183for (; Start !=End; ++Start)

184insert(*Start);

185 }

186

187 /// Remove an item from the set vector.

188boolremove(constvalue_type&X) {

189ifconstexpr (canBeSmall())

190if (isSmall()) {

191typename vector_type::iteratorI =find(vector_,X);

192if (I != vector_.end()) {

193 vector_.erase(I);

194returntrue;

195 }

196returnfalse;

197 }

198

199if (set_.erase(X)) {

200typename vector_type::iteratorI =find(vector_,X);

201assert(I != vector_.end() &&"Corrupted SetVector instances!");

202 vector_.erase(I);

203returntrue;

204 }

205returnfalse;

206 }

207

208 /// Erase a single element from the set vector.

209 /// \returns an iterator pointing to the next element that followed the

210 /// element erased. This is the end of the SetVector if the last element is

211 /// erased.

212iterator erase(const_iterator I) {

213ifconstexpr (canBeSmall())

214if (isSmall())

215return vector_.erase(I);

216

217constkey_type &V = *I;

218assert(set_.count(V) &&"Corrupted SetVector instances!");

219 set_.erase(V);

220return vector_.erase(I);

221 }

222

223 /// Remove items from the set vector based on a predicate function.

224 ///

225 /// This is intended to be equivalent to the following code, if we could

226 /// write it:

227 ///

228 /// \code

229 /// V.erase(remove_if(V, P), V.end());

230 /// \endcode

231 ///

232 /// However, SetVector doesn't expose non-const iterators, making any

233 /// algorithm like remove_if impossible to use.

234 ///

235 /// \returns true if any element is removed.

236template <typename UnaryPredicate>

237boolremove_if(UnaryPredicateP) {

238typename vector_type::iteratorI = [this,P] {

239ifconstexpr (canBeSmall())

240if (isSmall())

241returnllvm::remove_if(vector_,P);

242

243returnllvm::remove_if(vector_,

244 TestAndEraseFromSet<UnaryPredicate>(P, set_));

245 }();

246

247if (I == vector_.end())

248returnfalse;

249 vector_.erase(I, vector_.end());

250returntrue;

251 }

252

253 /// Check if the SetVector contains the given key.

254boolcontains(constkey_type &key) const{

255ifconstexpr (canBeSmall())

256if (isSmall())

257returnis_contained(vector_, key);

258

259return set_.find(key) != set_.end();

260 }

261

262 /// Count the number of elements of a given key in the SetVector.

263 /// \returns 0 if the element is not in the SetVector, 1 if it is.

264size_type count(constkey_type &key) const{

265ifconstexpr (canBeSmall())

266if (isSmall())

267returnis_contained(vector_, key);

268

269return set_.count(key);

270 }

271

272 /// Completely clear the SetVector

273voidclear() {

274 set_.clear();

275 vector_.clear();

276 }

277

278 /// Remove the last element of the SetVector.

279voidpop_back() {

280assert(!empty() &&"Cannot remove an element from an empty SetVector!");

281 set_.erase(back());

282 vector_.pop_back();

283 }

284

285 [[nodiscard]]value_type pop_back_val() {

286value_type Ret =back();

287pop_back();

288return Ret;

289 }

290

291booloperator==(constSetVector &that) const{

292return vector_ == that.vector_;

293 }

294

295booloperator!=(constSetVector &that) const{

296return vector_ != that.vector_;

297 }

298

299 /// Compute This := This u S, return whether 'This' changed.

300 /// TODO: We should be able to use set_union from SetOperations.h, but

301 /// SetVector interface is inconsistent with DenseSet.

302template <class STy>

303boolset_union(const STy &S) {

304bool Changed =false;

305

306for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;

307 ++SI)

308if (insert(*SI))

309 Changed =true;

310

311return Changed;

312 }

313

314 /// Compute This := This - B

315 /// TODO: We should be able to use set_subtract from SetOperations.h, but

316 /// SetVector interface is inconsistent with DenseSet.

317template <class STy>

318voidset_subtract(const STy &S) {

319for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;

320 ++SI)

321remove(*SI);

322 }

323

324voidswap(SetVector<T, Vector, Set, N> &RHS) {

325 set_.swap(RHS.set_);

326 vector_.swap(RHS.vector_);

327 }

328

329private:

330 /// A wrapper predicate designed for use with std::remove_if.

331 ///

332 /// This predicate wraps a predicate suitable for use with std::remove_if to

333 /// call set_.erase(x) on each element which is slated for removal.

334template <typename UnaryPredicate>

335classTestAndEraseFromSet {

336 UnaryPredicateP;

337set_type &set_;

338

339public:

340 TestAndEraseFromSet(UnaryPredicate P,set_type &set_)

341 :P(std::move(P)), set_(set_) {}

342

343template <typename ArgumentT>

344bool operator()(const ArgumentT &Arg) {

345if (P(Arg)) {

346 set_.erase(Arg);

347returntrue;

348 }

349returnfalse;

350 }

351 };

352

353 [[nodiscard]]staticconstexprbool canBeSmall() {returnN != 0; }

354

355 [[nodiscard]]bool isSmall() const{return set_.empty(); }

356

357void makeBig() {

358ifconstexpr (canBeSmall())

359for (constauto &entry : vector_)

360 set_.insert(entry);

361 }

362

363set_type set_;///< The set.

364vector_type vector_;///< The vector.

365};

366

367/// A SetVector that performs no allocations if smaller than

368/// a certain size.

369template <typename T,unsigned N>

370classSmallSetVector :publicSetVector<T, SmallVector<T, N>, DenseSet<T>, N> {

371public:

372SmallSetVector() =default;

373

374 /// Initialize a SmallSetVector with a range of elements

375template<typename It>

376SmallSetVector(It Start, ItEnd) {

377 this->insert(Start,End);

378 }

379};

380

381}// end namespace llvm

382

383namespacestd {

384

385/// Implement std::swap in terms of SetVector swap.

386template <typename T,typename V,typename S,unsigned N>

387inlinevoidswap(llvm::SetVector<T, V, S, N> &LHS,

388llvm::SetVector<T, V, S, N> &RHS) {

389LHS.swap(RHS);

390}

391

392/// Implement std::swap in terms of SmallSetVector swap.

393template<typename T,unsigned N>

394inlinevoid

395swap(llvm::SmallSetVector<T, N> &LHS,llvm::SmallSetVector<T, N> &RHS) {

396LHS.swap(RHS);

397}

398

399}// end namespace std

400

401#endif// LLVM_ADT_SETVECTOR_H

ArrayRef.h

Compiler.h

DenseSet.h

This file defines the DenseSet and SmallDenseSet classes.

End

bool End

Definition:ELF_riscv.cpp:480

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

#define I(x, y, z)

Definition:MD5.cpp:58

#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.

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

llvm::ArrayRef

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition:ArrayRef.h:41

llvm::SetVector

A vector that has set insertion semantics.

Definition:SetVector.h:57

llvm::SetVector::rend

const_reverse_iterator rend() const

Get a const_reverse_iterator to the beginning of the SetVector.

Definition:SetVector.h:138

llvm::SetVector::getArrayRef

ArrayRef< value_type > getArrayRef() const

Definition:SetVector.h:84

llvm::SetVector::reverse_iterator

typename vector_type::const_reverse_iterator reverse_iterator

Definition:SetVector.h:71

llvm::SetVector::erase

iterator erase(const_iterator I)

Erase a single element from the set vector.

Definition:SetVector.h:212

llvm::SetVector::remove

bool remove(const value_type &X)

Remove an item from the set vector.

Definition:SetVector.h:188

llvm::SetVector::remove_if

bool remove_if(UnaryPredicate P)

Remove items from the set vector based on a predicate function.

Definition:SetVector.h:237

llvm::SetVector::size

size_type size() const

Determine the number of elements in the SetVector.

Definition:SetVector.h:98

llvm::SetVector::front

const value_type & front() const

Return the first element of the SetVector.

Definition:SetVector.h:143

llvm::SetVector::operator==

bool operator==(const SetVector &that) const

Definition:SetVector.h:291

llvm::SetVector::reference

value_type & reference

Definition:SetVector.h:65

llvm::SetVector::const_reverse_iterator

typename vector_type::const_reverse_iterator const_reverse_iterator

Definition:SetVector.h:72

llvm::SetVector::vector_type

Vector vector_type

Definition:SetVector.h:68

llvm::SetVector::back

const value_type & back() const

Return the last element of the SetVector.

Definition:SetVector.h:149

llvm::SetVector::set_union

bool set_union(const STy &S)

Compute This := This u S, return whether 'This' changed.

Definition:SetVector.h:303

llvm::SetVector::value_type

typename Vector::value_type value_type

Definition:SetVector.h:63

llvm::SetVector::rbegin

const_reverse_iterator rbegin() const

Get a const_reverse_iterator to the end of the SetVector.

Definition:SetVector.h:128

llvm::SetVector::takeVector

Vector takeVector()

Clear the SetVector and return the underlying vector.

Definition:SetVector.h:87

llvm::SetVector::iterator

typename vector_type::const_iterator iterator

Definition:SetVector.h:69

llvm::SetVector::set_type

Set set_type

Definition:SetVector.h:67

llvm::SetVector::end

iterator end()

Get an iterator to the end of the SetVector.

Definition:SetVector.h:113

llvm::SetVector::SetVector

SetVector()=default

Construct an empty SetVector.

llvm::SetVector::rbegin

reverse_iterator rbegin()

Get an reverse_iterator to the end of the SetVector.

Definition:SetVector.h:123

llvm::SetVector::const_iterator

typename vector_type::const_iterator const_iterator

Definition:SetVector.h:70

llvm::SetVector::end

const_iterator end() const

Get a const_iterator to the end of the SetVector.

Definition:SetVector.h:118

llvm::SetVector::clear

void clear()

Completely clear the SetVector.

Definition:SetVector.h:273

llvm::SetVector::operator!=

bool operator!=(const SetVector &that) const

Definition:SetVector.h:295

llvm::SetVector::rend

reverse_iterator rend()

Get a reverse_iterator to the beginning of the SetVector.

Definition:SetVector.h:133

llvm::SetVector::size_type

typename vector_type::size_type size_type

Definition:SetVector.h:73

llvm::SetVector::begin

const_iterator begin() const

Get a const_iterator to the beginning of the SetVector.

Definition:SetVector.h:108

llvm::SetVector::count

size_type count(const key_type &key) const

Count the number of elements of a given key in the SetVector.

Definition:SetVector.h:264

llvm::SetVector::empty

bool empty() const

Determine if the SetVector is empty or not.

Definition:SetVector.h:93

llvm::SetVector::insert

void insert(It Start, It End)

Insert a range of elements into the SetVector.

Definition:SetVector.h:182

llvm::SetVector::const_reference

const value_type & const_reference

Definition:SetVector.h:66

llvm::SetVector::begin

iterator begin()

Get an iterator to the beginning of the SetVector.

Definition:SetVector.h:103

llvm::SetVector::SetVector

SetVector(It Start, It End)

Initialize a SetVector with a range of elements.

Definition:SetVector.h:80

llvm::SetVector::swap

void swap(SetVector< T, Vector, Set, N > &RHS)

Definition:SetVector.h:324

llvm::SetVector::key_type

typename Set::key_type key_type

Definition:SetVector.h:64

llvm::SetVector::set_subtract

void set_subtract(const STy &S)

Compute This := This - B TODO: We should be able to use set_subtract from SetOperations....

Definition:SetVector.h:318

llvm::SetVector::insert

bool insert(const value_type &X)

Insert a new element into the SetVector.

Definition:SetVector.h:162

llvm::SetVector::pop_back

void pop_back()

Remove the last element of the SetVector.

Definition:SetVector.h:279

llvm::SetVector::pop_back_val

value_type pop_back_val()

Definition:SetVector.h:285

llvm::SetVector::operator[]

const_reference operator[](size_type n) const

Index into the SetVector.

Definition:SetVector.h:155

llvm::SetVector::contains

bool contains(const key_type &key) const

Check if the SetVector contains the given key.

Definition:SetVector.h:254

llvm::SmallSetVector

A SetVector that performs no allocations if smaller than a certain size.

Definition:SetVector.h:370

llvm::SmallSetVector::SmallSetVector

SmallSetVector(It Start, It End)

Initialize a SmallSetVector with a range of elements.

Definition:SetVector.h:376

llvm::SmallSetVector::SmallSetVector

SmallSetVector()=default

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::find

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

Definition:STLExtras.h:1759

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

llvm::is_contained

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

Definition:STLExtras.h:1903

llvm::VFParamKind::Vector

@ Vector

std

Implement std::hash so that hash_code can be used in STL containers.

Definition:BitVector.h:858

std::swap

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

Definition:BitVector.h:860

#define N