source: trunk/src/gui/text/qfragmentmap_p.h@ 234

/****************************************************************************
**
** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
** Contact: Qt Software Information ([email protected])
**
** This file is part of the QtGui module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial Usage
** Licensees holding valid Qt Commercial licenses may use this file in
** accordance with the Qt Commercial License Agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Nokia.
**
** 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 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.0, 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.
**
** If you are unsure which license is appropriate for your use, please
** contact the sales department at [email protected].
** $QT_END_LICENSE$
**
****************************************************************************/

#ifndef QFRAGMENTMAP_P_H
#define QFRAGMENTMAP_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 "QtCore/qglobal.h"
#include <stdlib.h>
#include <private/qtools_p.h>

QT_BEGIN_NAMESPACE


template <int N = 1>
class QFragment
{
public:
    quint32 parent;
    quint32 left;
    quint32 right;
    quint32 color;
    quint32 size_left_array[N];
    quint32 size_array[N];
    enum {size_array_max = N };
};

template <class Fragment>
class QFragmentMapData
{
    enum Color { Red, Black };
public:
    QFragmentMapData();
    ~QFragmentMapData();

    void init();

    class Header
    {
    public:
        quint32 root; // this relies on being at the same position as parent in the fragment struct
        quint32 tag;
        quint32 freelist;
        quint32 node_count;
        quint32 allocated;
    };


    enum {fragmentSize = sizeof(Fragment) };


    int length(uint field = 0) const;


    inline Fragment *fragment(uint index) {
        return (fragments + index);
    }
    inline const Fragment *fragment(uint index) const {
        return (fragments + index);
    }


    inline Fragment &F(uint index) { return fragments[index] ; }
    inline const Fragment &F(uint index) const { return fragments[index] ; }

    inline bool isRoot(uint index) const {
        return !fragment(index)->parent;
    }

    inline uint position(uint node, uint field = 0) const {
        Q_ASSERT(field < Fragment::size_array_max);
        const Fragment *f = fragment(node);
        uint offset = f->size_left_array[field];
        while (f->parent) {
            uint p = f->parent;
            f = fragment(p);
            if (f->right == node)
                offset += f->size_left_array[field] + f->size_array[field];
            node = p;
        }
        return offset;
    }
    inline uint sizeRight(uint node, uint field = 0) const {
        Q_ASSERT(field < Fragment::size_array_max);
        uint sr = 0;
        const Fragment *f = fragment(node);
        node = f->right;
        while (node) {
            f = fragment(node);
            sr += f->size_left_array[field] + f->size_array[field];
            node = f->right;
        }
        return sr;
    }
    inline uint sizeLeft(uint node, uint field = 0) const {
        Q_ASSERT(field < Fragment::size_array_max);
        return fragment(node)->size_left_array[field];
    }


    inline uint size(uint node, uint field = 0) const {
        Q_ASSERT(field < Fragment::size_array_max);
        return fragment(node)->size_array[field];
    }

    inline void setSize(uint node, int new_size, uint field = 0) {
        Q_ASSERT(field < Fragment::size_array_max);
        Fragment *f = fragment(node);
        int diff = new_size - f->size_array[field];
        f->size_array[field] = new_size;
        while (f->parent) {
            uint p = f->parent;
            f = fragment(p);
            if (f->left == node)
                f->size_left_array[field] += diff;
            node = p;
        }
    }


    uint findNode(int k, uint field = 0) const;

    uint insert_single(int key, uint length);
    uint erase_single(uint f);

    uint minimum(uint n) const {
        while (n && fragment(n)->left)
            n = fragment(n)->left;
        return n;
    }

    uint maximum(uint n) const {
        while (n && fragment(n)->right)
            n = fragment(n)->right;
        return n;
    }

    uint next(uint n) const;
    uint previous(uint n) const;

    inline uint root() const {
        Q_ASSERT(!head->root || !fragment(head->root)->parent);
        return head->root;
    }
    inline void setRoot(uint new_root) {
        Q_ASSERT(!head->root || !fragment(new_root)->parent);
        head->root = new_root;
    }

    union {
        Header *head;
        Fragment *fragments;
    };

private:

    void rotateLeft(uint x);
    void rotateRight(uint x);
    void rebalance(uint x);
    void removeAndRebalance(uint z);

    uint createFragment();
    void freeFragment(uint f);

};

template <class Fragment>
QFragmentMapData<Fragment>::QFragmentMapData()
{
    init();
}

template <class Fragment>
void QFragmentMapData<Fragment>::init()
{
    fragments = (Fragment *)malloc(64*fragmentSize);
    head->tag = (((quint32)'p') << 24) | (((quint32)'m') << 16) | (((quint32)'a') << 8) | 'p'; //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;
}

template <class Fragment>
QFragmentMapData<Fragment>::~QFragmentMapData()
{
    free(head);
}

template <class Fragment>
uint QFragmentMapData<Fragment>::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 = (Fragment *)realloc(fragments, needed);
        head->allocated = needed/fragmentSize;
        F(freePos).right = 0;
    }

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

    head->freelist = nextPos;

    ++head->node_count;

    return freePos;
}

template <class Fragment>
void QFragmentMapData<Fragment>::freeFragment(uint i)
{
    F(i).right = head->freelist;
    head->freelist = i;

    --head->node_count;
}


template <class Fragment>
uint QFragmentMapData<Fragment>::next(uint n) const {
    Q_ASSERT(n);
    if (F(n).right) {
        n = F(n).right;
        while (F(n).left)
            n = F(n).left;
    } else {
        uint y = F(n).parent;
        while (F(n).parent && n == F(y).right) {
            n = y;
            y = F(y).parent;
        }
        n = y;
    }
    return n;
}

template <class Fragment>
uint QFragmentMapData<Fragment>::previous(uint n) const {
    if (!n)
        return maximum(root());

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


/*
     x              y
      \            / \
       y    -->   x   b
      / \          \
     a   b          a
*/
template <class Fragment>
void QFragmentMapData<Fragment>::rotateLeft(uint x)
{
    uint p = F(x).parent;
    uint y = F(x).right;


    if (y) {
        F(x).right = F(y).left;
        if (F(y).left)
            F(F(y).left).parent = x;
        F(y).left = x;
        F(y).parent = p;
    } else {
        F(x).right = 0;
    }
    if (!p) {
        Q_ASSERT(head->root == x);
        head->root = y;
    }
    else if (x == F(p).left)
        F(p).left = y;
    else
        F(p).right = y;
    F(x).parent = y;
    for (uint field = 0; field < Fragment::size_array_max; ++field)
        F(y).size_left_array[field] += F(x).size_left_array[field] + F(x).size_array[field];
}


/*
         x          y
        /          / \
       y    -->   a   x
      / \            /
     a   b          b
*/
template <class Fragment>
void QFragmentMapData<Fragment>::rotateRight(uint x)
{
    uint y = F(x).left;
    uint p = F(x).parent;

    if (y) {
        F(x).left = F(y).right;
        if (F(y).right)
            F(F(y).right).parent = x;
        F(y).right = x;
        F(y).parent = p;
    } else {
        F(x).left = 0;
    }
    if (!p) {
        Q_ASSERT(head->root == x);
        head->root = y;
    }
    else if (x == F(p).right)
        F(p).right = y;
    else
        F(p).left = y;
    F(x).parent = y;
    for (uint field = 0; field < Fragment::size_array_max; ++field)
        F(x).size_left_array[field] -= F(y).size_left_array[field] + F(y).size_array[field];
}


template <class Fragment>
void QFragmentMapData<Fragment>::rebalance(uint x)
{
    F(x).color = Red;

    while (F(x).parent && F(F(x).parent).color == Red) {
        uint p = F(x).parent;
        uint pp = F(p).parent;
        Q_ASSERT(pp);
        if (p == F(pp).left) {
            uint y = F(pp).right;
            if (y && F(y).color == Red) {
                F(p).color = Black;
                F(y).color = Black;
                F(pp).color = Red;
                x = pp;
            } else {
                if (x == F(p).right) {
                    x = p;
                    rotateLeft(x);
                    p = F(x).parent;
                    pp = F(p).parent;
                }
                F(p).color = Black;
                if (pp) {
                    F(pp).color = Red;
                    rotateRight(pp);
                }
            }
        } else {
            uint y = F(pp).left;
            if (y && F(y).color == Red) {
                F(p).color = Black;
                F(y).color = Black;
                F(pp).color = Red;
                x = pp;
            } else {
                if (x == F(p).left) {
                    x = p;
                    rotateRight(x);
                    p = F(x).parent;
                    pp = F(p).parent;
                }
                F(p).color = Black;
                if (pp) {
                    F(pp).color = Red;
                    rotateLeft(pp);
                }
            }
        }
    }
    F(root()).color = Black;
}


template <class Fragment>
uint QFragmentMapData<Fragment>::erase_single(uint z)
{
    uint w = previous(z);
    uint y = z;
    uint x;
    uint p;

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

    if (y != z) {
        F(F(z).left).parent = y;
        F(y).left = F(z).left;
        for (uint field = 0; field < Fragment::size_array_max; ++field)
            F(y).size_left_array[field] = F(z).size_left_array[field];
        if (y != F(z).right) {
            /*
                     z                y
                    / \              / \
                   a   b            a   b
                      /                /
                    ...     -->      ...
                    /                /
                   y                x
                  / \
                 0   x
             */
            p = F(y).parent;
            if (x)
                F(x).parent = p;
            F(p).left = x;
            F(y).right = F(z).right;
            F(F(z).right).parent = y;
            uint n = p;
            while (n != y) {
                for (uint field = 0; field < Fragment::size_array_max; ++field)
                    F(n).size_left_array[field] -= F(y).size_array[field];
                n = F(n).parent;
            }
        } else {
            /*
                     z                y
                    / \              / \
                   a   y     -->    a   x
                      / \
                     0   x
             */
            p = y;
        }
        uint zp = F(z).parent;
        if (!zp) {
            Q_ASSERT(head->root == z);
            head->root = y;
        } else if (F(zp).left == z) {
            F(zp).left = y;
            for (uint field = 0; field < Fragment::size_array_max; ++field)
                F(zp).size_left_array[field] -= F(z).size_array[field];
        } else {
            F(zp).right = y;
        }
        F(y).parent = zp;
        // Swap the colors
        uint c = F(y).color;
        F(y).color = F(z).color;
        F(z).color = c;
        y = z;
    } else {
        /*
                p          p            p          p
               /          /              \          \
              z    -->   x                z  -->     x
              |                           |
              x                           x
         */
        p = F(z).parent;
        if (x)
            F(x).parent = p;
        if (!p) {
            Q_ASSERT(head->root == z);
            head->root = x;
        } else if (F(p).left == z) {
            F(p).left = x;
            for (uint field = 0; field < Fragment::size_array_max; ++field)
                F(p).size_left_array[field] -= F(z).size_array[field];
        } else {
            F(p).right = x;
        }
    }
    uint n = z;
    while (F(n).parent) {
        uint p = F(n).parent;
        if (F(p).left == n) {
            for (uint field = 0; field < Fragment::size_array_max; ++field)
                F(p).size_left_array[field] -= F(z).size_array[field];
        }
        n = p;
    }

    freeFragment(z);


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