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 {
hashLookupKey__anona8cee3d60111::IdentityHashTraits31 uint32_t hashLookupKey(uint32_t N) const { return N; }
storageKeyToLookupKey__anona8cee3d60111::IdentityHashTraits32 uint32_t storageKeyToLookupKey(uint32_t N) const { return N; }
lookupKeyToStorageKey__anona8cee3d60111::IdentityHashTraits33 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
TEST(HashTableTest,TestSimple)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
TEST(HashTableTest,TestCollision)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
TEST(HashTableTest,TestRemove)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
TEST(HashTableTest,TestCollisionAfterMultipleProbes)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
TEST(HashTableTest,Grow)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
TEST(HashTableTest,Serialization)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
TEST(HashTableTest,NamedStreamMap)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
operator ==FooBar212 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
FooBarHashTraitsFooBarHashTraits220 FooBarHashTraits() { Buffer.push_back(0); }
221
hashLookupKeyFooBarHashTraits222 uint32_t hashLookupKey(StringRef S) const {
223 return llvm::pdb::hashStringV1(S);
224 }
225
storageKeyToLookupKeyFooBarHashTraits226 StringRef storageKeyToLookupKey(uint32_t N) const {
227 if (N >= Buffer.size())
228 return StringRef();
229
230 return StringRef(Buffer.data() + N);
231 }
232
lookupKeyToStorageKeyFooBarHashTraits233 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
TEST(HashTableTest,NonTrivialValueType)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 }
271