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