Revision control
Copy as Markdown
// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
#include "areaallocator_p.h"
#include <QtCore/qglobal.h>
#include <QtCore/qrect.h>
#include <QtCore/qpoint.h>
//
// This file is copied from qtdeclarative/src/quick/scenegraph/util/qsgareaallocator.cpp
//
QT_BEGIN_NAMESPACE
namespace Qt3DExtras {
enum SplitType
{
VerticalSplit,
HorizontalSplit
};
static const int maxMargin = 2;
struct AreaAllocatorNode
{
AreaAllocatorNode(AreaAllocatorNode *parent);
~AreaAllocatorNode();
inline bool isLeaf();
AreaAllocatorNode *parent;
AreaAllocatorNode *left;
AreaAllocatorNode *right;
int split; // only valid for inner nodes.
SplitType splitType;
bool isOccupied; // only valid for leaf nodes.
};
AreaAllocatorNode::AreaAllocatorNode(AreaAllocatorNode *parent)
: parent(parent)
, left(0)
, right(0)
, isOccupied(false)
{
}
AreaAllocatorNode::~AreaAllocatorNode()
{
delete left;
delete right;
}
bool AreaAllocatorNode::isLeaf()
{
Q_ASSERT((left != 0) == (right != 0));
return !left;
}
AreaAllocator::AreaAllocator(const QSize &size) : m_size(size)
{
m_root = new AreaAllocatorNode(0);
}
AreaAllocator::~AreaAllocator()
{
delete m_root;
}
QRect AreaAllocator::allocate(const QSize &size)
{
QPoint point;
bool result = allocateInNode(size, point, QRect(QPoint(0, 0), m_size), m_root);
return result ? QRect(point, size) : QRect();
}
bool AreaAllocator::deallocate(const QRect &rect)
{
return deallocateInNode(rect.topLeft(), m_root);
}
bool AreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect ¤tRect, AreaAllocatorNode *node)
{
if (size.width() > currentRect.width() || size.height() > currentRect.height())
return false;
if (node->isLeaf()) {
if (node->isOccupied)
return false;
if (size.width() + maxMargin >= currentRect.width() && size.height() + maxMargin >= currentRect.height()) {
//Snug fit, occupy entire rectangle.
node->isOccupied = true;
result = currentRect.topLeft();
return true;
}
// TODO: Reuse nodes.
// Split node.
node->left = new AreaAllocatorNode(node);
node->right = new AreaAllocatorNode(node);
QRect splitRect = currentRect;
if ((currentRect.width() - size.width()) * currentRect.height() < (currentRect.height() - size.height()) * currentRect.width()) {
node->splitType = HorizontalSplit;
node->split = currentRect.top() + size.height();
splitRect.setHeight(size.height());
} else {
node->splitType = VerticalSplit;
node->split = currentRect.left() + size.width();
splitRect.setWidth(size.width());
}
return allocateInNode(size, result, splitRect, node->left);
} else {
// TODO: avoid unnecessary recursion.
// has been split.
QRect leftRect = currentRect;
QRect rightRect = currentRect;
if (node->splitType == HorizontalSplit) {
leftRect.setHeight(node->split - leftRect.top());
rightRect.setTop(node->split);
} else {
leftRect.setWidth(node->split - leftRect.left());
rightRect.setLeft(node->split);
}
if (allocateInNode(size, result, leftRect, node->left))
return true;
if (allocateInNode(size, result, rightRect, node->right))
return true;
return false;
}
}
bool AreaAllocator::deallocateInNode(const QPoint &pos, AreaAllocatorNode *node)
{
while (!node->isLeaf()) {
// has been split.
int cmp = node->splitType == HorizontalSplit ? pos.y() : pos.x();
node = cmp < node->split ? node->left : node->right;
}
if (!node->isOccupied)
return false;
node->isOccupied = false;
mergeNodeWithNeighbors(node);
return true;
}
void AreaAllocator::mergeNodeWithNeighbors(AreaAllocatorNode *node)
{
bool done = false;
AreaAllocatorNode *parent = 0;
AreaAllocatorNode *current = 0;
AreaAllocatorNode *sibling;
while (!done) {
Q_ASSERT(node->isLeaf());
Q_ASSERT(!node->isOccupied);
if (node->parent == 0)
return; // No neighbors.
SplitType splitType = SplitType(node->parent->splitType);
done = true;
/* Special case. Might be faster than going through the general code path.
// Merge with sibling.
parent = node->parent;
sibling = (node == parent->left ? parent->right : parent->left);
if (sibling->isLeaf() && !sibling->isOccupied) {
Q_ASSERT(!sibling->right);
node = parent;
parent->isOccupied = false;
delete parent->left;
delete parent->right;
parent->left = parent->right = 0;
done = false;
continue;
}
*/
// Merge with left neighbor.
current = node;
parent = current->parent;
while (parent && current == parent->left && parent->splitType == splitType) {
current = parent;
parent = parent->parent;
}
if (parent && parent->splitType == splitType) {
Q_ASSERT(current == parent->right);
Q_ASSERT(parent->left);
AreaAllocatorNode *neighbor = parent->left;
while (neighbor->right && neighbor->splitType == splitType)
neighbor = neighbor->right;
if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
// Left neighbor can be merged.
parent->split = neighbor->parent->split;
parent = neighbor->parent;
sibling = neighbor == parent->left ? parent->right : parent->left;
AreaAllocatorNode **nodeRef = &m_root;
if (parent->parent) {
if (parent == parent->parent->left)
nodeRef = &parent->parent->left;
else
nodeRef = &parent->parent->right;
}
sibling->parent = parent->parent;
*nodeRef = sibling;
parent->left = parent->right = 0;
delete parent;
delete neighbor;
done = false;
}
}
// Merge with right neighbor.
current = node;
parent = current->parent;
while (parent && current == parent->right && parent->splitType == splitType) {
current = parent;
parent = parent->parent;
}
if (parent && parent->splitType == splitType) {
Q_ASSERT(current == parent->left);
Q_ASSERT(parent->right);
AreaAllocatorNode *neighbor = parent->right;
while (neighbor->left && neighbor->splitType == splitType)
neighbor = neighbor->left;
if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
// Right neighbor can be merged.
parent->split = neighbor->parent->split;
parent = neighbor->parent;
sibling = neighbor == parent->left ? parent->right : parent->left;
AreaAllocatorNode **nodeRef = &m_root;
if (parent->parent) {
if (parent == parent->parent->left)
nodeRef = &parent->parent->left;
else
nodeRef = &parent->parent->right;
}
sibling->parent = parent->parent;
*nodeRef = sibling;
parent->left = parent->right = 0;
delete parent;
delete neighbor;
done = false;
}
}
} // end while (!done)
}
} // namespace Qt3DExtras
QT_END_NAMESPACE