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 "qsgareaallocator_p.h"
5
6#include <QtCore/qglobal.h>
7#include <QtCore/qrect.h>
8#include <QtCore/qpoint.h>
9#include <QtCore/qdatastream.h>
10#include <QtCore/qstack.h>
11#include <QtCore/qendian.h>
12#include <QtCore/qvarlengtharray.h>
13
14QT_BEGIN_NAMESPACE
15
16enum SplitType
17{
18 VerticalSplit,
19 HorizontalSplit
20};
21
22static const int maxMargin = 2;
23
24struct QSGAreaAllocatorNode
25{
26 QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent);
27 ~QSGAreaAllocatorNode();
28 inline bool isLeaf();
29
30 QSGAreaAllocatorNode *parent;
31 QSGAreaAllocatorNode *left;
32 QSGAreaAllocatorNode *right;
33 int split; // only valid for inner nodes.
34 SplitType splitType;
35 bool isOccupied; // only valid for leaf nodes.
36};
37
38QSGAreaAllocatorNode::QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent)
39 : parent(parent)
40 , left(nullptr)
41 , right(nullptr)
42 , isOccupied(false)
43{
44}
45
46QSGAreaAllocatorNode::~QSGAreaAllocatorNode()
47{
48 delete left;
49 delete right;
50}
51
52bool QSGAreaAllocatorNode::isLeaf()
53{
54 Q_ASSERT((left != nullptr) == (right != nullptr));
55 return !left;
56}
57
58
59QSGAreaAllocator::QSGAreaAllocator(const QSize &size) : m_size(size)
60{
61 m_root = new QSGAreaAllocatorNode(nullptr);
62}
63
64QSGAreaAllocator::~QSGAreaAllocator()
65{
66 delete m_root;
67}
68
69QRect QSGAreaAllocator::allocate(const QSize &size)
70{
71 QPoint point;
72 bool result = allocateInNode(size, result&: point, currentRect: QRect(QPoint(0, 0), m_size), node: m_root);
73 return result ? QRect(point, size) : QRect();
74}
75
76bool QSGAreaAllocator::deallocate(const QRect &rect)
77{
78 return deallocateInNode(pos: rect.topLeft(), node: m_root);
79}
80
81bool QSGAreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect &currentRect, QSGAreaAllocatorNode *node)
82{
83 if (size.width() > currentRect.width() || size.height() > currentRect.height())
84 return false;
85
86 if (node->isLeaf()) {
87 if (node->isOccupied)
88 return false;
89 if (size.width() + maxMargin >= currentRect.width() && size.height() + maxMargin >= currentRect.height()) {
90 //Snug fit, occupy entire rectangle.
91 node->isOccupied = true;
92 result = currentRect.topLeft();
93 return true;
94 }
95 // TODO: Reuse nodes.
96 // Split node.
97 node->left = new QSGAreaAllocatorNode(node);
98 node->right = new QSGAreaAllocatorNode(node);
99 QRect splitRect = currentRect;
100 if ((currentRect.width() - size.width()) * currentRect.height() < (currentRect.height() - size.height()) * currentRect.width()) {
101 node->splitType = HorizontalSplit;
102 node->split = currentRect.top() + size.height();
103 splitRect.setHeight(size.height());
104 } else {
105 node->splitType = VerticalSplit;
106 node->split = currentRect.left() + size.width();
107 splitRect.setWidth(size.width());
108 }
109 return allocateInNode(size, result, currentRect: splitRect, node: node->left);
110 } else {
111 // TODO: avoid unnecessary recursion.
112 // has been split.
113 QRect leftRect = currentRect;
114 QRect rightRect = currentRect;
115 if (node->splitType == HorizontalSplit) {
116 leftRect.setHeight(node->split - leftRect.top());
117 rightRect.setTop(node->split);
118 } else {
119 leftRect.setWidth(node->split - leftRect.left());
120 rightRect.setLeft(node->split);
121 }
122 if (allocateInNode(size, result, currentRect: leftRect, node: node->left))
123 return true;
124 if (allocateInNode(size, result, currentRect: rightRect, node: node->right))
125 return true;
126 return false;
127 }
128}
129
130bool QSGAreaAllocator::deallocateInNode(const QPoint &pos, QSGAreaAllocatorNode *node)
131{
132 while (!node->isLeaf()) {
133 // has been split.
134 int cmp = node->splitType == HorizontalSplit ? pos.y() : pos.x();
135 node = cmp < node->split ? node->left : node->right;
136 }
137 if (!node->isOccupied)
138 return false;
139 node->isOccupied = false;
140 mergeNodeWithNeighbors(node);
141 return true;
142}
143
144void QSGAreaAllocator::mergeNodeWithNeighbors(QSGAreaAllocatorNode *node)
145{
146 bool done = false;
147 QSGAreaAllocatorNode *parent = nullptr;
148 QSGAreaAllocatorNode *current = nullptr;
149 QSGAreaAllocatorNode *sibling;
150 while (!done) {
151 Q_ASSERT(node->isLeaf());
152 Q_ASSERT(!node->isOccupied);
153 if (node->parent == nullptr)
154 return; // No neighbours.
155
156 SplitType splitType = SplitType(node->parent->splitType);
157 done = true;
158
159 /* Special case. Might be faster than going through the general code path.
160 // Merge with sibling.
161 parent = node->parent;
162 sibling = (node == parent->left ? parent->right : parent->left);
163 if (sibling->isLeaf() && !sibling->isOccupied) {
164 Q_ASSERT(!sibling->right);
165 node = parent;
166 parent->isOccupied = false;
167 delete parent->left;
168 delete parent->right;
169 parent->left = parent->right = 0;
170 done = false;
171 continue;
172 }
173 */
174
175 // Merge with left neighbour.
176 current = node;
177 parent = current->parent;
178 while (parent && current == parent->left && parent->splitType == splitType) {
179 current = parent;
180 parent = parent->parent;
181 }
182
183 if (parent && parent->splitType == splitType) {
184 Q_ASSERT(current == parent->right);
185 Q_ASSERT(parent->left);
186
187 QSGAreaAllocatorNode *neighbor = parent->left;
188 while (neighbor->right && neighbor->splitType == splitType)
189 neighbor = neighbor->right;
190
191 if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
192 // Left neighbour can be merged.
193 parent->split = neighbor->parent->split;
194
195 parent = neighbor->parent;
196 sibling = neighbor == parent->left ? parent->right : parent->left;
197 QSGAreaAllocatorNode **nodeRef = &m_root;
198 if (parent->parent) {
199 if (parent == parent->parent->left)
200 nodeRef = &parent->parent->left;
201 else
202 nodeRef = &parent->parent->right;
203 }
204 sibling->parent = parent->parent;
205 *nodeRef = sibling;
206 parent->left = parent->right = nullptr;
207 delete parent;
208 delete neighbor;
209 done = false;
210 }
211 }
212
213 // Merge with right neighbour.
214 current = node;
215 parent = current->parent;
216 while (parent && current == parent->right && parent->splitType == splitType) {
217 current = parent;
218 parent = parent->parent;
219 }
220
221 if (parent && parent->splitType == splitType) {
222 Q_ASSERT(current == parent->left);
223 Q_ASSERT(parent->right);
224
225 QSGAreaAllocatorNode *neighbor = parent->right;
226 while (neighbor->left && neighbor->splitType == splitType)
227 neighbor = neighbor->left;
228
229 if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
230 // Right 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 } // end while(!done)
251}
252
253namespace {
254 struct AreaAllocatorTable
255 {
256 enum TableSize {
257 HeaderSize = 10,
258 NodeSize = 9
259 };
260
261 enum Offset {
262 // Header
263 majorVersion = 0,
264 minorVersion = 1,
265 width = 2,
266 height = 6,
267
268 // Node
269 split = 0,
270 splitType = 4,
271 flags = 8
272 };
273
274 enum Flags {
275 IsOccupied = 1,
276 HasLeft = 2,
277 HasRight = 4
278 };
279
280 template <typename T>
281 static inline T fetch(const char *data, Offset offset)
282 {
283 return qFromBigEndian<T>(data + int(offset));
284 }
285
286 template <typename T>
287 static inline void put(char *data, Offset offset, T value)
288 {
289 qToBigEndian(value, data + int(offset));
290 }
291 };
292}
293
294QByteArray QSGAreaAllocator::serialize()
295{
296 QVarLengthArray<QSGAreaAllocatorNode *> nodesToProcess;
297
298 QStack<QSGAreaAllocatorNode *> nodes;
299 nodes.push(t: m_root);
300 while (!nodes.isEmpty()) {
301 QSGAreaAllocatorNode *node = nodes.pop();
302
303 nodesToProcess.append(t: node);
304 if (node->left != nullptr)
305 nodes.push(t: node->left);
306 if (node->right != nullptr)
307 nodes.push(t: node->right);
308 }
309
310 QByteArray ret;
311 ret.resize(size: AreaAllocatorTable::HeaderSize + AreaAllocatorTable::NodeSize * nodesToProcess.size());
312
313 char *data = ret.data();
314 AreaAllocatorTable::put(data, offset: AreaAllocatorTable::majorVersion, value: quint8(5));
315 AreaAllocatorTable::put(data, offset: AreaAllocatorTable::minorVersion, value: quint8(12));
316 AreaAllocatorTable::put(data, offset: AreaAllocatorTable::width, value: quint32(m_size.width()));
317 AreaAllocatorTable::put(data, offset: AreaAllocatorTable::height, value: quint32(m_size.height()));
318
319 data += AreaAllocatorTable::HeaderSize;
320 for (QSGAreaAllocatorNode *node : nodesToProcess) {
321 AreaAllocatorTable::put(data, offset: AreaAllocatorTable::split, value: qint32(node->split));
322 AreaAllocatorTable::put(data, offset: AreaAllocatorTable::splitType, value: quint32(node->splitType));
323
324 quint8 flags =
325 (node->isOccupied ? AreaAllocatorTable::IsOccupied : 0)
326 | (node->left != nullptr ? AreaAllocatorTable::HasLeft : 0)
327 | (node->right != nullptr ? AreaAllocatorTable::HasRight : 0);
328 AreaAllocatorTable::put(data, offset: AreaAllocatorTable::flags, value: flags);
329 data += AreaAllocatorTable::NodeSize;
330 }
331
332 return ret;
333}
334
335const char *QSGAreaAllocator::deserialize(const char *data, int size)
336{
337 if (uint(size) < AreaAllocatorTable::HeaderSize) {
338 qWarning(msg: "QSGAreaAllocator::deserialize: Data not long enough to fit header");
339 return nullptr;
340 }
341
342 const char *end = data + size;
343
344 quint8 majorVersion = AreaAllocatorTable::fetch<quint8>(data, offset: AreaAllocatorTable::majorVersion);
345 quint8 minorVersion = AreaAllocatorTable::fetch<quint8>(data, offset: AreaAllocatorTable::minorVersion);
346 if (majorVersion != 5 || minorVersion != 12) {
347 qWarning(msg: "Unrecognized version %d.%d of QSGAreaAllocator",
348 majorVersion,
349 minorVersion);
350 return nullptr;
351 }
352
353 m_size = QSize(AreaAllocatorTable::fetch<quint32>(data, offset: AreaAllocatorTable::width),
354 AreaAllocatorTable::fetch<quint32>(data, offset: AreaAllocatorTable::height));
355
356 Q_ASSERT(m_root != nullptr);
357 Q_ASSERT(m_root->left == nullptr);
358 Q_ASSERT(m_root->right == nullptr);
359
360 QStack<QSGAreaAllocatorNode *> nodes;
361 nodes.push(t: m_root);
362
363 data += AreaAllocatorTable::HeaderSize;
364 while (!nodes.isEmpty()) {
365 if (data + AreaAllocatorTable::NodeSize > end) {
366 qWarning(msg: "QSGAreaAllocator::deseriable: Data not long enough for nodes");
367 return nullptr;
368 }
369
370 QSGAreaAllocatorNode *node = nodes.pop();
371
372 node->split = AreaAllocatorTable::fetch<qint32>(data, offset: AreaAllocatorTable::split);
373 node->splitType = SplitType(AreaAllocatorTable::fetch<quint32>(data, offset: AreaAllocatorTable::splitType));
374
375 quint8 flags = AreaAllocatorTable::fetch<quint8>(data, offset: AreaAllocatorTable::flags);
376 node->isOccupied = flags & AreaAllocatorTable::IsOccupied;
377
378 if (flags & AreaAllocatorTable::HasLeft) {
379 node->left = new QSGAreaAllocatorNode(node);
380 nodes.push(t: node->left);
381 }
382
383 if (flags & AreaAllocatorTable::HasRight) {
384 node->right = new QSGAreaAllocatorNode(node);
385 nodes.push(t: node->right);
386 }
387
388 data += AreaAllocatorTable::NodeSize;
389 }
390
391 return data;
392}
393
394QT_END_NAMESPACE
395

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