1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtQuick module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or (at your option) the GNU General |
28 | ** Public license version 3 or any later version approved by the KDE Free |
29 | ** Qt Foundation. The licenses are as published by the Free Software |
30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
31 | ** included in the packaging of this file. Please review the following |
32 | ** information to ensure the GNU General Public License requirements will |
33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
35 | ** |
36 | ** $QT_END_LICENSE$ |
37 | ** |
38 | ****************************************************************************/ |
39 | |
40 | #include "qsgareaallocator_p.h" |
41 | |
42 | #include <QtCore/qglobal.h> |
43 | #include <QtCore/qrect.h> |
44 | #include <QtCore/qpoint.h> |
45 | #include <QtCore/qdatastream.h> |
46 | #include <QtCore/qstack.h> |
47 | #include <QtCore/qendian.h> |
48 | |
49 | QT_BEGIN_NAMESPACE |
50 | |
51 | namespace |
52 | { |
53 | enum SplitType |
54 | { |
55 | VerticalSplit, |
56 | HorizontalSplit |
57 | }; |
58 | |
59 | static const int maxMargin = 2; |
60 | } |
61 | |
62 | struct QSGAreaAllocatorNode |
63 | { |
64 | QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent); |
65 | ~QSGAreaAllocatorNode(); |
66 | inline bool isLeaf(); |
67 | |
68 | QSGAreaAllocatorNode *parent; |
69 | QSGAreaAllocatorNode *left; |
70 | QSGAreaAllocatorNode *right; |
71 | int split; // only valid for inner nodes. |
72 | SplitType splitType; |
73 | bool isOccupied; // only valid for leaf nodes. |
74 | }; |
75 | |
76 | QSGAreaAllocatorNode::QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent) |
77 | : parent(parent) |
78 | , left(nullptr) |
79 | , right(nullptr) |
80 | , isOccupied(false) |
81 | { |
82 | } |
83 | |
84 | QSGAreaAllocatorNode::~QSGAreaAllocatorNode() |
85 | { |
86 | delete left; |
87 | delete right; |
88 | } |
89 | |
90 | bool QSGAreaAllocatorNode::isLeaf() |
91 | { |
92 | Q_ASSERT((left != nullptr) == (right != nullptr)); |
93 | return !left; |
94 | } |
95 | |
96 | |
97 | QSGAreaAllocator::QSGAreaAllocator(const QSize &size) : m_size(size) |
98 | { |
99 | m_root = new QSGAreaAllocatorNode(nullptr); |
100 | } |
101 | |
102 | QSGAreaAllocator::~QSGAreaAllocator() |
103 | { |
104 | delete m_root; |
105 | } |
106 | |
107 | QRect QSGAreaAllocator::allocate(const QSize &size) |
108 | { |
109 | QPoint point; |
110 | bool result = allocateInNode(size, result&: point, currentRect: QRect(QPoint(0, 0), m_size), node: m_root); |
111 | return result ? QRect(point, size) : QRect(); |
112 | } |
113 | |
114 | bool QSGAreaAllocator::deallocate(const QRect &rect) |
115 | { |
116 | return deallocateInNode(pos: rect.topLeft(), node: m_root); |
117 | } |
118 | |
119 | bool QSGAreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect ¤tRect, QSGAreaAllocatorNode *node) |
120 | { |
121 | if (size.width() > currentRect.width() || size.height() > currentRect.height()) |
122 | return false; |
123 | |
124 | if (node->isLeaf()) { |
125 | if (node->isOccupied) |
126 | return false; |
127 | if (size.width() + maxMargin >= currentRect.width() && size.height() + maxMargin >= currentRect.height()) { |
128 | //Snug fit, occupy entire rectangle. |
129 | node->isOccupied = true; |
130 | result = currentRect.topLeft(); |
131 | return true; |
132 | } |
133 | // TODO: Reuse nodes. |
134 | // Split node. |
135 | node->left = new QSGAreaAllocatorNode(node); |
136 | node->right = new QSGAreaAllocatorNode(node); |
137 | QRect splitRect = currentRect; |
138 | if ((currentRect.width() - size.width()) * currentRect.height() < (currentRect.height() - size.height()) * currentRect.width()) { |
139 | node->splitType = HorizontalSplit; |
140 | node->split = currentRect.top() + size.height(); |
141 | splitRect.setHeight(size.height()); |
142 | } else { |
143 | node->splitType = VerticalSplit; |
144 | node->split = currentRect.left() + size.width(); |
145 | splitRect.setWidth(size.width()); |
146 | } |
147 | return allocateInNode(size, result, currentRect: splitRect, node: node->left); |
148 | } else { |
149 | // TODO: avoid unnecessary recursion. |
150 | // has been split. |
151 | QRect leftRect = currentRect; |
152 | QRect rightRect = currentRect; |
153 | if (node->splitType == HorizontalSplit) { |
154 | leftRect.setHeight(node->split - leftRect.top()); |
155 | rightRect.setTop(node->split); |
156 | } else { |
157 | leftRect.setWidth(node->split - leftRect.left()); |
158 | rightRect.setLeft(node->split); |
159 | } |
160 | if (allocateInNode(size, result, currentRect: leftRect, node: node->left)) |
161 | return true; |
162 | if (allocateInNode(size, result, currentRect: rightRect, node: node->right)) |
163 | return true; |
164 | return false; |
165 | } |
166 | } |
167 | |
168 | bool QSGAreaAllocator::deallocateInNode(const QPoint &pos, QSGAreaAllocatorNode *node) |
169 | { |
170 | while (!node->isLeaf()) { |
171 | // has been split. |
172 | int cmp = node->splitType == HorizontalSplit ? pos.y() : pos.x(); |
173 | node = cmp < node->split ? node->left : node->right; |
174 | } |
175 | if (!node->isOccupied) |
176 | return false; |
177 | node->isOccupied = false; |
178 | mergeNodeWithNeighbors(node); |
179 | return true; |
180 | } |
181 | |
182 | void QSGAreaAllocator::mergeNodeWithNeighbors(QSGAreaAllocatorNode *node) |
183 | { |
184 | bool done = false; |
185 | QSGAreaAllocatorNode *parent = nullptr; |
186 | QSGAreaAllocatorNode *current = nullptr; |
187 | QSGAreaAllocatorNode *sibling; |
188 | while (!done) { |
189 | Q_ASSERT(node->isLeaf()); |
190 | Q_ASSERT(!node->isOccupied); |
191 | if (node->parent == nullptr) |
192 | return; // No neighbours. |
193 | |
194 | SplitType splitType = SplitType(node->parent->splitType); |
195 | done = true; |
196 | |
197 | /* Special case. Might be faster than going through the general code path. |
198 | // Merge with sibling. |
199 | parent = node->parent; |
200 | sibling = (node == parent->left ? parent->right : parent->left); |
201 | if (sibling->isLeaf() && !sibling->isOccupied) { |
202 | Q_ASSERT(!sibling->right); |
203 | node = parent; |
204 | parent->isOccupied = false; |
205 | delete parent->left; |
206 | delete parent->right; |
207 | parent->left = parent->right = 0; |
208 | done = false; |
209 | continue; |
210 | } |
211 | */ |
212 | |
213 | // Merge with left neighbour. |
214 | current = node; |
215 | parent = current->parent; |
216 | while (parent && current == parent->left && parent->splitType == splitType) { |
217 | current = parent; |
218 | parent = parent->parent; |
219 | } |
220 | |
221 | if (parent && parent->splitType == splitType) { |
222 | Q_ASSERT(current == parent->right); |
223 | Q_ASSERT(parent->left); |
224 | |
225 | QSGAreaAllocatorNode *neighbor = parent->left; |
226 | while (neighbor->right && neighbor->splitType == splitType) |
227 | neighbor = neighbor->right; |
228 | |
229 | if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) { |
230 | // Left neighbour can be merged. |
231 | parent->split = neighbor->parent->split; |
232 | |
233 | parent = neighbor->parent; |
234 | sibling = neighbor == parent->left ? parent->right : parent->left; |
235 | QSGAreaAllocatorNode **nodeRef = &m_root; |
236 | if (parent->parent) { |
237 | if (parent == parent->parent->left) |
238 | nodeRef = &parent->parent->left; |
239 | else |
240 | nodeRef = &parent->parent->right; |
241 | } |
242 | sibling->parent = parent->parent; |
243 | *nodeRef = sibling; |
244 | parent->left = parent->right = nullptr; |
245 | delete parent; |
246 | delete neighbor; |
247 | done = false; |
248 | } |
249 | } |
250 | |
251 | // Merge with right neighbour. |
252 | current = node; |
253 | parent = current->parent; |
254 | while (parent && current == parent->right && parent->splitType == splitType) { |
255 | current = parent; |
256 | parent = parent->parent; |
257 | } |
258 | |
259 | if (parent && parent->splitType == splitType) { |
260 | Q_ASSERT(current == parent->left); |
261 | Q_ASSERT(parent->right); |
262 | |
263 | QSGAreaAllocatorNode *neighbor = parent->right; |
264 | while (neighbor->left && neighbor->splitType == splitType) |
265 | neighbor = neighbor->left; |
266 | |
267 | if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) { |
268 | // Right neighbour can be merged. |
269 | parent->split = neighbor->parent->split; |
270 | |
271 | parent = neighbor->parent; |
272 | sibling = neighbor == parent->left ? parent->right : parent->left; |
273 | QSGAreaAllocatorNode **nodeRef = &m_root; |
274 | if (parent->parent) { |
275 | if (parent == parent->parent->left) |
276 | nodeRef = &parent->parent->left; |
277 | else |
278 | nodeRef = &parent->parent->right; |
279 | } |
280 | sibling->parent = parent->parent; |
281 | *nodeRef = sibling; |
282 | parent->left = parent->right = nullptr; |
283 | delete parent; |
284 | delete neighbor; |
285 | done = false; |
286 | } |
287 | } |
288 | } // end while(!done) |
289 | } |
290 | |
291 | namespace { |
292 | struct AreaAllocatorTable |
293 | { |
294 | enum TableSize { |
295 | = 10, |
296 | NodeSize = 9 |
297 | }; |
298 | |
299 | enum Offset { |
300 | // Header |
301 | majorVersion = 0, |
302 | minorVersion = 1, |
303 | width = 2, |
304 | height = 6, |
305 | |
306 | // Node |
307 | split = 0, |
308 | splitType = 4, |
309 | flags = 8 |
310 | }; |
311 | |
312 | enum Flags { |
313 | IsOccupied = 1, |
314 | HasLeft = 2, |
315 | HasRight = 4 |
316 | }; |
317 | |
318 | template <typename T> |
319 | static inline T fetch(const char *data, Offset offset) |
320 | { |
321 | return qFromBigEndian<T>(data + int(offset)); |
322 | } |
323 | |
324 | template <typename T> |
325 | static inline void put(char *data, Offset offset, T value) |
326 | { |
327 | qToBigEndian(value, data + int(offset)); |
328 | } |
329 | }; |
330 | } |
331 | |
332 | QByteArray QSGAreaAllocator::serialize() |
333 | { |
334 | QVarLengthArray<QSGAreaAllocatorNode *> nodesToProcess; |
335 | |
336 | QStack<QSGAreaAllocatorNode *> nodes; |
337 | nodes.push(t: m_root); |
338 | while (!nodes.isEmpty()) { |
339 | QSGAreaAllocatorNode *node = nodes.pop(); |
340 | |
341 | nodesToProcess.append(t: node); |
342 | if (node->left != nullptr) |
343 | nodes.push(t: node->left); |
344 | if (node->right != nullptr) |
345 | nodes.push(t: node->right); |
346 | } |
347 | |
348 | QByteArray ret; |
349 | ret.resize(size: AreaAllocatorTable::HeaderSize + AreaAllocatorTable::NodeSize * nodesToProcess.size()); |
350 | |
351 | char *data = ret.data(); |
352 | AreaAllocatorTable::put(data, offset: AreaAllocatorTable::majorVersion, value: quint8(5)); |
353 | AreaAllocatorTable::put(data, offset: AreaAllocatorTable::minorVersion, value: quint8(12)); |
354 | AreaAllocatorTable::put(data, offset: AreaAllocatorTable::width, value: quint32(m_size.width())); |
355 | AreaAllocatorTable::put(data, offset: AreaAllocatorTable::height, value: quint32(m_size.height())); |
356 | |
357 | data += AreaAllocatorTable::HeaderSize; |
358 | for (QSGAreaAllocatorNode *node : nodesToProcess) { |
359 | AreaAllocatorTable::put(data, offset: AreaAllocatorTable::split, value: qint32(node->split)); |
360 | AreaAllocatorTable::put(data, offset: AreaAllocatorTable::splitType, value: quint32(node->splitType)); |
361 | |
362 | quint8 flags = |
363 | (node->isOccupied ? AreaAllocatorTable::IsOccupied : 0) |
364 | | (node->left != nullptr ? AreaAllocatorTable::HasLeft : 0) |
365 | | (node->right != nullptr ? AreaAllocatorTable::HasRight : 0); |
366 | AreaAllocatorTable::put(data, offset: AreaAllocatorTable::flags, value: flags); |
367 | data += AreaAllocatorTable::NodeSize; |
368 | } |
369 | |
370 | return ret; |
371 | } |
372 | |
373 | const char *QSGAreaAllocator::deserialize(const char *data, int size) |
374 | { |
375 | if (uint(size) < AreaAllocatorTable::HeaderSize) { |
376 | qWarning(msg: "QSGAreaAllocator::deserialize: Data not long enough to fit header" ); |
377 | return nullptr; |
378 | } |
379 | |
380 | const char *end = data + size; |
381 | |
382 | quint8 majorVersion = AreaAllocatorTable::fetch<quint8>(data, offset: AreaAllocatorTable::majorVersion); |
383 | quint8 minorVersion = AreaAllocatorTable::fetch<quint8>(data, offset: AreaAllocatorTable::minorVersion); |
384 | if (majorVersion != 5 || minorVersion != 12) { |
385 | qWarning(msg: "Unrecognized version %d.%d of QSGAreaAllocator" , |
386 | majorVersion, |
387 | minorVersion); |
388 | return nullptr; |
389 | } |
390 | |
391 | m_size = QSize(AreaAllocatorTable::fetch<quint32>(data, offset: AreaAllocatorTable::width), |
392 | AreaAllocatorTable::fetch<quint32>(data, offset: AreaAllocatorTable::height)); |
393 | |
394 | Q_ASSERT(m_root != nullptr); |
395 | Q_ASSERT(m_root->left == nullptr); |
396 | Q_ASSERT(m_root->right == nullptr); |
397 | |
398 | QStack<QSGAreaAllocatorNode *> nodes; |
399 | nodes.push(t: m_root); |
400 | |
401 | data += AreaAllocatorTable::HeaderSize; |
402 | while (!nodes.isEmpty()) { |
403 | if (data + AreaAllocatorTable::NodeSize > end) { |
404 | qWarning(msg: "QSGAreaAllocator::deseriable: Data not long enough for nodes" ); |
405 | return nullptr; |
406 | } |
407 | |
408 | QSGAreaAllocatorNode *node = nodes.pop(); |
409 | |
410 | node->split = AreaAllocatorTable::fetch<qint32>(data, offset: AreaAllocatorTable::split); |
411 | node->splitType = SplitType(AreaAllocatorTable::fetch<quint32>(data, offset: AreaAllocatorTable::splitType)); |
412 | |
413 | quint8 flags = AreaAllocatorTable::fetch<quint8>(data, offset: AreaAllocatorTable::flags); |
414 | node->isOccupied = flags & AreaAllocatorTable::IsOccupied; |
415 | |
416 | if (flags & AreaAllocatorTable::HasLeft) { |
417 | node->left = new QSGAreaAllocatorNode(node); |
418 | nodes.push(t: node->left); |
419 | } |
420 | |
421 | if (flags & AreaAllocatorTable::HasRight) { |
422 | node->right = new QSGAreaAllocatorNode(node); |
423 | nodes.push(t: node->right); |
424 | } |
425 | |
426 | data += AreaAllocatorTable::NodeSize; |
427 | } |
428 | |
429 | return data; |
430 | } |
431 | |
432 | QT_END_NAMESPACE |
433 | |