QFragmentMapData< Fragment > Class Template Reference

#include <qfragmentmap_p.h>

Classes
class	Header

Public Types
enum	{ fragmentSize = sizeof(Fragment) }

Public Functions
uint	erase_single (uint f)
Fragment &	F (uint index)
const Fragment &	F (uint index) const
uint	findNode (int k, uint field=0) const
Fragment *	fragment (uint index)
const Fragment *	fragment (uint index) const
void	init ()
uint	insert_single (int key, uint length)
bool	isRoot (uint index) const
bool	isValid (uint n) const
int	length (uint field=0) const
uint	maximum (uint n) const
uint	minimum (uint n) const
uint	next (uint n) const
uint	position (uint node, uint field=0) const
uint	previous (uint n) const
	QFragmentMapData ()
uint	root () const
void	setRoot (uint new_root)
void	setSize (uint node, int new_size, uint field=0)
uint	size (uint node, uint field=0) const
uint	sizeLeft (uint node, uint field=0) const
uint	sizeRight (uint node, uint field=0) const
	~QFragmentMapData ()

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

Private Types
enum	Color { Red, Black }

Private Functions
uint	createFragment ()
void	freeFragment (uint f)
void	rebalance (uint x)
void	removeAndRebalance (uint z)
void	rotateLeft (uint x)
void	rotateRight (uint x)

Detailed Description

template<class Fragment>
class QFragmentMapData< Fragment >

Definition at line 77 of file qfragmentmap_p.h.

Enumerations

anonymous enum

template<class Fragment>

anonymous enum

Enumerator
fragmentSize

Definition at line 97 of file qfragmentmap_p.h.

{fragmentSize = sizeof(Fragment) };

Color

template<class Fragment>

enum QFragmentMapData::Color

private

Enumerator
Red
Black

Definition at line 79 of file qfragmentmap_p.h.

{ Red, Black };

Constructors and Destructors

QFragmentMapData()

template<class Fragment >

QFragmentMapData< Fragment >::QFragmentMapData

(

)

Definition at line 220 of file qfragmentmap_p.h.

    : fragments(0)
{
    init();
}

~QFragmentMapData()

template<class Fragment >

QFragmentMapData< Fragment >::~QFragmentMapData

(

)

Definition at line 247 of file qfragmentmap_p.h.

{
    free(fragments);
}

Functions

createFragment()

template<class Fragment >

uint QFragmentMapData< Fragment >::createFragment ( )

private

Definition at line 253 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::insert_single().

{
    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);
        Fragment *newFragments = (Fragment *)realloc(fragments, needed);
        Q_CHECK_PTR(newFragments);
        fragments = newFragments;
        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;
}

erase_single()

template<class Fragment >

uint QFragmentMapData< Fragment >::erase_single

(

uint

f

)

Definition at line 461 of file qfragmentmap_p.h.

{
    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;
                    rotateRight(p);
                    w = F(p).left;
                }
                if ((F(w).right == 0 || F(F(w).right).color == Black) &&
                    (F(w).left == 0 || F(F(w).left).color == Black)) {
                    F(w).color = Red;
                    x = p;
                    p = F(x).parent;
                } else {
                    if (F(w).left == 0 || F(F(w).left).color == Black) {
                        if (F(w).right)
                            F(F(w).right).color = Black;
                        F(w).color = Red;
                        rotateLeft(F(p).left);
                        w = F(p).left;
                    }
                    F(w).color = F(p).color;
                    F(p).color = Black;
                    if (F(w).left)
                        F(F(w).left).color = Black;
                    rotateRight(p);
                    break;
                }
            }
        }
        if (x)
            F(x).color = Black;
    }

    return w;
}

F() [1/2]

template<class Fragment>

Fragment& QFragmentMapData< Fragment >::F ( uint  index )

inline

Definition at line 111 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::createFragment(), QFragmentMapData< QTextBlockData >::erase_single(), QFragmentMapData< QTextBlockData >::findNode(), QFragmentMapData< QTextBlockData >::freeFragment(), QFragmentMapData< QTextBlockData >::init(), QFragmentMapData< QTextBlockData >::insert_single(), QFragmentMapData< QTextBlockData >::next(), QFragmentMapData< QTextBlockData >::previous(), QFragmentMapData< QTextBlockData >::rebalance(), QFragmentMapData< QTextBlockData >::rotateLeft(), and QFragmentMapData< QTextBlockData >::rotateRight().

{ return fragments[index] ; }

F() [2/2]

template<class Fragment>

const Fragment& QFragmentMapData< Fragment >::F ( uint  index ) const

inline

Definition at line 112 of file qfragmentmap_p.h.

{ return fragments[index] ; }

findNode()

template<class Fragment >

uint QFragmentMapData< Fragment >::findNode	(	int	k,
		uint	field = 0
	)		const

Definition at line 638 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::insert_single().

{
    Q_ASSERT(field < Fragment::size_array_max);
    uint x = root();

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

fragment() [1/2]

template<class Fragment>

Fragment* QFragmentMapData< Fragment >::fragment ( uint  index )

inline

Definition at line 103 of file qfragmentmap_p.h.

Referenced by QFragmentMap< QTextBlockData >::erase_single(), QFragmentMap< QTextBlockData >::insert_single(), and QFragmentMap< QTextBlockData >::setSize().

                                          {
        return (fragments + index);
    }

fragment() [2/2]

template<class Fragment>

const Fragment* QFragmentMapData< Fragment >::fragment ( uint  index ) const

inline

Definition at line 106 of file qfragmentmap_p.h.

                                                      {
        return (fragments + index);
    }

freeFragment()

template<class Fragment >

void QFragmentMapData< Fragment >::freeFragment ( uint  f )

private

Definition at line 284 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::erase_single().

{
    F(i).right = head->freelist;
    head->freelist = i;

    --head->node_count;
}

init()

template<class Fragment >

void QFragmentMapData< Fragment >::init

(

)

Definition at line 227 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::QFragmentMapData().

{
    // the following code will realloc an existing fragment or create a new one.
    // it will also ignore errors when shrinking an existing fragment.
    Fragment *newFragments = (Fragment *)realloc(fragments, 64*fragmentSize);
    if (newFragments) {
        fragments = newFragments;
        head->allocated = 64;
    }
    Q_CHECK_PTR(fragments);

    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;
    // mark all items to the right as unused
    F(head->freelist).right = 0;
}

insert_single()

template<class Fragment >

uint QFragmentMapData< Fragment >::insert_single	(	int	key,
		uint	length
	)

Definition at line 658 of file qfragmentmap_p.h.

{
    Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key);

    uint z = createFragment();

    F(z).left = 0;
    F(z).right = 0;
    F(z).size_array[0] = length;
    for (uint field = 1; field < Fragment::size_array_max; ++field)
        F(z).size_array[field] = 1;
    for (uint field = 0; field < Fragment::size_array_max; ++field)
        F(z).size_left_array[field] = 0;

    uint y = 0;
    uint x = root();

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

    uint s = key;
    bool right = false;
    while (x) {
        y = x;
        if (s <= F(x).size_left_array[0]) {
            x = F(x).left;
            right = false;
        } else {
            s -= F(x).size_left_array[0] + F(x).size_array[0];
            x = F(x).right;
            right = true;
        }
    }

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

    return z;
}

isRoot()

template<class Fragment>

bool QFragmentMapData< Fragment >::isRoot ( uint  index ) const

inline

Definition at line 114 of file qfragmentmap_p.h.

                                         {
        return !fragment(index)->parent;
    }

isValid()

template<class Fragment>

bool QFragmentMapData< Fragment >::isValid ( uint  n ) const

inline

Definition at line 198 of file qfragmentmap_p.h.

                                      {
        return n > 0 && n != head->freelist;
    }

length()

template<class Fragment >

int QFragmentMapData< Fragment >::length

(

uint

field = 0

)

const

Definition at line 716 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::insert_single().

                                                       {
    uint root = this->root();
    return root ? sizeLeft(root, field) + size(root, field) + sizeRight(root, field) : 0;
}

maximum()

template<class Fragment>

uint QFragmentMapData< Fragment >::maximum ( uint  n ) const

inline

Definition at line 180 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::previous().

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

minimum()

template<class Fragment>

uint QFragmentMapData< Fragment >::minimum ( uint  n ) const

inline

Definition at line 174 of file qfragmentmap_p.h.

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

next()

template<class Fragment >

uint QFragmentMapData< Fragment >::next

(

uint

n

)

const

Definition at line 294 of file qfragmentmap_p.h.

                                                  {
    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;
}

position()

template<class Fragment>

uint QFragmentMapData< Fragment >::position ( uint  node, uint  field = 0  ) const

inline

Definition at line 118 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::insert_single(), QFragmentMap< Fragment >::Iterator::operator<(), and QFragmentMap< Fragment >::ConstIterator::operator<().

                                                          {
        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;
    }

previous()

template<class Fragment >

uint QFragmentMapData< Fragment >::previous

(

uint

n

)

const

Definition at line 312 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::erase_single().

                                                      {
    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;
}

rebalance()

template<class Fragment >

void QFragmentMapData< Fragment >::rebalance ( uint  x )

private

Definition at line 406 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::insert_single().

{
    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;
}

removeAndRebalance()

template<class Fragment>

void QFragmentMapData< Fragment >::removeAndRebalance ( uint  z )

private

root()

template<class Fragment>

uint QFragmentMapData< Fragment >::root ( ) const

inline

Definition at line 189 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::findNode(), QFragmentMapData< QTextBlockData >::insert_single(), QFragmentMapData< QTextBlockData >::length(), QFragmentMapData< QTextBlockData >::previous(), and QFragmentMapData< QTextBlockData >::rebalance().

                             {
        Q_ASSERT(!head->root || !fragment(head->root)->parent);
        return head->root;
    }

rotateLeft()

template<class Fragment >

void QFragmentMapData< Fragment >::rotateLeft ( uint  x )

private

Definition at line 340 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::erase_single(), and QFragmentMapData< QTextBlockData >::rebalance().

{
    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];
}

rotateRight()

template<class Fragment >

void QFragmentMapData< Fragment >::rotateRight ( uint  x )

private

Definition at line 377 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::erase_single(), and QFragmentMapData< QTextBlockData >::rebalance().

{
    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];
}

setRoot()

template<class Fragment>

void QFragmentMapData< Fragment >::setRoot ( uint  new_root )

inline

Definition at line 193 of file qfragmentmap_p.h.

                                       {
        Q_ASSERT(!head->root || !fragment(new_root)->parent);
        head->root = new_root;
    }

setSize()

template<class Fragment>

void QFragmentMapData< Fragment >::setSize ( uint  node, int  new_size, uint  field = 0  )

inline

Definition at line 154 of file qfragmentmap_p.h.

                                                                 {
        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;
        }
    }

size()

template<class Fragment>

uint QFragmentMapData< Fragment >::size ( uint  node, uint  field = 0  ) const

inline

Definition at line 149 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::findNode(), and QFragmentMapData< QTextBlockData >::length().

                                                      {
        Q_ASSERT(field < Fragment::size_array_max);
        return fragment(node)->size_array[field];
    }

sizeLeft()

template<class Fragment>

uint QFragmentMapData< Fragment >::sizeLeft ( uint  node, uint  field = 0  ) const

inline

Definition at line 143 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::findNode(), and QFragmentMapData< QTextBlockData >::length().

                                                          {
        Q_ASSERT(field < Fragment::size_array_max);
        return fragment(node)->size_left_array[field];
    }

sizeRight()

template<class Fragment>

uint QFragmentMapData< Fragment >::sizeRight ( uint  node, uint  field = 0  ) const

inline

Definition at line 131 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::length().

                                                           {
        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;
    }

Properties

@281

union { ... }

fragments

template<class Fragment>

Fragment* QFragmentMapData< Fragment >::fragments

Definition at line 204 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::createFragment(), QFragmentMapData< QTextBlockData >::init(), and QFragmentMapData< QTextBlockData >::~QFragmentMapData().

head

template<class Fragment>

Header* QFragmentMapData< Fragment >::head

Definition at line 203 of file qfragmentmap_p.h.

Referenced by QFragmentMapData< QTextBlockData >::createFragment(), QFragmentMapData< QTextBlockData >::erase_single(), QFragmentMapData< QTextBlockData >::freeFragment(), QFragmentMapData< QTextBlockData >::init(), QFragmentMapData< QTextBlockData >::insert_single(), QFragmentMapData< QTextBlockData >::rotateLeft(), and QFragmentMapData< QTextBlockData >::rotateRight().

---

The documentation for this class was generated from the following file:

• /src/gui/text/qfragmentmap_p.h