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