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
diff --git a/llvm/lib/DebugInfo/PDB/Native/HashTable.cpp b/llvm/lib/DebugInfo/PDB/Native/HashTable.cpp
index d3eef55..5ed0acc 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 @@
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 @@
}
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 983b6eb..6076b10 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) {}
-NamedStreamMap::NamedStreamMap() {}
+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()
+ : HashTraits(*this), OffsetIndexMap(HashTraits) {}
Error NamedStreamMap::load(BinaryStreamReader &Stream) {
uint32_t StringBufferSize;
@@ -98,7 +99,7 @@
}
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 @@
}
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 d3ef87d..0680b67 100644
--- a/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp
@@ -152,7 +152,9 @@
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());