jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#pragma once
28
29#include <AK/Assertions.h>
30#include <AK/NonnullRefPtr.h>
31#include <AK/Weakable.h>
32
33namespace Web {
34
35// FIXME: I wish I didn't have to forward declare these, but I can't seem to avoid
36// it if I still want to have for_each_in_subtree_of_type<U> inline here.
37class Node;
38class LayoutNode;
39template<typename T>
40bool is(const Node&);
41template<typename T>
42bool is(const LayoutNode&);
43
44template<typename T>
45class TreeNode : public Weakable<T> {
46public:
47 void ref()
48 {
49 ASSERT(m_ref_count);
50 ++m_ref_count;
51 }
52
53 void unref()
54 {
55 ASSERT(m_ref_count);
56 if (!--m_ref_count) {
57 if (m_next_sibling)
58 m_next_sibling->m_previous_sibling = m_previous_sibling;
59 if (m_previous_sibling)
60 m_previous_sibling->m_next_sibling = m_next_sibling;
61 T* next_child;
62 for (auto* child = m_first_child; child; child = next_child) {
63 next_child = child->m_next_sibling;
64 child->m_parent = nullptr;
65 child->unref();
66 }
67 delete static_cast<T*>(this);
68 }
69 }
70 int ref_count() const { return m_ref_count; }
71
72 T* parent() { return m_parent; }
73 const T* parent() const { return m_parent; }
74
75 bool has_children() const { return m_first_child; }
76 T* next_sibling() { return m_next_sibling; }
77 T* previous_sibling() { return m_previous_sibling; }
78 T* first_child() { return m_first_child; }
79 T* last_child() { return m_last_child; }
80 const T* next_sibling() const { return m_next_sibling; }
81 const T* previous_sibling() const { return m_previous_sibling; }
82 const T* first_child() const { return m_first_child; }
83 const T* last_child() const { return m_last_child; }
84
85 int child_count() const
86 {
87 int count = 0;
88 for (auto* child = first_child(); child; child = child->next_sibling())
89 ++count;
90 return count;
91 }
92
93 T* child_at_index(int index)
94 {
95 int count = 0;
96 for (auto* child = first_child(); child; child = child->next_sibling()) {
97 if (count == index)
98 return child;
99 ++count;
100 }
101 return nullptr;
102 }
103
104 const T* child_at_index(int index) const
105 {
106 return const_cast<TreeNode*>(this)->child_at_index(index);
107 }
108
109 bool is_ancestor_of(const TreeNode&) const;
110
111 void prepend_child(NonnullRefPtr<T> node);
112 void append_child(NonnullRefPtr<T> node);
113 NonnullRefPtr<T> remove_child(NonnullRefPtr<T> node);
114 void donate_all_children_to(T& node);
115
116 bool is_child_allowed(const T&) const { return true; }
117
118 T* next_in_pre_order()
119 {
120 if (first_child())
121 return first_child();
122 T* node;
123 if (!(node = next_sibling())) {
124 node = parent();
125 while (node && !node->next_sibling())
126 node = node->parent();
127 if (node)
128 node = node->next_sibling();
129 }
130 return node;
131 }
132
133 const T* next_in_pre_order() const
134 {
135 return const_cast<TreeNode*>(this)->next_in_pre_order();
136 }
137
138 template<typename Callback>
139 IterationDecision for_each_in_subtree(Callback callback) const
140 {
141 if (callback(static_cast<const T&>(*this)) == IterationDecision::Break)
142 return IterationDecision::Break;
143 for (auto* child = first_child(); child; child = child->next_sibling()) {
144 if (child->for_each_in_subtree(callback) == IterationDecision::Break)
145 return IterationDecision::Break;
146 }
147 return IterationDecision::Continue;
148 }
149
150 template<typename Callback>
151 IterationDecision for_each_in_subtree(Callback callback)
152 {
153 if (callback(static_cast<T&>(*this)) == IterationDecision::Break)
154 return IterationDecision::Break;
155 for (auto* child = first_child(); child; child = child->next_sibling()) {
156 if (child->for_each_in_subtree(callback) == IterationDecision::Break)
157 return IterationDecision::Break;
158 }
159 return IterationDecision::Continue;
160 }
161
162 template<typename U, typename Callback>
163 IterationDecision for_each_in_subtree_of_type(Callback callback)
164 {
165 if (is<U>(static_cast<const T&>(*this))) {
166 if (callback(static_cast<U&>(*this)) == IterationDecision::Break)
167 return IterationDecision::Break;
168 }
169 for (auto* child = first_child(); child; child = child->next_sibling()) {
170 if (child->template for_each_in_subtree_of_type<U>(callback) == IterationDecision::Break)
171 return IterationDecision::Break;
172 }
173 return IterationDecision::Continue;
174 }
175
176 template<typename U, typename Callback>
177 IterationDecision for_each_in_subtree_of_type(Callback callback) const
178 {
179 if (is<U>(static_cast<const T&>(*this))) {
180 if (callback(static_cast<const U&>(*this)) == IterationDecision::Break)
181 return IterationDecision::Break;
182 }
183 for (auto* child = first_child(); child; child = child->next_sibling()) {
184 if (child->template for_each_in_subtree_of_type<U>(callback) == IterationDecision::Break)
185 return IterationDecision::Break;
186 }
187 return IterationDecision::Continue;
188 }
189
190protected:
191 TreeNode() {}
192
193private:
194 int m_ref_count { 1 };
195 T* m_parent { nullptr };
196 T* m_first_child { nullptr };
197 T* m_last_child { nullptr };
198 T* m_next_sibling { nullptr };
199 T* m_previous_sibling { nullptr };
200};
201
202template<typename T>
203inline NonnullRefPtr<T> TreeNode<T>::remove_child(NonnullRefPtr<T> node)
204{
205 ASSERT(node->m_parent == this);
206
207 if (m_first_child == node)
208 m_first_child = node->m_next_sibling;
209
210 if (m_last_child == node)
211 m_last_child = node->m_previous_sibling;
212
213 if (node->m_next_sibling)
214 node->m_next_sibling->m_previous_sibling = node->m_previous_sibling;
215
216 if (node->m_previous_sibling)
217 node->m_previous_sibling->m_next_sibling = node->m_next_sibling;
218
219 node->m_next_sibling = nullptr;
220 node->m_previous_sibling = nullptr;
221 node->m_parent = nullptr;
222
223 node->removed_from(static_cast<T&>(*this));
224
225 node->unref();
226
227 static_cast<T*>(this)->children_changed();
228
229 return node;
230}
231
232template<typename T>
233inline void TreeNode<T>::append_child(NonnullRefPtr<T> node)
234{
235 ASSERT(!node->m_parent);
236
237 if (!static_cast<T*>(this)->is_child_allowed(*node))
238 return;
239
240 if (m_last_child)
241 m_last_child->m_next_sibling = node.ptr();
242 node->m_previous_sibling = m_last_child;
243 node->m_parent = static_cast<T*>(this);
244 m_last_child = node.ptr();
245 if (!m_first_child)
246 m_first_child = m_last_child;
247 node->inserted_into(static_cast<T&>(*this));
248 (void)node.leak_ref();
249
250 static_cast<T*>(this)->children_changed();
251}
252
253template<typename T>
254inline void TreeNode<T>::prepend_child(NonnullRefPtr<T> node)
255{
256 ASSERT(!node->m_parent);
257
258 if (!static_cast<T*>(this)->is_child_allowed(*node))
259 return;
260
261 if (m_first_child)
262 m_first_child->m_previous_sibling = node.ptr();
263 node->m_next_sibling = m_first_child;
264 node->m_parent = static_cast<T*>(this);
265 m_first_child = node.ptr();
266 if (!m_last_child)
267 m_last_child = m_first_child;
268 node->inserted_into(static_cast<T&>(*this));
269 (void)node.leak_ref();
270
271 static_cast<T*>(this)->children_changed();
272}
273
274template<typename T>
275inline void TreeNode<T>::donate_all_children_to(T& node)
276{
277 for (T* child = m_first_child; child != nullptr;) {
278 T* next_child = child->m_next_sibling;
279
280 child->m_parent = nullptr;
281 child->m_next_sibling = nullptr;
282 child->m_previous_sibling = nullptr;
283
284 node.append_child(adopt(*child));
285 child = next_child;
286 }
287
288 m_first_child = nullptr;
289 m_last_child = nullptr;
290}
291
292template<typename T>
293inline bool TreeNode<T>::is_ancestor_of(const TreeNode<T>& other) const
294{
295 for (auto* ancestor = other.parent(); ancestor; ancestor = ancestor->parent()) {
296 if (ancestor == this)
297 return true;
298 }
299 return false;
300}
301
302}