LLVM  10.0.0svn
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  friend HashTable<ValueT>;
42 
44  bool IsEnd)
45  : Map(&Map), Index(Index), IsEnd(IsEnd) {}
46 
47 public:
48  HashTableIterator(const HashTable<ValueT> &Map) : Map(&Map) {
49  int I = Map.Present.find_first();
50  if (I == -1) {
51  Index = 0;
52  IsEnd = true;
53  } else {
54  Index = static_cast<uint32_t>(I);
55  IsEnd = false;
56  }
57  }
58 
60  Map = R.Map;
61  return *this;
62  }
63  bool operator==(const HashTableIterator &R) const {
64  if (IsEnd && R.IsEnd)
65  return true;
66  if (IsEnd != R.IsEnd)
67  return false;
68 
69  return (Map == R.Map) && (Index == R.Index);
70  }
71  const std::pair<uint32_t, ValueT> &operator*() const {
72  assert(Map->Present.test(Index));
73  return Map->Buckets[Index];
74  }
75 
76  // Implement postfix op++ in terms of prefix op++ by using the superclass
77  // implementation.
79  std::forward_iterator_tag,
80  const std::pair<uint32_t, ValueT>>::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;
140  if (Present.intersects(Deleted))
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
Error writeObject(const T &Obj)
Writes the object Obj to the underlying stream, as if by using memcpy.
const std::pair< uint32_t, ValueT > & operator*() const
Definition: HashTable.h:71
HashTableIterator & operator++()
Definition: HashTable.h:81
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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
Error writeSparseBitVector(BinaryStreamWriter &Writer, SparseBitVector<> &Vec)
Definition: HashTable.cpp:46
Error readInteger(T &Dest)
Read an integer of the specified endianness into Dest and update the stream&#39;s offset.
BucketList Buckets
Definition: HashTable.h:268
void set(unsigned Idx)
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...
unsigned second
HashTableIterator & operator=(const HashTableIterator &R)
Definition: HashTable.h:59
SparseBitVector Present
Definition: HashTable.h:269
Key
PAL metadata keys.
uint32_t calculateSerializedLength() const
Definition: HashTable.h:156
SparseBitVector Deleted
Definition: HashTable.h:270
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:67
Error readSparseBitVector(BinaryStreamReader &Stream, SparseBitVector<> &V)
Definition: HashTable.cpp:24
#define P(N)
const_iterator begin() const
Definition: HashTable.h:215
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool empty() const
Definition: HashTable.h:211
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
#define H(x, y, z)
Definition: MD5.cpp:57
Provides write only access to a subclass of WritableBinaryStream.
Error commit(BinaryStreamWriter &Writer) const
Definition: HashTable.h:183
HashTableIterator(const HashTable< ValueT > &Map)
Definition: HashTable.h:48
Error writeInteger(T Value)
Write the integer Value to the underlying stream in the specified endianness.
bool operator==(const HashTableIterator &R) const
Definition: HashTable.h:63
void reset(unsigned Idx)
unsigned first
static ErrorSuccess success()
Create a success value.
Definition: Error.h:326
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1146
bool isDeleted(uint32_t K) const
Definition: HashTable.h:266
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
Error load(BinaryStreamReader &Stream)
Definition: HashTable.h:119
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:126
const_iterator end() const
Definition: HashTable.h:216
#define I(x, y, z)
Definition: MD5.cpp:58
uint32_t Size
Definition: Profile.cpp:46
bool isPresent(uint32_t K) const
Definition: HashTable.h:265
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
uint32_t capacity() const
Definition: HashTable.h:212
uint32_t size() const
Definition: HashTable.h:213
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
Provides read only access to a subclass of BinaryStream.
HashTable(uint32_t Capacity)
Definition: HashTable.h:115