PDB HashTable: Move TraitsT from class parameter to the methods that need it

[thakis]

Summary

The traits object is only used by a few methods. Deserializing a hash
table and walking it is possible without the traits object, so it
shouldn't be required to build a dummy object for that use case.

The TraitsT object used to be a function template parameter before
r327647, this restores it to that state.

This makes it clear that the traits object isn't needed at all in 1 of
the current 3 uses of HashTable (and I am going to add another use that
doesn't need it), and that the default PdbHashTraits isn't used outside
of tests.

While here, also re-enable 3 checks in the test that were commented out
(which requires making HashTableInternals templated and giving FooBar
an operator==).

No intended behavior change.

[rnk]

The traits object is only used by a few methods. Deserializing a hash
table and walking it is possible without the traits object, so it
shouldn't be required to build a dummy object for that use case.

The traits are needed to do any actual hashing. I think I have a bit of a preference for the code as it is before your change. Now all the hash lookup operations have to take an extra parameter, and the caller is responsible for managing the lifetime of a new object that probably should exactly match the lifetime of the hash table.

What do you think of having a traits-less HashTableView or HashTableBase and having HashTable inherit from it? Would that solve your use case?

[thakis]

In D64640#1583265, @rnk wrote:

The traits object is only used by a few methods. Deserializing a hash
table and walking it is possible without the traits object, so it
shouldn't be required to build a dummy object for that use case.

The traits are needed to do any actual hashing.

I believe that's not really true: The has key is always an uint32_t, and assuming that lookupKeyToStorageKey() and storageKeyToLookupKey() are inverses of each other (which currently is true for StringTableHashTraits; for NamedStreamMapTraits I'm not yet sure what the semantics for two streams with the same name are. I believe it's not allowed – passing two identical /natvis: params to lld seems to confuse everyone at least -- and then it'd be true there too). So I currently think (but could be wrong, I'm not sure yet) that the hashtable hash function is overly complicated and should always work just on the uint32_t key and there should be a convenience function to convert a string key to an uint32_t. But that's for another change.

I think I have a bit of a preference for the code as it is before your change. Now all the hash lookup operations have to take an extra parameter, and the caller is responsible for managing the lifetime of a new object that probably should exactly match the lifetime of the hash table.

The callers did manage the traits object before as well. Maybe that wasn't necessary, but see PDBFileBuilder.h and llvm/include/llvm/DebugInfo/PDB/Native/NamedStreamMap.h on the lhs – the traits objects were already member variables. There are 3 distinct call sites to the lookup operations from non-test code.

What do you think of having a traits-less HashTableView or HashTableBase and having HashTable inherit from it? Would that solve your use case?

https://reviews.llvm.org/D64428?id=208735 used to do this. It was imo much messier (see the "drat" comments for some unresolved issues with that approach, but even with them resolved it's pretty messy). I then left the hash table as is and added another traits class that was silently unused in https://reviews.llvm.org/D64428?id=209475 but didn't like that either (see "xxx blah" for an annoying issue there – a function that's silently unused can't be implemented nicely). I think this change is by far the nicest.

[rnk]

In D64640#1583291, @thakis wrote:

In D64640#1583265, @rnk wrote:

The traits object is only used by a few methods. Deserializing a hash
table and walking it is possible without the traits object, so it
shouldn't be required to build a dummy object for that use case.

The traits are needed to do any actual hashing.

I believe that's not really true: The has key is always an uint32_t, and assuming that lookupKeyToStorageKey() and storageKeyToLookupKey() are inverses of each other (which currently is true for StringTableHashTraits; for NamedStreamMapTraits I'm not yet sure what the semantics for two streams with the same name are. I believe it's not allowed – passing two identical /natvis: params to lld seems to confuse everyone at least -- and then it'd be true there too). So I currently think (but could be wrong, I'm not sure yet) that the hashtable hash function is overly complicated and should always work just on the uint32_t key and there should be a convenience function to convert a string key to an uint32_t. But that's for another change.

Hey, I like the sound of that: who needs traits templates, we can just use functions. Insofar as this is a step in that direction, I'm on board.

I think I have a bit of a preference for the code as it is before your change. Now all the hash lookup operations have to take an extra parameter, and the caller is responsible for managing the lifetime of a new object that probably should exactly match the lifetime of the hash table.

The callers did manage the traits object before as well. Maybe that wasn't necessary, but see PDBFileBuilder.h and llvm/include/llvm/DebugInfo/PDB/Native/NamedStreamMap.h on the lhs – the traits objects were already member variables. There are 3 distinct call sites to the lookup operations from non-test code.

What do you think of having a traits-less HashTableView or HashTableBase and having HashTable inherit from it? Would that solve your use case?

https://reviews.llvm.org/D64428?id=208735 used to do this. It was imo much messier (see the "drat" comments for some unresolved issues with that approach, but even with them resolved it's pretty messy). I then left the hash table as is and added another traits class that was silently unused in https://reviews.llvm.org/D64428?id=209475 but didn't like that either (see "xxx blah" for an annoying issue there – a function that's silently unused can't be implemented nicely). I think this change is by far the nicest.

I took a look at the linked stuff, but mostly I'm convinced that you've thought about these other approaches and I'll trust that you've made the right judgement here, looks good to me.

llvm/include/llvm/DebugInfo/PDB/Native/HashTable.h

 class BinaryStreamReader;
 class BinaryStreamWriter;
 
 namespace pdb {
 
 Error readSparseBitVector(BinaryStreamReader &Stream, SparseBitVector<> &V);
 Error writeSparseBitVector(BinaryStreamWriter &Writer, SparseBitVector<> &Vec);
 
-template <typename ValueT, typename TraitsT> class HashTable;
+template <typename ValueT> class HashTable;
 
-template <typename ValueT, typename TraitsT>
+template <typename ValueT>
 class HashTableIterator
-    : public iterator_facade_base<HashTableIterator<ValueT, TraitsT>,
+    : public iterator_facade_base<HashTableIterator<ValueT>,
                                   std::forward_iterator_tag,
                                   std::pair<uint32_t, ValueT>> {
-  friend HashTable<ValueT, TraitsT>;
+  friend HashTable<ValueT>;
 
-  HashTableIterator(const HashTable<ValueT, TraitsT> &Map, uint32_t Index,
+  HashTableIterator(const HashTable<ValueT> &Map, uint32_t Index,
                     bool IsEnd)
       : Map(&Map), Index(Index), IsEnd(IsEnd) {}
 
 public:
-  HashTableIterator(const HashTable<ValueT, TraitsT> &Map) : Map(&Map) {
+  HashTableIterator(const HashTable<ValueT> &Map) : Map(&Map) {
     int I = Map.Present.find_first();
     if (I == -1) {
       Index = 0;
       IsEnd = true;
     } else {
       Index = static_cast<uint32_t>(I);
       IsEnd = false;
     }
HashTableIterator &operator++() {
     IsEnd = true;
     return *this;
   }
 
 private:
   bool isEnd() const { return IsEnd; }
   uint32_t index() const { return Index; }
 
-  const HashTable<ValueT, TraitsT> *Map;
+  const HashTable<ValueT> *Map;
   uint32_t Index;
   bool IsEnd;
 };
 
-template <typename T> struct PdbHashTraits {};
-
-template <> struct PdbHashTraits<uint32_t> {
-  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 <typename ValueT, typename TraitsT = PdbHashTraits<ValueT>>
+template <typename ValueT>
 class HashTable {
-  using iterator = HashTableIterator<ValueT, TraitsT>;
+  using iterator = HashTableIterator<ValueT>;
   friend iterator;
 
   struct Header {
     support::ulittle32_t Size;
     support::ulittle32_t Capacity;
   };
 
   using BucketList = std::vector<std::pair<uint32_t, ValueT>>;
 
 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);
   }
 
   Error load(BinaryStreamReader &Stream) {
     const Header *H;
     if (auto EC = Stream.readObject(H))
       return EC;
     if (H->Capacity == 0)
public:
   uint32_t capacity() const { return Buckets.size(); }
   uint32_t size() const { return Present.count(); }
 
   iterator begin() const { return iterator(*this); }
   iterator end() const { return iterator(*this, 0, true); }
 
   /// Find the entry whose key has the specified hash value, using the specified
   /// traits defining hash function and equality.
-  template <typename Key> iterator find_as(const Key &K) const {
+  template <typename Key, typename TraitsT>
+  iterator find_as(const Key &K, TraitsT &Traits) const {
     uint32_t H = Traits.hashLookupKey(K) % capacity();
     uint32_t I = H;
     Optional<uint32_t> FirstUnused;
     do {
       if (isPresent(I)) {
         if (Traits.storageKeyToLookupKey(Buckets[I].first) == K)
           return iterator(*this, I, false);
       } else {
iterator find_as(const Key &K, TraitsT &Traits) const {
     // table were Present.  But this would violate the load factor constraints
     // that we impose, so it should never happen.
     assert(FirstUnused);
     return iterator(*this, *FirstUnused, true);
   }
 
   /// Set the entry using a key type that the specified Traits can convert
   /// from a real key to an internal key.
-  template <typename Key> bool set_as(const Key &K, ValueT V) {
-    return set_as_internal(K, std::move(V), None);
+  template <typename Key, typename TraitsT>
+  bool set_as(const Key &K, ValueT V, TraitsT &Traits) {
+    return set_as_internal(K, std::move(V), Traits, None);
   }
 
-  template <typename Key> ValueT get(const Key &K) const {
-    auto Iter = find_as(K);
+  template <typename Key, typename TraitsT>
+  ValueT get(const Key &K, TraitsT &Traits) const {
+    auto Iter = find_as(K, Traits);
     assert(Iter != end());
     return (*Iter).second;
   }
 
 protected:
   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;
 
 private:
   /// Set the entry using a key type that the specified Traits can convert
   /// from a real key to an internal key.
-  template <typename Key>
-  bool set_as_internal(const Key &K, ValueT V, Optional<uint32_t> InternalKey) {
-    auto Entry = find_as(K);
+  template <typename Key, typename TraitsT>
+  bool set_as_internal(const Key &K, ValueT V, TraitsT &Traits,
+                       Optional<uint32_t> InternalKey) {
+    auto Entry = find_as(K, Traits);
     if (Entry != end()) {
       assert(isPresent(Entry.index()));
       assert(Traits.storageKeyToLookupKey(Buckets[Entry.index()].first) == K);
       // We're updating, no need to do anything special.
       Buckets[Entry.index()].second = V;
       return false;
     }
 
     auto &B = Buckets[Entry.index()];
     assert(!isPresent(Entry.index()));
     assert(Entry.isEnd());
     B.first = InternalKey ? *InternalKey : Traits.lookupKeyToStorageKey(K);
     B.second = V;
     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 <typename TraitsT>
+  void grow(TraitsT &Traits) {
     uint32_t S = size();
     uint32_t MaxLoad = maxLoad(capacity());
     if (S < maxLoad(capacity()))
       return;
     assert(capacity() != UINT32_MAX && "Can't grow Hash table!");
 
     uint32_t NewCapacity = (capacity() <= INT32_MAX) ? MaxLoad * 2 : UINT32_MAX;
 
     // 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);
     std::swap(Present, NewMap.Present);
     std::swap(Deleted, NewMap.Deleted);
     assert(capacity() == NewCapacity);
     assert(size() == S);
   }
 };
 
 } // end namespace pdb
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H

llvm/include/llvm/DebugInfo/PDB/Native/NamedStreamMap.h

public:
   uint32_t hashString(uint32_t Offset) const;
 
   StringMap<uint32_t> entries() const;
 
 private:
   NamedStreamMapTraits HashTraits;
   /// Closed hash table from Offset -> StreamNumber, where Offset is the offset
   /// of the stream name in NamesBuffer.
-  HashTable<support::ulittle32_t, NamedStreamMapTraits> OffsetIndexMap;
+  HashTable<support::ulittle32_t> OffsetIndexMap;
 
   /// Buffer of string data.
   std::vector<char> NamesBuffer;
 };
 
 } // end namespace pdb
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_PDB_NATIVE_NAMEDSTREAMMAP_H

llvm/include/llvm/DebugInfo/PDB/Native/PDBFileBuilder.h

private:
   std::unique_ptr<InfoStreamBuilder> Info;
   std::unique_ptr<DbiStreamBuilder> Dbi;
   std::unique_ptr<GSIStreamBuilder> Gsi;
   std::unique_ptr<TpiStreamBuilder> Tpi;
   std::unique_ptr<TpiStreamBuilder> Ipi;
 
   PDBStringTableBuilder Strings;
   StringTableHashTraits InjectedSourceHashTraits;
-  HashTable<SrcHeaderBlockEntry, StringTableHashTraits> InjectedSourceTable;
+  HashTable<SrcHeaderBlockEntry> InjectedSourceTable;
 
   SmallVector<InjectedSourceDescriptor, 2> InjectedSources;
 
   NamedStreamMap NamedStreams;
   DenseMap<uint32_t, std::string> NamedStreamData;
 };
 }
 }
 
 #endif

llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp

 StringRef NamedStreamMapTraits::storageKeyToLookupKey(uint32_t Offset) const {
   return NS->getString(Offset);
 }
 
 uint32_t NamedStreamMapTraits::lookupKeyToStorageKey(StringRef S) {
   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;
   if (auto EC = Stream.readInteger(StringBufferSize))
     return joinErrors(std::move(EC),
                       make_error<RawError>(raw_error_code::corrupt_file,
                                            "Expected string buffer size"));
 
StringRef NamedStreamMap::getString(uint32_t Offset) const {
   return StringRef(NamesBuffer.data() + Offset);
 }
 
 uint32_t NamedStreamMap::hashString(uint32_t Offset) const {
   return hashStringV1(getString(Offset));
 }
 
 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;
   return true;
 }
 
 StringMap<uint32_t> NamedStreamMap::entries() const {
   StringMap<uint32_t> Result;
   for (const auto &Entry : OffsetIndexMap) {
     StringRef Stream(NamesBuffer.data() + Entry.first);
     Result.try_emplace(Stream, Entry.second);
   }
   return Result;
 }
 
 uint32_t NamedStreamMap::appendStringData(StringRef S) {
   uint32_t Offset = NamesBuffer.size();
   NamesBuffer.insert(NamesBuffer.end(), S.begin(), S.end());
   NamesBuffer.push_back('\0');
   return Offset;
 }
 
 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);
 }

llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

 using namespace llvm;
 using namespace llvm::codeview;
 using namespace llvm::msf;
 using namespace llvm::pdb;
 using namespace llvm::support;
 
 PDBFileBuilder::PDBFileBuilder(BumpPtrAllocator &Allocator)
     : Allocator(Allocator), InjectedSourceHashTraits(Strings),
-      InjectedSourceTable(2, InjectedSourceHashTraits) {}
+      InjectedSourceTable(2) {}
 
 PDBFileBuilder::~PDBFileBuilder() {}
 
 Error PDBFileBuilder::initialize(uint32_t BlockSize) {
   auto ExpectedMsf = MSFBuilder::create(Allocator, BlockSize);
   if (!ExpectedMsf)
     return ExpectedMsf.takeError();
   Msf = llvm::make_unique<MSFBuilder>(std::move(*ExpectedMsf));
for (const auto &IS : InjectedSources) {
       Entry.FileNI = IS.NameIndex;
       Entry.VFileNI = IS.VNameIndex;
       Entry.ObjNI = 1;
       Entry.IsVirtual = 0;
       Entry.Version =
           static_cast<uint32_t>(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 =
         sizeof(SrcHeaderBlockHeader) +
         InjectedSourceTable.calculateSerializedLength();
     SN = allocateNamedStream("/src/headerblock", SrcHeaderBlockSize);
     if (!SN)
       return SN.takeError();

llvm/unittests/DebugInfo/PDB/HashTableTest.cpp

 #include <vector>
 
 using namespace llvm;
 using namespace llvm::pdb;
 using namespace llvm::support;
 
 namespace {
 
-class HashTableInternals : public HashTable<uint32_t> {
+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 T = uint32_t>
+class HashTableInternals : public HashTable<T> {
 public:
-  using HashTable::Buckets;
-  using HashTable::Present;
-  using HashTable::Deleted;
+  using HashTable<T>::Buckets;
+  using HashTable<T>::Present;
+  using HashTable<T>::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);
 
   // We use knowledge of the hash table's implementation details to make sure
   // to add another value that is the equivalent to the first value modulo the
   // hash table's capacity.
   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);
 
   // Probing looks for the first available slot.  A slot may already be filled
   // as a result of an item with a *different* hash value already being there.
   // Test that when this happens, the probe still finds the value.
   uint32_t N1 = Table.capacity() + 1;
   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));
-
-  EXPECT_EQ(7u, Table.get(N1));
-  EXPECT_EQ(11u, Table.get(N2));
-  EXPECT_EQ(13u, Table.get(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, Traits));
+  EXPECT_EQ(11u, Table.get(N2, Traits));
+  EXPECT_EQ(13u, Table.get(N3, Traits));
 }
 
 TEST(HashTableTest, Grow) {
   // So that we are independent of the load factor, `capacity` items, which is
   // 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<uint8_t> Buffer(Table.calculateSerializedLength());
   MutableBinaryByteStream Stream(Buffer, little);
   BinaryStreamWriter Writer(Stream);
   EXPECT_THAT_ERROR(Table.commit(Writer), Succeeded());
   // 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.
   EXPECT_EQ(Buffer.size(), Reader.getOffset());
 
   EXPECT_EQ(Table.size(), Table2.size());
   EXPECT_EQ(Table.capacity(), Table2.capacity());
   EXPECT_EQ(Table.Buckets, Table2.Buckets);
do {
     EXPECT_TRUE(NSM.get("Six", N));
     EXPECT_EQ(6U, N);
 
     EXPECT_TRUE(NSM.get("Seven", N));
     EXPECT_EQ(7U, N);
   } 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<FooBar> {
+struct FooBarHashTraits {
   std::vector<char> Buffer;
 
-  PdbHashTraits() { Buffer.push_back(0); }
+  FooBarHashTraits() { Buffer.push_back(0); }
 
   uint32_t hashLookupKey(StringRef S) const {
     return llvm::pdb::hashStringV1(S);
   }
 
   StringRef storageKeyToLookupKey(uint32_t N) const {
     if (N >= Buffer.size())
       return StringRef();
 
     return StringRef(Buffer.data() + N);
   }
 
   uint32_t lookupKeyToStorageKey(StringRef S) {
     uint32_t N = Buffer.size();
     Buffer.insert(Buffer.end(), S.begin(), S.end());
     Buffer.push_back('\0');
     return N;
   }
 };
-} // namespace pdb
-} // namespace llvm
 
 TEST(HashTableTest, NonTrivialValueType) {
-  HashTable<FooBar> Table;
+  HashTableInternals<FooBar> 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<uint8_t> Buffer(Table.calculateSerializedLength());
   MutableBinaryByteStream Stream(Buffer, little);
   BinaryStreamWriter Writer(Stream);
   EXPECT_THAT_ERROR(Table.commit(Writer), Succeeded());
   // We should have written precisely the number of bytes we calculated earlier.
   EXPECT_EQ(Buffer.size(), Writer.getOffset());
 
-  HashTable<FooBar> Table2;
+  HashTableInternals<FooBar> Table2;
   BinaryStreamReader Reader(Stream);
   EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded());
   // We should have read precisely the number of bytes we calculated earlier.
   EXPECT_EQ(Buffer.size(), Reader.getOffset());
 
   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);
 }