aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/DebugInfo/PDB/Native/HashTable.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/DebugInfo/PDB/Native/HashTable.h')
-rw-r--r--include/llvm/DebugInfo/PDB/Native/HashTable.h92
1 files changed, 46 insertions, 46 deletions
diff --git a/include/llvm/DebugInfo/PDB/Native/HashTable.h b/include/llvm/DebugInfo/PDB/Native/HashTable.h
index 34cc6179688b..aa38417bcf4c 100644
--- a/include/llvm/DebugInfo/PDB/Native/HashTable.h
+++ b/include/llvm/DebugInfo/PDB/Native/HashTable.h
@@ -1,9 +1,8 @@
//===- HashTable.h - PDB Hash Table -----------------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
@@ -32,21 +31,21 @@ 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>;
+ const std::pair<uint32_t, ValueT>> {
+ 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;
@@ -73,6 +72,12 @@ public:
assert(Map->Present.test(Index));
return Map->Buckets[Index];
}
+
+ // Implement postfix op++ in terms of prefix op++ by using the superclass
+ // implementation.
+ using iterator_facade_base<HashTableIterator<ValueT>,
+ std::forward_iterator_tag,
+ const std::pair<uint32_t, ValueT>>::operator++;
HashTableIterator &operator++() {
while (Index < Map->Buckets.size()) {
++Index;
@@ -88,24 +93,13 @@ 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>;
- friend iterator;
-
struct Header {
support::ulittle32_t Size;
support::ulittle32_t Capacity;
@@ -114,10 +108,11 @@ class HashTable {
using BucketList = std::vector<std::pair<uint32_t, ValueT>>;
public:
- HashTable() { Buckets.resize(8); }
+ using const_iterator = HashTableIterator<ValueT>;
+ friend const_iterator;
- explicit HashTable(TraitsT Traits) : HashTable(8, std::move(Traits)) {}
- HashTable(uint32_t Capacity, TraitsT Traits) : Traits(Traits) {
+ HashTable() { Buckets.resize(8); }
+ explicit HashTable(uint32_t Capacity) {
Buckets.resize(Capacity);
}
@@ -144,7 +139,7 @@ public:
return EC;
if (Present.intersects(Deleted))
return make_error<RawError>(raw_error_code::corrupt_file,
- "Present bit vector interesects deleted!");
+ "Present bit vector intersects deleted!");
for (uint32_t P : Present) {
if (auto EC = Stream.readInteger(Buckets[P].first))
@@ -217,19 +212,20 @@ 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); }
+ const_iterator begin() const { return const_iterator(*this); }
+ const_iterator end() const { return const_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>
+ const_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);
+ return const_iterator(*this, I, false);
} else {
if (!FirstUnused)
FirstUnused = I;
@@ -248,17 +244,19 @@ public:
// 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);
+ return const_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;
}
@@ -267,7 +265,6 @@ 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;
@@ -275,9 +272,10 @@ protected:
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);
@@ -294,15 +292,16 @@ private:
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()))
@@ -314,10 +313,11 @@ private:
// 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);
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-08 10:47:11 +0000