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