← Back to branch summary

~ubuntu-branches/ubuntu/saucy/qtdeclarative-opensource-src/saucy

« back to all changes in this revision

Viewing changes to src/quick/scenegraph/util/qsgareaallocator.cpp

  • Committer: Package Import Robot
  • Author(s): Timo Jyrinki
  • Date: 2013-02-05 14:17:19 UTC
  • Revision ID: package-import@ubuntu.com-20130205141719-qqeyml8wslpyez52
Tags: upstream-5.0.1
Import upstream version 5.0.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/quick/scenegraph/util/qsgareaallocator.cpp
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
 
4
** Contact: http://www.qt-project.org/legal
 
5
**
 
6
** This file is part of the QtQml 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 Digia.  For licensing terms and
 
14
** conditions see http://qt.digia.com/licensing.  For further information
 
15
** use the contact form at http://qt.digia.com/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 2.1 as published by the Free Software
 
20
** Foundation and appearing in the file LICENSE.LGPL included in the
 
21
** packaging of this file.  Please review the following information to
 
22
** ensure the GNU Lesser General Public License version 2.1 requirements
 
23
** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
 
24
**
 
25
** In addition, as a special exception, Digia gives you certain additional
 
26
** rights.  These rights are described in the Digia Qt LGPL Exception
 
27
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
 
28
**
 
29
** GNU General Public License Usage
 
30
** Alternatively, this file may be used under the terms of the GNU
 
31
** General Public License version 3.0 as published by the Free Software
 
32
** Foundation and appearing in the file LICENSE.GPL included in the
 
33
** packaging of this file.  Please review the following information to
 
34
** ensure the GNU General Public License version 3.0 requirements will be
 
35
** met: http://www.gnu.org/copyleft/gpl.html.
 
36
**
 
37
**
 
38
** $QT_END_LICENSE$
 
39
**
 
40
****************************************************************************/
 
41
 
 
42
#include "qsgareaallocator_p.h"
 
43
 
 
44
#include <QtCore/qglobal.h>
 
45
#include <QtCore/qrect.h>
 
46
#include <QtCore/qpoint.h>
 
47
 
 
48
QT_BEGIN_NAMESPACE
 
49
 
 
50
namespace
 
51
{
 
52
    enum SplitType
 
53
    {
 
54
        VerticalSplit,
 
55
        HorizontalSplit
 
56
    };
 
57
 
 
58
    static const int maxMargin = 2;
 
59
}
 
60
 
 
61
struct QSGAreaAllocatorNode
 
62
{
 
63
    QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent);
 
64
    ~QSGAreaAllocatorNode();
 
65
    inline bool isLeaf();
 
66
 
 
67
    QSGAreaAllocatorNode *parent;
 
68
    QSGAreaAllocatorNode *left;
 
69
    QSGAreaAllocatorNode *right;
 
70
    int split; // only valid for inner nodes.
 
71
    SplitType splitType;
 
72
    bool isOccupied; // only valid for leaf nodes.
 
73
};
 
74
 
 
75
QSGAreaAllocatorNode::QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent)
 
76
    : parent(parent)
 
77
    , left(0)
 
78
    , right(0)
 
79
    , isOccupied(false)
 
80
{
 
81
}
 
82
 
 
83
QSGAreaAllocatorNode::~QSGAreaAllocatorNode()
 
84
{
 
85
    delete left;
 
86
    delete right;
 
87
}
 
88
 
 
89
bool QSGAreaAllocatorNode::isLeaf()
 
90
{
 
91
    Q_ASSERT((left != 0) == (right != 0));
 
92
    return !left;
 
93
}
 
94
 
 
95
 
 
96
QSGAreaAllocator::QSGAreaAllocator(const QSize &size) : m_size(size)
 
97
{
 
98
    m_root = new QSGAreaAllocatorNode(0);
 
99
}
 
100
 
 
101
QSGAreaAllocator::~QSGAreaAllocator()
 
102
{
 
103
    delete m_root;
 
104
}
 
105
 
 
106
QRect QSGAreaAllocator::allocate(const QSize &size)
 
107
{
 
108
    QPoint point;
 
109
    bool result = allocateInNode(size, point, QRect(QPoint(0, 0), m_size), m_root);
 
110
    return result ? QRect(point, size) : QRect();
 
111
}
 
112
 
 
113
bool QSGAreaAllocator::deallocate(const QRect &rect)
 
114
{
 
115
    return deallocateInNode(rect.topLeft(), m_root);
 
116
}
 
117
 
 
118
bool QSGAreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect &currentRect, QSGAreaAllocatorNode *node)
 
119
{
 
120
    if (size.width() > currentRect.width() || size.height() > currentRect.height())
 
121
        return false;
 
122
 
 
123
    if (node->isLeaf()) {
 
124
        if (node->isOccupied)
 
125
            return false;
 
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();
 
130
            return true;
 
131
        }
 
132
        // TODO: Reuse nodes.
 
133
        // Split node.
 
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());
 
141
        } else {
 
142
            node->splitType = VerticalSplit;
 
143
            node->split = currentRect.left() + size.width();
 
144
            splitRect.setWidth(size.width());
 
145
        }
 
146
        return allocateInNode(size, result, splitRect, node->left);
 
147
    } else {
 
148
        // TODO: avoid unnecessary recursion.
 
149
        //  has been split.
 
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);
 
155
        } else {
 
156
            leftRect.setWidth(node->split - leftRect.left());
 
157
            rightRect.setLeft(node->split);
 
158
        }
 
159
        if (allocateInNode(size, result, leftRect, node->left))
 
160
            return true;
 
161
        if (allocateInNode(size, result, rightRect, node->right))
 
162
            return true;
 
163
        return false;
 
164
    }
 
165
}
 
166
 
 
167
bool QSGAreaAllocator::deallocateInNode(const QPoint &pos, QSGAreaAllocatorNode *node)
 
168
{
 
169
    while (!node->isLeaf()) {
 
170
        //  has been split.
 
171
        int cmp = node->splitType == HorizontalSplit ? pos.y() : pos.x();
 
172
        node = cmp < node->split ? node->left : node->right;
 
173
    }
 
174
    if (!node->isOccupied)
 
175
        return false;
 
176
    node->isOccupied = false;
 
177
    mergeNodeWithNeighbors(node);
 
178
    return true;
 
179
}
 
180
 
 
181
void QSGAreaAllocator::mergeNodeWithNeighbors(QSGAreaAllocatorNode *node)
 
182
{
 
183
    bool done = false;
 
184
    QSGAreaAllocatorNode *parent = 0;
 
185
    QSGAreaAllocatorNode *current = 0;
 
186
    QSGAreaAllocatorNode *sibling;
 
187
    while (!done) {
 
188
        Q_ASSERT(node->isLeaf());
 
189
        Q_ASSERT(!node->isOccupied);
 
190
        if (node->parent == 0)
 
191
            return; // No neighbours.
 
192
 
 
193
        SplitType splitType = SplitType(node->parent->splitType);
 
194
        done = true;
 
195
 
 
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);
 
202
            node = parent;
 
203
            parent->isOccupied = false;
 
204
            delete parent->left;
 
205
            delete parent->right;
 
206
            parent->left = parent->right = 0;
 
207
            done = false;
 
208
            continue;
 
209
        }
 
210
        */
 
211
 
 
212
        // Merge with left neighbour.
 
213
        current = node;
 
214
        parent = current->parent;
 
215
        while (parent && current == parent->left && parent->splitType == splitType) {
 
216
            current = parent;
 
217
            parent = parent->parent;
 
218
        }
 
219
 
 
220
        if (parent && parent->splitType == splitType) {
 
221
            Q_ASSERT(current == parent->right);
 
222
            Q_ASSERT(parent->left);
 
223
 
 
224
            QSGAreaAllocatorNode *neighbor = parent->left;
 
225
            while (neighbor->right && neighbor->splitType == splitType)
 
226
                neighbor = neighbor->right;
 
227
 
 
228
            if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
 
229
                // Left neighbour can be merged.
 
230
                parent->split = neighbor->parent->split;
 
231
 
 
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;
 
238
                    else
 
239
                        nodeRef = &parent->parent->right;
 
240
                }
 
241
                sibling->parent = parent->parent;
 
242
                *nodeRef = sibling;
 
243
                parent->left = parent->right = 0;
 
244
                delete parent;
 
245
                delete neighbor;
 
246
                done = false;
 
247
            }
 
248
        }
 
249
 
 
250
        // Merge with right neighbour.
 
251
        current = node;
 
252
        parent = current->parent;
 
253
        while (parent && current == parent->right && parent->splitType == splitType) {
 
254
            current = parent;
 
255
            parent = parent->parent;
 
256
        }
 
257
 
 
258
        if (parent && parent->splitType == splitType) {
 
259
            Q_ASSERT(current == parent->left);
 
260
            Q_ASSERT(parent->right);
 
261
 
 
262
            QSGAreaAllocatorNode *neighbor = parent->right;
 
263
            while (neighbor->left && neighbor->splitType == splitType)
 
264
                neighbor = neighbor->left;
 
265
 
 
266
            if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
 
267
                // Right neighbour can be merged.
 
268
                parent->split = neighbor->parent->split;
 
269
 
 
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;
 
276
                    else
 
277
                        nodeRef = &parent->parent->right;
 
278
                }
 
279
                sibling->parent = parent->parent;
 
280
                *nodeRef = sibling;
 
281
                parent->left = parent->right = 0;
 
282
                delete parent;
 
283
                delete neighbor;
 
284
                done = false;
 
285
            }
 
286
        }
 
287
    } // end while(!done)
 
288
}
 
289
 
 
290
QT_END_NAMESPACE