1 | // Copyright (C) 2016 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | |
4 | #include "areaallocator_p.h" |
5 | |
6 | #include <QtCore/qglobal.h> |
7 | #include <QtCore/qrect.h> |
8 | #include <QtCore/qpoint.h> |
9 | |
10 | // |
11 | // This file is copied from qtdeclarative/src/quick/scenegraph/util/qsgareaallocator.cpp |
12 | // |
13 | |
14 | QT_BEGIN_NAMESPACE |
15 | |
16 | namespace Qt3DExtras { |
17 | |
18 | enum |
19 | { |
20 | , |
21 | |
22 | }; |
23 | |
24 | static const int = 2; |
25 | |
26 | struct |
27 | { |
28 | AreaAllocatorNode(AreaAllocatorNode *parent); |
29 | ~AreaAllocatorNode(); |
30 | inline bool isLeaf(); |
31 | |
32 | AreaAllocatorNode *; |
33 | AreaAllocatorNode *; |
34 | AreaAllocatorNode *; |
35 | int ; // only valid for inner nodes. |
36 | SplitType ; |
37 | bool ; // only valid for leaf nodes. |
38 | }; |
39 | |
40 | AreaAllocatorNode::(AreaAllocatorNode *parent) |
41 | : parent(parent) |
42 | , left(0) |
43 | , right(0) |
44 | , isOccupied(false) |
45 | { |
46 | } |
47 | |
48 | AreaAllocatorNode::() |
49 | { |
50 | delete left; |
51 | delete right; |
52 | } |
53 | |
54 | bool AreaAllocatorNode::() |
55 | { |
56 | Q_ASSERT((left != 0) == (right != 0)); |
57 | return !left; |
58 | } |
59 | |
60 | |
61 | AreaAllocator::(const QSize &size) : m_size(size) |
62 | { |
63 | m_root = new AreaAllocatorNode(0); |
64 | } |
65 | |
66 | AreaAllocator::() |
67 | { |
68 | delete m_root; |
69 | } |
70 | |
71 | QRect AreaAllocator::(const QSize &size) |
72 | { |
73 | QPoint point; |
74 | bool result = allocateInNode(size, result&: point, currentRect: QRect(QPoint(0, 0), m_size), node: m_root); |
75 | return result ? QRect(point, size) : QRect(); |
76 | } |
77 | |
78 | bool AreaAllocator::(const QRect &rect) |
79 | { |
80 | return deallocateInNode(pos: rect.topLeft(), node: m_root); |
81 | } |
82 | |
83 | bool AreaAllocator::(const QSize &size, QPoint &result, const QRect ¤tRect, AreaAllocatorNode *node) |
84 | { |
85 | if (size.width() > currentRect.width() || size.height() > currentRect.height()) |
86 | return false; |
87 | |
88 | if (node->isLeaf()) { |
89 | if (node->isOccupied) |
90 | return false; |
91 | if (size.width() + maxMargin >= currentRect.width() && size.height() + maxMargin >= currentRect.height()) { |
92 | //Snug fit, occupy entire rectangle. |
93 | node->isOccupied = true; |
94 | result = currentRect.topLeft(); |
95 | return true; |
96 | } |
97 | // TODO: Reuse nodes. |
98 | // Split node. |
99 | node->left = new AreaAllocatorNode(node); |
100 | node->right = new AreaAllocatorNode(node); |
101 | QRect splitRect = currentRect; |
102 | if ((currentRect.width() - size.width()) * currentRect.height() < (currentRect.height() - size.height()) * currentRect.width()) { |
103 | node->splitType = HorizontalSplit; |
104 | node->split = currentRect.top() + size.height(); |
105 | splitRect.setHeight(size.height()); |
106 | } else { |
107 | node->splitType = VerticalSplit; |
108 | node->split = currentRect.left() + size.width(); |
109 | splitRect.setWidth(size.width()); |
110 | } |
111 | return allocateInNode(size, result, currentRect: splitRect, node: node->left); |
112 | } else { |
113 | // TODO: avoid unnecessary recursion. |
114 | // has been split. |
115 | QRect leftRect = currentRect; |
116 | QRect rightRect = currentRect; |
117 | if (node->splitType == HorizontalSplit) { |
118 | leftRect.setHeight(node->split - leftRect.top()); |
119 | rightRect.setTop(node->split); |
120 | } else { |
121 | leftRect.setWidth(node->split - leftRect.left()); |
122 | rightRect.setLeft(node->split); |
123 | } |
124 | if (allocateInNode(size, result, currentRect: leftRect, node: node->left)) |
125 | return true; |
126 | if (allocateInNode(size, result, currentRect: rightRect, node: node->right)) |
127 | return true; |
128 | return false; |
129 | } |
130 | } |
131 | |
132 | bool AreaAllocator::(const QPoint &pos, AreaAllocatorNode *node) |
133 | { |
134 | while (!node->isLeaf()) { |
135 | // has been split. |
136 | int cmp = node->splitType == HorizontalSplit ? pos.y() : pos.x(); |
137 | node = cmp < node->split ? node->left : node->right; |
138 | } |
139 | if (!node->isOccupied) |
140 | return false; |
141 | node->isOccupied = false; |
142 | mergeNodeWithNeighbors(node); |
143 | return true; |
144 | } |
145 | |
146 | void AreaAllocator::(AreaAllocatorNode *node) |
147 | { |
148 | bool done = false; |
149 | AreaAllocatorNode *parent = 0; |
150 | AreaAllocatorNode *current = 0; |
151 | AreaAllocatorNode *sibling; |
152 | while (!done) { |
153 | Q_ASSERT(node->isLeaf()); |
154 | Q_ASSERT(!node->isOccupied); |
155 | if (node->parent == 0) |
156 | return; // No neighbors. |
157 | |
158 | SplitType splitType = SplitType(node->parent->splitType); |
159 | done = true; |
160 | |
161 | /* Special case. Might be faster than going through the general code path. |
162 | // Merge with sibling. |
163 | parent = node->parent; |
164 | sibling = (node == parent->left ? parent->right : parent->left); |
165 | if (sibling->isLeaf() && !sibling->isOccupied) { |
166 | Q_ASSERT(!sibling->right); |
167 | node = parent; |
168 | parent->isOccupied = false; |
169 | delete parent->left; |
170 | delete parent->right; |
171 | parent->left = parent->right = 0; |
172 | done = false; |
173 | continue; |
174 | } |
175 | */ |
176 | |
177 | // Merge with left neighbor. |
178 | current = node; |
179 | parent = current->parent; |
180 | while (parent && current == parent->left && parent->splitType == splitType) { |
181 | current = parent; |
182 | parent = parent->parent; |
183 | } |
184 | |
185 | if (parent && parent->splitType == splitType) { |
186 | Q_ASSERT(current == parent->right); |
187 | Q_ASSERT(parent->left); |
188 | |
189 | AreaAllocatorNode *neighbor = parent->left; |
190 | while (neighbor->right && neighbor->splitType == splitType) |
191 | neighbor = neighbor->right; |
192 | |
193 | if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) { |
194 | // Left neighbor can be merged. |
195 | parent->split = neighbor->parent->split; |
196 | |
197 | parent = neighbor->parent; |
198 | sibling = neighbor == parent->left ? parent->right : parent->left; |
199 | AreaAllocatorNode **nodeRef = &m_root; |
200 | if (parent->parent) { |
201 | if (parent == parent->parent->left) |
202 | nodeRef = &parent->parent->left; |
203 | else |
204 | nodeRef = &parent->parent->right; |
205 | } |
206 | sibling->parent = parent->parent; |
207 | *nodeRef = sibling; |
208 | parent->left = parent->right = 0; |
209 | delete parent; |
210 | delete neighbor; |
211 | done = false; |
212 | } |
213 | } |
214 | |
215 | // Merge with right neighbor. |
216 | current = node; |
217 | parent = current->parent; |
218 | while (parent && current == parent->right && parent->splitType == splitType) { |
219 | current = parent; |
220 | parent = parent->parent; |
221 | } |
222 | |
223 | if (parent && parent->splitType == splitType) { |
224 | Q_ASSERT(current == parent->left); |
225 | Q_ASSERT(parent->right); |
226 | |
227 | AreaAllocatorNode *neighbor = parent->right; |
228 | while (neighbor->left && neighbor->splitType == splitType) |
229 | neighbor = neighbor->left; |
230 | |
231 | if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) { |
232 | // Right neighbor can be merged. |
233 | parent->split = neighbor->parent->split; |
234 | |
235 | parent = neighbor->parent; |
236 | sibling = neighbor == parent->left ? parent->right : parent->left; |
237 | AreaAllocatorNode **nodeRef = &m_root; |
238 | if (parent->parent) { |
239 | if (parent == parent->parent->left) |
240 | nodeRef = &parent->parent->left; |
241 | else |
242 | nodeRef = &parent->parent->right; |
243 | } |
244 | sibling->parent = parent->parent; |
245 | *nodeRef = sibling; |
246 | parent->left = parent->right = 0; |
247 | delete parent; |
248 | delete neighbor; |
249 | done = false; |
250 | } |
251 | } |
252 | } // end while (!done) |
253 | } |
254 | |
255 | } // namespace Qt3DExtras |
256 | |
257 | QT_END_NAMESPACE |
258 | |