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 "ErrorChecking.h"
11 #include "gtest/gtest.h"
12 
13 #include "llvm/DebugInfo/MSF/ByteStream.h"
14 #include "llvm/DebugInfo/MSF/StreamReader.h"
15 #include "llvm/DebugInfo/MSF/StreamWriter.h"
16 #include "llvm/DebugInfo/PDB/Native/HashTable.h"
17 
18 #include <vector>
19 
20 using namespace llvm;
21 using namespace llvm::pdb;
22 
23 namespace {
24 class HashTableInternals : public HashTable {
25 public:
26   using HashTable::Buckets;
27   using HashTable::Present;
28   using HashTable::Deleted;
29 };
30 }
31 
32 TEST(HashTableTest, TestSimple) {
33   HashTable Table;
34   EXPECT_EQ(0u, Table.size());
35   EXPECT_GT(Table.capacity(), 0u);
36 
37   Table.set(3, 7);
38   EXPECT_EQ(1u, Table.size());
39   ASSERT_NE(Table.end(), Table.find(3));
40   EXPECT_EQ(7u, Table.get(3));
41 }
42 
43 TEST(HashTableTest, TestCollision) {
44   HashTable Table;
45   EXPECT_EQ(0u, Table.size());
46   EXPECT_GT(Table.capacity(), 0u);
47 
48   // We use knowledge of the hash table's implementation details to make sure
49   // to add another value that is the equivalent to the first value modulo the
50   // hash table's capacity.
51   uint32_t N1 = Table.capacity() + 1;
52   uint32_t N2 = 2 * N1;
53 
54   Table.set(N1, 7);
55   Table.set(N2, 12);
56   EXPECT_EQ(2u, Table.size());
57   ASSERT_NE(Table.end(), Table.find(N1));
58   ASSERT_NE(Table.end(), Table.find(N2));
59 
60   EXPECT_EQ(7u, Table.get(N1));
61   EXPECT_EQ(12u, Table.get(N2));
62 }
63 
64 TEST(HashTableTest, TestRemove) {
65   HashTable Table;
66   EXPECT_EQ(0u, Table.size());
67   EXPECT_GT(Table.capacity(), 0u);
68 
69   Table.set(1, 2);
70   Table.set(3, 4);
71   EXPECT_EQ(2u, Table.size());
72   ASSERT_NE(Table.end(), Table.find(1));
73   ASSERT_NE(Table.end(), Table.find(3));
74 
75   EXPECT_EQ(2u, Table.get(1));
76   EXPECT_EQ(4u, Table.get(3));
77 
78   Table.remove(1u);
79   EXPECT_EQ(1u, Table.size());
80   EXPECT_EQ(Table.end(), Table.find(1));
81   ASSERT_NE(Table.end(), Table.find(3));
82   EXPECT_EQ(4u, Table.get(3));
83 }
84 
85 TEST(HashTableTest, TestCollisionAfterMultipleProbes) {
86   HashTable Table;
87   EXPECT_EQ(0u, Table.size());
88   EXPECT_GT(Table.capacity(), 0u);
89 
90   // Probing looks for the first available slot.  A slot may already be filled
91   // as a result of an item with a *different* hash value already being there.
92   // Test that when this happens, the probe still finds the value.
93   uint32_t N1 = Table.capacity() + 1;
94   uint32_t N2 = N1 + 1;
95   uint32_t N3 = 2 * N1;
96 
97   Table.set(N1, 7);
98   Table.set(N2, 11);
99   Table.set(N3, 13);
100   EXPECT_EQ(3u, Table.size());
101   ASSERT_NE(Table.end(), Table.find(N1));
102   ASSERT_NE(Table.end(), Table.find(N2));
103   ASSERT_NE(Table.end(), Table.find(N3));
104 
105   EXPECT_EQ(7u, Table.get(N1));
106   EXPECT_EQ(11u, Table.get(N2));
107   EXPECT_EQ(13u, Table.get(N3));
108 
109   // Remove the one that had been filled in the middle, then insert another one
110   // with a collision.  It should fill the newly emptied slot.
111   Table.remove(N2);
112   uint32_t N4 = N1 * 3;
113   Table.set(N4, 17);
114   EXPECT_EQ(3u, Table.size());
115   ASSERT_NE(Table.end(), Table.find(N1));
116   ASSERT_NE(Table.end(), Table.find(N3));
117   ASSERT_NE(Table.end(), Table.find(N4));
118 
119   EXPECT_EQ(7u, Table.get(N1));
120   EXPECT_EQ(13u, Table.get(N3));
121   EXPECT_EQ(17u, Table.get(N4));
122 }
123 
124 TEST(HashTableTest, Grow) {
125   // So that we are independent of the load factor, `capacity` items, which is
126   // guaranteed to trigger a grow.  Then verify that the size is the same, the
127   // capacity is larger, and all the original items are still in the table.
128 
129   HashTable Table;
130   uint32_t OldCapacity = Table.capacity();
131   for (uint32_t I = 0; I < OldCapacity; ++I) {
132     Table.set(OldCapacity + I * 2 + 1, I * 2 + 3);
133   }
134   EXPECT_EQ(OldCapacity, Table.size());
135   EXPECT_GT(Table.capacity(), OldCapacity);
136   for (uint32_t I = 0; I < OldCapacity; ++I) {
137     ASSERT_NE(Table.end(), Table.find(OldCapacity + I * 2 + 1));
138     EXPECT_EQ(I * 2 + 3, Table.get(OldCapacity + I * 2 + 1));
139   }
140 }
141 
142 TEST(HashTableTest, Serialization) {
143   HashTableInternals Table;
144   uint32_t Cap = Table.capacity();
145   for (uint32_t I = 0; I < Cap; ++I) {
146     Table.set(Cap + I * 2 + 1, I * 2 + 3);
147   }
148 
149   std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
150   msf::MutableByteStream Stream(Buffer);
151   msf::StreamWriter Writer(Stream);
152   EXPECT_NO_ERROR(Table.commit(Writer));
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   msf::StreamReader Reader(Stream);
158   EXPECT_NO_ERROR(Table2.load(Reader));
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