272 lines · cpp
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-exception6//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 25using namespace llvm;26using namespace llvm::pdb;27using namespace llvm::support;28 29namespace {30 31struct IdentityHashTraits {32 uint32_t hashLookupKey(uint32_t N) const { return N; }33 uint32_t storageKeyToLookupKey(uint32_t N) const { return N; }34 uint32_t lookupKeyToStorageKey(uint32_t N) { return N; }35};36 37template <class T = uint32_t>38class HashTableInternals : public HashTable<T> {39public:40 using HashTable<T>::Buckets;41 using HashTable<T>::Present;42 using HashTable<T>::Deleted;43};44}45 46TEST(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 58TEST(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 sure64 // to add another value that is the equivalent to the first value modulo the65 // 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 80TEST(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 96TEST(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 filled102 // 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 122TEST(HashTableTest, Grow) {123 // So that we are independent of the load factor, `capacity` items, which is124 // guaranteed to trigger a grow. Then verify that the size is the same, the125 // 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 141TEST(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 169TEST(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 insertion177 // 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 209struct FooBar {210 uint32_t X;211 uint32_t Y;212 213 bool operator==(const FooBar &RHS) const {214 return X == RHS.X && Y == RHS.Y;215 }216};217 218struct FooBarHashTraits {219 std::vector<char> Buffer;220 221 FooBarHashTraits() { Buffer.push_back(0); }222 223 uint32_t hashLookupKey(StringRef S) const {224 return llvm::pdb::hashStringV1(S);225 }226 227 StringRef storageKeyToLookupKey(uint32_t N) const {228 if (N >= Buffer.size())229 return StringRef();230 231 return StringRef(Buffer.data() + N);232 }233 234 uint32_t lookupKeyToStorageKey(StringRef S) {235 uint32_t N = Buffer.size();236 llvm::append_range(Buffer, S);237 Buffer.push_back('\0');238 return N;239 }240};241 242TEST(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