OLD | NEW |
1 /* | 1 // Copyright 2017 The Chromium Authors. All rights reserved. |
2 * Copyright (C) 2013 Google Inc. All rights reserved. | 2 // Use of this source code is governed by a BSD-style license that can be |
3 * | 3 // found in the LICENSE file. |
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 | 4 |
31 #ifndef TreeNode_h | 5 #include "platform/wtf/TreeNode.h" |
32 #define TreeNode_h | |
33 | 6 |
34 #include "wtf/Assertions.h" | 7 // The contents of this header was moved to platform/wtf as part of |
35 | 8 // WTF migration project. See the following post for details: |
36 namespace WTF { | 9 // https://groups.google.com/a/chromium.org/d/msg/blink-dev/tLdAZCTlcAA/bYXVT8gY
CAAJ |
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 | |
43 // lifetime somehow. | |
44 // FIXME: lifetime management could be parameterized so that ref counted | |
45 // implementations can be used. | |
46 // * It checks invalid input. The callers have to ensure that given | |
47 // parameter is sound. | |
48 // * There is no branch-leaf difference. Every node can be a parent of other | |
49 // node. | |
50 // | |
51 // FIXME: oilpan: Trace tree node edges to ensure we don't have dangling | |
52 // pointers. | |
53 // As it is used in HTMLImport it is safe since they all die together. | |
54 template <class T> | |
55 class TreeNode { | |
56 public: | |
57 typedef T NodeType; | |
58 | |
59 TreeNode() | |
60 : m_next(0), | |
61 m_previous(0), | |
62 m_parent(0), | |
63 m_firstChild(0), | |
64 m_lastChild(0) {} | |
65 | |
66 NodeType* next() const { return m_next; } | |
67 NodeType* previous() const { return m_previous; } | |
68 NodeType* parent() const { return m_parent; } | |
69 NodeType* firstChild() const { return m_firstChild; } | |
70 NodeType* lastChild() const { return m_lastChild; } | |
71 NodeType* here() const { | |
72 return static_cast<NodeType*>(const_cast<TreeNode*>(this)); | |
73 } | |
74 | |
75 bool orphan() const { | |
76 return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; | |
77 } | |
78 bool hasChildren() const { return m_firstChild; } | |
79 | |
80 void insertBefore(NodeType* newChild, NodeType* refChild) { | |
81 DCHECK(!newChild->parent()); | |
82 DCHECK(!newChild->next()); | |
83 DCHECK(!newChild->previous()); | |
84 | |
85 DCHECK(!refChild || this == refChild->parent()); | |
86 | |
87 if (!refChild) { | |
88 appendChild(newChild); | |
89 return; | |
90 } | |
91 | |
92 NodeType* newPrevious = refChild->previous(); | |
93 newChild->m_parent = here(); | |
94 newChild->m_next = refChild; | |
95 newChild->m_previous = newPrevious; | |
96 refChild->m_previous = newChild; | |
97 if (newPrevious) | |
98 newPrevious->m_next = newChild; | |
99 else | |
100 m_firstChild = newChild; | |
101 } | |
102 | |
103 void appendChild(NodeType* child) { | |
104 DCHECK(!child->parent()); | |
105 DCHECK(!child->next()); | |
106 DCHECK(!child->previous()); | |
107 | |
108 child->m_parent = here(); | |
109 | |
110 if (!m_lastChild) { | |
111 DCHECK(!m_firstChild); | |
112 m_lastChild = m_firstChild = child; | |
113 return; | |
114 } | |
115 | |
116 DCHECK(!m_lastChild->m_next); | |
117 NodeType* oldLast = m_lastChild; | |
118 m_lastChild = child; | |
119 | |
120 child->m_previous = oldLast; | |
121 oldLast->m_next = child; | |
122 } | |
123 | |
124 NodeType* removeChild(NodeType* child) { | |
125 DCHECK_EQ(child->parent(), this); | |
126 | |
127 if (m_firstChild == child) | |
128 m_firstChild = child->next(); | |
129 if (m_lastChild == child) | |
130 m_lastChild = child->previous(); | |
131 | |
132 NodeType* oldNext = child->next(); | |
133 NodeType* oldPrevious = child->previous(); | |
134 child->m_parent = child->m_next = child->m_previous = 0; | |
135 | |
136 if (oldNext) | |
137 oldNext->m_previous = oldPrevious; | |
138 if (oldPrevious) | |
139 oldPrevious->m_next = oldNext; | |
140 | |
141 return child; | |
142 } | |
143 | |
144 void takeChildrenFrom(NodeType* oldParent) { | |
145 DCHECK_NE(oldParent, this); | |
146 while (oldParent->hasChildren()) { | |
147 NodeType* child = oldParent->firstChild(); | |
148 oldParent->removeChild(child); | |
149 this->appendChild(child); | |
150 } | |
151 } | |
152 | |
153 private: | |
154 NodeType* m_next; | |
155 NodeType* m_previous; | |
156 NodeType* m_parent; | |
157 NodeType* m_firstChild; | |
158 NodeType* m_lastChild; | |
159 }; | |
160 | |
161 template <class T> | |
162 inline typename TreeNode<T>::NodeType* traverseNext( | |
163 const TreeNode<T>* current, | |
164 const TreeNode<T>* stayWithin = 0) { | |
165 if (typename TreeNode<T>::NodeType* next = current->firstChild()) | |
166 return next; | |
167 if (current == stayWithin) | |
168 return 0; | |
169 if (typename TreeNode<T>::NodeType* next = current->next()) | |
170 return next; | |
171 for (typename TreeNode<T>::NodeType* parent = current->parent(); parent; | |
172 parent = parent->parent()) { | |
173 if (parent == stayWithin) | |
174 return 0; | |
175 if (typename TreeNode<T>::NodeType* next = parent->next()) | |
176 return next; | |
177 } | |
178 | |
179 return 0; | |
180 } | |
181 | |
182 template <class T> | |
183 inline typename TreeNode<T>::NodeType* traverseFirstPostOrder( | |
184 const TreeNode<T>* current) { | |
185 typename TreeNode<T>::NodeType* first = current->here(); | |
186 while (first->firstChild()) | |
187 first = first->firstChild(); | |
188 return first; | |
189 } | |
190 | |
191 template <class T> | |
192 inline typename TreeNode<T>::NodeType* traverseNextPostOrder( | |
193 const TreeNode<T>* current, | |
194 const TreeNode<T>* stayWithin = 0) { | |
195 if (current == stayWithin) | |
196 return 0; | |
197 | |
198 typename TreeNode<T>::NodeType* next = current->next(); | |
199 if (!next) | |
200 return current->parent(); | |
201 while (next->firstChild()) | |
202 next = next->firstChild(); | |
203 return next; | |
204 } | |
205 | |
206 } // namespace WTF | |
207 | |
208 using WTF::TreeNode; | |
209 using WTF::traverseNext; | |
210 using WTF::traverseNextPostOrder; | |
211 | |
212 #endif | |
OLD | NEW |