aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/ADT/DenseMap.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/ADT/DenseMap.h')
-rw-r--r--include/llvm/ADT/DenseMap.h76
1 files changed, 61 insertions, 15 deletions
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 6ee1960b5c82..917c086beba3 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -81,11 +81,13 @@ public:
}
unsigned size() const { return getNumEntries(); }
- /// Grow the densemap so that it has at least Size buckets. Does not shrink
- void resize(size_type Size) {
+ /// Grow the densemap so that it can contain at least \p NumEntries items
+ /// before resizing again.
+ void reserve(size_type NumEntries) {
+ auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
incrementEpoch();
- if (Size > getNumBuckets())
- grow(Size);
+ if (NumBuckets > getNumBuckets())
+ grow(NumBuckets);
}
void clear() {
@@ -195,6 +197,26 @@ public:
true);
}
+ /// Alternate version of insert() which allows a different, and possibly
+ /// less expensive, key type.
+ /// The DenseMapInfo is responsible for supplying methods
+ /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
+ /// type used.
+ template <typename LookupKeyT>
+ std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
+ const LookupKeyT &Val) {
+ BucketT *TheBucket;
+ if (LookupBucketFor(Val, TheBucket))
+ return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
+ false); // Already in map.
+
+ // Otherwise, insert the new element.
+ TheBucket = InsertIntoBucket(std::move(KV.first), std::move(KV.second), Val,
+ TheBucket);
+ return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
+ true);
+ }
+
/// insert - Range insertion of pairs.
template<typename InputIt>
void insert(InputIt I, InputIt E) {
@@ -285,6 +307,17 @@ protected:
::new (&B->getFirst()) KeyT(EmptyKey);
}
+ /// Returns the number of buckets to allocate to ensure that the DenseMap can
+ /// accommodate \p NumEntries without need to grow().
+ unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
+ // Ensure that "NumEntries * 4 < NumBuckets * 3"
+ if (NumEntries == 0)
+ return 0;
+ // +1 is required because of the strict equality.
+ // For example if NumEntries is 48, we need to return 401.
+ return NextPowerOf2(NumEntries * 4 / 3 + 1);
+ }
+
void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
initEmpty();
@@ -399,7 +432,7 @@ private:
BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
BucketT *TheBucket) {
- TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+ TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
TheBucket->getFirst() = Key;
::new (&TheBucket->getSecond()) ValueT(Value);
@@ -408,7 +441,7 @@ private:
BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value,
BucketT *TheBucket) {
- TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+ TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
TheBucket->getFirst() = Key;
::new (&TheBucket->getSecond()) ValueT(std::move(Value));
@@ -416,14 +449,26 @@ private:
}
BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) {
- TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+ TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
TheBucket->getFirst() = std::move(Key);
::new (&TheBucket->getSecond()) ValueT(std::move(Value));
return TheBucket;
}
- BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {
+ template <typename LookupKeyT>
+ BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, LookupKeyT &Lookup,
+ BucketT *TheBucket) {
+ TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
+
+ TheBucket->getFirst() = std::move(Key);
+ ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
+ return TheBucket;
+ }
+
+ template <typename LookupKeyT>
+ BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
+ BucketT *TheBucket) {
incrementEpoch();
// If the load of the hash table is more than 3/4, or if fewer than 1/8 of
@@ -439,12 +484,12 @@ private:
unsigned NumBuckets = getNumBuckets();
if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
this->grow(NumBuckets * 2);
- LookupBucketFor(Key, TheBucket);
+ LookupBucketFor(Lookup, TheBucket);
NumBuckets = getNumBuckets();
} else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
NumBuckets/8)) {
this->grow(NumBuckets);
- LookupBucketFor(Key, TheBucket);
+ LookupBucketFor(Lookup, TheBucket);
}
assert(TheBucket);
@@ -550,9 +595,9 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
unsigned NumBuckets;
public:
- explicit DenseMap(unsigned NumInitBuckets = 0) {
- init(NumInitBuckets);
- }
+ /// Create a DenseMap wth an optional \p InitialReserve that guarantee that
+ /// this number of elements can be inserted in the map without grow()
+ explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }
DenseMap(const DenseMap &other) : BaseT() {
init(0);
@@ -566,7 +611,7 @@ public:
template<typename InputIt>
DenseMap(const InputIt &I, const InputIt &E) {
- init(NextPowerOf2(std::distance(I, E)));
+ init(std::distance(I, E));
this->insert(I, E);
}
@@ -609,7 +654,8 @@ public:
}
}
- void init(unsigned InitBuckets) {
+ void init(unsigned InitNumEntries) {
+ auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
if (allocateBuckets(InitBuckets)) {
this->BaseT::initEmpty();
} else {