Branch data 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 : 0 : KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
46 : : const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
47 : 0 : 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 : 0 : std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) {
261 : : BucketT *TheBucket;
262 [ # # # # ]: 0 : 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 [ # # ]: 0 : TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
272 [ # # # # : 0 : return std::make_pair(makeIterator(TheBucket,
# # ]
273 : 0 : shouldReverseIterate<KeyT>()
274 [ # # ]: 0 : ? getBuckets()
275 [ # # ]: 0 : : getBucketsEnd(),
276 : : *this, true),
277 : 0 : 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 : 0 : void destroyAll() {
404 [ # # # # ]: 0 : if (getNumBuckets() == 0) // Nothing to do.
405 : 0 : return;
406 : :
407 : 0 : const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
408 [ # # # # : 0 : for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
# # ]
409 [ # # # # ]: 0 : if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
410 [ # # ]: 0 : !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
411 : 0 : P->getSecond().~ValueT();
412 : 0 : P->getFirst().~KeyT();
413 : : }
414 : : }
415 : :
416 : 0 : void initEmpty() {
417 : 0 : setNumEntries(0);
418 : 0 : setNumTombstones(0);
419 : :
420 [ # # ]: 0 : assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
421 : : "# initial buckets must be a power of two!");
422 : 0 : const KeyT EmptyKey = getEmptyKey();
423 [ # # ]: 0 : for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
424 [ # # ]: 0 : ::new (&B->getFirst()) KeyT(EmptyKey);
425 : 0 : }
426 : :
427 : : /// Returns the number of buckets to allocate to ensure that the DenseMap can
428 : : /// accommodate \p NumEntries without need to grow().
429 : 0 : unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
430 : : // Ensure that "NumEntries * 4 < NumBuckets * 3"
431 [ # # ]: 0 : if (NumEntries == 0)
432 : 0 : 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 : 0 : static unsigned getHashValue(const KeyT &Val) {
488 : 0 : 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 : 0 : static const KeyT getEmptyKey() {
497 : : static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
498 : : "Must pass the derived type to this template!");
499 : 0 : return KeyInfoT::getEmptyKey();
500 : : }
501 : :
502 : 0 : static const KeyT getTombstoneKey() {
503 : 0 : return KeyInfoT::getTombstoneKey();
504 : : }
505 : :
506 : : private:
507 : 0 : iterator makeIterator(BucketT *P, BucketT *E,
508 : : DebugEpochBase &Epoch,
509 : : bool NoAdvance=false) {
510 [ # # ]: 0 : if (shouldReverseIterate<KeyT>()) {
511 [ # # ]: 0 : BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
512 [ # # ]: 0 : return iterator(B, E, Epoch, NoAdvance);
513 : : }
514 [ # # ]: 0 : 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 : 0 : unsigned getNumEntries() const {
528 : 0 : return static_cast<const DerivedT *>(this)->getNumEntries();
529 : : }
530 : :
531 : 0 : void setNumEntries(unsigned Num) {
532 : 0 : static_cast<DerivedT *>(this)->setNumEntries(Num);
533 : 0 : }
534 : :
535 : 0 : void incrementNumEntries() {
536 : 0 : setNumEntries(getNumEntries() + 1);
537 : 0 : }
538 : :
539 : : void decrementNumEntries() {
540 : : setNumEntries(getNumEntries() - 1);
541 : : }
542 : :
543 : 0 : unsigned getNumTombstones() const {
544 : 0 : return static_cast<const DerivedT *>(this)->getNumTombstones();
545 : : }
546 : :
547 : 0 : void setNumTombstones(unsigned Num) {
548 : 0 : static_cast<DerivedT *>(this)->setNumTombstones(Num);
549 : 0 : }
550 : :
551 : : void incrementNumTombstones() {
552 : : setNumTombstones(getNumTombstones() + 1);
553 : : }
554 : :
555 : 0 : void decrementNumTombstones() {
556 : 0 : setNumTombstones(getNumTombstones() - 1);
557 : 0 : }
558 : :
559 : 0 : const BucketT *getBuckets() const {
560 : 0 : return static_cast<const DerivedT *>(this)->getBuckets();
561 : : }
562 : :
563 : 0 : BucketT *getBuckets() {
564 : 0 : return static_cast<DerivedT *>(this)->getBuckets();
565 : : }
566 : :
567 : 0 : unsigned getNumBuckets() const {
568 : 0 : return static_cast<const DerivedT *>(this)->getNumBuckets();
569 : : }
570 : :
571 : 0 : BucketT *getBucketsEnd() {
572 : 0 : return getBuckets() + getNumBuckets();
573 : : }
574 : :
575 : : const BucketT *getBucketsEnd() const {
576 : : return getBuckets() + getNumBuckets();
577 : : }
578 : :
579 : 0 : void grow(unsigned AtLeast) {
580 : 0 : static_cast<DerivedT *>(this)->grow(AtLeast);
581 : 0 : }
582 : :
583 : : void shrink_and_clear() {
584 : : static_cast<DerivedT *>(this)->shrink_and_clear();
585 : : }
586 : :
587 : : template <typename KeyArg, typename... ValueArgs>
588 : 0 : BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
589 : : ValueArgs &&... Values) {
590 : 0 : TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
591 : :
592 : 0 : TheBucket->getFirst() = std::forward<KeyArg>(Key);
593 [ # # ]: 0 : ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
594 : 0 : 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 : 0 : BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
609 : : BucketT *TheBucket) {
610 : 0 : 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 : 0 : unsigned NewNumEntries = getNumEntries() + 1;
622 : 0 : unsigned NumBuckets = getNumBuckets();
623 [ # # ]: 0 : if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
624 : 0 : this->grow(NumBuckets * 2);
625 : 0 : LookupBucketFor(Lookup, TheBucket);
626 : 0 : NumBuckets = getNumBuckets();
627 [ # # ]: 0 : } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
628 : : NumBuckets/8)) {
629 : 0 : this->grow(NumBuckets);
630 : 0 : LookupBucketFor(Lookup, TheBucket);
631 : : }
632 [ # # ]: 0 : 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 : 0 : incrementNumEntries();
637 : :
638 : : // If we are writing over a tombstone, remember this.
639 : 0 : const KeyT EmptyKey = getEmptyKey();
640 [ # # ]: 0 : if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
641 : 0 : decrementNumTombstones();
642 : :
643 : 0 : 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 : 0 : bool LookupBucketFor(const LookupKeyT &Val,
652 : : const BucketT *&FoundBucket) const {
653 : 0 : const BucketT *BucketsPtr = getBuckets();
654 : 0 : const unsigned NumBuckets = getNumBuckets();
655 : :
656 [ # # ]: 0 : if (NumBuckets == 0) {
657 : 0 : FoundBucket = nullptr;
658 : 0 : return false;
659 : : }
660 : :
661 : : // FoundTombstone - Keep track of whether we find a tombstone while probing.
662 : 0 : const BucketT *FoundTombstone = nullptr;
663 : 0 : const KeyT EmptyKey = getEmptyKey();
664 : 0 : const KeyT TombstoneKey = getTombstoneKey();
665 [ # # # # ]: 0 : assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
666 : : !KeyInfoT::isEqual(Val, TombstoneKey) &&
667 : : "Empty/Tombstone value shouldn't be inserted into map!");
668 : :
669 : 0 : unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
670 : 0 : unsigned ProbeAmt = 1;
671 : 0 : while (true) {
672 : 0 : const BucketT *ThisBucket = BucketsPtr + BucketNo;
673 : : // Found Val's bucket? If so, return it.
674 [ # # ]: 0 : 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 [ # # ]: 0 : 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 [ # # ]: 0 : FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
685 : 0 : 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 [ # # # # : 0 : 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 : 0 : BucketNo += ProbeAmt++;
697 : 0 : BucketNo &= (NumBuckets-1);
698 : : }
699 : : }
700 : :
701 : : template <typename LookupKeyT>
702 : 0 : bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
703 : : const BucketT *ConstFoundBucket;
704 : : bool Result = const_cast<const DenseMapBase *>(this)
705 [ # # ]: 0 : ->LookupBucketFor(Val, ConstFoundBucket);
706 : 0 : FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
707 : 0 : 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 : 0 : 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 : 0 : ~DenseMap() {
797 : 0 : this->destroyAll();
798 : 0 : deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
799 : 0 : }
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 : 0 : void init(unsigned InitNumEntries) {
836 : 0 : auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
837 [ # # ]: 0 : if (allocateBuckets(InitBuckets)) {
838 : 0 : this->BaseT::initEmpty();
839 : : } else {
840 : 0 : NumEntries = 0;
841 : 0 : NumTombstones = 0;
842 : : }
843 : 0 : }
844 : :
845 : 0 : void grow(unsigned AtLeast) {
846 : 0 : unsigned OldNumBuckets = NumBuckets;
847 : 0 : BucketT *OldBuckets = Buckets;
848 : :
849 [ # # ]: 0 : allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1))));
850 [ # # ]: 0 : assert(Buckets);
851 [ # # ]: 0 : if (!OldBuckets) {
852 : 0 : this->BaseT::initEmpty();
853 : 0 : 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 : 0 : unsigned getNumEntries() const {
884 : 0 : return NumEntries;
885 : : }
886 : :
887 : 0 : void setNumEntries(unsigned Num) {
888 : 0 : NumEntries = Num;
889 : 0 : }
890 : :
891 : 0 : unsigned getNumTombstones() const {
892 : 0 : return NumTombstones;
893 : : }
894 : :
895 : 0 : void setNumTombstones(unsigned Num) {
896 : 0 : NumTombstones = Num;
897 : 0 : }
898 : :
899 : 0 : BucketT *getBuckets() const {
900 : 0 : return Buckets;
901 : : }
902 : :
903 : 0 : unsigned getNumBuckets() const {
904 : 0 : return NumBuckets;
905 : : }
906 : :
907 : 0 : bool allocateBuckets(unsigned Num) {
908 : 0 : NumBuckets = Num;
909 [ # # ]: 0 : if (NumBuckets == 0) {
910 : 0 : Buckets = nullptr;
911 : 0 : return false;
912 : : }
913 : :
914 : 0 : Buckets = static_cast<BucketT *>(
915 : 0 : allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT)));
916 : 0 : 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 : 0 : DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
1256 : : bool NoAdvance = false)
1257 : 0 : : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
1258 [ # # ]: 0 : assert(isHandleInSync() && "invalid construction!");
1259 : :
1260 [ # # ]: 0 : 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
|
