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
++
++ #include "qv4sparsearray_p.h"
++ #include <stdlib.h>
++
++ #ifdef QT_QMAP_DEBUG
++ # include <qstring.h>
++ # include <qvector.h>
++ #endif
++
++ using namespace QV4;
++
++ const SparseArrayNode *SparseArrayNode::nextNode() const
++ {
++ const SparseArrayNode *n = this;
++ if (n->right) {
++ n = n->right;
++ while (n->left)
++ n = n->left;
++ } else {
++ const SparseArrayNode *y = n->parent();
++ while (y && n == y->right) {
++ n = y;
++ y = n->parent();
++ }
++ n = y;
++ }
++ return n;
++ }
++
++ const SparseArrayNode *SparseArrayNode::previousNode() const
++ {
++ const SparseArrayNode *n = this;
++ if (n->left) {
++ n = n->left;
++ while (n->right)
++ n = n->right;
++ } else {
++ const SparseArrayNode *y = n->parent();
++ while (y && n == y->left) {
++ n = y;
++ y = n->parent();
++ }
++ n = y;
++ }
++ return n;
++ }
++
++ SparseArrayNode *SparseArrayNode::copy(SparseArray *d) const
++ {
++ SparseArrayNode *n = d->createNode(size_left, nullptr, false);
++ n->value = value;
++ n->setColor(color());
++ if (left) {
++ n->left = left->copy(d);
++ n->left->setParent(n);
++ } else {
++ n->left = nullptr;
++ }
++ if (right) {
++ n->right = right->copy(d);
++ n->right->setParent(n);
++ } else {
++ n->right = nullptr;
++ }
++ return n;
++ }
++
++ /*
++ x y
++ \ / \
++ y --> x b
++ / \ \
++ a b a
++ */
++ void SparseArray::rotateLeft(SparseArrayNode *x)
++ {
++ SparseArrayNode *&root = header.left;
++ SparseArrayNode *y = x->right;
++ x->right = y->left;
++ if (y->left != nullptr)
++ y->left->setParent(x);
++ y->setParent(x->parent());
++ if (x == root)
++ root = y;
++ else if (x == x->parent()->left)
++ x->parent()->left = y;
++ else
++ x->parent()->right = y;
++ y->left = x;
++ x->setParent(y);
++ y->size_left += x->size_left;
++ }
++
++
++ /*
++ x y
++ / / \
++ y --> a x
++ / \ /
++ a b b
++ */
++ void SparseArray::rotateRight(SparseArrayNode *x)
++ {
++ SparseArrayNode *&root = header.left;
++ SparseArrayNode *y = x->left;
++ x->left = y->right;
++ if (y->right != nullptr)
++ y->right->setParent(x);
++ y->setParent(x->parent());
++ if (x == root)
++ root = y;
++ else if (x == x->parent()->right)
++ x->parent()->right = y;
++ else
++ x->parent()->left = y;
++ y->right = x;
++ x->setParent(y);
++ x->size_left -= y->size_left;
++ }
++
++
++ void SparseArray::rebalance(SparseArrayNode *x)
++ {
++ SparseArrayNode *&root = header.left;
++ x->setColor(SparseArrayNode::Red);
++ while (x != root && x->parent()->color() == SparseArrayNode::Red) {
++ if (x->parent() == x->parent()->parent()->left) {
++ SparseArrayNode *y = x->parent()->parent()->right;
++ if (y && y->color() == SparseArrayNode::Red) {
++ x->parent()->setColor(SparseArrayNode::Black);
++ y->setColor(SparseArrayNode::Black);
++ x->parent()->parent()->setColor(SparseArrayNode::Red);
++ x = x->parent()->parent();
++ } else {
++ if (x == x->parent()->right) {
++ x = x->parent();
++ rotateLeft(x);
++ }
++ x->parent()->setColor(SparseArrayNode::Black);
++ x->parent()->parent()->setColor(SparseArrayNode::Red);
++ rotateRight (x->parent()->parent());
++ }
++ } else {
++ SparseArrayNode *y = x->parent()->parent()->left;
++ if (y && y->color() == SparseArrayNode::Red) {
++ x->parent()->setColor(SparseArrayNode::Black);
++ y->setColor(SparseArrayNode::Black);
++ x->parent()->parent()->setColor(SparseArrayNode::Red);
++ x = x->parent()->parent();
++ } else {
++ if (x == x->parent()->left) {
++ x = x->parent();
++ rotateRight(x);
++ }
++ x->parent()->setColor(SparseArrayNode::Black);
++ x->parent()->parent()->setColor(SparseArrayNode::Red);
++ rotateLeft(x->parent()->parent());
++ }
++ }
++ }
++ root->setColor(SparseArrayNode::Black);
++ }
++
++ void SparseArray::deleteNode(SparseArrayNode *z)
++ {
++ SparseArrayNode *&root = header.left;
++ SparseArrayNode *y = z;
++ SparseArrayNode *x;
++ SparseArrayNode *x_parent;
++ if (y->left == nullptr) {
++ x = y->right;
++ if (y == mostLeftNode) {
++ if (x)
++ mostLeftNode = x; // It cannot have (left) children due the red black invariant.
++ else
++ mostLeftNode = y->parent();
++ }
++ } else if (y->right == nullptr) {
++ x = y->left;
++ } else {
++ y = y->right;
++ while (y->left != nullptr)
++ y = y->left;
++ x = y->right;
++ }
++ if (y != z) {
++ // move y into the position of z
++ // adjust size_left so the keys are ok.
++ z->size_left += y->size_left;
++ SparseArrayNode *n = y->parent();
++ while (n != z) {
++ n->size_left -= y->size_left;
++ n = n->parent();
++ }
++ y->size_left = 0;
++ z->value = y->value;
++
++ if (y != z->right) {
++ x_parent = y->parent();
++ y->parent()->left = x;
++ } else {
++ x_parent = z;
++ z->right = x;
++ }
++ if (x)
++ x->setParent(x_parent);
++ } else {
++ x_parent = y->parent();
++ if (x)
++ x->setParent(y->parent());
++ if (root == y)
++ root = x;
++ else if (y->parent()->left == y)
++ y->parent()->left = x;
++ else
++ y->parent()->right = x;
++ if (x && x == y->right)
++ x->size_left += y->size_left;
++ y->size_left = 0;
++ }
++ if (y->color() != SparseArrayNode::Red) {
++ while (x != root && (x == nullptr || x->color() == SparseArrayNode::Black)) {
++ if (x == x_parent->left) {
++ SparseArrayNode *w = x_parent->right;
++ if (w->color() == SparseArrayNode::Red) {
++ w->setColor(SparseArrayNode::Black);
++ x_parent->setColor(SparseArrayNode::Red);
++ rotateLeft(x_parent);
++ w = x_parent->right;
++ }
++ if ((w->left == nullptr || w->left->color() == SparseArrayNode::Black) &&
++ (w->right == nullptr || w->right->color() == SparseArrayNode::Black)) {
++ w->setColor(SparseArrayNode::Red);
++ x = x_parent;
++ x_parent = x_parent->parent();
++ } else {
++ if (w->right == nullptr || w->right->color() == SparseArrayNode::Black) {
++ if (w->left)
++ w->left->setColor(SparseArrayNode::Black);
++ w->setColor(SparseArrayNode::Red);
++ rotateRight(w);
++ w = x_parent->right;
++ }
++ w->setColor(x_parent->color());
++ x_parent->setColor(SparseArrayNode::Black);
++ if (w->right)
++ w->right->setColor(SparseArrayNode::Black);
++ rotateLeft(x_parent);
++ break;
++ }
++ } else {
++ SparseArrayNode *w = x_parent->left;
++ if (w->color() == SparseArrayNode::Red) {
++ w->setColor(SparseArrayNode::Black);
++ x_parent->setColor(SparseArrayNode::Red);
++ rotateRight(x_parent);
++ w = x_parent->left;
++ }
++ if ((w->right == nullptr || w->right->color() == SparseArrayNode::Black) &&
++ (w->left == nullptr || w->left->color() == SparseArrayNode::Black)) {
++ w->setColor(SparseArrayNode::Red);
++ x = x_parent;
++ x_parent = x_parent->parent();
++ } else {
++ if (w->left == nullptr || w->left->color() == SparseArrayNode::Black) {
++ if (w->right)
++ w->right->setColor(SparseArrayNode::Black);
++ w->setColor(SparseArrayNode::Red);
++ rotateLeft(w);
++ w = x_parent->left;
++ }
++ w->setColor(x_parent->color());
++ x_parent->setColor(SparseArrayNode::Black);
++ if (w->left)
++ w->left->setColor(SparseArrayNode::Black);
++ rotateRight(x_parent);
++ break;
++ }
++ }
++ }
++ if (x)
++ x->setColor(SparseArrayNode::Black);
++ }
++ free(y);
++ --numEntries;
++ }
++
++ void SparseArray::recalcMostLeftNode()
++ {
++ mostLeftNode = &header;
++ while (mostLeftNode->left)
++ mostLeftNode = mostLeftNode->left;
++ }
++
++ static inline int qMapAlignmentThreshold()
++ {
++ // malloc on 32-bit platforms should return pointers that are 8-byte
++ // aligned or more while on 64-bit platforms they should be 16-byte aligned
++ // or more
++ return 2 * sizeof(void*);
++ }
++
++ static inline void *qMapAllocate(int alloc, int alignment)
++ {
++ return alignment > qMapAlignmentThreshold()
++ ? qMallocAligned(alloc, alignment)
++ : ::malloc(alloc);
++ }
++
++ static inline void qMapDeallocate(SparseArrayNode *node, int alignment)
++ {
++ if (alignment > qMapAlignmentThreshold())
++ qFreeAligned(node);
++ else
++ ::free(node);
++ }
++
++ SparseArrayNode *SparseArray::createNode(uint sl, SparseArrayNode *parent, bool left)
++ {
++ SparseArrayNode *node = static_cast<SparseArrayNode *>(qMapAllocate(sizeof(SparseArrayNode), alignof(SparseArrayNode)));
++ Q_CHECK_PTR(node);
++
++ node->p = (quintptr)parent;
++ node->left = nullptr;
++ node->right = nullptr;
++ node->size_left = sl;
++ node->value = UINT_MAX;
++ ++numEntries;
++
++ if (parent) {
++ if (left) {
++ parent->left = node;
++ if (parent == mostLeftNode)
++ mostLeftNode = node;
++ } else {
++ parent->right = node;
++ }
++ node->setParent(parent);
++ rebalance(node);
++ }
++ return node;
++ }
++
++ void SparseArray::freeTree(SparseArrayNode *root, int alignment)
++ {
++ if (root->left)
++ freeTree(root->left, alignment);
++ if (root->right)
++ freeTree(root->right, alignment);
++ qMapDeallocate(root, alignment);
++ }
++
++ SparseArray::SparseArray()
++ : numEntries(0)
++ {
++ freeList = Encode(-1);
++ header.p = 0;
++ header.left = nullptr;
++ header.right = nullptr;
++ mostLeftNode = &header;
++ }
++
++ SparseArray::SparseArray(const SparseArray &other)
++ {
++ header.p = 0;
++ header.right = nullptr;
++ if (other.header.left) {
++ header.left = other.header.left->copy(this);
++ header.left->setParent(&header);
++ recalcMostLeftNode();
++ }
++ freeList = other.freeList;
++ }
++
++ SparseArrayNode *SparseArray::insert(uint akey)
++ {
++ SparseArrayNode *n = root();
++ SparseArrayNode *y = end();
++ bool left = true;
++ uint s = akey;
++ while (n) {
++ y = n;
++ if (s == n->size_left) {
++ return n;
++ } else if (s < n->size_left) {
++ left = true;
++ n = n->left;
++ } else {
++ left = false;
++ s -= n->size_left;
++ n = n->right;
++ }
++ }
++
++ return createNode(s, y, left);
++ }