LLVM  14.0.0git
HashTable.h
Go to the documentation of this file.
1 //===- HashTable.h - PDB Hash Table -----------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
10 #define LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
11 
13 #include "llvm/ADT/iterator.h"
17 #include "llvm/Support/Endian.h"
18 #include "llvm/Support/Error.h"
19 #include <cstdint>
20 #include <iterator>
21 #include <utility>
22 #include <vector>
23 
24 namespace llvm {
25 
26 class BinaryStreamReader;
27 class BinaryStreamWriter;
28 
29 namespace pdb {
30 
31 Error readSparseBitVector(BinaryStreamReader &Stream, SparseBitVector<> &V);
32 Error writeSparseBitVector(BinaryStreamWriter &Writer, SparseBitVector<> &Vec);
33 
34 template <typename ValueT> class HashTable;
35 
36 template <typename ValueT>
38  : public iterator_facade_base<HashTableIterator<ValueT>,
39  std::forward_iterator_tag,
40  const std::pair<uint32_t, ValueT>> {
41  using BaseT = typename HashTableIterator::iterator_facade_base;
42  friend HashTable<ValueT>;
43 
45  bool IsEnd)
46  : Map(&Map), Index(Index), IsEnd(IsEnd) {}
47 
48 public:
49  HashTableIterator(const HashTable<ValueT> &Map) : Map(&Map) {
50  int I = Map.Present.find_first();
51  if (I == -1) {
52  Index = 0;
53  IsEnd = true;
54  } else {
55  Index = static_cast<uint32_t>(I);
56  IsEnd = false;
57  }
58  }
59 
60  HashTableIterator(const HashTableIterator &R) = default;
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  // Implement postfix op++ in terms of prefix op++ by using the superclass
79  // implementation.
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 
92 private:
93  bool isEnd() const { return IsEnd; }
94  uint32_t index() const { return Index; }
95 
96  const HashTable<ValueT> *Map;
97  uint32_t Index;
98  bool IsEnd;
99 };
100 
101 template <typename ValueT>
102 class HashTable {
103  struct Header {
105  support::ulittle32_t Capacity;
106  };
107 
108  using BucketList = std::vector<std::pair<uint32_t, ValueT>>;
109 
110 public:
113 
114  HashTable() { Buckets.resize(8); }
115  explicit HashTable(uint32_t Capacity) {
116  Buckets.resize(Capacity);
117  }
118 
120  const Header *H;
121  if (auto EC = Stream.readObject(H))
122  return EC;
123  if (H->Capacity == 0)
124  return make_error<RawError>(raw_error_code::corrupt_file,
125  "Invalid Hash Table Capacity");
126  if (H->Size > maxLoad(H->Capacity))
127  return make_error<RawError>(raw_error_code::corrupt_file,
128  "Invalid Hash Table Size");
129 
130  Buckets.resize(H->Capacity);
131 
132  if (auto EC = readSparseBitVector(Stream, Present))
133  return EC;
134  if (Present.count() != H->Size)
135  return make_error<RawError>(raw_error_code::corrupt_file,
136  "Present bit vector does not match size!");
137 
138  if (auto EC = readSparseBitVector(Stream, Deleted))
139  return EC;
141  return make_error<RawError>(raw_error_code::corrupt_file,
142  "Present bit vector intersects deleted!");
143 
144  for (uint32_t P : Present) {
145  if (auto EC = Stream.readInteger(Buckets[P].first))
146  return EC;
147  const ValueT *Value;
148  if (auto EC = Stream.readObject(Value))
149  return EC;
150  Buckets[P].second = *Value;
151  }
152 
153  return Error::success();
154  }
155 
157  uint32_t Size = sizeof(Header);
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  // Present bit set number of words (4 bytes), followed by that many actual
168  // words (4 bytes each).
169  Size += sizeof(uint32_t);
170  Size += NumWordsP * sizeof(uint32_t);
171 
172  // Deleted bit set number of words (4 bytes), followed by that many actual
173  // words (4 bytes each).
174  Size += sizeof(uint32_t);
175  Size += NumWordsD * sizeof(uint32_t);
176 
177  // One (Key, ValueT) pair for each entry Present.
178  Size += (sizeof(uint32_t) + sizeof(ValueT)) * size();
179 
180  return Size;
181  }
182 
183  Error commit(BinaryStreamWriter &Writer) const {
184  Header H;
185  H.Size = size();
186  H.Capacity = capacity();
187  if (auto EC = Writer.writeObject(H))
188  return EC;
189 
190  if (auto EC = writeSparseBitVector(Writer, Present))
191  return EC;
192 
193  if (auto EC = writeSparseBitVector(Writer, Deleted))
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  }
202  return Error::success();
203  }
204 
205  void clear() {
206  Buckets.resize(8);
207  Present.clear();
208  Deleted.clear();
209  }
210 
211  bool empty() const { return size() == 0; }
212  uint32_t capacity() const { return Buckets.size(); }
213  uint32_t size() const { return Present.count(); }
214 
215  const_iterator begin() const { return const_iterator(*this); }
216  const_iterator end() const { return const_iterator(*this, 0, true); }
217 
218  /// Find the entry whose key has the specified hash value, using the specified
219  /// traits defining hash function and equality.
220  template <typename Key, typename TraitsT>
221  const_iterator find_as(const Key &K, TraitsT &Traits) const {
222  uint32_t H = Traits.hashLookupKey(K) % capacity();
223  uint32_t I = H;
224  Optional<uint32_t> FirstUnused;
225  do {
226  if (isPresent(I)) {
227  if (Traits.storageKeyToLookupKey(Buckets[I].first) == K)
228  return const_iterator(*this, I, false);
229  } else {
230  if (!FirstUnused)
231  FirstUnused = I;
232  // Insertion occurs via linear probing from the slot hint, and will be
233  // inserted at the first empty / deleted location. Therefore, if we are
234  // probing and find a location that is neither present nor deleted, then
235  // nothing must have EVER been inserted at this location, and thus it is
236  // not possible for a matching value to occur later.
237  if (!isDeleted(I))
238  break;
239  }
240  I = (I + 1) % capacity();
241  } while (I != H);
242 
243  // The only way FirstUnused would not be set is if every single entry in the
244  // table were Present. But this would violate the load factor constraints
245  // that we impose, so it should never happen.
246  assert(FirstUnused);
247  return const_iterator(*this, *FirstUnused, true);
248  }
249 
250  /// Set the entry using a key type that the specified Traits can convert
251  /// from a real key to an internal key.
252  template <typename Key, typename TraitsT>
253  bool set_as(const Key &K, ValueT V, TraitsT &Traits) {
254  return set_as_internal(K, std::move(V), Traits, None);
255  }
256 
257  template <typename Key, typename TraitsT>
258  ValueT get(const Key &K, TraitsT &Traits) const {
259  auto Iter = find_as(K, Traits);
260  assert(Iter != end());
261  return (*Iter).second;
262  }
263 
264 protected:
265  bool isPresent(uint32_t K) const { return Present.test(K); }
266  bool isDeleted(uint32_t K) const { return Deleted.test(K); }
267 
268  BucketList Buckets;
271 
272 private:
273  /// Set the entry using a key type that the specified Traits can convert
274  /// from a real key to an internal key.
275  template <typename Key, typename TraitsT>
276  bool set_as_internal(const Key &K, ValueT V, TraitsT &Traits,
277  Optional<uint32_t> InternalKey) {
278  auto Entry = find_as(K, Traits);
279  if (Entry != end()) {
280  assert(isPresent(Entry.index()));
281  assert(Traits.storageKeyToLookupKey(Buckets[Entry.index()].first) == K);
282  // We're updating, no need to do anything special.
283  Buckets[Entry.index()].second = V;
284  return false;
285  }
286 
287  auto &B = Buckets[Entry.index()];
288  assert(!isPresent(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 
297  assert((find_as(K, Traits)) != end());
298  return true;
299  }
300 
301  static uint32_t maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; }
302 
303  template <typename TraitsT>
304  void grow(TraitsT &Traits) {
305  uint32_t S = size();
306  uint32_t MaxLoad = maxLoad(capacity());
307  if (S < maxLoad(capacity()))
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  // Growing requires rebuilding the table and re-hashing every item. Make a
314  // copy with a larger capacity, insert everything into the copy, then swap
315  // it in.
316  HashTable NewMap(NewCapacity);
317  for (auto I : Present) {
318  auto LookupKey = Traits.storageKeyToLookupKey(Buckets[I].first);
319  NewMap.set_as_internal(LookupKey, Buckets[I].second, Traits,
320  Buckets[I].first);
321  }
322 
323  Buckets.swap(NewMap.Buckets);
324  std::swap(Present, NewMap.Present);
325  std::swap(Deleted, NewMap.Deleted);
326  assert(capacity() == NewCapacity);
327  assert(size() == S);
328  }
329 };
330 
331 } // end namespace pdb
332 
333 } // end namespace llvm
334 
335 #endif // LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:148
BinaryStreamReader.h
llvm::pdb::readSparseBitVector
Error readSparseBitVector(BinaryStreamReader &Stream, SparseBitVector<> &V)
Definition: HashTable.cpp:24
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::BinaryStreamWriter::writeInteger
Error writeInteger(T Value)
Write the integer Value to the underlying stream in the specified endianness.
Definition: BinaryStreamWriter.h:64
llvm::lltok::Error
@ Error
Definition: LLToken.h:21
llvm::pdb::writeSparseBitVector
Error writeSparseBitVector(BinaryStreamWriter &Writer, SparseBitVector<> &Vec)
Definition: HashTable.cpp:46
llvm::pdb::HashTable::end
const_iterator end() const
Definition: HashTable.h:216
llvm::SparseBitVector::clear
void clear()
Definition: SparseBitVector.h:451
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::pdb::HashTable::load
Error load(BinaryStreamReader &Stream)
Definition: HashTable.h:119
llvm::BinaryStreamWriter
Provides write only access to a subclass of WritableBinaryStream.
Definition: BinaryStreamWriter.h:31
llvm::SparseBitVector::count
unsigned count() const
Definition: SparseBitVector.h:799
llvm::Error::success
static ErrorSuccess success()
Create a success value.
Definition: Error.h:331
Error.h
llvm::SparseBitVector::reset
void reset(unsigned Idx)
Definition: SparseBitVector.h:486
llvm::Optional< uint32_t >
RawError.h
llvm::pdb::HashTable::const_iterator
friend const_iterator
Definition: HashTable.h:112
llvm::pdb::HashTable::commit
Error commit(BinaryStreamWriter &Writer) const
Definition: HashTable.h:183
SparseBitVector.h
llvm::pdb::HashTableIterator::operator==
bool operator==(const HashTableIterator &R) const
Definition: HashTable.h:65
llvm::SparseBitVector
Definition: SparseBitVector.h:255
llvm::pdb::raw_error_code::corrupt_file
@ corrupt_file
llvm::pdb::HashTable::HashTable
HashTable(uint32_t Capacity)
Definition: HashTable.h:115
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::pdb::HashTable::calculateSerializedLength
uint32_t calculateSerializedLength() const
Definition: HashTable.h:156
llvm::BinaryStreamReader::readInteger
Error readInteger(T &Dest)
Read an integer of the specified endianness into Dest and update the stream's offset.
Definition: BinaryStreamReader.h:75
llvm::pdb::HashTable::begin
const_iterator begin() const
Definition: HashTable.h:215
llvm::None
const NoneType None
Definition: None.h:23
llvm::pdb::HashTable::get
ValueT get(const Key &K, TraitsT &Traits) const
Definition: HashTable.h:258
llvm::BinaryStreamReader
Provides read only access to a subclass of BinaryStream.
Definition: BinaryStreamReader.h:31
llvm::pdb::HashTable::set_as
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
llvm::pdb::HashTable::capacity
uint32_t capacity() const
Definition: HashTable.h:212
llvm::support::ulittle32_t
detail::packed_endian_specific_integral< uint32_t, little, unaligned > ulittle32_t
Definition: Endian.h:272
llvm::pdb::HashTable::clear
void clear()
Definition: HashTable.h:205
llvm::pdb::HashTable::Deleted
SparseBitVector Deleted
Definition: HashTable.h:270
llvm::SparseBitVector::set
void set(unsigned Idx)
Definition: SparseBitVector.h:507
llvm::pdb::HashTableIterator::HashTableIterator
HashTableIterator(const HashTable< ValueT > &Map)
Definition: HashTable.h:49
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::SparseBitVector::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:471
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
TraitsT
llvm::pdb::HashTable::HashTable
HashTable()
Definition: HashTable.h:114
llvm::BinaryStreamReader::readObject
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...
Definition: BinaryStreamReader.h:169
llvm::pdb::HashTable::Buckets
BucketList Buckets
Definition: HashTable.h:268
llvm::pdb::HashTable::size
uint32_t size() const
Definition: HashTable.h:213
llvm::SparseBitVector::intersects
bool intersects(const SparseBitVector< ElementSize > *RHS) const
Definition: SparseBitVector.h:738
llvm::BinaryStreamWriter::writeObject
Error writeObject(const T &Obj)
Writes the object Obj to the underlying stream, as if by using memcpy.
Definition: BinaryStreamWriter.h:135
llvm::pdb::HashTable::const_iterator
HashTableIterator< ValueT > const_iterator
Definition: HashTable.h:111
llvm::pdb::HashTableIterator::operator*
const std::pair< uint32_t, ValueT > & operator*() const
Definition: HashTable.h:73
ValueT
uint32_t
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
H
#define H(x, y, z)
Definition: MD5.cpp:58
llvm::pdb::HashTable::empty
bool empty() const
Definition: HashTable.h:211
llvm::Error
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
llvm::pdb::HashTableIterator
Definition: HashTable.h:37
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::pdb::HashTable
Definition: HashTable.h:34
llvm::pdb::HashTable::isDeleted
bool isDeleted(uint32_t K) const
Definition: HashTable.h:266
llvm::pdb::HashTable::Present
SparseBitVector Present
Definition: HashTable.h:269
llvm::pdb::HashTableIterator::operator++
HashTableIterator & operator++()
Definition: HashTable.h:81
llvm::pdb::HashTable::find_as
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
llvm::pdb::HashTable::isPresent
bool isPresent(uint32_t K) const
Definition: HashTable.h:265
llvm::pdb::HashTableIterator::operator=
HashTableIterator & operator=(const HashTableIterator &R)
Definition: HashTable.h:61
BinaryStreamWriter.h
llvm::SparseBitVector::find_last
int find_last() const
Definition: SparseBitVector.h:787
Endian.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74