qsgareaallocator.cpp

Go to the documentation of this file.

// 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 &currentRect, 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