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
++ // 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