nridge created this revision.
nridge added a reviewer: kadircet.
Herald added subscribers: cfe-commits, arphaman, jkorous, MaskRay, ioeric,
ilya-biryukov.
Herald added a project: clang.
RelationSlab is a new index data structure, similar to SymbolSlab and
RefSlab. RelationSlab stores relations between Symbols.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D59407
Files:
clang-tools-extra/clangd/index/Index.cpp
clang-tools-extra/clangd/index/Index.h
Index: clang-tools-extra/clangd/index/Index.h
===================================================================
--- clang-tools-extra/clangd/index/Index.h
+++ clang-tools-extra/clangd/index/Index.h
@@ -22,6 +22,71 @@
namespace clang {
namespace clangd {
+enum class RelationKind { Subtype };
+
+struct RelationKey {
+ SymbolID Symbol;
+ RelationKind Kind;
+
+ bool operator==(const RelationKey &Other) const {
+ return Symbol == Other.Symbol && Kind == Other.Kind;
+ }
+
+private:
+ friend llvm::hash_code hash_value(const RelationKey &Key) {
+ return llvm::hash_combine(Key.Symbol, static_cast<int>(Key.Kind));
+ }
+};
+
+class RelationSlab {
+public:
+ using value_type = std::pair<RelationKey, llvm::ArrayRef<SymbolID>>;
+ using const_iterator = std::vector<value_type>::const_iterator;
+ using iterator = const_iterator;
+
+ RelationSlab() = default;
+ RelationSlab(RelationSlab &&Slab) = default;
+ RelationSlab &operator=(RelationSlab &&RHS) = default;
+
+ const_iterator begin() const { return Relations.begin(); }
+ const_iterator end() const { return Relations.end(); }
+ size_t size() const { return Relations.size(); }
+ size_t numRelations() const { return NumRelations; }
+ bool empty() const { return Relations.empty(); }
+
+ size_t bytes() const {
+ return sizeof(*this) + Arena.getTotalMemory() +
+ sizeof(value_type) * Relations.size();
+ }
+
+ // RelationSlab::Builder is a mutable container that can 'freeze' to
+ // RelationSlab.
+ class Builder {
+ public:
+ Builder() {}
+ // Adds a relation to the slab. Deep copy: Strings will be owned by the
+ // slab.
+ void insert(const RelationKey &Key, const SymbolID &S);
+ // Consumes the builder to finalize the slab.
+ RelationSlab build() &&;
+
+ private:
+ llvm::BumpPtrAllocator Arena;
+ llvm::DenseMap<RelationKey, std::vector<SymbolID>> Relations;
+ };
+
+private:
+ RelationSlab(std::vector<value_type> Relations, llvm::BumpPtrAllocator Arena,
+ size_t NumRelations)
+ : Arena(std::move(Arena)), Relations(std::move(Relations)),
+ NumRelations(NumRelations) {}
+
+ llvm::BumpPtrAllocator Arena;
+ std::vector<value_type> Relations;
+ // Number of all relations.
+ size_t NumRelations = 0;
+};
+
struct FuzzyFindRequest {
/// \brief A query string for the fuzzy find. This is matched against symbols'
/// un-qualified identifiers and should not contain qualifiers like "::".
@@ -136,4 +201,30 @@
} // namespace clangd
} // namespace clang
+namespace llvm {
+
+// Support RelationKeys as DenseMap keys.
+template <> struct DenseMapInfo<clang::clangd::RelationKey> {
+ static inline clang::clangd::RelationKey getEmptyKey() {
+ return {DenseMapInfo<clang::clangd::SymbolID>::getEmptyKey(),
+ clang::clangd::RelationKind::Subtype};
+ }
+
+ static inline clang::clangd::RelationKey getTombstoneKey() {
+ return {DenseMapInfo<clang::clangd::SymbolID>::getTombstoneKey(),
+ clang::clangd::RelationKind::Subtype};
+ }
+
+ static unsigned getHashValue(const clang::clangd::RelationKey &Key) {
+ return hash_value(Key);
+ }
+
+ static bool isEqual(const clang::clangd::RelationKey &LHS,
+ const clang::clangd::RelationKey &RHS) {
+ return LHS == RHS;
+ }
+};
+
+} // namespace llvm
+
#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
Index: clang-tools-extra/clangd/index/Index.cpp
===================================================================
--- clang-tools-extra/clangd/index/Index.cpp
+++ clang-tools-extra/clangd/index/Index.cpp
@@ -17,6 +17,28 @@
namespace clang {
namespace clangd {
+void RelationSlab::Builder::insert(const RelationKey &Key, const SymbolID &S) {
+ Relations[Key].push_back(S);
+}
+
+RelationSlab RelationSlab::Builder::build() && {
+ // Reallocate relations on the arena to reduce waste and indirections when
+ // reading.
+ std::vector<std::pair<RelationKey, llvm::ArrayRef<SymbolID>>> Result;
+ Result.reserve(Relations.size());
+ size_t NumRelations = 0;
+ for (auto &Entry : Relations) {
+ auto &Rels = Entry.second;
+
+ NumRelations += Rels.size();
+ auto *Array = Arena.Allocate<SymbolID>(Rels.size());
+ std::uninitialized_copy(Rels.begin(), Rels.end(), Array);
+ Result.emplace_back(Entry.first,
+ llvm::ArrayRef<SymbolID>(Array, Rels.size()));
+ }
+ return RelationSlab(std::move(Result), std::move(Arena), NumRelations);
+}
+
void SwapIndex::reset(std::unique_ptr<SymbolIndex> Index) {
// Keep the old index alive, so we don't destroy it under lock (may be slow).
std::shared_ptr<SymbolIndex> Pin;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
