clang  6.0.0svn
MultiOnDiskHashTable.h
Go to the documentation of this file.
1 //===--- MultiOnDiskHashTable.h - Merged set of hash tables -----*- C++ -*-===//
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 //
10 // This file provides a hash table data structure suitable for incremental and
11 // distributed storage across a set of files.
12 //
13 // Multiple hash tables from different files are implicitly merged to improve
14 // performance, and on reload the merged table will override those from other
15 // files.
16 //
17 //===----------------------------------------------------------------------===//
18 #ifndef LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H
19 #define LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H
20 
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/PointerUnion.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/TinyPtrVector.h"
26 #include "llvm/Support/EndianStream.h"
27 #include "llvm/Support/OnDiskHashTable.h"
28 
29 namespace clang {
30 namespace serialization {
31 
32 class ModuleFile;
33 
34 /// \brief A collection of on-disk hash tables, merged when relevant for performance.
35 template<typename Info> class MultiOnDiskHashTable {
36 public:
37  /// A handle to a file, used when overriding tables.
38  typedef typename Info::file_type file_type;
39  /// A pointer to an on-disk representation of the hash table.
40  typedef const unsigned char *storage_type;
41 
42  typedef typename Info::external_key_type external_key_type;
43  typedef typename Info::internal_key_type internal_key_type;
44  typedef typename Info::data_type data_type;
45  typedef typename Info::data_type_builder data_type_builder;
46  typedef unsigned hash_value_type;
47 
48 private:
49  /// \brief A hash table stored on disk.
50  struct OnDiskTable {
52 
53  file_type File;
54  HashTable Table;
55 
56  OnDiskTable(file_type File, unsigned NumBuckets, unsigned NumEntries,
57  storage_type Buckets, storage_type Payload, storage_type Base,
58  const Info &InfoObj)
59  : File(File),
60  Table(NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj) {}
61  };
62 
63  struct MergedTable {
64  std::vector<file_type> Files;
65  llvm::DenseMap<internal_key_type, data_type> Data;
66  };
67 
68  typedef llvm::PointerUnion<OnDiskTable*, MergedTable*> Table;
69  typedef llvm::TinyPtrVector<void*> TableVector;
70 
71  /// \brief The current set of on-disk and merged tables.
72  /// We manually store the opaque value of the Table because TinyPtrVector
73  /// can't cope with holding a PointerUnion directly.
74  /// There can be at most one MergedTable in this vector, and if present,
75  /// it is the first table.
76  TableVector Tables;
77 
78  /// \brief Files corresponding to overridden tables that we've not yet
79  /// discarded.
80  llvm::TinyPtrVector<file_type> PendingOverrides;
81 
82  struct AsOnDiskTable {
83  typedef OnDiskTable *result_type;
84  result_type operator()(void *P) const {
85  return Table::getFromOpaqueValue(P).template get<OnDiskTable *>();
86  }
87  };
88  typedef llvm::mapped_iterator<TableVector::iterator, AsOnDiskTable>
89  table_iterator;
90  typedef llvm::iterator_range<table_iterator> table_range;
91 
92  /// \brief The current set of on-disk tables.
93  table_range tables() {
94  auto Begin = Tables.begin(), End = Tables.end();
95  if (getMergedTable())
96  ++Begin;
97  return llvm::make_range(llvm::map_iterator(Begin, AsOnDiskTable()),
98  llvm::map_iterator(End, AsOnDiskTable()));
99  }
100 
101  MergedTable *getMergedTable() const {
102  // If we already have a merged table, it's the first one.
103  return Tables.empty() ? nullptr : Table::getFromOpaqueValue(*Tables.begin())
104  .template dyn_cast<MergedTable*>();
105  }
106 
107  /// \brief Delete all our current on-disk tables.
108  void clear() {
109  for (auto *T : tables())
110  delete T;
111  if (auto *M = getMergedTable())
112  delete M;
113  Tables.clear();
114  }
115 
116  void removeOverriddenTables() {
118  Files.insert(PendingOverrides.begin(), PendingOverrides.end());
119  // Explicitly capture Files to work around an MSVC 2015 rejects-valid bug.
120  auto ShouldRemove = [&Files](void *T) -> bool {
121  auto *ODT = Table::getFromOpaqueValue(T).template get<OnDiskTable *>();
122  bool Remove = Files.count(ODT->File);
123  if (Remove)
124  delete ODT;
125  return Remove;
126  };
127  Tables.erase(std::remove_if(tables().begin().getCurrent(), Tables.end(),
128  ShouldRemove),
129  Tables.end());
130  PendingOverrides.clear();
131  }
132 
133  void condense() {
134  MergedTable *Merged = getMergedTable();
135  if (!Merged)
136  Merged = new MergedTable;
137 
138  // Read in all the tables and merge them together.
139  // FIXME: Be smarter about which tables we merge.
140  for (auto *ODT : tables()) {
141  auto &HT = ODT->Table;
142  Info &InfoObj = HT.getInfoObj();
143 
144  for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) {
145  auto *LocalPtr = I.getItem();
146 
147  // FIXME: Don't rely on the OnDiskHashTable format here.
148  auto L = InfoObj.ReadKeyDataLength(LocalPtr);
149  const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
150  data_type_builder ValueBuilder(Merged->Data[Key]);
151  InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second,
152  ValueBuilder);
153  }
154 
155  Merged->Files.push_back(ODT->File);
156  delete ODT;
157  }
158 
159  Tables.clear();
160  Tables.push_back(Table(Merged).getOpaqueValue());
161  }
162 
163  /// The generator is permitted to read our merged table.
164  template<typename ReaderInfo, typename WriterInfo>
166 
167 public:
170  : Tables(std::move(O.Tables)),
171  PendingOverrides(std::move(O.PendingOverrides)) {
172  O.Tables.clear();
173  }
175  if (&O == this)
176  return *this;
177  clear();
178  Tables = std::move(O.Tables);
179  O.Tables.clear();
180  PendingOverrides = std::move(O.PendingOverrides);
181  return *this;
182  }
184 
185  /// \brief Add the table \p Data loaded from file \p File.
186  void add(file_type File, storage_type Data, Info InfoObj = Info()) {
187  using namespace llvm::support;
188  storage_type Ptr = Data;
189 
190  uint32_t BucketOffset = endian::readNext<uint32_t, little, unaligned>(Ptr);
191 
192  // Read the list of overridden files.
193  uint32_t NumFiles = endian::readNext<uint32_t, little, unaligned>(Ptr);
194  // FIXME: Add a reserve() to TinyPtrVector so that we don't need to make
195  // an additional copy.
196  llvm::SmallVector<file_type, 16> OverriddenFiles;
197  OverriddenFiles.reserve(NumFiles);
198  for (/**/; NumFiles != 0; --NumFiles)
199  OverriddenFiles.push_back(InfoObj.ReadFileRef(Ptr));
200  PendingOverrides.insert(PendingOverrides.end(), OverriddenFiles.begin(),
201  OverriddenFiles.end());
202 
203  // Read the OnDiskChainedHashTable header.
204  storage_type Buckets = Data + BucketOffset;
205  auto NumBucketsAndEntries =
206  OnDiskTable::HashTable::readNumBucketsAndEntries(Buckets);
207 
208  // Register the table.
209  Table NewTable = new OnDiskTable(File, NumBucketsAndEntries.first,
210  NumBucketsAndEntries.second,
211  Buckets, Ptr, Data, std::move(InfoObj));
212  Tables.push_back(NewTable.getOpaqueValue());
213  }
214 
215  /// \brief Find and read the lookup results for \p EKey.
216  data_type find(const external_key_type &EKey) {
217  data_type Result;
218 
219  if (!PendingOverrides.empty())
220  removeOverriddenTables();
221 
222  if (Tables.size() > static_cast<unsigned>(Info::MaxTables))
223  condense();
224 
225  internal_key_type Key = Info::GetInternalKey(EKey);
226  auto KeyHash = Info::ComputeHash(Key);
227 
228  if (MergedTable *M = getMergedTable()) {
229  auto It = M->Data.find(Key);
230  if (It != M->Data.end())
231  Result = It->second;
232  }
233 
234  data_type_builder ResultBuilder(Result);
235 
236  for (auto *ODT : tables()) {
237  auto &HT = ODT->Table;
238  auto It = HT.find_hashed(Key, KeyHash);
239  if (It != HT.end())
240  HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(),
241  ResultBuilder);
242  }
243 
244  return Result;
245  }
246 
247  /// \brief Read all the lookup results into a single value. This only makes
248  /// sense if merging values across keys is meaningful.
249  data_type findAll() {
250  data_type Result;
251  data_type_builder ResultBuilder(Result);
252 
253  if (!PendingOverrides.empty())
254  removeOverriddenTables();
255 
256  if (MergedTable *M = getMergedTable()) {
257  for (auto &KV : M->Data)
258  Info::MergeDataInto(KV.second, ResultBuilder);
259  }
260 
261  for (auto *ODT : tables()) {
262  auto &HT = ODT->Table;
263  Info &InfoObj = HT.getInfoObj();
264  for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) {
265  auto *LocalPtr = I.getItem();
266 
267  // FIXME: Don't rely on the OnDiskHashTable format here.
268  auto L = InfoObj.ReadKeyDataLength(LocalPtr);
269  const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
270  InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder);
271  }
272  }
273 
274  return Result;
275  }
276 };
277 
278 /// \brief Writer for the on-disk hash table.
279 template<typename ReaderInfo, typename WriterInfo>
282  typedef llvm::OnDiskChainedHashTableGenerator<WriterInfo> Generator;
283 
284  Generator Gen;
285 
286 public:
288 
289  void insert(typename WriterInfo::key_type_ref Key,
290  typename WriterInfo::data_type_ref Data, WriterInfo &Info) {
291  Gen.insert(Key, Data, Info);
292  }
293 
294  void emit(llvm::SmallVectorImpl<char> &Out, WriterInfo &Info,
295  const BaseTable *Base) {
296  using namespace llvm::support;
297  llvm::raw_svector_ostream OutStream(Out);
298 
299  // Write our header information.
300  {
301  endian::Writer<little> Writer(OutStream);
302 
303  // Reserve four bytes for the bucket offset.
304  Writer.write<uint32_t>(0);
305 
306  if (auto *Merged = Base ? Base->getMergedTable() : nullptr) {
307  // Write list of overridden files.
308  Writer.write<uint32_t>(Merged->Files.size());
309  for (const auto &F : Merged->Files)
310  Info.EmitFileRef(OutStream, F);
311 
312  // Add all merged entries from Base to the generator.
313  for (auto &KV : Merged->Data) {
314  if (!Gen.contains(KV.first, Info))
315  Gen.insert(KV.first, Info.ImportData(KV.second), Info);
316  }
317  } else {
318  Writer.write<uint32_t>(0);
319  }
320  }
321 
322  // Write the table itself.
323  uint32_t BucketOffset = Gen.Emit(OutStream, Info);
324 
325  // Replace the first four bytes with the bucket offset.
326  endian::write32le(Out.data(), BucketOffset);
327  }
328 };
329 
330 } // end namespace clang::serialization
331 } // end namespace clang
332 
333 
334 #endif
StringRef P
virtual void clear()
Definition: Format.h:1821
void insert(typename WriterInfo::key_type_ref Key, typename WriterInfo::data_type_ref Data, WriterInfo &Info)
data_type find(const external_key_type &EKey)
Find and read the lookup results for EKey.
A collection of on-disk hash tables, merged when relevant for performance.
SourceLocation End
const FunctionProtoType * T
SourceLocation Begin
const unsigned char * storage_type
A pointer to an on-disk representation of the hash table.
unsigned ComputeHash(Selector Sel)
Definition: ASTCommon.cpp:167
Dataflow Directional Tag Classes.
void emit(llvm::SmallVectorImpl< char > &Out, WriterInfo &Info, const BaseTable *Base)
MultiOnDiskHashTable & operator=(MultiOnDiskHashTable &&O)
data_type findAll()
Read all the lookup results into a single value.
void add(file_type File, storage_type Data, Info InfoObj=Info())
Add the table Data loaded from file File.
Info::file_type file_type
A handle to a file, used when overriding tables.