Import LLVM 3.9.1 including clang and lld.

1 files changed, 15 insertions, 1 deletions

diff --git a/gnu/llvm/lib/Support/StringMap.cpp b/gnu/llvm/lib/Support/StringMap.cpp
index 7be946642d9..7da9ccbd40c 100644
--- a/gnu/llvm/lib/Support/StringMap.cpp
+++ b/gnu/llvm/lib/Support/StringMap.cpp
@@ -17,12 +17,26 @@
 #include <cassert>
 using namespace llvm;
 
+/// Returns the number of buckets to allocate to ensure that the DenseMap can
+/// accommodate \p NumEntries without need to grow().
+static 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);
+}
+
 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
   ItemSize = itemSize;
   
   // If a size is specified, initialize the table with that many buckets.
   if (InitSize) {
-    init(InitSize);
+    // The table will grow when the number of entries reach 3/4 of the number of
+    // buckets. To guarantee that "InitSize" number of entries can be inserted
+    // in the table without growing, we allocate just what is needed here.
+    init(getMinBucketToReserveForEntries(InitSize));
     return;
   }