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
14QT_BEGIN_NAMESPACE
15
16namespace Qt3DExtras {
17
18enum SplitType
19{
20 VerticalSplit,
21 HorizontalSplit
22};
23
24static const int maxMargin = 2;
25
26struct AreaAllocatorNode
27{
28 AreaAllocatorNode(AreaAllocatorNode *parent);
29 ~AreaAllocatorNode();
30 inline bool isLeaf();
31
32 AreaAllocatorNode *parent;
33 AreaAllocatorNode *left;
34 AreaAllocatorNode *right;
35 int split; // only valid for inner nodes.
36 SplitType splitType;
37 bool isOccupied; // only valid for leaf nodes.
38};
39
40AreaAllocatorNode::AreaAllocatorNode(AreaAllocatorNode *parent)
41 : parent(parent)
42 , left(0)
43 , right(0)
44 , isOccupied(false)
45{
46}
47
48AreaAllocatorNode::~AreaAllocatorNode()
49{
50 delete left;
51 delete right;
52}
53
54bool AreaAllocatorNode::isLeaf()
55{
56 Q_ASSERT((left != 0) == (right != 0));
57 return !left;
58}
59
60
61AreaAllocator::AreaAllocator(const QSize &size) : m_size(size)
62{
63 m_root = new AreaAllocatorNode(0);
64}
65
66AreaAllocator::~AreaAllocator()
67{
68 delete m_root;
69}
70
71QRect AreaAllocator::allocate(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
78bool AreaAllocator::deallocate(const QRect &rect)
79{
80 return deallocateInNode(pos: rect.topLeft(), node: m_root);
81}
82
83bool AreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect &currentRect, 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
132bool AreaAllocator::deallocateInNode(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
146void AreaAllocator::mergeNodeWithNeighbors(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
257QT_END_NAMESPACE
258

source code of qt3d/src/extras/text/areaallocator.cpp