1 //===- sanitizer_dense_map.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 // This is fork of llvm/ADT/DenseMap.h class with the following changes:
10 // * Use mmap to allocate.
11 // * No iterators.
12 // * Does not shrink.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #ifndef SANITIZER_DENSE_MAP_H
17 #define SANITIZER_DENSE_MAP_H
18
19 #include "sanitizer_common.h"
20 #include "sanitizer_dense_map_info.h"
21 #include "sanitizer_internal_defs.h"
22 #include "sanitizer_type_traits.h"
23
24 namespace __sanitizer {
25
26 template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
27 typename BucketT>
28 class DenseMapBase {
29 public:
30 using size_type = unsigned;
31 using key_type = KeyT;
32 using mapped_type = ValueT;
33 using value_type = BucketT;
34
35 WARN_UNUSED_RESULT bool empty() const { return getNumEntries() == 0; }
36 unsigned size() const { return getNumEntries(); }
37
38 /// Grow the densemap so that it can contain at least \p NumEntries items
39 /// before resizing again.
40 void reserve(size_type NumEntries) {
41 auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
42 if (NumBuckets > getNumBuckets())
43 grow(NumBuckets);
44 }
45
46 void clear() {
47 if (getNumEntries() == 0 && getNumTombstones() == 0)
48 return;
49
50 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
51 if (__sanitizer::is_trivially_destructible<ValueT>::value) {
52 // Use a simpler loop when values don't need destruction.
53 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
54 P->getFirst() = EmptyKey;
55 } else {
56 unsigned NumEntries = getNumEntries();
57 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
58 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
59 if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
60 P->getSecond().~ValueT();
61 --NumEntries;
62 }
63 P->getFirst() = EmptyKey;
64 }
65 }
66 CHECK_EQ(NumEntries, 0);
67 }
68 setNumEntries(0);
69 setNumTombstones(0);
70 }
71
72 /// Return 1 if the specified key is in the map, 0 otherwise.
73 size_type count(const KeyT &Key) const {
74 const BucketT *TheBucket;
75 return LookupBucketFor(Key, TheBucket) ? 1 : 0;
76 }
77
78 value_type *find(const KeyT &Key) {
79 BucketT *TheBucket;
80 if (LookupBucketFor(Key, TheBucket))
81 return TheBucket;
82 return nullptr;
83 }
84 const value_type *find(const KeyT &Key) const {
85 const BucketT *TheBucket;
86 if (LookupBucketFor(Key, TheBucket))
87 return TheBucket;
88 return nullptr;
89 }
90
91 /// Alternate version of find() which allows a different, and possibly
92 /// less expensive, key type.
93 /// The DenseMapInfo is responsible for supplying methods
94 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
95 /// type used.
96 template <class LookupKeyT>
97 value_type *find_as(const LookupKeyT &Key) {
98 BucketT *TheBucket;
99 if (LookupBucketFor(Key, TheBucket))
100 return TheBucket;
101 return nullptr;
102 }
103 template <class LookupKeyT>
104 const value_type *find_as(const LookupKeyT &Key) const {
105 const BucketT *TheBucket;
106 if (LookupBucketFor(Key, TheBucket))
107 return TheBucket;
108 return nullptr;
109 }
110
111 /// lookup - Return the entry for the specified key, or a default
112 /// constructed value if no such entry exists.
113 ValueT lookup(const KeyT &Key) const {
114 const BucketT *TheBucket;
115 if (LookupBucketFor(Key, TheBucket))
116 return TheBucket->getSecond();
117 return ValueT();
118 }
119
120 // Inserts key,value pair into the map if the key isn't already in the map.
121 // If the key is already in the map, it returns false and doesn't update the
122 // value.
123 detail::DenseMapPair<value_type *, bool> insert(const value_type &KV) {
124 return try_emplace(KV.first, KV.second);
125 }
126
127 // Inserts key,value pair into the map if the key isn't already in the map.
128 // If the key is already in the map, it returns false and doesn't update the
129 // value.
130 detail::DenseMapPair<value_type *, bool> insert(value_type &&KV) {
131 return try_emplace(__sanitizer::move(KV.first),
132 __sanitizer::move(KV.second));
133 }
134
135 // Inserts key,value pair into the map if the key isn't already in the map.
136 // The value is constructed in-place if the key is not in the map, otherwise
137 // it is not moved.
138 template <typename... Ts>
139 detail::DenseMapPair<value_type *, bool> try_emplace(KeyT &&Key,
140 Ts &&...Args) {
141 BucketT *TheBucket;
142 if (LookupBucketFor(Key, TheBucket))
143 return {TheBucket, false}; // Already in map.
144
145 // Otherwise, insert the new element.
146 TheBucket = InsertIntoBucket(TheBucket, __sanitizer::move(Key),
147 __sanitizer::forward<Ts>(Args)...);
148 return {TheBucket, true};
149 }
150
151 // Inserts key,value pair into the map if the key isn't already in the map.
152 // The value is constructed in-place if the key is not in the map, otherwise
153 // it is not moved.
154 template <typename... Ts>
155 detail::DenseMapPair<value_type *, bool> try_emplace(const KeyT &Key,
156 Ts &&...Args) {
157 BucketT *TheBucket;
158 if (LookupBucketFor(Key, TheBucket))
159 return {TheBucket, false}; // Already in map.
160
161 // Otherwise, insert the new element.
162 TheBucket =
163 InsertIntoBucket(TheBucket, Key, __sanitizer::forward<Ts>(Args)...);
164 return {TheBucket, true};
165 }
166
167 /// Alternate version of insert() which allows a different, and possibly
168 /// less expensive, key type.
169 /// The DenseMapInfo is responsible for supplying methods
170 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
171 /// type used.
172 template <typename LookupKeyT>
173 detail::DenseMapPair<value_type *, bool> insert_as(value_type &&KV,
174 const LookupKeyT &Val) {
175 BucketT *TheBucket;
176 if (LookupBucketFor(Val, TheBucket))
177 return {TheBucket, false}; // Already in map.
178
179 // Otherwise, insert the new element.
180 TheBucket =
181 InsertIntoBucketWithLookup(TheBucket, __sanitizer::move(KV.first),
182 __sanitizer::move(KV.second), Val);
183 return {TheBucket, true};
184 }
185
186 bool erase(const KeyT &Val) {
187 BucketT *TheBucket;
188 if (!LookupBucketFor(Val, TheBucket))
189 return false; // not in map.
190
191 TheBucket->getSecond().~ValueT();
192 TheBucket->getFirst() = getTombstoneKey();
193 decrementNumEntries();
194 incrementNumTombstones();
195 return true;
196 }
197
198 void erase(value_type *I) {
199 CHECK_NE(I, nullptr);
200 BucketT *TheBucket = &*I;
201 TheBucket->getSecond().~ValueT();
202 TheBucket->getFirst() = getTombstoneKey();
203 decrementNumEntries();
204 incrementNumTombstones();
205 }
206
207 value_type &FindAndConstruct(const KeyT &Key) {
208 BucketT *TheBucket;
209 if (LookupBucketFor(Key, TheBucket))
210 return *TheBucket;
211
212 return *InsertIntoBucket(TheBucket, Key);
213 }
214
215 ValueT &operator[](const KeyT &Key) { return FindAndConstruct(Key).second; }
216
217 value_type &FindAndConstruct(KeyT &&Key) {
218 BucketT *TheBucket;
219 if (LookupBucketFor(Key, TheBucket))
220 return *TheBucket;
221
222 return *InsertIntoBucket(TheBucket, __sanitizer::move(Key));
223 }
224
225 ValueT &operator[](KeyT &&Key) {
226 return FindAndConstruct(__sanitizer::move(Key)).second;
227 }
228
229 /// Iterate over active entries of the container.
230 ///
231 /// Function can return fast to stop the process.
232 template <class Fn>
233 void forEach(Fn fn) {
234 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
235 for (auto *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
236 const KeyT K = P->getFirst();
237 if (!KeyInfoT::isEqual(K, EmptyKey) &&
238 !KeyInfoT::isEqual(K, TombstoneKey)) {
239 if (!fn(*P))
240 return;
241 }
242 }
243 }
244
245 template <class Fn>
246 void forEach(Fn fn) const {
247 const_cast<DenseMapBase *>(this)->forEach(
248 [&](const value_type &KV) { return fn(KV); });
249 }
250
251 protected:
252 DenseMapBase() = default;
253
254 void destroyAll() {
255 if (getNumBuckets() == 0) // Nothing to do.
256 return;
257
258 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
259 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
260 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
261 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
262 P->getSecond().~ValueT();
263 P->getFirst().~KeyT();
264 }
265 }
266
267 void initEmpty() {
268 setNumEntries(0);
269 setNumTombstones(0);
270
271 CHECK_EQ((getNumBuckets() & (getNumBuckets() - 1)), 0);
272 const KeyT EmptyKey = getEmptyKey();
273 for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
274 ::new (&B->getFirst()) KeyT(EmptyKey);
275 }
276
277 /// Returns the number of buckets to allocate to ensure that the DenseMap can
278 /// accommodate \p NumEntries without need to grow().
279 unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
280 // Ensure that "NumEntries * 4 < NumBuckets * 3"
281 if (NumEntries == 0)
282 return 0;
283 // +1 is required because of the strict equality.
284 // For example if NumEntries is 48, we need to return 401.
285 return RoundUpToPowerOfTwo((NumEntries * 4 / 3 + 1) + /* NextPowerOf2 */ 1);
286 }
287
288 void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
289 initEmpty();
290
291 // Insert all the old elements.
292 const KeyT EmptyKey = getEmptyKey();
293 const KeyT TombstoneKey = getTombstoneKey();
294 for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
295 if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
296 !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
297 // Insert the key/value into the new table.
298 BucketT *DestBucket;
299 bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
300 (void)FoundVal; // silence warning.
301 CHECK(!FoundVal);
302 DestBucket->getFirst() = __sanitizer::move(B->getFirst());
303 ::new (&DestBucket->getSecond())
304 ValueT(__sanitizer::move(B->getSecond()));
305 incrementNumEntries();
306
307 // Free the value.
308 B->getSecond().~ValueT();
309 }
310 B->getFirst().~KeyT();
311 }
312 }
313
314 template <typename OtherBaseT>
315 void copyFrom(
316 const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
317 CHECK_NE(&other, this);
318 CHECK_EQ(getNumBuckets(), other.getNumBuckets());
319
320 setNumEntries(other.getNumEntries());
321 setNumTombstones(other.getNumTombstones());
322
323 if (__sanitizer::is_trivially_copyable<KeyT>::value &&
324 __sanitizer::is_trivially_copyable<ValueT>::value)
325 internal_memcpy(reinterpret_cast<void *>(getBuckets()),
326 other.getBuckets(), getNumBuckets() * sizeof(BucketT));
327 else
328 for (uptr i = 0; i < getNumBuckets(); ++i) {
329 ::new (&getBuckets()[i].getFirst())
330 KeyT(other.getBuckets()[i].getFirst());
331 if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
332 !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
333 ::new (&getBuckets()[i].getSecond())
334 ValueT(other.getBuckets()[i].getSecond());
335 }
336 }
337
338 static unsigned getHashValue(const KeyT &Val) {
339 return KeyInfoT::getHashValue(Val);
340 }
341
342 template <typename LookupKeyT>
343 static unsigned getHashValue(const LookupKeyT &Val) {
344 return KeyInfoT::getHashValue(Val);
345 }
346
347 static const KeyT getEmptyKey() { return KeyInfoT::getEmptyKey(); }
348
349 static const KeyT getTombstoneKey() { return KeyInfoT::getTombstoneKey(); }
350
351 private:
352 unsigned getNumEntries() const {
353 return static_cast<const DerivedT *>(this)->getNumEntries();
354 }
355
356 void setNumEntries(unsigned Num) {
357 static_cast<DerivedT *>(this)->setNumEntries(Num);
358 }
359
360 void incrementNumEntries() { setNumEntries(getNumEntries() + 1); }
361
362 void decrementNumEntries() { setNumEntries(getNumEntries() - 1); }
363
364 unsigned getNumTombstones() const {
365 return static_cast<const DerivedT *>(this)->getNumTombstones();
366 }
367
368 void setNumTombstones(unsigned Num) {
369 static_cast<DerivedT *>(this)->setNumTombstones(Num);
370 }
371
372 void incrementNumTombstones() { setNumTombstones(getNumTombstones() + 1); }
373
374 void decrementNumTombstones() { setNumTombstones(getNumTombstones() - 1); }
375
376 const BucketT *getBuckets() const {
377 return static_cast<const DerivedT *>(this)->getBuckets();
378 }
379
380 BucketT *getBuckets() { return static_cast<DerivedT *>(this)->getBuckets(); }
381
382 unsigned getNumBuckets() const {
383 return static_cast<const DerivedT *>(this)->getNumBuckets();
384 }
385
386 BucketT *getBucketsEnd() { return getBuckets() + getNumBuckets(); }
387
388 const BucketT *getBucketsEnd() const {
389 return getBuckets() + getNumBuckets();
390 }
391
392 void grow(unsigned AtLeast) { static_cast<DerivedT *>(this)->grow(AtLeast); }
393
394 template <typename KeyArg, typename... ValueArgs>
395 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
396 ValueArgs &&...Values) {
397 TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
398
399 TheBucket->getFirst() = __sanitizer::forward<KeyArg>(Key);
400 ::new (&TheBucket->getSecond())
401 ValueT(__sanitizer::forward<ValueArgs>(Values)...);
402 return TheBucket;
403 }
404
405 template <typename LookupKeyT>
406 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
407 ValueT &&Value, LookupKeyT &Lookup) {
408 TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
409
410 TheBucket->getFirst() = __sanitizer::move(Key);
411 ::new (&TheBucket->getSecond()) ValueT(__sanitizer::move(Value));
412 return TheBucket;
413 }
414
415 template <typename LookupKeyT>
416 BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
417 BucketT *TheBucket) {
418 // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
419 // the buckets are empty (meaning that many are filled with tombstones),
420 // grow the table.
421 //
422 // The later case is tricky. For example, if we had one empty bucket with
423 // tons of tombstones, failing lookups (e.g. for insertion) would have to
424 // probe almost the entire table until it found the empty bucket. If the
425 // table completely filled with tombstones, no lookup would ever succeed,
426 // causing infinite loops in lookup.
427 unsigned NewNumEntries = getNumEntries() + 1;
428 unsigned NumBuckets = getNumBuckets();
429 if (UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
430 this->grow(NumBuckets * 2);
431 LookupBucketFor(Lookup, TheBucket);
432 NumBuckets = getNumBuckets();
433 } else if (UNLIKELY(NumBuckets - (NewNumEntries + getNumTombstones()) <=
434 NumBuckets / 8)) {
435 this->grow(NumBuckets);
436 LookupBucketFor(Lookup, TheBucket);
437 }
438 CHECK(TheBucket);
439
440 // Only update the state after we've grown our bucket space appropriately
441 // so that when growing buckets we have self-consistent entry count.
442 incrementNumEntries();
443
444 // If we are writing over a tombstone, remember this.
445 const KeyT EmptyKey = getEmptyKey();
446 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
447 decrementNumTombstones();
448
449 return TheBucket;
450 }
451
452 /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
453 /// FoundBucket. If the bucket contains the key and a value, this returns
454 /// true, otherwise it returns a bucket with an empty marker or tombstone and
455 /// returns false.
456 template <typename LookupKeyT>
457 bool LookupBucketFor(const LookupKeyT &Val,
458 const BucketT *&FoundBucket) const {
459 const BucketT *BucketsPtr = getBuckets();
460 const unsigned NumBuckets = getNumBuckets();
461
462 if (NumBuckets == 0) {
463 FoundBucket = nullptr;
464 return false;
465 }
466
467 // FoundTombstone - Keep track of whether we find a tombstone while probing.
468 const BucketT *FoundTombstone = nullptr;
469 const KeyT EmptyKey = getEmptyKey();
470 const KeyT TombstoneKey = getTombstoneKey();
471 CHECK(!KeyInfoT::isEqual(Val, EmptyKey));
472 CHECK(!KeyInfoT::isEqual(Val, TombstoneKey));
473
474 unsigned BucketNo = getHashValue(Val) & (NumBuckets - 1);
475 unsigned ProbeAmt = 1;
476 while (true) {
477 const BucketT *ThisBucket = BucketsPtr + BucketNo;
478 // Found Val's bucket? If so, return it.
479 if (LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
480 FoundBucket = ThisBucket;
481 return true;
482 }
483
484 // If we found an empty bucket, the key doesn't exist in the set.
485 // Insert it and return the default value.
486 if (LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
487 // If we've already seen a tombstone while probing, fill it in instead
488 // of the empty bucket we eventually probed to.
489 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
490 return false;
491 }
492
493 // If this is a tombstone, remember it. If Val ends up not in the map, we
494 // prefer to return it than something that would require more probing.
495 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
496 !FoundTombstone)
497 FoundTombstone = ThisBucket; // Remember the first tombstone found.
498
499 // Otherwise, it's a hash collision or a tombstone, continue quadratic
500 // probing.
501 BucketNo += ProbeAmt++;
502 BucketNo &= (NumBuckets - 1);
503 }
504 }
505
506 template <typename LookupKeyT>
507 bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
508 const BucketT *ConstFoundBucket;
509 bool Result = const_cast<const DenseMapBase *>(this)->LookupBucketFor(
510 Val, ConstFoundBucket);
511 FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
512 return Result;
513 }
514
515 public:
516 /// Return the approximate size (in bytes) of the actual map.
517 /// This is just the raw memory used by DenseMap.
518 /// If entries are pointers to objects, the size of the referenced objects
519 /// are not included.
520 uptr getMemorySize() const {
521 return RoundUpTo(getNumBuckets() * sizeof(BucketT), GetPageSizeCached());
522 }
523 };
524
525 /// Equality comparison for DenseMap.
526 ///
527 /// Iterates over elements of LHS confirming that each (key, value) pair in LHS
528 /// is also in RHS, and that no additional pairs are in RHS.
529 /// Equivalent to N calls to RHS.find and N value comparisons. Amortized
530 /// complexity is linear, worst case is O(N^2) (if every hash collides).
531 template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
532 typename BucketT>
533 bool operator==(
534 const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
535 const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
536 if (LHS.size() != RHS.size())
537 return false;
538
539 bool R = true;
540 LHS.forEach(
541 [&](const typename DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT,
542 BucketT>::value_type &KV) -> bool {
543 const auto *I = RHS.find(KV.first);
544 if (!I || I->second != KV.second) {
545 R = false;
546 return false;
547 }
548 return true;
549 });
550
551 return R;
552 }
553
554 /// Inequality comparison for DenseMap.
555 ///
556 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
557 template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
558 typename BucketT>
559 bool operator!=(
560 const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
561 const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
562 return !(LHS == RHS);
563 }
564
565 template <typename KeyT, typename ValueT,
566 typename KeyInfoT = DenseMapInfo<KeyT>,
567 typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
568 class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
569 KeyT, ValueT, KeyInfoT, BucketT> {
570 friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
571
572 // Lift some types from the dependent base class into this class for
573 // simplicity of referring to them.
574 using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
575
576 BucketT *Buckets = nullptr;
577 unsigned NumEntries = 0;
578 unsigned NumTombstones = 0;
579 unsigned NumBuckets = 0;
580
581 public:
582 /// Create a DenseMap with an optional \p InitialReserve that guarantee that
583 /// this number of elements can be inserted in the map without grow()
584 explicit DenseMap(unsigned InitialReserve) { init(InitialReserve); }
585 constexpr DenseMap() = default;
586
587 DenseMap(const DenseMap &other) : BaseT() {
588 init(0);
589 copyFrom(other);
590 }
591
592 DenseMap(DenseMap &&other) : BaseT() {
593 init(0);
594 swap(other);
595 }
596
597 ~DenseMap() {
598 this->destroyAll();
599 deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets);
600 }
601
602 void swap(DenseMap &RHS) {
603 Swap(Buckets, RHS.Buckets);
604 Swap(NumEntries, RHS.NumEntries);
605 Swap(NumTombstones, RHS.NumTombstones);
606 Swap(NumBuckets, RHS.NumBuckets);
607 }
608
609 DenseMap &operator=(const DenseMap &other) {
610 if (&other != this)
611 copyFrom(other);
612 return *this;
613 }
614
615 DenseMap &operator=(DenseMap &&other) {
616 this->destroyAll();
617 deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
618 init(0);
619 swap(other);
620 return *this;
621 }
622
623 void copyFrom(const DenseMap &other) {
624 this->destroyAll();
625 deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets);
626 if (allocateBuckets(other.NumBuckets)) {
627 this->BaseT::copyFrom(other);
628 } else {
629 NumEntries = 0;
630 NumTombstones = 0;
631 }
632 }
633
634 void init(unsigned InitNumEntries) {
635 auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
636 if (allocateBuckets(InitBuckets)) {
637 this->BaseT::initEmpty();
638 } else {
639 NumEntries = 0;
640 NumTombstones = 0;
641 }
642 }
643
644 void grow(unsigned AtLeast) {
645 unsigned OldNumBuckets = NumBuckets;
646 BucketT *OldBuckets = Buckets;
647
648 allocateBuckets(RoundUpToPowerOfTwo(Max<unsigned>(64, AtLeast)));
649 CHECK(Buckets);
650 if (!OldBuckets) {
651 this->BaseT::initEmpty();
652 return;
653 }
654
655 this->moveFromOldBuckets(OldBuckets, OldBuckets + OldNumBuckets);
656
657 // Free the old table.
658 deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets);
659 }
660
661 private:
662 unsigned getNumEntries() const { return NumEntries; }
663
664 void setNumEntries(unsigned Num) { NumEntries = Num; }
665
666 unsigned getNumTombstones() const { return NumTombstones; }
667
668 void setNumTombstones(unsigned Num) { NumTombstones = Num; }
669
670 BucketT *getBuckets() const { return Buckets; }
671
672 unsigned getNumBuckets() const { return NumBuckets; }
673
674 bool allocateBuckets(unsigned Num) {
675 NumBuckets = Num;
676 if (NumBuckets == 0) {
677 Buckets = nullptr;
678 return false;
679 }
680
681 uptr Size = sizeof(BucketT) * NumBuckets;
682 if (Size * 2 <= GetPageSizeCached()) {
683 // We always allocate at least a page, so use entire space.
684 unsigned Log2 = MostSignificantSetBitIndex(GetPageSizeCached() / Size);
685 Size <<= Log2;
686 NumBuckets <<= Log2;
687 CHECK_EQ(Size, sizeof(BucketT) * NumBuckets);
688 CHECK_GT(Size * 2, GetPageSizeCached());
689 }
690 Buckets = static_cast<BucketT *>(allocate_buffer(Size));
691 return true;
692 }
693
694 static void *allocate_buffer(uptr Size) {
695 return MmapOrDie(RoundUpTo(Size, GetPageSizeCached()), "DenseMap");
696 }
697
698 static void deallocate_buffer(void *Ptr, uptr Size) {
699 UnmapOrDie(Ptr, RoundUpTo(Size, GetPageSizeCached()));
700 }
701 };
702
703 } // namespace __sanitizer
704
705 #endif // SANITIZER_DENSE_MAP_H