1 // Copyright 2019 PDFium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef CORE_FXCRT_TREE_NODE_H_
6 #define CORE_FXCRT_TREE_NODE_H_
7 
8 #include "core/fxcrt/fx_system.h"
9 #include "third_party/base/logging.h"
10 
11 namespace fxcrt {
12 
13 // Implements the usual DOM/XML-ish trees.
14 template <typename T>
15 class TreeNode {
16  public:
17   TreeNode() = default;
18   virtual ~TreeNode() = default;
19 
GetParent()20   T* GetParent() const { return m_pParent; }
GetFirstChild()21   T* GetFirstChild() const { return m_pFirstChild; }
GetLastChild()22   T* GetLastChild() const { return m_pLastChild; }
GetNextSibling()23   T* GetNextSibling() const { return m_pNextSibling; }
GetPrevSibling()24   T* GetPrevSibling() const { return m_pPrevSibling; }
25 
HasChild(const T * child)26   bool HasChild(const T* child) const {
27     return child != this && child->m_pParent == this;
28   }
29 
GetNthChild(int32_t n)30   T* GetNthChild(int32_t n) {
31     if (n < 0)
32       return nullptr;
33     T* result = GetFirstChild();
34     while (n-- && result) {
35       result = result->GetNextSibling();
36     }
37     return result;
38   }
39 
AppendFirstChild(T * child)40   void AppendFirstChild(T* child) {
41     BecomeParent(child);
42     if (m_pFirstChild) {
43       CHECK(m_pLastChild);
44       m_pFirstChild->m_pPrevSibling = child;
45       child->m_pNextSibling = m_pFirstChild;
46       m_pFirstChild = child;
47     } else {
48       CHECK(!m_pLastChild);
49       m_pFirstChild = child;
50       m_pLastChild = child;
51     }
52   }
53 
AppendLastChild(T * child)54   void AppendLastChild(T* child) {
55     BecomeParent(child);
56     if (m_pLastChild) {
57       CHECK(m_pFirstChild);
58       m_pLastChild->m_pNextSibling = child;
59       child->m_pPrevSibling = m_pLastChild;
60       m_pLastChild = child;
61     } else {
62       CHECK(!m_pFirstChild);
63       m_pFirstChild = child;
64       m_pLastChild = child;
65     }
66   }
67 
InsertBefore(T * child,T * other)68   void InsertBefore(T* child, T* other) {
69     if (!other) {
70       AppendLastChild(child);
71       return;
72     }
73     BecomeParent(child);
74     CHECK(HasChild(other));
75     child->m_pNextSibling = other;
76     child->m_pPrevSibling = other->m_pPrevSibling;
77     if (m_pFirstChild == other) {
78       CHECK(!other->m_pPrevSibling);
79       m_pFirstChild = child;
80     } else {
81       other->m_pPrevSibling->m_pNextSibling = child;
82     }
83     other->m_pPrevSibling = child;
84   }
85 
InsertAfter(T * child,T * other)86   void InsertAfter(T* child, T* other) {
87     if (!other) {
88       AppendFirstChild(child);
89       return;
90     }
91     BecomeParent(child);
92     CHECK(HasChild(other));
93     child->m_pNextSibling = other->m_pNextSibling;
94     child->m_pPrevSibling = other;
95     if (m_pLastChild == other) {
96       CHECK(!other->m_pNextSibling);
97       m_pLastChild = child;
98     } else {
99       other->m_pNextSibling->m_pPrevSibling = child;
100     }
101     other->m_pNextSibling = child;
102   }
103 
RemoveChild(T * child)104   void RemoveChild(T* child) {
105     CHECK(HasChild(child));
106     if (m_pLastChild == child) {
107       CHECK(!child->m_pNextSibling);
108       m_pLastChild = child->m_pPrevSibling;
109     } else {
110       child->m_pNextSibling->m_pPrevSibling = child->m_pPrevSibling;
111     }
112     if (m_pFirstChild == child) {
113       CHECK(!child->m_pPrevSibling);
114       m_pFirstChild = child->m_pNextSibling;
115     } else {
116       child->m_pPrevSibling->m_pNextSibling = child->m_pNextSibling;
117     }
118     child->m_pParent = nullptr;
119     child->m_pPrevSibling = nullptr;
120     child->m_pNextSibling = nullptr;
121   }
122 
RemoveAllChildren()123   void RemoveAllChildren() {
124     while (T* child = GetFirstChild())
125       RemoveChild(child);
126   }
127 
RemoveSelfIfParented()128   void RemoveSelfIfParented() {
129     if (T* parent = GetParent())
130       parent->RemoveChild(static_cast<T*>(this));
131   }
132 
133  private:
134   // Child left in state where sibling members need subsequent adjustment.
BecomeParent(T * child)135   void BecomeParent(T* child) {
136     CHECK(child != this);  // Detect attempts at self-insertion.
137     if (child->m_pParent)
138       child->m_pParent->TreeNode<T>::RemoveChild(child);
139     child->m_pParent = static_cast<T*>(this);
140     CHECK(!child->m_pNextSibling);
141     CHECK(!child->m_pPrevSibling);
142   }
143 
144   T* m_pParent = nullptr;       // Raw, intra-tree pointer.
145   T* m_pFirstChild = nullptr;   // Raw, intra-tree pointer.
146   T* m_pLastChild = nullptr;    // Raw, intra-tree pointer.
147   T* m_pNextSibling = nullptr;  // Raw, intra-tree pointer
148   T* m_pPrevSibling = nullptr;  // Raw, intra-tree pointer
149 };
150 
151 }  // namespace fxcrt
152 
153 using fxcrt::TreeNode;
154 
155 #endif  // CORE_FXCRT_TREE_NODE_H_
156