LLVM  6.0.0svn
HashTable.cpp
Go to the documentation of this file.
1 //===- HashTable.cpp - PDB Hash Table -------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
11 #include "llvm/ADT/Optional.h"
15 #include "llvm/Support/Error.h"
17 #include <algorithm>
18 #include <cassert>
19 #include <cstdint>
20 #include <utility>
21 
22 using namespace llvm;
23 using namespace llvm::pdb;
24 
26 
27 HashTable::HashTable(uint32_t Capacity) { Buckets.resize(Capacity); }
28 
30  const Header *H;
31  if (auto EC = Stream.readObject(H))
32  return EC;
33  if (H->Capacity == 0)
34  return make_error<RawError>(raw_error_code::corrupt_file,
35  "Invalid Hash Table Capacity");
36  if (H->Size > maxLoad(H->Capacity))
37  return make_error<RawError>(raw_error_code::corrupt_file,
38  "Invalid Hash Table Size");
39 
40  Buckets.resize(H->Capacity);
41 
42  if (auto EC = readSparseBitVector(Stream, Present))
43  return EC;
44  if (Present.count() != H->Size)
45  return make_error<RawError>(raw_error_code::corrupt_file,
46  "Present bit vector does not match size!");
47 
48  if (auto EC = readSparseBitVector(Stream, Deleted))
49  return EC;
51  return make_error<RawError>(raw_error_code::corrupt_file,
52  "Present bit vector interesects deleted!");
53 
54  for (uint32_t P : Present) {
55  if (auto EC = Stream.readInteger(Buckets[P].first))
56  return EC;
57  if (auto EC = Stream.readInteger(Buckets[P].second))
58  return EC;
59  }
60 
61  return Error::success();
62 }
63 
65  uint32_t Size = sizeof(Header);
66 
67  int NumBitsP = Present.find_last() + 1;
68  int NumBitsD = Deleted.find_last() + 1;
69 
70  // Present bit set number of words, followed by that many actual words.
71  Size += sizeof(uint32_t);
72  Size += alignTo(NumBitsP, sizeof(uint32_t));
73 
74  // Deleted bit set number of words, followed by that many actual words.
75  Size += sizeof(uint32_t);
76  Size += alignTo(NumBitsD, sizeof(uint32_t));
77 
78  // One (Key, Value) pair for each entry Present.
79  Size += 2 * sizeof(uint32_t) * size();
80 
81  return Size;
82 }
83 
85  Header H;
86  H.Size = size();
87  H.Capacity = capacity();
88  if (auto EC = Writer.writeObject(H))
89  return EC;
90 
91  if (auto EC = writeSparseBitVector(Writer, Present))
92  return EC;
93 
94  if (auto EC = writeSparseBitVector(Writer, Deleted))
95  return EC;
96 
97  for (const auto &Entry : *this) {
98  if (auto EC = Writer.writeInteger(Entry.first))
99  return EC;
100  if (auto EC = Writer.writeInteger(Entry.second))
101  return EC;
102  }
103  return Error::success();
104 }
105 
107  Buckets.resize(8);
108  Present.clear();
109  Deleted.clear();
110 }
111 
112 uint32_t HashTable::capacity() const { return Buckets.size(); }
113 
114 uint32_t HashTable::size() const { return Present.count(); }
115 
117 
119  return HashTableIterator(*this, 0, true);
120 }
121 
123  uint32_t H = K % capacity();
124  uint32_t I = H;
125  Optional<uint32_t> FirstUnused;
126  do {
127  if (isPresent(I)) {
128  if (Buckets[I].first == K)
129  return HashTableIterator(*this, I, false);
130  } else {
131  if (!FirstUnused)
132  FirstUnused = I;
133  // Insertion occurs via linear probing from the slot hint, and will be
134  // inserted at the first empty / deleted location. Therefore, if we are
135  // probing and find a location that is neither present nor deleted, then
136  // nothing must have EVER been inserted at this location, and thus it is
137  // not possible for a matching value to occur later.
138  if (!isDeleted(I))
139  break;
140  }
141  I = (I + 1) % capacity();
142  } while (I != H);
143 
144  // The only way FirstUnused would not be set is if every single entry in the
145  // table were Present. But this would violate the load factor constraints
146  // that we impose, so it should never happen.
147  assert(FirstUnused);
148  return HashTableIterator(*this, *FirstUnused, true);
149 }
150 
152  auto Entry = find(K);
153  if (Entry != end()) {
154  assert(isPresent(Entry.index()));
155  assert(Buckets[Entry.index()].first == K);
156  // We're updating, no need to do anything special.
157  Buckets[Entry.index()].second = V;
158  return;
159  }
160 
161  auto &B = Buckets[Entry.index()];
162  assert(!isPresent(Entry.index()));
163  assert(Entry.isEnd());
164  B.first = K;
165  B.second = V;
166  Present.set(Entry.index());
167  Deleted.reset(Entry.index());
168 
169  grow();
170 
171  assert(find(K) != end());
172 }
173 
175  auto Iter = find(K);
176  // It wasn't here to begin with, just exit.
177  if (Iter == end())
178  return;
179 
180  assert(Present.test(Iter.index()));
181  assert(!Deleted.test(Iter.index()));
182  Deleted.set(Iter.index());
183  Present.reset(Iter.index());
184 }
185 
187  auto I = find(K);
188  assert(I != end());
189  return (*I).second;
190 }
191 
192 uint32_t HashTable::maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; }
193 
194 void HashTable::grow() {
195  uint32_t S = size();
196  if (S < maxLoad(capacity()))
197  return;
198  assert(capacity() != UINT32_MAX && "Can't grow Hash table!");
199 
200  uint32_t NewCapacity =
201  (capacity() <= INT32_MAX) ? capacity() * 2 : UINT32_MAX;
202 
203  // Growing requires rebuilding the table and re-hashing every item. Make a
204  // copy with a larger capacity, insert everything into the copy, then swap
205  // it in.
206  HashTable NewMap(NewCapacity);
207  for (auto I : Present) {
208  NewMap.set(Buckets[I].first, Buckets[I].second);
209  }
210 
211  Buckets.swap(NewMap.Buckets);
212  std::swap(Present, NewMap.Present);
213  std::swap(Deleted, NewMap.Deleted);
214  assert(capacity() == NewCapacity);
215  assert(size() == S);
216 }
217 
218 Error HashTable::readSparseBitVector(BinaryStreamReader &Stream,
219  SparseBitVector<> &V) {
220  uint32_t NumWords;
221  if (auto EC = Stream.readInteger(NumWords))
222  return joinErrors(
223  std::move(EC),
224  make_error<RawError>(raw_error_code::corrupt_file,
225  "Expected hash table number of words"));
226 
227  for (uint32_t I = 0; I != NumWords; ++I) {
228  uint32_t Word;
229  if (auto EC = Stream.readInteger(Word))
230  return joinErrors(std::move(EC),
231  make_error<RawError>(raw_error_code::corrupt_file,
232  "Expected hash table word"));
233  for (unsigned Idx = 0; Idx < 32; ++Idx)
234  if (Word & (1U << Idx))
235  V.set((I * 32) + Idx);
236  }
237  return Error::success();
238 }
239 
240 Error HashTable::writeSparseBitVector(BinaryStreamWriter &Writer,
241  SparseBitVector<> &Vec) {
242  int ReqBits = Vec.find_last() + 1;
243  uint32_t NumWords = alignTo(ReqBits, sizeof(uint32_t)) / sizeof(uint32_t);
244  if (auto EC = Writer.writeInteger(NumWords))
245  return joinErrors(
246  std::move(EC),
247  make_error<RawError>(raw_error_code::corrupt_file,
248  "Could not write linear map number of words"));
249 
250  uint32_t Idx = 0;
251  for (uint32_t I = 0; I != NumWords; ++I) {
252  uint32_t Word = 0;
253  for (uint32_t WordIdx = 0; WordIdx < 32; ++WordIdx, ++Idx) {
254  if (Vec.test(Idx))
255  Word |= (1 << WordIdx);
256  }
257  if (auto EC = Writer.writeInteger(Word))
258  return joinErrors(std::move(EC), make_error<RawError>(
260  "Could not write linear map word"));
261  }
262  return Error::success();
263 }
264 
265 HashTableIterator::HashTableIterator(const HashTable &Map, uint32_t Index,
266  bool IsEnd)
267  : Map(&Map), Index(Index), IsEnd(IsEnd) {}
268 
269 HashTableIterator::HashTableIterator(const HashTable &Map) : Map(&Map) {
270  int I = Map.Present.find_first();
271  if (I == -1) {
272  Index = 0;
273  IsEnd = true;
274  } else {
275  Index = static_cast<uint32_t>(I);
276  IsEnd = false;
277  }
278 }
279 
281  Map = R.Map;
282  return *this;
283 }
284 
286  if (IsEnd && R.IsEnd)
287  return true;
288  if (IsEnd != R.IsEnd)
289  return false;
290 
291  return (Map == R.Map) && (Index == R.Index);
292 }
293 
294 const std::pair<uint32_t, uint32_t> &HashTableIterator::operator*() const {
295  assert(Map->Present.test(Index));
296  return Map->Buckets[Index];
297 }
298 
300  while (Index < Map->Buckets.size()) {
301  ++Index;
302  if (Map->Present.test(Index))
303  return *this;
304  }
305 
306  IsEnd = true;
307  return *this;
308 }
Error writeObject(const T &Obj)
Writes the object Obj to the underlying stream, as if by using memcpy.
const std::pair< uint32_t, uint32_t > & operator*() const
Definition: HashTable.cpp:294
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Error readInteger(T &Dest)
Read an integer of the specified endianness into Dest and update the stream&#39;s offset.
HashTableIterator & operator++()
Definition: HashTable.cpp:299
Error commit(BinaryStreamWriter &Writer) const
Definition: HashTable.cpp:84
void set(unsigned Idx)
SparseBitVector Present
Definition: HashTable.h:68
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
unsigned count() const
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:677
bool test(unsigned Idx)
support::ulittle32_t Word
Definition: IRSymtab.h:51
friend class HashTableIterator
Definition: HashTable.h:32
void set(uint32_t K, uint32_t V)
Definition: HashTable.cpp:151
HashTableIterator end() const
Definition: HashTable.cpp:118
HashTableIterator begin() const
Definition: HashTable.cpp:116
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
uint32_t size() const
Definition: HashTable.cpp:114
bool isPresent(uint32_t K) const
Definition: HashTable.h:64
HashTableIterator find(uint32_t K)
Definition: HashTable.cpp:122
#define H(x, y, z)
Definition: MD5.cpp:57
uint32_t get(uint32_t K)
Definition: HashTable.cpp:186
Provides write only access to a subclass of WritableBinaryStream.
Error writeInteger(T Value)
Write the the integer Value to the underlying stream in the specified endianness. ...
HashTableIterator & operator=(const HashTableIterator &R)
Definition: HashTable.cpp:280
void reset(unsigned Idx)
Error load(BinaryStreamReader &Stream)
Definition: HashTable.cpp:29
BucketList Buckets
Definition: HashTable.h:67
unsigned first
void remove(uint32_t K)
Definition: HashTable.cpp:174
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
bool operator==(const HashTableIterator &R) const
Definition: HashTable.cpp:285
SparseBitVector Deleted
Definition: HashTable.h:69
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
uint32_t capacity() const
Definition: HashTable.cpp:112
Error joinErrors(Error E1, Error E2)
Concatenate errors.
Definition: Error.h:408
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
uint32_t calculateSerializedLength() const
Definition: HashTable.cpp:64
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
Provides read only access to a subclass of BinaryStream.
bool isDeleted(uint32_t K) const
Definition: HashTable.h:65
bool intersects(const SparseBitVector< ElementSize > *RHS) const