Revision control
++ // 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 "qsgareaallocator_p.h"
++
++ #include <QtCore/qglobal.h>
++ #include <QtCore/qrect.h>
++ #include <QtCore/qpoint.h>
++ #include <QtCore/qdatastream.h>
++ #include <QtCore/qstack.h>
++ #include <QtCore/qendian.h>
++ #include <QtCore/qvarlengtharray.h>
++
++ QT_BEGIN_NAMESPACE
++
++ enum SplitType
++ {
++ VerticalSplit,
++ HorizontalSplit
++ };
++
++ static const int maxMargin = 2;
++
++ struct QSGAreaAllocatorNode
++ {
++ QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent);
++ ~QSGAreaAllocatorNode();
++ inline bool isLeaf();
++
++ QSGAreaAllocatorNode *parent;
++ QSGAreaAllocatorNode *left;
++ QSGAreaAllocatorNode *right;
++ int split; // only valid for inner nodes.
++ SplitType splitType;
++ bool isOccupied; // only valid for leaf nodes.
++ };
++
++ QSGAreaAllocatorNode::QSGAreaAllocatorNode(QSGAreaAllocatorNode *parent)
++ : parent(parent)
++ , left(nullptr)
++ , right(nullptr)
++ , isOccupied(false)
++ {
++ }
++
++ QSGAreaAllocatorNode::~QSGAreaAllocatorNode()
++ {
++ delete left;
++ delete right;
++ }
++
++ bool QSGAreaAllocatorNode::isLeaf()
++ {
++ Q_ASSERT((left != nullptr) == (right != nullptr));
++ return !left;
++ }
++
++
++ // If sliceHeight is set, the area is treated as a vertical stack of slices of
++ // that height, and no allocation will cross the boundary between two slices.
++ QSGAreaAllocator::QSGAreaAllocator(const QSize &size, int sliceHeight)
++ : m_size(size)
++ , m_sliceHeight(sliceHeight)
++ {
++ m_root = new QSGAreaAllocatorNode(nullptr);
++ }
++
++ QSGAreaAllocator::~QSGAreaAllocator()
++ {
++ delete m_root;
++ }
++
++ QRect QSGAreaAllocator::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 QSGAreaAllocator::deallocate(const QRect &rect)
++ {
++ return deallocateInNode(rect.topLeft(), m_root);
++ }
++
++ bool QSGAreaAllocator::allocateInNode(const QSize &size, QPoint &result, const QRect ¤tRect, QSGAreaAllocatorNode *node)
++ {
++ if (size.width() > currentRect.width() || size.height() > currentRect.height())
++ return false;
++
++ if (node->isLeaf()) {
++ if (node->isOccupied)
++ return false;
++ if (m_sliceHeight > 0) {
++ // Does this leaf contain the slice boundary? In that case, we pre-split it so
++ // that we never get an allocation that crosses two slices.
++ const int boundary = (currentRect.top() / m_sliceHeight + 1) * m_sliceHeight;
++ if (boundary <= currentRect.bottom()) {
++ node->left = new QSGAreaAllocatorNode(node);
++ node->right = new QSGAreaAllocatorNode(node);
++ node->splitType = HorizontalSplit;
++ node->split = boundary;
++
++ // Re-call function with same arguments now that node is no longer leaf to
++ // trigger the search.
++ return allocateInNode(size, result, currentRect, node);
++ }
++ }
++ 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 QSGAreaAllocatorNode(node);
++ node->right = new QSGAreaAllocatorNode(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 QSGAreaAllocator::deallocateInNode(const QPoint &pos, QSGAreaAllocatorNode *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 QSGAreaAllocator::mergeNodeWithNeighbors(QSGAreaAllocatorNode *node)
++ {
++ bool done = false;
++ QSGAreaAllocatorNode *parent = nullptr;
++ QSGAreaAllocatorNode *current = nullptr;
++ QSGAreaAllocatorNode *sibling;
++ while (!done) {
++ Q_ASSERT(node->isLeaf());
++ Q_ASSERT(!node->isOccupied);
++ if (node->parent == nullptr)
++ return; // No neighbours.
++
++ 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 neighbour.
++ 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);
++
++ QSGAreaAllocatorNode *neighbor = parent->left;
++ while (neighbor->right && neighbor->splitType == splitType)
++ neighbor = neighbor->right;
++
++ if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
++ // Left neighbour can be merged.
++ parent->split = neighbor->parent->split;
++
++ parent = neighbor->parent;
++ sibling = neighbor == parent->left ? parent->right : parent->left;
++ QSGAreaAllocatorNode **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 = nullptr;
++ delete parent;
++ delete neighbor;
++ done = false;
++ }
++ }
++
++ // Merge with right neighbour.
++ 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);
++
++ QSGAreaAllocatorNode *neighbor = parent->right;
++ while (neighbor->left && neighbor->splitType == splitType)
++ neighbor = neighbor->left;
++
++ if (neighbor->isLeaf() && neighbor->parent->splitType == splitType && !neighbor->isOccupied) {
++ // Right neighbour can be merged.
++ parent->split = neighbor->parent->split;
++
++ parent = neighbor->parent;
++ sibling = neighbor == parent->left ? parent->right : parent->left;
++ QSGAreaAllocatorNode **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 = nullptr;
++ delete parent;
++ delete neighbor;
++ done = false;
++ }
++ }
++ } // end while(!done)
++ }
++
++ namespace {
++ struct AreaAllocatorTable
++ {
++ enum TableSize {
++ HeaderSize = 10,
++ NodeSize = 9
++ };
++
++ enum Offset {
++ // Header
++ majorVersion = 0,
++ minorVersion = 1,
++ width = 2,
++ height = 6,
++
++ // Node
++ split = 0,
++ splitType = 4,
++ flags = 8
++ };
++
++ enum Flags {
++ IsOccupied = 1,
++ HasLeft = 2,
++ HasRight = 4
++ };
++
++ template <typename T>
++ static inline T fetch(const char *data, Offset offset)
++ {
++ return qFromBigEndian<T>(data + int(offset));
++ }
++
++ template <typename T>
++ static inline void put(char *data, Offset offset, T value)
++ {
++ qToBigEndian(value, data + int(offset));
++ }
++ };
++ }
++
++ QByteArray QSGAreaAllocator::serialize()
++ {
++ QVarLengthArray<QSGAreaAllocatorNode *> nodesToProcess;
++
++ QStack<QSGAreaAllocatorNode *> nodes;
++ nodes.push(m_root);
++ while (!nodes.isEmpty()) {
++ QSGAreaAllocatorNode *node = nodes.pop();
++
++ nodesToProcess.append(node);
++ if (node->left != nullptr)
++ nodes.push(node->left);
++ if (node->right != nullptr)
++ nodes.push(node->right);
++ }
++
++ QByteArray ret;
++ ret.resize(AreaAllocatorTable::HeaderSize + AreaAllocatorTable::NodeSize * nodesToProcess.size());
++
++ char *data = ret.data();
++ AreaAllocatorTable::put(data, AreaAllocatorTable::majorVersion, quint8(5));
++ AreaAllocatorTable::put(data, AreaAllocatorTable::minorVersion, quint8(12));
++ AreaAllocatorTable::put(data, AreaAllocatorTable::width, quint32(m_size.width()));
++ AreaAllocatorTable::put(data, AreaAllocatorTable::height, quint32(m_size.height()));
++
++ data += AreaAllocatorTable::HeaderSize;
++ for (QSGAreaAllocatorNode *node : nodesToProcess) {
++ AreaAllocatorTable::put(data, AreaAllocatorTable::split, qint32(node->split));
++ AreaAllocatorTable::put(data, AreaAllocatorTable::splitType, quint32(node->splitType));
++
++ quint8 flags =
++ (node->isOccupied ? AreaAllocatorTable::IsOccupied : 0)
++ | (node->left != nullptr ? AreaAllocatorTable::HasLeft : 0)
++ | (node->right != nullptr ? AreaAllocatorTable::HasRight : 0);
++ AreaAllocatorTable::put(data, AreaAllocatorTable::flags, flags);
++ data += AreaAllocatorTable::NodeSize;
++ }
++
++ return ret;
++ }
++
++ const char *QSGAreaAllocator::deserialize(const char *data, int size)
++ {
++ if (uint(size) < AreaAllocatorTable::HeaderSize) {
++ qWarning("QSGAreaAllocator::deserialize: Data not long enough to fit header");
++ return nullptr;
++ }
++
++ const char *end = data + size;
++
++ quint8 majorVersion = AreaAllocatorTable::fetch<quint8>(data, AreaAllocatorTable::majorVersion);
++ quint8 minorVersion = AreaAllocatorTable::fetch<quint8>(data, AreaAllocatorTable::minorVersion);
++ if (majorVersion != 5 || minorVersion != 12) {
++ qWarning("Unrecognized version %d.%d of QSGAreaAllocator",
++ majorVersion,
++ minorVersion);
++ return nullptr;
++ }
++
++ m_size = QSize(AreaAllocatorTable::fetch<quint32>(data, AreaAllocatorTable::width),
++ AreaAllocatorTable::fetch<quint32>(data, AreaAllocatorTable::height));
++
++ Q_ASSERT(m_root != nullptr);
++ Q_ASSERT(m_root->left == nullptr);
++ Q_ASSERT(m_root->right == nullptr);
++
++ QStack<QSGAreaAllocatorNode *> nodes;
++ nodes.push(m_root);
++
++ data += AreaAllocatorTable::HeaderSize;
++ while (!nodes.isEmpty()) {
++ if (data + AreaAllocatorTable::NodeSize > end) {
++ qWarning("QSGAreaAllocator::deseriable: Data not long enough for nodes");
++ return nullptr;
++ }
++
++ QSGAreaAllocatorNode *node = nodes.pop();
++
++ node->split = AreaAllocatorTable::fetch<qint32>(data, AreaAllocatorTable::split);
++ node->splitType = SplitType(AreaAllocatorTable::fetch<quint32>(data, AreaAllocatorTable::splitType));
++
++ quint8 flags = AreaAllocatorTable::fetch<quint8>(data, AreaAllocatorTable::flags);
++ node->isOccupied = flags & AreaAllocatorTable::IsOccupied;
++
++ if (flags & AreaAllocatorTable::HasLeft) {
++ node->left = new QSGAreaAllocatorNode(node);
++ nodes.push(node->left);
++ }
++
++ if (flags & AreaAllocatorTable::HasRight) {
++ node->right = new QSGAreaAllocatorNode(node);
++ nodes.push(node->right);
++ }
++
++ data += AreaAllocatorTable::NodeSize;
++ }
++
++ return data;
++ }
++
++ QT_END_NAMESPACE