An error occurred while loading the file. Please try again.
-
Jason McDonald authored
As in the past, to avoid rewriting various autotests that contain line-number information, an extra blank line has been inserted at the end of the license text to ensure that this commit does not change the total number of lines in the license header. Change-Id: I752b02a8155143626d22bd86082177550bd1cfb4 Reviewed-by:Rohan McGovern <rohan.mcgovern@nokia.com>
d6365ee7
/******************************************************************************** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).** Contact: http://www.qt-project.org/legal**** This file is part of the QtCore module of the Qt Toolkit.**** $QT_BEGIN_LICENSE:LGPL21$** Commercial License Usage** Licensees holding valid commercial Qt licenses may use this file in** accordance with the commercial license agreement provided with the** Software or, alternatively, in accordance with the terms contained in** a written agreement between you and Digia. For licensing terms and** conditions see http://qt.digia.com/licensing. For further information** use the contact form at http://qt.digia.com/contact-us.**** GNU Lesser General Public License Usage** Alternatively, this file may be used under the terms of the GNU Lesser** General Public License version 2.1 or version 3 as published by the Free** Software Foundation and appearing in the file LICENSE.LGPLv21 and** LICENSE.LGPLv3 included in the packaging of this file. Please review the** following information to ensure the GNU Lesser General Public License** requirements will be met: https://www.gnu.org/licenses/lgpl.html and** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.**** In addition, as a special exception, Digia gives you certain additional** rights. These rights are described in the Digia Qt LGPL Exception** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.**** $QT_END_LICENSE$******************************************************************************/#include "qv4sparsearray_p.h"#include "qv4runtime_p.h"#include "qv4object_p.h"#include "qv4functionobject_p.h"#include "qv4scopedvalue_p.h"#include <stdlib.h>#ifdef QT_QMAP_DEBUG# include <qstring.h># include <qvector.h>#endifusing 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;7172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
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, 0, false);
n->value = value;
n->setColor(color());
if (left) {
n->left = left->copy(d);
n->left->setParent(n);
} else {
n->left = 0;
}
if (right) {
n->right = right->copy(d);
n->right->setParent(n);
} else {
n->right = 0;
}
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 != 0)
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;
141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
SparseArrayNode *y = x->left;
x->left = y->right;
if (y->right != 0)
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 == 0) {
x = y->right;
if (y == mostLeftNode) {
if (x)
mostLeftNode = x; // It cannot have (left) children due the red black invariant.
211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280
else
mostLeftNode = y->parent();
}
} else if (y->right == 0) {
x = y->left;
} else {
y = y->right;
while (y->left != 0)
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;
if (x)
x->size_left += y->size_left;
} else {
y->parent()->right = x;
if (x)
x->size_left += y->size_left;
}
y->size_left = 0;
}
if (y->color() != SparseArrayNode::Red) {
while (x != root && (x == 0 || 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 == 0 || w->left->color() == SparseArrayNode::Black) &&
(w->right == 0 || w->right->color() == SparseArrayNode::Black)) {
w->setColor(SparseArrayNode::Red);
x = x_parent;
x_parent = x_parent->parent();
} else {
if (w->right == 0 || w->right->color() == SparseArrayNode::Black) {
if (w->left)
w->left->setColor(SparseArrayNode::Black);
w->setColor(SparseArrayNode::Red);
rotateRight(w);
281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350
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 == 0 || w->right->color() == SparseArrayNode::Black) &&
(w->left == 0 || w->left->color() == SparseArrayNode::Black)) {
w->setColor(SparseArrayNode::Red);
x = x_parent;
x_parent = x_parent->parent();
} else {
if (w->left == 0 || 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)
{
351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420
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), Q_ALIGNOF(SparseArrayNode)));
Q_CHECK_PTR(node);
node->p = (quintptr)parent;
node->left = 0;
node->right = 0;
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)
{
header.p = 0;
header.left = 0;
header.right = 0;
mostLeftNode = &header;
}
SparseArray::SparseArray(const SparseArray &other)
{
header.p = 0;
header.right = 0;
if (other.header.left) {
header.left = other.header.left->copy(this);
header.left->setParent(&header);
recalcMostLeftNode();
}
}
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) {
421422423424425426427428429430431432433434
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);
}