unittests/DebugInfo/PDB/HashTableTest.cpp

   1 //===- llvm/unittest/DebugInfo/PDB/HashTableTest.cpp ----------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/DebugInfo/PDB/Native/HashTable.h"
  10
  11 #include "llvm/DebugInfo/PDB/Native/Hash.h"
  12 #include "llvm/DebugInfo/PDB/Native/NamedStreamMap.h"
  13 #include "llvm/Support/Allocator.h"
  14 #include "llvm/Support/BinaryByteStream.h"
  15 #include "llvm/Support/BinaryStreamReader.h"
  16 #include "llvm/Support/BinaryStreamWriter.h"
  17 #include "llvm/Support/StringSaver.h"
  18 #include "llvm/Testing/Support/Error.h"
  19
  20 #include "gtest/gtest.h"
  21
  22 #include <vector>
  23
  24 using namespace llvm;
  25 using namespace llvm::pdb;
  26 using namespace llvm::support;
  27
  28 namespace {
  29
  30 class HashTableInternals : public HashTable<uint32_t> {
  31 public:
  32   using HashTable::Buckets;
  33   using HashTable::Present;
  34   using HashTable::Deleted;
  35 };
  36 }
  37
  38 TEST(HashTableTest, TestSimple) {
  39   HashTableInternals Table;
  40   EXPECT_EQ(0u, Table.size());
  41   EXPECT_GT(Table.capacity(), 0u);
  42
  43   Table.set_as(3u, 7);
  44   EXPECT_EQ(1u, Table.size());
  45   ASSERT_NE(Table.end(), Table.find_as(3u));
  46   EXPECT_EQ(7u, Table.get(3u));
  47 }
  48
  49 TEST(HashTableTest, TestCollision) {
  50   HashTableInternals Table;
  51   EXPECT_EQ(0u, Table.size());
  52   EXPECT_GT(Table.capacity(), 0u);
  53
  54   // We use knowledge of the hash table's implementation details to make sure
  55   // to add another value that is the equivalent to the first value modulo the
  56   // hash table's capacity.
  57   uint32_t N1 = Table.capacity() + 1;
  58   uint32_t N2 = 2 * N1;
  59
  60   Table.set_as(N1, 7);
  61   Table.set_as(N2, 12);
  62   EXPECT_EQ(2u, Table.size());
  63   ASSERT_NE(Table.end(), Table.find_as(N1));
  64   ASSERT_NE(Table.end(), Table.find_as(N2));
  65
  66   EXPECT_EQ(7u, Table.get(N1));
  67   EXPECT_EQ(12u, Table.get(N2));
  68 }
  69
  70 TEST(HashTableTest, TestRemove) {
  71   HashTableInternals Table;
  72   EXPECT_EQ(0u, Table.size());
  73   EXPECT_GT(Table.capacity(), 0u);
  74
  75   Table.set_as(1u, 2);
  76   Table.set_as(3u, 4);
  77   EXPECT_EQ(2u, Table.size());
  78   ASSERT_NE(Table.end(), Table.find_as(1u));
  79   ASSERT_NE(Table.end(), Table.find_as(3u));
  80
  81   EXPECT_EQ(2u, Table.get(1u));
  82   EXPECT_EQ(4u, Table.get(3u));
  83 }
  84
  85 TEST(HashTableTest, TestCollisionAfterMultipleProbes) {
  86   HashTableInternals Table;
  87   EXPECT_EQ(0u, Table.size());
  88   EXPECT_GT(Table.capacity(), 0u);
  89
  90   // Probing looks for the first available slot.  A slot may already be filled
  91   // as a result of an item with a *different* hash value already being there.
  92   // Test that when this happens, the probe still finds the value.
  93   uint32_t N1 = Table.capacity() + 1;
  94   uint32_t N2 = N1 + 1;
  95   uint32_t N3 = 2 * N1;
  96
  97   Table.set_as(N1, 7);
  98   Table.set_as(N2, 11);
  99   Table.set_as(N3, 13);
 100   EXPECT_EQ(3u, Table.size());
 101   ASSERT_NE(Table.end(), Table.find_as(N1));
 102   ASSERT_NE(Table.end(), Table.find_as(N2));
 103   ASSERT_NE(Table.end(), Table.find_as(N3));
 104
 105   EXPECT_EQ(7u, Table.get(N1));
 106   EXPECT_EQ(11u, Table.get(N2));
 107   EXPECT_EQ(13u, Table.get(N3));
 108 }
 109
 110 TEST(HashTableTest, Grow) {
 111   // So that we are independent of the load factor, `capacity` items, which is
 112   // guaranteed to trigger a grow.  Then verify that the size is the same, the
 113   // capacity is larger, and all the original items are still in the table.
 114
 115   HashTableInternals Table;
 116   uint32_t OldCapacity = Table.capacity();
 117   for (uint32_t I = 0; I < OldCapacity; ++I) {
 118     Table.set_as(OldCapacity + I * 2 + 1, I * 2 + 3);
 119   }
 120   EXPECT_EQ(OldCapacity, Table.size());
 121   EXPECT_GT(Table.capacity(), OldCapacity);
 122   for (uint32_t I = 0; I < OldCapacity; ++I) {
 123     ASSERT_NE(Table.end(), Table.find_as(OldCapacity + I * 2 + 1));
 124     EXPECT_EQ(I * 2 + 3, Table.get(OldCapacity + I * 2 + 1));
 125   }
 126 }
 127
 128 TEST(HashTableTest, Serialization) {
 129   HashTableInternals Table;
 130   uint32_t Cap = Table.capacity();
 131   for (uint32_t I = 0; I < Cap; ++I) {
 132     Table.set_as(Cap + I * 2 + 1, I * 2 + 3);
 133   }
 134
 135   std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
 136   MutableBinaryByteStream Stream(Buffer, little);
 137   BinaryStreamWriter Writer(Stream);
 138   EXPECT_THAT_ERROR(Table.commit(Writer), Succeeded());
 139   // We should have written precisely the number of bytes we calculated earlier.
 140   EXPECT_EQ(Buffer.size(), Writer.getOffset());
 141
 142   HashTableInternals Table2;
 143   BinaryStreamReader Reader(Stream);
 144   EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded());
 145   // We should have read precisely the number of bytes we calculated earlier.
 146   EXPECT_EQ(Buffer.size(), Reader.getOffset());
 147
 148   EXPECT_EQ(Table.size(), Table2.size());
 149   EXPECT_EQ(Table.capacity(), Table2.capacity());
 150   EXPECT_EQ(Table.Buckets, Table2.Buckets);
 151   EXPECT_EQ(Table.Present, Table2.Present);
 152   EXPECT_EQ(Table.Deleted, Table2.Deleted);
 153 }
 154
 155 TEST(HashTableTest, NamedStreamMap) {
 156   std::vector<StringRef> Streams = {"One",  "Two", "Three", "Four",
 157                                     "Five", "Six", "Seven"};
 158   StringMap<uint32_t> ExpectedIndices;
 159   for (uint32_t I = 0; I < Streams.size(); ++I)
 160     ExpectedIndices[Streams[I]] = I + 1;
 161
 162   // To verify the hash table actually works, we want to verify that insertion
 163   // order doesn't matter.  So try inserting in every possible order of 7 items.
 164   do {
 165     NamedStreamMap NSM;
 166     for (StringRef S : Streams)
 167       NSM.set(S, ExpectedIndices[S]);
 168
 169     EXPECT_EQ(Streams.size(), NSM.size());
 170
 171     uint32_t N;
 172     EXPECT_TRUE(NSM.get("One", N));
 173     EXPECT_EQ(1U, N);
 174
 175     EXPECT_TRUE(NSM.get("Two", N));
 176     EXPECT_EQ(2U, N);
 177
 178     EXPECT_TRUE(NSM.get("Three", N));
 179     EXPECT_EQ(3U, N);
 180
 181     EXPECT_TRUE(NSM.get("Four", N));
 182     EXPECT_EQ(4U, N);
 183
 184     EXPECT_TRUE(NSM.get("Five", N));
 185     EXPECT_EQ(5U, N);
 186
 187     EXPECT_TRUE(NSM.get("Six", N));
 188     EXPECT_EQ(6U, N);
 189
 190     EXPECT_TRUE(NSM.get("Seven", N));
 191     EXPECT_EQ(7U, N);
 192   } while (std::next_permutation(Streams.begin(), Streams.end()));
 193 }
 194
 195 namespace {
 196 struct FooBar {
 197   uint32_t X;
 198   uint32_t Y;
 199 };
 200
 201 } // namespace
 202
 203 namespace llvm {
 204 namespace pdb {
 205 template <> struct PdbHashTraits<FooBar> {
 206   std::vector<char> Buffer;
 207
 208   PdbHashTraits() { Buffer.push_back(0); }
 209
 210   uint32_t hashLookupKey(StringRef S) const {
 211     return llvm::pdb::hashStringV1(S);
 212   }
 213
 214   StringRef storageKeyToLookupKey(uint32_t N) const {
 215     if (N >= Buffer.size())
 216       return StringRef();
 217
 218     return StringRef(Buffer.data() + N);
 219   }
 220
 221   uint32_t lookupKeyToStorageKey(StringRef S) {
 222     uint32_t N = Buffer.size();
 223     Buffer.insert(Buffer.end(), S.begin(), S.end());
 224     Buffer.push_back('\0');
 225     return N;
 226   }
 227 };
 228 } // namespace pdb
 229 } // namespace llvm
 230
 231 TEST(HashTableTest, NonTrivialValueType) {
 232   HashTable<FooBar> Table;
 233   uint32_t Cap = Table.capacity();
 234   for (uint32_t I = 0; I < Cap; ++I) {
 235     FooBar F;
 236     F.X = I;
 237     F.Y = I + 1;
 238     Table.set_as(utostr(I), F);
 239   }
 240
 241   std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
 242   MutableBinaryByteStream Stream(Buffer, little);
 243   BinaryStreamWriter Writer(Stream);
 244   EXPECT_THAT_ERROR(Table.commit(Writer), Succeeded());
 245   // We should have written precisely the number of bytes we calculated earlier.
 246   EXPECT_EQ(Buffer.size(), Writer.getOffset());
 247
 248   HashTable<FooBar> Table2;
 249   BinaryStreamReader Reader(Stream);
 250   EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded());
 251   // We should have read precisely the number of bytes we calculated earlier.
 252   EXPECT_EQ(Buffer.size(), Reader.getOffset());
 253
 254   EXPECT_EQ(Table.size(), Table2.size());
 255   EXPECT_EQ(Table.capacity(), Table2.capacity());
 256   // EXPECT_EQ(Table.Buckets, Table2.Buckets);
 257   // EXPECT_EQ(Table.Present, Table2.Present);
 258   // EXPECT_EQ(Table.Deleted, Table2.Deleted);
 259 }