Refactor the PDB HashTable class.

It previously only worked when the key and value types were
both 4 byte integers.  We now have a use case for a non trivial
value type, so we need to extend it to support arbitrary value
types, which means templatizing it.

llvm-svn: 327647

3 files changed, 27 insertions, 192 deletions

diff --git a/llvm/lib/DebugInfo/PDB/Native/HashTable.cpp b/llvm/lib/DebugInfo/PDB/Native/HashTable.cpp
index d3eef553271..5ed0acc8fd7 100644
--- a/llvm/lib/DebugInfo/PDB/Native/HashTable.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/HashTable.cpp
@@ -22,130 +22,7 @@
 using namespace llvm;
 using namespace llvm::pdb;
 
-namespace {
-struct IdentityTraits {
-  static uint32_t hash(uint32_t K, const HashTable &Ctx) { return K; }
-  static uint32_t realKey(uint32_t K, const HashTable &Ctx) { return K; }
-  static uint32_t lowerKey(uint32_t K, const HashTable &Ctx) { return K; }
-};
-} // namespace
-
-HashTable::HashTable() : HashTable(8) {}
-
-HashTable::HashTable(uint32_t Capacity) { Buckets.resize(Capacity); }
-
-Error HashTable::load(BinaryStreamReader &Stream) {
-  const Header *H;
-  if (auto EC = Stream.readObject(H))
-    return EC;
-  if (H->Capacity == 0)
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Invalid Hash Table Capacity");
-  if (H->Size > maxLoad(H->Capacity))
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Invalid Hash Table Size");
-
-  Buckets.resize(H->Capacity);
-
-  if (auto EC = readSparseBitVector(Stream, Present))
-    return EC;
-  if (Present.count() != H->Size)
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Present bit vector does not match size!");
-
-  if (auto EC = readSparseBitVector(Stream, Deleted))
-    return EC;
-  if (Present.intersects(Deleted))
-    return make_error<RawError>(raw_error_code::corrupt_file,
-                                "Present bit vector interesects deleted!");
-
-  for (uint32_t P : Present) {
-    if (auto EC = Stream.readInteger(Buckets[P].first))
-      return EC;
-    if (auto EC = Stream.readInteger(Buckets[P].second))
-      return EC;
-  }
-
-  return Error::success();
-}
-
-uint32_t HashTable::calculateSerializedLength() const {
-  uint32_t Size = sizeof(Header);
-
-  int NumBitsP = Present.find_last() + 1;
-  int NumBitsD = Deleted.find_last() + 1;
-
-  // Present bit set number of words, followed by that many actual words.
-  Size += sizeof(uint32_t);
-  Size += alignTo(NumBitsP, sizeof(uint32_t));
-
-  // Deleted bit set number of words, followed by that many actual words.
-  Size += sizeof(uint32_t);
-  Size += alignTo(NumBitsD, sizeof(uint32_t));
-
-  // One (Key, Value) pair for each entry Present.
-  Size += 2 * sizeof(uint32_t) * size();
-
-  return Size;
-}
-
-Error HashTable::commit(BinaryStreamWriter &Writer) const {
-  Header H;
-  H.Size = size();
-  H.Capacity = capacity();
-  if (auto EC = Writer.writeObject(H))
-    return EC;
-
-  if (auto EC = writeSparseBitVector(Writer, Present))
-    return EC;
-
-  if (auto EC = writeSparseBitVector(Writer, Deleted))
-    return EC;
-
-  for (const auto &Entry : *this) {
-    if (auto EC = Writer.writeInteger(Entry.first))
-      return EC;
-    if (auto EC = Writer.writeInteger(Entry.second))
-      return EC;
-  }
-  return Error::success();
-}
-
-void HashTable::clear() {
-  Buckets.resize(8);
-  Present.clear();
-  Deleted.clear();
-}
-
-uint32_t HashTable::capacity() const { return Buckets.size(); }
-
-uint32_t HashTable::size() const { return Present.count(); }
-
-HashTableIterator HashTable::begin() const { return HashTableIterator(*this); }
-
-HashTableIterator HashTable::end() const {
-  return HashTableIterator(*this, 0, true);
-}
-
-HashTableIterator HashTable::find(uint32_t K) const {
-  return find_as<IdentityTraits>(K, *this);
-}
-
-void HashTable::set(uint32_t K, uint32_t V) {
-  set_as<IdentityTraits, uint32_t>(K, V, *this);
-}
-
-void HashTable::remove(uint32_t K) { remove_as<IdentityTraits>(K, *this); }
-
-uint32_t HashTable::get(uint32_t K) {
-  auto I = find(K);
-  assert(I != end());
-  return (*I).second;
-}
-
-uint32_t HashTable::maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; }
-
-Error HashTable::readSparseBitVector(BinaryStreamReader &Stream,
+Error llvm::pdb::readSparseBitVector(BinaryStreamReader &Stream,
                                      SparseBitVector<> &V) {
   uint32_t NumWords;
   if (auto EC = Stream.readInteger(NumWords))
@@ -167,7 +44,7 @@ Error HashTable::readSparseBitVector(BinaryStreamReader &Stream,
   return Error::success();
 }
 
-Error HashTable::writeSparseBitVector(BinaryStreamWriter &Writer,
+Error llvm::pdb::writeSparseBitVector(BinaryStreamWriter &Writer,
                                       SparseBitVector<> &Vec) {
   int ReqBits = Vec.find_last() + 1;
   uint32_t NumWords = alignTo(ReqBits, sizeof(uint32_t)) / sizeof(uint32_t);
@@ -191,48 +68,3 @@ Error HashTable::writeSparseBitVector(BinaryStreamWriter &Writer,
   }
   return Error::success();
 }
-
-HashTableIterator::HashTableIterator(const HashTable &Map, uint32_t Index,
-                                     bool IsEnd)
-    : Map(&Map), Index(Index), IsEnd(IsEnd) {}
-
-HashTableIterator::HashTableIterator(const HashTable &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 &HashTableIterator::operator=(const HashTableIterator &R) {
-  Map = R.Map;
-  return *this;
-}
-
-bool HashTableIterator::operator==(const HashTableIterator &R) const {
-  if (IsEnd && R.IsEnd)
-    return true;
-  if (IsEnd != R.IsEnd)
-    return false;
-
-  return (Map == R.Map) && (Index == R.Index);
-}
-
-const std::pair<uint32_t, uint32_t> &HashTableIterator::operator*() const {
-  assert(Map->Present.test(Index));
-  return Map->Buckets[Index];
-}
-
-HashTableIterator &HashTableIterator::operator++() {
-  while (Index < Map->Buckets.size()) {
-    ++Index;
-    if (Map->Present.test(Index))
-      return *this;
-  }
-
-  IsEnd = true;
-  return *this;
-}
diff --git a/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp b/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
index 983b6ebf36a..6076b10c5c9 100644
--- a/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
@@ -27,26 +27,27 @@
 using namespace llvm;
 using namespace llvm::pdb;
 
-namespace {
-struct NamedStreamMapTraits {
-  static uint16_t hash(StringRef S, const NamedStreamMap &NS) {
-    // In the reference implementation, this uses
-    // HASH Hasher<ULONG*, USHORT*>::hashPbCb(PB pb, size_t cb, ULONG ulMod).
-    // Here, the type HASH is a typedef of unsigned short.
-    // ** It is not a bug that we truncate the result of hashStringV1, in fact
-    //    it is a bug if we do not! **
-    return static_cast<uint16_t>(hashStringV1(S));
-  }
-  static StringRef realKey(uint32_t Offset, const NamedStreamMap &NS) {
-    return NS.getString(Offset);
-  }
-  static uint32_t lowerKey(StringRef S, NamedStreamMap &NS) {
-    return NS.appendStringData(S);
-  }
-};
-} // namespace
+NamedStreamMapTraits::NamedStreamMapTraits(NamedStreamMap &NS) : NS(&NS) {}
+
+uint16_t NamedStreamMapTraits::hashLookupKey(StringRef S) const {
+  // In the reference implementation, this uses
+  // HASH Hasher<ULONG*, USHORT*>::hashPbCb(PB pb, size_t cb, ULONG ulMod).
+  // Here, the type HASH is a typedef of unsigned short.
+  // ** It is not a bug that we truncate the result of hashStringV1, in fact
+  //    it is a bug if we do not! **
+  return static_cast<uint16_t>(hashStringV1(S));
+}
+
+StringRef NamedStreamMapTraits::storageKeyToLookupKey(uint32_t Offset) const {
+  return NS->getString(Offset);
+}
+
+uint32_t NamedStreamMapTraits::lookupKeyToStorageKey(StringRef S) {
+  return NS->appendStringData(S);
+}
 
-NamedStreamMap::NamedStreamMap() {}
+NamedStreamMap::NamedStreamMap()
+    : HashTraits(*this), OffsetIndexMap(HashTraits) {}
 
 Error NamedStreamMap::load(BinaryStreamReader &Stream) {
   uint32_t StringBufferSize;
@@ -98,7 +99,7 @@ uint32_t NamedStreamMap::hashString(uint32_t Offset) const {
 }
 
 bool NamedStreamMap::get(StringRef Stream, uint32_t &StreamNo) const {
-  auto Iter = OffsetIndexMap.find_as<NamedStreamMapTraits>(Stream, *this);
+  auto Iter = OffsetIndexMap.find_as(Stream);
   if (Iter == OffsetIndexMap.end())
     return false;
   StreamNo = (*Iter).second;
@@ -122,5 +123,5 @@ uint32_t NamedStreamMap::appendStringData(StringRef S) {
 }
 
 void NamedStreamMap::set(StringRef Stream, uint32_t StreamNo) {
-  OffsetIndexMap.set_as<NamedStreamMapTraits>(Stream, StreamNo, *this);
+  OffsetIndexMap.set_as(Stream, support::ulittle32_t(StreamNo));
 }
diff --git a/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp b/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp
index d3ef87d9009..0680b673380 100644
--- a/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp
@@ -152,7 +152,9 @@ FixedStreamArray<TypeIndexOffset> TpiStream::getTypeIndexOffsets() const {
   return TypeIndexOffsets;
 }
 
-HashTable &TpiStream::getHashAdjusters() { return HashAdjusters; }
+HashTable<support::ulittle32_t> &TpiStream::getHashAdjusters() {
+  return HashAdjusters;
+}
 
 CVTypeRange TpiStream::types(bool *HadError) const {
   return make_range(TypeRecords.begin(HadError), TypeRecords.end());