SmallPtrSet.h Source File (original) (raw)

15#ifndef LLVM_ADT_SMALLPTRSET_H

16#define LLVM_ADT_SMALLPTRSET_H

22#include

23#include

24#include

25#include

26#include

27#include <initializer_list>

28#include

29#include

30#include

32namespace llvm {

55protected:

79 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&

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

81 }

86 }

88public:

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

100

103 return shrink_and_clear();

104

106 }

107

110 }

111

114

115 if (NumEntries == 0)

116 return;

117

119 return;

120

121

123 return;

124

125

126 size_type NewSize = NumEntries + (NumEntries / 3);

128

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

130 Grow(NewSize);

131 }

132

133protected:

135

137

138

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

140 }

141

144 }

145

146

147

148

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

151

153 APtr != E; ++APtr) {

154 const void *Value = *APtr;

156 return std::make_pair(APtr, false);

157 }

158

159

164 }

165

166 }

167 return insert_imp_big(Ptr);

168 }

169

170

171

172

173

177 APtr != E; ++APtr) {

178 if (*APtr == Ptr) {

181 return true;

182 }

183 }

184 return false;

185 }

186

187 auto *Bucket = doFind(Ptr);

188 if (!Bucket)

189 return false;

190

193

194

196 return true;

197 }

198

199

200

201

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

204

205 for (const void *const *APtr = CurArray, *const *E =

207 APtr != E; ++APtr)

208 if (*APtr == Ptr)

209 return APtr;

211 }

212

213

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

215 return Bucket;

217 }

218

221

222 const void *const *APtr = CurArray;

224 for (; APtr != E; ++APtr)

225 if (*APtr == Ptr)

226 return true;

227 return false;

228 }

229

230 return doFind(Ptr) != nullptr;

231 }

232

234

235private:

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

237

238 const void *const *doFind(const void *Ptr) const;

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

240 void shrink_and_clear();

241

242

243 void Grow(unsigned NewSize);

244

245protected:

246

247

248 void swap(const void **SmallStorage, const void **RHSSmallStorage,

250

252 void moveFrom(const void **SmallStorage, unsigned SmallSize,

254

255private:

256

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

259

261};

262

263

264

266protected:

268 const void *const *End;

269

270public:

275 return;

276 }

278 }

279

282 }

285 }

286

287protected:

288

289

290

297 }

304 }

305 }

306};

307

308

309template

314

315public:

321

325

326

327

329 assert(isHandleInSync() && "invalid iterator access!");

332 return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));

333 }

335 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));

336 }

337

339 assert(isHandleInSync() && "invalid iterator access!");

341 --Bucket;

342 RetreatIfNotValid();

343 return *this;

344 }

345 ++Bucket;

346 AdvanceIfNotValid();

347 return *this;

348 }

349

352 ++*this;

353 return tmp;

354 }

355};

356

357

358

359

360

361

362template

367

368protected:

369

371

372public:

377

379

380

381

382

383

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

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

386 return std::make_pair(makeIterator(p.first), p.second);

387 }

388

389

390

391

394 }

395

396

397

398

399

400

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

403 }

404

405

406

407

408

409

410

411

412

413

414

415

416

417 template

419 bool Removed = false;

422 while (APtr != E) {

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

424 if (P(Ptr)) {

425 *APtr = *--E;

428 Removed = true;

429 } else {

430 ++APtr;

431 }

432 }

433 return Removed;

434 }

435

437 const void *Value = *APtr;

439 continue;

440 PtrType Ptr = PtrTraits::getFromVoidPointer(const_cast<void *>(Value));

441 if (P(Ptr)) {

445 Removed = true;

446 }

447 }

448 return Removed;

449 }

450

451

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

454 }

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

457 }

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

460 }

461

462 template

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

466 }

467

468 void insert(std::initializer_list IL) {

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

470 }

471

474 return makeIterator(EndPointer() - 1);

475 return makeIterator(CurArray);

476 }

478

479private:

480

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

485 }

486};

487

488

489

490

491

492template

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

496 return false;

497

498 for (const auto *KV : LHS)

499 if ( RHS .count(KV))

500 return false;

501

502 return true;

503}

504

505

506

507

508template

511 return !(LHS == RHS);

512}

513

514

515

516

517

518template<class PtrType, unsigned SmallSize>

520

521

522

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

524

526

527

528

529 static constexpr size_t RoundUpToPowerOfTwo(size_t X) {

530 size_t C = 1;

531 size_t CMax = C << (std::numeric_limits<size_t>::digits - 1);

532 while (C < X && C < CMax)

533 C <<= 1;

534 return C;

535 }

536

537

538 static constexpr size_t SmallSizePowTwo = RoundUpToPowerOfTwo(SmallSize);

539

540 const void *SmallStorage[SmallSizePowTwo];

541

542public:

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

548

549 template

552 }

553

555 : BaseT(SmallStorage, SmallSizePowTwo) {

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

557 }

558

561 if (&RHS != this)

563 return *this;

564 }

565

568 if (&RHS != this)

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

570 std::move(RHS));

571 return *this;

572 }

573

575 operator=(std::initializer_list IL) {

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

578 return *this;

579 }

580

581

584 }

585};

586

587}

588

589namespace std {

590

591

592 template<class T, unsigned N>

595 }

596

597}

598

599#endif

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

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

#define LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE

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

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

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

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

Returns the raw pointer needed to construct an iterator.

unsigned NumTombstones

Number of tombstones in CurArray.

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

SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)

const void ** CurArray

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

bool IsSmall

Whether the set is in small representation.

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

bool contains_imp(const void *Ptr) const

unsigned NumNonEmpty

Number of elements in CurArray that contain a value or are a tombstone.

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.

SmallPtrSetImplBase & operator=(const SmallPtrSetImplBase &)=delete

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

unsigned CurArraySize

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

const void ** EndPointer() const

bool erase_imp(const void *Ptr)

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

static void * getEmptyMarker()

void reserve(size_type NumEntries)

static void * getTombstoneMarker()

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

swap - Swaps the elements of two sets.

size_type capacity() const

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

iterator insert(iterator, PtrType Ptr)

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

bool erase(PtrType Ptr)

Remove pointer from the set.

iterator find(ConstPtrType Ptr) const

size_type count(ConstPtrType Ptr) const

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

SmallPtrSetImpl(const SmallPtrSetImpl &)=delete

void insert(IterT I, IterT E)

bool remove_if(UnaryPredicate P)

Remove elements that match the given predicate.

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

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

SmallPtrSetIterator< PtrType > iterator

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

bool contains(ConstPtrType Ptr) const

SmallPtrSetIteratorImpl - This is the common base class shared between all instances of SmallPtrSetIt...

bool operator!=(const SmallPtrSetIteratorImpl &RHS) const

SmallPtrSetIteratorImpl(const void *const *BP, const void *const *E)

const void *const * Bucket

bool operator==(const SmallPtrSetIteratorImpl &RHS) const

void AdvanceIfNotValid()

AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket that is.

SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.

const PtrTy operator*() const

std::ptrdiff_t difference_type

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

SmallPtrSetIterator operator++(int)

SmallPtrSetIterator & operator++()

std::forward_iterator_tag iterator_category

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

SmallPtrSet(SmallPtrSet &&that)

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

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

swap - Swaps the elements of two sets.

SmallPtrSet(std::initializer_list< PtrType > IL)

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

SmallPtrSet(const SmallPtrSet &that)

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

LLVM Value Representation.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

unsigned Log2_32_Ceil(uint32_t Value)

Return the ceil log base 2 of the specified value, 32 if the value is zero.

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

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

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