vendor/llvm/llvm-trunk-r302069

9 files changed, 303 insertions, 235 deletions

diff --git a/lib/DebugInfo/PDB/CMakeLists.txt b/lib/DebugInfo/PDB/CMakeLists.txt
index bd35efb51c74..e1753018c7df 100644
--- a/lib/DebugInfo/PDB/CMakeLists.txt
+++ b/lib/DebugInfo/PDB/CMakeLists.txt
@@ -48,11 +48,11 @@ add_pdb_impl_folder(Native
   Native/NativeSession.cpp
   Native/PDBFile.cpp
   Native/PDBFileBuilder.cpp
+  Native/PDBStringTable.cpp
+  Native/PDBStringTableBuilder.cpp
   Native/PDBTypeServerHandler.cpp
   Native/PublicsStream.cpp
   Native/RawError.cpp
-  Native/StringTable.cpp
-  Native/StringTableBuilder.cpp
   Native/SymbolStream.cpp
   Native/TpiHashing.cpp
   Native/TpiStream.cpp
diff --git a/lib/DebugInfo/PDB/Native/DbiModuleDescriptorBuilder.cpp b/lib/DebugInfo/PDB/Native/DbiModuleDescriptorBuilder.cpp
index f994b4538ef0..867864e47dce 100644
--- a/lib/DebugInfo/PDB/Native/DbiModuleDescriptorBuilder.cpp
+++ b/lib/DebugInfo/PDB/Native/DbiModuleDescriptorBuilder.cpp
@@ -89,6 +89,14 @@ uint32_t DbiModuleDescriptorBuilder::calculateSerializedLength() const {
   return alignTo(L + M + O, sizeof(uint32_t));
 }
 
+template <typename T> struct Foo {
+  explicit Foo(T &&Answer) : Answer(Answer) {}
+
+  T Answer;
+};
+
+template <typename T> Foo<T> makeFoo(T &&t) { return Foo<T>(std::move(t)); }
+
 void DbiModuleDescriptorBuilder::finalize() {
   Layout.FileNameOffs = 0; // TODO: Fix this
   Layout.Flags = 0;        // TODO: Fix this
diff --git a/lib/DebugInfo/PDB/Native/DbiStream.cpp b/lib/DebugInfo/PDB/Native/DbiStream.cpp
index 4802cc6e8197..db703809f7c9 100644
--- a/lib/DebugInfo/PDB/Native/DbiStream.cpp
+++ b/lib/DebugInfo/PDB/Native/DbiStream.cpp
@@ -146,7 +146,7 @@ Error DbiStream::reload() {
 
   if (ECSubstream.getLength() > 0) {
     BinaryStreamReader ECReader(ECSubstream);
-    if (auto EC = ECNames.load(ECReader))
+    if (auto EC = ECNames.reload(ECReader))
       return EC;
   }
 
diff --git a/lib/DebugInfo/PDB/Native/PDBFile.cpp b/lib/DebugInfo/PDB/Native/PDBFile.cpp
index 943e7fa13ab7..859295d2c7d3 100644
--- a/lib/DebugInfo/PDB/Native/PDBFile.cpp
+++ b/lib/DebugInfo/PDB/Native/PDBFile.cpp
@@ -15,9 +15,9 @@
 #include "llvm/DebugInfo/PDB/Native/DbiStream.h"
 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStream.h"
+#include "llvm/DebugInfo/PDB/Native/PDBStringTable.h"
 #include "llvm/DebugInfo/PDB/Native/PublicsStream.h"
 #include "llvm/DebugInfo/PDB/Native/RawError.h"
-#include "llvm/DebugInfo/PDB/Native/StringTable.h"
 #include "llvm/DebugInfo/PDB/Native/SymbolStream.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 #include "llvm/Support/BinaryStream.h"
@@ -337,8 +337,8 @@ Expected<SymbolStream &> PDBFile::getPDBSymbolStream() {
   return *Symbols;
 }
 
-Expected<StringTable &> PDBFile::getStringTable() {
-  if (!Strings || !StringTableStream) {
+Expected<PDBStringTable &> PDBFile::getStringTable() {
+  if (!Strings) {
     auto IS = getPDBInfoStream();
     if (!IS)
       return IS.takeError();
@@ -350,12 +350,13 @@ Expected<StringTable &> PDBFile::getStringTable() {
     if (!NS)
       return NS.takeError();
 
+    auto N = llvm::make_unique<PDBStringTable>();
     BinaryStreamReader Reader(**NS);
-    auto N = llvm::make_unique<StringTable>();
-    if (auto EC = N->load(Reader))
+    if (auto EC = N->reload(Reader))
       return std::move(EC);
-    Strings = std::move(N);
+    assert(Reader.bytesRemaining() == 0);
     StringTableStream = std::move(*NS);
+    Strings = std::move(N);
   }
   return *Strings;
 }
@@ -389,7 +390,7 @@ bool PDBFile::hasPDBSymbolStream() {
 
 bool PDBFile::hasPDBTpiStream() const { return StreamTPI < getNumStreams(); }
 
-bool PDBFile::hasStringTable() {
+bool PDBFile::hasPDBStringTable() {
   auto IS = getPDBInfoStream();
   if (!IS)
     return false;
diff --git a/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp b/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp
index b3c84903bc7e..4dd965c69071 100644
--- a/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp
+++ b/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp
@@ -17,8 +17,8 @@
 #include "llvm/DebugInfo/PDB/Native/DbiStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStream.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStreamBuilder.h"
+#include "llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/RawError.h"
-#include "llvm/DebugInfo/PDB/Native/StringTableBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h"
 #include "llvm/Support/BinaryStream.h"
@@ -67,7 +67,9 @@ TpiStreamBuilder &PDBFileBuilder::getIpiBuilder() {
   return *Ipi;
 }
 
-StringTableBuilder &PDBFileBuilder::getStringTableBuilder() { return Strings; }
+PDBStringTableBuilder &PDBFileBuilder::getStringTableBuilder() {
+  return Strings;
+}
 
 Error PDBFileBuilder::addNamedStream(StringRef Name, uint32_t Size) {
   auto ExpectedStream = Msf->addStream(Size);
@@ -78,9 +80,9 @@ Error PDBFileBuilder::addNamedStream(StringRef Name, uint32_t Size) {
 }
 
 Expected<msf::MSFLayout> PDBFileBuilder::finalizeMsfLayout() {
-  uint32_t StringTableSize = Strings.finalize();
+  uint32_t StringsLen = Strings.calculateSerializedSize();
 
-  if (auto EC = addNamedStream("/names", StringTableSize))
+  if (auto EC = addNamedStream("/names", StringsLen))
     return std::move(EC);
   if (auto EC = addNamedStream("/LinkInfo", 0))
     return std::move(EC);
@@ -107,6 +109,13 @@ Expected<msf::MSFLayout> PDBFileBuilder::finalizeMsfLayout() {
   return Msf->build();
 }
 
+Expected<uint32_t> PDBFileBuilder::getNamedStreamIndex(StringRef Name) const {
+  uint32_t SN = 0;
+  if (!NamedStreams.get(Name, SN))
+    return llvm::make_error<pdb::RawError>(raw_error_code::no_stream);
+  return SN;
+}
+
 Error PDBFileBuilder::commit(StringRef Filename) {
   auto ExpectedLayout = finalizeMsfLayout();
   if (!ExpectedLayout)
@@ -144,12 +153,12 @@ Error PDBFileBuilder::commit(StringRef Filename) {
       return EC;
   }
 
-  uint32_t StringTableStreamNo = 0;
-  if (!NamedStreams.get("/names", StringTableStreamNo))
-    return llvm::make_error<pdb::RawError>(raw_error_code::no_stream);
+  auto ExpectedSN = getNamedStreamIndex("/names");
+  if (!ExpectedSN)
+    return ExpectedSN.takeError();
 
   auto NS = WritableMappedBlockStream::createIndexedStream(Layout, Buffer,
-                                                           StringTableStreamNo);
+                                                           *ExpectedSN);
   BinaryStreamWriter NSWriter(*NS);
   if (auto EC = Strings.commit(NSWriter))
     return EC;
diff --git a/lib/DebugInfo/PDB/Native/PDBStringTable.cpp b/lib/DebugInfo/PDB/Native/PDBStringTable.cpp
new file mode 100644
index 000000000000..e84573fe07b8
--- /dev/null
+++ b/lib/DebugInfo/PDB/Native/PDBStringTable.cpp
@@ -0,0 +1,134 @@
+//===- PDBStringTable.cpp - PDB String Table ---------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/PDB/Native/PDBStringTable.h"
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/DebugInfo/MSF/MappedBlockStream.h"
+#include "llvm/DebugInfo/PDB/Native/Hash.h"
+#include "llvm/DebugInfo/PDB/Native/RawError.h"
+#include "llvm/DebugInfo/PDB/Native/RawTypes.h"
+#include "llvm/Support/BinaryStreamReader.h"
+#include "llvm/Support/Endian.h"
+
+using namespace llvm;
+using namespace llvm::support;
+using namespace llvm::pdb;
+
+uint32_t PDBStringTable::getByteSize() const { return ByteSize; }
+uint32_t PDBStringTable::getNameCount() const { return NameCount; }
+uint32_t PDBStringTable::getHashVersion() const { return Header->HashVersion; }
+uint32_t PDBStringTable::getSignature() const { return Header->Signature; }
+
+Error PDBStringTable::readHeader(BinaryStreamReader &Reader) {
+  if (auto EC = Reader.readObject(Header))
+    return EC;
+
+  if (Header->Signature != PDBStringTableSignature)
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "Invalid hash table signature");
+  if (Header->HashVersion != 1 && Header->HashVersion != 2)
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "Unsupported hash version");
+
+  assert(Reader.bytesRemaining() == 0);
+  return Error::success();
+}
+
+Error PDBStringTable::readStrings(BinaryStreamReader &Reader) {
+  BinaryStreamRef Stream;
+  if (auto EC = Reader.readStreamRef(Stream))
+    return EC;
+
+  if (auto EC = Strings.initialize(Stream)) {
+    return joinErrors(std::move(EC),
+                      make_error<RawError>(raw_error_code::corrupt_file,
+                                           "Invalid hash table byte length"));
+  }
+
+  assert(Reader.bytesRemaining() == 0);
+  return Error::success();
+}
+
+Error PDBStringTable::readHashTable(BinaryStreamReader &Reader) {
+  const support::ulittle32_t *HashCount;
+  if (auto EC = Reader.readObject(HashCount))
+    return EC;
+
+  if (auto EC = Reader.readArray(IDs, *HashCount)) {
+    return joinErrors(std::move(EC),
+                      make_error<RawError>(raw_error_code::corrupt_file,
+                                           "Could not read bucket array"));
+  }
+
+  return Error::success();
+}
+
+Error PDBStringTable::readEpilogue(BinaryStreamReader &Reader) {
+  if (auto EC = Reader.readInteger(NameCount))
+    return EC;
+
+  assert(Reader.bytesRemaining() == 0);
+  return Error::success();
+}
+
+Error PDBStringTable::reload(BinaryStreamReader &Reader) {
+
+  BinaryStreamReader SectionReader;
+
+  std::tie(SectionReader, Reader) = Reader.split(sizeof(PDBStringTableHeader));
+  if (auto EC = readHeader(SectionReader))
+    return EC;
+
+  std::tie(SectionReader, Reader) = Reader.split(Header->ByteSize);
+  if (auto EC = readStrings(SectionReader))
+    return EC;
+
+  // We don't know how long the hash table is until we parse it, so let the
+  // function responsible for doing that figure it out.
+  if (auto EC = readHashTable(Reader))
+    return EC;
+
+  std::tie(SectionReader, Reader) = Reader.split(sizeof(uint32_t));
+  if (auto EC = readEpilogue(SectionReader))
+    return EC;
+
+  assert(Reader.bytesRemaining() == 0);
+  return Error::success();
+}
+
+Expected<StringRef> PDBStringTable::getStringForID(uint32_t ID) const {
+  return Strings.getString(ID);
+}
+
+Expected<uint32_t> PDBStringTable::getIDForString(StringRef Str) const {
+  uint32_t Hash =
+      (Header->HashVersion == 1) ? hashStringV1(Str) : hashStringV2(Str);
+  size_t Count = IDs.size();
+  uint32_t Start = Hash % Count;
+  for (size_t I = 0; I < Count; ++I) {
+    // The hash is just a starting point for the search, but if it
+    // doesn't work we should find the string no matter what, because
+    // we iterate the entire array.
+    uint32_t Index = (Start + I) % Count;
+
+    uint32_t ID = IDs[Index];
+    auto ExpectedStr = getStringForID(ID);
+    if (!ExpectedStr)
+      return ExpectedStr.takeError();
+
+    if (*ExpectedStr == Str)
+      return ID;
+  }
+  return make_error<RawError>(raw_error_code::no_entry);
+}
+
+FixedStreamArray<support::ulittle32_t> PDBStringTable::name_ids() const {
+  return IDs;
+}
diff --git a/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp b/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp
new file mode 100644
index 000000000000..a472181a4895
--- /dev/null
+++ b/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp
@@ -0,0 +1,133 @@
+//===- PDBStringTableBuilder.cpp - PDB String Table -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/DebugInfo/MSF/MappedBlockStream.h"
+#include "llvm/DebugInfo/PDB/Native/Hash.h"
+#include "llvm/DebugInfo/PDB/Native/PDBFileBuilder.h"
+#include "llvm/DebugInfo/PDB/Native/RawTypes.h"
+#include "llvm/Support/BinaryStreamWriter.h"
+#include "llvm/Support/Endian.h"
+
+using namespace llvm;
+using namespace llvm::msf;
+using namespace llvm::support;
+using namespace llvm::support::endian;
+using namespace llvm::pdb;
+
+uint32_t PDBStringTableBuilder::insert(StringRef S) {
+  return Strings.insert(S);
+}
+
+static uint32_t computeBucketCount(uint32_t NumStrings) {
+  // The /names stream is basically an on-disk open-addressing hash table.
+  // Hash collisions are resolved by linear probing. We cannot make
+  // utilization 100% because it will make the linear probing extremely
+  // slow. But lower utilization wastes disk space. As a reasonable
+  // load factor, we choose 80%. We need +1 because slot 0 is reserved.
+  return (NumStrings + 1) * 1.25;
+}
+
+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());
+
+  return Size;
+}
+
+uint32_t PDBStringTableBuilder::calculateSerializedSize() const {
+  uint32_t Size = 0;
+  Size += sizeof(PDBStringTableHeader);
+  Size += Strings.calculateSerializedSize();
+  Size += calculateHashTableSize();
+  Size += sizeof(uint32_t); // The /names stream ends with the string count.
+  return Size;
+}
+
+Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
+  // Write a header
+  PDBStringTableHeader H;
+  H.Signature = PDBStringTableSignature;
+  H.HashVersion = 1;
+  H.ByteSize = Strings.calculateSerializedSize();
+  if (auto EC = Writer.writeObject(H))
+    return EC;
+  assert(Writer.bytesRemaining() == 0);
+  return Error::success();
+}
+
+Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
+  if (auto EC = Strings.commit(Writer))
+    return EC;
+
+  assert(Writer.bytesRemaining() == 0);
+  return Error::success();
+}
+
+Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
+  // Write a hash table.
+  uint32_t BucketCount = computeBucketCount(Strings.size());
+  if (auto EC = Writer.writeInteger(BucketCount))
+    return EC;
+  std::vector<ulittle32_t> Buckets(BucketCount);
+
+  for (auto &Pair : Strings) {
+    StringRef S = Pair.getKey();
+    uint32_t Offset = Pair.getValue();
+    uint32_t Hash = hashStringV1(S);
+
+    for (uint32_t I = 0; I != BucketCount; ++I) {
+      uint32_t Slot = (Hash + I) % BucketCount;
+      if (Slot == 0)
+        continue; // Skip reserved slot
+      if (Buckets[Slot] != 0)
+        continue;
+      Buckets[Slot] = Offset;
+      break;
+    }
+  }
+
+  if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
+    return EC;
+
+  assert(Writer.bytesRemaining() == 0);
+  return Error::success();
+}
+
+Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
+  if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
+    return EC;
+  assert(Writer.bytesRemaining() == 0);
+  return Error::success();
+}
+
+Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
+  BinaryStreamWriter SectionWriter;
+
+  std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
+  if (auto EC = writeHeader(SectionWriter))
+    return EC;
+
+  std::tie(SectionWriter, Writer) =
+      Writer.split(Strings.calculateSerializedSize());
+  if (auto EC = writeStrings(SectionWriter))
+    return EC;
+
+  std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
+  if (auto EC = writeHashTable(SectionWriter))
+    return EC;
+
+  std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
+  if (auto EC = writeEpilogue(SectionWriter))
+    return EC;
+
+  return Error::success();
+}
diff --git a/lib/DebugInfo/PDB/Native/StringTable.cpp b/lib/DebugInfo/PDB/Native/StringTable.cpp
deleted file mode 100644
index 7e28389b8383..000000000000
--- a/lib/DebugInfo/PDB/Native/StringTable.cpp
+++ /dev/null
@@ -1,109 +0,0 @@
-//===- StringTable.cpp - PDB String Table -----------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/DebugInfo/PDB/Native/StringTable.h"
-
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/DebugInfo/PDB/Native/Hash.h"
-#include "llvm/DebugInfo/PDB/Native/RawError.h"
-#include "llvm/DebugInfo/PDB/Native/RawTypes.h"
-#include "llvm/Support/BinaryStreamReader.h"
-#include "llvm/Support/Endian.h"
-
-using namespace llvm;
-using namespace llvm::support;
-using namespace llvm::pdb;
-
-StringTable::StringTable() {}
-
-Error StringTable::load(BinaryStreamReader &Stream) {
-  ByteSize = Stream.getLength();
-
-  const StringTableHeader *H;
-  if (auto EC = Stream.readObject(H))
-    return EC;
-
-  if (H->Signature != StringTableSignature)
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Invalid hash table signature");
-  if (H->HashVersion != 1 && H->HashVersion != 2)
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Unsupported hash version");
-
-  Signature = H->Signature;
-  HashVersion = H->HashVersion;
-  if (auto EC = Stream.readStreamRef(NamesBuffer, H->ByteSize))
-    return joinErrors(std::move(EC),
-                      make_error<RawError>(raw_error_code::corrupt_file,
-                                           "Invalid hash table byte length"));
-
-  const support::ulittle32_t *HashCount;
-  if (auto EC = Stream.readObject(HashCount))
-    return EC;
-
-  if (auto EC = Stream.readArray(IDs, *HashCount))
-    return joinErrors(std::move(EC),
-                      make_error<RawError>(raw_error_code::corrupt_file,
-                                           "Could not read bucket array"));
-
-  if (Stream.bytesRemaining() < sizeof(support::ulittle32_t))
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Missing name count");
-
-  if (auto EC = Stream.readInteger(NameCount))
-    return EC;
-
-  if (Stream.bytesRemaining() > 0)
-    return make_error<RawError>(raw_error_code::stream_too_long,
-      "Unexpected bytes found in string table");
-
-  return Error::success();
-}
-
-uint32_t StringTable::getByteSize() const {
-  return ByteSize;
-}
-
-StringRef StringTable::getStringForID(uint32_t ID) const {
-  if (ID == IDs[0])
-    return StringRef();
-
-  // NamesBuffer is a buffer of null terminated strings back to back.  ID is
-  // the starting offset of the string we're looking for.  So just seek into
-  // the desired offset and a read a null terminated stream from that offset.
-  StringRef Result;
-  BinaryStreamReader NameReader(NamesBuffer);
-  NameReader.setOffset(ID);
-  if (auto EC = NameReader.readCString(Result))
-    consumeError(std::move(EC));
-  return Result;
-}
-
-uint32_t StringTable::getIDForString(StringRef Str) const {
-  uint32_t Hash = (HashVersion == 1) ? hashStringV1(Str) : hashStringV2(Str);
-  size_t Count = IDs.size();
-  uint32_t Start = Hash % Count;
-  for (size_t I = 0; I < Count; ++I) {
-    // The hash is just a starting point for the search, but if it
-    // doesn't work we should find the string no matter what, because
-    // we iterate the entire array.
-    uint32_t Index = (Start + I) % Count;
-
-    uint32_t ID = IDs[Index];
-    StringRef S = getStringForID(ID);
-    if (S == Str)
-      return ID;
-  }
-  // IDs[0] contains the ID of the "invalid" entry.
-  return IDs[0];
-}
-
-FixedStreamArray<support::ulittle32_t> StringTable::name_ids() const {
-  return IDs;
-}
diff --git a/lib/DebugInfo/PDB/Native/StringTableBuilder.cpp b/lib/DebugInfo/PDB/Native/StringTableBuilder.cpp
deleted file mode 100644
index 40dc8e1bfcb1..000000000000
--- a/lib/DebugInfo/PDB/Native/StringTableBuilder.cpp
+++ /dev/null
@@ -1,108 +0,0 @@
-//===- StringTableBuilder.cpp - PDB String Table ----------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/DebugInfo/PDB/Native/StringTableBuilder.h"
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/DebugInfo/PDB/Native/Hash.h"
-#include "llvm/DebugInfo/PDB/Native/RawTypes.h"
-#include "llvm/Support/BinaryStreamWriter.h"
-#include "llvm/Support/Endian.h"
-
-using namespace llvm;
-using namespace llvm::support;
-using namespace llvm::support::endian;
-using namespace llvm::pdb;
-
-uint32_t StringTableBuilder::insert(StringRef S) {
-  auto P = Strings.insert({S, StringSize});
-
-  // If a given string didn't exist in the string table, we want to increment
-  // the string table size.
-  if (P.second)
-    StringSize += S.size() + 1; // +1 for '\0'
-  return P.first->second;
-}
-
-uint32_t StringTableBuilder::getStringIndex(StringRef S) {
-  auto Iter = Strings.find(S);
-  assert(Iter != Strings.end());
-  return Iter->second;
-}
-
-static uint32_t computeBucketCount(uint32_t NumStrings) {
-  // The /names stream is basically an on-disk open-addressing hash table.
-  // Hash collisions are resolved by linear probing. We cannot make
-  // utilization 100% because it will make the linear probing extremely
-  // slow. But lower utilization wastes disk space. As a reasonable
-  // load factor, we choose 80%. We need +1 because slot 0 is reserved.
-  return (NumStrings + 1) * 1.25;
-}
-
-uint32_t StringTableBuilder::finalize() {
-  uint32_t Size = 0;
-  Size += sizeof(StringTableHeader);
-  Size += StringSize;
-  Size += sizeof(uint32_t); // Hash table begins with 4-byte size field.
-
-  uint32_t BucketCount = computeBucketCount(Strings.size());
-  Size += BucketCount * sizeof(uint32_t);
-
-  Size +=
-      sizeof(uint32_t); // The /names stream ends with the number of strings.
-  return Size;
-}
-
-Error StringTableBuilder::commit(BinaryStreamWriter &Writer) const {
-  // Write a header
-  StringTableHeader H;
-  H.Signature = StringTableSignature;
-  H.HashVersion = 1;
-  H.ByteSize = StringSize;
-  if (auto EC = Writer.writeObject(H))
-    return EC;
-
-  // Write a string table.
-  uint32_t StringStart = Writer.getOffset();
-  for (auto Pair : Strings) {
-    StringRef S = Pair.first;
-    uint32_t Offset = Pair.second;
-    Writer.setOffset(StringStart + Offset);
-    if (auto EC = Writer.writeCString(S))
-      return EC;
-  }
-  Writer.setOffset(StringStart + StringSize);
-
-  // Write a hash table.
-  uint32_t BucketCount = computeBucketCount(Strings.size());
-  if (auto EC = Writer.writeInteger(BucketCount))
-    return EC;
-  std::vector<ulittle32_t> Buckets(BucketCount);
-
-  for (auto Pair : Strings) {
-    StringRef S = Pair.first;
-    uint32_t Offset = Pair.second;
-    uint32_t Hash = hashStringV1(S);
-
-    for (uint32_t I = 0; I != BucketCount; ++I) {
-      uint32_t Slot = (Hash + I) % BucketCount;
-      if (Slot == 0)
-        continue; // Skip reserved slot
-      if (Buckets[Slot] != 0)
-        continue;
-      Buckets[Slot] = Offset;
-      break;
-    }
-  }
-
-  if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
-    return EC;
-  if (auto EC = Writer.writeInteger(static_cast<uint32_t>(Strings.size())))
-    return EC;
-  return Error::success();
-}