1 // Copyright 2019 The PDFium Authors 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 <stdint.h> 9 10 #include "third_party/base/check.h" 11 12 namespace fxcrt { 13 14 // Implements the usual DOM/XML-ish trees allowing for a variety of 15 // pointer types with which to connect the nodes. Public methods maintain 16 // the invariants of the tree. 17 18 template <typename T> 19 class TreeNodeBase { 20 public: 21 TreeNodeBase() = default; 22 virtual ~TreeNodeBase() = default; 23 GetParent()24 inline T* GetParent() const { return static_cast<const T*>(this)->m_pParent; } GetFirstChild()25 inline T* GetFirstChild() const { 26 return static_cast<const T*>(this)->m_pFirstChild; 27 } GetLastChild()28 inline T* GetLastChild() const { 29 return static_cast<const T*>(this)->m_pLastChild; 30 } GetNextSibling()31 inline T* GetNextSibling() const { 32 return static_cast<const T*>(this)->m_pNextSibling; 33 } GetPrevSibling()34 inline T* GetPrevSibling() const { 35 return static_cast<const T*>(this)->m_pPrevSibling; 36 } 37 HasChild(const T * child)38 bool HasChild(const T* child) const { 39 return child != this && child->GetParent() == this; 40 } 41 GetNthChild(int32_t n)42 T* GetNthChild(int32_t n) { 43 if (n < 0) 44 return nullptr; 45 T* result = GetFirstChild(); 46 while (n-- && result) { 47 result = result->GetNextSibling(); 48 } 49 return result; 50 } 51 AppendFirstChild(T * child)52 void AppendFirstChild(T* child) { 53 BecomeParent(child); 54 if (GetFirstChild()) { 55 CHECK(GetLastChild()); 56 GetFirstChild()->SetPrevSibling(child); 57 child->SetNextSibling(GetFirstChild()); 58 SetFirstChild(child); 59 } else { 60 CHECK(!GetLastChild()); 61 SetFirstChild(child); 62 SetLastChild(child); 63 } 64 } 65 AppendLastChild(T * child)66 void AppendLastChild(T* child) { 67 BecomeParent(child); 68 if (GetLastChild()) { 69 CHECK(GetFirstChild()); 70 GetLastChild()->SetNextSibling(child); 71 child->SetPrevSibling(GetLastChild()); 72 SetLastChild(child); 73 } else { 74 CHECK(!GetFirstChild()); 75 SetFirstChild(child); 76 SetLastChild(child); 77 } 78 } 79 InsertBefore(T * child,T * other)80 void InsertBefore(T* child, T* other) { 81 if (!other) { 82 AppendLastChild(child); 83 return; 84 } 85 BecomeParent(child); 86 CHECK(HasChild(other)); 87 child->SetNextSibling(other); 88 child->SetPrevSibling(other->GetPrevSibling()); 89 if (GetFirstChild() == other) { 90 CHECK(!other->GetPrevSibling()); 91 SetFirstChild(child); 92 } else { 93 other->GetPrevSibling()->SetNextSibling(child); 94 } 95 other->m_pPrevSibling = child; 96 } 97 InsertAfter(T * child,T * other)98 void InsertAfter(T* child, T* other) { 99 if (!other) { 100 AppendFirstChild(child); 101 return; 102 } 103 BecomeParent(child); 104 CHECK(HasChild(other)); 105 child->SetNextSibling(other->GetNextSibling()); 106 child->SetPrevSibling(other); 107 if (GetLastChild() == other) { 108 CHECK(!other->GetNextSibling()); 109 SetLastChild(child); 110 } else { 111 other->GetNextSibling()->SetPrevSibling(child); 112 } 113 other->SetNextSibling(child); 114 } 115 RemoveChild(T * child)116 void RemoveChild(T* child) { 117 CHECK(HasChild(child)); 118 if (GetLastChild() == child) { 119 CHECK(!child->GetNextSibling()); 120 SetLastChild(child->GetPrevSibling()); 121 } else { 122 child->GetNextSibling()->SetPrevSibling(child->GetPrevSibling()); 123 } 124 if (GetFirstChild() == child) { 125 CHECK(!child->GetPrevSibling()); 126 SetFirstChild(child->GetNextSibling()); 127 } else { 128 child->GetPrevSibling()->SetNextSibling(child->GetNextSibling()); 129 } 130 child->SetParent(nullptr); 131 child->SetPrevSibling(nullptr); 132 child->SetNextSibling(nullptr); 133 } 134 RemoveAllChildren()135 void RemoveAllChildren() { 136 while (T* child = GetFirstChild()) 137 RemoveChild(child); 138 } 139 RemoveSelfIfParented()140 void RemoveSelfIfParented() { 141 if (T* parent = GetParent()) 142 parent->RemoveChild(static_cast<T*>(this)); 143 } 144 145 private: 146 // These are private because they may leave the tree in an invalid state 147 // until subsequent operations restore it. SetParent(T * pParent)148 inline void SetParent(T* pParent) { 149 static_cast<T*>(this)->m_pParent = pParent; 150 } SetFirstChild(T * pChild)151 inline void SetFirstChild(T* pChild) { 152 static_cast<T*>(this)->m_pFirstChild = pChild; 153 } SetLastChild(T * pChild)154 inline void SetLastChild(T* pChild) { 155 static_cast<T*>(this)->m_pLastChild = pChild; 156 } SetNextSibling(T * pSibling)157 inline void SetNextSibling(T* pSibling) { 158 static_cast<T*>(this)->m_pNextSibling = pSibling; 159 } SetPrevSibling(T * pSibling)160 inline void SetPrevSibling(T* pSibling) { 161 static_cast<T*>(this)->m_pPrevSibling = pSibling; 162 } 163 164 // Child left in state where sibling members need subsequent adjustment. BecomeParent(T * child)165 void BecomeParent(T* child) { 166 CHECK(child != this); // Detect attempts at self-insertion. 167 if (child->m_pParent) 168 child->m_pParent->TreeNodeBase<T>::RemoveChild(child); 169 child->m_pParent = static_cast<T*>(this); 170 CHECK(!child->m_pNextSibling); 171 CHECK(!child->m_pPrevSibling); 172 } 173 }; 174 175 // Tree connected using C-style pointers. 176 template <typename T> 177 class TreeNode : public TreeNodeBase<T> { 178 public: 179 TreeNode() = default; 180 virtual ~TreeNode() = default; 181 182 private: 183 friend class TreeNodeBase<T>; 184 185 T* m_pParent = nullptr; // Raw, intra-tree pointer. 186 T* m_pFirstChild = nullptr; // Raw, intra-tree pointer. 187 T* m_pLastChild = nullptr; // Raw, intra-tree pointer. 188 T* m_pNextSibling = nullptr; // Raw, intra-tree pointer 189 T* m_pPrevSibling = nullptr; // Raw, intra-tree pointer 190 }; 191 192 } // namespace fxcrt 193 194 using fxcrt::TreeNode; 195 196 #endif // CORE_FXCRT_TREE_NODE_H_ 197