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
49QT_BEGIN_NAMESPACE
50
51namespace
52{
53 enum SplitType
54 {
55 VerticalSplit,
56 HorizontalSplit
57 };
58
59 static const int maxMargin = 2;
60}
61
62struct 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
76QSGAreaAllocatorNode::QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent)
77 : parent(parent)
78 , left(nullptr)
79 , right(nullptr)
80 , isOccupied(false)
81{
82}
83
84QSGAreaAllocatorNode::~QSGAreaAllocatorNode()
85{
86 delete left;
87 delete right;
88}
89
90bool QSGAreaAllocatorNode::isLeaf()
91{
92 Q_ASSERT((left != nullptr) == (right != nullptr));
93 return !left;
94}
95
96
97QSGAreaAllocator::QSGAreaAllocator(const QSize &size) : m_size(size)
98{
99 m_root = new QSGAreaAllocatorNode(nullptr);
100}
101
102QSGAreaAllocator::~QSGAreaAllocator()
103{
104 delete m_root;
105}
106
107QRect 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
114bool QSGAreaAllocator::deallocate(const QRect &rect)
115{
116 return deallocateInNode(pos: rect.topLeft(), node: m_root);
117}
118
119bool QSGAreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect &currentRect, 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
168bool 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
182void 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
291namespace {
292 struct AreaAllocatorTable
293 {
294 enum TableSize {
295 HeaderSize = 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
332QByteArray 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
373const 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
432QT_END_NAMESPACE
433

source code of qtdeclarative/src/quick/scenegraph/util/qsgareaallocator.cpp