1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
6 ** This file is part of the QtQml module of the Qt Toolkit.
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** GNU Lesser General Public License Usage
10 ** This file may be used under the terms of the GNU Lesser General Public
11 ** License version 2.1 as published by the Free Software Foundation and
12 ** appearing in the file LICENSE.LGPL included in the packaging of this
13 ** file. Please review the following information to ensure the GNU Lesser
14 ** General Public License version 2.1 requirements will be met:
15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
17 ** In addition, as a special exception, Nokia gives you certain additional
18 ** rights. These rights are described in the Nokia Qt LGPL Exception
19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
21 ** GNU General Public License Usage
22 ** Alternatively, this file may be used under the terms of the GNU General
23 ** Public License version 3.0 as published by the Free Software Foundation
24 ** and appearing in the file LICENSE.GPL included in the packaging of this
25 ** file. Please review the following information to ensure the GNU General
26 ** Public License version 3.0 requirements will be met:
27 ** http://www.gnu.org/copyleft/gpl.html.
30 ** Alternatively, this file may be used in accordance with the terms and
31 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
42 #include "qsgareaallocator_p.h"
44 #include <QtCore/qglobal.h>
45 #include <QtCore/qrect.h>
46 #include <QtCore/qpoint.h>
58 static const int maxMargin = 2;
61 struct QSGAreaAllocatorNode
63 QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent);
64 ~QSGAreaAllocatorNode();
67 QSGAreaAllocatorNode *parent;
68 QSGAreaAllocatorNode *left;
69 QSGAreaAllocatorNode *right;
70 int split; // only valid for inner nodes.
72 bool isOccupied; // only valid for leaf nodes.
75 QSGAreaAllocatorNode::QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent)
83 QSGAreaAllocatorNode::~QSGAreaAllocatorNode()
89 bool QSGAreaAllocatorNode::isLeaf()
91 Q_ASSERT((left != 0) == (right != 0));
96 QSGAreaAllocator::QSGAreaAllocator(const QSize &size) : m_size(size)
98 m_root = new QSGAreaAllocatorNode(0);
101 QSGAreaAllocator::~QSGAreaAllocator()
106 QRect QSGAreaAllocator::allocate(const QSize &size)
109 bool result = allocateInNode(size, point, QRect(QPoint(0, 0), m_size), m_root);
110 return result ? QRect(point, size) : QRect();
113 bool QSGAreaAllocator::deallocate(const QRect &rect)
115 return deallocateInNode(rect.topLeft(), m_root);
118 bool QSGAreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect ¤tRect, QSGAreaAllocatorNode *node)
120 if (size.width() > currentRect.width() || size.height() > currentRect.height())
123 if (node->isLeaf()) {
124 if (node->isOccupied)
126 if (size.width() + maxMargin >= currentRect.width() && size.height() + maxMargin >= currentRect.height()) {
127 //Snug fit, occupy entire rectangle.
128 node->isOccupied = true;
129 result = currentRect.topLeft();
132 // TODO: Reuse nodes.
134 node->left = new QSGAreaAllocatorNode(node);
135 node->right = new QSGAreaAllocatorNode(node);
136 QRect splitRect = currentRect;
137 if ((currentRect.width() - size.width()) * currentRect.height() < (currentRect.height() - size.height()) * currentRect.width()) {
138 node->splitType = HorizontalSplit;
139 node->split = currentRect.top() + size.height();
140 splitRect.setHeight(size.height());
142 node->splitType = VerticalSplit;
143 node->split = currentRect.left() + size.width();
144 splitRect.setWidth(size.width());
146 return allocateInNode(size, result, splitRect, node->left);
148 // TODO: avoid unnecessary recursion.
150 QRect leftRect = currentRect;
151 QRect rightRect = currentRect;
152 if (node->splitType == HorizontalSplit) {
153 leftRect.setHeight(node->split - leftRect.top());
154 rightRect.setTop(node->split);
156 leftRect.setWidth(node->split - leftRect.left());
157 rightRect.setLeft(node->split);
159 if (allocateInNode(size, result, leftRect, node->left))
161 if (allocateInNode(size, result, rightRect, node->right))
167 bool QSGAreaAllocator::deallocateInNode(const QPoint &pos, QSGAreaAllocatorNode *node)
169 while (!node->isLeaf()) {
171 int cmp = node->splitType == HorizontalSplit ? pos.y() : pos.x();
172 node = cmp < node->split ? node->left : node->right;
174 if (!node->isOccupied)
176 node->isOccupied = false;
177 mergeNodeWithNeighbors(node);
181 void QSGAreaAllocator::mergeNodeWithNeighbors(QSGAreaAllocatorNode *node)
184 QSGAreaAllocatorNode *parent = 0;
185 QSGAreaAllocatorNode *current = 0;
186 QSGAreaAllocatorNode *sibling;
188 Q_ASSERT(node->isLeaf());
189 Q_ASSERT(!node->isOccupied);
190 if (node->parent == 0)
191 return; // No neighbours.
193 SplitType splitType = SplitType(node->parent->splitType);
196 /* Special case. Might be faster than going through the general code path.
197 // Merge with sibling.
198 parent = node->parent;
199 sibling = (node == parent->left ? parent->right : parent->left);
200 if (sibling->isLeaf() && !sibling->isOccupied) {
201 Q_ASSERT(!sibling->right);
203 parent->isOccupied = false;
205 delete parent->right;
206 parent->left = parent->right = 0;
212 // Merge with left neighbour.
214 parent = current->parent;
215 while (parent && current == parent->left && parent->splitType == splitType) {
217 parent = parent->parent;
220 if (parent && parent->splitType == splitType) {
221 Q_ASSERT(current == parent->right);
222 Q_ASSERT(parent->left);
224 QSGAreaAllocatorNode *neighbor = parent->left;
225 while (neighbor->right && neighbor->splitType == splitType)
226 neighbor = neighbor->right;
228 if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
229 // Left neighbour can be merged.
230 parent->split = neighbor->parent->split;
232 parent = neighbor->parent;
233 sibling = neighbor == parent->left ? parent->right : parent->left;
234 QSGAreaAllocatorNode **nodeRef = &m_root;
235 if (parent->parent) {
236 if (parent == parent->parent->left)
237 nodeRef = &parent->parent->left;
239 nodeRef = &parent->parent->right;
241 sibling->parent = parent->parent;
243 parent->left = parent->right = 0;
250 // Merge with right neighbour.
252 parent = current->parent;
253 while (parent && current == parent->right && parent->splitType == splitType) {
255 parent = parent->parent;
258 if (parent && parent->splitType == splitType) {
259 Q_ASSERT(current == parent->left);
260 Q_ASSERT(parent->right);
262 QSGAreaAllocatorNode *neighbor = parent->right;
263 while (neighbor->left && neighbor->splitType == splitType)
264 neighbor = neighbor->left;
266 if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
267 // Right neighbour can be merged.
268 parent->split = neighbor->parent->split;
270 parent = neighbor->parent;
271 sibling = neighbor == parent->left ? parent->right : parent->left;
272 QSGAreaAllocatorNode **nodeRef = &m_root;
273 if (parent->parent) {
274 if (parent == parent->parent->left)
275 nodeRef = &parent->parent->left;
277 nodeRef = &parent->parent->right;
279 sibling->parent = parent->parent;
281 parent->left = parent->right = 0;
287 } // end while(!done)