src/quick/scenegraph/util/qsgareaallocator.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtDeclarative module of the Qt Toolkit.
   7 **
   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.
  16 **
  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.
  20 **
  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.
  28 **
  29 ** Other Usage
  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.
  32 **
  33 **
  34 **
  35 **
  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