From b1a0f7c0d23fb303b00265bb2c5615990f909f98 Mon Sep 17 00:00:00 2001 From: Kim Motoyoshi Kalland Date: Fri, 15 Jul 2011 13:56:26 +0200 Subject: Moved red-black tree from qtriangulator.cpp into its own file. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Moved the red-black tree class so it can be used outside the triangulator as well. Change-Id: I1d63fc88502e8e6c390cac2820c0ce45721cda79 Reviewed-on: http://codereview.qt.nokia.com/1710 Reviewed-by: Qt Sanity Bot Reviewed-by: Samuel Rødal --- src/opengl/gl2paintengineex/qrbtree_p.h | 573 ++++++++++++++++++++++++++ src/opengl/gl2paintengineex/qtriangulator.cpp | 521 +---------------------- src/opengl/opengl.pro | 1 + 3 files changed, 577 insertions(+), 518 deletions(-) create mode 100644 src/opengl/gl2paintengineex/qrbtree_p.h diff --git a/src/opengl/gl2paintengineex/qrbtree_p.h b/src/opengl/gl2paintengineex/qrbtree_p.h new file mode 100644 index 0000000000..09ef81cdbb --- /dev/null +++ b/src/opengl/gl2paintengineex/qrbtree_p.h @@ -0,0 +1,573 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtOpenGL module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** This file may be used under the terms of the GNU Lesser General Public +** License version 2.1 as published by the Free Software Foundation and +** appearing in the file LICENSE.LGPL included in the packaging of this +** file. Please review the following information to ensure the GNU Lesser +** General Public License version 2.1 requirements will be met: +** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU General +** Public License version 3.0 as published by the Free Software Foundation +** and appearing in the file LICENSE.GPL included in the packaging of this +** file. Please review the following information to ensure the GNU General +** Public License version 3.0 requirements will be met: +** http://www.gnu.org/copyleft/gpl.html. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QRBTREE_P_H +#define QRBTREE_P_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 + +QT_BEGIN_NAMESPACE + +template +struct QRBTree +{ + struct Node + { + inline Node() : parent(0), left(0), right(0), red(true) { } + inline ~Node() {if (left) delete left; if (right) delete right;} + T data; + Node *parent; + Node *left; + Node *right; + bool red; + }; + + inline QRBTree() : root(0), freeList(0) { } + inline ~QRBTree(); + + inline void clear(); + + void attachBefore(Node *parent, Node *child); + void attachAfter(Node *parent, Node *child); + + inline Node *front(Node *node) const; + inline Node *back(Node *node) const; + Node *next(Node *node) const; + Node *previous(Node *node) const; + + inline void deleteNode(Node *&node); + inline Node *newNode(); + + // Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise. + // 'left' and 'right' cannot be null. + int order(Node *left, Node *right); + inline bool validate() const; + +private: + void rotateLeft(Node *node); + void rotateRight(Node *node); + void update(Node *node); + + inline void attachLeft(Node *parent, Node *child); + inline void attachRight(Node *parent, Node *child); + + int blackDepth(Node *top) const; + bool checkRedBlackProperty(Node *top) const; + + void swapNodes(Node *n1, Node *n2); + void detach(Node *node); + + // 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree. + void rebalance(Node *node); + +public: + Node *root; +private: + Node *freeList; +}; + +template +inline QRBTree::~QRBTree() +{ + clear(); + while (freeList) { + // Avoid recursively calling the destructor, as this list may become large. + Node *next = freeList->right; + freeList->right = 0; + delete freeList; + freeList = next; + } +} + +template +inline void QRBTree::clear() +{ + if (root) + delete root; + root = 0; +} + +template +void QRBTree::rotateLeft(Node *node) +{ + // | | // + // N B // + // / \ / \ // + // A B ---> N D // + // / \ / \ // + // C D A C // + + Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root); + ref = node->right; + node->right->parent = node->parent; + + // : // + // N // + // / :| // + // A B // + // / \ // + // C D // + + node->right = ref->left; + if (ref->left) + ref->left->parent = node; + + // : | // + // N B // + // / \ : \ // + // A C D // + + ref->left = node; + node->parent = ref; + + // | // + // B // + // / \ // + // N D // + // / \ // + // A C // +} + +template +void QRBTree::rotateRight(Node *node) +{ + // | | // + // N A // + // / \ / \ // + // A B ---> C N // + // / \ / \ // + // C D D B // + + Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root); + ref = node->left; + node->left->parent = node->parent; + + node->left = ref->right; + if (ref->right) + ref->right->parent = node; + + ref->right = node; + node->parent = ref; +} + +template +void QRBTree::update(Node *node) // call this after inserting a node +{ + for (;;) { + Node *parent = node->parent; + + // if the node is the root, color it black + if (!parent) { + node->red = false; + return; + } + + // if the parent is black, the node can be left red + if (!parent->red) + return; + + // at this point, the parent is red and cannot be the root + Node *grandpa = parent->parent; + Q_ASSERT(grandpa); + + Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left); + if (uncle && uncle->red) { + // grandpa's black, parent and uncle are red. + // let parent and uncle be black, grandpa red and recursively update grandpa. + Q_ASSERT(!grandpa->red); + parent->red = false; + uncle->red = false; + grandpa->red = true; + node = grandpa; + continue; + } + + // at this point, uncle is black + if (node == parent->right && parent == grandpa->left) + rotateLeft(node = parent); + else if (node == parent->left && parent == grandpa->right) + rotateRight(node = parent); + parent = node->parent; + + if (parent == grandpa->left) { + rotateRight(grandpa); + parent->red = false; + grandpa->red = true; + } else { + rotateLeft(grandpa); + parent->red = false; + grandpa->red = true; + } + return; + } +} + +template +inline void QRBTree::attachLeft(Node *parent, Node *child) +{ + Q_ASSERT(!parent->left); + parent->left = child; + child->parent = parent; + update(child); +} + +template +inline void QRBTree::attachRight(Node *parent, Node *child) +{ + Q_ASSERT(!parent->right); + parent->right = child; + child->parent = parent; + update(child); +} + +template +void QRBTree::attachBefore(Node *parent, Node *child) +{ + if (!root) + update(root = child); + else if (!parent) + attachRight(back(root), child); + else if (parent->left) + attachRight(back(parent->left), child); + else + attachLeft(parent, child); +} + +template +void QRBTree::attachAfter(Node *parent, Node *child) +{ + if (!root) + update(root = child); + else if (!parent) + attachLeft(front(root), child); + else if (parent->right) + attachLeft(front(parent->right), child); + else + attachRight(parent, child); +} + +template +void QRBTree::swapNodes(Node *n1, Node *n2) +{ + // Since iterators must not be invalidated, it is not sufficient to only swap the data. + if (n1->parent == n2) { + n1->parent = n2->parent; + n2->parent = n1; + } else if (n2->parent == n1) { + n2->parent = n1->parent; + n1->parent = n2; + } else { + qSwap(n1->parent, n2->parent); + } + + qSwap(n1->left, n2->left); + qSwap(n1->right, n2->right); + qSwap(n1->red, n2->red); + + if (n1->parent) { + if (n1->parent->left == n2) + n1->parent->left = n1; + else + n1->parent->right = n1; + } else { + root = n1; + } + + if (n2->parent) { + if (n2->parent->left == n1) + n2->parent->left = n2; + else + n2->parent->right = n2; + } else { + root = n2; + } + + if (n1->left) + n1->left->parent = n1; + if (n1->right) + n1->right->parent = n1; + + if (n2->left) + n2->left->parent = n2; + if (n2->right) + n2->right->parent = n2; +} + +template +void QRBTree::detach(Node *node) // call this before removing a node. +{ + if (node->right) + swapNodes(node, front(node->right)); + + Node *child = (node->left ? node->left : node->right); + + if (!node->red) { + if (child && child->red) + child->red = false; + else + rebalance(node); + } + + Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root); + ref = child; + if (child) + child->parent = node->parent; + node->left = node->right = node->parent = 0; +} + +// 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree. +template +void QRBTree::rebalance(Node *node) +{ + Q_ASSERT(!node->red); + for (;;) { + if (!node->parent) + return; + + // at this point, node is not a parent, it is black, thus it must have a sibling. + Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left); + Q_ASSERT(sibling); + + if (sibling->red) { + sibling->red = false; + node->parent->red = true; + if (node == node->parent->left) + rotateLeft(node->parent); + else + rotateRight(node->parent); + sibling = (node == node->parent->left ? node->parent->right : node->parent->left); + Q_ASSERT(sibling); + } + + // at this point, the sibling is black. + Q_ASSERT(!sibling->red); + + if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) { + bool parentWasRed = node->parent->red; + sibling->red = true; + node->parent->red = false; + if (parentWasRed) + return; + node = node->parent; + continue; + } + + // at this point, at least one of the sibling's children is red. + + if (node == node->parent->left) { + if (!sibling->right || !sibling->right->red) { + Q_ASSERT(sibling->left); + sibling->red = true; + sibling->left->red = false; + rotateRight(sibling); + + sibling = sibling->parent; + Q_ASSERT(sibling); + } + sibling->red = node->parent->red; + node->parent->red = false; + + Q_ASSERT(sibling->right->red); + sibling->right->red = false; + rotateLeft(node->parent); + } else { + if (!sibling->left || !sibling->left->red) { + Q_ASSERT(sibling->right); + sibling->red = true; + sibling->right->red = false; + rotateLeft(sibling); + + sibling = sibling->parent; + Q_ASSERT(sibling); + } + sibling->red = node->parent->red; + node->parent->red = false; + + Q_ASSERT(sibling->left->red); + sibling->left->red = false; + rotateRight(node->parent); + } + return; + } +} + +template +inline typename QRBTree::Node *QRBTree::front(Node *node) const +{ + while (node->left) + node = node->left; + return node; +} + +template +inline typename QRBTree::Node *QRBTree::back(Node *node) const +{ + while (node->right) + node = node->right; + return node; +} + +template +typename QRBTree::Node *QRBTree::next(Node *node) const +{ + if (node->right) + return front(node->right); + while (node->parent && node == node->parent->right) + node = node->parent; + return node->parent; +} + +template +typename QRBTree::Node *QRBTree::previous(Node *node) const +{ + if (node->left) + return back(node->left); + while (node->parent && node == node->parent->left) + node = node->parent; + return node->parent; +} + +template +int QRBTree::blackDepth(Node *top) const +{ + if (!top) + return 0; + int leftDepth = blackDepth(top->left); + int rightDepth = blackDepth(top->right); + if (leftDepth != rightDepth) + return -1; + if (!top->red) + ++leftDepth; + return leftDepth; +} + +template +bool QRBTree::checkRedBlackProperty(Node *top) const +{ + if (!top) + return true; + if (top->left && !checkRedBlackProperty(top->left)) + return false; + if (top->right && !checkRedBlackProperty(top->right)) + return false; + return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red))); +} + +template +inline bool QRBTree::validate() const +{ + return checkRedBlackProperty(root) && blackDepth(root) != -1; +} + +template +inline void QRBTree::deleteNode(Node *&node) +{ + Q_ASSERT(node); + detach(node); + node->right = freeList; + freeList = node; + node = 0; +} + +template +inline typename QRBTree::Node *QRBTree::newNode() +{ + if (freeList) { + Node *node = freeList; + freeList = freeList->right; + node->parent = node->left = node->right = 0; + node->red = true; + return node; + } + return new Node; +} + +// Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise. +// 'left' and 'right' cannot be null. +template +int QRBTree::order(Node *left, Node *right) +{ + Q_ASSERT(left && right); + if (left == right) + return 0; + + QVector leftAncestors; + QVector rightAncestors; + while (left) { + leftAncestors.push_back(left); + left = left->parent; + } + while (right) { + rightAncestors.push_back(right); + right = right->parent; + } + Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root); + + while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) { + leftAncestors.pop_back(); + rightAncestors.pop_back(); + } + + if (!leftAncestors.empty()) + return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1); + + if (!rightAncestors.empty()) + return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1); + + // The code should never reach this point. + Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty()); + return 0; +} + +QT_END_NAMESPACE + +#endif diff --git a/src/opengl/gl2paintengineex/qtriangulator.cpp b/src/opengl/gl2paintengineex/qtriangulator.cpp index c1cad7e881..d4b7131794 100644 --- a/src/opengl/gl2paintengineex/qtriangulator.cpp +++ b/src/opengl/gl2paintengineex/qtriangulator.cpp @@ -53,11 +53,11 @@ #include #include #include -#include - -#include #include +#include + +#include QT_BEGIN_NAMESPACE @@ -587,521 +587,6 @@ T QMaxHeap::pop() return result; } -//============================================================================// -// QRBTree // -//============================================================================// - -template -struct QRBTree -{ - struct Node - { - inline Node() : parent(0), left(0), right(0), red(true) { } - inline ~Node() {if (left) delete left; if (right) delete right;} - T data; - Node *parent; - Node *left; - Node *right; - bool red; - }; - - inline QRBTree() : root(0), freeList(0) { } - inline ~QRBTree(); - - inline void clear(); - - void attachBefore(Node *parent, Node *child); - void attachAfter(Node *parent, Node *child); - - inline Node *front(Node *node) const; - inline Node *back(Node *node) const; - Node *next(Node *node) const; - Node *previous(Node *node) const; - - inline void deleteNode(Node *&node); - inline Node *newNode(); - - // Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise. - // 'left' and 'right' cannot be null. - int order(Node *left, Node *right); - inline bool validate() const; - -private: - void rotateLeft(Node *node); - void rotateRight(Node *node); - void update(Node *node); - - inline void attachLeft(Node *parent, Node *child); - inline void attachRight(Node *parent, Node *child); - - int blackDepth(Node *top) const; - bool checkRedBlackProperty(Node *top) const; - - void swapNodes(Node *n1, Node *n2); - void detach(Node *node); - - // 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree. - void rebalance(Node *node); - -public: - Node *root; -private: - Node *freeList; -}; - -template -inline QRBTree::~QRBTree() -{ - clear(); - while (freeList) { - // Avoid recursively calling the destructor, as this list may become large. - Node *next = freeList->right; - freeList->right = 0; - delete freeList; - freeList = next; - } -} - -template -inline void QRBTree::clear() -{ - if (root) - delete root; - root = 0; -} - -template -void QRBTree::rotateLeft(Node *node) -{ - // | | // - // N B // - // / \ / \ // - // A B ---> N D // - // / \ / \ // - // C D A C // - - Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root); - ref = node->right; - node->right->parent = node->parent; - - // : // - // N // - // / :| // - // A B // - // / \ // - // C D // - - node->right = ref->left; - if (ref->left) - ref->left->parent = node; - - // : | // - // N B // - // / \ : \ // - // A C D // - - ref->left = node; - node->parent = ref; - - // | // - // B // - // / \ // - // N D // - // / \ // - // A C // -} - -template -void QRBTree::rotateRight(Node *node) -{ - // | | // - // N A // - // / \ / \ // - // A B ---> C N // - // / \ / \ // - // C D D B // - - Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root); - ref = node->left; - node->left->parent = node->parent; - - node->left = ref->right; - if (ref->right) - ref->right->parent = node; - - ref->right = node; - node->parent = ref; -} - -template -void QRBTree::update(Node *node) // call this after inserting a node -{ - for (;;) { - Node *parent = node->parent; - - // if the node is the root, color it black - if (!parent) { - node->red = false; - return; - } - - // if the parent is black, the node can be left red - if (!parent->red) - return; - - // at this point, the parent is red and cannot be the root - Node *grandpa = parent->parent; - Q_ASSERT(grandpa); - - Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left); - if (uncle && uncle->red) { - // grandpa's black, parent and uncle are red. - // let parent and uncle be black, grandpa red and recursively update grandpa. - Q_ASSERT(!grandpa->red); - parent->red = false; - uncle->red = false; - grandpa->red = true; - node = grandpa; - continue; - } - - // at this point, uncle is black - if (node == parent->right && parent == grandpa->left) - rotateLeft(node = parent); - else if (node == parent->left && parent == grandpa->right) - rotateRight(node = parent); - parent = node->parent; - - if (parent == grandpa->left) { - rotateRight(grandpa); - parent->red = false; - grandpa->red = true; - } else { - rotateLeft(grandpa); - parent->red = false; - grandpa->red = true; - } - return; - } -} - -template -inline void QRBTree::attachLeft(Node *parent, Node *child) -{ - Q_ASSERT(!parent->left); - parent->left = child; - child->parent = parent; - update(child); -} - -template -inline void QRBTree::attachRight(Node *parent, Node *child) -{ - Q_ASSERT(!parent->right); - parent->right = child; - child->parent = parent; - update(child); -} - -template -void QRBTree::attachBefore(Node *parent, Node *child) -{ - if (!root) - update(root = child); - else if (!parent) - attachRight(back(root), child); - else if (parent->left) - attachRight(back(parent->left), child); - else - attachLeft(parent, child); -} - -template -void QRBTree::attachAfter(Node *parent, Node *child) -{ - if (!root) - update(root = child); - else if (!parent) - attachLeft(front(root), child); - else if (parent->right) - attachLeft(front(parent->right), child); - else - attachRight(parent, child); -} - -template -void QRBTree::swapNodes(Node *n1, Node *n2) -{ - // Since iterators must not be invalidated, it is not sufficient to only swap the data. - if (n1->parent == n2) { - n1->parent = n2->parent; - n2->parent = n1; - } else if (n2->parent == n1) { - n2->parent = n1->parent; - n1->parent = n2; - } else { - qSwap(n1->parent, n2->parent); - } - - qSwap(n1->left, n2->left); - qSwap(n1->right, n2->right); - qSwap(n1->red, n2->red); - - if (n1->parent) { - if (n1->parent->left == n2) - n1->parent->left = n1; - else - n1->parent->right = n1; - } else { - root = n1; - } - - if (n2->parent) { - if (n2->parent->left == n1) - n2->parent->left = n2; - else - n2->parent->right = n2; - } else { - root = n2; - } - - if (n1->left) - n1->left->parent = n1; - if (n1->right) - n1->right->parent = n1; - - if (n2->left) - n2->left->parent = n2; - if (n2->right) - n2->right->parent = n2; -} - -template -void QRBTree::detach(Node *node) // call this before removing a node. -{ - if (node->right) - swapNodes(node, front(node->right)); - - Node *child = (node->left ? node->left : node->right); - - if (!node->red) { - if (child && child->red) - child->red = false; - else - rebalance(node); - } - - Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root); - ref = child; - if (child) - child->parent = node->parent; - node->left = node->right = node->parent = 0; -} - -// 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree. -template -void QRBTree::rebalance(Node *node) -{ - Q_ASSERT(!node->red); - for (;;) { - if (!node->parent) - return; - - // at this point, node is not a parent, it is black, thus it must have a sibling. - Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left); - Q_ASSERT(sibling); - - if (sibling->red) { - sibling->red = false; - node->parent->red = true; - if (node == node->parent->left) - rotateLeft(node->parent); - else - rotateRight(node->parent); - sibling = (node == node->parent->left ? node->parent->right : node->parent->left); - Q_ASSERT(sibling); - } - - // at this point, the sibling is black. - Q_ASSERT(!sibling->red); - - if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) { - bool parentWasRed = node->parent->red; - sibling->red = true; - node->parent->red = false; - if (parentWasRed) - return; - node = node->parent; - continue; - } - - // at this point, at least one of the sibling's children is red. - - if (node == node->parent->left) { - if (!sibling->right || !sibling->right->red) { - Q_ASSERT(sibling->left); - sibling->red = true; - sibling->left->red = false; - rotateRight(sibling); - - sibling = sibling->parent; - Q_ASSERT(sibling); - } - sibling->red = node->parent->red; - node->parent->red = false; - - Q_ASSERT(sibling->right->red); - sibling->right->red = false; - rotateLeft(node->parent); - } else { - if (!sibling->left || !sibling->left->red) { - Q_ASSERT(sibling->right); - sibling->red = true; - sibling->right->red = false; - rotateLeft(sibling); - - sibling = sibling->parent; - Q_ASSERT(sibling); - } - sibling->red = node->parent->red; - node->parent->red = false; - - Q_ASSERT(sibling->left->red); - sibling->left->red = false; - rotateRight(node->parent); - } - return; - } -} - -template -inline typename QRBTree::Node *QRBTree::front(Node *node) const -{ - while (node->left) - node = node->left; - return node; -} - -template -inline typename QRBTree::Node *QRBTree::back(Node *node) const -{ - while (node->right) - node = node->right; - return node; -} - -template -typename QRBTree::Node *QRBTree::next(Node *node) const -{ - if (node->right) - return front(node->right); - while (node->parent && node == node->parent->right) - node = node->parent; - return node->parent; -} - -template -typename QRBTree::Node *QRBTree::previous(Node *node) const -{ - if (node->left) - return back(node->left); - while (node->parent && node == node->parent->left) - node = node->parent; - return node->parent; -} - -template -int QRBTree::blackDepth(Node *top) const -{ - if (!top) - return 0; - int leftDepth = blackDepth(top->left); - int rightDepth = blackDepth(top->right); - if (leftDepth != rightDepth) - return -1; - if (!top->red) - ++leftDepth; - return leftDepth; -} - -template -bool QRBTree::checkRedBlackProperty(Node *top) const -{ - if (!top) - return true; - if (top->left && !checkRedBlackProperty(top->left)) - return false; - if (top->right && !checkRedBlackProperty(top->right)) - return false; - return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red))); -} - -template -inline bool QRBTree::validate() const -{ - return checkRedBlackProperty(root) && blackDepth(root) != -1; -} - -template -inline void QRBTree::deleteNode(Node *&node) -{ - Q_ASSERT(node); - detach(node); - node->right = freeList; - freeList = node; - node = 0; -} - -template -inline typename QRBTree::Node *QRBTree::newNode() -{ - if (freeList) { - Node *node = freeList; - freeList = freeList->right; - node->parent = node->left = node->right = 0; - node->red = true; - return node; - } - return new Node; -} - -// Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise. -// 'left' and 'right' cannot be null. -template -int QRBTree::order(Node *left, Node *right) -{ - Q_ASSERT(left && right); - if (left == right) - return 0; - - QVector leftAncestors; - QVector rightAncestors; - while (left) { - leftAncestors.push_back(left); - left = left->parent; - } - while (right) { - rightAncestors.push_back(right); - right = right->parent; - } - Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root); - - while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) { - leftAncestors.pop_back(); - rightAncestors.pop_back(); - } - - if (!leftAncestors.empty()) - return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1); - - if (!rightAncestors.empty()) - return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1); - - // The code should never reach this point. - Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty()); - return 0; -} - //============================================================================// // QInt64Hash // //============================================================================// diff --git a/src/opengl/opengl.pro b/src/opengl/opengl.pro index 16a4ce00e9..e2dc011532 100644 --- a/src/opengl/opengl.pro +++ b/src/opengl/opengl.pro @@ -68,6 +68,7 @@ SOURCES += qgl.cpp \ gl2paintengineex/qglcustomshaderstage_p.h \ gl2paintengineex/qtriangulatingstroker_p.h \ gl2paintengineex/qtriangulator_p.h \ + gl2paintengineex/qrbtree_p.h \ gl2paintengineex/qtextureglyphcache_gl_p.h \ gl2paintengineex/qglshadercache_p.h \ gl2paintengineex/qglshadercache_meego_p.h -- cgit v1.2.3