1 files changed, 346 insertions, 0 deletions

diff --git a/contrib/llvm-project/clang/lib/Serialization/MultiOnDiskHashTable.h b/contrib/llvm-project/clang/lib/Serialization/MultiOnDiskHashTable.h
new file mode 100644
index 000000000000..adc97d57e0ac
--- /dev/null
+++ b/contrib/llvm-project/clang/lib/Serialization/MultiOnDiskHashTable.h
@@ -0,0 +1,346 @@
+//===- MultiOnDiskHashTable.h - Merged set of hash tables -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file provides a hash table data structure suitable for incremental and
+//  distributed storage across a set of files.
+//
+//  Multiple hash tables from different files are implicitly merged to improve
+//  performance, and on reload the merged table will override those from other
+//  files.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H
+#define LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/TinyPtrVector.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/EndianStream.h"
+#include "llvm/Support/OnDiskHashTable.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cstdint>
+#include <vector>
+
+namespace clang {
+namespace serialization {
+
+/// A collection of on-disk hash tables, merged when relevant for performance.
+template<typename Info> class MultiOnDiskHashTable {
+public:
+  /// A handle to a file, used when overriding tables.
+  using file_type = typename Info::file_type;
+
+  /// A pointer to an on-disk representation of the hash table.
+  using storage_type = const unsigned char *;
+
+  using external_key_type = typename Info::external_key_type;
+  using internal_key_type = typename Info::internal_key_type;
+  using data_type = typename Info::data_type;
+  using data_type_builder = typename Info::data_type_builder;
+  using hash_value_type = unsigned;
+
+private:
+  /// The generator is permitted to read our merged table.
+  template<typename ReaderInfo, typename WriterInfo>
+  friend class MultiOnDiskHashTableGenerator;
+
+  /// A hash table stored on disk.
+  struct OnDiskTable {
+    using HashTable = llvm::OnDiskIterableChainedHashTable<Info>;
+
+    file_type File;
+    HashTable Table;
+
+    OnDiskTable(file_type File, unsigned NumBuckets, unsigned NumEntries,
+                storage_type Buckets, storage_type Payload, storage_type Base,
+                const Info &InfoObj)
+        : File(File),
+          Table(NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj) {}
+  };
+
+  struct MergedTable {
+    std::vector<file_type> Files;
+    llvm::DenseMap<internal_key_type, data_type> Data;
+  };
+
+  using Table = llvm::PointerUnion<OnDiskTable *, MergedTable *>;
+  using TableVector = llvm::TinyPtrVector<void *>;
+
+  /// The current set of on-disk and merged tables.
+  /// We manually store the opaque value of the Table because TinyPtrVector
+  /// can't cope with holding a PointerUnion directly.
+  /// There can be at most one MergedTable in this vector, and if present,
+  /// it is the first table.
+  TableVector Tables;
+
+  /// Files corresponding to overridden tables that we've not yet
+  /// discarded.
+  llvm::TinyPtrVector<file_type> PendingOverrides;
+
+  struct AsOnDiskTable {
+    using result_type = OnDiskTable *;
+
+    result_type operator()(void *P) const {
+      return Table::getFromOpaqueValue(P).template get<OnDiskTable *>();
+    }
+  };
+
+  using table_iterator =
+      llvm::mapped_iterator<TableVector::iterator, AsOnDiskTable>;
+  using table_range = llvm::iterator_range<table_iterator>;
+
+  /// The current set of on-disk tables.
+  table_range tables() {
+    auto Begin = Tables.begin(), End = Tables.end();
+    if (getMergedTable())
+      ++Begin;
+    return llvm::make_range(llvm::map_iterator(Begin, AsOnDiskTable()),
+                            llvm::map_iterator(End, AsOnDiskTable()));
+  }
+
+  MergedTable *getMergedTable() const {
+    // If we already have a merged table, it's the first one.
+    return Tables.empty() ? nullptr : Table::getFromOpaqueValue(*Tables.begin())
+                                          .template dyn_cast<MergedTable*>();
+  }
+
+  /// Delete all our current on-disk tables.
+  void clear() {
+    for (auto *T : tables())
+      delete T;
+    if (auto *M = getMergedTable())
+      delete M;
+    Tables.clear();
+  }
+
+  void removeOverriddenTables() {
+    llvm::DenseSet<file_type> Files;
+    Files.insert(PendingOverrides.begin(), PendingOverrides.end());
+    // Explicitly capture Files to work around an MSVC 2015 rejects-valid bug.
+    auto ShouldRemove = [&Files](void *T) -> bool {
+      auto *ODT = Table::getFromOpaqueValue(T).template get<OnDiskTable *>();
+      bool Remove = Files.count(ODT->File);
+      if (Remove)
+        delete ODT;
+      return Remove;
+    };
+    Tables.erase(std::remove_if(tables().begin().getCurrent(), Tables.end(),
+                                ShouldRemove),
+                 Tables.end());
+    PendingOverrides.clear();
+  }
+
+  void condense() {
+    MergedTable *Merged = getMergedTable();
+    if (!Merged)
+      Merged = new MergedTable;
+
+    // Read in all the tables and merge them together.
+    // FIXME: Be smarter about which tables we merge.
+    for (auto *ODT : tables()) {
+      auto &HT = ODT->Table;
+      Info &InfoObj = HT.getInfoObj();
+
+      for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) {
+        auto *LocalPtr = I.getItem();
+
+        // FIXME: Don't rely on the OnDiskHashTable format here.
+        auto L = InfoObj.ReadKeyDataLength(LocalPtr);
+        const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
+        data_type_builder ValueBuilder(Merged->Data[Key]);
+        InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second,
+                             ValueBuilder);
+      }
+
+      Merged->Files.push_back(ODT->File);
+      delete ODT;
+    }
+
+    Tables.clear();
+    Tables.push_back(Table(Merged).getOpaqueValue());
+  }
+
+public:
+  MultiOnDiskHashTable() = default;
+
+  MultiOnDiskHashTable(MultiOnDiskHashTable &&O)
+      : Tables(std::move(O.Tables)),
+        PendingOverrides(std::move(O.PendingOverrides)) {
+    O.Tables.clear();
+  }
+
+  MultiOnDiskHashTable &operator=(MultiOnDiskHashTable &&O) {
+    if (&O == this)
+      return *this;
+    clear();
+    Tables = std::move(O.Tables);
+    O.Tables.clear();
+    PendingOverrides = std::move(O.PendingOverrides);
+    return *this;
+  }
+
+  ~MultiOnDiskHashTable() { clear(); }
+
+  /// Add the table \p Data loaded from file \p File.
+  void add(file_type File, storage_type Data, Info InfoObj = Info()) {
+    using namespace llvm::support;
+
+    storage_type Ptr = Data;
+
+    uint32_t BucketOffset = endian::readNext<uint32_t, little, unaligned>(Ptr);
+
+    // Read the list of overridden files.
+    uint32_t NumFiles = endian::readNext<uint32_t, little, unaligned>(Ptr);
+    // FIXME: Add a reserve() to TinyPtrVector so that we don't need to make
+    // an additional copy.
+    llvm::SmallVector<file_type, 16> OverriddenFiles;
+    OverriddenFiles.reserve(NumFiles);
+    for (/**/; NumFiles != 0; --NumFiles)
+      OverriddenFiles.push_back(InfoObj.ReadFileRef(Ptr));
+    PendingOverrides.insert(PendingOverrides.end(), OverriddenFiles.begin(),
+                            OverriddenFiles.end());
+
+    // Read the OnDiskChainedHashTable header.
+    storage_type Buckets = Data + BucketOffset;
+    auto NumBucketsAndEntries =
+        OnDiskTable::HashTable::readNumBucketsAndEntries(Buckets);
+
+    // Register the table.
+    Table NewTable = new OnDiskTable(File, NumBucketsAndEntries.first,
+                                     NumBucketsAndEntries.second,
+                                     Buckets, Ptr, Data, std::move(InfoObj));
+    Tables.push_back(NewTable.getOpaqueValue());
+  }
+
+  /// Find and read the lookup results for \p EKey.
+  data_type find(const external_key_type &EKey) {
+    data_type Result;
+
+    if (!PendingOverrides.empty())
+      removeOverriddenTables();
+
+    if (Tables.size() > static_cast<unsigned>(Info::MaxTables))
+      condense();
+
+    internal_key_type Key = Info::GetInternalKey(EKey);
+    auto KeyHash = Info::ComputeHash(Key);
+
+    if (MergedTable *M = getMergedTable()) {
+      auto It = M->Data.find(Key);
+      if (It != M->Data.end())
+        Result = It->second;
+    }
+
+    data_type_builder ResultBuilder(Result);
+
+    for (auto *ODT : tables()) {
+      auto &HT = ODT->Table;
+      auto It = HT.find_hashed(Key, KeyHash);
+      if (It != HT.end())
+        HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(),
+                                     ResultBuilder);
+    }
+
+    return Result;
+  }
+
+  /// Read all the lookup results into a single value. This only makes
+  /// sense if merging values across keys is meaningful.
+  data_type findAll() {
+    data_type Result;
+    data_type_builder ResultBuilder(Result);
+
+    if (!PendingOverrides.empty())
+      removeOverriddenTables();
+
+    if (MergedTable *M = getMergedTable()) {
+      for (auto &KV : M->Data)
+        Info::MergeDataInto(KV.second, ResultBuilder);
+    }
+
+    for (auto *ODT : tables()) {
+      auto &HT = ODT->Table;
+      Info &InfoObj = HT.getInfoObj();
+      for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) {
+        auto *LocalPtr = I.getItem();
+
+        // FIXME: Don't rely on the OnDiskHashTable format here.
+        auto L = InfoObj.ReadKeyDataLength(LocalPtr);
+        const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
+        InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder);
+      }
+    }
+
+    return Result;
+  }
+};
+
+/// Writer for the on-disk hash table.
+template<typename ReaderInfo, typename WriterInfo>
+class MultiOnDiskHashTableGenerator {
+  using BaseTable = MultiOnDiskHashTable<ReaderInfo>;
+  using Generator = llvm::OnDiskChainedHashTableGenerator<WriterInfo>;
+
+  Generator Gen;
+
+public:
+  MultiOnDiskHashTableGenerator() : Gen() {}
+
+  void insert(typename WriterInfo::key_type_ref Key,
+              typename WriterInfo::data_type_ref Data, WriterInfo &Info) {
+    Gen.insert(Key, Data, Info);
+  }
+
+  void emit(llvm::SmallVectorImpl<char> &Out, WriterInfo &Info,
+            const BaseTable *Base) {
+    using namespace llvm::support;
+
+    llvm::raw_svector_ostream OutStream(Out);
+
+    // Write our header information.
+    {
+      endian::Writer Writer(OutStream, little);
+
+      // Reserve four bytes for the bucket offset.
+      Writer.write<uint32_t>(0);
+
+      if (auto *Merged = Base ? Base->getMergedTable() : nullptr) {
+        // Write list of overridden files.
+        Writer.write<uint32_t>(Merged->Files.size());
+        for (const auto &F : Merged->Files)
+          Info.EmitFileRef(OutStream, F);
+
+        // Add all merged entries from Base to the generator.
+        for (auto &KV : Merged->Data) {
+          if (!Gen.contains(KV.first, Info))
+            Gen.insert(KV.first, Info.ImportData(KV.second), Info);
+        }
+      } else {
+        Writer.write<uint32_t>(0);
+      }
+    }
+
+    // Write the table itself.
+    uint32_t BucketOffset = Gen.Emit(OutStream, Info);
+
+    // Replace the first four bytes with the bucket offset.
+    endian::write32le(Out.data(), BucketOffset);
+  }
+};
+
+} // namespace serialization
+} // namespace clang
+
+#endif // LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H