qfragmentmap.cpp

/****************************************************************************
**
** Copyright (C) 1992-2008 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 versions 2.0 or 3.0 as published by the Free Software
** Foundation and appearing in the files LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file.  Alternatively you may (at
** your option) use any later version of the GNU General Public
** License if such license has been publicly approved by Trolltech ASA
** (or its successors, if any) and the KDE Free Qt Foundation. In
** addition, as a special exception, Trolltech gives you certain
** additional rights. These rights are described in the Trolltech GPL
** Exception version 1.1, which can be found at
** http://www.trolltech.com/products/qt/gplexception/ and in the file
** GPL_EXCEPTION.txt in this package.
**
** 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 sales@trolltech.com.
**
** 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.
**
** This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
** INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
** A PARTICULAR PURPOSE. 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;
                    rotateLeft(x);
                    p = X.parent;
                    pp = P.parent;
                }
                P.color = Black;
                if (pp) {
                    PP.color = Red;
                    rotateRight(pp);
                }
            }
        } else {
            uint y = PP.left;
            if (y && Y.color == Red) {
                P.color = Black;
                Y.color = Black;
                PP.color = Red;
                x = pp;
            } else {
                if (x == P.left) {
                    x = p;
                    rotateRight(x);
                    p = X.parent;
                    pp = P.parent;
                }
                P.color = Black;
                if (pp) {
                    PP.color = Red;
                    rotateLeft(pp);
                }
            }
        }
    }
    F(root()).color = Black;
    check();
}


uint QFragmentMapData::erase_single(uint z)
{
    uint w = previous(z);
    uint y = z;
    uint x;
    uint p;

    if (!Y.left) {
        x = Y.right;
    } else if (!Y.right) {
        x = Y.left;
    } else {
        y = Y.right;
        while (Y.left)
            y = Y.left;
        x = Y.right;
    }

    PMDEBUG("removeAndRebalance on %d (x=%d, y=%d)", z, x, y);
    inorder();

    if (y != z) {
        F(Z.left).parent = y;
        Y.left = Z.left;
        Y.size_left = Z.size_left;
        if (y != Z.right) {
            /*
                     z                y
                    / \              / \
                   a   b            a   b
                      /                /
                    ...     -->      ...
                    /                /
                   y                x
                  / \
                 0   x
             */
            p = Y.parent;
            if (x)
                X.parent = p;
            P.left = x;
            Y.right = Z.right;
            F(Z.right).parent = y;
            uint n = p;
            while (n != y) {
                N.size_left -= Y.size;
                n = N.parent;
            }
        } else {
            /*
                     z                y
                    / \              / \
                   a   y     -->    a   x
                      / \
                     0   x
             */
            p = y;
        }
        uint zp = Z.parent;
        if (!zp) {
            Q_ASSERT(head->root == z);
            head->root = y;
        } else if (F(zp).left == z) {
            F(zp).left = y;
            F(zp).size_left -= Z.size;
        } else {
            F(zp).right = y;
        }
        Y.parent = zp;
        // Swap the colors
        uint c = Y.color;
        Y.color = Z.color;
        Z.color = c;
        y = z;
    } else {
        /*
                p          p            p          p
               /          /              \          \
              z    -->   x                z  -->     x
              |                           |
              x                           x
         */
        p = Z.parent;
        if (x)
            X.parent = p;
        if (!p) {
            Q_ASSERT(head->root == z);
            head->root = x;
        } else if (P.left == z) {
            P.left = x;
            P.size_left -= Z.size;
        } else {
            P.right = x;
        }
    }
    uint n = z;
    while (N.parent) {
        uint p = N.parent;
        if (P.left == n) {
            PMDEBUG("reducing size_left of %d by %d", N.parent, Z.size);
            P.size_left -= Z.size;
        }
        n = p;
    }

    freeFragment(z);
    PMDEBUG("after removal");
    inorder();
    check();


    if (Y.color != Red) {
        while (X.parent && (x == 0 || X.color == Black)) {
            if (x == P.left) {
                uint w = P.right;
                if (W.color == Red) {
                    W.color = Black;
                    P.color = Red;
                    rotateLeft(p);
                    w = P.right;
                }
                if ((W.left == 0 || F(W.left).color == Black) &&
                    (W.right == 0 || F(W.right).color == Black)) {
                    W.color = Red;
                    x = p;
                    p = X.parent;
                } else {
                    if (W.right == 0 || F(W.right).color == Black) {
                        if (W.left)
                            F(W.left).color = Black;
                        W.color = Red;
                        rotateRight(P.right);
                        w = P.right;
                    }
                    W.color = P.color;
                    P.color = Black;
                    if (W.right)
                        F(W.right).color = Black;
                    rotateLeft(p);
                    break;
                }
            } else {
                uint w = P.left;
                if (W.color == Red) {
                    W.color = Black;
                    P.color = Red;
                    rotateRight(p);
                    w = P.left;
                }
                if ((W.right == 0 || F(W.right).color == Black) &&
                    (W.left == 0 || F(W.left).color == Black)) {
                    W.color = Red;
                    x = p;
                    p = X.parent;
                } else {
                    if (W.left == 0 || F(W.left).color == Black) {
                        if (W.right)
                            F(W.right).color = Black;
                        W.color = Red;
                        rotateLeft(P.left);
                        w = P.left;
                    }
                    W.color = P.color;
                    P.color = Black;
                    if (W.left)
                        F(W.left).color = Black;
                    rotateRight(p);
                    break;
                }
            }
        }
        if (x)
            X.color = Black;
    }

    PMDEBUG("after rebalance");
    inorder();
    check();

    return w;
}

uint QFragmentMapData::findNode(int k) const
{
    uint x = root();

    uint s = k;
    while (x) {
        if (sizeLeft(x) <= s) {
            if (s < sizeLeft(x) + size(x))
                return x;
            s -= sizeLeft(x) + size(x);
            x = X.right;
        } else {
            x = X.left;
        }
    }
    return 0;
}

uint QFragmentMapData::insert_single(int key, uint length)
{
    Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key);

    uint z = createFragment();

    Z.size = length;
    Z.left = 0;
    Z.right = 0;
    Z.size_left = 0;

    PMDEBUG("inserting with key %d", key);
    uint y = 0;
    uint x = root();

    Q_ASSERT(!x || X.parent == 0);

    uint s = key;
//     inorder();
    bool right = false;
    while (x) {
        y = x;
//          PMDEBUG("x=%p: x->size_left=%d, key=%d, s=%d", x, x->size_left, x->key(), s);
        if (s <= X.size_left) {
            x = X.left;
            right = false;
        } else {
            s -= X.size_left + X.size;
            x = X.right;
            right = true;
        }
    }
//     if (y)
//         PMDEBUG("  y=%p: y->size_left=%d, y->key=%d s=%d", y, y->size_left, y ? y->key() : -1, s);

    Z.parent = y;
    if (!y) {
        head->root = z;
    } else if (!right) {
//          PMDEBUG("inserting left");
        Y.left = z;
        Y.size_left = Z.size;
    } else {
//          PMDEBUG("inserting right");
        Y.right = z;
    }
    while (y && Y.parent) {
        uint p = Y.parent;
        if (P.left == y)
            P.size_left += Z.size;
        y = p;
    }
//     PMDEBUG("before rebalance");
//     inorder();
    rebalance(z);

    inorder();
    PMDEBUG("end insert\n");

    return z;
}


int QFragmentMapData::length() const {
    uint root = this->root();
    return root ? sizeLeft(root) + size(root) + sizeRight(root) : 0;
}