qfragmentmap.cpp

奇趣公司比较新的qt/emd版本

/****************************************************************************
**
** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
**
** This file is part of the QtGui module of the Qt Toolkit.
**
** This file may be used under the terms of the GNU General Public
** License version 2.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 GNU
** General Public Licensing requirements will be met:
** http://trolltech.com/products/qt/licenses/licensing/opensource/
**
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
** or contact the sales department at [e-mail].
**
** In addition, as a special exception, Trolltech gives you certain
** additional rights. These rights are described in the Trolltech GPL
** Exception version 1.0, which can be found at
** http://www.trolltech.com/products/qt/gplexception/ and in the file
** GPL_EXCEPTION.txt in this package.
**
** In addition, as a special exception, Trolltech, as the sole copyright
** holder for Qt Designer, grants users of the Qt/Eclipse Integration
** plug-in the right for the Qt/Eclipse Integration to link to
** functionality provided by Qt Designer and its related libraries.
**
** Trolltech reserves all rights not expressly granted herein.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
****************************************************************************/

#include <private/qtools_p.h>

#include "qfragmentmap_p.h"

#include <stdlib.h>
#include <new>

#define F(x) (*fragment(x))
#define X (*fragment(x))
#define Y (*fragment(y))
#define Z (*fragment(z))
#define W (*fragment(w))
#define N (*fragment(n))
#define P (*fragment(p))
#define PP (*fragment(pp))

#ifdef QT_QMAP_DEBUG
#define PMDEBUG qDebug
void QFragmentMap::inorder(uint x, int level) {
    if (X.left)
        inorder(X.left, level + 1);
    for (int i = 0; i < level; ++i)
        std::cout << "    ";
    std::cout << "this=" << x << " Key=" << key(x) << " size_left=" << X.size_left
              << " size=" << X.size
              << " textPos=" << X.position << (X.color == Red ? " Red" : " Black")
              << std::endl;
    if (X.right)
        inorder(X.right, level + 1);
}
void QFragmentMap::check()
{
    Q_ASSERT((head->node_count == 0 && head->root == 0)
             || (head->node_count != 0 && head->root != 0 && F(head->root).parent == 0));

    ConstIterator it = begin();
    int key = 0;
    for (; it != end(); ++it) {
        Q_ASSERT(key == it.key());
        key += (*it)->size;
    }
}
#else
#define PMDEBUG if(0)qDebug
static inline void inorder() {}
static inline void check() {}
#endif

#define TAG(a,b,c,d) (((quint32)a) << 24) | (((quint32)b) << 16) | (((quint32)c) << 8) | d;

QFragmentMapData::QFragmentMapData(uint fs)
    : fragmentSize(qMax<uint>(fs, sizeof(Header)))
{
    init();
}

void QFragmentMapData::init()
{
    fragments = (char *)malloc(64*fragmentSize);
    head->tag = TAG('p', 'm', 'a', 'p');
    head->root = 0;
    head->freelist = 1;
    head->node_count = 0;
    head->allocated = 64;
    // mark all items to the right as unused
    F(head->freelist).right = 0;
#ifndef QT_NO_DEBUG
    for (uint i = 1; i < head->allocated; ++i)
        F(i).parent = 0xdeadbeef;
#endif
}

QFragmentMapData::~QFragmentMapData()
{
    free(head);
}

uint QFragmentMapData::createFragment()
{
    Q_ASSERT(head->freelist <= head->allocated);

    uint freePos = head->freelist;
    if (freePos == head->allocated) {
        // need to create some free space
        uint needed = qAllocMore((freePos+1)*fragmentSize, 0);
        Q_ASSERT(needed/fragmentSize > head->allocated);
        fragments = (char *)realloc(fragments, needed);
        head->allocated = needed/fragmentSize;
        F(freePos).right = 0;
#ifndef QT_NO_DEBUG
        for (uint i = freePos; i < head->allocated; ++i)
            F(i).parent = 0xdeadbeef;
#endif
    }

    uint nextPos = F(freePos).right;
    if (!nextPos) {
        nextPos = freePos+1;
        if (nextPos < head->allocated)
            F(nextPos).right = 0;
    }

    head->freelist = nextPos;

#ifndef QT_NO_DEBUG
    Q_ASSERT(F(freePos).parent == 0xdeadbeef);
    F(freePos).parent = 0;
    if (nextPos < head->allocated) {
        Q_ASSERT(F(nextPos).parent == 0xdeadbeef);
    }
#endif

    ++head->node_count;

    PMDEBUG("===> createFragment at %d", freePos);
    return freePos;
}

void QFragmentMapData::freeFragment(uint i)
{
    PMDEBUG("===> freeFragment at %d", i);
#ifndef QT_NO_DEBUG
    Q_ASSERT(F(i).parent != 0xdeadbeef);
    if (head->freelist < head->allocated) {
        Q_ASSERT(F(head->freelist).parent == 0xdeadbeef);
    }
    F(i).parent = 0xdeadbeef;
#endif
    F(i).right = head->freelist;
    head->freelist = i;

    --head->node_count;
}


uint QFragmentMapData::next(uint n) const {
    Q_ASSERT(n);
    if (N.right) {
        n = N.right;
        while (N.left)
            n = N.left;
    } else {
        uint y = N.parent;
        while (N.parent && n == Y.right) {
            n = y;
            y = Y.parent;
        }
        n = y;
    }
    return n;
}

uint QFragmentMapData::previous(uint n) const {
    if (!n)
        return maximum(root());

    if (N.left) {
        n = N.left;
        while (N.right)
            n = N.right;
    } else {
        uint y = N.parent;
        while (N.parent && n == Y.left) {
            n = y;
            y = Y.parent;
        }
        n = y;
    }
    return n;
}


/*
     x              y
      \            / \
       y    -->   x   b
      / \          \
     a   b          a
*/
void QFragmentMapData::rotateLeft(uint x)
{
    uint p = X.parent;
    uint y = X.right;
    PMDEBUG("    rotateLeft on x=%d (y=%d, p=%d)", x, y, p);


    if (y) {
        X.right = Y.left;
        if (Y.left)
            F(Y.left).parent = x;
        Y.left = x;
        Y.parent = p;
    } else {
        X.right = 0;
    }
    if (!p) {
        Q_ASSERT(head->root == x);
        head->root = y;
    }
    else if (x == P.left)
        P.left = y;
    else
        P.right = y;
    X.parent = y;
    Y.size_left += X.size_left + X.size;

    inorder();
    check();
}


/*
         x          y
        /          / \
       y    -->   a   x
      / \            /
     a   b          b
*/
void QFragmentMapData::rotateRight(uint x)
{
    uint y = X.left;
    uint p = X.parent;
    PMDEBUG("    rotateRight on x=%d (y=%d, p=%d)", x, y, p);

    if (y) {
        X.left = Y.right;
        if (Y.right)
            F(Y.right).parent = x;
        Y.right = x;
        Y.parent = p;
    } else {
        X.left = 0;
    }
    if (!p) {
        Q_ASSERT(head->root == x);
        head->root = y;
    }
    else if (x == P.right)
        P.right = y;
    else
        P.left = y;
    X.parent = y;
    X.size_left -= Y.size_left + Y.size;

    inorder();
    check();
}


void QFragmentMapData::rebalance(uint x)
{
    X.color = Red;

    PMDEBUG("  -> rebalance x=%d", x);
    inorder();

    while (X.parent && F(X.parent).color == Red) {
        uint p = X.parent;
        uint pp = P.parent;
        Q_ASSERT(pp);
        if (p == PP.left) {
            uint y = PP.right;
            if (y && Y.color == Red) {
                P.color = Black;
                Y.color = Black;
                PP.color = Red;
                x = pp;
            } else {
                if (x == P.right) {
                    x = p;