Line data Source code
1 : //===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
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/ReverseIteration.h"
23 : #include "llvm/Support/type_traits.h"
24 : #include <algorithm>
25 : #include <cassert>
26 : #include <cstddef>
27 : #include <cstring>
28 : #include <initializer_list>
29 : #include <iterator>
30 : #include <new>
31 : #include <type_traits>
32 : #include <utility>
33 :
34 : namespace llvm {
35 :
36 : namespace detail {
37 :
38 : // We extend a pair to allow users to override the bucket type with their own
39 : // implementation without requiring two members.
40 : template <typename KeyT, typename ValueT>
41 442 : struct DenseMapPair : public std::pair<KeyT, ValueT> {
42 :
43 7 : using std::pair<KeyT, ValueT>::pair;
44 :
45 672987033 : KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
46 354722738 : const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
47 119784013 : ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
48 48361 : const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
49 : };
50 :
51 : } // end namespace detail
52 :
53 : template <typename KeyT, typename ValueT,
54 : typename KeyInfoT = DenseMapInfo<KeyT>,
55 : typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
56 : bool IsConst = false>
57 : class DenseMapIterator;
58 :
59 : template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
60 : typename BucketT>
61 : class DenseMapBase : public DebugEpochBase {
62 : template <typename T>
63 : using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
64 :
65 : public:
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 125873806 : inline iterator begin() {
76 : // When the map is empty, avoid the overhead of advancing/retreating past
77 : // empty buckets.
78 125873806 : if (empty())
79 : return end();
80 : if (shouldReverseIterate<KeyT>())
81 : return makeIterator(getBucketsEnd() - 1, getBuckets(), *this);
82 : return makeIterator(getBuckets(), getBucketsEnd(), *this);
83 : }
84 85369935 : inline iterator end() {
85 : return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
86 : }
87 87460306 : inline const_iterator begin() const {
88 2090371 : if (empty())
89 : return end();
90 : if (shouldReverseIterate<KeyT>())
91 : return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this);
92 : return makeConstIterator(getBuckets(), getBucketsEnd(), *this);
93 13500945 : }
94 961008 : inline const_iterator end() const {
95 961008 : return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
96 13500945 : }
97 :
98 : LLVM_NODISCARD bool empty() const {
99 1 : return getNumEntries() == 0;
100 : }
101 615812 : unsigned size() const { return getNumEntries(); }
102 801962 :
103 : /// Grow the densemap so that it can contain at least \p NumEntries items
104 : /// before resizing again.
105 1237455 : void reserve(size_type NumEntries) {
106 307244 : auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
107 : incrementEpoch();
108 744251 : if (NumBuckets > getNumBuckets())
109 190 : grow(NumBuckets);
110 744061 : }
111 396378 :
112 98990475 : void clear() {
113 6787 : incrementEpoch();
114 175679675 : if (getNumEntries() == 0 && getNumTombstones() == 0) return;
115 18803 :
116 61617 : // If the capacity of the array is huge, and the # elements used is small,
117 78444 : // shrink the array.
118 21090504 : if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
119 4115 : shrink_and_clear();
120 4485101 : return;
121 1 : }
122 78917 :
123 511499 : const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
124 5880010 : if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) {
125 2 : // Use a simpler loop when these are trivial types.
126 1082038280 : for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
127 1021415677 : P->getFirst() = EmptyKey;
128 13352078 : } else {
129 282961 : unsigned NumEntries = getNumEntries();
130 68426048 : for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
131 52129780 : if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
132 28503760 : if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
133 255654 : P->getSecond().~ValueT();
134 130782 : --NumEntries;
135 326 : }
136 7298380 : P->getFirst() = EmptyKey;
137 329 : }
138 951295 : }
139 2771953 : assert(NumEntries == 0 && "Node count imbalance!");
140 188768572 : }
141 187851722 : setNumEntries(0);
142 198831019 : setNumTombstones(0);
143 195947840 : }
144 403100734 :
145 356843712 : /// Return 1 if the specified key is in the map, 0 otherwise.
146 58015335 : size_type count(const_arg_type_t<KeyT> Val) const {
147 2307714 : const BucketT *TheBucket;
148 68704840 : return LookupBucketFor(Val, TheBucket) ? 1 : 0;
149 16085 : }
150 10993940 :
151 1884921150 : iterator find(const_arg_type_t<KeyT> Val) {
152 39669 : BucketT *TheBucket;
153 1906455001 : if (LookupBucketFor(Val, TheBucket))
154 18828555 : return makeIterator(TheBucket, getBucketsEnd(), *this, true);
155 30 : return end();
156 171341 : }
157 222918165 : const_iterator find(const_arg_type_t<KeyT> Val) const {
158 295544100 : const BucketT *TheBucket;
159 499576437 : if (LookupBucketFor(Val, TheBucket))
160 62117851 : return makeConstIterator(TheBucket, getBucketsEnd(), *this, true);
161 : return end();
162 11465668 : }
163 81606164 :
164 8755930 : /// Alternate version of find() which allows a different, and possibly
165 80123592 : /// less expensive, key type.
166 23948238 : /// The DenseMapInfo is responsible for supplying methods
167 10088228 : /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
168 2244882 : /// type used.
169 921987343 : template<class LookupKeyT>
170 75999138 : iterator find_as(const LookupKeyT &Val) {
171 922553606 : BucketT *TheBucket;
172 265382840 : if (LookupBucketFor(Val, TheBucket))
173 168950455 : return makeIterator(TheBucket, getBucketsEnd(), *this, true);
174 977848 : return end();
175 49728250 : }
176 43917182 : template<class LookupKeyT>
177 69958301 : const_iterator find_as(const LookupKeyT &Val) const {
178 77580265 : const BucketT *TheBucket;
179 4420510 : if (LookupBucketFor(Val, TheBucket))
180 28277924 : return makeConstIterator(TheBucket, getBucketsEnd(), *this, true);
181 582376934 : return end();
182 84711209 : }
183 583097944 :
184 85178381 : /// lookup - Return the entry for the specified key, or a default
185 3048753 : /// constructed value if no such entry exists.
186 7636299 : ValueT lookup(const_arg_type_t<KeyT> Val) const {
187 129662490 : const BucketT *TheBucket;
188 77826009 : if (LookupBucketFor(Val, TheBucket))
189 173144634 : return TheBucket->getSecond();
190 279760863 : return ValueT();
191 254632412 : }
192 3561718 :
193 53052103 : // Inserts key,value pair into the map if the key isn't already in the map.
194 50364147 : // If the key is already in the map, it returns false and doesn't update the
195 71512511 : // value.
196 37989263 : std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
197 3077112 : return try_emplace(KV.first, KV.second);
198 5149438 : }
199 25756022 :
200 32146768 : // Inserts key,value pair into the map if the key isn't already in the map.
201 28489651 : // If the key is already in the map, it returns false and doesn't update the
202 65606766 : // value.
203 3024653 : std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
204 634818185 : return try_emplace(std::move(KV.first), std::move(KV.second));
205 8314350 : }
206 44817638 :
207 46880930 : // Inserts key,value pair into the map if the key isn't already in the map.
208 203955429 : // The value is constructed in-place if the key is not in the map, otherwise
209 184345618 : // it is not moved.
210 14109873 : template <typename... Ts>
211 700389580 : std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
212 61208517 : BucketT *TheBucket;
213 700354954 : if (LookupBucketFor(Key, TheBucket))
214 22923076 : return std::make_pair(
215 126635567 : makeIterator(TheBucket, getBucketsEnd(), *this, true),
216 10791449 : false); // Already in map.
217 126932405 :
218 10021870 : // Otherwise, insert the new element.
219 5411919 : TheBucket =
220 5888499 : InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
221 6567228 : return std::make_pair(
222 172734876 : makeIterator(TheBucket, getBucketsEnd(), *this, true),
223 721496132 : true);
224 3745242 : }
225 569896600 :
226 67181989 : // Inserts key,value pair into the map if the key isn't already in the map.
227 32702933 : // The value is constructed in-place if the key is not in the map, otherwise
228 55275046 : // it is not moved.
229 37627729 : template <typename... Ts>
230 139629842 : std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) {
231 91588081 : BucketT *TheBucket;
232 25727733 : if (LookupBucketFor(Key, TheBucket))
233 29807558 : return std::make_pair(
234 1787141 : makeIterator(TheBucket, getBucketsEnd(), *this, true),
235 77348986 : false); // Already in map.
236 10545309 :
237 60074173 : // Otherwise, insert the new element.
238 164100353 : TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
239 178778915 : return std::make_pair(
240 12204497 : makeIterator(TheBucket, getBucketsEnd(), *this, true),
241 14182404 : true);
242 11475966 : }
243 22912965 :
244 21063407 : /// Alternate version of insert() which allows a different, and possibly
245 26540374 : /// less expensive, key type.
246 1345860 : /// The DenseMapInfo is responsible for supplying methods
247 217527969 : /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
248 24825887 : /// type used.
249 206256163 : template <typename LookupKeyT>
250 20488755 : std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
251 6288727 : const LookupKeyT &Val) {
252 18735259 : BucketT *TheBucket;
253 90583497 : if (LookupBucketFor(Val, TheBucket))
254 2504523 : return std::make_pair(
255 70908526 : makeIterator(TheBucket, getBucketsEnd(), *this, true),
256 35532563 : false); // Already in map.
257 918557 :
258 18136515 : // Otherwise, insert the new element.
259 65103420 : TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
260 1672576 : std::move(KV.second), Val);
261 65744682 : return std::make_pair(
262 4340730 : makeIterator(TheBucket, getBucketsEnd(), *this, true),
263 36235456 : true);
264 1261449 : }
265 37747121 :
266 749578 : /// insert - Range insertion of pairs.
267 6112114 : template<typename InputIt>
268 10045378 : void insert(InputIt I, InputIt E) {
269 9887947 : for (; I != E; ++I)
270 2719361 : insert(*I);
271 4252321 : }
272 21624964 :
273 193874701 : bool erase(const KeyT &Val) {
274 175350 : BucketT *TheBucket;
275 173290731 : if (!LookupBucketFor(Val, TheBucket))
276 3587931 : return false; // not in map.
277 499862537 :
278 12103753 : TheBucket->getSecond().~ValueT();
279 648730020 : TheBucket->getFirst() = getTombstoneKey();
280 2021139 : decrementNumEntries();
281 41281350 : incrementNumTombstones();
282 170160250 : return true;
283 14582654 : }
284 153913481 : void erase(iterator I) {
285 33611780 : BucketT *TheBucket = &*I;
286 152891851 : TheBucket->getSecond().~ValueT();
287 20829293 : TheBucket->getFirst() = getTombstoneKey();
288 294452 : decrementNumEntries();
289 41365735 : incrementNumTombstones();
290 118259893 : }
291 37953039 :
292 437747351 : value_type& FindAndConstruct(const KeyT &Key) {
293 152033321 : BucketT *TheBucket;
294 445335325 : if (LookupBucketFor(Key, TheBucket))
295 82338778 : return *TheBucket;
296 10809246 :
297 230842746 : return *InsertIntoBucket(TheBucket, Key);
298 61487489 : }
299 128789555 :
300 3836462 : ValueT &operator[](const KeyT &Key) {
301 249174433 : return FindAndConstruct(Key).second;
302 36600 : }
303 19330085 :
304 251634052 : value_type& FindAndConstruct(KeyT &&Key) {
305 108074818 : BucketT *TheBucket;
306 395727773 : if (LookupBucketFor(Key, TheBucket))
307 13365396 : return *TheBucket;
308 272031840 :
309 180761247 : return *InsertIntoBucket(TheBucket, std::move(Key));
310 496712232 : }
311 79402751 :
312 30873920 : ValueT &operator[](KeyT &&Key) {
313 294208097 : return FindAndConstruct(std::move(Key)).second;
314 53638696 : }
315 270171073 :
316 154463745 : /// isPointerIntoBucketsArray - Return true if the specified pointer points
317 556597300 : /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
318 66245113 : /// value in the DenseMap).
319 662886603 : bool isPointerIntoBucketsArray(const void *Ptr) const {
320 96599038 : return Ptr >= getBuckets() && Ptr < getBucketsEnd();
321 258010917 : }
322 97410028 :
323 127992701 : /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
324 45892476 : /// array. In conjunction with the previous method, this can be used to
325 103189356 : /// determine whether an insertion caused the DenseMap to reallocate.
326 180870178 : const void *getPointerIntoBucketsArray() const { return getBuckets(); }
327 189525155 :
328 237392643 : protected:
329 25301247 : DenseMapBase() = default;
330 243383779 :
331 187442610 : void destroyAll() {
332 168588092 : if (getNumBuckets() == 0) // Nothing to do.
333 239124384 : return;
334 44681446 :
335 193911736 : const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
336 238689676 : for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
337 257845129 : if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
338 191019652 : !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
339 122002014 : P->getSecond().~ValueT();
340 16687735 : P->getFirst().~KeyT();
341 54669983 : }
342 12752572 : }
343 27260101 :
344 47813533 : void initEmpty() {
345 524410092 : setNumEntries(0);
346 141786396 : setNumTombstones(0);
347 512710700 :
348 55754318 : assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
349 165761640 : "# initial buckets must be a power of two!");
350 432282668 : const KeyT EmptyKey = getEmptyKey();
351 3604871778 : for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
352 3023788059 : ::new (&B->getFirst()) KeyT(EmptyKey);
353 216951186 : }
354 46527172 :
355 165535030 : /// Returns the number of buckets to allocate to ensure that the DenseMap can
356 810989272 : /// accommodate \p NumEntries without need to grow().
357 94291978 : unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
358 287425181 : // Ensure that "NumEntries * 4 < NumBuckets * 3"
359 58882447 : if (NumEntries == 0)
360 35243492 : return 0;
361 113536130 : // +1 is required because of the strict equality.
362 27262242 : // For example if NumEntries is 48, we need to return 401.
363 79606794 : return NextPowerOf2(NumEntries * 4 / 3 + 1);
364 25789210 : }
365 402820771 :
366 308409306 : void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
367 44279965 : initEmpty();
368 104234958 :
369 187147440 : // Insert all the old elements.
370 184817080 : const KeyT EmptyKey = getEmptyKey();
371 39844801 : const KeyT TombstoneKey = getTombstoneKey();
372 233659405 : for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
373 229073733 : if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
374 227494961 : !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
375 269824856 : // Insert the key/value into the new table.
376 23267929 : BucketT *DestBucket;
377 177731548 : bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
378 151005922 : (void)FoundVal; // silence warning.
379 31804507 : assert(!FoundVal && "Key already in new map?");
380 250355104 : DestBucket->getFirst() = std::move(B->getFirst());
381 124309877 : ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
382 94850187 : incrementNumEntries();
383 43132879 :
384 147773199 : // Free the value.
385 86876165 : B->getSecond().~ValueT();
386 139702465 : }
387 281187427 : B->getFirst().~KeyT();
388 207805552 : }
389 436995307 : }
390 257981323 :
391 75813754 : template <typename OtherBaseT>
392 61194030 : void copyFrom(
393 30948778 : const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
394 24474296 : assert(&other != this);
395 32279851 : assert(getNumBuckets() == other.getNumBuckets());
396 69162616 :
397 92831920 : setNumEntries(other.getNumEntries());
398 44778735 : setNumTombstones(other.getNumTombstones());
399 15422625 :
400 76376912 : if (isPodLike<KeyT>::value && isPodLike<ValueT>::value)
401 115900999 : memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(),
402 37800695 : getNumBuckets() * sizeof(BucketT));
403 471166740 : else
404 391678599 : for (size_t i = 0; i < getNumBuckets(); ++i) {
405 13780333 : ::new (&getBuckets()[i].getFirst())
406 12029736 : KeyT(other.getBuckets()[i].getFirst());
407 235649478 : if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
408 150657906 : !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
409 190784617 : ::new (&getBuckets()[i].getSecond())
410 91700702 : ValueT(other.getBuckets()[i].getSecond());
411 92710025 : }
412 57768227 : }
413 25175106 :
414 15510173 : static unsigned getHashValue(const KeyT &Val) {
415 67944822 : return KeyInfoT::getHashValue(Val);
416 97463817 : }
417 507267239 :
418 620272234 : template<typename LookupKeyT>
419 312533387 : static unsigned getHashValue(const LookupKeyT &Val) {
420 33351533 : return KeyInfoT::getHashValue(Val);
421 21058603 : }
422 71796627 :
423 1095903939 : static const KeyT getEmptyKey() {
424 1004775175 : static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
425 413944967 : "Must pass the derived type to this template!");
426 301498683 : return KeyInfoT::getEmptyKey();
427 49775737 : }
428 32263504 :
429 5800370 : static const KeyT getTombstoneKey() {
430 15497954 : return KeyInfoT::getTombstoneKey();
431 21246352 : }
432 104777204 :
433 111558105 : private:
434 22645526 : iterator makeIterator(BucketT *P, BucketT *E,
435 433529523 : DebugEpochBase &Epoch,
436 447004327 : bool NoAdvance=false) {
437 47643368 : if (shouldReverseIterate<KeyT>()) {
438 145101654 : BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
439 161446628 : return iterator(B, E, Epoch, NoAdvance);
440 91815745 : }
441 108127135 : return iterator(P, E, Epoch, NoAdvance);
442 112564940 : }
443 212318523 :
444 36778201 : const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
445 33714411 : const DebugEpochBase &Epoch,
446 26802242 : const bool NoAdvance=false) const {
447 33548901 : if (shouldReverseIterate<KeyT>()) {
448 607399311 : const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
449 591902847 : return const_iterator(B, E, Epoch, NoAdvance);
450 114362648 : }
451 107998594 : return const_iterator(P, E, Epoch, NoAdvance);
452 13830859 : }
453 119421343 :
454 114789971 : unsigned getNumEntries() const {
455 229683871 : return static_cast<const DerivedT *>(this)->getNumEntries();
456 24218771 : }
457 26379066 :
458 17509973 : void setNumEntries(unsigned Num) {
459 6966855 : static_cast<DerivedT *>(this)->setNumEntries(Num);
460 77933831 : }
461 92766889 :
462 8534084 : void incrementNumEntries() {
463 399801941 : setNumEntries(getNumEntries() + 1);
464 70683513 : }
465 70452457 :
466 395301234 : void decrementNumEntries() {
467 866221935 : setNumEntries(getNumEntries() - 1);
468 526926530 : }
469 42218302 :
470 37276412 : unsigned getNumTombstones() const {
471 228127658 : return static_cast<const DerivedT *>(this)->getNumTombstones();
472 192645959 : }
473 63312280 :
474 114126471 : void setNumTombstones(unsigned Num) {
475 26936442 : static_cast<DerivedT *>(this)->setNumTombstones(Num);
476 10785655 : }
477 17481475 :
478 217191067 : void incrementNumTombstones() {
479 237290355 : setNumTombstones(getNumTombstones() + 1);
480 61124367 : }
481 36944256 :
482 5354055 : void decrementNumTombstones() {
483 11427325 : setNumTombstones(getNumTombstones() - 1);
484 13444326 : }
485 14355837 :
486 11146497 : const BucketT *getBuckets() const {
487 1091741615 : return static_cast<const DerivedT *>(this)->getBuckets();
488 145586233 : }
489 252131492 :
490 238786479 : BucketT *getBuckets() {
491 550711041 : return static_cast<DerivedT *>(this)->getBuckets();
492 23156148 : }
493 145430756 :
494 139356315 : unsigned getNumBuckets() const {
495 1528117153 : return static_cast<const DerivedT *>(this)->getNumBuckets();
496 24616723 : }
497 36233661 :
498 30727479 : BucketT *getBucketsEnd() {
499 3146798559 : return getBuckets() + getNumBuckets();
500 287639859 : }
501 298652194 :
502 5481976 : const BucketT *getBucketsEnd() const {
503 223741249 : return getBuckets() + getNumBuckets();
504 48590389 : }
505 47726463 :
506 75788668 : void grow(unsigned AtLeast) {
507 161442739 : static_cast<DerivedT *>(this)->grow(AtLeast);
508 68507567 : }
509 307875635 :
510 441401 : void shrink_and_clear() {
511 269219842 : static_cast<DerivedT *>(this)->shrink_and_clear();
512 94405031 : }
513 10141818 :
514 31820300 : template <typename KeyArg, typename... ValueArgs>
515 251051784 : BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
516 342730271 : ValueArgs &&... Values) {
517 252040219 : TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
518 20862631 :
519 187690610 : TheBucket->getFirst() = std::forward<KeyArg>(Key);
520 181372051 : ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
521 128672462 : return TheBucket;
522 139794614 : }
523 129857768 :
524 82658982 : template <typename LookupKeyT>
525 59033051 : BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
526 29293438 : ValueT &&Value, LookupKeyT &Lookup) {
527 31874564 : TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
528 70337738 :
529 1331038211 : TheBucket->getFirst() = std::move(Key);
530 148605262 : ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
531 1283021235 : return TheBucket;
532 185252552 : }
533 82093840 :
534 49634473 : template <typename LookupKeyT>
535 274813476 : BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
536 116614619 : BucketT *TheBucket) {
537 154892814 : incrementEpoch();
538 35687959 :
539 39331245 : // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
540 41513956 : // the buckets are empty (meaning that many are filled with tombstones),
541 58041591 : // grow the table.
542 29619103 : //
543 96589442 : // The later case is tricky. For example, if we had one empty bucket with
544 86657102 : // tons of tombstones, failing lookups (e.g. for insertion) would have to
545 9116029 : // probe almost the entire table until it found the empty bucket. If the
546 183684523 : // table completely filled with tombstones, no lookup would ever succeed,
547 21537545 : // causing infinite loops in lookup.
548 253420919 : unsigned NewNumEntries = getNumEntries() + 1;
549 66015008 : unsigned NumBuckets = getNumBuckets();
550 582179786 : if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
551 111170761 : this->grow(NumBuckets * 2);
552 19110301 : LookupBucketFor(Lookup, TheBucket);
553 163964828 : NumBuckets = getNumBuckets();
554 230511645 : } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
555 5874039 : NumBuckets/8)) {
556 5484630 : this->grow(NumBuckets);
557 295454611 : LookupBucketFor(Lookup, TheBucket);
558 17804367 : }
559 38508506 : assert(TheBucket);
560 10209321 :
561 350300588 : // Only update the state after we've grown our bucket space appropriately
562 85043763 : // so that when growing buckets we have self-consistent entry count.
563 101667452 : incrementNumEntries();
564 13907271 :
565 245309263 : // If we are writing over a tombstone, remember this.
566 43034502 : const KeyT EmptyKey = getEmptyKey();
567 286413524 : if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
568 7995193 : decrementNumTombstones();
569 186172535 :
570 248373121 : return TheBucket;
571 1286378165 : }
572 19020919 :
573 1352163985 : /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
574 45159153 : /// FoundBucket. If the bucket contains the key and a value, this returns
575 16814171 : /// true, otherwise it returns a bucket with an empty marker or tombstone and
576 27864976 : /// returns false.
577 501523491 : template<typename LookupKeyT>
578 2604802216 : bool LookupBucketFor(const LookupKeyT &Val,
579 530250987 : const BucketT *&FoundBucket) const {
580 176623456 : const BucketT *BucketsPtr = getBuckets();
581 224989145 : const unsigned NumBuckets = getNumBuckets();
582 36597301 :
583 1901452534 : if (NumBuckets == 0) {
584 84177937 : FoundBucket = nullptr;
585 1156124915 : return false;
586 12910228 : }
587 18065165 :
588 5257691 : // FoundTombstone - Keep track of whether we find a tombstone while probing.
589 274072176 : const BucketT *FoundTombstone = nullptr;
590 4275103947 : const KeyT EmptyKey = getEmptyKey();
591 3982866675 : const KeyT TombstoneKey = getTombstoneKey();
592 65400278 : assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
593 346212376 : !KeyInfoT::isEqual(Val, TombstoneKey) &&
594 96537079 : "Empty/Tombstone value shouldn't be inserted into map!");
595 6701962 :
596 2938161739 : unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
597 15338790 : unsigned ProbeAmt = 1;
598 2385966853 : while (true) {
599 4555242521 : const BucketT *ThisBucket = BucketsPtr + BucketNo;
600 10992935 : // Found Val's bucket? If so, return it.
601 5753354822 : if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
602 986109089 : FoundBucket = ThisBucket;
603 915752820 : return true;
604 15341960 : }
605 44350548 :
606 78109183 : // If we found an empty bucket, the key doesn't exist in the set.
607 201882428 : // Insert it and return the default value.
608 3655542785 : if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
609 290502379 : // If we've already seen a tombstone while probing, fill it in instead
610 128361358 : // of the empty bucket we eventually probed to.
611 1466431218 : FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
612 1472777412 : return false;
613 31448158 : }
614 11336939 :
615 33123741 : // If this is a tombstone, remember it. If Val ends up not in the map, we
616 320141107 : // prefer to return it than something that would require more probing.
617 2668612980 : if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
618 13652320 : !FoundTombstone)
619 153006173 : FoundTombstone = ThisBucket; // Remember the first tombstone found.
620 244264429 :
621 46163758 : // Otherwise, it's a hash collision or a tombstone, continue quadratic
622 21572611 : // probing.
623 2380171564 : BucketNo += ProbeAmt++;
624 2454775874 : BucketNo &= (NumBuckets-1);
625 131078125 : }
626 29859911 : }
627 102722173 :
628 89599778 : template <typename LookupKeyT>
629 44077726 : bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
630 46220304 : const BucketT *ConstFoundBucket;
631 2009966946 : bool Result = const_cast<const DenseMapBase *>(this)
632 152566565 : ->LookupBucketFor(Val, ConstFoundBucket);
633 1927448426 : FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
634 9603297 : return Result;
635 55566800 : }
636 183635632 :
637 154462087 : public:
638 124398187 : /// Return the approximate size (in bytes) of the actual map.
639 83810457 : /// This is just the raw memory used by DenseMap.
640 600671750 : /// If entries are pointers to objects, the size of the referenced objects
641 232832492 : /// are not included.
642 14545832 : size_t getMemorySize() const {
643 88587425 : return getNumBuckets() * sizeof(BucketT);
644 118655515 : }
645 142403829 : };
646 19461100 :
647 152772019 : /// Equality comparison for DenseMap.
648 213732476 : ///
649 54847580 : /// Iterates over elements of LHS confirming that each (key, value) pair in LHS
650 122575313 : /// is also in RHS, and that no additional pairs are in RHS.
651 16851281 : /// Equivalent to N calls to RHS.find and N value comparisons. Amortized
652 36250132 : /// complexity is linear, worst case is O(N^2) (if every hash collides).
653 22511995 : template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
654 27582710 : typename BucketT>
655 148821320 : bool operator==(
656 417174046 : const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
657 1504661048 : const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
658 25665002 : if (LHS.size() != RHS.size())
659 54424022 : return false;
660 492718701 :
661 108129724 : for (auto &KV : LHS) {
662 112634330 : auto I = RHS.find(KV.first);
663 17315045 : if (I == RHS.end() || I->second != KV.second)
664 834364237 : return false;
665 105361254 : }
666 27240220 :
667 6102695 : return true;
668 250579590 : }
669 12095726 :
670 12864258 : /// Inequality comparison for DenseMap.
671 10564652 : ///
672 91627596 : /// Equivalent to !(LHS == RHS). See operator== for performance notes.
673 221358399 : template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
674 35414456 : typename BucketT>
675 181127090 : bool operator!=(
676 152982568 : const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
677 115317744 : const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
678 29748206 : return !(LHS == RHS);
679 364452476 : }
680 389205119 :
681 231000669 : template <typename KeyT, typename ValueT,
682 126902551 : typename KeyInfoT = DenseMapInfo<KeyT>,
683 68227006 : typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
684 87565231 : class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
685 66668869 : KeyT, ValueT, KeyInfoT, BucketT> {
686 325445462 : friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
687 24393623 :
688 43792291 : // Lift some types from the dependent base class into this class for
689 181502436 : // simplicity of referring to them.
690 7707064 : using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
691 29127321 :
692 43473508 : BucketT *Buckets;
693 19036546 : unsigned NumEntries;
694 254607391 : unsigned NumTombstones;
695 24001994 : unsigned NumBuckets;
696 13052177 :
697 135621636 : public:
698 80514598 : /// Create a DenseMap wth an optional \p InitialReserve that guarantee that
699 40809108 : /// this number of elements can be inserted in the map without grow()
700 47099328 : explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }
701 45093406 :
702 211231760 : DenseMap(const DenseMap &other) : BaseT() {
703 23020879 : init(0);
704 64330728 : copyFrom(other);
705 44333685 : }
706 118674726 :
707 49040050 : DenseMap(DenseMap &&other) : BaseT() {
708 15832948 : init(0);
709 13746225 : swap(other);
710 153062706 : }
711 63384942 :
712 159229226 : template<typename InputIt>
713 183781043 : DenseMap(const InputIt &I, const InputIt &E) {
714 73702257 : init(std::distance(I, E));
715 37718550 : this->insert(I, E);
716 35272879 : }
717 137022323 :
718 125591312 : DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
719 28503956 : init(Vals.size());
720 197148157 : this->insert(Vals.begin(), Vals.end());
721 20960771 : }
722 226131831 :
723 14578589 : ~DenseMap() {
724 75900535 : this->destroyAll();
725 222205413 : operator delete(Buckets);
726 240574905 : }
727 158984923 :
728 36605537 : void swap(DenseMap& RHS) {
729 235914610 : this->incrementEpoch();
730 121147410 : RHS.incrementEpoch();
731 136884542 : std::swap(Buckets, RHS.Buckets);
732 87937868 : std::swap(NumEntries, RHS.NumEntries);
733 164443790 : std::swap(NumTombstones, RHS.NumTombstones);
734 15495263 : std::swap(NumBuckets, RHS.NumBuckets);
735 163572193 : }
736 10036114 :
737 294408991 : DenseMap& operator=(const DenseMap& other) {
738 59595771 : if (&other != this)
739 231745443 : copyFrom(other);
740 494499427 : return *this;
741 135259950 : }
742 642260449 :
743 430289962 : DenseMap& operator=(DenseMap &&other) {
744 104027517 : this->destroyAll();
745 546931702 : operator delete(Buckets);
746 209717506 : init(0);
747 628312833 : swap(other);
748 333857576 : return *this;
749 51034629 : }
750 98488763 :
751 64770694 : void copyFrom(const DenseMap& other) {
752 279101889 : this->destroyAll();
753 25925905 : operator delete(Buckets);
754 10321138 : if (allocateBuckets(other.NumBuckets)) {
755 181254681 : this->BaseT::copyFrom(other);
756 133096932 : } else {
757 75590307 : NumEntries = 0;
758 61062254 : NumTombstones = 0;
759 108575496 : }
760 946650330 : }
761 255944395 :
762 734361279 : void init(unsigned InitNumEntries) {
763 1197152740 : auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
764 94887365 : if (allocateBuckets(InitBuckets)) {
765 2288582510 : this->BaseT::initEmpty();
766 504963002 : } else {
767 612387419 : NumEntries = 0;
768 265706085 : NumTombstones = 0;
769 295476294 : }
770 203754727 : }
771 56340873 :
772 850987972 : void grow(unsigned AtLeast) {
773 111049181 : unsigned OldNumBuckets = NumBuckets;
774 191546099 : BucketT *OldBuckets = Buckets;
775 176604462 :
776 271904039 : allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1))));
777 88270522 : assert(Buckets);
778 30570959 : if (!OldBuckets) {
779 269479459 : this->BaseT::initEmpty();
780 33467603 : return;
781 825927593 : }
782 25072778 :
783 21882739 : this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
784 77734500 :
785 294637127 : // Free the old table.
786 151912607 : operator delete(OldBuckets);
787 742731034 : }
788 721899407 :
789 280832853 : void shrink_and_clear() {
790 61745896 : unsigned OldNumEntries = NumEntries;
791 315790003 : this->destroyAll();
792 351084790 :
793 53741154 : // Reduce the number of buckets.
794 65818281 : unsigned NewNumBuckets = 0;
795 249486574 : if (OldNumEntries)
796 371105484 : NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
797 605710803 : if (NewNumBuckets == NumBuckets) {
798 140959165 : this->BaseT::initEmpty();
799 111959015 : return;
800 108815217 : }
801 145473444 :
802 27430375 : operator delete(Buckets);
803 57018344 : init(NewNumBuckets);
804 140839505 : }
805 93727045 :
806 28471728 : private:
807 177704208 : unsigned getNumEntries() const {
808 174890958 : return NumEntries;
809 568188500 : }
810 114358957 :
811 599116865 : void setNumEntries(unsigned Num) {
812 1061882891 : NumEntries = Num;
813 68601979 : }
814 1897861435 :
815 256054005 : unsigned getNumTombstones() const {
816 240286527 : return NumTombstones;
817 151744706 : }
818 60466402 :
819 169627044 : void setNumTombstones(unsigned Num) {
820 111947747 : NumTombstones = Num;
821 784665463 : }
822 133415275 :
823 71400215 : BucketT *getBuckets() const {
824 200651198 : return Buckets;
825 281130303 : }
826 115992379 :
827 29231772 : unsigned getNumBuckets() const {
828 100457234 : return NumBuckets;
829 71597280 : }
830 749207635 :
831 142580802 : bool allocateBuckets(unsigned Num) {
832 139651129 : NumBuckets = Num;
833 28791676 : if (NumBuckets == 0) {
834 69013457 : Buckets = nullptr;
835 98729102 : return false;
836 667373080 : }
837 713270197 :
838 89611924 : Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
839 22052240 : return true;
840 381345991 : }
841 197576835 : };
842 199176246 :
843 75945542 : template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
844 175936335 : typename KeyInfoT = DenseMapInfo<KeyT>,
845 352371608 : typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
846 175363954 : class SmallDenseMap
847 272841568 : : public DenseMapBase<
848 90627454 : SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
849 140884616 : ValueT, KeyInfoT, BucketT> {
850 183831899 : friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
851 418073516 :
852 232239218 : // Lift some types from the dependent base class into this class for
853 140360526 : // simplicity of referring to them.
854 117327995 : using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
855 67464922 :
856 93521963 : static_assert(isPowerOf2_64(InlineBuckets),
857 47483018 : "InlineBuckets must be a power of 2.");
858 498878012 :
859 537616220 : unsigned Small : 1;
860 296650223 : unsigned NumEntries : 31;
861 632552169 : unsigned NumTombstones;
862 82834200 :
863 740512234 : struct LargeRep {
864 289213574 : BucketT *Buckets;
865 424061251 : unsigned NumBuckets;
866 262598419 : };
867 109386329 :
868 99471593 : /// A "union" of an inline bucket array and the struct representing
869 645178636 : /// a large bucket. This union will be discriminated by the 'Small' bit.
870 179989829 : AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;
871 125885237 :
872 146660131 : public:
873 262294024 : explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
874 688754164 : init(NumInitBuckets);
875 84473762 : }
876 55635243 :
877 261183988 : SmallDenseMap(const SmallDenseMap &other) : BaseT() {
878 36551608 : init(0);
879 696346065 : copyFrom(other);
880 43793592 : }
881 82574851 :
882 147442460 : SmallDenseMap(SmallDenseMap &&other) : BaseT() {
883 11896966 : init(0);
884 168939738 : swap(other);
885 194871704 : }
886 236562615 :
887 328610265 : template<typename InputIt>
888 56498318 : SmallDenseMap(const InputIt &I, const InputIt &E) {
889 120729041 : init(NextPowerOf2(std::distance(I, E)));
890 627277824 : this->insert(I, E);
891 116769794 : }
892 1408720875 :
893 1033784831 : ~SmallDenseMap() {
894 425500216 : this->destroyAll();
895 1381534396 : deallocateBuckets();
896 218995497 : }
897 1244841264 :
898 409070436 : void swap(SmallDenseMap& RHS) {
899 519312241 : unsigned TmpNumEntries = RHS.NumEntries;
900 74186688 : RHS.NumEntries = NumEntries;
901 158423024 : NumEntries = TmpNumEntries;
902 156280959 : std::swap(NumTombstones, RHS.NumTombstones);
903 104586825 :
904 353075297 : const KeyT EmptyKey = this->getEmptyKey();
905 258555727 : const KeyT TombstoneKey = this->getTombstoneKey();
906 143098576 : if (Small && RHS.Small) {
907 197706755 : // If we're swapping inline bucket arrays, we have to cope with some of
908 328573468 : // the tricky bits of DenseMap's storage system: the buckets are not
909 126239932 : // fully initialized. Thus we swap every key, but we may have
910 78012703 : // a one-directional move of the value.
911 281589726 : for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
912 136666849 : BucketT *LHSB = &getInlineBuckets()[i],
913 246247419 : *RHSB = &RHS.getInlineBuckets()[i];
914 316103651 : bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
915 228004039 : !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
916 387228105 : bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
917 268189514 : !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
918 210726830 : if (hasLHSValue && hasRHSValue) {
919 230225026 : // Swap together if we can...
920 447514044 : std::swap(*LHSB, *RHSB);
921 185839097 : continue;
922 168774596 : }
923 145203000 : // Swap separately and handle any assymetry.
924 183330351 : std::swap(LHSB->getFirst(), RHSB->getFirst());
925 1238786801 : if (hasLHSValue) {
926 49288991 : ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
927 140628166 : LHSB->getSecond().~ValueT();
928 194591968 : } else if (hasRHSValue) {
929 1722085618 : ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
930 61570105 : RHSB->getSecond().~ValueT();
931 26215679 : }
932 56397557 : }
933 45329538 : return;
934 23641383 : }
935 15384302 : if (!Small && !RHS.Small) {
936 43620613 : std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets);
937 1714549537 : std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets);
938 388308167 : return;
939 114340796 : }
940 414075050 :
941 668493045 : SmallDenseMap &SmallSide = Small ? *this : RHS;
942 106438144 : SmallDenseMap &LargeSide = Small ? RHS : *this;
943 835793448 :
944 177279849 : // First stash the large side's rep and move the small side across.
945 298947365 : LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
946 123702910 : LargeSide.getLargeRep()->~LargeRep();
947 198589024 : LargeSide.Small = true;
948 73052022 : // This is similar to the standard move-from-old-buckets, but the bucket
949 49385469 : // count hasn't actually rotated in this case. So we have to carefully
950 439583398 : // move construct the keys and values into their new locations, but there
951 14365816 : // is no need to re-hash things.
952 58343573 : for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
953 184626868 : BucketT *NewB = &LargeSide.getInlineBuckets()[i],
954 248729798 : *OldB = &SmallSide.getInlineBuckets()[i];
955 119681352 : ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
956 45105219 : OldB->getFirst().~KeyT();
957 149876606 : if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
958 142848843 : !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
959 180295137 : ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
960 153350997 : OldB->getSecond().~ValueT();
961 58857500 : }
962 29850466 : }
963 169748867 :
964 12288851 : // The hard part of moving the small buckets across is done, just move
965 333416189 : // the TmpRep into its new home.
966 327417729 : SmallSide.Small = false;
967 47609623 : new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
968 36030763 : }
969 231396324 :
970 223419264 : SmallDenseMap& operator=(const SmallDenseMap& other) {
971 210989334 : if (&other != this)
972 79040353 : copyFrom(other);
973 140966777 : return *this;
974 16547020 : }
975 81892539 :
976 146001766 : SmallDenseMap& operator=(SmallDenseMap &&other) {
977 66564689 : this->destroyAll();
978 70846268 : deallocateBuckets();
979 84449723 : init(0);
980 16518891 : swap(other);
981 20569805 : return *this;
982 55010535 : }
983 188663399 :
984 236252444 : void copyFrom(const SmallDenseMap& other) {
985 10090620 : this->destroyAll();
986 109709584 : deallocateBuckets();
987 108710433 : Small = true;
988 108361227 : if (other.getNumBuckets() > InlineBuckets) {
989 336061818 : Small = false;
990 80740953 : new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
991 150438089 : }
992 309835114 : this->BaseT::copyFrom(other);
993 51262354 : }
994 367908593 :
995 316707126 : void init(unsigned InitBuckets) {
996 225367781 : Small = true;
997 68696241 : if (InitBuckets > InlineBuckets) {
998 45911469 : Small = false;
999 72124942 : new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
1000 57917019 : }
1001 222905202 : this->BaseT::initEmpty();
1002 60173662 : }
1003 197979093 :
1004 91829147 : void grow(unsigned AtLeast) {
1005 246575459 : if (AtLeast >= InlineBuckets)
1006 149638673 : AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1));
1007 95610374 :
1008 153680582 : if (Small) {
1009 169371832 : if (AtLeast < InlineBuckets)
1010 87849891 : return; // Nothing to do.
1011 107085751 :
1012 131456951 : // First move the inline buckets into a temporary storage.
1013 120286192 : AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;
1014 181151715 : BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer);
1015 66011966 : BucketT *TmpEnd = TmpBegin;
1016 138069727 :
1017 69945417 : // Loop over the buckets, moving non-empty, non-tombstones into the
1018 43319048 : // temporary storage. Have the loop move the TmpEnd forward as it goes.
1019 215695253 : const KeyT EmptyKey = this->getEmptyKey();
1020 43818488 : const KeyT TombstoneKey = this->getTombstoneKey();
1021 498713957 : for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
1022 162985871 : if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
1023 12414941 : !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
1024 311736740 : assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&
1025 84798722 : "Too many inline buckets!");
1026 617782030 : ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
1027 43814414 : ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
1028 57166214 : ++TmpEnd;
1029 147905672 : P->getSecond().~ValueT();
1030 51469377 : }
1031 204788776 : P->getFirst().~KeyT();
1032 108463188 : }
1033 61629698 :
1034 136674622 : // Now make this map use the large rep, and move all the entries back
1035 88928530 : // into it.
1036 48944430 : Small = false;
1037 34699071 : new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1038 145758452 : this->moveFromOldBuckets(TmpBegin, TmpEnd);
1039 758323651 : return;
1040 314478466 : }
1041 761024132 :
1042 598818445 : LargeRep OldRep = std::move(*getLargeRep());
1043 111801262 : getLargeRep()->~LargeRep();
1044 1058591564 : if (AtLeast <= InlineBuckets) {
1045 488850201 : Small = true;
1046 353637549 : } else {
1047 167601332 : new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1048 17489372 : }
1049 17542387 :
1050 52958408 : this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
1051 316815364 :
1052 28247896 : // Free the old table.
1053 117513182 : operator delete(OldRep.Buckets);
1054 219108150 : }
1055 162423648 :
1056 60596938 : void shrink_and_clear() {
1057 269645302 : unsigned OldSize = this->size();
1058 733860900 : this->destroyAll();
1059 57510412 :
1060 258031045 : // Reduce the number of buckets.
1061 229348434 : unsigned NewNumBuckets = 0;
1062 167303936 : if (OldSize) {
1063 432856472 : NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1);
1064 42888969 : if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
1065 78763124 : NewNumBuckets = 64;
1066 240597959 : }
1067 365349720 : if ((Small && NewNumBuckets <= InlineBuckets) ||
1068 102568981 : (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
1069 132309986 : this->BaseT::initEmpty();
1070 218996202 : return;
1071 42849363 : }
1072 124686882 :
1073 239434295 : deallocateBuckets();
1074 250764546 : init(NewNumBuckets);
1075 58282862 : }
1076 98213283 :
1077 811642565 : private:
1078 110039052 : unsigned getNumEntries() const {
1079 132399900 : return NumEntries;
1080 133273246 : }
1081 33170370 :
1082 200955783 : void setNumEntries(unsigned Num) {
1083 83977647 : // NumEntries is hardcoded to be 31 bits wide.
1084 21811972 : assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries");
1085 430477147 : NumEntries = Num;
1086 96916197 : }
1087 528689153 :
1088 498061822 : unsigned getNumTombstones() const {
1089 136112106 : return NumTombstones;
1090 465230462 : }
1091 104440453 :
1092 202876209 : void setNumTombstones(unsigned Num) {
1093 128791134 : NumTombstones = Num;
1094 103967443 : }
1095 599178170 :
1096 18183201 : const BucketT *getInlineBuckets() const {
1097 322639534 : assert(Small);
1098 145652133 : // Note that this cast does not violate aliasing rules as we assert that
1099 57112204 : // the memory's dynamic type is the small, inline bucket buffer, and the
1100 264408978 : // 'storage.buffer' static type is 'char *'.
1101 1062583001 : return reinterpret_cast<const BucketT *>(storage.buffer);
1102 21239717 : }
1103 30529541 :
1104 41478771 : BucketT *getInlineBuckets() {
1105 189957739 : return const_cast<BucketT *>(
1106 400530730 : const_cast<const SmallDenseMap *>(this)->getInlineBuckets());
1107 342982783 : }
1108 56452014 :
1109 37894293 : const LargeRep *getLargeRep() const {
1110 179133428 : assert(!Small);
1111 155698648 : // Note, same rule about aliasing as with getInlineBuckets.
1112 689938783 : return reinterpret_cast<const LargeRep *>(storage.buffer);
1113 727009094 : }
1114 24167395 :
1115 77728055 : LargeRep *getLargeRep() {
1116 124687036 : return const_cast<LargeRep *>(
1117 177062694 : const_cast<const SmallDenseMap *>(this)->getLargeRep());
1118 130203393 : }
1119 64511791 :
1120 20443330 : const BucketT *getBuckets() const {
1121 3926057932 : return Small ? getInlineBuckets() : getLargeRep()->Buckets;
1122 58433972 : }
1123 611396981 :
1124 245762464 : BucketT *getBuckets() {
1125 445490844 : return const_cast<BucketT *>(
1126 81076337 : const_cast<const SmallDenseMap *>(this)->getBuckets());
1127 208100876 : }
1128 107652385 :
1129 531554373 : unsigned getNumBuckets() const {
1130 4075780620 : return Small ? InlineBuckets : getLargeRep()->NumBuckets;
1131 108360020 : }
1132 203184279 :
1133 21040565 : void deallocateBuckets() {
1134 235793740 : if (Small)
1135 25231951 : return;
1136 331153115 :
1137 325099535 : operator delete(getLargeRep()->Buckets);
1138 103472952 : getLargeRep()->~LargeRep();
1139 590313064 : }
1140 98630771 :
1141 385746844 : LargeRep allocateBuckets(unsigned Num) {
1142 101491198 : assert(Num > InlineBuckets && "Must allocate more buckets than are inline");
1143 151805636 : LargeRep Rep = {
1144 154334615 : static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num
1145 114490426 : };
1146 333839304 : return Rep;
1147 60224190 : }
1148 119254746 : };
1149 132458222 :
1150 105770356 : template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
1151 149640289 : bool IsConst>
1152 169074168 : class DenseMapIterator : DebugEpochBase::HandleBase {
1153 513594715 : friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
1154 17073035 : friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;
1155 58220414 :
1156 137622261 : using ConstIterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
1157 100884668 :
1158 109803664 : public:
1159 84038943 : using difference_type = ptrdiff_t;
1160 8569658 : using value_type =
1161 141528877 : typename std::conditional<IsConst, const Bucket, Bucket>::type;
1162 161983236 : using pointer = value_type *;
1163 106532412 : using reference = value_type &;
1164 61741976 : using iterator_category = std::forward_iterator_tag;
1165 49089435 :
1166 428782169 : private:
1167 49915452 : pointer Ptr = nullptr;
1168 502846848 : pointer End = nullptr;
1169 233401315 :
1170 8266301 : public:
1171 218833309 : DenseMapIterator() = default;
1172 444189554 :
1173 16149306 : DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
1174 23595184 : bool NoAdvance = false)
1175 64260137 : : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
1176 23906260 : assert(isHandleInSync() && "invalid construction!");
1177 23861011 :
1178 21648466 : if (NoAdvance) return;
1179 37453579 : if (shouldReverseIterate<KeyT>()) {
1180 51252833 : RetreatPastEmptyBuckets();
1181 43928509 : return;
1182 29623095 : }
1183 74651290 : AdvancePastEmptyBuckets();
1184 59561981 : }
1185 456826754 :
1186 34871522 : // Converting ctor from non-const iterators to const iterators. SFINAE'd out
1187 187686696 : // for const iterator destinations so it doesn't end up as a user defined copy
1188 427684231 : // constructor.
1189 89804361 : template <bool IsConstSrc,
1190 15739754 : typename = typename std::enable_if<!IsConstSrc && IsConst>::type>
1191 108550570 : DenseMapIterator(
1192 198149590 : const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
1193 209145872 : : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}
1194 34936883 :
1195 69349425 : reference operator*() const {
1196 72786126 : assert(isHandleInSync() && "invalid iterator access!");
1197 148586960 : if (shouldReverseIterate<KeyT>())
1198 107916250 : return Ptr[-1];
1199 31127405 : return *Ptr;
1200 52088351 : }
1201 3836026 : pointer operator->() const {
1202 181522936 : assert(isHandleInSync() && "invalid iterator access!");
1203 151700821 : if (shouldReverseIterate<KeyT>())
1204 215564559 : return &(Ptr[-1]);
1205 406143280 : return Ptr;
1206 27232344 : }
1207 69086057 :
1208 227603785 : bool operator==(const ConstIterator &RHS) const {
1209 189359571 : assert((!Ptr || isHandleInSync()) && "handle not in sync!");
1210 285681348 : assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
1211 344080422 : assert(getEpochAddress() == RHS.getEpochAddress() &&
1212 41040010 : "comparing incomparable iterators!");
1213 77561459 : return Ptr == RHS.Ptr;
1214 43657544 : }
1215 85853644 : bool operator!=(const ConstIterator &RHS) const {
1216 32946151 : assert((!Ptr || isHandleInSync()) && "handle not in sync!");
1217 147696104 : assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
1218 158101642 : assert(getEpochAddress() == RHS.getEpochAddress() &&
1219 50453131 : "comparing incomparable iterators!");
1220 442323465 : return Ptr != RHS.Ptr;
1221 183276149 : }
1222 391359651 :
1223 114980793 : inline DenseMapIterator& operator++() { // Preincrement
1224 131175016 : assert(isHandleInSync() && "invalid iterator access!");
1225 295753447 : if (shouldReverseIterate<KeyT>()) {
1226 162677255 : --Ptr;
1227 350608361 : RetreatPastEmptyBuckets();
1228 226531637 : return *this;
1229 226554993 : }
1230 86347468 : ++Ptr;
1231 394702478 : AdvancePastEmptyBuckets();
1232 69288981 : return *this;
1233 22955058 : }
1234 190894129 : DenseMapIterator operator++(int) { // Postincrement
1235 55441025 : assert(isHandleInSync() && "invalid iterator access!");
1236 179744436 : DenseMapIterator tmp = *this; ++*this; return tmp;
1237 146818506 : }
1238 226982539 :
1239 124528325 : private:
1240 406916748 : void AdvancePastEmptyBuckets() {
1241 178275283 : assert(Ptr <= End);
1242 57891684 : const KeyT Empty = KeyInfoT::getEmptyKey();
1243 132785651 : const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1244 545834887 :
1245 442770096 : while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
1246 109649167 : KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
1247 85469611 : ++Ptr;
1248 313534793 : }
1249 79726090 :
1250 68432813 : void RetreatPastEmptyBuckets() {
1251 101271093 : assert(Ptr >= End);
1252 117932560 : const KeyT Empty = KeyInfoT::getEmptyKey();
1253 250714845 : const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1254 88866424 :
1255 90728932 : while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
1256 22561200 : KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
1257 144573607 : --Ptr;
1258 60104288 : }
1259 514182045 : };
1260 25807478 :
1261 272308204 : template <typename KeyT, typename ValueT, typename KeyInfoT>
1262 163422508 : inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
1263 148249104 : return X.getMemorySize();
1264 284173746 : }
1265 36379395 :
1266 450210822 : } // end namespace llvm
1267 96550246 :
1268 78578973 : #endif // LLVM_ADT_DENSEMAP_H
|
