An error occurred while loading the file. Please try again.
-
Michael Bruning authored
Adds default QPageLayout values. Change-Id: Ibf2964ecd86350a51d682e385973f830ac4347a7 Reviewed-by:Joerg Bornemann <joerg.bornemann@theqtcompany.com>
a3d2ee4e
/******************************************************************************** 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);
}