Index: llvm/include/llvm/DebugInfo/PDB/Native/HashTable.h =================================================================== --- llvm/include/llvm/DebugInfo/PDB/Native/HashTable.h +++ llvm/include/llvm/DebugInfo/PDB/Native/HashTable.h @@ -31,21 +31,21 @@ Error readSparseBitVector(BinaryStreamReader &Stream, SparseBitVector<> &V); Error writeSparseBitVector(BinaryStreamWriter &Writer, SparseBitVector<> &Vec); -template class HashTable; +template class HashTable; -template +template class HashTableIterator - : public iterator_facade_base, + : public iterator_facade_base, std::forward_iterator_tag, std::pair> { - friend HashTable; + friend HashTable; - HashTableIterator(const HashTable &Map, uint32_t Index, + HashTableIterator(const HashTable &Map, uint32_t Index, bool IsEnd) : Map(&Map), Index(Index), IsEnd(IsEnd) {} public: - HashTableIterator(const HashTable &Map) : Map(&Map) { + HashTableIterator(const HashTable &Map) : Map(&Map) { int I = Map.Present.find_first(); if (I == -1) { Index = 0; @@ -87,22 +87,14 @@ bool isEnd() const { return IsEnd; } uint32_t index() const { return Index; } - const HashTable *Map; + const HashTable *Map; uint32_t Index; bool IsEnd; }; -template struct PdbHashTraits {}; - -template <> struct PdbHashTraits { - uint32_t hashLookupKey(uint32_t N) const { return N; } - uint32_t storageKeyToLookupKey(uint32_t N) const { return N; } - uint32_t lookupKeyToStorageKey(uint32_t N) { return N; } -}; - -template > +template class HashTable { - using iterator = HashTableIterator; + using iterator = HashTableIterator; friend iterator; struct Header { @@ -114,9 +106,7 @@ public: HashTable() { Buckets.resize(8); } - - explicit HashTable(TraitsT Traits) : HashTable(8, std::move(Traits)) {} - HashTable(uint32_t Capacity, TraitsT Traits) : Traits(Traits) { + explicit HashTable(uint32_t Capacity) { Buckets.resize(Capacity); } @@ -221,7 +211,8 @@ /// Find the entry whose key has the specified hash value, using the specified /// traits defining hash function and equality. - template iterator find_as(const Key &K) const { + template + iterator find_as(const Key &K, TraitsT &Traits) const { uint32_t H = Traits.hashLookupKey(K) % capacity(); uint32_t I = H; Optional FirstUnused; @@ -252,12 +243,14 @@ /// Set the entry using a key type that the specified Traits can convert /// from a real key to an internal key. - template bool set_as(const Key &K, ValueT V) { - return set_as_internal(K, std::move(V), None); + template + bool set_as(const Key &K, ValueT V, TraitsT &Traits) { + return set_as_internal(K, std::move(V), Traits, None); } - template ValueT get(const Key &K) const { - auto Iter = find_as(K); + template + ValueT get(const Key &K, TraitsT &Traits) const { + auto Iter = find_as(K, Traits); assert(Iter != end()); return (*Iter).second; } @@ -266,7 +259,6 @@ bool isPresent(uint32_t K) const { return Present.test(K); } bool isDeleted(uint32_t K) const { return Deleted.test(K); } - TraitsT Traits; BucketList Buckets; mutable SparseBitVector<> Present; mutable SparseBitVector<> Deleted; @@ -274,9 +266,10 @@ private: /// Set the entry using a key type that the specified Traits can convert /// from a real key to an internal key. - template - bool set_as_internal(const Key &K, ValueT V, Optional InternalKey) { - auto Entry = find_as(K); + template + bool set_as_internal(const Key &K, ValueT V, TraitsT &Traits, + Optional InternalKey) { + auto Entry = find_as(K, Traits); if (Entry != end()) { assert(isPresent(Entry.index())); assert(Traits.storageKeyToLookupKey(Buckets[Entry.index()].first) == K); @@ -293,15 +286,16 @@ Present.set(Entry.index()); Deleted.reset(Entry.index()); - grow(); + grow(Traits); - assert((find_as(K)) != end()); + assert((find_as(K, Traits)) != end()); return true; } static uint32_t maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; } - void grow() { + template + void grow(TraitsT &Traits) { uint32_t S = size(); uint32_t MaxLoad = maxLoad(capacity()); if (S < maxLoad(capacity())) @@ -313,10 +307,11 @@ // Growing requires rebuilding the table and re-hashing every item. Make a // copy with a larger capacity, insert everything into the copy, then swap // it in. - HashTable NewMap(NewCapacity, Traits); + HashTable NewMap(NewCapacity); for (auto I : Present) { auto LookupKey = Traits.storageKeyToLookupKey(Buckets[I].first); - NewMap.set_as_internal(LookupKey, Buckets[I].second, Buckets[I].first); + NewMap.set_as_internal(LookupKey, Buckets[I].second, Traits, + Buckets[I].first); } Buckets.swap(NewMap.Buckets); Index: llvm/include/llvm/DebugInfo/PDB/Native/NamedStreamMap.h =================================================================== --- llvm/include/llvm/DebugInfo/PDB/Native/NamedStreamMap.h +++ llvm/include/llvm/DebugInfo/PDB/Native/NamedStreamMap.h @@ -59,7 +59,7 @@ NamedStreamMapTraits HashTraits; /// Closed hash table from Offset -> StreamNumber, where Offset is the offset /// of the stream name in NamesBuffer. - HashTable OffsetIndexMap; + HashTable OffsetIndexMap; /// Buffer of string data. std::vector NamesBuffer; Index: llvm/include/llvm/DebugInfo/PDB/Native/PDBFileBuilder.h =================================================================== --- llvm/include/llvm/DebugInfo/PDB/Native/PDBFileBuilder.h +++ llvm/include/llvm/DebugInfo/PDB/Native/PDBFileBuilder.h @@ -97,7 +97,7 @@ PDBStringTableBuilder Strings; StringTableHashTraits InjectedSourceHashTraits; - HashTable InjectedSourceTable; + HashTable InjectedSourceTable; SmallVector InjectedSources; Index: llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp =================================================================== --- llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp +++ llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp @@ -46,8 +46,7 @@ return NS->appendStringData(S); } -NamedStreamMap::NamedStreamMap() - : HashTraits(*this), OffsetIndexMap(1, HashTraits) {} +NamedStreamMap::NamedStreamMap() : HashTraits(*this), OffsetIndexMap(1) {} Error NamedStreamMap::load(BinaryStreamReader &Stream) { uint32_t StringBufferSize; @@ -99,7 +98,7 @@ } bool NamedStreamMap::get(StringRef Stream, uint32_t &StreamNo) const { - auto Iter = OffsetIndexMap.find_as(Stream); + auto Iter = OffsetIndexMap.find_as(Stream, HashTraits); if (Iter == OffsetIndexMap.end()) return false; StreamNo = (*Iter).second; @@ -123,5 +122,5 @@ } void NamedStreamMap::set(StringRef Stream, uint32_t StreamNo) { - OffsetIndexMap.set_as(Stream, support::ulittle32_t(StreamNo)); + OffsetIndexMap.set_as(Stream, support::ulittle32_t(StreamNo), HashTraits); } Index: llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp =================================================================== --- llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp +++ llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp @@ -34,7 +34,7 @@ PDBFileBuilder::PDBFileBuilder(BumpPtrAllocator &Allocator) : Allocator(Allocator), InjectedSourceHashTraits(Strings), - InjectedSourceTable(2, InjectedSourceHashTraits) {} + InjectedSourceTable(2) {} PDBFileBuilder::~PDBFileBuilder() {} @@ -189,7 +189,8 @@ static_cast(PdbRaw_SrcHeaderBlockVer::SrcVerOne); Entry.CRC = CRC.getCRC(); StringRef VName = getStringTableBuilder().getStringForId(IS.VNameIndex); - InjectedSourceTable.set_as(VName, std::move(Entry)); + InjectedSourceTable.set_as(VName, std::move(Entry), + InjectedSourceHashTraits); } uint32_t SrcHeaderBlockSize = Index: llvm/unittests/DebugInfo/PDB/HashTableTest.cpp =================================================================== --- llvm/unittests/DebugInfo/PDB/HashTableTest.cpp +++ llvm/unittests/DebugInfo/PDB/HashTableTest.cpp @@ -27,27 +27,35 @@ namespace { -class HashTableInternals : public HashTable { +struct IdentityHashTraits { + uint32_t hashLookupKey(uint32_t N) const { return N; } + uint32_t storageKeyToLookupKey(uint32_t N) const { return N; } + uint32_t lookupKeyToStorageKey(uint32_t N) { return N; } +}; + +template +class HashTableInternals : public HashTable { public: - using HashTable::Buckets; - using HashTable::Present; - using HashTable::Deleted; + using HashTable::Buckets; + using HashTable::Present; + using HashTable::Deleted; }; } TEST(HashTableTest, TestSimple) { - HashTableInternals Table; + HashTableInternals<> Table; EXPECT_EQ(0u, Table.size()); EXPECT_GT(Table.capacity(), 0u); - Table.set_as(3u, 7); + IdentityHashTraits Traits; + Table.set_as(3u, 7, Traits); EXPECT_EQ(1u, Table.size()); - ASSERT_NE(Table.end(), Table.find_as(3u)); - EXPECT_EQ(7u, Table.get(3u)); + ASSERT_NE(Table.end(), Table.find_as(3u, Traits)); + EXPECT_EQ(7u, Table.get(3u, Traits)); } TEST(HashTableTest, TestCollision) { - HashTableInternals Table; + HashTableInternals<> Table; EXPECT_EQ(0u, Table.size()); EXPECT_GT(Table.capacity(), 0u); @@ -57,33 +65,35 @@ uint32_t N1 = Table.capacity() + 1; uint32_t N2 = 2 * N1; - Table.set_as(N1, 7); - Table.set_as(N2, 12); + IdentityHashTraits Traits; + Table.set_as(N1, 7, Traits); + Table.set_as(N2, 12, Traits); EXPECT_EQ(2u, Table.size()); - ASSERT_NE(Table.end(), Table.find_as(N1)); - ASSERT_NE(Table.end(), Table.find_as(N2)); + ASSERT_NE(Table.end(), Table.find_as(N1, Traits)); + ASSERT_NE(Table.end(), Table.find_as(N2, Traits)); - EXPECT_EQ(7u, Table.get(N1)); - EXPECT_EQ(12u, Table.get(N2)); + EXPECT_EQ(7u, Table.get(N1, Traits)); + EXPECT_EQ(12u, Table.get(N2, Traits)); } TEST(HashTableTest, TestRemove) { - HashTableInternals Table; + HashTableInternals<> Table; EXPECT_EQ(0u, Table.size()); EXPECT_GT(Table.capacity(), 0u); - Table.set_as(1u, 2); - Table.set_as(3u, 4); + IdentityHashTraits Traits; + Table.set_as(1u, 2, Traits); + Table.set_as(3u, 4, Traits); EXPECT_EQ(2u, Table.size()); - ASSERT_NE(Table.end(), Table.find_as(1u)); - ASSERT_NE(Table.end(), Table.find_as(3u)); + ASSERT_NE(Table.end(), Table.find_as(1u, Traits)); + ASSERT_NE(Table.end(), Table.find_as(3u, Traits)); - EXPECT_EQ(2u, Table.get(1u)); - EXPECT_EQ(4u, Table.get(3u)); + EXPECT_EQ(2u, Table.get(1u, Traits)); + EXPECT_EQ(4u, Table.get(3u, Traits)); } TEST(HashTableTest, TestCollisionAfterMultipleProbes) { - HashTableInternals Table; + HashTableInternals<> Table; EXPECT_EQ(0u, Table.size()); EXPECT_GT(Table.capacity(), 0u); @@ -94,17 +104,18 @@ uint32_t N2 = N1 + 1; uint32_t N3 = 2 * N1; - Table.set_as(N1, 7); - Table.set_as(N2, 11); - Table.set_as(N3, 13); + IdentityHashTraits Traits; + Table.set_as(N1, 7, Traits); + Table.set_as(N2, 11, Traits); + Table.set_as(N3, 13, Traits); EXPECT_EQ(3u, Table.size()); - ASSERT_NE(Table.end(), Table.find_as(N1)); - ASSERT_NE(Table.end(), Table.find_as(N2)); - ASSERT_NE(Table.end(), Table.find_as(N3)); + ASSERT_NE(Table.end(), Table.find_as(N1, Traits)); + ASSERT_NE(Table.end(), Table.find_as(N2, Traits)); + ASSERT_NE(Table.end(), Table.find_as(N3, Traits)); - EXPECT_EQ(7u, Table.get(N1)); - EXPECT_EQ(11u, Table.get(N2)); - EXPECT_EQ(13u, Table.get(N3)); + EXPECT_EQ(7u, Table.get(N1, Traits)); + EXPECT_EQ(11u, Table.get(N2, Traits)); + EXPECT_EQ(13u, Table.get(N3, Traits)); } TEST(HashTableTest, Grow) { @@ -112,24 +123,26 @@ // guaranteed to trigger a grow. Then verify that the size is the same, the // capacity is larger, and all the original items are still in the table. - HashTableInternals Table; + HashTableInternals<> Table; + IdentityHashTraits Traits; uint32_t OldCapacity = Table.capacity(); for (uint32_t I = 0; I < OldCapacity; ++I) { - Table.set_as(OldCapacity + I * 2 + 1, I * 2 + 3); + Table.set_as(OldCapacity + I * 2 + 1, I * 2 + 3, Traits); } EXPECT_EQ(OldCapacity, Table.size()); EXPECT_GT(Table.capacity(), OldCapacity); for (uint32_t I = 0; I < OldCapacity; ++I) { - ASSERT_NE(Table.end(), Table.find_as(OldCapacity + I * 2 + 1)); - EXPECT_EQ(I * 2 + 3, Table.get(OldCapacity + I * 2 + 1)); + ASSERT_NE(Table.end(), Table.find_as(OldCapacity + I * 2 + 1, Traits)); + EXPECT_EQ(I * 2 + 3, Table.get(OldCapacity + I * 2 + 1, Traits)); } } TEST(HashTableTest, Serialization) { - HashTableInternals Table; + HashTableInternals<> Table; + IdentityHashTraits Traits; uint32_t Cap = Table.capacity(); for (uint32_t I = 0; I < Cap; ++I) { - Table.set_as(Cap + I * 2 + 1, I * 2 + 3); + Table.set_as(Cap + I * 2 + 1, I * 2 + 3, Traits); } std::vector Buffer(Table.calculateSerializedLength()); @@ -139,7 +152,7 @@ // We should have written precisely the number of bytes we calculated earlier. EXPECT_EQ(Buffer.size(), Writer.getOffset()); - HashTableInternals Table2; + HashTableInternals<> Table2; BinaryStreamReader Reader(Stream); EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded()); // We should have read precisely the number of bytes we calculated earlier. @@ -192,20 +205,19 @@ } while (std::next_permutation(Streams.begin(), Streams.end())); } -namespace { struct FooBar { uint32_t X; uint32_t Y; -}; -} // namespace + bool operator==(const FooBar &RHS) const { + return X == RHS.X && Y == RHS.Y; + } +}; -namespace llvm { -namespace pdb { -template <> struct PdbHashTraits { +struct FooBarHashTraits { std::vector Buffer; - PdbHashTraits() { Buffer.push_back(0); } + FooBarHashTraits() { Buffer.push_back(0); } uint32_t hashLookupKey(StringRef S) const { return llvm::pdb::hashStringV1(S); @@ -225,17 +237,16 @@ return N; } }; -} // namespace pdb -} // namespace llvm TEST(HashTableTest, NonTrivialValueType) { - HashTable Table; + HashTableInternals Table; + FooBarHashTraits Traits; uint32_t Cap = Table.capacity(); for (uint32_t I = 0; I < Cap; ++I) { FooBar F; F.X = I; F.Y = I + 1; - Table.set_as(utostr(I), F); + Table.set_as(utostr(I), F, Traits); } std::vector Buffer(Table.calculateSerializedLength()); @@ -245,7 +256,7 @@ // We should have written precisely the number of bytes we calculated earlier. EXPECT_EQ(Buffer.size(), Writer.getOffset()); - HashTable Table2; + HashTableInternals Table2; BinaryStreamReader Reader(Stream); EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded()); // We should have read precisely the number of bytes we calculated earlier. @@ -253,7 +264,7 @@ EXPECT_EQ(Table.size(), Table2.size()); EXPECT_EQ(Table.capacity(), Table2.capacity()); - // EXPECT_EQ(Table.Buckets, Table2.Buckets); - // EXPECT_EQ(Table.Present, Table2.Present); - // EXPECT_EQ(Table.Deleted, Table2.Deleted); + EXPECT_EQ(Table.Buckets, Table2.Buckets); + EXPECT_EQ(Table.Present, Table2.Present); + EXPECT_EQ(Table.Deleted, Table2.Deleted); }