diff options
| -rw-r--r-- | llvm/include/llvm/ADT/DenseMap.h | 6 | ||||
| -rw-r--r-- | llvm/unittests/ADT/DenseMapTest.cpp | 13 |
2 files changed, 18 insertions, 1 deletions
diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h index 4cf0d6d328b..4dee41f1729 100644 --- a/llvm/include/llvm/ADT/DenseMap.h +++ b/llvm/include/llvm/ADT/DenseMap.h @@ -81,8 +81,12 @@ public: } unsigned size() const { return getNumEntries(); } - /// Grow the densemap so that it has at least Size buckets. Does not shrink + /// Grow the densemap so that it can contain at least Size items before + /// resizing again. This means somewhat more than Size buckets because + /// densemap resizes upon reaching 3/4 full. void resize(size_type Size) { + // Size *= (4/3), rounding up. + Size = (Size * 4 + 2) / 3; incrementEpoch(); if (Size > getNumBuckets()) grow(Size); diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp index f3dcf95e92f..0fda2c62332 100644 --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -339,6 +339,19 @@ TYPED_TEST(DenseMapTest, ConstIteratorTest) { EXPECT_TRUE(cit == cit2); } +// Make sure resize actually gives us enough buckets to insert N items +// without increasing allocation size. +TEST(DenseMapCustomTest, ResizeTest) { + for (unsigned Size = 16; Size < 32; ++Size) { + DenseMap<unsigned, unsigned> Map; + Map.resize(Size); + unsigned MemorySize = Map.getMemorySize(); + for (unsigned i = 0; i < Size; ++i) + Map[i] = i; + EXPECT_TRUE(Map.getMemorySize() == MemorySize); + } +} + // Make sure DenseMap works with StringRef keys. TEST(DenseMapCustomTest, StringRefTest) { DenseMap<StringRef, int> M; |
