LLVM: include/llvm/DebugInfo/PDB/Native/HashTable.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9#ifndef LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
10#define LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
11
20#include
21#include
22#include
23#include
24
25namespace llvm {
26
27namespace pdb {
28
30 SparseBitVector<> &V);
32 SparseBitVector<> &Vec);
33
34template class HashTable;
35
36template
37class HashTableIterator
39 std::forward_iterator_tag,
40 const std::pair<uint32_t, ValueT>> {
41 using BaseT = typename HashTableIterator::iterator_facade_base;
43
45 bool IsEnd)
46 : Map(&Map), Index(Index), IsEnd(IsEnd) {}
47
48public:
50 int I = Map.Present.find_first();
51 if (I == -1) {
52 Index = 0;
53 IsEnd = true;
54 } else {
56 IsEnd = false;
57 }
58 }
59
61 HashTableIterator &operator=(const HashTableIterator &R) {
62 Map = R.Map;
63 return *this;
64 }
65 bool operator==(const HashTableIterator &R) const {
66 if (IsEnd && R.IsEnd)
67 return true;
68 if (IsEnd != R.IsEnd)
69 return false;
70
71 return (Map == R.Map) && (Index == R.Index);
72 }
73 const std::pair<uint32_t, ValueT> &operator*() const {
74 assert(Map->Present.test(Index));
75 return Map->Buckets[Index];
76 }
77
78
79
80 using BaseT::operator++;
82 while (Index < Map->Buckets.size()) {
83 ++Index;
84 if (Map->Present.test(Index))
85 return *this;
86 }
87
88 IsEnd = true;
89 return *this;
90 }
91
92private:
93 bool isEnd() const { return IsEnd; }
94 uint32_t index() const { return Index; }
95
96 const HashTable *Map;
98 bool IsEnd;
99};
100
101template
103 struct Header {
106 };
107
108 using BucketList = std::vector<std::pair<uint32_t, ValueT>>;
109
110public:
113
116 Buckets.resize(Capacity);
117 }
118
120 const Header *H;
122 return EC;
123 if (H->Capacity == 0)
125 "Invalid Hash Table Capacity");
126 if (H->Size > maxLoad(H->Capacity))
128 "Invalid Hash Table Size");
129
131
133 return EC;
134 if (Present.count() != H->Size)
136 "Present bit vector does not match size!");
137
139 return EC;
142 "Present bit vector intersects deleted!");
143
146 return EC;
147 const ValueT *Value;
149 return EC;
151 }
152
154 }
155
158
159 constexpr int BitsPerWord = 8 * sizeof(uint32_t);
160
161 int NumBitsP = Present.find_last() + 1;
162 int NumBitsD = Deleted.find_last() + 1;
163
164 uint32_t NumWordsP = alignTo(NumBitsP, BitsPerWord) / BitsPerWord;
165 uint32_t NumWordsD = alignTo(NumBitsD, BitsPerWord) / BitsPerWord;
166
167
168
171
172
173
176
177
179
181 }
182
184 Header H;
188 return EC;
189
191 return EC;
192
194 return EC;
195
196 for (const auto &Entry : *this) {
197 if (auto EC = Writer.writeInteger(Entry.first))
198 return EC;
199 if (auto EC = Writer.writeObject(Entry.second))
200 return EC;
201 }
203 }
204
210
214
217
218
219
220 template <typename Key, typename TraitsT>
224 std::optional<uint32_t> FirstUnused;
225 do {
227 if (Traits.storageKeyToLookupKey(Buckets[I].first) == K)
229 } else {
230 if (!FirstUnused)
231 FirstUnused = I;
232
233
234
235
236
238 break;
239 }
242
243
244
245
248 }
249
250
251
252 template <typename Key, typename TraitsT>
254 return set_as_internal(K, std::move(V), Traits, std::nullopt);
255 }
256
257 template <typename Key, typename TraitsT>
259 auto Iter = find_as(K, Traits);
261 return (*Iter).second;
262 }
263
264protected:
267
271
272private:
273
274
275 template <typename Key, typename TraitsT>
276 bool set_as_internal(const Key &K, ValueT V, TraitsT &Traits,
277 std::optional<uint32_t> InternalKey) {
278 auto Entry = find_as(K, Traits);
279 if (Entry != end()) {
281 assert(Traits.storageKeyToLookupKey(Buckets[Entry.index()].first) == K);
282
283 Buckets[Entry.index()].second = V;
284 return false;
285 }
286
287 auto &B = Buckets[Entry.index()];
289 assert(Entry.isEnd());
290 B.first = InternalKey ? *InternalKey : Traits.lookupKeyToStorageKey(K);
291 B.second = V;
292 Present.set(Entry.index());
293 Deleted.reset(Entry.index());
294
295 grow(Traits);
296
298 return true;
299 }
300
302
303 template
304 void grow(TraitsT &Traits) {
308 return;
309 assert(capacity() != UINT32_MAX && "Can't grow Hash table!");
310
311 uint32_t NewCapacity = (capacity() <= INT32_MAX) ? MaxLoad * 2 : UINT32_MAX;
312
313
314
315
318 auto LookupKey = Traits.storageKeyToLookupKey(Buckets[I].first);
319 NewMap.set_as_internal(LookupKey, Buckets[I].second, Traits,
321 }
322
323 Buckets.swap(NewMap.Buckets);
328 }
329};
330
331}
332
333}
334
335#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the SparseBitVector class.
Provides read only access to a subclass of BinaryStream.
Error readObject(const T *&Dest)
Get a pointer to an object of type T from the underlying stream, as if by memcpy, and store the resul...
Error readInteger(T &Dest)
Read an integer of the specified endianness into Dest and update the stream's offset.
Provides write only access to a subclass of WritableBinaryStream.
Error writeInteger(T Value)
Write the integer Value to the underlying stream in the specified endianness.
Error writeObject(const T &Obj)
Writes the object Obj to the underlying stream, as if by using memcpy.
Lightweight error class with error context and mandatory checking.
static ErrorSuccess success()
Create a success value.
LLVM Value Representation.
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition HashTable.h:40
HashTableIterator & operator++()
Definition HashTable.h:81
bool operator==(const HashTableIterator &R) const
Definition HashTable.h:65
HashTableIterator(const HashTable< ValueT > &Map)
Definition HashTable.h:49
const std::pair< uint32_t, ValueT > & operator*() const
Definition HashTable.h:73
HashTableIterator & operator=(const HashTableIterator &R)
Definition HashTable.h:61
HashTableIterator(const HashTableIterator &R)=default
Definition HashTable.h:102
Error load(BinaryStreamReader &Stream)
Definition HashTable.h:119
bool isDeleted(uint32_t K) const
Definition HashTable.h:266
bool set_as(const Key &K, ValueT V, TraitsT &Traits)
Set the entry using a key type that the specified Traits can convert from a real key to an internal k...
Definition HashTable.h:253
uint32_t size() const
Definition HashTable.h:213
Error commit(BinaryStreamWriter &Writer) const
Definition HashTable.h:183
HashTableIterator< ValueT > const_iterator
Definition HashTable.h:111
BucketList Buckets
Definition HashTable.h:268
friend const_iterator
Definition HashTable.h:112
const_iterator begin() const
Definition HashTable.h:215
HashTable()
Definition HashTable.h:114
ValueT get(const Key &K, TraitsT &Traits) const
Definition HashTable.h:258
uint32_t capacity() const
Definition HashTable.h:212
bool empty() const
Definition HashTable.h:211
void clear()
Definition HashTable.h:205
bool isPresent(uint32_t K) const
Definition HashTable.h:265
SparseBitVector Present
Definition HashTable.h:269
const_iterator find_as(const Key &K, TraitsT &Traits) const
Find the entry whose key has the specified hash value, using the specified traits defining hash funct...
Definition HashTable.h:221
const_iterator end() const
Definition HashTable.h:216
uint32_t calculateSerializedLength() const
Definition HashTable.h:156
HashTable(uint32_t Capacity)
Definition HashTable.h:115
SparseBitVector Deleted
Definition HashTable.h:270
LLVM_ABI Error readSparseBitVector(BinaryStreamReader &Stream, SparseBitVector<> &V)
LLVM_ABI Error writeSparseBitVector(BinaryStreamWriter &Writer, SparseBitVector<> &Vec)
detail::packed_endian_specific_integral< uint32_t, llvm::endianness::little, unaligned > ulittle32_t
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
Error make_error(ArgTs &&... Args)
Make a Error instance representing failure using the given error info type.
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.