1 /* 2 * Copyright (C) 2013 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #ifndef TreeNode_h 32 #define TreeNode_h 33 34 #include "wtf/Assertions.h" 35 36 namespace WTF { 37 38 // 39 // TreeNode is generic, ContainerNode-like linked tree data structure. 40 // There are a few notable difference between TreeNode and Node: 41 // 42 // * Each TreeNode node is NOT ref counted. The user have to retain its lifetime somehow. 43 // FIXME: lifetime management could be parameterized so that ref counted implementations can be used. 44 // * It ASSERT()s invalid input. The callers have to ensure that given parameter is sound. 45 // * There is no branch-leaf difference. Every node can be a parent of other node. 46 // 47 // FIXME: oilpan: Trace tree node edges to ensure we don't have dangling pointers. 48 // As it is used in HTMLImport it is safe since they all die together. 49 template <class T> 50 class TreeNode { 51 public: 52 typedef T NodeType; 53 54 TreeNode() 55 : m_next(0) 56 , m_previous(0) 57 , m_parent(0) 58 , m_firstChild(0) 59 , m_lastChild(0) 60 { 61 } 62 63 NodeType* next() const { return m_next; } 64 NodeType* previous() const { return m_previous; } 65 NodeType* parent() const { return m_parent; } 66 NodeType* firstChild() const { return m_firstChild; } 67 NodeType* lastChild() const { return m_lastChild; } 68 NodeType* here() const { return static_cast<NodeType*>(const_cast<TreeNode*>(this)); } 69 70 bool orphan() const { return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; } 71 bool hasChildren() const { return m_firstChild; } 72 73 void insertBefore(NodeType* newChild, NodeType* refChild) 74 { 75 ASSERT(!newChild->parent()); 76 ASSERT(!newChild->next()); 77 ASSERT(!newChild->previous()); 78 79 ASSERT(!refChild || this == refChild->parent()); 80 81 if (!refChild) { 82 appendChild(newChild); 83 return; 84 } 85 86 NodeType* newPrevious = refChild->previous(); 87 newChild->m_parent = here(); 88 newChild->m_next = refChild; 89 newChild->m_previous = newPrevious; 90 refChild->m_previous = newChild; 91 if (newPrevious) 92 newPrevious->m_next = newChild; 93 else 94 m_firstChild = newChild; 95 } 96 97 void appendChild(NodeType* child) 98 { 99 ASSERT(!child->parent()); 100 ASSERT(!child->next()); 101 ASSERT(!child->previous()); 102 103 child->m_parent = here(); 104 105 if (!m_lastChild) { 106 ASSERT(!m_firstChild); 107 m_lastChild = m_firstChild = child; 108 return; 109 } 110 111 ASSERT(!m_lastChild->m_next); 112 NodeType* oldLast = m_lastChild; 113 m_lastChild = child; 114 115 child->m_previous = oldLast; 116 oldLast->m_next = child; 117 } 118 119 NodeType* removeChild(NodeType* child) 120 { 121 ASSERT(child->parent() == this); 122 123 if (m_firstChild == child) 124 m_firstChild = child->next(); 125 if (m_lastChild == child) 126 m_lastChild = child->previous(); 127 128 NodeType* oldNext = child->next(); 129 NodeType* oldPrevious = child->previous(); 130 child->m_parent = child->m_next = child->m_previous = 0; 131 132 if (oldNext) 133 oldNext->m_previous = oldPrevious; 134 if (oldPrevious) 135 oldPrevious->m_next = oldNext; 136 137 return child; 138 } 139 140 void takeChildrenFrom(NodeType* oldParent) 141 { 142 ASSERT(oldParent != this); 143 while (oldParent->hasChildren()) { 144 NodeType* child = oldParent->firstChild(); 145 oldParent->removeChild(child); 146 this->appendChild(child); 147 } 148 } 149 150 private: 151 NodeType* m_next; 152 NodeType* m_previous; 153 NodeType* m_parent; 154 NodeType* m_firstChild; 155 NodeType* m_lastChild; 156 }; 157 158 template<class T> 159 inline typename TreeNode<T>::NodeType* traverseNext(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0) 160 { 161 if (typename TreeNode<T>::NodeType* next = current->firstChild()) 162 return next; 163 if (current == stayWithin) 164 return 0; 165 if (typename TreeNode<T>::NodeType* next = current->next()) 166 return next; 167 for (typename TreeNode<T>::NodeType* parent = current->parent(); parent; parent = parent->parent()) { 168 if (parent == stayWithin) 169 return 0; 170 if (typename TreeNode<T>::NodeType* next = parent->next()) 171 return next; 172 } 173 174 return 0; 175 } 176 177 template<class T> 178 inline typename TreeNode<T>::NodeType* traverseFirstPostOrder(const TreeNode<T>* current) 179 { 180 typename TreeNode<T>::NodeType* first = current->here(); 181 while (first->firstChild()) 182 first = first->firstChild(); 183 return first; 184 } 185 186 template<class T> 187 inline typename TreeNode<T>::NodeType* traverseNextPostOrder(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0) 188 { 189 if (current == stayWithin) 190 return 0; 191 192 typename TreeNode<T>::NodeType* next = current->next(); 193 if (!next) 194 return current->parent(); 195 while (next->firstChild()) 196 next = next->firstChild(); 197 return next; 198 } 199 200 } 201 202 using WTF::TreeNode; 203 using WTF::traverseNext; 204 using WTF::traverseNextPostOrder; 205 206 #endif 207