LLVM  7.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 
25 namespace {
26 struct IdentityTraits {
27  static uint32_t hash(uint32_t K, const HashTable &Ctx) { return K; }
28  static uint32_t realKey(uint32_t K, const HashTable &Ctx) { return K; }
29  static uint32_t lowerKey(uint32_t K, const HashTable &Ctx) { return K; }
30 };
31 } // namespace
32 
34 
35 HashTable::HashTable(uint32_t Capacity) { Buckets.resize(Capacity); }
36 
38  const Header *H;
39  if (auto EC = Stream.readObject(H))
40  return EC;
41  if (H->Capacity == 0)
42  return make_error<RawError>(raw_error_code::corrupt_file,
43  "Invalid Hash Table Capacity");
44  if (H->Size > maxLoad(H->Capacity))
45  return make_error<RawError>(raw_error_code::corrupt_file,
46  "Invalid Hash Table Size");
47 
48  Buckets.resize(H->Capacity);
49 
50  if (auto EC = readSparseBitVector(Stream, Present))
51  return EC;
52  if (Present.count() != H->Size)
53  return make_error<RawError>(raw_error_code::corrupt_file,
54  "Present bit vector does not match size!");
55 
56  if (auto EC = readSparseBitVector(Stream, Deleted))
57  return EC;
59  return make_error<RawError>(raw_error_code::corrupt_file,
60  "Present bit vector interesects deleted!");
61 
62  for (uint32_t P : Present) {
63  if (auto EC = Stream.readInteger(Buckets[P].first))
64  return EC;
65  if (auto EC = Stream.readInteger(Buckets[P].second))
66  return EC;
67  }
68 
69  return Error::success();
70 }
71 
73  uint32_t Size = sizeof(Header);
74 
75  int NumBitsP = Present.find_last() + 1;
76  int NumBitsD = Deleted.find_last() + 1;
77 
78  // Present bit set number of words, followed by that many actual words.
79  Size += sizeof(uint32_t);
80  Size += alignTo(NumBitsP, sizeof(uint32_t));
81 
82  // Deleted bit set number of words, followed by that many actual words.
83  Size += sizeof(uint32_t);
84  Size += alignTo(NumBitsD, sizeof(uint32_t));
85 
86  // One (Key, Value) pair for each entry Present.
87  Size += 2 * sizeof(uint32_t) * size();
88 
89  return Size;
90 }
91 
93  Header H;
94  H.Size = size();
95  H.Capacity = capacity();
96  if (auto EC = Writer.writeObject(H))
97  return EC;
98 
99  if (auto EC = writeSparseBitVector(Writer, Present))
100  return EC;
101 
102  if (auto EC = writeSparseBitVector(Writer, Deleted))
103  return EC;
104 
105  for (const auto &Entry : *this) {
106  if (auto EC = Writer.writeInteger(Entry.first))
107  return EC;
108  if (auto EC = Writer.writeInteger(Entry.second))
109  return EC;
110  }
111  return Error::success();
112 }
113 
115  Buckets.resize(8);
116  Present.clear();
117  Deleted.clear();
118 }
119 
120 uint32_t HashTable::capacity() const { return Buckets.size(); }
121 
122 uint32_t HashTable::size() const { return Present.count(); }
123 
125 
127  return HashTableIterator(*this, 0, true);
128 }
129 
131  return find_as<IdentityTraits>(K, *this);
132 }
133 
135  set_as<IdentityTraits, uint32_t>(K, V, *this);
136 }
137 
138 void HashTable::remove(uint32_t K) { remove_as<IdentityTraits>(K, *this); }
139 
141  auto I = find(K);
142  assert(I != end());
143  return (*I).second;
144 }
145 
146 uint32_t HashTable::maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; }
147 
148 Error HashTable::readSparseBitVector(BinaryStreamReader &Stream,
149  SparseBitVector<> &V) {
150  uint32_t NumWords;
151  if (auto EC = Stream.readInteger(NumWords))
152  return joinErrors(
153  std::move(EC),
154  make_error<RawError>(raw_error_code::corrupt_file,
155  "Expected hash table number of words"));
156 
157  for (uint32_t I = 0; I != NumWords; ++I) {
158  uint32_t Word;
159  if (auto EC = Stream.readInteger(Word))
160  return joinErrors(std::move(EC),
161  make_error<RawError>(raw_error_code::corrupt_file,
162  "Expected hash table word"));
163  for (unsigned Idx = 0; Idx < 32; ++Idx)
164  if (Word & (1U << Idx))
165  V.set((I * 32) + Idx);
166  }
167  return Error::success();
168 }
169 
170 Error HashTable::writeSparseBitVector(BinaryStreamWriter &Writer,
171  SparseBitVector<> &Vec) {
172  int ReqBits = Vec.find_last() + 1;
173  uint32_t NumWords = alignTo(ReqBits, sizeof(uint32_t)) / sizeof(uint32_t);
174  if (auto EC = Writer.writeInteger(NumWords))
175  return joinErrors(
176  std::move(EC),
177  make_error<RawError>(raw_error_code::corrupt_file,
178  "Could not write linear map number of words"));
179 
180  uint32_t Idx = 0;
181  for (uint32_t I = 0; I != NumWords; ++I) {
182  uint32_t Word = 0;
183  for (uint32_t WordIdx = 0; WordIdx < 32; ++WordIdx, ++Idx) {
184  if (Vec.test(Idx))
185  Word |= (1 << WordIdx);
186  }
187  if (auto EC = Writer.writeInteger(Word))
188  return joinErrors(std::move(EC), make_error<RawError>(
190  "Could not write linear map word"));
191  }
192  return Error::success();
193 }
194 
195 HashTableIterator::HashTableIterator(const HashTable &Map, uint32_t Index,
196  bool IsEnd)
197  : Map(&Map), Index(Index), IsEnd(IsEnd) {}
198 
199 HashTableIterator::HashTableIterator(const HashTable &Map) : Map(&Map) {
200  int I = Map.Present.find_first();
201  if (I == -1) {
202  Index = 0;
203  IsEnd = true;
204  } else {
205  Index = static_cast<uint32_t>(I);
206  IsEnd = false;
207  }
208 }
209 
211  Map = R.Map;
212  return *this;
213 }
214 
216  if (IsEnd && R.IsEnd)
217  return true;
218  if (IsEnd != R.IsEnd)
219  return false;
220 
221  return (Map == R.Map) && (Index == R.Index);
222 }
223 
224 const std::pair<uint32_t, uint32_t> &HashTableIterator::operator*() const {
225  assert(Map->Present.test(Index));
226  return Map->Buckets[Index];
227 }
228 
230  while (Index < Map->Buckets.size()) {
231  ++Index;
232  if (Map->Present.test(Index))
233  return *this;
234  }
235 
236  IsEnd = true;
237  return *this;
238 }
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:224
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:229
Error commit(BinaryStreamWriter &Writer) const
Definition: HashTable.cpp:92
void set(unsigned Idx)
SparseBitVector Present
Definition: HashTable.h:149
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 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:56
void set(uint32_t K, uint32_t V)
Set the entry with the specified key to the specified value.
Definition: HashTable.cpp:134
HashTableIterator end() const
Definition: HashTable.cpp:126
HashTableIterator find(uint32_t K) const
Find the entry with the specified key value.
Definition: HashTable.cpp:130
HashTableIterator begin() const
Definition: HashTable.cpp:124
#define P(N)
uint32_t size() const
Definition: HashTable.cpp:122
#define H(x, y, z)
Definition: MD5.cpp:57
uint32_t get(uint32_t K)
Definition: HashTable.cpp:140
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.
HashTableIterator & operator=(const HashTableIterator &R)
Definition: HashTable.cpp:210
Error load(BinaryStreamReader &Stream)
Definition: HashTable.cpp:37
BucketList Buckets
Definition: HashTable.h:148
void remove(uint32_t K)
Definition: HashTable.cpp:138
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
bool operator==(const HashTableIterator &R) const
Definition: HashTable.cpp:215
SparseBitVector Deleted
Definition: HashTable.h:150
uint32_t capacity() const
Definition: HashTable.cpp:120
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:72
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 intersects(const SparseBitVector< ElementSize > *RHS) const