qv4sparsearray_p.h

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
// Qt-Security score:significant
 
#ifndef QV4SPARSEARRAY_H
#define QV4SPARSEARRAY_H
 
//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists purely as an
// implementation detail.  This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//
 
#include "qv4global_p.h"
#include "qv4value_p.h"
#include <QtCore/qlist.h>
 
//#define Q_MAP_DEBUG
#ifdef Q_MAP_DEBUG
#include <QtCore/qdebug.h>
#endif
 
#include <new>
 
QT_BEGIN_NAMESPACE
 
namespace QV4 {
 
struct SparseArray;
 
struct SparseArrayNode
{
    quintptr p;
    SparseArrayNode *left;
    SparseArrayNode *right;
    uint size_left;
    uint value;
 
    enum Color { Red = 0, Black = 1 };
    enum { Mask = 3 }; // reserve the second bit as well
 
    const SparseArrayNode *nextNode() const;
    SparseArrayNode *nextNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->nextNode()); }
    const SparseArrayNode *previousNode() const;
    SparseArrayNode *previousNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->previousNode()); }
 
    Color color() const { return Color(p & 1); }
    void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
    SparseArrayNode *parent() const { return reinterpret_cast<SparseArrayNode *>(p & ~Mask); }
    void setParent(SparseArrayNode *pp) { p = (p & Mask) | quintptr(pp); }
 
    uint key() const {
        uint k = size_left;
        const SparseArrayNode *n = this;
        while (SparseArrayNode *p = n->parent()) {
            if (p && p->right == n)
                k += p->size_left;
            n = p;
        }
        return k;
    }
 
    SparseArrayNode *copy(SparseArray *d) const;
 
    SparseArrayNode *lowerBound(uint key);
    SparseArrayNode *upperBound(uint key);
};
 
 
inline SparseArrayNode *SparseArrayNode::lowerBound(uint akey)
{
    SparseArrayNode *n = this;
    SparseArrayNode *last = nullptr;
    while (n) {
        if (akey <= n->size_left) {
            last = n;
            n = n->left;
        } else {
            akey -= n->size_left;
            n = n->right;
        }
    }
    return last;
}
 
 
inline SparseArrayNode *SparseArrayNode::upperBound(uint akey)
{
    SparseArrayNode *n = this;
    SparseArrayNode *last = nullptr;
    while (n) {
        if (akey < n->size_left) {
            last = n;
            n = n->left;
        } else {
            akey -= n->size_left;
            n = n->right;
        }
    }
    return last;
}
 
 
 
struct Q_QML_EXPORT SparseArray
{
    SparseArray();
    ~SparseArray() {
        if (SparseArrayNode *n = root())
            freeTree(n, alignof(SparseArrayNode));
    }
 
    SparseArray(const SparseArray &other);
 
    Value freeList;
private:
    SparseArray &operator=(const SparseArray &other);
 
    int numEntries;
    SparseArrayNode header;
    SparseArrayNode *mostLeftNode;
 
    void rotateLeft(SparseArrayNode *x);
    void rotateRight(SparseArrayNode *x);
    void rebalance(SparseArrayNode *x);
    void recalcMostLeftNode();
 
    SparseArrayNode *root() const { return header.left; }
 
    void deleteNode(SparseArrayNode *z);
 
 
public:
    SparseArrayNode *createNode(uint sl, SparseArrayNode *parent, bool left);
    void freeTree(SparseArrayNode *root, int alignment);
 
    SparseArrayNode *findNode(uint akey) const;
 
    uint nEntries() const { return numEntries; }
 
    uint pop_front();
    void push_front(uint at);
    uint pop_back(uint len);
    void push_back(uint at, uint len);
 
    QList<int> keys() const;
 
    const SparseArrayNode *end() const { return &header; }
    SparseArrayNode *end() { return &header; }
    const SparseArrayNode *begin() const { if (root()) return mostLeftNode; return end(); }
    SparseArrayNode *begin() { if (root()) return mostLeftNode; return end(); }
 
    SparseArrayNode *erase(SparseArrayNode *n);
 
    SparseArrayNode *lowerBound(uint key);
    const SparseArrayNode *lowerBound(uint key) const;
    SparseArrayNode *upperBound(uint key);
    const SparseArrayNode *upperBound(uint key) const;
    SparseArrayNode *insert(uint akey);
 
    // STL compatibility
    typedef uint key_type;
    typedef int mapped_type;
    typedef qptrdiff difference_type;
    typedef int size_type;
 
#ifdef Q_MAP_DEBUG
    void dump() const;
#endif
};
 
inline SparseArrayNode *SparseArray::findNode(uint akey) const
{
    SparseArrayNode *n = root();
 
    while (n) {
        if (akey == n->size_left) {
            return n;
        } else if (akey < n->size_left) {
            n = n->left;
        } else {
            akey -= n->size_left;
            n = n->right;
        }
    }
 
    return nullptr;
}
 
inline uint SparseArray::pop_front()
{
    uint idx = UINT_MAX ;
 
    SparseArrayNode *n = findNode(0);
    if (n) {
        idx = n->value;
        deleteNode(n);
        // adjust all size_left indices on the path to leftmost item by 1
        SparseArrayNode *rootNode = root();
        while (rootNode) {
            rootNode->size_left -= 1;
            rootNode = rootNode->left;
        }
    }
    return idx;
}
 
inline void SparseArray::push_front(uint value)
{
    // adjust all size_left indices on the path to leftmost item by 1
    SparseArrayNode *n = root();
    while (n) {
        n->size_left += 1;
        n = n->left;
    }
    n = insert(0);
    n->value = value;
}
 
inline uint SparseArray::pop_back(uint len)
{
    uint idx = UINT_MAX;
    if (!len)
        return idx;
 
    SparseArrayNode *n = findNode(len - 1);
    if (n) {
        idx = n->value;
        deleteNode(n);
    }
    return idx;
}
 
inline void SparseArray::push_back(uint index, uint len)
{
    SparseArrayNode *n = insert(len);
    n->value = index;
}
 
#ifdef Q_MAP_DEBUG
inline void SparseArray::dump() const
{
    const SparseArrayNode *it = begin();
    qDebug() << "map dump:";
    while (it != end()) {
        const SparseArrayNode *n = it;
        int depth = 0;
        while (n && n != root()) {
            ++depth;
            n = n->parent();
        }
        QByteArray space(4*depth, ' ');
        qDebug() << space << (it->color() == SparseArrayNode::Red ? "Red  " : "Black") << it << it->size_left << it->left << it->right
                 << it->key() << it->value;
        it = it->nextNode();
    }
    qDebug() << "---------";
}
#endif
 
 
inline SparseArrayNode *SparseArray::erase(SparseArrayNode *n)
{
    if (n == end())
        return n;
 
    SparseArrayNode *next = n->nextNode();
    deleteNode(n);
    return next;
}
 
inline QList<int> SparseArray::keys() const
{
    QList<int> res;
    res.reserve(numEntries);
    SparseArrayNode *n = mostLeftNode;
    while (n != end()) {
        res.append(n->key());
        n = n->nextNode();
    }
    return res;
}
 
inline const SparseArrayNode *SparseArray::lowerBound(uint akey) const
{
    if (SparseArrayNode *n = root()) {
        if (const SparseArrayNode *lb = n->lowerBound(akey))
            return lb;
    }
 
    return end();
}
 
 
inline SparseArrayNode *SparseArray::lowerBound(uint akey)
{
    if (SparseArrayNode *n = root()) {
        if (SparseArrayNode *lb = n->lowerBound(akey))
            return lb;
    }
 
    return end();
}
 
 
inline const SparseArrayNode *SparseArray::upperBound(uint akey) const
{
    if (SparseArrayNode *n = root()) {
        if (const SparseArrayNode *ub = n->upperBound(akey))
            return ub;
    }
 
    return end();
}
 
 
inline SparseArrayNode *SparseArray::upperBound(uint akey)
{
    if (SparseArrayNode *n = root()) {
        if (SparseArrayNode *ub = n->upperBound(akey))
            return ub;
    }
 
    return end();
}
 
}
 
QT_END_NAMESPACE
 
#endif