Movatterモバイル変換

Go to the documentation of this file.

1//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8///

9/// \file

10/// This file defines the DenseMap class.

11///

12//===----------------------------------------------------------------------===//

14#ifndef LLVM_ADT_DENSEMAP_H

15#define LLVM_ADT_DENSEMAP_H

17#include "llvm/ADT/DenseMapInfo.h"

18#include "llvm/ADT/EpochTracker.h"

19#include "llvm/Support/AlignOf.h"

20#include "llvm/Support/Compiler.h"

21#include "llvm/Support/MathExtras.h"

22#include "llvm/Support/MemAlloc.h"

23#include "llvm/Support/ReverseIteration.h"

24#include "llvm/Support/type_traits.h"

25#include <algorithm>

26#include <cassert>

27#include <cstddef>

28#include <cstring>

29#include <initializer_list>

30#include <iterator>

31#include <new>

32#include <type_traits>

33#include <utility>

35namespacellvm {

37namespacedetail {

39// We extend a pair to allow users to override the bucket type with their own

40// implementation without requiring two members.

41template <typename KeyT,typename ValueT>

42structDenseMapPair :public std::pair<KeyT, ValueT> {

43usingstd::pair<KeyT,ValueT>::pair;

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

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

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

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

49};

51}// end namespace detail

53template <typenameKeyT,typenameValueT,

54typename KeyInfoT = DenseMapInfo<KeyT>,

55typename Bucket =llvm::detail::DenseMapPair<KeyT, ValueT>,

56bool IsConst =false>

57classDenseMapIterator;

59template <typename DerivedT,typenameKeyT,typenameValueT,typename KeyInfoT,

60typename BucketT>

61classDenseMapBase :publicDebugEpochBase {

62template <typename T>

63usingconst_arg_type_t =typenameconst_pointer_or_const_ref<T>::type;

65public:

66usingsize_type =unsigned;

67usingkey_type =KeyT;

68usingmapped_type =ValueT;

69usingvalue_type = BucketT;

71usingiterator =DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>;

72usingconst_iterator =

73DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>;

75inlineiterator begin() {

76// When the map is empty, avoid the overhead of advancing/retreating past

77// empty buckets.

78if (empty())

79returnend();

80if (shouldReverseIterate<KeyT>())

81return makeIterator(getBucketsEnd() - 1, getBuckets(), *this);

82return makeIterator(getBuckets(), getBucketsEnd(), *this);

83 }

84inlineiterator end() {

85return makeIterator(getBucketsEnd(), getBucketsEnd(), *this,true);

86 }

87inlineconst_iterator begin() const{

88if (empty())

89returnend();

90if (shouldReverseIterate<KeyT>())

91return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this);

92return makeConstIterator(getBuckets(), getBucketsEnd(), *this);

93 }

94inlineconst_iterator end() const{

95return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this,true);

96 }

98 [[nodiscard]]boolempty() const{return getNumEntries() == 0; }

99unsignedsize() const{return getNumEntries(); }

100

101 /// Grow the densemap so that it can contain at least \p NumEntries items

102 /// before resizing again.

103voidreserve(size_type NumEntries) {

104auto NumBuckets =getMinBucketToReserveForEntries(NumEntries);

105incrementEpoch();

106if (NumBuckets > getNumBuckets())

107 grow(NumBuckets);

108 }

109

110voidclear() {

111incrementEpoch();

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

113return;

114

115// If the capacity of the array is huge, and the # elements used is small,

116// shrink the array.

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

118 shrink_and_clear();

119return;

120 }

121

122constKeyT EmptyKey =getEmptyKey();

123ifconstexpr (std::is_trivially_destructible_v<ValueT>) {

124// Use a simpler loop when values don't need destruction.

125for (BucketT *P = getBuckets(), *E = getBucketsEnd();P !=E; ++P)

126P->getFirst() = EmptyKey;

127 }else {

128constKeyT TombstoneKey =getTombstoneKey();

129unsigned NumEntries = getNumEntries();

130for (BucketT *P = getBuckets(), *E = getBucketsEnd();P !=E; ++P) {

131if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {

132if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {

133P->getSecond().~ValueT();

134 --NumEntries;

135 }

136P->getFirst() = EmptyKey;

137 }

138 }

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

140 (void)NumEntries;

141 }

142 setNumEntries(0);

143 setNumTombstones(0);

144 }

145

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

147boolcontains(const_arg_type_t<KeyT> Val) const{

148return doFind(Val) !=nullptr;

149 }

150

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

152size_type count(const_arg_type_t<KeyT> Val) const{

153returncontains(Val) ? 1 : 0;

154 }

155

156iterator find(const_arg_type_t<KeyT> Val) {

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

158return makeIterator(

159 Bucket, shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),

160 *this,true);

161returnend();

162 }

163const_iterator find(const_arg_type_t<KeyT> Val) const{

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

165return makeConstIterator(

166 Bucket, shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),

167 *this,true);

168returnend();

169 }

170

171 /// Alternate version of find() which allows a different, and possibly

172 /// less expensive, key type.

173 /// The DenseMapInfo is responsible for supplying methods

174 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key

175 /// type used.

176template <class LookupKeyT>iterator find_as(const LookupKeyT &Val) {

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

178return makeIterator(

179 Bucket, shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),

180 *this,true);

181returnend();

182 }

183template <class LookupKeyT>

184const_iterator find_as(const LookupKeyT &Val) const{

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

186return makeConstIterator(

187 Bucket, shouldReverseIterate<KeyT>() ? getBuckets() : getBucketsEnd(),

188 *this,true);

189returnend();

190 }

191

192 /// lookup - Return the entry for the specified key, or a default

193 /// constructed value if no such entry exists.

194ValueT lookup(const_arg_type_t<KeyT> Val) const{

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

196return Bucket->getSecond();

197returnValueT();

198 }

199

200 /// at - Return the entry for the specified key, or abort if no such

201 /// entry exists.

202constValueT &at(const_arg_type_t<KeyT> Val) const{

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

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

205return Iter->second;

206 }

207

208// Inserts key,value pair into the map if the key isn't already in the map.

209// If the key is already in the map, it returns false and doesn't update the

210// value.

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

212returntry_emplace(KV.first, KV.second);

213 }

214

215// Inserts key,value pair into the map if the key isn't already in the map.

216// If the key is already in the map, it returns false and doesn't update the

217// value.

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

219returntry_emplace(std::move(KV.first), std::move(KV.second));

220 }

221

222// Inserts key,value pair into the map if the key isn't already in the map.

223// The value is constructed in-place if the key is not in the map, otherwise

224// it is not moved.

225template <typename... Ts>

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

227 BucketT *TheBucket;

228if (LookupBucketFor(Key, TheBucket))

229return std::make_pair(makeIterator(TheBucket,

230 shouldReverseIterate<KeyT>()

231 ? getBuckets()

232 : getBucketsEnd(),

233 *this,true),

234false);// Already in map.

235

236// Otherwise, insert the new element.

237 TheBucket =

238 InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);

239return std::make_pair(makeIterator(TheBucket,

240 shouldReverseIterate<KeyT>()

241 ? getBuckets()

242 : getBucketsEnd(),

243 *this,true),

244true);

245 }

246

247// Inserts key,value pair into the map if the key isn't already in the map.

248// The value is constructed in-place if the key is not in the map, otherwise

249// it is not moved.

250template <typename... Ts>

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

252 BucketT *TheBucket;

253if (LookupBucketFor(Key, TheBucket))

254return std::make_pair(makeIterator(TheBucket,

255 shouldReverseIterate<KeyT>()

256 ? getBuckets()

257 : getBucketsEnd(),

258 *this,true),

259false);// Already in map.

260

261// Otherwise, insert the new element.

262 TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);

263return std::make_pair(makeIterator(TheBucket,

264 shouldReverseIterate<KeyT>()

265 ? getBuckets()

266 : getBucketsEnd(),

267 *this,true),

268true);

269 }

270

271 /// Alternate version of insert() which allows a different, and possibly

272 /// less expensive, key type.

273 /// The DenseMapInfo is responsible for supplying methods

274 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key

275 /// type used.

276template <typename LookupKeyT>

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

278const LookupKeyT &Val) {

279 BucketT *TheBucket;

280if (LookupBucketFor(Val, TheBucket))

281return std::make_pair(makeIterator(TheBucket,

282 shouldReverseIterate<KeyT>()

283 ? getBuckets()

284 : getBucketsEnd(),

285 *this,true),

286false);// Already in map.

287

288// Otherwise, insert the new element.

289 TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),

290 std::move(KV.second), Val);

291return std::make_pair(makeIterator(TheBucket,

292 shouldReverseIterate<KeyT>()

293 ? getBuckets()

294 : getBucketsEnd(),

295 *this,true),

296true);

297 }

298

299 /// insert - Range insertion of pairs.

300template <typename InputIt>voidinsert(InputItI, InputItE) {

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

302insert(*I);

303 }

304

305template <typename V>

306 std::pair<iterator, bool>insert_or_assign(constKeyT &Key, V &&Val) {

307auto Ret =try_emplace(Key, std::forward<V>(Val));

308if (!Ret.second)

309 Ret.first->second = std::forward<V>(Val);

310return Ret;

311 }

312

313template <typename V>

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

315auto Ret =try_emplace(std::move(Key), std::forward<V>(Val));

316if (!Ret.second)

317 Ret.first->second = std::forward<V>(Val);

318return Ret;

319 }

320

321boolerase(constKeyT &Val) {

322 BucketT *TheBucket = doFind(Val);

323if (!TheBucket)

324returnfalse;// not in map.

325

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

327 TheBucket->getFirst() =getTombstoneKey();

328 decrementNumEntries();

329 incrementNumTombstones();

330returntrue;

331 }

332voiderase(iterator I) {

333 BucketT *TheBucket = &*I;

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

335 TheBucket->getFirst() =getTombstoneKey();

336 decrementNumEntries();

337 incrementNumTombstones();

338 }

339

340ValueT &operator[](constKeyT &Key) {

341 BucketT *TheBucket;

342if (LookupBucketFor(Key, TheBucket))

343return TheBucket->second;

344

345return InsertIntoBucket(TheBucket, Key)->second;

346 }

347

348ValueT &operator[](KeyT &&Key) {

349 BucketT *TheBucket;

350if (LookupBucketFor(Key, TheBucket))

351return TheBucket->second;

352

353return InsertIntoBucket(TheBucket, std::move(Key))->second;

354 }

355

356 /// isPointerIntoBucketsArray - Return true if the specified pointer points

357 /// somewhere into the DenseMap's array of buckets (i.e. either to a key or

358 /// value in the DenseMap).

359boolisPointerIntoBucketsArray(constvoid *Ptr) const{

360returnPtr >= getBuckets() &&Ptr < getBucketsEnd();

361 }

362

363 /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets

364 /// array. In conjunction with the previous method, this can be used to

365 /// determine whether an insertion caused the DenseMap to reallocate.

366constvoid *getPointerIntoBucketsArray() const{return getBuckets(); }

367

368protected:

369DenseMapBase() =default;

370

371voiddestroyAll() {

372if (getNumBuckets() == 0)// Nothing to do.

373return;

374

375constKeyT EmptyKey =getEmptyKey(), TombstoneKey =getTombstoneKey();

376for (BucketT *P = getBuckets(), *E = getBucketsEnd();P !=E; ++P) {

377if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&

378 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))

379P->getSecond().~ValueT();

380P->getFirst().~KeyT();

381 }

382 }

383

384voidinitEmpty() {

385 setNumEntries(0);

386 setNumTombstones(0);

387

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

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

390constKeyT EmptyKey =getEmptyKey();

391for (BucketT *B = getBuckets(), *E = getBucketsEnd();B !=E; ++B)

392 ::new (&B->getFirst())KeyT(EmptyKey);

393 }

394

395 /// Returns the number of buckets to allocate to ensure that the DenseMap can

396 /// accommodate \p NumEntries without need to grow().

397unsignedgetMinBucketToReserveForEntries(unsigned NumEntries) {

398// Ensure that "NumEntries * 4 < NumBuckets * 3"

399if (NumEntries == 0)

400return 0;

401// +1 is required because of the strict equality.

402// For example if NumEntries is 48, we need to return 401.

403returnNextPowerOf2(NumEntries * 4 / 3 + 1);

404 }

405

406voidmoveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {

407initEmpty();

408

409// Insert all the old elements.

410constKeyT EmptyKey =getEmptyKey();

411constKeyT TombstoneKey =getTombstoneKey();

412for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd;B !=E; ++B) {

413if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&

414 !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {

415// Insert the key/value into the new table.

416 BucketT *DestBucket;

417bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);

418 (void)FoundVal;// silence warning.

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

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

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

422 incrementNumEntries();

423

424// Free the value.

425B->getSecond().~ValueT();

426 }

427B->getFirst().~KeyT();

428 }

429 }

430

431template <typename OtherBaseT>

432voidcopyFrom(

433constDenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {

434assert(&other !=this);

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

436

437 setNumEntries(other.getNumEntries());

438 setNumTombstones(other.getNumTombstones());

439

440 BucketT *Buckets = getBuckets();

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

442constsize_t NumBuckets = getNumBuckets();

443ifconstexpr (std::is_trivially_copyable_v<KeyT> &&

444 std::is_trivially_copyable_v<ValueT>) {

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

446 NumBuckets *sizeof(BucketT));

447 }else {

448constKeyT EmptyKey =getEmptyKey();

449constKeyT TombstoneKey =getTombstoneKey();

450for (size_tI = 0;I < NumBuckets; ++I) {

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

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

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

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

455 }

456 }

457 }

458

459staticunsignedgetHashValue(constKeyT &Val) {

460return KeyInfoT::getHashValue(Val);

461 }

462

463template <typename LookupKeyT>

464staticunsignedgetHashValue(const LookupKeyT &Val) {

465return KeyInfoT::getHashValue(Val);

466 }

467

468staticconstKeyT getEmptyKey() {

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

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

471return KeyInfoT::getEmptyKey();

472 }

473

474staticconstKeyT getTombstoneKey() {return KeyInfoT::getTombstoneKey(); }

475

476private:

477iterator makeIterator(BucketT *P, BucketT *E,DebugEpochBase &Epoch,

478bool NoAdvance =false) {

479if (shouldReverseIterate<KeyT>()) {

480 BucketT *B =P == getBucketsEnd() ? getBuckets() :P + 1;

481returniterator(B,E, Epoch, NoAdvance);

482 }

483returniterator(P,E, Epoch, NoAdvance);

484 }

485

486const_iterator makeConstIterator(const BucketT *P,const BucketT *E,

487const DebugEpochBase &Epoch,

488constbool NoAdvance =false) const{

489if (shouldReverseIterate<KeyT>()) {

490const BucketT *B =P == getBucketsEnd() ? getBuckets() :P + 1;

491returnconst_iterator(B,E, Epoch, NoAdvance);

492 }

493returnconst_iterator(P,E, Epoch, NoAdvance);

494 }

495

496unsigned getNumEntries() const{

497returnstatic_cast<constDerivedT *>(this)->getNumEntries();

498 }

499

500void setNumEntries(unsigned Num) {

501static_cast<DerivedT *>(this)->setNumEntries(Num);

502 }

503

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

505

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

507

508unsigned getNumTombstones() const{

509returnstatic_cast<constDerivedT *>(this)->getNumTombstones();

510 }

511

512void setNumTombstones(unsigned Num) {

513static_cast<DerivedT *>(this)->setNumTombstones(Num);

514 }

515

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

517

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

519

520const BucketT *getBuckets() const{

521returnstatic_cast<constDerivedT *>(this)->getBuckets();

522 }

523

524 BucketT *getBuckets() {returnstatic_cast<DerivedT *>(this)->getBuckets(); }

525

526unsigned getNumBuckets() const{

527returnstatic_cast<constDerivedT *>(this)->getNumBuckets();

528 }

529

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

531

532const BucketT *getBucketsEnd() const{

533return getBuckets() + getNumBuckets();

534 }

535

536void grow(unsigned AtLeast) {static_cast<DerivedT *>(this)->grow(AtLeast); }

537

538void shrink_and_clear() {static_cast<DerivedT *>(this)->shrink_and_clear(); }

539

540template <typename KeyArg,typename... ValueArgs>

541 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,

542 ValueArgs &&...Values) {

543 TheBucket = InsertIntoBucketImpl(Key, TheBucket);

544

545 TheBucket->getFirst() = std::forward<KeyArg>(Key);

546 ::new (&TheBucket->getSecond())ValueT(std::forward<ValueArgs>(Values)...);

547 return TheBucket;

548 }

549

550 template <typename LookupKeyT>

551 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket,KeyT &&Key,

552ValueT &&Value, LookupKeyT &Lookup) {

553 TheBucket = InsertIntoBucketImpl(Lookup, TheBucket);

554

555 TheBucket->getFirst() = std::move(Key);

556 ::new (&TheBucket->getSecond())ValueT(std::move(Value));

557 return TheBucket;

558 }

559

560 template <typename LookupKeyT>

561 BucketT *InsertIntoBucketImpl(const LookupKeyT &Lookup, BucketT *TheBucket) {

562incrementEpoch();

563

564// If the load of the hash table is more than 3/4, or if fewer than 1/8 of

565// the buckets are empty (meaning that many are filled with tombstones),

566// grow the table.

567//

568// The later case is tricky. For example, if we had one empty bucket with

569// tons of tombstones, failing lookups (e.g. for insertion) would have to

570// probe almost the entire table until it found the empty bucket. If the

571// table completely filled with tombstones, no lookup would ever succeed,

572// causing infinite loops in lookup.

573unsigned NewNumEntries = getNumEntries() + 1;

574unsigned NumBuckets = getNumBuckets();

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

576 this->grow(NumBuckets * 2);

577 LookupBucketFor(Lookup, TheBucket);

578 NumBuckets = getNumBuckets();

579 }elseif (LLVM_UNLIKELY(NumBuckets -

580 (NewNumEntries + getNumTombstones()) <=

581 NumBuckets / 8)) {

582 this->grow(NumBuckets);

583 LookupBucketFor(Lookup, TheBucket);

584 }

585assert(TheBucket);

586

587// Only update the state after we've grown our bucket space appropriately

588// so that when growing buckets we have self-consistent entry count.

589 incrementNumEntries();

590

591// If we are writing over a tombstone, remember this.

592constKeyT EmptyKey =getEmptyKey();

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

594 decrementNumTombstones();

595

596return TheBucket;

597 }

598

599template <typename LookupKeyT> BucketT *doFind(const LookupKeyT &Val) {

600 BucketT *BucketsPtr = getBuckets();

601constunsigned NumBuckets = getNumBuckets();

602if (NumBuckets == 0)

603returnnullptr;

604

605constKeyT EmptyKey =getEmptyKey();

606unsigned BucketNo =getHashValue(Val) & (NumBuckets - 1);

607unsigned ProbeAmt = 1;

608while (true) {

609 BucketT *Bucket = BucketsPtr + BucketNo;

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

611return Bucket;

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

613returnnullptr;

614

615// Otherwise, it's a hash collision or a tombstone, continue quadratic

616// probing.

617 BucketNo += ProbeAmt++;

618 BucketNo &= NumBuckets - 1;

619 }

620 }

621

622template <typename LookupKeyT>

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

624returnconst_cast<DenseMapBase *>(this)->doFind(Val);// NOLINT

625 }

626

627 /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in

628 /// FoundBucket. If the bucket contains the key and a value, this returns

629 /// true, otherwise it returns a bucket with an empty marker or tombstone and

630 /// returns false.

631template <typename LookupKeyT>

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

633 BucketT *BucketsPtr = getBuckets();

634constunsigned NumBuckets = getNumBuckets();

635

636if (NumBuckets == 0) {

637 FoundBucket =nullptr;

638returnfalse;

639 }

640

641// FoundTombstone - Keep track of whether we find a tombstone while probing.

642 BucketT *FoundTombstone =nullptr;

643constKeyT EmptyKey =getEmptyKey();

644constKeyT TombstoneKey =getTombstoneKey();

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

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

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

648

649unsigned BucketNo =getHashValue(Val) & (NumBuckets - 1);

650unsigned ProbeAmt = 1;

651while (true) {

652 BucketT *ThisBucket = BucketsPtr + BucketNo;

653// Found Val's bucket? If so, return it.

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

655 FoundBucket = ThisBucket;

656returntrue;

657 }

658

659// If we found an empty bucket, the key doesn't exist in the set.

660// Insert it and return the default value.

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

662// If we've already seen a tombstone while probing, fill it in instead

663// of the empty bucket we eventually probed to.

664 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;

665returnfalse;

666 }

667

668// If this is a tombstone, remember it. If Val ends up not in the map, we

669// prefer to return it than something that would require more probing.

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

671 !FoundTombstone)

672 FoundTombstone = ThisBucket;// Remember the first tombstone found.

673

674// Otherwise, it's a hash collision or a tombstone, continue quadratic

675// probing.

676 BucketNo += ProbeAmt++;

677 BucketNo &= (NumBuckets - 1);

678 }

679 }

680

681public:

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

683 /// This is just the raw memory used by DenseMap.

684 /// If entries are pointers to objects, the size of the referenced objects

685 /// are not included.

686size_tgetMemorySize() const{return getNumBuckets() *sizeof(BucketT); }

687};

688

689/// Equality comparison for DenseMap.

690///

691/// Iterates over elements of LHS confirming that each (key, value) pair in LHS

692/// is also in RHS, and that no additional pairs are in RHS.

693/// Equivalent to N calls to RHS.find and N value comparisons. Amortized

694/// complexity is linear, worst case is O(N^2) (if every hash collides).

695template <typename DerivedT,typenameKeyT,typenameValueT,typename KeyInfoT,

696typename BucketT>

697booloperator==(

698constDenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,

699constDenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {

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

701returnfalse;

702

703for (auto &KV :LHS) {

704autoI =RHS.find(KV.first);

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

706returnfalse;

707 }

708

709returntrue;

710}

711

712/// Inequality comparison for DenseMap.

713///

714/// Equivalent to !(LHS == RHS). See operator== for performance notes.

715template <typename DerivedT,typenameKeyT,typenameValueT,typename KeyInfoT,

716typename BucketT>

717booloperator!=(

718constDenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,

719constDenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {

720return !(LHS ==RHS);

721}

722

723template <typenameKeyT,typenameValueT,

724typename KeyInfoT = DenseMapInfo<KeyT>,

725typename BucketT =llvm::detail::DenseMapPair<KeyT, ValueT>>

726classDenseMap :publicDenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,

727 KeyT, ValueT, KeyInfoT, BucketT> {

728friendclassDenseMapBase<DenseMap,KeyT,ValueT, KeyInfoT, BucketT>;

729

730// Lift some types from the dependent base class into this class for

731// simplicity of referring to them.

732usingBaseT =DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

733

734 BucketT *Buckets;

735unsigned NumEntries;

736unsigned NumTombstones;

737unsigned NumBuckets;

738

739public:

740 /// Create a DenseMap with an optional \p InitialReserve that guarantee that

741 /// this number of elements can be inserted in the map without grow()

742explicitDenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }

743

744DenseMap(constDenseMap &other) :BaseT() {

745 init(0);

746 copyFrom(other);

747 }

748

749DenseMap(DenseMap &&other) :BaseT() {

750 init(0);

751 swap(other);

752 }

753

754template <typename InputIt>DenseMap(const InputIt &I,const InputIt &E) {

755 init(std::distance(I,E));

756 this->insert(I,E);

757 }

758

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

760 init(Vals.size());

761 this->insert(Vals.begin(), Vals.end());

762 }

763

764~DenseMap() {

765 this->destroyAll();

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

767 }

768

769voidswap(DenseMap &RHS) {

770 this->incrementEpoch();

771RHS.incrementEpoch();

772std::swap(Buckets,RHS.Buckets);

773std::swap(NumEntries,RHS.NumEntries);

774std::swap(NumTombstones,RHS.NumTombstones);

775std::swap(NumBuckets,RHS.NumBuckets);

776 }

777

778DenseMap &operator=(constDenseMap &other) {

779if (&other !=this)

780 copyFrom(other);

781return *this;

782 }

783

784DenseMap &operator=(DenseMap &&other) {

785 this->destroyAll();

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

787 init(0);

788 swap(other);

789return *this;

790 }

791

792voidcopyFrom(constDenseMap &other) {

793 this->destroyAll();

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

795if (allocateBuckets(other.NumBuckets)) {

796 this->BaseT::copyFrom(other);

797 }else {

798 NumEntries = 0;

799 NumTombstones = 0;

800 }

801 }

802

803voidinit(unsigned InitNumEntries) {

804auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);

805if (allocateBuckets(InitBuckets)) {

806 this->BaseT::initEmpty();

807 }else {

808 NumEntries = 0;

809 NumTombstones = 0;

810 }

811 }

812

813voidgrow(unsigned AtLeast) {

814unsigned OldNumBuckets = NumBuckets;

815 BucketT *OldBuckets = Buckets;

816

817 allocateBuckets(std::max<unsigned>(

818 64,static_cast<unsigned>(NextPowerOf2(AtLeast - 1))));

819assert(Buckets);

820if (!OldBuckets) {

821 this->BaseT::initEmpty();

822return;

823 }

824

825 this->moveFromOldBuckets(OldBuckets, OldBuckets + OldNumBuckets);

826

827// Free the old table.

828deallocate_buffer(OldBuckets,sizeof(BucketT) * OldNumBuckets,

829alignof(BucketT));

830 }

831

832voidshrink_and_clear() {

833unsigned OldNumBuckets = NumBuckets;

834unsigned OldNumEntries = NumEntries;

835 this->destroyAll();

836

837// Reduce the number of buckets.

838unsigned NewNumBuckets = 0;

839if (OldNumEntries)

840 NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));

841if (NewNumBuckets == NumBuckets) {

842 this->BaseT::initEmpty();

843return;

844 }

845

846deallocate_buffer(Buckets,sizeof(BucketT) * OldNumBuckets,

847alignof(BucketT));

848 init(NewNumBuckets);

849 }

850

851private:

852unsigned getNumEntries() const{return NumEntries; }

853

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

855

856unsigned getNumTombstones() const{return NumTombstones; }

857

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

859

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

861

862unsigned getNumBuckets() const{return NumBuckets; }

863

864bool allocateBuckets(unsigned Num) {

865 NumBuckets = Num;

866if (NumBuckets == 0) {

867 Buckets =nullptr;

868returnfalse;

869 }

870

871 Buckets =static_cast<BucketT *>(

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

873returntrue;

874 }

875};

876

877template <typenameKeyT,typenameValueT,unsigned InlineBuckets = 4,

878typename KeyInfoT = DenseMapInfo<KeyT>,

879typename BucketT =llvm::detail::DenseMapPair<KeyT, ValueT>>

880classSmallDenseMap

881 :publicDenseMapBase<

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

883 ValueT, KeyInfoT, BucketT> {

884friendclassDenseMapBase<SmallDenseMap,KeyT,ValueT, KeyInfoT, BucketT>;

885

886// Lift some types from the dependent base class into this class for

887// simplicity of referring to them.

888usingBaseT =DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

889

890static_assert(isPowerOf2_64(InlineBuckets),

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

892

893unsigned Small : 1;

894unsigned NumEntries : 31;

895unsigned NumTombstones;

896

897structLargeRep {

898 BucketT *Buckets;

899unsigned NumBuckets;

900 };

901

902 /// A "union" of an inline bucket array and the struct representing

903 /// a large bucket. This union will be discriminated by the 'Small' bit.

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

905

906public:

907explicitSmallDenseMap(unsigned NumInitBuckets = 0) {

908if (NumInitBuckets > InlineBuckets)

909 NumInitBuckets =llvm::bit_ceil(NumInitBuckets);

910 init(NumInitBuckets);

911 }

912

913SmallDenseMap(constSmallDenseMap &other) :BaseT() {

914 init(0);

915 copyFrom(other);

916 }

917

918SmallDenseMap(SmallDenseMap &&other) :BaseT() {

919 init(0);

920 swap(other);

921 }

922

923template <typename InputIt>

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

925 init(NextPowerOf2(std::distance(I,E)));

926 this->insert(I,E);

927 }

928

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

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

931

932~SmallDenseMap() {

933 this->destroyAll();

934 deallocateBuckets();

935 }

936

937voidswap(SmallDenseMap &RHS) {

938unsigned TmpNumEntries =RHS.NumEntries;

939RHS.NumEntries = NumEntries;

940 NumEntries = TmpNumEntries;

941std::swap(NumTombstones,RHS.NumTombstones);

942

943constKeyT EmptyKey = this->getEmptyKey();

944constKeyT TombstoneKey = this->getTombstoneKey();

945if (Small &&RHS.Small) {

946// If we're swapping inline bucket arrays, we have to cope with some of

947// the tricky bits of DenseMap's storage system: the buckets are not

948// fully initialized. Thus we swap every key, but we may have

949// a one-directional move of the value.

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

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

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

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

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

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

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

957if (hasLHSValue && hasRHSValue) {

958// Swap together if we can...

959std::swap(*LHSB, *RHSB);

960continue;

961 }

962// Swap separately and handle any asymmetry.

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

964if (hasLHSValue) {

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

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

967 }elseif (hasRHSValue) {

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

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

970 }

971 }

972return;

973 }

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

975std::swap(getLargeRep()->Buckets,RHS.getLargeRep()->Buckets);

976std::swap(getLargeRep()->NumBuckets,RHS.getLargeRep()->NumBuckets);

977return;

978 }

979

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

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

982

983// First stash the large side's rep and move the small side across.

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

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

986 LargeSide.Small =true;

987// This is similar to the standard move-from-old-buckets, but the bucket

988// count hasn't actually rotated in this case. So we have to carefully

989// move construct the keys and values into their new locations, but there

990// is no need to re-hash things.

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

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

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

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

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

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

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

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

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

1000 }

1001 }

1002

1003// The hard part of moving the small buckets across is done, just move

1004// the TmpRep into its new home.

1005 SmallSide.Small =false;

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

1007 }

1008

1009SmallDenseMap &operator=(constSmallDenseMap &other) {

1010if (&other !=this)

1011 copyFrom(other);

1012return *this;

1013 }

1014

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

1016 this->destroyAll();

1017 deallocateBuckets();

1018 init(0);

1019 swap(other);

1020return *this;

1021 }

1022

1023voidcopyFrom(constSmallDenseMap &other) {

1024 this->destroyAll();

1025 deallocateBuckets();

1026 Small =true;

1027if (other.getNumBuckets() > InlineBuckets) {

1028 Small =false;

1029new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));

1030 }

1031 this->BaseT::copyFrom(other);

1032 }

1033

1034voidinit(unsigned InitBuckets) {

1035 Small =true;

1036if (InitBuckets > InlineBuckets) {

1037 Small =false;

1038new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));

1039 }

1040 this->BaseT::initEmpty();

1041 }

1042

1043voidgrow(unsigned AtLeast) {

1044if (AtLeast > InlineBuckets)

1045 AtLeast = std::max<unsigned>(64,NextPowerOf2(AtLeast - 1));

1046

1047if (Small) {

1048// First move the inline buckets into a temporary storage.

1049AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;

1050 BucketT *TmpBegin =reinterpret_cast<BucketT *>(&TmpStorage);

1051 BucketT *TmpEnd = TmpBegin;

1052

1053// Loop over the buckets, moving non-empty, non-tombstones into the

1054// temporary storage. Have the loop move the TmpEnd forward as it goes.

1055constKeyT EmptyKey = this->getEmptyKey();

1056constKeyT TombstoneKey = this->getTombstoneKey();

1057for (BucketT *P = getBuckets(), *E =P + InlineBuckets;P !=E; ++P) {

1058if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&

1059 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {

1060assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&

1061"Too many inline buckets!");

1062 ::new (&TmpEnd->getFirst())KeyT(std::move(P->getFirst()));

1063 ::new (&TmpEnd->getSecond())ValueT(std::move(P->getSecond()));

1064 ++TmpEnd;

1065P->getSecond().~ValueT();

1066 }

1067P->getFirst().~KeyT();

1068 }

1069

1070// AtLeast == InlineBuckets can happen if there are many tombstones,

1071// and grow() is used to remove them. Usually we always switch to the

1072// large rep here.

1073if (AtLeast > InlineBuckets) {

1074 Small =false;

1075new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));

1076 }

1077 this->moveFromOldBuckets(TmpBegin, TmpEnd);

1078return;

1079 }

1080

1081 LargeRep OldRep = std::move(*getLargeRep());

1082 getLargeRep()->~LargeRep();

1083if (AtLeast <= InlineBuckets) {

1084 Small =true;

1085 }else {

1086new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));

1087 }

1088

1089 this->moveFromOldBuckets(OldRep.Buckets,

1090 OldRep.Buckets + OldRep.NumBuckets);

1091

1092// Free the old table.

1093deallocate_buffer(OldRep.Buckets,sizeof(BucketT) * OldRep.NumBuckets,

1094alignof(BucketT));

1095 }

1096

1097voidshrink_and_clear() {

1098unsigned OldSize = this->size();

1099 this->destroyAll();

1100

1101// Reduce the number of buckets.

1102unsigned NewNumBuckets = 0;

1103if (OldSize) {

1104 NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1);

1105if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)

1106 NewNumBuckets = 64;

1107 }

1108if ((Small && NewNumBuckets <= InlineBuckets) ||

1109 (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {

1110 this->BaseT::initEmpty();

1111return;

1112 }

1113

1114 deallocateBuckets();

1115 init(NewNumBuckets);

1116 }

1117

1118private:

1119unsigned getNumEntries() const{return NumEntries; }

1120

1121void setNumEntries(unsigned Num) {

1122// NumEntries is hardcoded to be 31 bits wide.

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

1124 NumEntries = Num;

1125 }

1126

1127unsigned getNumTombstones() const{return NumTombstones; }

1128

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

1130

1131const BucketT *getInlineBuckets() const{

1132assert(Small);

1133// Note that this cast does not violate aliasing rules as we assert that

1134// the memory's dynamic type is the small, inline bucket buffer, and the

1135// 'storage' is a POD containing a char buffer.

1136returnreinterpret_cast<constBucketT *>(&storage);

1137 }

1138

1139 BucketT *getInlineBuckets() {

1140returnconst_cast<BucketT *>(

1141const_cast<constSmallDenseMap *>(this)->getInlineBuckets());

1142 }

1143

1144const LargeRep *getLargeRep() const{

1145assert(!Small);

1146// Note, same rule about aliasing as with getInlineBuckets.

1147returnreinterpret_cast<constLargeRep *>(&storage);

1148 }

1149

1150 LargeRep *getLargeRep() {

1151returnconst_cast<LargeRep *>(

1152const_cast<constSmallDenseMap *>(this)->getLargeRep());

1153 }

1154

1155const BucketT *getBuckets() const{

1156returnSmall ? getInlineBuckets() : getLargeRep()->Buckets;

1157 }

1158

1159 BucketT *getBuckets() {

1160returnconst_cast<BucketT *>(

1161const_cast<constSmallDenseMap *>(this)->getBuckets());

1162 }

1163

1164unsigned getNumBuckets() const{

1165returnSmall ? InlineBuckets : getLargeRep()->NumBuckets;

1166 }

1167

1168void deallocateBuckets() {

1169if (Small)

1170return;

1171

1172deallocate_buffer(getLargeRep()->Buckets,

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

1174alignof(BucketT));

1175 getLargeRep()->~LargeRep();

1176 }

1177

1178 LargeRep allocateBuckets(unsigned Num) {

1179assert(Num > InlineBuckets &&"Must allocate more buckets than are inline");

1180 LargeRep Rep = {static_cast<BucketT *>(allocate_buffer(

1181sizeof(BucketT) * Num,alignof(BucketT))),

1182 Num};

1183return Rep;

1184 }

1185};

1186

1187template <typenameKeyT,typenameValueT,typename KeyInfoT,typename Bucket,

1188boolIsConst>

1189classDenseMapIterator :DebugEpochBase::HandleBase {

1190friendclassDenseMapIterator<KeyT,ValueT, KeyInfoT, Bucket,true>;

1191friendclassDenseMapIterator<KeyT,ValueT, KeyInfoT, Bucket,false>;

1192

1193public:

1194usingdifference_type =ptrdiff_t;

1195usingvalue_type = std::conditional_t<IsConst, const Bucket, Bucket>;

1196usingpointer =value_type *;

1197usingreference =value_type &;

1198usingiterator_category = std::forward_iterator_tag;

1199

1200private:

1201pointer Ptr =nullptr;

1202pointer End =nullptr;

1203

1204public:

1205DenseMapIterator() =default;

1206

1207DenseMapIterator(pointer Pos,pointer E,constDebugEpochBase &Epoch,

1208bool NoAdvance =false)

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

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

1211

1212if (NoAdvance)

1213return;

1214if (shouldReverseIterate<KeyT>()) {

1215 RetreatPastEmptyBuckets();

1216return;

1217 }

1218 AdvancePastEmptyBuckets();

1219 }

1220

1221// Converting ctor from non-const iterators to const iterators. SFINAE'd out

1222// for const iterator destinations so it doesn't end up as a user defined copy

1223// constructor.

1224template <bool IsConstSrc,

1225typename = std::enable_if_t<!IsConstSrc && IsConst>>

1226DenseMapIterator(

1227constDenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)

1228 :DebugEpochBase::HandleBase(I),Ptr(I.Ptr),End(I.End) {}

1229

1230reference operator*() const{

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

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

1233if (shouldReverseIterate<KeyT>())

1234returnPtr[-1];

1235return *Ptr;

1236 }

1237pointer operator->() const{

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

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

1240if (shouldReverseIterate<KeyT>())

1241return &(Ptr[-1]);

1242returnPtr;

1243 }

1244

1245friendbooloperator==(constDenseMapIterator &LHS,

1246constDenseMapIterator &RHS) {

1247assert((!LHS.Ptr ||LHS.isHandleInSync()) &&"handle not in sync!");

1248assert((!RHS.Ptr ||RHS.isHandleInSync()) &&"handle not in sync!");

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

1250"comparing incomparable iterators!");

1251returnLHS.Ptr ==RHS.Ptr;

1252 }

1253

1254friendbooloperator!=(constDenseMapIterator &LHS,

1255constDenseMapIterator &RHS) {

1256return !(LHS ==RHS);

1257 }

1258

1259inlineDenseMapIterator &operator++() {// Preincrement

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

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

1262if (shouldReverseIterate<KeyT>()) {

1263 --Ptr;

1264 RetreatPastEmptyBuckets();

1265return *this;

1266 }

1267 ++Ptr;

1268 AdvancePastEmptyBuckets();

1269return *this;

1270 }

1271DenseMapIterator operator++(int) {// Postincrement

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

1273DenseMapIterator tmp = *this;

1274 ++*this;

1275return tmp;

1276 }

1277

1278private:

1279void AdvancePastEmptyBuckets() {

1280assert(Ptr <=End);

1281constKeyT Empty = KeyInfoT::getEmptyKey();

1282constKeyT Tombstone = KeyInfoT::getTombstoneKey();

1283

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

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

1286 ++Ptr;

1287 }

1288

1289void RetreatPastEmptyBuckets() {

1290assert(Ptr >=End);

1291constKeyT Empty = KeyInfoT::getEmptyKey();

1292constKeyT Tombstone = KeyInfoT::getTombstoneKey();

1293

1294while (Ptr !=End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||

1295 KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))

1296 --Ptr;

1297 }

1298};

1299

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

1301inlinesize_tcapacity_in_bytes(constDenseMap<KeyT, ValueT, KeyInfoT> &X) {

1302returnX.getMemorySize();

1303}

1304

1305}// end namespace llvm

1306

1307#endif// LLVM_ADT_DENSEMAP_H

const

aarch64 promote const

Definition:AArch64PromoteConstant.cpp:230

AlignOf.h

true

basic Basic Alias true

Definition:BasicAliasAnalysis.cpp:1981

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

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

Compiler.h

LLVM_UNLIKELY

#define LLVM_UNLIKELY(EXPR)

Definition:Compiler.h:320

LLVM_LIKELY

#define LLVM_LIKELY(EXPR)

Definition:Compiler.h:319

DenseMapInfo.h

This file defines DenseMapInfo traits for DenseMap.

End

bool End

Definition:ELF_riscv.cpp:480

EpochTracker.h

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

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

#define I(x, y, z)

Definition:MD5.cpp:58

MathExtras.h

MemAlloc.h

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

#define P(N)

ReverseIteration.h

assert

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

Ptr

@ Ptr

Definition:TargetLibraryInfo.cpp:77

Lookup

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

Definition:X86FloatingPoint.cpp:613

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

KeyT

const_iterator

ValueT

llvm::DebugEpochBase::HandleBase

Definition:EpochTracker.h:92

llvm::DebugEpochBase

Definition:EpochTracker.h:88

llvm::DebugEpochBase::incrementEpoch

void incrementEpoch()

Definition:EpochTracker.h:90

llvm::DenseMapBase

Definition:DenseMap.h:61

llvm::DenseMapBase::lookup

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:194

llvm::DenseMapBase::find

iterator find(const_arg_type_t< KeyT > Val)

Definition:DenseMap.h:156

llvm::DenseMapBase::getHashValue

static unsigned getHashValue(const KeyT &Val)

Definition:DenseMap.h:459

llvm::DenseMapBase::getEmptyKey

static const KeyT getEmptyKey()

Definition:DenseMap.h:468

llvm::DenseMapBase::try_emplace

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

Definition:DenseMap.h:226

llvm::DenseMapBase::insert

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

Definition:DenseMap.h:218

llvm::DenseMapBase::erase

bool erase(const KeyT &Val)

Definition:DenseMap.h:321

llvm::DenseMapBase::iterator

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

Definition:DenseMap.h:71

llvm::DenseMapBase::insert_as

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:277

llvm::DenseMapBase::DenseMapBase

DenseMapBase()=default

llvm::DenseMapBase::find_as

const_iterator find_as(const LookupKeyT &Val) const

Definition:DenseMap.h:184

llvm::DenseMapBase::end

const_iterator end() const

Definition:DenseMap.h:94

llvm::DenseMapBase::moveFromOldBuckets

void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd)

Definition:DenseMap.h:406

llvm::DenseMapBase::find_as

iterator find_as(const LookupKeyT &Val)

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

Definition:DenseMap.h:176

llvm::DenseMapBase::size

unsigned size() const

Definition:DenseMap.h:99

llvm::DenseMapBase::find

const_iterator find(const_arg_type_t< KeyT > Val) const

Definition:DenseMap.h:163

llvm::DenseMapBase::empty

bool empty() const

Definition:DenseMap.h:98

llvm::DenseMapBase::insert

void insert(InputIt I, InputIt E)

insert - Range insertion of pairs.

Definition:DenseMap.h:300

llvm::DenseMapBase::begin

iterator begin()

Definition:DenseMap.h:75

llvm::DenseMapBase::count

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:152

llvm::DenseMapBase::end

iterator end()

Definition:DenseMap.h:84

llvm::DenseMapBase::getTombstoneKey

static const KeyT getTombstoneKey()

Definition:DenseMap.h:474

llvm::DenseMapBase::at

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:202

llvm::DenseMapBase::isPointerIntoBucketsArray

bool isPointerIntoBucketsArray(const void *Ptr) const

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

Definition:DenseMap.h:359

llvm::DenseMapBase::copyFrom

void copyFrom(const DenseMapBase< OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT > &other)

Definition:DenseMap.h:432

llvm::DenseMapBase::contains

bool contains(const_arg_type_t< KeyT > Val) const

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

Definition:DenseMap.h:147

llvm::DenseMapBase::try_emplace

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

Definition:DenseMap.h:251

llvm::DenseMapBase::begin

const_iterator begin() const

Definition:DenseMap.h:87

llvm::DenseMapBase::getPointerIntoBucketsArray

const void * getPointerIntoBucketsArray() const

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

Definition:DenseMap.h:366

llvm::DenseMapBase::insert_or_assign

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

Definition:DenseMap.h:314

llvm::DenseMapBase::getMinBucketToReserveForEntries

unsigned getMinBucketToReserveForEntries(unsigned NumEntries)

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

Definition:DenseMap.h:397

llvm::DenseMapBase::getHashValue

static unsigned getHashValue(const LookupKeyT &Val)

Definition:DenseMap.h:464

llvm::DenseMapBase::initEmpty

void initEmpty()

Definition:DenseMap.h:384

llvm::DenseMapBase::operator[]

ValueT & operator[](const KeyT &Key)

Definition:DenseMap.h:340

llvm::DenseMapBase::value_type

BucketT value_type

Definition:DenseMap.h:69

llvm::DenseMapBase::const_iterator

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

Definition:DenseMap.h:73

llvm::DenseMapBase::destroyAll

void destroyAll()

Definition:DenseMap.h:371

llvm::DenseMapBase::insert

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

Definition:DenseMap.h:211

llvm::DenseMapBase::erase

void erase(iterator I)

Definition:DenseMap.h:332

llvm::DenseMapBase::clear

void clear()

Definition:DenseMap.h:110

llvm::DenseMapBase::insert_or_assign

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

Definition:DenseMap.h:306

llvm::DenseMapBase::reserve

void reserve(size_type NumEntries)

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

Definition:DenseMap.h:103

llvm::DenseMapBase::operator[]

ValueT & operator[](KeyT &&Key)

Definition:DenseMap.h:348

llvm::DenseMapBase::getMemorySize

size_t getMemorySize() const

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

Definition:DenseMap.h:686

llvm::DenseMapIterator

Definition:DenseMap.h:1189

llvm::DenseMapIterator::value_type

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

Definition:DenseMap.h:1195

llvm::DenseMapIterator::operator!=

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

Definition:DenseMap.h:1254

llvm::DenseMapIterator::pointer

value_type * pointer

Definition:DenseMap.h:1196

llvm::DenseMapIterator::operator++

DenseMapIterator & operator++()

Definition:DenseMap.h:1259

llvm::DenseMapIterator::operator->

pointer operator->() const

Definition:DenseMap.h:1237

llvm::DenseMapIterator::operator*

reference operator*() const

Definition:DenseMap.h:1230

llvm::DenseMapIterator::DenseMapIterator

DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, bool NoAdvance=false)

Definition:DenseMap.h:1207

llvm::DenseMapIterator::DenseMapIterator

DenseMapIterator()=default

llvm::DenseMapIterator::operator++

DenseMapIterator operator++(int)

Definition:DenseMap.h:1271

llvm::DenseMapIterator::DenseMapIterator

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

Definition:DenseMap.h:1226

llvm::DenseMapIterator::operator==

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

Definition:DenseMap.h:1245

llvm::DenseMapIterator::iterator_category

std::forward_iterator_tag iterator_category

Definition:DenseMap.h:1198

llvm::DenseMapIterator::reference

value_type & reference

Definition:DenseMap.h:1197

llvm::DenseMap

Definition:DenseMap.h:727

llvm::DenseMap::~DenseMap

~DenseMap()

Definition:DenseMap.h:764

llvm::DenseMap::DenseMap

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

Definition:DenseMap.h:759

llvm::DenseMap::copyFrom

void copyFrom(const DenseMap &other)

Definition:DenseMap.h:792

llvm::DenseMap::shrink_and_clear

void shrink_and_clear()

Definition:DenseMap.h:832

llvm::DenseMap::operator=

DenseMap & operator=(DenseMap &&other)

Definition:DenseMap.h:784

llvm::DenseMap::DenseMap

DenseMap(unsigned InitialReserve=0)

Create a DenseMap with an optional InitialReserve that guarantee that this number of elements can be ...

Definition:DenseMap.h:742

llvm::DenseMap::grow

void grow(unsigned AtLeast)

Definition:DenseMap.h:813

llvm::DenseMap::init

void init(unsigned InitNumEntries)

Definition:DenseMap.h:803

llvm::DenseMap::DenseMap

DenseMap(const DenseMap &other)

Definition:DenseMap.h:744

llvm::DenseMap::swap

void swap(DenseMap &RHS)

Definition:DenseMap.h:769

llvm::DenseMap::DenseMap

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

Definition:DenseMap.h:754

llvm::DenseMap::DenseMap

DenseMap(DenseMap &&other)

Definition:DenseMap.h:749

llvm::DenseMap::operator=

DenseMap & operator=(const DenseMap &other)

Definition:DenseMap.h:778

llvm::SmallDenseMap

Definition:DenseMap.h:883

llvm::SmallDenseMap::grow

void grow(unsigned AtLeast)

Definition:DenseMap.h:1043

llvm::SmallDenseMap::SmallDenseMap

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

Definition:DenseMap.h:924

llvm::SmallDenseMap::swap

void swap(SmallDenseMap &RHS)

Definition:DenseMap.h:937

llvm::SmallDenseMap::init

void init(unsigned InitBuckets)

Definition:DenseMap.h:1034

llvm::SmallDenseMap::operator=

SmallDenseMap & operator=(SmallDenseMap &&other)

Definition:DenseMap.h:1015

llvm::SmallDenseMap::operator=

SmallDenseMap & operator=(const SmallDenseMap &other)

Definition:DenseMap.h:1009

llvm::SmallDenseMap::SmallDenseMap

SmallDenseMap(unsigned NumInitBuckets=0)

Definition:DenseMap.h:907

llvm::SmallDenseMap::SmallDenseMap

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

Definition:DenseMap.h:929

llvm::SmallDenseMap::SmallDenseMap

SmallDenseMap(SmallDenseMap &&other)

Definition:DenseMap.h:918

llvm::SmallDenseMap::SmallDenseMap

SmallDenseMap(const SmallDenseMap &other)

Definition:DenseMap.h:913

llvm::SmallDenseMap::copyFrom

void copyFrom(const SmallDenseMap &other)

Definition:DenseMap.h:1023

llvm::SmallDenseMap::~SmallDenseMap

~SmallDenseMap()

Definition:DenseMap.h:932

llvm::SmallDenseMap::shrink_and_clear

void shrink_and_clear()

Definition:DenseMap.h:1097

ptrdiff_t

unsigned

detail

Definition:ClauseT.h:112

false

Definition:StackSlotColoring.cpp:193

llvm::AMDGPU::HSAMD::Kernel::Arg::Key::IsConst

constexpr char IsConst[]

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

Definition:AMDGPUMetadata.h:196

llvm::CodeModel::Small

@ Small

Definition:CodeGen.h:31

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::Log2_32_Ceil

unsigned Log2_32_Ceil(uint32_t Value)

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

Definition:MathExtras.h:354

llvm::size

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

Definition:STLExtras.h:1697

llvm::capacity_in_bytes

BitVector::size_type capacity_in_bytes(const BitVector &X)

Definition:BitVector.h:835

llvm::operator!=

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

Definition:APInt.h:2082

llvm::isPowerOf2_64

constexpr bool isPowerOf2_64(uint64_t Value)

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

Definition:MathExtras.h:297

llvm::bit_ceil

T bit_ceil(T Value)

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

Definition:bit.h:342

llvm::operator==

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

Definition:AddressRanges.h:153

llvm::allocate_buffer

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.

Definition:MemAlloc.cpp:15

llvm::deallocate_buffer

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

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

Definition:MemAlloc.cpp:27

llvm::move

OutputIt move(R &&Range, OutputIt Out)

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

Definition:STLExtras.h:1873

llvm::NextPowerOf2

constexpr uint64_t NextPowerOf2(uint64_t A)

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

Definition:MathExtras.h:383

std

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

Definition:BitVector.h:858

std::swap

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

Implement std::swap in terms of BitVector swap.

Definition:BitVector.h:860

llvm::AlignedCharArrayUnion

A suitably aligned and sized character array member which can hold elements of any type.

Definition:AlignOf.h:27

llvm::detail::DenseMapPair

Definition:DenseMap.h:42

llvm::detail::DenseMapPair::getSecond

const ValueT & getSecond() const

Definition:DenseMap.h:48

llvm::detail::DenseMapPair::getFirst

KeyT & getFirst()

Definition:DenseMap.h:45

llvm::detail::DenseMapPair::getFirst

const KeyT & getFirst() const

Definition:DenseMap.h:46

llvm::detail::DenseMapPair::getSecond

ValueT & getSecond()

Definition:DenseMap.h:47

type_traits.h