QPatternist::CompressedWhitespace Class Reference

A compression facility for whitespace nodes. More...

#include <qcompressedwhitespace_p.h>

Static Public Functions
static QString	compress (const QStringRef &input)
	Compresses input into a compressed format, returned as a QString. More...
static QString	decompress (const QString &input)
	Decompresses input into a usual QString. More...

Private Types
enum	CharIdentifier { Space = 0x0, CR = 0x80, LF = 0x40, Tab = 0xC0 }
enum	Constants { MaxCharCount = (1 << 6) - 1, Lower8Bits = (1 << 8) - 1, Lower6Bits = (1 << 6) - 1, UpperTwoBits = 3 << 6 }

Private Functions
	CompressedWhitespace ()
	This class can only be used via its static members. More...

Static Private Functions
static bool	isEven (const int number)
	Returns true if number is an even number, otherwise false. More...
static QChar	toChar (const CharIdentifier id)
static quint8	toCompressedChar (const QChar ch, const int len)
static CharIdentifier	toIdentifier (const QChar ch)

Detailed Description

A compression facility for whitespace nodes.

CompressedWhitespace compresses and decompresses strings that consists of whitespace only, and do so with a scheme that is designed to do this specialized task in an efficient way. The approach is simple: each sequence of equal whitespace in the input gets coded into one byte, where the first two bits signals the type, CharIdentifier, and the remininding six bits is the count.

For instance, this scheme manages to compress a sequence of spaces followed by a new line into 16 bits(one QChar), and QString stores strings of one QChar quite efficiently, by avoiding a heap allocation.

There is no way to tell whether a QString is compressed or not.

The compression scheme originates from Saxon, by Michael Kay.

Author

Frans Englich frans.nosp@m..eng.nosp@m.lich@.nosp@m.noki.nosp@m.a.com

Definition at line 87 of file qcompressedwhitespace_p.h.

Enumerations

CharIdentifier

enum QPatternist::CompressedWhitespace::CharIdentifier

private

We use the two upper bits for communicating what space it is.

Enumerator
Space
CR	0xA, \r Binary: 10000000
LF	0xD, \n Binary: 01000000
Tab	Binary: 11000000

Definition at line 117 of file qcompressedwhitespace_p.h.

            {
                Space   = 0x0,

                CR      = 0x80,

                LF      = 0x40,

                Tab     = 0xC0
            };

Constants

enum QPatternist::CompressedWhitespace::Constants

private

Enumerator
MaxCharCount
Lower8Bits	Binary: 11111111
Lower6Bits	Binary: 111111
UpperTwoBits

Definition at line 141 of file qcompressedwhitespace_p.h.

            {
                /* We can at maximum store this many consecutive characters
                 * of one type. We use 6 bits for the count. */
                MaxCharCount = (1 << 6) - 1,

                Lower8Bits = (1 << 8) - 1,

                Lower6Bits = (1 << 6) - 1,

                /*
                 * Binary: 11000000
                 */
                UpperTwoBits = 3 << 6
            };

Constructors and Destructors

CompressedWhitespace()

QPatternist::CompressedWhitespace::CompressedWhitespace ( )

inlineprivate

This class can only be used via its static members.

Functions

compress()

QString CompressedWhitespace::compress ( const QStringRef &  input )

static

Compresses input into a compressed format, returned as a QString.

The caller guarantees that input is not empty and consists only of whitespace.

The returned format is opaque. There is no way to find out whether a QString contains compressed data or not.

See also

decompress()

Definition at line 101 of file qcompressedwhitespace.cpp.

{
    Q_ASSERT(!isEven(1) && isEven(0) && isEven(2));
    Q_ASSERT(!input.isEmpty());

    QString result;
    const int len = input.length();

    /* The amount of compressed characters. For instance, if input is
     * four spaces followed by one tab, compressedChars will be 2, and the resulting
     * QString will have a length of 1, two compressedChars stored in one QChar. */
    int compressedChars = 0;

    for(int i = 0; i < len; ++i)
    {
        const QChar c(input.at(i));

        int start = i;

        while(true)
        {
            if(i + 1 == input.length() || input.at(i + 1) != c)
                break;
            else
                ++i;
        }

        /* The length of subsequent whitespace characters in the input. */
        int wsLen = (i - start) + 1;

        /* We might get a sequence of whitespace that is so long, that we can't
         * store it in one unit/byte. In that case we chop it into as many subsequent
         * ones that is needed. */
        while(true)
        {
            const int unitLength = qMin(wsLen, int(MaxCharCount));
            wsLen -= unitLength;

            ushort resultCP = toCompressedChar(c, unitLength);

            if(isEven(compressedChars))
                result += QChar(resultCP);
            else
            {
                resultCP = resultCP << 8;
                resultCP |= result.at(result.size() - 1).unicode();
                result[result.size() - 1] = resultCP;
            }

            ++compressedChars;

            if(wsLen == 0)
                break;
        }
    }

    return result;
}

decompress()

QString CompressedWhitespace::decompress ( const QString &  input )

static

Decompresses input into a usual QString.

input must be a QString as per returned from compress().

See also

compress()

Definition at line 160 of file qcompressedwhitespace.cpp.

Referenced by QPatternist::AccelTree::printStats(), and QPatternist::AccelTree::stringValue().

{
    Q_ASSERT(!input.isEmpty());
    const int len = input.length() * 2;
    QString retval;

    for(int i = 0; i < len; ++i)
    {
        ushort cp = input.at(i / 2).unicode();

        if(isEven(i))
            cp &= Lower8Bits;
        else
        {
            cp = cp >> 8;

            if(cp == 0)
                return retval;
        }

        const quint8 wsLen = cp & Lower6Bits;
        const quint8 id = cp & UpperTwoBits;

        /* Resize retval, and fill in on the top. */
        const int oldSize = retval.size();
        const int newSize = retval.size() + wsLen;
        retval.resize(newSize);
        const QChar ch(toChar(CharIdentifier(id)));

        for(int f = oldSize; f < newSize; ++f)
            retval[f] = ch;
    }

    return retval;
}

isEven()

bool CompressedWhitespace::isEven ( const int  number )

inlinestaticprivate

Returns true if number is an even number, otherwise false.

Definition at line 71 of file qcompressedwhitespace.cpp.

Referenced by compress(), and decompress().

{
    Q_ASSERT(number >= 0);
    return number % 2 == 0;
}

toChar()

QChar CompressedWhitespace::toChar ( const CharIdentifier  id )

inlinestaticprivate

Definition at line 85 of file qcompressedwhitespace.cpp.

Referenced by decompress().

{
    switch(id)
    {
        case Space: return QLatin1Char(' ');
        case CR:    return QLatin1Char('\r');
        case LF:    return QLatin1Char('\n');
        case Tab:   return QLatin1Char('\t');
        default:
                    {
                        Q_ASSERT_X(false, Q_FUNC_INFO, "Unexpected input");
                        return QChar();
                    }
    }
}

toCompressedChar()

quint8 CompressedWhitespace::toCompressedChar ( const QChar  ch, const int  len  )

inlinestaticprivate

Definition at line 77 of file qcompressedwhitespace.cpp.

Referenced by compress().

{
    Q_ASSERT(len > 0);
    Q_ASSERT(len <= MaxCharCount);

    return len + toIdentifier(ch);
}

toIdentifier()

CompressedWhitespace::CharIdentifier CompressedWhitespace::toIdentifier ( const QChar  ch )

inlinestaticprivate

Definition at line 50 of file qcompressedwhitespace.cpp.

Referenced by toCompressedChar().

{
    switch(ch.unicode())
    {
        case ' ':
            return Space;
        case '\n':
            return LF;
        case '\r':
            return CR;
        case '\t':
            return Tab;
        default:
        {
            Q_ASSERT_X(false, Q_FUNC_INFO,
                       "The caller must guarantee only whitespace is passed.");
            return Tab;
        }
    }
}

---

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

• /src/xmlpatterns/acceltree/qcompressedwhitespace_p.h
• /src/xmlpatterns/acceltree/qcompressedwhitespace.cpp