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/PDB/Native/HashTable.h"
14 #include "llvm/Support/BinaryByteStream.h"
15 #include "llvm/Support/BinaryStreamReader.h"
16 #include "llvm/Support/BinaryStreamWriter.h"
17 
18 #include <vector>
19 
20 using namespace llvm;
21 using namespace llvm::pdb;
22 using namespace llvm::support;
23 
24 namespace {
25 class HashTableInternals : public HashTable {
26 public:
27   using HashTable::Buckets;
28   using HashTable::Present;
29   using HashTable::Deleted;
30 };
31 }
32 
33 TEST(HashTableTest, TestSimple) {
34   HashTable Table;
35   EXPECT_EQ(0u, Table.size());
36   EXPECT_GT(Table.capacity(), 0u);
37 
38   Table.set(3, 7);
39   EXPECT_EQ(1u, Table.size());
40   ASSERT_NE(Table.end(), Table.find(3));
41   EXPECT_EQ(7u, Table.get(3));
42 }
43 
44 TEST(HashTableTest, TestCollision) {
45   HashTable Table;
46   EXPECT_EQ(0u, Table.size());
47   EXPECT_GT(Table.capacity(), 0u);
48 
49   // We use knowledge of the hash table's implementation details to make sure
50   // to add another value that is the equivalent to the first value modulo the
51   // hash table's capacity.
52   uint32_t N1 = Table.capacity() + 1;
53   uint32_t N2 = 2 * N1;
54 
55   Table.set(N1, 7);
56   Table.set(N2, 12);
57   EXPECT_EQ(2u, Table.size());
58   ASSERT_NE(Table.end(), Table.find(N1));
59   ASSERT_NE(Table.end(), Table.find(N2));
60 
61   EXPECT_EQ(7u, Table.get(N1));
62   EXPECT_EQ(12u, Table.get(N2));
63 }
64 
65 TEST(HashTableTest, TestRemove) {
66   HashTable Table;
67   EXPECT_EQ(0u, Table.size());
68   EXPECT_GT(Table.capacity(), 0u);
69 
70   Table.set(1, 2);
71   Table.set(3, 4);
72   EXPECT_EQ(2u, Table.size());
73   ASSERT_NE(Table.end(), Table.find(1));
74   ASSERT_NE(Table.end(), Table.find(3));
75 
76   EXPECT_EQ(2u, Table.get(1));
77   EXPECT_EQ(4u, Table.get(3));
78 
79   Table.remove(1u);
80   EXPECT_EQ(1u, Table.size());
81   EXPECT_EQ(Table.end(), Table.find(1));
82   ASSERT_NE(Table.end(), Table.find(3));
83   EXPECT_EQ(4u, Table.get(3));
84 }
85 
86 TEST(HashTableTest, TestCollisionAfterMultipleProbes) {
87   HashTable 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(N1, 7);
99   Table.set(N2, 11);
100   Table.set(N3, 13);
101   EXPECT_EQ(3u, Table.size());
102   ASSERT_NE(Table.end(), Table.find(N1));
103   ASSERT_NE(Table.end(), Table.find(N2));
104   ASSERT_NE(Table.end(), Table.find(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   // Remove the one that had been filled in the middle, then insert another one
111   // with a collision.  It should fill the newly emptied slot.
112   Table.remove(N2);
113   uint32_t N4 = N1 * 3;
114   Table.set(N4, 17);
115   EXPECT_EQ(3u, Table.size());
116   ASSERT_NE(Table.end(), Table.find(N1));
117   ASSERT_NE(Table.end(), Table.find(N3));
118   ASSERT_NE(Table.end(), Table.find(N4));
119 
120   EXPECT_EQ(7u, Table.get(N1));
121   EXPECT_EQ(13u, Table.get(N3));
122   EXPECT_EQ(17u, Table.get(N4));
123 }
124 
125 TEST(HashTableTest, Grow) {
126   // So that we are independent of the load factor, `capacity` items, which is
127   // guaranteed to trigger a grow.  Then verify that the size is the same, the
128   // capacity is larger, and all the original items are still in the table.
129 
130   HashTable Table;
131   uint32_t OldCapacity = Table.capacity();
132   for (uint32_t I = 0; I < OldCapacity; ++I) {
133     Table.set(OldCapacity + I * 2 + 1, I * 2 + 3);
134   }
135   EXPECT_EQ(OldCapacity, Table.size());
136   EXPECT_GT(Table.capacity(), OldCapacity);
137   for (uint32_t I = 0; I < OldCapacity; ++I) {
138     ASSERT_NE(Table.end(), Table.find(OldCapacity + I * 2 + 1));
139     EXPECT_EQ(I * 2 + 3, Table.get(OldCapacity + I * 2 + 1));
140   }
141 }
142 
143 TEST(HashTableTest, Serialization) {
144   HashTableInternals Table;
145   uint32_t Cap = Table.capacity();
146   for (uint32_t I = 0; I < Cap; ++I) {
147     Table.set(Cap + I * 2 + 1, I * 2 + 3);
148   }
149 
150   std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
151   MutableBinaryByteStream Stream(Buffer, little);
152   BinaryStreamWriter Writer(Stream);
153   EXPECT_NO_ERROR(Table.commit(Writer));
154   // We should have written precisely the number of bytes we calculated earlier.
155   EXPECT_EQ(Buffer.size(), Writer.getOffset());
156 
157   HashTableInternals Table2;
158   BinaryStreamReader Reader(Stream);
159   EXPECT_NO_ERROR(Table2.load(Reader));
160   // We should have read precisely the number of bytes we calculated earlier.
161   EXPECT_EQ(Buffer.size(), Reader.getOffset());
162 
163   EXPECT_EQ(Table.size(), Table2.size());
164   EXPECT_EQ(Table.capacity(), Table2.capacity());
165   EXPECT_EQ(Table.Buckets, Table2.Buckets);
166   EXPECT_EQ(Table.Present, Table2.Present);
167   EXPECT_EQ(Table.Deleted, Table2.Deleted);
168 }
169