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