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
33// FIXME: I wish I didn't have to forward declare these, but I can't seem to avoid
34// it if I still want to have for_each_in_subtree_of_type<U> inline here.
35class Node;
36class LayoutNode;
37template<typename T>
38bool is(const Node&);
39template<typename T>
40bool is(const LayoutNode&);
41
42template<typename T>
43class TreeNode : public Weakable<T> {
44public:
45 void ref()
46 {
47 ASSERT(m_ref_count);
48 ++m_ref_count;
49 }
50
51 void unref()
52 {
53 ASSERT(m_ref_count);
54 if (!--m_ref_count) {
55 if (m_next_sibling)
56 m_next_sibling->m_previous_sibling = m_previous_sibling;
57 if (m_previous_sibling)
58 m_previous_sibling->m_next_sibling = m_next_sibling;
59 T* next_child;
60 for (auto* child = m_first_child; child; child = next_child) {
61 next_child = child->m_next_sibling;
62 child->m_parent = nullptr;
63 child->unref();
64 }
65 delete static_cast<T*>(this);
66 }
67 }
68 int ref_count() const { return m_ref_count; }
69
70 T* parent() { return m_parent; }
71 const T* parent() const { return m_parent; }
72
73 bool has_children() const { return m_first_child; }
74 T* next_sibling() { return m_next_sibling; }
75 T* previous_sibling() { return m_previous_sibling; }
76 T* first_child() { return m_first_child; }
77 T* last_child() { return m_last_child; }
78 const T* next_sibling() const { return m_next_sibling; }
79 const T* previous_sibling() const { return m_previous_sibling; }
80 const T* first_child() const { return m_first_child; }
81 const T* last_child() const { return m_last_child; }
82
83 int child_count() const
84 {
85 int count = 0;
86 for (auto* child = first_child(); child; child = child->next_sibling())
87 ++count;
88 return count;
89 }
90
91 T* child_at_index(int index)
92 {
93 int count = 0;
94 for (auto* child = first_child(); child; child = child->next_sibling()) {
95 if (count == index)
96 return child;
97 ++count;
98 }
99 return nullptr;
100 }
101
102 const T* child_at_index(int index) const
103 {
104 return const_cast<TreeNode*>(this)->child_at_index(index);
105 }
106
107 bool is_ancestor_of(const TreeNode&) const;
108
109 void prepend_child(NonnullRefPtr<T> node, bool call_inserted_into = true);
110 void append_child(NonnullRefPtr<T> node, bool call_inserted_into = true);
111 NonnullRefPtr<T> remove_child(NonnullRefPtr<T> node, bool call_removed_from = true);
112 void donate_all_children_to(T& node);
113
114 bool is_child_allowed(const T&) const { return true; }
115
116 T* next_in_pre_order()
117 {
118 if (first_child())
119 return first_child();
120 T* node;
121 if (!(node = next_sibling())) {
122 node = parent();
123 while (node && !node->next_sibling())
124 node = node->parent();
125 if (node)
126 node = node->next_sibling();
127 }
128 return node;
129 }
130
131 const T* next_in_pre_order() const
132 {
133 return const_cast<TreeNode*>(this)->next_in_pre_order();
134 }
135
136 template<typename Callback>
137 IterationDecision for_each_in_subtree(Callback callback) const
138 {
139 if (callback(static_cast<const T&>(*this)) == IterationDecision::Break)
140 return IterationDecision::Break;
141 for (auto* child = first_child(); child; child = child->next_sibling()) {
142 if (child->for_each_in_subtree(callback) == IterationDecision::Break)
143 return IterationDecision::Break;
144 }
145 return IterationDecision::Continue;
146 }
147
148 template<typename Callback>
149 IterationDecision for_each_in_subtree(Callback callback)
150 {
151 if (callback(static_cast<T&>(*this)) == IterationDecision::Break)
152 return IterationDecision::Break;
153 for (auto* child = first_child(); child; child = child->next_sibling()) {
154 if (child->for_each_in_subtree(callback) == IterationDecision::Break)
155 return IterationDecision::Break;
156 }
157 return IterationDecision::Continue;
158 }
159
160 template<typename U, typename Callback>
161 IterationDecision for_each_in_subtree_of_type(Callback callback)
162 {
163 if (is<U>(static_cast<const T&>(*this))) {
164 if (callback(static_cast<U&>(*this)) == IterationDecision::Break)
165 return IterationDecision::Break;
166 }
167 for (auto* child = first_child(); child; child = child->next_sibling()) {
168 if (child->template for_each_in_subtree_of_type<U>(callback) == IterationDecision::Break)
169 return IterationDecision::Break;
170 }
171 return IterationDecision::Continue;
172 }
173
174 template<typename U, typename Callback>
175 IterationDecision for_each_in_subtree_of_type(Callback callback) const
176 {
177 if (is<U>(static_cast<const T&>(*this))) {
178 if (callback(static_cast<const U&>(*this)) == IterationDecision::Break)
179 return IterationDecision::Break;
180 }
181 for (auto* child = first_child(); child; child = child->next_sibling()) {
182 if (child->template for_each_in_subtree_of_type<U>(callback) == IterationDecision::Break)
183 return IterationDecision::Break;
184 }
185 return IterationDecision::Continue;
186 }
187
188protected:
189 TreeNode() {}
190
191private:
192 int m_ref_count { 1 };
193 T* m_parent { nullptr };
194 T* m_first_child { nullptr };
195 T* m_last_child { nullptr };
196 T* m_next_sibling { nullptr };
197 T* m_previous_sibling { nullptr };
198};
199
200template<typename T>
201inline NonnullRefPtr<T> TreeNode<T>::remove_child(NonnullRefPtr<T> node, bool call_removed_from)
202{
203 ASSERT(node->m_parent == this);
204
205 if (m_first_child == node)
206 m_first_child = node->m_next_sibling;
207
208 if (m_last_child == node)
209 m_last_child = node->m_previous_sibling;
210
211 if (node->m_next_sibling)
212 node->m_next_sibling->m_previous_sibling = node->m_previous_sibling;
213
214 if (node->m_previous_sibling)
215 node->m_previous_sibling->m_next_sibling = node->m_next_sibling;
216
217 node->m_next_sibling = nullptr;
218 node->m_previous_sibling = nullptr;
219 node->m_parent = nullptr;
220
221 if (call_removed_from)
222 node->removed_from(static_cast<T&>(*this));
223
224 node->unref();
225
226 return node;
227}
228
229template<typename T>
230inline void TreeNode<T>::append_child(NonnullRefPtr<T> node, bool call_inserted_into)
231{
232 ASSERT(!node->m_parent);
233
234 if (!static_cast<T*>(this)->is_child_allowed(*node))
235 return;
236
237 if (m_last_child)
238 m_last_child->m_next_sibling = node.ptr();
239 node->m_previous_sibling = m_last_child;
240 node->m_parent = static_cast<T*>(this);
241 m_last_child = node.ptr();
242 if (!m_first_child)
243 m_first_child = m_last_child;
244 if (call_inserted_into)
245 node->inserted_into(static_cast<T&>(*this));
246 (void)node.leak_ref();
247}
248
249template<typename T>
250inline void TreeNode<T>::prepend_child(NonnullRefPtr<T> node, bool call_inserted_into)
251{
252 ASSERT(!node->m_parent);
253
254 if (!static_cast<T*>(this)->is_child_allowed(*node))
255 return;
256
257 if (m_first_child)
258 m_first_child->m_previous_sibling = node.ptr();
259 node->m_next_sibling = m_first_child;
260 node->m_parent = static_cast<T*>(this);
261 m_first_child = node.ptr();
262 if (!m_last_child)
263 m_last_child = m_first_child;
264 if (call_inserted_into)
265 node->inserted_into(static_cast<T&>(*this));
266 (void)node.leak_ref();
267}
268
269template<typename T>
270inline void TreeNode<T>::donate_all_children_to(T& node)
271{
272 for (T* child = m_first_child; child != nullptr;) {
273 T* next_child = child->m_next_sibling;
274
275 child->m_parent = nullptr;
276 child->m_next_sibling = nullptr;
277 child->m_previous_sibling = nullptr;
278
279 node.append_child(adopt(*child));
280 child = next_child;
281 }
282
283 m_first_child = nullptr;
284 m_last_child = nullptr;
285}
286
287template<typename T>
288inline bool TreeNode<T>::is_ancestor_of(const TreeNode<T>& other) const
289{
290 for (auto* ancestor = other.parent(); ancestor; ancestor = ancestor->parent()) {
291 if (ancestor == this)
292 return true;
293 }
294 return false;
295}