SetVector.h Source File (original) (raw)

20#ifndef LLVM_ADT_SETVECTOR_H

21#define LLVM_ADT_SETVECTOR_H

28#include

29#include

31namespace llvm {

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

56 typename Set = DenseSet, unsigned N = 0>

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

62public:

63 using value_type = typename Vector::value_type;

64 using key_type = typename Set::key_type;

69 using iterator = typename vector_type::const_iterator;

71 using reverse_iterator = typename vector_type::const_reverse_iterator;

73 using size_type = typename vector_type::size_type;

79 template

82 }

88 set_.clear();

89 return std::move(vector_);

90 }

94 return vector_.empty();

95 }

99 return vector_.size();

100 }

101

102

104 return vector_.begin();

105 }

106

107

109 return vector_.begin();

110 }

111

112

114 return vector_.end();

115 }

116

117

119 return vector_.end();

120 }

121

122

124 return vector_.rbegin();

125 }

126

127

129 return vector_.rbegin();

130 }

131

132

134 return vector_.rend();

135 }

136

137

139 return vector_.rend();

140 }

141

142

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

145 return vector_.front();

146 }

147

148

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

151 return vector_.back();

152 }

153

154

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

157 return vector_[n];

158 }

159

160

161

163 if constexpr (canBeSmall())

164 if (isSmall()) {

166 vector_.push_back(X);

167 if (vector_.size() > N)

168 makeBig();

169 return true;

170 }

171 return false;

172 }

173

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

175 if (result)

176 vector_.push_back(X);

177 return result;

178 }

179

180

181 template

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

185 }

186

187

189 if constexpr (canBeSmall())

190 if (isSmall()) {

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

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

193 vector_.erase(I);

194 return true;

195 }

196 return false;

197 }

198

199 if (set_.erase(X)) {

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

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

202 vector_.erase(I);

203 return true;

204 }

205 return false;

206 }

207

208

209

210

211

213 if constexpr (canBeSmall())

214 if (isSmall())

215 return vector_.erase(I);

216

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

219 set_.erase(V);

220 return vector_.erase(I);

221 }

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236 template

238 typename vector_type::iterator I = [this, P] {

239 if constexpr (canBeSmall())

240 if (isSmall())

242

244 TestAndEraseFromSet(P, set_));

245 }();

246

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

248 return false;

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

250 return true;

251 }

252

253

255 if constexpr (canBeSmall())

256 if (isSmall())

258

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

260 }

261

262

263

265 if constexpr (canBeSmall())

266 if (isSmall())

268

269 return set_.count(key);

270 }

271

272

274 set_.clear();

275 vector_.clear();

276 }

277

278

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

281 set_.erase(back());

282 vector_.pop_back();

283 }

284

288 return Ret;

289 }

290

292 return vector_ == that.vector_;

293 }

294

296 return vector_ != that.vector_;

297 }

298

299

300

301

302 template

304 bool Changed = false;

305

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

307 ++SI)

309 Changed = true;

310

311 return Changed;

312 }

313

314

315

316

317 template

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

320 ++SI)

322 }

323

325 set_.swap(RHS.set_);

326 vector_.swap(RHS.vector_);

327 }

328

329private:

330

331

332

333

334 template

335 class TestAndEraseFromSet {

336 UnaryPredicate P;

338

339 public:

340 TestAndEraseFromSet(UnaryPredicate P, set_type &set_)

342

343 template

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

345 if (P(Arg)) {

346 set_.erase(Arg);

347 return true;

348 }

349 return false;

350 }

351 };

352

353 [[nodiscard]] static constexpr bool canBeSmall() { return N != 0; }

354

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

356

357 void makeBig() {

358 if constexpr (canBeSmall())

359 for (const auto &entry : vector_)

360 set_.insert(entry);

361 }

362

365};

366

367

368

369template <typename T, unsigned N>

371public:

373

374

375 template

378 }

379};

380

381}

382

383namespace std {

384

385

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

390}

391

392

393template<typename T, unsigned N>

394inline void

397}

398

399}

400

401#endif

This file defines the DenseSet and SmallDenseSet classes.

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

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file defines the SmallVector class.

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

A vector that has set insertion semantics.

const_reverse_iterator rend() const

Get a const_reverse_iterator to the beginning of the SetVector.

ArrayRef< value_type > getArrayRef() const

typename vector_type::const_reverse_iterator reverse_iterator

iterator erase(const_iterator I)

Erase a single element from the set vector.

bool remove(const value_type &X)

Remove an item from the set vector.

bool remove_if(UnaryPredicate P)

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

size_type size() const

Determine the number of elements in the SetVector.

const value_type & front() const

Return the first element of the SetVector.

bool operator==(const SetVector &that) const

typename vector_type::const_reverse_iterator const_reverse_iterator

const value_type & back() const

Return the last element of the SetVector.

bool set_union(const STy &S)

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

typename Vector::value_type value_type

const_reverse_iterator rbegin() const

Get a const_reverse_iterator to the end of the SetVector.

Vector takeVector()

Clear the SetVector and return the underlying vector.

typename vector_type::const_iterator iterator

iterator end()

Get an iterator to the end of the SetVector.

SetVector()=default

Construct an empty SetVector.

reverse_iterator rbegin()

Get an reverse_iterator to the end of the SetVector.

typename vector_type::const_iterator const_iterator

const_iterator end() const

Get a const_iterator to the end of the SetVector.

void clear()

Completely clear the SetVector.

bool operator!=(const SetVector &that) const

reverse_iterator rend()

Get a reverse_iterator to the beginning of the SetVector.

typename vector_type::size_type size_type

const_iterator begin() const

Get a const_iterator to the beginning of the SetVector.

size_type count(const key_type &key) const

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

bool empty() const

Determine if the SetVector is empty or not.

void insert(It Start, It End)

Insert a range of elements into the SetVector.

const value_type & const_reference

iterator begin()

Get an iterator to the beginning of the SetVector.

SetVector(It Start, It End)

Initialize a SetVector with a range of elements.

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

typename Set::key_type key_type

void set_subtract(const STy &S)

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

bool insert(const value_type &X)

Insert a new element into the SetVector.

void pop_back()

Remove the last element of the SetVector.

value_type pop_back_val()

const_reference operator[](size_type n) const

Index into the SetVector.

bool contains(const key_type &key) const

Check if the SetVector contains the given key.

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

SmallSetVector(It Start, It End)

Initialize a SmallSetVector with a range of elements.

This is an optimization pass for GlobalISel generic memory operations.

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

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

auto remove_if(R &&Range, UnaryPredicate P)

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

OutputIt move(R &&Range, OutputIt Out)

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

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

Returns true if Element is found in Range.

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

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

Implement std::swap in terms of BitVector swap.