1 #ifndef CPPROFILER_NODE_TREE_HH
2 #define CPPROFILER_NODE_TREE_HH
3 
4 #include "node.hh"
5 
6 #include "../core.hh"
7 
8 #include "memory"
9 
10 namespace cpprofiler
11 {
12 namespace tree
13 {
14 
15 struct invalid_tree : std::exception
16 {
whatcpprofiler::tree::invalid_tree17     const char *what() const throw() override
18     {
19         return "invalid tree\n";
20     }
21 };
22 
23 class LayoutComputer;
24 
25 /// Structure is responsible for dealing with the tree's structural information.
26 /// Since it is not aware of statuses, labels etc., it is the caller's responsibility
27 /// to ensure that this information is stored elsewhere when, for example, new nodes
28 /// are created using Structure's API.
29 class Structure
30 {
31 
32     /// Protects `nodes_`
33     mutable utils::Mutex mutex_;
34 
35     /// Nodes that describe the structure of the tree
36     std::vector<std::unique_ptr<Node>> nodes_;
37 
38     /// Allocate memory for a new node and return its Id
39     NodeID createNode(NodeID pid, int kids);
40 
41     /// Create a new node with `kids` kids and add set it as the `alt`th kid of `pid`
42     NodeID createChild(NodeID pid, int alt, int kids);
43 
44     void db_createNode(NodeID nid, NodeID pid, int kids);
45 
46   public:
47     Structure();
48 
49     /// Get mutex protecting structural information
50     utils::Mutex &getMutex() const;
51 
52     /// Get the identifier of the root (should be 0)
53     NodeID getRoot() const;
54 
55     /// Get the parent of node `nid` (returns NodeID::NoNode for root)
56     NodeID getParent(NodeID nid) const;
57 
58     /// Get the child of node `pid` at position `alt`
59     NodeID getChild(NodeID pid, int alt) const;
60 
61     /// Get the position of node `nid` relative to its left-most sibling
62     int getAlternative(NodeID nid) const;
63 
64     /// Get the total nuber of siblings of `nid` including the node itself
65     int getNumberOfSiblings(NodeID nid) const;
66 
67     /// Get the total number of children of node `pid`
68     int childrenCount(NodeID pid) const;
69 
70     /// Get the total nuber of nodes (including undetermined)
71     int nodeCount() const;
72 
73     /// ************ Modifying (building) a tree ************
74 
75     /// Create a root node and `kids` children
76     NodeID createRoot(int kids);
77 
78     /// Extend node's children with one more child
79     NodeID addExtraChild(NodeID nid);
80 
81     /// Add `kids` children to an open node
82     void addChildren(NodeID nid, int kids);
83 
84     /// Remove `alt` child of `pid`
85     void removeChild(NodeID pid, int alt);
86 
87     /// ************ Building a tree from a database ************
88 
89     void db_initialize(int size);
90 
91     void db_createRoot(NodeID nid);
92 
93     void db_createChild(NodeID nid, NodeID pid, int alt);
94 
95     void db_addChild(NodeID nid, NodeID pid, int alt);
96 };
97 
98 } // namespace tree
99 } // namespace cpprofiler
100 
101 #endif