kadircet created this revision. kadircet added a reviewer: sammccall. Herald added subscribers: cfe-commits, usaxena95, arphaman, mgorny. Herald added a project: clang. kadircet requested review of this revision. Herald added subscribers: MaskRay, ilya-biryukov.
A structure that can be used to represent memory usage of a nested set of systems. Repository: rG LLVM Github Monorepo https://reviews.llvm.org/D88411 Files: clang-tools-extra/clangd/support/CMakeLists.txt clang-tools-extra/clangd/support/MemoryTree.cpp clang-tools-extra/clangd/support/MemoryTree.h clang-tools-extra/clangd/unittests/CMakeLists.txt clang-tools-extra/clangd/unittests/support/MemoryTreeTests.cpp
Index: clang-tools-extra/clangd/unittests/support/MemoryTreeTests.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/unittests/support/MemoryTreeTests.cpp @@ -0,0 +1,81 @@ +//===-- MemoryTreeTests.cpp -------------------------------------*- 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 +// +//===----------------------------------------------------------------------===// + +#include "support/MemoryTree.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +namespace clang { +namespace clangd { +namespace { +using testing::ElementsAreArray; + +TEST(MemoryTree, Traversal) { + // * + // | - leaf + // | - child1 + // | - leaf + // | - child2 (detailed) + // | - leaf + // | - child + // | - leaf + MemoryTree MT; + MT.addChild("leaf", 1); + { + MemoryTree Child1; + Child1.addChild("leaf", 1); + MT.addChild("child1", Child1); + { + MemoryTree Child2; + Child2.addChild("leaf", 1); + Child1.addChild("child", std::move(Child2)); + MT.addChild("child2", std::move(Child1), true); + } + } + + struct Component { + std::string Name; + size_t Size; + bool operator==(const Component &RHS) const { + return std::tie(Name, Size) == std::tie(RHS.Name, RHS.Size); + } + }; + std::vector<Component> SeenComponents; + auto CB = [&SeenComponents](size_t Size, llvm::StringRef CompName) { + Component C; + C.Name = CompName.str(); + C.Size = Size; + SeenComponents.emplace_back(std::move(C)); + }; + + // Ensure sizes and component names are reported correctly. + Component ExpectedComponents[] = { + {"", 0}, + {"leaf", 1}, + {"child1", 0}, + {"child1.leaf", 1}, + {"child2", 0}, + {"child2.leaf", 1}, + {"child2.child", 0}, + {"child2.child.leaf", 1}, + }; + MT.traverseTree(false, CB); + EXPECT_THAT(SeenComponents, ElementsAreArray(ExpectedComponents)); + SeenComponents.clear(); + + // Ensure detailed sub-trees are collapsed when requested. + Component ExpectedComponentsHidden[] = { + {"", 0}, {"leaf", 1}, {"child1", 0}, {"child1.leaf", 1}, {"child2", 2}, + }; + MT.traverseTree(true, CB); + EXPECT_THAT(SeenComponents, ElementsAreArray(ExpectedComponentsHidden)); +} + +} // namespace +} // namespace clangd +} // namespace clang Index: clang-tools-extra/clangd/unittests/CMakeLists.txt =================================================================== --- clang-tools-extra/clangd/unittests/CMakeLists.txt +++ clang-tools-extra/clangd/unittests/CMakeLists.txt @@ -99,6 +99,7 @@ support/ContextTests.cpp support/FunctionTests.cpp support/MarkupTests.cpp + support/MemoryTreeTests.cpp support/ThreadingTests.cpp support/TestTracer.cpp support/TraceTests.cpp Index: clang-tools-extra/clangd/support/MemoryTree.h =================================================================== --- /dev/null +++ clang-tools-extra/clangd/support/MemoryTree.h @@ -0,0 +1,52 @@ +//===--- MemoryTree.h - A special tree for components and sizes -*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_MEMORYTREE_H_ +#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_MEMORYTREE_H_ + +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/StringRef.h" +#include <cstddef> +#include <vector> + +namespace clang { +namespace clangd { + +/// A tree that can be used to represent memory usage of nested components while +/// preserving the hierarchy. +struct MemoryTree { +public: + void addChild(llvm::StringRef Name, MemoryTree MT, bool IsDetail = false); + void addChild(llvm::StringRef Name, size_t Size); + + /// Performs a pre-order traversal of the tree, while concatenating compenent + /// names with dots("."). + /// If CollapseDetails is set, accumulates the size of subtrees marked as + /// detail to root, and doesn't report any descendants. + void traverseTree(bool CollapseDetails, + llvm::function_ref<void(size_t /*Size*/, + llvm::StringRef /*ComponentName*/)> + CB, + llvm::StringRef ComponentPrefix = "") const; + +private: + // Enables optional traversal of the tree by collapsing any descendants into + // this node. + bool IsDetail = false; + // A human-readable identifier for the component. + std::string Name; + // Bytes owned by this component specifically. + size_t Size = 0; + // Significant components nested under current one. + std::vector<MemoryTree> Children; +}; + +} // namespace clangd +} // namespace clang + +#endif Index: clang-tools-extra/clangd/support/MemoryTree.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/support/MemoryTree.cpp @@ -0,0 +1,44 @@ +#include "support/MemoryTree.h" + +namespace clang { +namespace clangd { + +void MemoryTree::addChild(llvm::StringRef Name, MemoryTree MT, bool IsDetail) { + MT.IsDetail = IsDetail; + MT.Name = Name.str(); + Children.emplace_back(std::move(MT)); +} + +void MemoryTree::addChild(llvm::StringRef Name, size_t Size) { + Children.emplace_back(); + Children.back().Name = Name.str(); + Children.back().Size = Size; +} + +void MemoryTree::traverseTree( + bool CollapseDetails, llvm::function_ref<void(size_t, llvm::StringRef)> CB, + llvm::StringRef ComponentPrefix) const { + std::string ComponentName = ComponentPrefix.str(); + if (!ComponentName.empty()) + ComponentName += '.'; + ComponentName += Name; + + if (CollapseDetails && IsDetail) { + size_t ChildrenSize = 0; + for (const auto &C : Children) { + C.traverseTree(CollapseDetails, + [&ChildrenSize](size_t Size, llvm::StringRef) { + ChildrenSize += Size; + }); + } + CB(Size + ChildrenSize, ComponentName); + return; + } + + CB(Size, ComponentName); + for (const auto &C : Children) + C.traverseTree(CollapseDetails, CB, ComponentName); +} + +} // namespace clangd +} // namespace clang Index: clang-tools-extra/clangd/support/CMakeLists.txt =================================================================== --- clang-tools-extra/clangd/support/CMakeLists.txt +++ clang-tools-extra/clangd/support/CMakeLists.txt @@ -21,6 +21,7 @@ Context.cpp Logger.cpp Markup.cpp + MemoryTree.cpp Shutdown.cpp Threading.cpp ThreadsafeFS.cpp
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
