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