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