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 #include "llvm/DebugInfo/PDB/Native/NamedStreamMap.h"
12 #include "llvm/Support/BinaryByteStream.h"
13 #include "llvm/Support/BinaryStreamReader.h"
14 #include "llvm/Support/BinaryStreamWriter.h"
15 #include "llvm/Testing/Support/Error.h"
16 
17 #include "gtest/gtest.h"
18 
19 #include <vector>
20 
21 using namespace llvm;
22 using namespace llvm::pdb;
23 using namespace llvm::support;
24 
25 namespace {
26 class HashTableInternals : public HashTable {
27 public:
28   using HashTable::Buckets;
29   using HashTable::Present;
30   using HashTable::Deleted;
31 };
32 }
33 
34 TEST(HashTableTest, TestSimple) {
35   HashTable Table;
36   EXPECT_EQ(0u, Table.size());
37   EXPECT_GT(Table.capacity(), 0u);
38 
39   Table.set(3, 7);
40   EXPECT_EQ(1u, Table.size());
41   ASSERT_NE(Table.end(), Table.find(3));
42   EXPECT_EQ(7u, Table.get(3));
43 }
44 
45 TEST(HashTableTest, TestCollision) {
46   HashTable Table;
47   EXPECT_EQ(0u, Table.size());
48   EXPECT_GT(Table.capacity(), 0u);
49 
50   // We use knowledge of the hash table's implementation details to make sure
51   // to add another value that is the equivalent to the first value modulo the
52   // hash table's capacity.
53   uint32_t N1 = Table.capacity() + 1;
54   uint32_t N2 = 2 * N1;
55 
56   Table.set(N1, 7);
57   Table.set(N2, 12);
58   EXPECT_EQ(2u, Table.size());
59   ASSERT_NE(Table.end(), Table.find(N1));
60   ASSERT_NE(Table.end(), Table.find(N2));
61 
62   EXPECT_EQ(7u, Table.get(N1));
63   EXPECT_EQ(12u, Table.get(N2));
64 }
65 
66 TEST(HashTableTest, TestRemove) {
67   HashTable Table;
68   EXPECT_EQ(0u, Table.size());
69   EXPECT_GT(Table.capacity(), 0u);
70 
71   Table.set(1, 2);
72   Table.set(3, 4);
73   EXPECT_EQ(2u, Table.size());
74   ASSERT_NE(Table.end(), Table.find(1));
75   ASSERT_NE(Table.end(), Table.find(3));
76 
77   EXPECT_EQ(2u, Table.get(1));
78   EXPECT_EQ(4u, Table.get(3));
79 
80   Table.remove(1u);
81   EXPECT_EQ(1u, Table.size());
82   EXPECT_EQ(Table.end(), Table.find(1));
83   ASSERT_NE(Table.end(), Table.find(3));
84   EXPECT_EQ(4u, Table.get(3));
85 }
86 
87 TEST(HashTableTest, TestCollisionAfterMultipleProbes) {
88   HashTable Table;
89   EXPECT_EQ(0u, Table.size());
90   EXPECT_GT(Table.capacity(), 0u);
91 
92   // Probing looks for the first available slot.  A slot may already be filled
93   // as a result of an item with a *different* hash value already being there.
94   // Test that when this happens, the probe still finds the value.
95   uint32_t N1 = Table.capacity() + 1;
96   uint32_t N2 = N1 + 1;
97   uint32_t N3 = 2 * N1;
98 
99   Table.set(N1, 7);
100   Table.set(N2, 11);
101   Table.set(N3, 13);
102   EXPECT_EQ(3u, Table.size());
103   ASSERT_NE(Table.end(), Table.find(N1));
104   ASSERT_NE(Table.end(), Table.find(N2));
105   ASSERT_NE(Table.end(), Table.find(N3));
106 
107   EXPECT_EQ(7u, Table.get(N1));
108   EXPECT_EQ(11u, Table.get(N2));
109   EXPECT_EQ(13u, Table.get(N3));
110 
111   // Remove the one that had been filled in the middle, then insert another one
112   // with a collision.  It should fill the newly emptied slot.
113   Table.remove(N2);
114   uint32_t N4 = N1 * 3;
115   Table.set(N4, 17);
116   EXPECT_EQ(3u, Table.size());
117   ASSERT_NE(Table.end(), Table.find(N1));
118   ASSERT_NE(Table.end(), Table.find(N3));
119   ASSERT_NE(Table.end(), Table.find(N4));
120 
121   EXPECT_EQ(7u, Table.get(N1));
122   EXPECT_EQ(13u, Table.get(N3));
123   EXPECT_EQ(17u, Table.get(N4));
124 }
125 
126 TEST(HashTableTest, Grow) {
127   // So that we are independent of the load factor, `capacity` items, which is
128   // guaranteed to trigger a grow.  Then verify that the size is the same, the
129   // capacity is larger, and all the original items are still in the table.
130 
131   HashTable Table;
132   uint32_t OldCapacity = Table.capacity();
133   for (uint32_t I = 0; I < OldCapacity; ++I) {
134     Table.set(OldCapacity + I * 2 + 1, I * 2 + 3);
135   }
136   EXPECT_EQ(OldCapacity, Table.size());
137   EXPECT_GT(Table.capacity(), OldCapacity);
138   for (uint32_t I = 0; I < OldCapacity; ++I) {
139     ASSERT_NE(Table.end(), Table.find(OldCapacity + I * 2 + 1));
140     EXPECT_EQ(I * 2 + 3, Table.get(OldCapacity + I * 2 + 1));
141   }
142 }
143 
144 TEST(HashTableTest, Serialization) {
145   HashTableInternals Table;
146   uint32_t Cap = Table.capacity();
147   for (uint32_t I = 0; I < Cap; ++I) {
148     Table.set(Cap + I * 2 + 1, I * 2 + 3);
149   }
150 
151   std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
152   MutableBinaryByteStream Stream(Buffer, little);
153   BinaryStreamWriter Writer(Stream);
154   EXPECT_THAT_ERROR(Table.commit(Writer), Succeeded());
155   // We should have written precisely the number of bytes we calculated earlier.
156   EXPECT_EQ(Buffer.size(), Writer.getOffset());
157 
158   HashTableInternals Table2;
159   BinaryStreamReader Reader(Stream);
160   EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded());
161   // We should have read precisely the number of bytes we calculated earlier.
162   EXPECT_EQ(Buffer.size(), Reader.getOffset());
163 
164   EXPECT_EQ(Table.size(), Table2.size());
165   EXPECT_EQ(Table.capacity(), Table2.capacity());
166   EXPECT_EQ(Table.Buckets, Table2.Buckets);
167   EXPECT_EQ(Table.Present, Table2.Present);
168   EXPECT_EQ(Table.Deleted, Table2.Deleted);
169 }
170 
171 TEST(HashTableTest, NamedStreamMap) {
172   std::vector<StringRef> Streams = {"One",  "Two", "Three", "Four",
173                                     "Five", "Six", "Seven"};
174   StringMap<uint32_t> ExpectedIndices;
175   for (uint32_t I = 0; I < Streams.size(); ++I)
176     ExpectedIndices[Streams[I]] = I + 1;
177 
178   // To verify the hash table actually works, we want to verify that insertion
179   // order doesn't matter.  So try inserting in every possible order of 7 items.
180   do {
181     NamedStreamMap NSM;
182     for (StringRef S : Streams)
183       NSM.set(S, ExpectedIndices[S]);
184 
185     EXPECT_EQ(Streams.size(), NSM.size());
186 
187     uint32_t N;
188     EXPECT_TRUE(NSM.get("One", N));
189     EXPECT_EQ(1U, N);
190 
191     EXPECT_TRUE(NSM.get("Two", N));
192     EXPECT_EQ(2U, N);
193 
194     EXPECT_TRUE(NSM.get("Three", N));
195     EXPECT_EQ(3U, N);
196 
197     EXPECT_TRUE(NSM.get("Four", N));
198     EXPECT_EQ(4U, N);
199 
200     EXPECT_TRUE(NSM.get("Five", N));
201     EXPECT_EQ(5U, N);
202 
203     EXPECT_TRUE(NSM.get("Six", N));
204     EXPECT_EQ(6U, N);
205 
206     EXPECT_TRUE(NSM.get("Seven", N));
207     EXPECT_EQ(7U, N);
208   } while (std::next_permutation(Streams.begin(), Streams.end()));
209 }
210