DenseMap.h Source File (original) (raw)

14#ifndef LLVM_ADT_DENSEMAP_H

15#define LLVM_ADT_DENSEMAP_H

28#include

29#include

30#include

31#include

32#include <initializer_list>

33#include

34#include

35#include <type_traits>

36#include

38namespace llvm {

44template <typename KeyT, typename ValueT>

46 using std::pair<KeyT, ValueT>::pair;

48 KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }

49 const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }

50 ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }

51 const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }

52};

54}

56template <typename KeyT, typename ValueT,

57 typename KeyInfoT = DenseMapInfo,

59 bool IsConst = false>

60class DenseMapIterator;

62template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,

63 typename BucketT>

65 template

68public:

92 [[nodiscard]] inline auto keys() {

93 return map_range(*this, [](const BucketT &P) { return P.getFirst(); });

94 }

97 [[nodiscard]] inline auto values() {

98 return map_range(*this, [](const BucketT &P) { return P.getSecond(); });

99 }

100

101 [[nodiscard]] inline auto keys() const {

102 return map_range(*this, [](const BucketT &P) { return P.getFirst(); });

103 }

104

105 [[nodiscard]] inline auto values() const {

106 return map_range(*this, [](const BucketT &P) { return P.getSecond(); });

107 }

108

109 [[nodiscard]] bool empty() const { return getNumEntries() == 0; }

110 [[nodiscard]] unsigned size() const { return getNumEntries(); }

111

112

113

117 if (NumBuckets > getNumBuckets())

118 grow(NumBuckets);

119 }

120

123 if (getNumEntries() == 0 && getNumTombstones() == 0)

124 return;

125

126

127

128 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {

130 return;

131 }

132

133 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

134 if constexpr (std::is_trivially_destructible_v) {

135

136 for (BucketT &B : buckets())

137 B.getFirst() = EmptyKey;

138 } else {

139 const KeyT TombstoneKey = KeyInfoT::getTombstoneKey();

140 unsigned NumEntries = getNumEntries();

141 for (BucketT &B : buckets()) {

142 if (!KeyInfoT::isEqual(B.getFirst(), EmptyKey)) {

143 if (!KeyInfoT::isEqual(B.getFirst(), TombstoneKey)) {

144 B.getSecond().~ValueT();

145 --NumEntries;

146 }

147 B.getFirst() = EmptyKey;

148 }

149 }

150 assert(NumEntries == 0 && "Node count imbalance!");

151 (void)NumEntries;

152 }

153 setNumEntries(0);

154 setNumTombstones(0);

155 }

156

158 auto [Reallocate, NewNumBuckets] = derived().planShrinkAndClear();

160 if (!Reallocate) {

162 return;

163 }

164 derived().deallocateBuckets();

166 }

167

168

169 [[nodiscard]] bool contains(const_arg_type_t Val) const {

170 return doFind(Val) != nullptr;

171 }

172

173

177

184

185

186

187

188

189

190 template

192 if (BucketT *Bucket = doFind(Val))

193 return makeIterator(Bucket);

194 return end();

195 }

196 template

198 if (const BucketT *Bucket = doFind(Val))

199 return makeConstIterator(Bucket);

200 return end();

201 }

202

203

204

205 [[nodiscard]] ValueT lookup(const_arg_type_t Val) const {

206 if (const BucketT *Bucket = doFind(Val))

207 return Bucket->getSecond();

208 return ValueT();

209 }

210

211

212

213

214 template <typename U = std::remove_cv_t>

215 [[nodiscard]] ValueT lookup_or(const_arg_type_t Val,

217 if (const BucketT *Bucket = doFind(Val))

218 return Bucket->getSecond();

220 }

221

222

223

224 [[nodiscard]] ValueT &at(const_arg_type_t Val) {

225 auto Iter = this->find(std::move(Val));

226 assert(Iter != this->end() && "DenseMap::at failed due to a missing key");

227 return Iter->second;

228 }

229

230

231

232 [[nodiscard]] const ValueT &at(const_arg_type_t Val) const {

233 auto Iter = this->find(std::move(Val));

234 assert(Iter != this->end() && "DenseMap::at failed due to a missing key");

235 return Iter->second;

236 }

237

238

239

240

241 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {

242 return try_emplace_impl(KV.first, KV.second);

243 }

244

245

246

247

248 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {

249 return try_emplace_impl(std::move(KV.first), std::move(KV.second));

250 }

251

252

253

254

255 template <typename... Ts>

257 return try_emplace_impl(std::move(Key), std::forward(Args)...);

258 }

259

260

261

262

263 template <typename... Ts>

265 return try_emplace_impl(Key, std::forward(Args)...);

266 }

267

268

269

270

271

272

273 template

274 std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,

275 const LookupKeyT &Val) {

276 BucketT *TheBucket;

277 if (LookupBucketFor(Val, TheBucket))

278 return {makeIterator(TheBucket), false};

279

280

281 TheBucket = findBucketForInsertion(Val, TheBucket);

282 TheBucket->getFirst() = std::move(KV.first);

283 ::new (&TheBucket->getSecond()) ValueT(std::move(KV.second));

284 return {makeIterator(TheBucket), true};

285 }

286

287

288 template void insert(InputIt I, InputIt E) {

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

291 }

292

293

297

298 template

301 if (!Ret.second)

302 Ret.first->second = std::forward(Val);

303 return Ret;

304 }

305

306 template

308 auto Ret = try_emplace(std::move(Key), std::forward(Val));

309 if (!Ret.second)

310 Ret.first->second = std::forward(Val);

311 return Ret;

312 }

313

314 template <typename... Ts>

316 auto Ret = try_emplace(Key, std::forward(Args)...);

317 if (!Ret.second)

318 Ret.first->second = ValueT(std::forward(Args)...);

319 return Ret;

320 }

321

322 template <typename... Ts>

324 auto Ret = try_emplace(std::move(Key), std::forward(Args)...);

325 if (!Ret.second)

326 Ret.first->second = ValueT(std::forward(Args)...);

327 return Ret;

328 }

329

331 BucketT *TheBucket = doFind(Val);

332 if (!TheBucket)

333 return false;

334

335 TheBucket->getSecond().~ValueT();

336 TheBucket->getFirst() = KeyInfoT::getTombstoneKey();

337 decrementNumEntries();

338 incrementNumTombstones();

339 return true;

340 }

342 BucketT *TheBucket = &*I;

343 TheBucket->getSecond().~ValueT();

344 TheBucket->getFirst() = KeyInfoT::getTombstoneKey();

345 decrementNumEntries();

346 incrementNumTombstones();

347 }

348

350 return lookupOrInsertIntoBucket(Key).first->second;

351 }

352

354 return lookupOrInsertIntoBucket(std::move(Key)).first->second;

355 }

356

357

358

359

361 return Ptr >= getBuckets() && Ptr < getBucketsEnd();

362 }

363

364

365

366

368 return getBuckets();

369 }

370

373 RHS.incrementEpoch();

374 derived().swapImpl(RHS);

375 }

376

377protected:

379

381

383 if (derived().allocateBuckets(NewNumBuckets)) {

385 } else {

386 setNumEntries(0);

387 setNumTombstones(0);

388 }

389 }

390

392

393

394 if constexpr (std::is_trivially_destructible_v &&

395 std::is_trivially_destructible_v)

396 return;

397

398 if (getNumBuckets() == 0)

399 return;

400

401 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

402 const KeyT TombstoneKey = KeyInfoT::getTombstoneKey();

403 for (BucketT &B : buckets()) {

404 if (!KeyInfoT::isEqual(B.getFirst(), EmptyKey) &&

405 !KeyInfoT::isEqual(B.getFirst(), TombstoneKey))

406 B.getSecond().~ValueT();

407 B.getFirst().~KeyT();

408 }

409 }

410

412 static_assert(std::is_base_of_v<DenseMapBase, DerivedT>,

413 "Must pass the derived type to this template!");

414 setNumEntries(0);

415 setNumTombstones(0);

416

417 assert((getNumBuckets() & (getNumBuckets() - 1)) == 0 &&

418 "# initial buckets must be a power of two!");

419 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

420 for (BucketT &B : buckets())

421 ::new (&B.getFirst()) KeyT(EmptyKey);

422 }

423

424

425

427

428 if (NumEntries == 0)

429 return 0;

430

431

433 }

434

435

436

438

439 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

440 const KeyT TombstoneKey = KeyInfoT::getTombstoneKey();

441 for (BucketT &B : Other.buckets()) {

442 if (!KeyInfoT::isEqual(B.getFirst(), EmptyKey) &&

443 !KeyInfoT::isEqual(B.getFirst(), TombstoneKey)) {

444

445 BucketT *DestBucket;

446 bool FoundVal = LookupBucketFor(B.getFirst(), DestBucket);

447 (void)FoundVal;

448 assert(!FoundVal && "Key already in new map?");

449 DestBucket->getFirst() = std::move(B.getFirst());

450 ::new (&DestBucket->getSecond()) ValueT(std::move(B.getSecond()));

451 incrementNumEntries();

452

453

454 B.getSecond().~ValueT();

455 }

456 B.getFirst().~KeyT();

457 }

458 Other.derived().kill();

459 }

460

463 derived().deallocateBuckets();

464 setNumEntries(0);

465 setNumTombstones(0);

466 if (!derived().allocateBuckets(other.getNumBuckets())) {

467

468 return;

469 }

470

471 assert(&other != this);

472 assert(getNumBuckets() == other.getNumBuckets());

473

474 setNumEntries(other.getNumEntries());

475 setNumTombstones(other.getNumTombstones());

476

477 BucketT *Buckets = getBuckets();

478 const BucketT *OtherBuckets = other.getBuckets();

479 const size_t NumBuckets = getNumBuckets();

480 if constexpr (std::is_trivially_copyable_v &&

481 std::is_trivially_copyable_v) {

482 memcpy(reinterpret_cast<void *>(Buckets), OtherBuckets,

483 NumBuckets * sizeof(BucketT));

484 } else {

485 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

486 const KeyT TombstoneKey = KeyInfoT::getTombstoneKey();

487 for (size_t I = 0; I < NumBuckets; ++I) {

488 ::new (&Buckets[I].getFirst()) KeyT(OtherBuckets[I].getFirst());

489 if (!KeyInfoT::isEqual(Buckets[I].getFirst(), EmptyKey) &&

490 !KeyInfoT::isEqual(Buckets[I].getFirst(), TombstoneKey))

491 ::new (&Buckets[I].getSecond()) ValueT(OtherBuckets[I].getSecond());

492 }

493 }

494 }

495

496private:

497 DerivedT &derived() { return *static_cast<DerivedT *>(this); }

498 const DerivedT &derived() const {

499 return *static_cast<const DerivedT *>(this);

500 }

501

502 template <typename KeyArgT, typename... Ts>

503 std::pair<BucketT *, bool> lookupOrInsertIntoBucket(KeyArgT &&Key,

504 Ts &&...Args) {

505 BucketT *TheBucket = nullptr;

506 if (LookupBucketFor(Key, TheBucket))

507 return {TheBucket, false};

508

509

510 TheBucket = findBucketForInsertion(Key, TheBucket);

511 TheBucket->getFirst() = std::forward(Key);

512 ::new (&TheBucket->getSecond()) ValueT(std::forward(Args)...);

513 return {TheBucket, true};

514 }

515

516 template <typename KeyArgT, typename... Ts>

517 std::pair<iterator, bool> try_emplace_impl(KeyArgT &&Key, Ts &&...Args) {

518 auto [Bucket, Inserted] = lookupOrInsertIntoBucket(

519 std::forward(Key), std::forward(Args)...);

520 return {makeIterator(Bucket), Inserted};

521 }

522

523 iterator makeIterator(BucketT *TheBucket) {

525 }

526

527 const_iterator makeConstIterator(const BucketT *TheBucket) const {

529 }

530

531 unsigned getNumEntries() const { return derived().getNumEntries(); }

532

533 void setNumEntries(unsigned Num) { derived().setNumEntries(Num); }

534

535 void incrementNumEntries() { setNumEntries(getNumEntries() + 1); }

536

537 void decrementNumEntries() { setNumEntries(getNumEntries() - 1); }

538

539 unsigned getNumTombstones() const { return derived().getNumTombstones(); }

540

541 void setNumTombstones(unsigned Num) { derived().setNumTombstones(Num); }

542

543 void incrementNumTombstones() { setNumTombstones(getNumTombstones() + 1); }

544

545 void decrementNumTombstones() { setNumTombstones(getNumTombstones() - 1); }

546

547 const BucketT *getBuckets() const { return derived().getBuckets(); }

548

549 BucketT *getBuckets() { return derived().getBuckets(); }

550

551 unsigned getNumBuckets() const { return derived().getNumBuckets(); }

552

553 BucketT *getBucketsEnd() { return getBuckets() + getNumBuckets(); }

554

555 const BucketT *getBucketsEnd() const {

556 return getBuckets() + getNumBuckets();

557 }

558

561 }

562

565 }

566

567 void grow(unsigned MinNumBuckets) {

568 unsigned NumBuckets = DerivedT::roundUpNumBuckets(MinNumBuckets);

570 Tmp.moveFrom(derived());

571 if (derived().maybeMoveFast(std::move(Tmp)))

572 return;

575 }

576

577 template

578 BucketT *findBucketForInsertion(const LookupKeyT &Lookup,

579 BucketT *TheBucket) {

581

582

583

584

585

586

587

588

589

590

591 unsigned NewNumEntries = getNumEntries() + 1;

592 unsigned NumBuckets = getNumBuckets();

593 if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {

594 this->grow(NumBuckets * 2);

595 LookupBucketFor(Lookup, TheBucket);

597 (NewNumEntries + getNumTombstones()) <=

598 NumBuckets / 8)) {

599 this->grow(NumBuckets);

600 LookupBucketFor(Lookup, TheBucket);

601 }

603

604

605

606 incrementNumEntries();

607

608

609 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

610 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))

611 decrementNumTombstones();

612

613 return TheBucket;

614 }

615

616 template

617 const BucketT *doFind(const LookupKeyT &Val) const {

618 const BucketT *BucketsPtr = getBuckets();

619 const unsigned NumBuckets = getNumBuckets();

620 if (NumBuckets == 0)

621 return nullptr;

622

623 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

624 unsigned BucketNo = KeyInfoT::getHashValue(Val) & (NumBuckets - 1);

625 unsigned ProbeAmt = 1;

626 while (true) {

627 const BucketT *Bucket = BucketsPtr + BucketNo;

628 if (LLVM_LIKELY(KeyInfoT::isEqual(Val, Bucket->getFirst())))

629 return Bucket;

630 if (LLVM_LIKELY(KeyInfoT::isEqual(Bucket->getFirst(), EmptyKey)))

631 return nullptr;

632

633

634

635 BucketNo += ProbeAmt++;

636 BucketNo &= NumBuckets - 1;

637 }

638 }

639

640 template BucketT *doFind(const LookupKeyT &Val) {

641 return const_cast<BucketT *>(

642 static_cast<const DenseMapBase *>(this)->doFind(Val));

643 }

644

645

646

647

648

649 template

650 bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {

651 BucketT *BucketsPtr = getBuckets();

652 const unsigned NumBuckets = getNumBuckets();

653

654 if (NumBuckets == 0) {

655 FoundBucket = nullptr;

656 return false;

657 }

658

659

660 BucketT *FoundTombstone = nullptr;

661 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

662 const KeyT TombstoneKey = KeyInfoT::getTombstoneKey();

663 assert(!KeyInfoT::isEqual(Val, EmptyKey) &&

664 !KeyInfoT::isEqual(Val, TombstoneKey) &&

665 "Empty/Tombstone value shouldn't be inserted into map!");

666

667 unsigned BucketNo = KeyInfoT::getHashValue(Val) & (NumBuckets - 1);

668 unsigned ProbeAmt = 1;

669 while (true) {

670 BucketT *ThisBucket = BucketsPtr + BucketNo;

671

672 if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {

673 FoundBucket = ThisBucket;

674 return true;

675 }

676

677

678

679 if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {

680

681

682 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;

683 return false;

684 }

685

686

687

688 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&

689 !FoundTombstone)

690 FoundTombstone = ThisBucket;

691

692

693

694 BucketNo += ProbeAmt++;

695 BucketNo &= (NumBuckets - 1);

696 }

697 }

698

699public:

700

701

702

703

705 return getNumBuckets() * sizeof(BucketT);

706 }

707};

708

709

710

711

712

713

714

715template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,

716 typename BucketT>

717[[nodiscard]] bool

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

721 return false;

722

723 for (auto &KV : LHS) {

724 auto I = RHS.find(KV.first);

725 if (I == RHS.end() || I->second != KV.second)

726 return false;

727 }

728

729 return true;

730}

731

732

733

734

735template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,

736 typename BucketT>

737[[nodiscard]] bool

740 return !(LHS == RHS);

741}

742

743template <typename KeyT, typename ValueT,

744 typename KeyInfoT = DenseMapInfo,

746class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,

747 KeyT, ValueT, KeyInfoT, BucketT> {

748 friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

749

750

751

753

754 BucketT *Buckets;

755 unsigned NumEntries;

756 unsigned NumTombstones;

757 unsigned NumBuckets;

758

759 explicit DenseMap(unsigned NumBuckets, typename BaseT::ExactBucketCount) {

761 }

762

763public:

764

765

766 explicit DenseMap(unsigned NumElementsToReserve = 0)

769

771

772 DenseMap(DenseMap &&other) : DenseMap() { this->swap(other); }

773

774 template

778

779 template

782

783 DenseMap(std::initializer_list<typename BaseT::value_type> Vals)

784 : DenseMap(Vals.begin(), Vals.end()) {}

785

788 deallocateBuckets();

789 }

790

792 if (&other != this)

794 return *this;

795 }

796

799 deallocateBuckets();

801 this->swap(other);

802 return *this;

803 }

804

805private:

811 }

812

813 unsigned getNumEntries() const { return NumEntries; }

814

815 void setNumEntries(unsigned Num) { NumEntries = Num; }

816

817 unsigned getNumTombstones() const { return NumTombstones; }

818

819 void setNumTombstones(unsigned Num) { NumTombstones = Num; }

820

821 BucketT *getBuckets() const { return Buckets; }

822

823 unsigned getNumBuckets() const { return NumBuckets; }

824

825 void deallocateBuckets() {

826 deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));

827 }

828

829 bool allocateBuckets(unsigned Num) {

830 NumBuckets = Num;

831 if (NumBuckets == 0) {

832 Buckets = nullptr;

833 return false;

834 }

835

836 Buckets = static_cast<BucketT *>(

837 allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT)));

838 return true;

839 }

840

841

842 void kill() {

843 deallocateBuckets();

844 Buckets = nullptr;

845 NumBuckets = 0;

846 }

847

848 static unsigned roundUpNumBuckets(unsigned MinNumBuckets) {

849 return std::max(64u,

850 static_cast<unsigned>(NextPowerOf2(MinNumBuckets - 1)));

851 }

852

853 bool maybeMoveFast(DenseMap &&Other) {

855 return true;

856 }

857

858

859

860

861 std::pair<bool, unsigned> planShrinkAndClear() const {

862 unsigned NewNumBuckets = 0;

863 if (NumEntries)

864 NewNumBuckets = std::max(64u, 1u << (Log2_32_Ceil(NumEntries) + 1));

865 if (NewNumBuckets == NumBuckets)

866 return {false, 0};

867 return {true, NewNumBuckets};

868 }

869};

870

871template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,

872 typename KeyInfoT = DenseMapInfo,

874class SmallDenseMap

876 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,

877 ValueT, KeyInfoT, BucketT> {

878 friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

879

880

881

883

885 "InlineBuckets must be a power of 2.");

886

887 unsigned Small : 1;

888 unsigned NumEntries : 31;

889 unsigned NumTombstones;

890

891 struct LargeRep {

892 BucketT *Buckets;

893 unsigned NumBuckets;

896 }

897 };

898

899

900

901 AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;

902

903 SmallDenseMap(unsigned NumBuckets, typename BaseT::ExactBucketCount) {

905 }

906

907public:

912

916

917 SmallDenseMap(SmallDenseMap &&other) : SmallDenseMap() { this->swap(other); }

918

919 template

921 : SmallDenseMap(std::distance(I, E)) {

923 }

924

925 template

928

929 SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals)

930 : SmallDenseMap(Vals.begin(), Vals.end()) {}

931

934 deallocateBuckets();

935 }

936

937 SmallDenseMap &operator=(const SmallDenseMap &other) {

938 if (&other != this)

940 return *this;

941 }

942

943 SmallDenseMap &operator=(SmallDenseMap &&other) {

945 deallocateBuckets();

947 this->swap(other);

948 return *this;

949 }

950

951private:

953 unsigned TmpNumEntries = RHS.NumEntries;

954 RHS.NumEntries = NumEntries;

955 NumEntries = TmpNumEntries;

957

958 const KeyT EmptyKey = KeyInfoT::getEmptyKey();

959 const KeyT TombstoneKey = KeyInfoT::getTombstoneKey();

960 if (Small && RHS.Small) {

961

962

963

964

965 for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {

966 BucketT *LHSB = &getInlineBuckets()[i],

967 *RHSB = &RHS.getInlineBuckets()[i];

968 bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&

969 !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));

970 bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&

971 !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));

972 if (hasLHSValue && hasRHSValue) {

973

975 continue;

976 }

977

978 std::swap(LHSB->getFirst(), RHSB->getFirst());

979 if (hasLHSValue) {

980 ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));

981 LHSB->getSecond().~ValueT();

982 } else if (hasRHSValue) {

983 ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));

984 RHSB->getSecond().~ValueT();

985 }

986 }

987 return;

988 }

989 if (!Small && RHS .Small) {

990 std::swap(*getLargeRep(), *RHS.getLargeRep());

991 return;

992 }

993

994 SmallDenseMap &SmallSide = Small ? *this : RHS;

995 SmallDenseMap &LargeSide = Small ? RHS : *this;

996

997

998 LargeRep TmpRep = std::move(*LargeSide.getLargeRep());

999 LargeSide.getLargeRep()->~LargeRep();

1000 LargeSide.Small = true;

1001

1002

1003

1004

1005 for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {

1006 BucketT *NewB = &LargeSide.getInlineBuckets()[i],

1007 *OldB = &SmallSide.getInlineBuckets()[i];

1008 ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));

1009 OldB->getFirst().~KeyT();

1010 if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&

1011 !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {

1012 ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));

1013 OldB->getSecond().~ValueT();

1014 }

1015 }

1016

1017

1018

1019 SmallSide.Small = false;

1020 new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));

1021 }

1022

1023 unsigned getNumEntries() const { return NumEntries; }

1024

1025 void setNumEntries(unsigned Num) {

1026

1027 assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries");

1028 NumEntries = Num;

1029 }

1030

1031 unsigned getNumTombstones() const { return NumTombstones; }

1032

1033 void setNumTombstones(unsigned Num) { NumTombstones = Num; }

1034

1035 const BucketT *getInlineBuckets() const {

1037

1038

1039

1040 return reinterpret_cast<const BucketT *>(&storage);

1041 }

1042

1043 BucketT *getInlineBuckets() {

1044 return const_cast<BucketT *>(

1045 const_cast<const SmallDenseMap *>(this)->getInlineBuckets());

1046 }

1047

1048 const LargeRep *getLargeRep() const {

1050

1051 return reinterpret_cast<const LargeRep *>(&storage);

1052 }

1053

1054 LargeRep *getLargeRep() {

1055 return const_cast<LargeRep *>(

1056 const_cast<const SmallDenseMap *>(this)->getLargeRep());

1057 }

1058

1059 const BucketT *getBuckets() const {

1060 return Small ? getInlineBuckets() : getLargeRep()->Buckets;

1061 }

1062

1063 BucketT *getBuckets() {

1064 return const_cast<BucketT *>(

1065 const_cast<const SmallDenseMap *>(this)->getBuckets());

1066 }

1067

1068 unsigned getNumBuckets() const {

1069 return Small ? InlineBuckets : getLargeRep()->NumBuckets;

1070 }

1071

1073 BucketT *Begin = getInlineBuckets();

1075 }

1076

1077 void deallocateBuckets() {

1078

1079

1080

1081 if (Small || getLargeRep()->NumBuckets == 0)

1082 return;

1083

1085 sizeof(BucketT) * getLargeRep()->NumBuckets,

1086 alignof(BucketT));

1087 getLargeRep()->~LargeRep();

1088 }

1089

1090 bool allocateBuckets(unsigned Num) {

1091 if (Num <= InlineBuckets) {

1092 Small = true;

1093 } else {

1094 Small = false;

1095 BucketT *NewBuckets = static_cast<BucketT *>(

1096 allocate_buffer(sizeof(BucketT) * Num, alignof(BucketT)));

1097 new (getLargeRep()) LargeRep{NewBuckets, Num};

1098 }

1099 return true;

1100 }

1101

1102

1103 void kill() {

1104 deallocateBuckets();

1105 Small = false;

1106 new (getLargeRep()) LargeRep{nullptr, 0};

1107 }

1108

1109 static unsigned roundUpNumBuckets(unsigned MinNumBuckets) {

1110 if (MinNumBuckets <= InlineBuckets)

1111 return MinNumBuckets;

1112 return std::max(64u,

1113 static_cast<unsigned>(NextPowerOf2(MinNumBuckets - 1)));

1114 }

1115

1116 bool maybeMoveFast(SmallDenseMap &&Other) {

1117 if (Other.Small)

1118 return false;

1119

1120 Small = false;

1121 NumEntries = Other.NumEntries;

1122 NumTombstones = Other.NumTombstones;

1123 *getLargeRep() = std::move(*Other.getLargeRep());

1124 Other.getLargeRep()->NumBuckets = 0;

1125 return true;

1126 }

1127

1128

1129

1130

1131 std::pair<bool, unsigned> planShrinkAndClear() const {

1132 unsigned NewNumBuckets = 0;

1133 if (!this->empty()) {

1135 if (NewNumBuckets > InlineBuckets)

1136 NewNumBuckets = std::max(64u, NewNumBuckets);

1137 }

1138 bool Reuse = Small ? NewNumBuckets <= InlineBuckets

1139 : NewNumBuckets == getLargeRep()->NumBuckets;

1140 if (Reuse)

1141 return {false, 0};

1142 return {true, NewNumBuckets};

1143 }

1144};

1145

1146template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,

1149 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;

1150 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;

1151

1152public:

1154 using value_type = std::conditional_t<IsConst, const Bucket, Bucket>;

1158

1159private:

1160 using BucketItTy =

1161 std::conditional_t<shouldReverseIterate(),

1162 std::reverse_iterator, pointer>;

1163

1164 BucketItTy Ptr = {};

1165 BucketItTy End = {};

1166

1167 DenseMapIterator(BucketItTy Pos, BucketItTy E, const DebugEpochBase &Epoch)

1168 : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {

1169 assert(isHandleInSync() && "invalid construction!");

1170 }

1171

1172public:

1174

1177

1178

1179 if (IsEmpty)

1180 return makeEnd(Buckets, Epoch);

1181 auto R = maybeReverse(Buckets);

1182 DenseMapIterator Iter(R.begin(), R.end(), Epoch);

1183 Iter.AdvancePastEmptyBuckets();

1184 return Iter;

1185 }

1186

1189 auto R = maybeReverse(Buckets);

1190 return DenseMapIterator(R.end(), R.end(), Epoch);

1191 }

1192

1196 auto R = maybeReverse(Buckets);

1198 return DenseMapIterator(BucketItTy(P + Offset), R.end(), Epoch);

1199 }

1200

1201

1202

1203

1204 template <bool IsConstSrc,

1205 typename = std::enable_if_t>

1207 const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)

1209

1212 assert(Ptr != End && "dereferencing end() iterator");

1213 return *Ptr;

1214 }

1216

1217 [[nodiscard]] friend bool operator==(const DenseMapIterator &LHS,

1218 const DenseMapIterator &RHS) {

1219 assert(( LHS .getEpochAddress() || LHS.isHandleInSync()) &&

1220 "handle not in sync!");

1221 assert(( RHS .getEpochAddress() || RHS.isHandleInSync()) &&

1222 "handle not in sync!");

1223 assert(LHS.getEpochAddress() == RHS.getEpochAddress() &&

1224 "comparing incomparable iterators!");

1225 return LHS.Ptr == RHS.Ptr;

1226 }

1227

1228 [[nodiscard]] friend bool operator!=(const DenseMapIterator &LHS,

1229 const DenseMapIterator &RHS) {

1230 return !(LHS == RHS);

1231 }

1232

1233 inline DenseMapIterator &operator++() {

1235 assert(Ptr != End && "incrementing end() iterator");

1236 ++Ptr;

1237 AdvancePastEmptyBuckets();

1238 return *this;

1239 }

1242 DenseMapIterator tmp = *this;

1243 ++*this;

1244 return tmp;

1245 }

1246

1247private:

1248 void AdvancePastEmptyBuckets() {

1250 const KeyT Empty = KeyInfoT::getEmptyKey();

1251 const KeyT Tombstone = KeyInfoT::getTombstoneKey();

1252

1253 while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||

1254 KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))

1255 ++Ptr;

1256 }

1257

1258 static auto maybeReverse(iterator_range Range) {

1259 if constexpr (shouldReverseIterate())

1260 return reverse(Range);

1261 else

1263 }

1264};

1265

1266template <typename KeyT, typename ValueT, typename KeyInfoT>

1267[[nodiscard]] inline size_t

1269 return X.getMemorySize();

1270}

1271

1272}

1273

1274#endif

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

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

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

#define LLVM_UNLIKELY(EXPR)

#define LLVM_LIKELY(EXPR)

This file defines DenseMapInfo traits for DenseMap.

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

This file defines counterparts of C library allocation functions defined in the namespace 'std'.

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

This file contains library features backported from future STL versions.

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

LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty

LocallyHashedType DenseMapInfo< LocallyHashedType >::Tombstone

static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)

bool isHandleInSync() const

ValueT & at(const_arg_type_t< KeyT > Val)

at - Return the entry for the specified key, or abort if no such entry exists.

Definition DenseMap.h:224

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

Definition DenseMap.h:205

iterator find(const_arg_type_t< KeyT > Val)

Definition DenseMap.h:178

void copyFrom(const DerivedT &other)

Definition DenseMap.h:461

unsigned size_type

Definition DenseMap.h:69

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

Definition DenseMap.h:256

std::pair< iterator, bool > insert(std::pair< KeyT, ValueT > &&KV)

Definition DenseMap.h:248

bool erase(const KeyT &Val)

Definition DenseMap.h:330

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

Definition DenseMap.h:74

std::pair< iterator, bool > insert_as(std::pair< KeyT, ValueT > &&KV, const LookupKeyT &Val)

Alternate version of insert() which allows a different, and possibly less expensive,...

Definition DenseMap.h:274

auto keys()

Definition DenseMap.h:92

void moveFrom(DerivedT &Other)

Definition DenseMap.h:437

const_iterator find_as(const LookupKeyT &Val) const

Definition DenseMap.h:197

const_iterator end() const

Definition DenseMap.h:87

iterator find_as(const LookupKeyT &Val)

Alternate version of find() which allows a different, and possibly less expensive,...

Definition DenseMap.h:191

unsigned size() const

Definition DenseMap.h:110

const_iterator find(const_arg_type_t< KeyT > Val) const

Definition DenseMap.h:181

bool empty() const

Definition DenseMap.h:109

std::pair< iterator, bool > emplace_or_assign(const KeyT &Key, Ts &&...Args)

Definition DenseMap.h:315

void insert(InputIt I, InputIt E)

insert - Range insertion of pairs.

Definition DenseMap.h:288

iterator begin()

Definition DenseMap.h:78

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

Definition DenseMap.h:174

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator

Definition DenseMap.h:75

iterator end()

Definition DenseMap.h:81

const ValueT & at(const_arg_type_t< KeyT > Val) const

at - Return the entry for the specified key, or abort if no such entry exists.

Definition DenseMap.h:232

bool isPointerIntoBucketsArray(const void *Ptr) const

isPointerIntoBucketsArray - Return true if the specified pointer points somewhere into the DenseMap's...

Definition DenseMap.h:360

ValueT mapped_type

Definition DenseMap.h:71

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

Definition DenseMap.h:169

std::pair< iterator, bool > try_emplace(const KeyT &Key, Ts &&...Args)

Definition DenseMap.h:264

KeyT key_type

Definition DenseMap.h:70

const_iterator begin() const

Definition DenseMap.h:84

std::pair< iterator, bool > emplace_or_assign(KeyT &&Key, Ts &&...Args)

Definition DenseMap.h:323

void insert_range(Range &&R)

Inserts range of 'std::pair<KeyT, ValueT>' values into the map.

Definition DenseMap.h:294

const void * getPointerIntoBucketsArray() const

getPointerIntoBucketsArray() - Return an opaque pointer into the buckets array.

Definition DenseMap.h:367

std::pair< iterator, bool > insert_or_assign(KeyT &&Key, V &&Val)

Definition DenseMap.h:307

ValueT lookup_or(const_arg_type_t< KeyT > Val, U &&Default) const

Definition DenseMap.h:215

unsigned getMinBucketToReserveForEntries(unsigned NumEntries)

Returns the number of buckets to allocate to ensure that the DenseMap can accommodate NumEntries with...

Definition DenseMap.h:426

void swap(DerivedT &RHS)

Definition DenseMap.h:371

void initEmpty()

Definition DenseMap.h:411

ValueT & operator[](const KeyT &Key)

Definition DenseMap.h:349

BucketT value_type

Definition DenseMap.h:72

auto keys() const

Definition DenseMap.h:101

void initWithExactBucketCount(unsigned NewNumBuckets)

Definition DenseMap.h:382

void destroyAll()

Definition DenseMap.h:391

void shrink_and_clear()

Definition DenseMap.h:157

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Definition DenseMap.h:241

void erase(iterator I)

Definition DenseMap.h:341

void clear()

Definition DenseMap.h:121

std::pair< iterator, bool > insert_or_assign(const KeyT &Key, V &&Val)

Definition DenseMap.h:299

void reserve(size_type NumEntries)

Grow the densemap so that it can contain at least NumEntries items before resizing again.

Definition DenseMap.h:114

auto values()

Definition DenseMap.h:97

ValueT & operator[](KeyT &&Key)

Definition DenseMap.h:353

auto values() const

Definition DenseMap.h:105

size_t getMemorySize() const

Return the approximate size (in bytes) of the actual map.

Definition DenseMap.h:704

Definition DenseMap.h:1148

std::conditional_t< IsConst, const BucketT, BucketT > value_type

Definition DenseMap.h:1154

static DenseMapIterator makeIterator(pointer P, iterator_range< pointer > Buckets, const DebugEpochBase &Epoch)

Definition DenseMap.h:1193

friend bool operator!=(const DenseMapIterator &LHS, const DenseMapIterator &RHS)

Definition DenseMap.h:1228

value_type * pointer

Definition DenseMap.h:1155

DenseMapIterator & operator++()

Definition DenseMap.h:1233

pointer operator->() const

Definition DenseMap.h:1215

reference operator*() const

Definition DenseMap.h:1210

DenseMapIterator()=default

static DenseMapIterator makeBegin(iterator_range< pointer > Buckets, bool IsEmpty, const DebugEpochBase &Epoch)

Definition DenseMap.h:1175

DenseMapIterator operator++(int)

Definition DenseMap.h:1240

DenseMapIterator(const DenseMapIterator< KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc > &I)

Definition DenseMap.h:1206

ptrdiff_t difference_type

Definition DenseMap.h:1153

friend bool operator==(const DenseMapIterator &LHS, const DenseMapIterator &RHS)

Definition DenseMap.h:1217

static DenseMapIterator makeEnd(iterator_range< pointer > Buckets, const DebugEpochBase &Epoch)

Definition DenseMap.h:1187

std::forward_iterator_tag iterator_category

Definition DenseMap.h:1157

value_type & reference

Definition DenseMap.h:1156

Definition DenseMap.h:747

~DenseMap()

Definition DenseMap.h:786

DenseMap(std::initializer_list< typename BaseT::value_type > Vals)

Definition DenseMap.h:783

DenseMap(unsigned NumElementsToReserve=0)

Create a DenseMap with an optional NumElementsToReserve to guarantee that this number of elements can...

Definition DenseMap.h:766

DenseMap & operator=(DenseMap &&other)

Definition DenseMap.h:797

DenseMap(llvm::from_range_t, const RangeT &Range)

Definition DenseMap.h:780

DenseMap(const DenseMap &other)

Definition DenseMap.h:770

DenseMap(const InputIt &I, const InputIt &E)

Definition DenseMap.h:775

DenseMap(DenseMap &&other)

Definition DenseMap.h:772

DenseMap & operator=(const DenseMap &other)

Definition DenseMap.h:791

Definition DenseMap.h:877

SmallDenseMap(const InputIt &I, const InputIt &E)

Definition DenseMap.h:920

SmallDenseMap & operator=(SmallDenseMap &&other)

Definition DenseMap.h:943

SmallDenseMap & operator=(const SmallDenseMap &other)

Definition DenseMap.h:937

SmallDenseMap(unsigned NumElementsToReserve=0)

Definition DenseMap.h:908

SmallDenseMap(std::initializer_list< typename BaseT::value_type > Vals)

Definition DenseMap.h:929

SmallDenseMap(SmallDenseMap &&other)

Definition DenseMap.h:917

SmallDenseMap(const SmallDenseMap &other)

Definition DenseMap.h:913

~SmallDenseMap()

Definition DenseMap.h:932

SmallDenseMap(llvm::from_range_t, const RangeT &Range)

Definition DenseMap.h:926

A range adaptor for a pair of iterators.

constexpr char IsConst[]

Key for Kernel::Arg::Metadata::mIsConst.

A self-contained host- and target-independent arbitrary-precision floating-point software implementat...

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 isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)

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

BitVector::size_type capacity_in_bytes(const BitVector &X)

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 bool isPowerOf2_64(uint64_t Value)

Return true if the argument is a power of two > 0 (64 bit edition.)

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

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

auto map_range(ContainerTy &&C, FuncTy F)

LLVM_ABI LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * allocate_buffer(size_t Size, size_t Alignment)

Allocate a buffer of memory with the given size and alignment.

LLVM_ABI void deallocate_buffer(void *Ptr, size_t Size, size_t Alignment)

Deallocate a buffer of memory with the given size and alignment.

constexpr bool shouldReverseIterate()

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >

OutputIt move(R &&Range, OutputIt Out)

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

@ Default

The result values are uniform if and only if all operands are uniform.

constexpr uint64_t NextPowerOf2(uint64_t A)

Returns the next power of two (in 64-bits) that is strictly greater than A.

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.

Definition DenseMap.h:380

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

const ValueT & getSecond() const

Definition DenseMap.h:51

KeyT & getFirst()

Definition DenseMap.h:48

const KeyT & getFirst() const

Definition DenseMap.h:49

ValueT & getSecond()

Definition DenseMap.h:50