SmallPtrSet.h Source File (original) (raw)

15#ifndef LLVM_ADT_SMALLPTRSET_H

16#define LLVM_ADT_SMALLPTRSET_H

26#include

27#include

28#include

29#include

30#include

31#include <initializer_list>

32#include

33#include

34#include

36namespace llvm {

59protected:

78 const void **RHSSmallStorage,

85 "Initial size must be a power of two!");

86 }

93public:

98 [[nodiscard]] bool empty() const { return size() == 0; }

101

104

105

108 return shrink_and_clear();

109

111 }

112

115 }

116

119

120 if (NewNumEntries == 0)

121 return;

122

124 return;

125

126

128 return;

129

130

131 size_type NewSize = NewNumEntries + (NewNumEntries / 3);

133

134 NewSize = std::max(128u, NewSize);

135 Grow(NewSize);

136 }

137

138protected:

140

142

143

144 return reinterpret_cast<void *>(-1);

145 }

146

150

154

158

162

166

167

168

169

170 std::pair<const void *const *, bool> insert_imp(const void *Ptr) {

172

174 if (Bucket == Ptr)

175 return {&Bucket, false};

176 }

177

178

183 }

184

185 }

186 return insert_imp_big(Ptr);

187 }

188

189

190

191

192

196 if (Bucket == Ptr) {

199 return true;

200 }

201 }

202 return false;

203 }

204

205 auto *Bucket = doFind(Ptr);

206 if (!Bucket)

207 return false;

208

212

213

215 return true;

216 }

217

218

219

220

221 const void *const *find_imp(const void *Ptr) const {

223

224 for (const void *const &Bucket : small_buckets())

225 if (Bucket == Ptr)

226 return &Bucket;

228 }

229

230

231 if (auto *Bucket = doFind(Ptr))

232 return Bucket;

234 }

235

238

239 for (const void *const &Bucket : small_buckets())

240 if (Bucket == Ptr)

241 return true;

242 return false;

243 }

244

245 return doFind(Ptr) != nullptr;

246 }

247

249

250private:

251 LLVM_ABI std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);

252

253 LLVM_ABI const void *const *doFind(const void *Ptr) const;

254 const void *const *FindBucketFor(const void *Ptr) const;

255 LLVM_ABI void shrink_and_clear();

256

257

258 LLVM_ABI void Grow(unsigned NewSize);

259

260protected:

261

262

263 LLVM_ABI void swap(const void **SmallStorage, const void **RHSSmallStorage,

265

268 LLVM_ABI void moveFrom(const void **SmallStorage, unsigned SmallSize,

269 const void **RHSSmallStorage,

271

272private:

273

274 void moveHelper(const void **SmallStorage, unsigned SmallSize,

276

278};

279

280

281

284public:

288 AdvanceIfNotValid();

289 }

290

292 return Bucket == RHS.Bucket;

293 }

295 return Bucket != RHS.Bucket;

296 }

297

298protected:

301 assert(Bucket < End);

302 return const_cast<void *>(*Bucket);

303 }

306 ++Bucket;

307 AdvanceIfNotValid();

308 }

309

310private:

311

312

313

314 void AdvanceIfNotValid() {

315 assert(Bucket <= End);

316 while (Bucket != End &&

319 ++Bucket;

320 }

321

322 using BucketItTy =

323 std::conditional_t<shouldReverseIterate(),

324 std::reverse_iterator<const void *const *>,

325 const void *const *>;

326

327 BucketItTy Bucket;

328 BucketItTy End;

329};

330

331

332template

335

336public:

342

344

345

346

350

355

361};

362

363

364

365

366

367

372

373protected:

374

376

377public:

382

384

385

386

387

388

389 std::pair<iterator, bool> insert(PtrType Ptr) {

390 auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));

391 return {makeIterator(p.first), p.second};

392 }

393

394

395

396

398

399

400

401

402

403

405 return erase_imp(PtrTraits::getAsVoidPointer(Ptr));

406 }

407

408

409

410

411

412

413

414

415

416

417

418

419

420 template bool remove_if(UnaryPredicate P) {

421 bool Removed = false;

424 const void **APtr = Buckets.begin(), **E = Buckets.end();

425 while (APtr != E) {

426 PtrType Ptr = PtrTraits::getFromVoidPointer(const_cast<void *>(*APtr));

427 if (P(Ptr)) {

428 *APtr = *--E;

431 Removed = true;

432 } else {

433 ++APtr;

434 }

435 }

436 return Removed;

437 }

438

439 for (const void *&Bucket : buckets()) {

441 continue;

442 PtrType Ptr = PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket));

443 if (P(Ptr)) {

448 Removed = true;

449 }

450 }

451 return Removed;

452 }

453

454

456 return contains_imp(ConstPtrTraits::getAsVoidPointer(Ptr));

457 }

459 return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));

460 }

461 [[nodiscard]] bool contains(ConstPtrType Ptr) const {

462 return contains_imp(ConstPtrTraits::getAsVoidPointer(Ptr));

463 }

464

465 template void insert(IterT I, IterT E) {

466 for (; I != E; ++I)

468 }

469

470 void insert(std::initializer_list IL) {

471 insert(IL.begin(), IL.end());

472 }

473

477

480 return makeIterator(EndPointer() - 1);

481 else

482 return makeIterator(CurArray);

483 }

485

486private:

487

488 iterator makeIterator(const void *const *P) const {

491 else

493 }

494};

495

496

497

498

499

500template

503 if (LHS.size() != RHS.size())

504 return false;

505

506 for (const auto *KV : LHS)

507 if ( RHS .count(KV))

508 return false;

509

510 return true;

511}

512

513

514

515

516template

519 return !(LHS == RHS);

520}

521

522

523

524

525

526template <class PtrType, unsigned SmallSize>

528

529

530

531 static_assert(SmallSize <= 32, "SmallSize should be small");

532

534

535

537

538 const void *SmallStorage[SmallSizePowTwo];

539

540public:

541 SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}

544 : BaseT(SmallStorage, SmallSizePowTwo, that.SmallStorage,

546

547 template

551

552 template

555

557 : BaseT(SmallStorage, SmallSizePowTwo) {

558 this->insert(IL.begin(), IL.end());

559 }

560

563 if (&RHS != this)

565 return *this;

566 }

567

570 if (&RHS != this)

571 this->moveFrom(SmallStorage, SmallSizePowTwo, RHS.SmallStorage,

572 std::move(RHS));

573 return *this;

574 }

575

577 operator=(std::initializer_list IL) {

579 this->insert(IL.begin(), IL.end());

580 return *this;

581 }

582

583

587};

588

589}

590

591namespace std {

592

593

594template <class T, unsigned N>

598

599}

600

601#endif

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

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes.

#define LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE

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

This file contains library features backported from future STL versions.

bool isHandleInSync() const

SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s,...

Definition SmallPtrSet.h:56

size_type size() const

Definition SmallPtrSet.h:99

iterator_range< const void ** > buckets()

Definition SmallPtrSet.h:159

void clear()

Definition SmallPtrSet.h:102

const void *const * find_imp(const void *Ptr) const

Returns the raw pointer needed to construct an iterator.

Definition SmallPtrSet.h:221

unsigned size_type

Definition SmallPtrSet.h:94

unsigned NumTombstones

Number of tombstones in CurArray.

Definition SmallPtrSet.h:70

iterator_range< const void *const * > small_buckets() const

Definition SmallPtrSet.h:155

LLVM_ABI SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)

bool isSmall() const

Definition SmallPtrSet.h:248

SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)

Definition SmallPtrSet.h:81

unsigned NumEntries

Number of elements in CurArray that contain a value.

Definition SmallPtrSet.h:68

const void ** CurArray

The current set of buckets, in either small or big representation.

Definition SmallPtrSet.h:61

bool IsSmall

Whether the set is in small representation.

Definition SmallPtrSet.h:72

LLVM_ABI void copyFrom(const void **SmallStorage, const SmallPtrSetImplBase &RHS)

void reserve(size_type NewNumEntries)

Definition SmallPtrSet.h:117

bool contains_imp(const void *Ptr) const

Definition SmallPtrSet.h:236

friend class SmallPtrSetIteratorImpl

Definition SmallPtrSet.h:57

std::pair< const void *const *, bool > insert_imp(const void *Ptr)

insert_imp - This returns true if the pointer was new to the set, false if it was already in the set.

Definition SmallPtrSet.h:170

SmallPtrSetImplBase & operator=(const SmallPtrSetImplBase &)=delete

LLVM_ABI void moveFrom(const void **SmallStorage, unsigned SmallSize, const void **RHSSmallStorage, SmallPtrSetImplBase &&RHS)

iterator_range< const void ** > small_buckets()

Definition SmallPtrSet.h:151

unsigned CurArraySize

CurArraySize - The allocated size of CurArray, always a power of two.

Definition SmallPtrSet.h:63

iterator_range< const void *const * > buckets() const

Definition SmallPtrSet.h:163

const void ** EndPointer() const

Definition SmallPtrSet.h:147

bool erase_imp(const void *Ptr)

erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return fa...

Definition SmallPtrSet.h:193

~SmallPtrSetImplBase()

Definition SmallPtrSet.h:88

static void * getEmptyMarker()

Definition SmallPtrSet.h:141

static void * getTombstoneMarker()

Definition SmallPtrSet.h:139

LLVM_ABI void swap(const void **SmallStorage, const void **RHSSmallStorage, SmallPtrSetImplBase &RHS)

swap - Swaps the elements of two sets.

size_type capacity() const

Definition SmallPtrSet.h:100

bool empty() const

Definition SmallPtrSet.h:98

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

Definition SmallPtrSet.h:368

SmallPtrSetIterator< PtrType > const_iterator

Definition SmallPtrSet.h:379

iterator insert(iterator, PtrType Ptr)

Insert the given pointer with an iterator hint that is ignored.

Definition SmallPtrSet.h:397

bool erase(PtrType Ptr)

Remove pointer from the set.

Definition SmallPtrSet.h:404

iterator find(ConstPtrType Ptr) const

Definition SmallPtrSet.h:458

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

Definition SmallPtrSet.h:455

SmallPtrSetImpl(const SmallPtrSetImpl &)=delete

LLVM_ABI SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)

void insert(IterT I, IterT E)

Definition SmallPtrSet.h:465

bool remove_if(UnaryPredicate P)

Remove elements that match the given predicate.

Definition SmallPtrSet.h:420

iterator end() const

Definition SmallPtrSet.h:484

ConstPtrType key_type

Definition SmallPtrSet.h:380

void insert_range(Range &&R)

Definition SmallPtrSet.h:474

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

Definition SmallPtrSet.h:389

SmallPtrSetIterator< PtrType > iterator

Definition SmallPtrSet.h:378

iterator begin() const

Definition SmallPtrSet.h:478

void insert(std::initializer_list< PtrType > IL)

Definition SmallPtrSet.h:470

PtrType value_type

Definition SmallPtrSet.h:381

bool contains(ConstPtrType Ptr) const

Definition SmallPtrSet.h:461

bool operator!=(const SmallPtrSetIteratorImpl &RHS) const

Definition SmallPtrSet.h:294

void * dereference() const

Definition SmallPtrSet.h:299

SmallPtrSetIteratorImpl(const void *const *BP, const void *const *E, const DebugEpochBase &Epoch)

Definition SmallPtrSet.h:285

void increment()

Definition SmallPtrSet.h:304

bool operator==(const SmallPtrSetIteratorImpl &RHS) const

Definition SmallPtrSet.h:291

SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.

Definition SmallPtrSet.h:333

const PtrTy operator*() const

Definition SmallPtrSet.h:347

SmallPtrSetIteratorImpl(const void *const *BP, const void *const *E, const DebugEpochBase &Epoch)

Definition SmallPtrSet.h:285

std::ptrdiff_t difference_type

Definition SmallPtrSet.h:340

PtrTy value_type

Definition SmallPtrSet.h:337

PtrTy pointer

Definition SmallPtrSet.h:339

SmallPtrSetIterator operator++(int)

Definition SmallPtrSet.h:356

SmallPtrSetIterator & operator++()

Definition SmallPtrSet.h:351

std::forward_iterator_tag iterator_category

Definition SmallPtrSet.h:341

PtrTy reference

Definition SmallPtrSet.h:338

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

Definition SmallPtrSet.h:527

SmallPtrSet(SmallPtrSet &&that)

Definition SmallPtrSet.h:543

SmallPtrSet(It I, It E)

Definition SmallPtrSet.h:548

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

Definition SmallPtrSet.h:553

SmallPtrSet< PtrType, SmallSize > & operator=(SmallPtrSet< PtrType, SmallSize > &&RHS)

Definition SmallPtrSet.h:569

void swap(SmallPtrSet< PtrType, SmallSize > &RHS)

swap - Swaps the elements of two sets.

Definition SmallPtrSet.h:584

SmallPtrSet(std::initializer_list< PtrType > IL)

Definition SmallPtrSet.h:556

SmallPtrSet< PtrType, SmallSize > & operator=(const SmallPtrSet< PtrType, SmallSize > &RHS)

Definition SmallPtrSet.h:562

SmallPtrSet(const SmallPtrSet &that)

Definition SmallPtrSet.h:542

SmallPtrSet< PtrType, SmallSize > & operator=(std::initializer_list< PtrType > IL)

Definition SmallPtrSet.h:577

SmallPtrSet()

Definition SmallPtrSet.h:541

A range adaptor for a pair of iterators.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

This is an optimization pass for GlobalISel generic memory operations.

constexpr T bit_ceil_constexpr(T Value)

Returns the smallest integral power of two no smaller than Value if Value is nonzero.

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

bool operator!=(uint64_t V1, const APInt &V2)

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

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

T bit_ceil(T Value)

Returns the smallest integral power of two no smaller than Value if Value is nonzero.

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

constexpr bool has_single_bit(T Value) noexcept

constexpr bool shouldReverseIterate()

OutputIt move(R &&Range, OutputIt Out)

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

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.

A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...

std::conditional_t< std::is_pointer_v< T >, const std::remove_pointer_t< T > *, const T > type