SetVector.h Source File (original) (raw)

20#ifndef LLVM_ADT_SETVECTOR_H

21#define LLVM_ADT_SETVECTOR_H

30#include

32namespace 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!");

62 using const_arg_type =

65public:

66 using value_type = typename Vector::value_type;

67 using key_type = typename Set::key_type;

82 template

87 template

95 set_.clear();

96 return std::move(vector_);

97 }

100 [[nodiscard]] bool empty() const { return vector_.empty(); }

101

102

103 [[nodiscard]] size_type size() const { return vector_.size(); }

104

105

107

108

110

111

112 [[nodiscard]] iterator end() { return vector_.end(); }

113

114

116

117

119

120

122 return vector_.rbegin();

123 }

124

125

127

128

130

131

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

134 return vector_.front();

135 }

136

137

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

140 return vector_.back();

141 }

142

143

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

146 return vector_[n];

147 }

148

149

150

152 if constexpr (canBeSmall())

153 if (isSmall()) {

155 vector_.push_back(X);

156 if (vector_.size() > N)

157 makeBig();

158 return true;

159 }

160 return false;

161 }

162

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

164 if (result)

165 vector_.push_back(X);

166 return result;

167 }

168

169

170 template

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

174 }

175

179

180

182 if constexpr (canBeSmall())

183 if (isSmall()) {

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

186 vector_.erase(I);

187 return true;

188 }

189 return false;

190 }

191

192 if (set_.erase(X)) {

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

195 vector_.erase(I);

196 return true;

197 }

198 return false;

199 }

200

201

202

203

204

206 if constexpr (canBeSmall())

207 if (isSmall())

208 return vector_.erase(I);

209

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

212 set_.erase(V);

213 return vector_.erase(I);

214 }

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229 template

232 if constexpr (canBeSmall())

233 if (isSmall())

235

237 if (P(V)) {

238 set_.erase(V);

239 return true;

240 }

241 return false;

242 });

243 }();

244

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

246 return false;

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

248 return true;

249 }

250

251

252 [[nodiscard]] bool contains(const_arg_type key) const {

253 if constexpr (canBeSmall())

254 if (isSmall())

256

258 }

259

260

261

265

266

268 set_.clear();

269 vector_.clear();

270 }

271

272

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

275 set_.erase(back());

276 vector_.pop_back();

277 }

278

284

286 return vector_ == that.vector_;

287 }

288

290 return vector_ != that.vector_;

291 }

292

293

294

295

296 template

299

300 for (const auto &Elem : S)

303

305 }

306

307

308

309

310 template

312 for (const auto &Elem : S)

314 }

315

317 set_.swap(RHS.set_);

318 vector_.swap(RHS.vector_);

319 }

320

321private:

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

323

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

325

326 void makeBig() {

327 if constexpr (canBeSmall())

328 for (const auto &entry : vector_)

329 set_.insert(entry);

330 }

331

334};

335

336

337

338template <typename T, unsigned N>

343

344}

345

346namespace std {

347

348

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

354

355

356template<typename T, unsigned N>

357inline void

361

362}

363

364#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file defines the DenseSet and SmallDenseSet classes.

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

This file contains library features backported from future STL versions.

This file defines the SmallVector class.

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

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

Implements a dense probed hash-table based set.

A vector that has set insertion semantics.

Definition SetVector.h:57

const_reverse_iterator rend() const

Get a const_reverse_iterator to the beginning of the SetVector.

Definition SetVector.h:129

ArrayRef< value_type > getArrayRef() const

Definition SetVector.h:91

typename vector_type::const_reverse_iterator reverse_iterator

Definition SetVector.h:74

iterator erase(const_iterator I)

Erase a single element from the set vector.

Definition SetVector.h:205

bool remove(const value_type &X)

Remove an item from the set vector.

Definition SetVector.h:181

bool remove_if(UnaryPredicate P)

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

Definition SetVector.h:230

size_type size() const

Determine the number of elements in the SetVector.

Definition SetVector.h:103

const value_type & front() const

Return the first element of the SetVector.

Definition SetVector.h:132

bool operator==(const SetVector &that) const

Definition SetVector.h:285

value_type & reference

Definition SetVector.h:68

typename vector_type::const_reverse_iterator const_reverse_iterator

Definition SetVector.h:75

SmallVector< EdgeType *, 0 > vector_type

Definition SetVector.h:71

const value_type & back() const

Return the last element of the SetVector.

Definition SetVector.h:138

void insert_range(Range &&R)

Definition SetVector.h:176

bool set_union(const STy &S)

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

Definition SetVector.h:297

typename SmallVector< EdgeType *, 0 >::value_type value_type

Definition SetVector.h:66

const_reverse_iterator rbegin() const

Get a const_reverse_iterator to the end of the SetVector.

Definition SetVector.h:121

size_type count(const_arg_type key) const

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

Definition SetVector.h:262

Vector takeVector()

Clear the SetVector and return the underlying vector.

Definition SetVector.h:94

typename vector_type::const_iterator iterator

Definition SetVector.h:72

DenseSet< EdgeType * > set_type

Definition SetVector.h:70

iterator end()

Get an iterator to the end of the SetVector.

Definition SetVector.h:112

SetVector()=default

Construct an empty SetVector.

bool contains(const_arg_type key) const

Check if the SetVector contains the given key.

Definition SetVector.h:252

SetVector(llvm::from_range_t, Range &&R)

Definition SetVector.h:88

reverse_iterator rbegin()

Get an reverse_iterator to the end of the SetVector.

Definition SetVector.h:118

typename vector_type::const_iterator const_iterator

Definition SetVector.h:73

const_iterator end() const

Get a const_iterator to the end of the SetVector.

Definition SetVector.h:115

void clear()

Completely clear the SetVector.

Definition SetVector.h:267

bool operator!=(const SetVector &that) const

Definition SetVector.h:289

reverse_iterator rend()

Get a reverse_iterator to the beginning of the SetVector.

Definition SetVector.h:126

typename vector_type::size_type size_type

Definition SetVector.h:76

const_iterator begin() const

Get a const_iterator to the beginning of the SetVector.

Definition SetVector.h:109

bool empty() const

Determine if the SetVector is empty or not.

Definition SetVector.h:100

void insert(It Start, It End)

Insert a range of elements into the SetVector.

Definition SetVector.h:171

const value_type & const_reference

Definition SetVector.h:69

iterator begin()

Get an iterator to the beginning of the SetVector.

Definition SetVector.h:106

SetVector(It Start, It End)

Initialize a SetVector with a range of elements.

Definition SetVector.h:83

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

Definition SetVector.h:316

typename DenseSet< EdgeType * >::key_type key_type

Definition SetVector.h:67

void set_subtract(const STy &S)

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

Definition SetVector.h:311

bool insert(const value_type &X)

Insert a new element into the SetVector.

Definition SetVector.h:151

void pop_back()

Remove the last element of the SetVector.

Definition SetVector.h:273

value_type pop_back_val()

Definition SetVector.h:279

const_reference operator[](size_type n) const

Index into the SetVector.

Definition SetVector.h:144

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

Definition SetVector.h:339

std::reverse_iterator< const_iterator > const_reverse_iterator

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

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.

constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))

Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...

constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))

Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...

auto remove_if(R &&Range, UnaryPredicate P)

Provide wrappers to std::remove_if 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.

std::conditional_t< std::is_pointer_v< T >, typename add_const_past_pointer< T >::type, const T & > type