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