From bd3306aecb3a15e8967143b8cdbbccf2b1b19b74 Mon Sep 17 00:00:00 2001 From: patrick Date: Sat, 14 Jan 2017 19:55:43 +0000 Subject: Import LLVM 3.9.1 including clang and lld. --- gnu/llvm/lib/Support/StringMap.cpp | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) (limited to 'gnu/llvm/lib/Support/StringMap.cpp') 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 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; } -- cgit v1.2.3-59-g8ed1b