1 //===--- MemoryTree.h - A special tree for components and sizes -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_MEMORYTREE_H_
10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_MEMORYTREE_H_
11 
12 #include "Trace.h"
13 #include "llvm/ADT/DenseMap.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/StringRef.h"
16 #include "llvm/Support/Allocator.h"
17 #include "llvm/Support/StringSaver.h"
18 #include <cstddef>
19 #include <string>
20 #include <vector>
21 
22 namespace clang {
23 namespace clangd {
24 
25 /// A tree that can be used to represent memory usage of nested components while
26 /// preserving the hierarchy.
27 /// Edges have associated names. An edge that might not be interesting to all
28 /// traversers or costly to copy (e.g. file names) can be marked as "detail".
29 /// Tree construction allows chosing between a detailed and brief mode, in brief
30 /// mode all "detail" edges are ignored and tree is constructed without any
31 /// string copies.
32 struct MemoryTree {
33 public:
34   /// If Alloc is nullptr, tree is in brief mode and will ignore detail edges.
35   MemoryTree(llvm::BumpPtrAllocator *DetailAlloc = nullptr)
DetailAllocMemoryTree36       : DetailAlloc(DetailAlloc) {}
37 
38   /// No copy of the \p Name.
39   /// Note that returned pointers are invalidated with subsequent calls to
40   /// child/detail.
childMemoryTree41   MemoryTree &child(llvm::StringLiteral Name) { return createChild(Name); }
42 
43   MemoryTree(const MemoryTree &) = delete;
44   MemoryTree &operator=(const MemoryTree &) = delete;
45 
46   MemoryTree(MemoryTree &&) = default;
47   MemoryTree &operator=(MemoryTree &&) = default;
48 
49   /// Makes a copy of the \p Name in detailed mode, returns current node
50   /// otherwise.
51   /// Note that returned pointers are invalidated with subsequent calls to
52   /// child/detail.
detailMemoryTree53   MemoryTree &detail(llvm::StringRef Name) {
54     return DetailAlloc ? createChild(Name.copy(*DetailAlloc)) : *this;
55   }
56 
57   /// Increases size of current node by \p Increment.
addUsageMemoryTree58   void addUsage(size_t Increment) { Size += Increment; }
59 
60   /// Returns edges to direct children of this node.
61   const llvm::DenseMap<llvm::StringRef, MemoryTree> &children() const;
62 
63   /// Returns total number of bytes used by this sub-tree. Performs a traversal.
64   size_t total() const;
65 
66   /// Returns total number of bytes used by this node only.
selfMemoryTree67   size_t self() const { return Size; }
68 
69 private:
70   /// Adds a child with an edge labeled as \p Name. Multiple calls to this
71   /// function returns the same node.
72   MemoryTree &createChild(llvm::StringRef Name);
73 
74   /// Allocator to use for detailed edge names.
75   llvm::BumpPtrAllocator *DetailAlloc = nullptr;
76 
77   /// Bytes owned by this component specifically.
78   size_t Size = 0;
79 
80   /// Edges from current node to its children. Keys are the labels for edges.
81   llvm::DenseMap<llvm::StringRef, MemoryTree> Children;
82 };
83 
84 /// Records total memory usage of each node under \p Out. Labels are edges on
85 /// the path joined with ".", starting with \p RootName.
86 void record(const MemoryTree &MT, std::string RootName,
87             const trace::Metric &Out);
88 
89 } // namespace clangd
90 } // namespace clang
91 
92 #endif
93