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//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_DENSEMAP_H
15#define LLVM_ADT_DENSEMAP_H
16
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>
34
35namespace llvm {
36
37namespace detail {
38
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>
42struct DenseMapPair : public std::pair<KeyT, ValueT> {
43 using std::pair<KeyT, ValueT>::pair;
44
45 KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
46 const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
47 ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
48 const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
49};
50
51} // end namespace detail
52
53template <typename KeyT, typename ValueT,
54 typename KeyInfoT = DenseMapInfo<KeyT>,
55 typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
56 bool IsConst = false>
57class DenseMapIterator;
58
59template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
60 typename BucketT>
61class DenseMapBase : public DebugEpochBase {
62 template <typename T>
63 using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
64
65public:
66 using size_type = unsigned;
67 using key_type = KeyT;
68 using mapped_type = ValueT;
69 using value_type = BucketT;
70
71 using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>;
72 using const_iterator =
73 DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>;
74
75 inline iterator begin() {
76 // When the map is empty, avoid the overhead of advancing/retreating past
77 // empty buckets.
78 if (empty())
79 return end();
80 if (shouldReverseIterate<KeyT>())
81 return makeIterator(P: getBucketsEnd() - 1, E: getBuckets(), Epoch&: *this);
82 return makeIterator(P: getBuckets(), E: getBucketsEnd(), Epoch&: *this);
83 }
84 inline iterator end() {
85 return makeIterator(P: getBucketsEnd(), E: getBucketsEnd(), Epoch&: *this, NoAdvance: true);
86 }
87 inline const_iterator begin() const {
88 if (empty())
89 return end();
90 if (shouldReverseIterate<KeyT>())
91 return makeConstIterator(P: getBucketsEnd() - 1, E: getBuckets(), Epoch: *this);
92 return makeConstIterator(P: getBuckets(), E: getBucketsEnd(), Epoch: *this);
93 }
94 inline const_iterator end() const {
95 return makeConstIterator(P: getBucketsEnd(), E: getBucketsEnd(), Epoch: *this, NoAdvance: true);
96 }
97
98 [[nodiscard]] bool empty() const { return getNumEntries() == 0; }
99 unsigned size() const { return getNumEntries(); }
100
101 /// Grow the densemap so that it can contain at least \p NumEntries items
102 /// before resizing again.
103 void reserve(size_type NumEntries) {
104 auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
105 incrementEpoch();
106 if (NumBuckets > getNumBuckets())
107 grow(AtLeast: NumBuckets);
108 }
109
110 void clear() {
111 incrementEpoch();
112 if (getNumEntries() == 0 && getNumTombstones() == 0) return;
113
114 // If the capacity of the array is huge, and the # elements used is small,
115 // shrink the array.
116 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
117 shrink_and_clear();
118 return;
119 }
120
121 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
122 if (std::is_trivially_destructible<ValueT>::value) {
123 // Use a simpler loop when values don't need destruction.
124 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
125 P->getFirst() = EmptyKey;
126 } else {
127 unsigned NumEntries = getNumEntries();
128 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
129 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
130 if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
131 P->getSecond().~ValueT();
132 --NumEntries;
133 }
134 P->getFirst() = EmptyKey;
135 }
136 }
137 assert(NumEntries == 0 && "Node count imbalance!");
138 (void)NumEntries;
139 }
140 setNumEntries(0);
141 setNumTombstones(0);
142 }
143
144 /// Return true if the specified key is in the map, false otherwise.
145 bool contains(const_arg_type_t<KeyT> Val) const {
146 const BucketT *TheBucket;
147 return LookupBucketFor(Val, TheBucket);
148 }
149
150 /// Return 1 if the specified key is in the map, 0 otherwise.
151 size_type count(const_arg_type_t<KeyT> Val) const {
152 return contains(Val) ? 1 : 0;
153 }
154
155 iterator find(const_arg_type_t<KeyT> Val) {
156 BucketT *TheBucket;
157 if (LookupBucketFor(Val, TheBucket))
158 return makeIterator(P: TheBucket,
159 E: shouldReverseIterate<KeyT>() ? getBuckets()
160 : getBucketsEnd(),
161 Epoch&: *this, NoAdvance: true);
162 return end();
163 }
164 const_iterator find(const_arg_type_t<KeyT> Val) const {
165 const BucketT *TheBucket;
166 if (LookupBucketFor(Val, TheBucket))
167 return makeConstIterator(P: TheBucket,
168 E: shouldReverseIterate<KeyT>() ? getBuckets()
169 : getBucketsEnd(),
170 Epoch: *this, NoAdvance: true);
171 return end();
172 }
173
174 /// Alternate version of find() which allows a different, and possibly
175 /// less expensive, key type.
176 /// The DenseMapInfo is responsible for supplying methods
177 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
178 /// type used.
179 template<class LookupKeyT>
180 iterator find_as(const LookupKeyT &Val) {
181 BucketT *TheBucket;
182 if (LookupBucketFor(Val, TheBucket))
183 return makeIterator(P: TheBucket,
184 E: shouldReverseIterate<KeyT>() ? getBuckets()
185 : getBucketsEnd(),
186 Epoch&: *this, NoAdvance: true);
187 return end();
188 }
189 template<class LookupKeyT>
190 const_iterator find_as(const LookupKeyT &Val) const {
191 const BucketT *TheBucket;
192 if (LookupBucketFor(Val, TheBucket))
193 return makeConstIterator(P: TheBucket,
194 E: shouldReverseIterate<KeyT>() ? getBuckets()
195 : getBucketsEnd(),
196 Epoch: *this, NoAdvance: true);
197 return end();
198 }
199
200 /// lookup - Return the entry for the specified key, or a default
201 /// constructed value if no such entry exists.
202 ValueT lookup(const_arg_type_t<KeyT> Val) const {
203 const BucketT *TheBucket;
204 if (LookupBucketFor(Val, TheBucket))
205 return TheBucket->getSecond();
206 return ValueT();
207 }
208
209 /// at - Return the entry for the specified key, or abort if no such
210 /// entry exists.
211 const ValueT &at(const_arg_type_t<KeyT> Val) const {
212 auto Iter = this->find(std::move(Val));
213 assert(Iter != this->end() && "DenseMap::at failed due to a missing key");
214 return Iter->second;
215 }
216
217 // Inserts key,value pair into the map if the key isn't already in the map.
218 // If the key is already in the map, it returns false and doesn't update the
219 // value.
220 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
221 return try_emplace(KV.first, KV.second);
222 }
223
224 // Inserts key,value pair into the map if the key isn't already in the map.
225 // If the key is already in the map, it returns false and doesn't update the
226 // value.
227 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
228 return try_emplace(std::move(KV.first), std::move(KV.second));
229 }
230
231 // Inserts key,value pair into the map if the key isn't already in the map.
232 // The value is constructed in-place if the key is not in the map, otherwise
233 // it is not moved.
234 template <typename... Ts>
235 std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
236 BucketT *TheBucket;
237 if (LookupBucketFor(Key, TheBucket))
238 return std::make_pair(makeIterator(P: TheBucket,
239 E: shouldReverseIterate<KeyT>()
240 ? getBuckets()
241 : getBucketsEnd(),
242 Epoch&: *this, NoAdvance: true),
243 false); // Already in map.
244
245 // Otherwise, insert the new element.
246 TheBucket =
247 InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
248 return std::make_pair(makeIterator(P: TheBucket,
249 E: shouldReverseIterate<KeyT>()
250 ? getBuckets()
251 : getBucketsEnd(),
252 Epoch&: *this, NoAdvance: true),
253 true);
254 }
255
256 // Inserts key,value pair into the map if the key isn't already in the map.
257 // The value is constructed in-place if the key is not in the map, otherwise
258 // it is not moved.
259 template <typename... Ts>
260 std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) {
261 BucketT *TheBucket;
262 if (LookupBucketFor(Key, TheBucket))
263 return std::make_pair(makeIterator(P: TheBucket,
264 E: shouldReverseIterate<KeyT>()
265 ? getBuckets()
266 : getBucketsEnd(),
267 Epoch&: *this, NoAdvance: true),
268 false); // Already in map.
269
270 // Otherwise, insert the new element.
271 TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
272 return std::make_pair(makeIterator(P: TheBucket,
273 E: shouldReverseIterate<KeyT>()
274 ? getBuckets()
275 : getBucketsEnd(),
276 Epoch&: *this, NoAdvance: true),
277 true);
278 }
279
280 /// Alternate version of insert() which allows a different, and possibly
281 /// less expensive, key type.
282 /// The DenseMapInfo is responsible for supplying methods
283 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
284 /// type used.
285 template <typename LookupKeyT>
286 std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
287 const LookupKeyT &Val) {
288 BucketT *TheBucket;
289 if (LookupBucketFor(Val, TheBucket))
290 return std::make_pair(makeIterator(P: TheBucket,
291 E: shouldReverseIterate<KeyT>()
292 ? getBuckets()
293 : getBucketsEnd(),
294 Epoch&: *this, NoAdvance: true),
295 false); // Already in map.
296
297 // Otherwise, insert the new element.
298 TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
299 std::move(KV.second), Val);
300 return std::make_pair(makeIterator(P: TheBucket,
301 E: shouldReverseIterate<KeyT>()
302 ? getBuckets()
303 : getBucketsEnd(),
304 Epoch&: *this, NoAdvance: true),
305 true);
306 }
307
308 /// insert - Range insertion of pairs.
309 template<typename InputIt>
310 void insert(InputIt I, InputIt E) {
311 for (; I != E; ++I)
312 insert(*I);
313 }
314
315 /// Returns the value associated to the key in the map if it exists. If it
316 /// does not exist, emplace a default value for the key and returns a
317 /// reference to the newly created value.
318 ValueT &getOrInsertDefault(KeyT &&Key) {
319 return try_emplace(Key).first->second;
320 }
321
322 /// Returns the value associated to the key in the map if it exists. If it
323 /// does not exist, emplace a default value for the key and returns a
324 /// reference to the newly created value.
325 ValueT &getOrInsertDefault(const KeyT &Key) {
326 return try_emplace(Key).first->second;
327 }
328
329 bool erase(const KeyT &Val) {
330 BucketT *TheBucket;
331 if (!LookupBucketFor(Val, TheBucket))
332 return false; // not in map.
333
334 TheBucket->getSecond().~ValueT();
335 TheBucket->getFirst() = getTombstoneKey();
336 decrementNumEntries();
337 incrementNumTombstones();
338 return true;
339 }
340 void erase(iterator I) {
341 BucketT *TheBucket = &*I;
342 TheBucket->getSecond().~ValueT();
343 TheBucket->getFirst() = getTombstoneKey();
344 decrementNumEntries();
345 incrementNumTombstones();
346 }
347
348 value_type& FindAndConstruct(const KeyT &Key) {
349 BucketT *TheBucket;
350 if (LookupBucketFor(Key, TheBucket))
351 return *TheBucket;
352
353 return *InsertIntoBucket(TheBucket, Key);
354 }
355
356 ValueT &operator[](const KeyT &Key) {
357 return FindAndConstruct(Key).second;
358 }
359
360 value_type& FindAndConstruct(KeyT &&Key) {
361 BucketT *TheBucket;
362 if (LookupBucketFor(Key, TheBucket))
363 return *TheBucket;
364
365 return *InsertIntoBucket(TheBucket, std::move(Key));
366 }
367
368 ValueT &operator[](KeyT &&Key) {
369 return FindAndConstruct(std::move(Key)).second;
370 }
371
372 /// isPointerIntoBucketsArray - Return true if the specified pointer points
373 /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
374 /// value in the DenseMap).
375 bool isPointerIntoBucketsArray(const void *Ptr) const {
376 return Ptr >= getBuckets() && Ptr < getBucketsEnd();
377 }
378
379 /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
380 /// array. In conjunction with the previous method, this can be used to
381 /// determine whether an insertion caused the DenseMap to reallocate.
382 const void *getPointerIntoBucketsArray() const { return getBuckets(); }
383
384protected:
385 DenseMapBase() = default;
386
387 void destroyAll() {
388 if (getNumBuckets() == 0) // Nothing to do.
389 return;
390
391 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
392 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
393 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
394 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
395 P->getSecond().~ValueT();
396 P->getFirst().~KeyT();
397 }
398 }
399
400 void initEmpty() {
401 setNumEntries(0);
402 setNumTombstones(0);
403
404 assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
405 "# initial buckets must be a power of two!");
406 const KeyT EmptyKey = getEmptyKey();
407 for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
408 ::new (&B->getFirst()) KeyT(EmptyKey);
409 }
410
411 /// Returns the number of buckets to allocate to ensure that the DenseMap can
412 /// accommodate \p NumEntries without need to grow().
413 unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
414 // Ensure that "NumEntries * 4 < NumBuckets * 3"
415 if (NumEntries == 0)
416 return 0;
417 // +1 is required because of the strict equality.
418 // For example if NumEntries is 48, we need to return 401.
419 return NextPowerOf2(A: NumEntries * 4 / 3 + 1);
420 }
421
422 void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
423 initEmpty();
424
425 // Insert all the old elements.
426 const KeyT EmptyKey = getEmptyKey();
427 const KeyT TombstoneKey = getTombstoneKey();
428 for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
429 if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
430 !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
431 // Insert the key/value into the new table.
432 BucketT *DestBucket;
433 bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
434 (void)FoundVal; // silence warning.
435 assert(!FoundVal && "Key already in new map?");
436 DestBucket->getFirst() = std::move(B->getFirst());
437 ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
438 incrementNumEntries();
439
440 // Free the value.
441 B->getSecond().~ValueT();
442 }
443 B->getFirst().~KeyT();
444 }
445 }
446
447 template <typename OtherBaseT>
448 void copyFrom(
449 const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
450 assert(&other != this);
451 assert(getNumBuckets() == other.getNumBuckets());
452
453 setNumEntries(other.getNumEntries());
454 setNumTombstones(other.getNumTombstones());
455
456 if (std::is_trivially_copyable<KeyT>::value &&
457 std::is_trivially_copyable<ValueT>::value)
458 memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(),
459 getNumBuckets() * sizeof(BucketT));
460 else
461 for (size_t i = 0; i < getNumBuckets(); ++i) {
462 ::new (&getBuckets()[i].getFirst())
463 KeyT(other.getBuckets()[i].getFirst());
464 if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
465 !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
466 ::new (&getBuckets()[i].getSecond())
467 ValueT(other.getBuckets()[i].getSecond());
468 }
469 }
470
471 static unsigned getHashValue(const KeyT &Val) {
472 return KeyInfoT::getHashValue(Val);
473 }
474
475 template<typename LookupKeyT>
476 static unsigned getHashValue(const LookupKeyT &Val) {
477 return KeyInfoT::getHashValue(Val);
478 }
479
480 static const KeyT getEmptyKey() {
481 static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
482 "Must pass the derived type to this template!");
483 return KeyInfoT::getEmptyKey();
484 }
485
486 static const KeyT getTombstoneKey() {
487 return KeyInfoT::getTombstoneKey();
488 }
489
490private:
491 iterator makeIterator(BucketT *P, BucketT *E,
492 DebugEpochBase &Epoch,
493 bool NoAdvance=false) {
494 if (shouldReverseIterate<KeyT>()) {
495 BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
496 return iterator(B, E, Epoch, NoAdvance);
497 }
498 return iterator(P, E, Epoch, NoAdvance);
499 }
500
501 const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
502 const DebugEpochBase &Epoch,
503 const bool NoAdvance=false) const {
504 if (shouldReverseIterate<KeyT>()) {
505 const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
506 return const_iterator(B, E, Epoch, NoAdvance);
507 }
508 return const_iterator(P, E, Epoch, NoAdvance);
509 }
510
511 unsigned getNumEntries() const {
512 return static_cast<const DerivedT *>(this)->getNumEntries();
513 }
514
515 void setNumEntries(unsigned Num) {
516 static_cast<DerivedT *>(this)->setNumEntries(Num);
517 }
518
519 void incrementNumEntries() {
520 setNumEntries(getNumEntries() + 1);
521 }
522
523 void decrementNumEntries() {
524 setNumEntries(getNumEntries() - 1);
525 }
526
527 unsigned getNumTombstones() const {
528 return static_cast<const DerivedT *>(this)->getNumTombstones();
529 }
530
531 void setNumTombstones(unsigned Num) {
532 static_cast<DerivedT *>(this)->setNumTombstones(Num);
533 }
534
535 void incrementNumTombstones() {
536 setNumTombstones(getNumTombstones() + 1);
537 }
538
539 void decrementNumTombstones() {
540 setNumTombstones(getNumTombstones() - 1);
541 }
542
543 const BucketT *getBuckets() const {
544 return static_cast<const DerivedT *>(this)->getBuckets();
545 }
546
547 BucketT *getBuckets() {
548 return static_cast<DerivedT *>(this)->getBuckets();
549 }
550
551 unsigned getNumBuckets() const {
552 return static_cast<const DerivedT *>(this)->getNumBuckets();
553 }
554
555 BucketT *getBucketsEnd() {
556 return getBuckets() + getNumBuckets();
557 }
558
559 const BucketT *getBucketsEnd() const {
560 return getBuckets() + getNumBuckets();
561 }
562
563 void grow(unsigned AtLeast) {
564 static_cast<DerivedT *>(this)->grow(AtLeast);
565 }
566
567 void shrink_and_clear() {
568 static_cast<DerivedT *>(this)->shrink_and_clear();
569 }
570
571 template <typename KeyArg, typename... ValueArgs>
572 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
573 ValueArgs &&... Values) {
574 TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
575
576 TheBucket->getFirst() = std::forward<KeyArg>(Key);
577 ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
578 return TheBucket;
579 }
580
581 template <typename LookupKeyT>
582 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
583 ValueT &&Value, LookupKeyT &Lookup) {
584 TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
585
586 TheBucket->getFirst() = std::move(Key);
587 ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
588 return TheBucket;
589 }
590
591 template <typename LookupKeyT>
592 BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
593 BucketT *TheBucket) {
594 incrementEpoch();
595
596 // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
597 // the buckets are empty (meaning that many are filled with tombstones),
598 // grow the table.
599 //
600 // The later case is tricky. For example, if we had one empty bucket with
601 // tons of tombstones, failing lookups (e.g. for insertion) would have to
602 // probe almost the entire table until it found the empty bucket. If the
603 // table completely filled with tombstones, no lookup would ever succeed,
604 // causing infinite loops in lookup.
605 unsigned NewNumEntries = getNumEntries() + 1;
606 unsigned NumBuckets = getNumBuckets();
607 if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
608 this->grow(NumBuckets * 2);
609 LookupBucketFor(Lookup, TheBucket);
610 NumBuckets = getNumBuckets();
611 } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
612 NumBuckets/8)) {
613 this->grow(NumBuckets);
614 LookupBucketFor(Lookup, TheBucket);
615 }
616 assert(TheBucket);
617
618 // Only update the state after we've grown our bucket space appropriately
619 // so that when growing buckets we have self-consistent entry count.
620 incrementNumEntries();
621
622 // If we are writing over a tombstone, remember this.
623 const KeyT EmptyKey = getEmptyKey();
624 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
625 decrementNumTombstones();
626
627 return TheBucket;
628 }
629
630 /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
631 /// FoundBucket. If the bucket contains the key and a value, this returns
632 /// true, otherwise it returns a bucket with an empty marker or tombstone and
633 /// returns false.
634 template<typename LookupKeyT>
635 bool LookupBucketFor(const LookupKeyT &Val,
636 const BucketT *&FoundBucket) const {
637 const BucketT *BucketsPtr = getBuckets();
638 const unsigned NumBuckets = getNumBuckets();
639
640 if (NumBuckets == 0) {
641 FoundBucket = nullptr;
642 return false;
643 }
644
645 // FoundTombstone - Keep track of whether we find a tombstone while probing.
646 const BucketT *FoundTombstone = nullptr;
647 const KeyT EmptyKey = getEmptyKey();
648 const KeyT TombstoneKey = getTombstoneKey();
649 assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
650 !KeyInfoT::isEqual(Val, TombstoneKey) &&
651 "Empty/Tombstone value shouldn't be inserted into map!");
652
653 unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
654 unsigned ProbeAmt = 1;
655 while (true) {
656 const BucketT *ThisBucket = BucketsPtr + BucketNo;
657 // Found Val's bucket? If so, return it.
658 if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
659 FoundBucket = ThisBucket;
660 return true;
661 }
662
663 // If we found an empty bucket, the key doesn't exist in the set.
664 // Insert it and return the default value.
665 if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
666 // If we've already seen a tombstone while probing, fill it in instead
667 // of the empty bucket we eventually probed to.
668 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
669 return false;
670 }
671
672 // If this is a tombstone, remember it. If Val ends up not in the map, we
673 // prefer to return it than something that would require more probing.
674 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
675 !FoundTombstone)
676 FoundTombstone = ThisBucket; // Remember the first tombstone found.
677
678 // Otherwise, it's a hash collision or a tombstone, continue quadratic
679 // probing.
680 BucketNo += ProbeAmt++;
681 BucketNo &= (NumBuckets-1);
682 }
683 }
684
685 template <typename LookupKeyT>
686 bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
687 const BucketT *ConstFoundBucket;
688 bool Result = const_cast<const DenseMapBase *>(this)
689 ->LookupBucketFor(Val, ConstFoundBucket);
690 FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
691 return Result;
692 }
693
694public:
695 /// Return the approximate size (in bytes) of the actual map.
696 /// This is just the raw memory used by DenseMap.
697 /// If entries are pointers to objects, the size of the referenced objects
698 /// are not included.
699 size_t getMemorySize() const {
700 return getNumBuckets() * sizeof(BucketT);
701 }
702};
703
704/// Equality comparison for DenseMap.
705///
706/// Iterates over elements of LHS confirming that each (key, value) pair in LHS
707/// is also in RHS, and that no additional pairs are in RHS.
708/// Equivalent to N calls to RHS.find and N value comparisons. Amortized
709/// complexity is linear, worst case is O(N^2) (if every hash collides).
710template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
711 typename BucketT>
712bool operator==(
713 const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
714 const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
715 if (LHS.size() != RHS.size())
716 return false;
717
718 for (auto &KV : LHS) {
719 auto I = RHS.find(KV.first);
720 if (I == RHS.end() || I->second != KV.second)
721 return false;
722 }
723
724 return true;
725}
726
727/// Inequality comparison for DenseMap.
728///
729/// Equivalent to !(LHS == RHS). See operator== for performance notes.
730template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
731 typename BucketT>
732bool operator!=(
733 const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
734 const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
735 return !(LHS == RHS);
736}
737
738template <typename KeyT, typename ValueT,
739 typename KeyInfoT = DenseMapInfo<KeyT>,
740 typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
741class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
742 KeyT, ValueT, KeyInfoT, BucketT> {
743 friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
744
745 // Lift some types from the dependent base class into this class for
746 // simplicity of referring to them.
747 using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
748
749 BucketT *Buckets;
750 unsigned NumEntries;
751 unsigned NumTombstones;
752 unsigned NumBuckets;
753
754public:
755 /// Create a DenseMap with an optional \p InitialReserve that guarantee that
756 /// this number of elements can be inserted in the map without grow()
757 explicit DenseMap(unsigned InitialReserve = 0) { init(InitNumEntries: InitialReserve); }
758
759 DenseMap(const DenseMap &other) : BaseT() {
760 init(InitNumEntries: 0);
761 copyFrom(other);
762 }
763
764 DenseMap(DenseMap &&other) : BaseT() {
765 init(InitNumEntries: 0);
766 swap(RHS&: other);
767 }
768
769 template<typename InputIt>
770 DenseMap(const InputIt &I, const InputIt &E) {
771 init(InitNumEntries: std::distance(I, E));
772 this->insert(I, E);
773 }
774
775 DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
776 init(InitNumEntries: Vals.size());
777 this->insert(Vals.begin(), Vals.end());
778 }
779
780 ~DenseMap() {
781 this->destroyAll();
782 deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
783 }
784
785 void swap(DenseMap& RHS) {
786 this->incrementEpoch();
787 RHS.incrementEpoch();
788 std::swap(Buckets, RHS.Buckets);
789 std::swap(NumEntries, RHS.NumEntries);
790 std::swap(NumTombstones, RHS.NumTombstones);
791 std::swap(NumBuckets, RHS.NumBuckets);
792 }
793
794 DenseMap& operator=(const DenseMap& other) {
795 if (&other != this)
796 copyFrom(other);
797 return *this;
798 }
799
800 DenseMap& operator=(DenseMap &&other) {
801 this->destroyAll();
802 deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
803 init(InitNumEntries: 0);
804 swap(RHS&: other);
805 return *this;
806 }
807
808 void copyFrom(const DenseMap& other) {
809 this->destroyAll();
810 deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
811 if (allocateBuckets(Num: other.NumBuckets)) {
812 this->BaseT::copyFrom(other);
813 } else {
814 NumEntries = 0;
815 NumTombstones = 0;
816 }
817 }
818
819 void init(unsigned InitNumEntries) {
820 auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
821 if (allocateBuckets(Num: InitBuckets)) {
822 this->BaseT::initEmpty();
823 } else {
824 NumEntries = 0;
825 NumTombstones = 0;
826 }
827 }
828
829 void grow(unsigned AtLeast) {
830 unsigned OldNumBuckets = NumBuckets;
831 BucketT *OldBuckets = Buckets;
832
833 allocateBuckets(Num: std::max<unsigned>(a: 64, b: static_cast<unsigned>(NextPowerOf2(A: AtLeast-1))));
834 assert(Buckets);
835 if (!OldBuckets) {
836 this->BaseT::initEmpty();
837 return;
838 }
839
840 this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
841
842 // Free the old table.
843 deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets,
844 alignof(BucketT));
845 }
846
847 void shrink_and_clear() {
848 unsigned OldNumBuckets = NumBuckets;
849 unsigned OldNumEntries = NumEntries;
850 this->destroyAll();
851
852 // Reduce the number of buckets.
853 unsigned NewNumBuckets = 0;
854 if (OldNumEntries)
855 NewNumBuckets = std::max(a: 64, b: 1 << (Log2_32_Ceil(Value: OldNumEntries) + 1));
856 if (NewNumBuckets == NumBuckets) {
857 this->BaseT::initEmpty();
858 return;
859 }
860
861 deallocate_buffer(Buckets, sizeof(BucketT) * OldNumBuckets,
862 alignof(BucketT));
863 init(InitNumEntries: NewNumBuckets);
864 }
865
866private:
867 unsigned getNumEntries() const {
868 return NumEntries;
869 }
870
871 void setNumEntries(unsigned Num) {
872 NumEntries = Num;
873 }
874
875 unsigned getNumTombstones() const {
876 return NumTombstones;
877 }
878
879 void setNumTombstones(unsigned Num) {
880 NumTombstones = Num;
881 }
882
883 BucketT *getBuckets() const {
884 return Buckets;
885 }
886
887 unsigned getNumBuckets() const {
888 return NumBuckets;
889 }
890
891 bool allocateBuckets(unsigned Num) {
892 NumBuckets = Num;
893 if (NumBuckets == 0) {
894 Buckets = nullptr;
895 return false;
896 }
897
898 Buckets = static_cast<BucketT *>(
899 allocate_buffer(Size: sizeof(BucketT) * NumBuckets, Alignment: alignof(BucketT)));
900 return true;
901 }
902};
903
904template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
905 typename KeyInfoT = DenseMapInfo<KeyT>,
906 typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
907class SmallDenseMap
908 : public DenseMapBase<
909 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
910 ValueT, KeyInfoT, BucketT> {
911 friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
912
913 // Lift some types from the dependent base class into this class for
914 // simplicity of referring to them.
915 using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
916
917 static_assert(isPowerOf2_64(Value: InlineBuckets),
918 "InlineBuckets must be a power of 2.");
919
920 unsigned Small : 1;
921 unsigned NumEntries : 31;
922 unsigned NumTombstones;
923
924 struct LargeRep {
925 BucketT *Buckets;
926 unsigned NumBuckets;
927 };
928
929 /// A "union" of an inline bucket array and the struct representing
930 /// a large bucket. This union will be discriminated by the 'Small' bit.
931 AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;
932
933public:
934 explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
935 if (NumInitBuckets > InlineBuckets)
936 NumInitBuckets = llvm::bit_ceil(Value: NumInitBuckets);
937 init(InitBuckets: NumInitBuckets);
938 }
939
940 SmallDenseMap(const SmallDenseMap &other) : BaseT() {
941 init(InitBuckets: 0);
942 copyFrom(other);
943 }
944
945 SmallDenseMap(SmallDenseMap &&other) : BaseT() {
946 init(InitBuckets: 0);
947 swap(RHS&: other);
948 }
949
950 template<typename InputIt>
951 SmallDenseMap(const InputIt &I, const InputIt &E) {
952 init(InitBuckets: NextPowerOf2(std::distance(I, E)));
953 this->insert(I, E);
954 }
955
956 SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals)
957 : SmallDenseMap(Vals.begin(), Vals.end()) {}
958
959 ~SmallDenseMap() {
960 this->destroyAll();
961 deallocateBuckets();
962 }
963
964 void swap(SmallDenseMap& RHS) {
965 unsigned TmpNumEntries = RHS.NumEntries;
966 RHS.NumEntries = NumEntries;
967 NumEntries = TmpNumEntries;
968 std::swap(NumTombstones, RHS.NumTombstones);
969
970 const KeyT EmptyKey = this->getEmptyKey();
971 const KeyT TombstoneKey = this->getTombstoneKey();
972 if (Small && RHS.Small) {
973 // If we're swapping inline bucket arrays, we have to cope with some of
974 // the tricky bits of DenseMap's storage system: the buckets are not
975 // fully initialized. Thus we swap every key, but we may have
976 // a one-directional move of the value.
977 for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
978 BucketT *LHSB = &getInlineBuckets()[i],
979 *RHSB = &RHS.getInlineBuckets()[i];
980 bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
981 !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
982 bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
983 !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
984 if (hasLHSValue && hasRHSValue) {
985 // Swap together if we can...
986 std::swap(*LHSB, *RHSB);
987 continue;
988 }
989 // Swap separately and handle any asymmetry.
990 std::swap(LHSB->getFirst(), RHSB->getFirst());
991 if (hasLHSValue) {
992 ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
993 LHSB->getSecond().~ValueT();
994 } else if (hasRHSValue) {
995 ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
996 RHSB->getSecond().~ValueT();
997 }
998 }
999 return;
1000 }
1001 if (!Small && !RHS.Small) {
1002 std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets);
1003 std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets);
1004 return;
1005 }
1006
1007 SmallDenseMap &SmallSide = Small ? *this : RHS;
1008 SmallDenseMap &LargeSide = Small ? RHS : *this;
1009
1010 // First stash the large side's rep and move the small side across.
1011 LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
1012 LargeSide.getLargeRep()->~LargeRep();
1013 LargeSide.Small = true;
1014 // This is similar to the standard move-from-old-buckets, but the bucket
1015 // count hasn't actually rotated in this case. So we have to carefully
1016 // move construct the keys and values into their new locations, but there
1017 // is no need to re-hash things.
1018 for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
1019 BucketT *NewB = &LargeSide.getInlineBuckets()[i],
1020 *OldB = &SmallSide.getInlineBuckets()[i];
1021 ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
1022 OldB->getFirst().~KeyT();
1023 if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
1024 !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
1025 ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
1026 OldB->getSecond().~ValueT();
1027 }
1028 }
1029
1030 // The hard part of moving the small buckets across is done, just move
1031 // the TmpRep into its new home.
1032 SmallSide.Small = false;
1033 new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
1034 }
1035
1036 SmallDenseMap& operator=(const SmallDenseMap& other) {
1037 if (&other != this)
1038 copyFrom(other);
1039 return *this;
1040 }
1041
1042 SmallDenseMap& operator=(SmallDenseMap &&other) {
1043 this->destroyAll();
1044 deallocateBuckets();
1045 init(InitBuckets: 0);
1046 swap(RHS&: other);
1047 return *this;
1048 }
1049
1050 void copyFrom(const SmallDenseMap& other) {
1051 this->destroyAll();
1052 deallocateBuckets();
1053 Small = true;
1054 if (other.getNumBuckets() > InlineBuckets) {
1055 Small = false;
1056 new (getLargeRep()) LargeRep(allocateBuckets(Num: other.getNumBuckets()));
1057 }
1058 this->BaseT::copyFrom(other);
1059 }
1060
1061 void init(unsigned InitBuckets) {
1062 Small = true;
1063 if (InitBuckets > InlineBuckets) {
1064 Small = false;
1065 new (getLargeRep()) LargeRep(allocateBuckets(Num: InitBuckets));
1066 }
1067 this->BaseT::initEmpty();
1068 }
1069
1070 void grow(unsigned AtLeast) {
1071 if (AtLeast > InlineBuckets)
1072 AtLeast = std::max<unsigned>(a: 64, b: NextPowerOf2(A: AtLeast-1));
1073
1074 if (Small) {
1075 // First move the inline buckets into a temporary storage.
1076 AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;
1077 BucketT *TmpBegin = reinterpret_cast<BucketT *>(&TmpStorage);
1078 BucketT *TmpEnd = TmpBegin;
1079
1080 // Loop over the buckets, moving non-empty, non-tombstones into the
1081 // temporary storage. Have the loop move the TmpEnd forward as it goes.
1082 const KeyT EmptyKey = this->getEmptyKey();
1083 const KeyT TombstoneKey = this->getTombstoneKey();
1084 for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
1085 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
1086 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
1087 assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&
1088 "Too many inline buckets!");
1089 ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
1090 ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
1091 ++TmpEnd;
1092 P->getSecond().~ValueT();
1093 }
1094 P->getFirst().~KeyT();
1095 }
1096
1097 // AtLeast == InlineBuckets can happen if there are many tombstones,
1098 // and grow() is used to remove them. Usually we always switch to the
1099 // large rep here.
1100 if (AtLeast > InlineBuckets) {
1101 Small = false;
1102 new (getLargeRep()) LargeRep(allocateBuckets(Num: AtLeast));
1103 }
1104 this->moveFromOldBuckets(TmpBegin, TmpEnd);
1105 return;
1106 }
1107
1108 LargeRep OldRep = std::move(*getLargeRep());
1109 getLargeRep()->~LargeRep();
1110 if (AtLeast <= InlineBuckets) {
1111 Small = true;
1112 } else {
1113 new (getLargeRep()) LargeRep(allocateBuckets(Num: AtLeast));
1114 }
1115
1116 this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
1117
1118 // Free the old table.
1119 deallocate_buffer(OldRep.Buckets, sizeof(BucketT) * OldRep.NumBuckets,
1120 alignof(BucketT));
1121 }
1122
1123 void shrink_and_clear() {
1124 unsigned OldSize = this->size();
1125 this->destroyAll();
1126
1127 // Reduce the number of buckets.
1128 unsigned NewNumBuckets = 0;
1129 if (OldSize) {
1130 NewNumBuckets = 1 << (Log2_32_Ceil(Value: OldSize) + 1);
1131 if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
1132 NewNumBuckets = 64;
1133 }
1134 if ((Small && NewNumBuckets <= InlineBuckets) ||
1135 (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
1136 this->BaseT::initEmpty();
1137 return;
1138 }
1139
1140 deallocateBuckets();
1141 init(InitBuckets: NewNumBuckets);
1142 }
1143
1144private:
1145 unsigned getNumEntries() const {
1146 return NumEntries;
1147 }
1148
1149 void setNumEntries(unsigned Num) {
1150 // NumEntries is hardcoded to be 31 bits wide.
1151 assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries");
1152 NumEntries = Num;
1153 }
1154
1155 unsigned getNumTombstones() const {
1156 return NumTombstones;
1157 }
1158
1159 void setNumTombstones(unsigned Num) {
1160 NumTombstones = Num;
1161 }
1162
1163 const BucketT *getInlineBuckets() const {
1164 assert(Small);
1165 // Note that this cast does not violate aliasing rules as we assert that
1166 // the memory's dynamic type is the small, inline bucket buffer, and the
1167 // 'storage' is a POD containing a char buffer.
1168 return reinterpret_cast<const BucketT *>(&storage);
1169 }
1170
1171 BucketT *getInlineBuckets() {
1172 return const_cast<BucketT *>(
1173 const_cast<const SmallDenseMap *>(this)->getInlineBuckets());
1174 }
1175
1176 const LargeRep *getLargeRep() const {
1177 assert(!Small);
1178 // Note, same rule about aliasing as with getInlineBuckets.
1179 return reinterpret_cast<const LargeRep *>(&storage);
1180 }
1181
1182 LargeRep *getLargeRep() {
1183 return const_cast<LargeRep *>(
1184 const_cast<const SmallDenseMap *>(this)->getLargeRep());
1185 }
1186
1187 const BucketT *getBuckets() const {
1188 return Small ? getInlineBuckets() : getLargeRep()->Buckets;
1189 }
1190
1191 BucketT *getBuckets() {
1192 return const_cast<BucketT *>(
1193 const_cast<const SmallDenseMap *>(this)->getBuckets());
1194 }
1195
1196 unsigned getNumBuckets() const {
1197 return Small ? InlineBuckets : getLargeRep()->NumBuckets;
1198 }
1199
1200 void deallocateBuckets() {
1201 if (Small)
1202 return;
1203
1204 deallocate_buffer(getLargeRep()->Buckets,
1205 sizeof(BucketT) * getLargeRep()->NumBuckets,
1206 alignof(BucketT));
1207 getLargeRep()->~LargeRep();
1208 }
1209
1210 LargeRep allocateBuckets(unsigned Num) {
1211 assert(Num > InlineBuckets && "Must allocate more buckets than are inline");
1212 LargeRep Rep = {static_cast<BucketT *>(allocate_buffer(
1213 Size: sizeof(BucketT) * Num, Alignment: alignof(BucketT))),
1214 Num};
1215 return Rep;
1216 }
1217};
1218
1219template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
1220 bool IsConst>
1221class DenseMapIterator : DebugEpochBase::HandleBase {
1222 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
1223 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;
1224
1225public:
1226 using difference_type = ptrdiff_t;
1227 using value_type = std::conditional_t<IsConst, const Bucket, Bucket>;
1228 using pointer = value_type *;
1229 using reference = value_type &;
1230 using iterator_category = std::forward_iterator_tag;
1231
1232private:
1233 pointer Ptr = nullptr;
1234 pointer End = nullptr;
1235
1236public:
1237 DenseMapIterator() = default;
1238
1239 DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
1240 bool NoAdvance = false)
1241 : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
1242 assert(isHandleInSync() && "invalid construction!");
1243
1244 if (NoAdvance) return;
1245 if (shouldReverseIterate<KeyT>()) {
1246 RetreatPastEmptyBuckets();
1247 return;
1248 }
1249 AdvancePastEmptyBuckets();
1250 }
1251
1252 // Converting ctor from non-const iterators to const iterators. SFINAE'd out
1253 // for const iterator destinations so it doesn't end up as a user defined copy
1254 // constructor.
1255 template <bool IsConstSrc,
1256 typename = std::enable_if_t<!IsConstSrc && IsConst>>
1257 DenseMapIterator(
1258 const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
1259 : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}
1260
1261 reference operator*() const {
1262 assert(isHandleInSync() && "invalid iterator access!");
1263 assert(Ptr != End && "dereferencing end() iterator");
1264 if (shouldReverseIterate<KeyT>())
1265 return Ptr[-1];
1266 return *Ptr;
1267 }
1268 pointer operator->() const {
1269 assert(isHandleInSync() && "invalid iterator access!");
1270 assert(Ptr != End && "dereferencing end() iterator");
1271 if (shouldReverseIterate<KeyT>())
1272 return &(Ptr[-1]);
1273 return Ptr;
1274 }
1275
1276 friend bool operator==(const DenseMapIterator &LHS,
1277 const DenseMapIterator &RHS) {
1278 assert((!LHS.Ptr || LHS.isHandleInSync()) && "handle not in sync!");
1279 assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
1280 assert(LHS.getEpochAddress() == RHS.getEpochAddress() &&
1281 "comparing incomparable iterators!");
1282 return LHS.Ptr == RHS.Ptr;
1283 }
1284
1285 friend bool operator!=(const DenseMapIterator &LHS,
1286 const DenseMapIterator &RHS) {
1287 return !(LHS == RHS);
1288 }
1289
1290 inline DenseMapIterator& operator++() { // Preincrement
1291 assert(isHandleInSync() && "invalid iterator access!");
1292 assert(Ptr != End && "incrementing end() iterator");
1293 if (shouldReverseIterate<KeyT>()) {
1294 --Ptr;
1295 RetreatPastEmptyBuckets();
1296 return *this;
1297 }
1298 ++Ptr;
1299 AdvancePastEmptyBuckets();
1300 return *this;
1301 }
1302 DenseMapIterator operator++(int) { // Postincrement
1303 assert(isHandleInSync() && "invalid iterator access!");
1304 DenseMapIterator tmp = *this; ++*this; return tmp;
1305 }
1306
1307private:
1308 void AdvancePastEmptyBuckets() {
1309 assert(Ptr <= End);
1310 const KeyT Empty = KeyInfoT::getEmptyKey();
1311 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1312
1313 while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
1314 KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
1315 ++Ptr;
1316 }
1317
1318 void RetreatPastEmptyBuckets() {
1319 assert(Ptr >= End);
1320 const KeyT Empty = KeyInfoT::getEmptyKey();
1321 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1322
1323 while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
1324 KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
1325 --Ptr;
1326 }
1327};
1328
1329template <typename KeyT, typename ValueT, typename KeyInfoT>
1330inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
1331 return X.getMemorySize();
1332}
1333
1334} // end namespace llvm
1335
1336#endif // LLVM_ADT_DENSEMAP_H
1337

source code of include/llvm-17/llvm/ADT/DenseMap.h