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