vendor/llvm/llvm-trunk-r338150

1 files changed, 140 insertions, 48 deletions

diff --git a/unittests/DebugInfo/PDB/HashTableTest.cpp b/unittests/DebugInfo/PDB/HashTableTest.cpp
index f1968e55e86f..301b215badf5 100644
--- a/unittests/DebugInfo/PDB/HashTableTest.cpp
+++ b/unittests/DebugInfo/PDB/HashTableTest.cpp
@@ -8,9 +8,14 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/PDB/Native/HashTable.h"
+
+#include "llvm/DebugInfo/PDB/Native/Hash.h"
+#include "llvm/DebugInfo/PDB/Native/NamedStreamMap.h"
+#include "llvm/Support/Allocator.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/BinaryStreamWriter.h"
+#include "llvm/Support/StringSaver.h"
 #include "llvm/Testing/Support/Error.h"
 
 #include "gtest/gtest.h"
@@ -22,7 +27,8 @@ using namespace llvm::pdb;
 using namespace llvm::support;
 
 namespace {
-class HashTableInternals : public HashTable {
+
+class HashTableInternals : public HashTable<uint32_t> {
 public:
   using HashTable::Buckets;
   using HashTable::Present;
@@ -31,18 +37,18 @@ public:
 }
 
 TEST(HashTableTest, TestSimple) {
-  HashTable Table;
+  HashTableInternals Table;
   EXPECT_EQ(0u, Table.size());
   EXPECT_GT(Table.capacity(), 0u);
 
-  Table.set(3, 7);
+  Table.set_as(3u, 7);
   EXPECT_EQ(1u, Table.size());
-  ASSERT_NE(Table.end(), Table.find(3));
-  EXPECT_EQ(7u, Table.get(3));
+  ASSERT_NE(Table.end(), Table.find_as(3u));
+  EXPECT_EQ(7u, Table.get(3u));
 }
 
 TEST(HashTableTest, TestCollision) {
-  HashTable Table;
+  HashTableInternals Table;
   EXPECT_EQ(0u, Table.size());
   EXPECT_GT(Table.capacity(), 0u);
 
@@ -52,39 +58,33 @@ TEST(HashTableTest, TestCollision) {
   uint32_t N1 = Table.capacity() + 1;
   uint32_t N2 = 2 * N1;
 
-  Table.set(N1, 7);
-  Table.set(N2, 12);
+  Table.set_as(N1, 7);
+  Table.set_as(N2, 12);
   EXPECT_EQ(2u, Table.size());
-  ASSERT_NE(Table.end(), Table.find(N1));
-  ASSERT_NE(Table.end(), Table.find(N2));
+  ASSERT_NE(Table.end(), Table.find_as(N1));
+  ASSERT_NE(Table.end(), Table.find_as(N2));
 
   EXPECT_EQ(7u, Table.get(N1));
   EXPECT_EQ(12u, Table.get(N2));
 }
 
 TEST(HashTableTest, TestRemove) {
-  HashTable Table;
+  HashTableInternals Table;
   EXPECT_EQ(0u, Table.size());
   EXPECT_GT(Table.capacity(), 0u);
 
-  Table.set(1, 2);
-  Table.set(3, 4);
+  Table.set_as(1u, 2);
+  Table.set_as(3u, 4);
   EXPECT_EQ(2u, Table.size());
-  ASSERT_NE(Table.end(), Table.find(1));
-  ASSERT_NE(Table.end(), Table.find(3));
-
-  EXPECT_EQ(2u, Table.get(1));
-  EXPECT_EQ(4u, Table.get(3));
+  ASSERT_NE(Table.end(), Table.find_as(1u));
+  ASSERT_NE(Table.end(), Table.find_as(3u));
 
-  Table.remove(1u);
-  EXPECT_EQ(1u, Table.size());
-  EXPECT_EQ(Table.end(), Table.find(1));
-  ASSERT_NE(Table.end(), Table.find(3));
-  EXPECT_EQ(4u, Table.get(3));
+  EXPECT_EQ(2u, Table.get(1u));
+  EXPECT_EQ(4u, Table.get(3u));
 }
 
 TEST(HashTableTest, TestCollisionAfterMultipleProbes) {
-  HashTable Table;
+  HashTableInternals Table;
   EXPECT_EQ(0u, Table.size());
   EXPECT_GT(Table.capacity(), 0u);
 
@@ -95,31 +95,17 @@ TEST(HashTableTest, TestCollisionAfterMultipleProbes) {
   uint32_t N2 = N1 + 1;
   uint32_t N3 = 2 * N1;
 
-  Table.set(N1, 7);
-  Table.set(N2, 11);
-  Table.set(N3, 13);
+  Table.set_as(N1, 7);
+  Table.set_as(N2, 11);
+  Table.set_as(N3, 13);
   EXPECT_EQ(3u, Table.size());
-  ASSERT_NE(Table.end(), Table.find(N1));
-  ASSERT_NE(Table.end(), Table.find(N2));
-  ASSERT_NE(Table.end(), Table.find(N3));
+  ASSERT_NE(Table.end(), Table.find_as(N1));
+  ASSERT_NE(Table.end(), Table.find_as(N2));
+  ASSERT_NE(Table.end(), Table.find_as(N3));
 
   EXPECT_EQ(7u, Table.get(N1));
   EXPECT_EQ(11u, Table.get(N2));
   EXPECT_EQ(13u, Table.get(N3));
-
-  // Remove the one that had been filled in the middle, then insert another one
-  // with a collision.  It should fill the newly emptied slot.
-  Table.remove(N2);
-  uint32_t N4 = N1 * 3;
-  Table.set(N4, 17);
-  EXPECT_EQ(3u, Table.size());
-  ASSERT_NE(Table.end(), Table.find(N1));
-  ASSERT_NE(Table.end(), Table.find(N3));
-  ASSERT_NE(Table.end(), Table.find(N4));
-
-  EXPECT_EQ(7u, Table.get(N1));
-  EXPECT_EQ(13u, Table.get(N3));
-  EXPECT_EQ(17u, Table.get(N4));
 }
 
 TEST(HashTableTest, Grow) {
@@ -127,15 +113,15 @@ TEST(HashTableTest, Grow) {
   // guaranteed to trigger a grow.  Then verify that the size is the same, the
   // capacity is larger, and all the original items are still in the table.
 
-  HashTable Table;
+  HashTableInternals Table;
   uint32_t OldCapacity = Table.capacity();
   for (uint32_t I = 0; I < OldCapacity; ++I) {
-    Table.set(OldCapacity + I * 2 + 1, I * 2 + 3);
+    Table.set_as(OldCapacity + I * 2 + 1, I * 2 + 3);
   }
   EXPECT_EQ(OldCapacity, Table.size());
   EXPECT_GT(Table.capacity(), OldCapacity);
   for (uint32_t I = 0; I < OldCapacity; ++I) {
-    ASSERT_NE(Table.end(), Table.find(OldCapacity + I * 2 + 1));
+    ASSERT_NE(Table.end(), Table.find_as(OldCapacity + I * 2 + 1));
     EXPECT_EQ(I * 2 + 3, Table.get(OldCapacity + I * 2 + 1));
   }
 }
@@ -144,7 +130,7 @@ TEST(HashTableTest, Serialization) {
   HashTableInternals Table;
   uint32_t Cap = Table.capacity();
   for (uint32_t I = 0; I < Cap; ++I) {
-    Table.set(Cap + I * 2 + 1, I * 2 + 3);
+    Table.set_as(Cap + I * 2 + 1, I * 2 + 3);
   }
 
   std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
@@ -166,3 +152,109 @@ TEST(HashTableTest, Serialization) {
   EXPECT_EQ(Table.Present, Table2.Present);
   EXPECT_EQ(Table.Deleted, Table2.Deleted);
 }
+
+TEST(HashTableTest, NamedStreamMap) {
+  std::vector<StringRef> Streams = {"One",  "Two", "Three", "Four",
+                                    "Five", "Six", "Seven"};
+  StringMap<uint32_t> ExpectedIndices;
+  for (uint32_t I = 0; I < Streams.size(); ++I)
+    ExpectedIndices[Streams[I]] = I + 1;
+
+  // To verify the hash table actually works, we want to verify that insertion
+  // order doesn't matter.  So try inserting in every possible order of 7 items.
+  do {
+    NamedStreamMap NSM;
+    for (StringRef S : Streams)
+      NSM.set(S, ExpectedIndices[S]);
+
+    EXPECT_EQ(Streams.size(), NSM.size());
+
+    uint32_t N;
+    EXPECT_TRUE(NSM.get("One", N));
+    EXPECT_EQ(1U, N);
+
+    EXPECT_TRUE(NSM.get("Two", N));
+    EXPECT_EQ(2U, N);
+
+    EXPECT_TRUE(NSM.get("Three", N));
+    EXPECT_EQ(3U, N);
+
+    EXPECT_TRUE(NSM.get("Four", N));
+    EXPECT_EQ(4U, N);
+
+    EXPECT_TRUE(NSM.get("Five", N));
+    EXPECT_EQ(5U, N);
+
+    EXPECT_TRUE(NSM.get("Six", N));
+    EXPECT_EQ(6U, N);
+
+    EXPECT_TRUE(NSM.get("Seven", N));
+    EXPECT_EQ(7U, N);
+  } while (std::next_permutation(Streams.begin(), Streams.end()));
+}
+
+namespace {
+struct FooBar {
+  uint32_t X;
+  uint32_t Y;
+};
+
+} // namespace
+
+namespace llvm {
+namespace pdb {
+template <> struct PdbHashTraits<FooBar> {
+  std::vector<char> Buffer;
+
+  PdbHashTraits() { Buffer.push_back(0); }
+
+  uint32_t hashLookupKey(StringRef S) const {
+    return llvm::pdb::hashStringV1(S);
+  }
+
+  StringRef storageKeyToLookupKey(uint32_t N) const {
+    if (N >= Buffer.size())
+      return StringRef();
+
+    return StringRef(Buffer.data() + N);
+  }
+
+  uint32_t lookupKeyToStorageKey(StringRef S) {
+    uint32_t N = Buffer.size();
+    Buffer.insert(Buffer.end(), S.begin(), S.end());
+    Buffer.push_back('\0');
+    return N;
+  }
+};
+} // namespace pdb
+} // namespace llvm
+
+TEST(HashTableTest, NonTrivialValueType) {
+  HashTable<FooBar> Table;
+  uint32_t Cap = Table.capacity();
+  for (uint32_t I = 0; I < Cap; ++I) {
+    FooBar F;
+    F.X = I;
+    F.Y = I + 1;
+    Table.set_as(utostr(I), F);
+  }
+
+  std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
+  MutableBinaryByteStream Stream(Buffer, little);
+  BinaryStreamWriter Writer(Stream);
+  EXPECT_THAT_ERROR(Table.commit(Writer), Succeeded());
+  // We should have written precisely the number of bytes we calculated earlier.
+  EXPECT_EQ(Buffer.size(), Writer.getOffset());
+
+  HashTable<FooBar> Table2;
+  BinaryStreamReader Reader(Stream);
+  EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded());
+  // We should have read precisely the number of bytes we calculated earlier.
+  EXPECT_EQ(Buffer.size(), Reader.getOffset());
+
+  EXPECT_EQ(Table.size(), Table2.size());
+  EXPECT_EQ(Table.capacity(), Table2.capacity());
+  // EXPECT_EQ(Table.Buckets, Table2.Buckets);
+  // EXPECT_EQ(Table.Present, Table2.Present);
+  // EXPECT_EQ(Table.Deleted, Table2.Deleted);
+}