Expand comment about how StringsToBuckets was computed, and add more entries

[thakis]

Summary

The construction was explained in
https://reviews.llvm.org/D44810?id=139526#inline-391999 but reading the code
shouldn't require hunting down old reviews to understand it.

The precomputed list was missing an entry for the empty list case, and
one entry at the very end. (The current last entry is the last one where
3 * BucketCount fits in a signed int, but the reference implementation
uses unsigneds as far as I can tell, so there's room for one more entry.)

No behavior change for inputs seen in practice.

[rnk]

lgtm

llvm/trunk/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp

StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const {
   return Strings.getStringForId(Id);
 }
 
 static uint32_t computeBucketCount(uint32_t NumStrings) {
   // This is a precomputed list of Buckets given the specified number of
   // strings.  Matching the reference algorithm exactly is not strictly
   // necessary for correctness, but it helps when comparing LLD's PDBs with
   // Microsoft's PDBs so as to eliminate superfluous differences.
+  // The reference implementation does (in nmt.h, NMT::grow()):
+  //   unsigned StringCount = 0;
+  //   unsigned BucketCount = 1;
+  //   fn insert() {
+  //     ++StringCount;
+  //     if (BucketCount * 3 / 4 < StringCount)
+  //       BucketCount = BucketCount * 3 / 2 + 1;
+  //   }
+  // This list contains all StringCount, BucketCount pairs where BucketCount was
+  // just incremented.  It ends before the first BucketCount entry where
+  // BucketCount * 3 would overflow a 32-bit unsigned int.
   static std::map<uint32_t, uint32_t> StringsToBuckets = {
+      {0, 1},
       {1, 2},
       {2, 4},
       {4, 7},
       {6, 11},
       {9, 17},
       {13, 26},
       {20, 40},
       {31, 61},
static std::map<uint32_t, uint32_t> StringsToBuckets = {
       {30270348, 60540695},
       {45405522, 90811043},
       {68108283, 136216565},
       {102162424, 204324848},
       {153243637, 306487273},
       {229865455, 459730910},
       {344798183, 689596366},
       {517197275, 1034394550},
-      {775795913, 1551591826}};
+      {775795913, 1551591826},
+      {1163693870, 2327387740}};
   auto Entry = StringsToBuckets.lower_bound(NumStrings);
   assert(Entry != StringsToBuckets.end());
   return Entry->second;
 }
 
 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
   uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
   Size += sizeof(uint32_t) * computeBucketCount(Strings.size());