/****************************************************************************

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtCore module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** 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.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qstringlist.h"

#include "qregexp.h"

#include "qunicodetables_p.h"

#ifndef QT_NO_TEXTCODEC

#include <qtextcodec.h>

#endif

#include <private/qutfcodec_p.h>

#include "qsimd_p.h"

#include <qdatastream.h>

#include <qlist.h>

#include "qlocale.h"

#include "qlocale_p.h"

#include "qstringmatcher.h"

#include "qvarlengtharray.h"

#include "qtools_p.h"

#include "qhash.h"

#include "qdebug.h"

#include "qendian.h"

#ifdef Q_OS_MAC

#include <private/qcore_mac_p.h>

#endif

#include <private/qfunctions_p.h>

#if defined(Q_OS_WINCE)

#include <windows.h>

#include <winnls.h>

#endif

#ifdef Q_OS_SYMBIAN

#include <e32cmn.h>

#endif

#include <limits.h>

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#include <stdarg.h>

#ifdef truncate

#undef truncate

#endif

#include "qchar.cpp"

#include "qstringmatcher.cpp"

#ifndef LLONG_MAX

#define LLONG_MAX qint64_C(9223372036854775807)

#endif

#ifndef LLONG_MIN

#define LLONG_MIN (-LLONG_MAX - qint64_C(1))

#endif

#ifndef ULLONG_MAX

#define ULLONG_MAX quint64_C(18446744073709551615)

#endif

QT_BEGIN_NAMESPACE

#ifndef QT_NO_TEXTCODEC

QTextCodec *QString::codecForCStrings;

#endif

#ifdef QT3_SUPPORT

static QHash<void *, QByteArray> *asciiCache = 0;

#endif

// internal

int qFindString(const QChar *haystack, int haystackLen, int from,

    const QChar *needle, int needleLen, Qt::CaseSensitivity cs);

int qFindStringBoyerMoore(const QChar *haystack, int haystackLen, int from,

    const QChar *needle, int needleLen, Qt::CaseSensitivity cs);

// Unicode case-insensitive comparison

static int ucstricmp(const ushort *a, const ushort *ae, const ushort *b, const ushort *be)

{

    if (a == b)

        return (ae - be);

    if (a == 0)

        return 1;

    if (b == 0)

        return -1;

    const ushort *e = ae;

    if (be - b < ae - a)

        e = a + (be - b);

    uint alast = 0;

    uint blast = 0;

    while (a < e) {

//         qDebug() << hex << alast << blast;

//         qDebug() << hex << "*a=" << *a << "alast=" << alast << "folded=" << foldCase (*a, alast);

//         qDebug() << hex << "*b=" << *b << "blast=" << blast << "folded=" << foldCase (*b, blast);

        int diff = foldCase(*a, alast) - foldCase(*b, blast);

        if ((diff))

            return diff;

        ++a;

        ++b;

    }

    if (a == ae) {

        if (b == be)

            return 0;

        return -1;

    }

    return 1;

}

// Case-insensitive comparison between a Unicode string and a QLatin1String

static int ucstricmp(const ushort *a, const ushort *ae, const uchar *b)

{

    if (a == 0) {

        if (b == 0)

            return 0;

        return 1;

    }

    if (b == 0)

        return -1;

    while (a < ae && *b) {

        int diff = foldCase(*a) - foldCase(*b);

        if ((diff))

            return diff;

        ++a;

        ++b;

    }

    if (a == ae) {

        if (!*b)

            return 0;

        return -1;

    }

    return 1;

}

// Unicode case-insensitive comparison

static int ucstrcmp(const QChar *a, int alen, const QChar *b, int blen)

{

    if (a == b && alen == blen)

        return 0;

    int l = qMin(alen, blen);

    while (l-- && *a == *b)

        a++,b++;

    if (l == -1)

        return (alen-blen);

    return a->unicode() - b->unicode();

}

// Unicode case-sensitive compare two same-sized strings

static int ucstrncmp(const QChar *a, const QChar *b, int l)

{

    while (l-- && *a == *b)

        a++,b++;

    if (l==-1)

        return 0;

    return a->unicode() - b->unicode();

}

// Unicode case-insensitive compare two same-sized strings

static int ucstrnicmp(const ushort *a, const ushort *b, int l)

{

    return ucstricmp(a, a + l, b, b + l);

}

static bool qMemEquals(const quint16 *a, const quint16 *b, int length)

{

    // Benchmarking indicates that doing memcmp is much slower than

    // executing the comparison ourselves.

    // To make it even faster, we do a 32-bit comparison, comparing

    // twice the amount of data as a normal word-by-word comparison.

    //

    // Benchmarking results on a 2.33 GHz Core2 Duo, with a 64-QChar

    // block of data, with 4194304 iterations (per iteration):

    //    operation             usec            cpu ticks

    //     memcmp                330               710

    //     16-bit                 79             167-171

    //  32-bit aligned            49             105-109

    //

    // Testing also indicates that unaligned 32-bit loads are as

    // performant as 32-bit aligned.

    if (a == b || !length)

        return true;

    register union {

        const quint16 *w;

        const quint32 *d;

        quintptr value;

    } sa, sb;

    sa.w = a;

    sb.w = b;

    // check alignment

    if ((sa.value & 2) == (sb.value & 2)) {

        // both addresses have the same alignment

        if (sa.value & 2) {

            // both addresses are not aligned to 4-bytes boundaries

            // compare the first character

            if (*sa.w != *sb.w)

                return false;

            --length;

            ++sa.w;

            ++sb.w;

            // now both addresses are 4-bytes aligned

        }

        // both addresses are 4-bytes aligned

        // do a fast 32-bit comparison

        register const quint32 *e = sa.d + (length >> 1);

        for ( ; sa.d != e; ++sa.d, ++sb.d) {

            if (*sa.d != *sb.d)

                return false;

        }

        // do we have a tail?

        return (length & 1) ? *sa.w == *sb.w : true;

    } else {

        // one of the addresses isn't 4-byte aligned but the other is

        register const quint16 *e = sa.w + length;

        for ( ; sa.w != e; ++sa.w, ++sb.w) {

            if (*sa.w != *sb.w)

                return false;

        }

    }

    return true;

}

/*!

    \internal

    Returns the index position of the first occurrence of the

    character \a ch in the string given by \a str and \a len,

    searching forward from index

    position \a from. Returns -1 if \a ch could not be found.

*/

static int findChar(const QChar *str, int len, QChar ch, int from,

    Qt::CaseSensitivity cs)

{

    const ushort *s = (const ushort *)str;

    ushort c = ch.unicode();

    if (from < 0)

        from = qMax(from + len, 0);

    if (from < len) {

        const ushort *n = s + from - 1;

        const ushort *e = s + len;

        if (cs == Qt::CaseSensitive) {

            while (++n != e)

                if (*n == c)

                    return  n - s;

        } else {

            c = foldCase(c);

            while (++n != e)

                if (foldCase(*n) == c)

                    return  n - s;

        }

    }

    return -1;

}

#define REHASH(a) \

    if (sl_minus_1 < (int)sizeof(int) * CHAR_BIT)       \

        hashHaystack -= (a) << sl_minus_1; \

    hashHaystack <<= 1

inline bool qIsUpper(char ch)

{

    return ch >= 'A' && ch <= 'Z';

}

inline bool qIsDigit(char ch)

{

    return ch >= '0' && ch <= '9';

}

inline char qToLower(char ch)

{

    if (ch >= 'A' && ch <= 'Z')

        return ch - 'A' + 'a';

    else

        return ch;

}

#if defined(Q_CC_MSVC) && _MSC_VER <= 1300

const QString::Null QString::null;

#else

const QString::Null QString::null = { };

#endif

/*!

  \macro QT_NO_CAST_FROM_ASCII

  \relates QString

  Disables automatic conversions from 8-bit strings (char *) to unicode QStrings

  \sa QT_NO_CAST_TO_ASCII, QT_NO_CAST_FROM_BYTEARRAY

*/

/*!

  \macro QT_NO_CAST_TO_ASCII

  \relates QString

  disables automatic conversion from QString to 8-bit strings (char *)

  \sa QT_NO_CAST_FROM_ASCII, QT_NO_CAST_FROM_BYTEARRAY

*/

/*!

  \macro QT_ASCII_CAST_WARNINGS

  \internal

  \relates QString

  This macro can be defined to force a warning whenever a function is

  called that automatically converts between unicode and 8-bit encodings.

  Note: This only works for compilers that support warnings for

  deprecated API.

  \sa QT_NO_CAST_TO_ASCII, QT_NO_CAST_FROM_ASCII

*/

/*!

    \class QCharRef

    \reentrant

    \brief The QCharRef class is a helper class for QString.

    \internal

    \ingroup string-processing

    When you get an object of type QCharRef, if you can assign to it,

    the assignment will apply to the character in the string from

    which you got the reference. That is its whole purpose in life.

    The QCharRef becomes invalid once modifications are made to the

    string: if you want to keep the character, copy it into a QChar.

    Most of the QChar member functions also exist in QCharRef.

    However, they are not explicitly documented here.

    \sa QString::operator[]() QString::at() QChar

*/

/*!

    \class QString

    \reentrant

    \brief The QString class provides a Unicode character string.

    \ingroup tools

    \ingroup shared

    \ingroup string-processing

    QString stores a string of 16-bit \l{QChar}s, where each QChar

    corresponds one Unicode 4.0 character. (Unicode characters

    with code values above 65535 are stored using surrogate pairs,

    i.e., two consecutive \l{QChar}s.)

    \l{Unicode} is an international standard that supports most of the

    writing systems in use today. It is a superset of US-ASCII (ANSI

    X3.4-1986) and Latin-1 (ISO 8859-1), and all the US-ASCII/Latin-1

    characters are available at the same code positions.

    Behind the scenes, QString uses \l{implicit sharing}

    (copy-on-write) to reduce memory usage and to avoid the needless

    copying of data. This also helps reduce the inherent overhead of

    storing 16-bit characters instead of 8-bit characters.

    In addition to QString, Qt also provides the QByteArray class to

    store raw bytes and traditional 8-bit '\\0'-terminated strings.

    For most purposes, QString is the class you want to use. It is

    used throughout the Qt API, and the Unicode support ensures that

    your applications will be easy to translate if you want to expand

    your application's market at some point. The two main cases where

    QByteArray is appropriate are when you need to store raw binary

    data, and when memory conservation is critical (e.g., with

    \l{Qt for Embedded Linux}).

    \tableofcontents

    \section1 Initializing a String

    One way to initialize a QString is simply to pass a \c{const char

    *} to its constructor. For example, the following code creates a

    QString of size 5 containing the data "Hello":

    \snippet doc/src/snippets/qstring/main.cpp 0

    QString converts the \c{const char *} data into Unicode using the

    fromAscii() function. By default, fromAscii() treats character

    above 128 as Latin-1 characters, but this can be changed by

    calling QTextCodec::setCodecForCStrings().

    In all of the QString functions that take \c{const char *}

    parameters, the \c{const char *} is interpreted as a classic

    C-style '\\0'-terminated string. It is legal for the \c{const char

    *} parameter to be 0.

    You can also provide string data as an array of \l{QChar}s:

    \snippet doc/src/snippets/qstring/main.cpp 1

    QString makes a deep copy of the QChar data, so you can modify it

    later without experiencing side effects. (If for performance

    reasons you don't want to take a deep copy of the character data,

    use QString::fromRawData() instead.)

    Another approach is to set the size of the string using resize()

    and to initialize the data character per character. QString uses

    0-based indexes, just like C++ arrays. To access the character at

    a particular index position, you can use \l operator[](). On

    non-const strings, \l operator[]() returns a reference to a

    character that can be used on the left side of an assignment. For

    example:

    \snippet doc/src/snippets/qstring/main.cpp 2

    For read-only access, an alternative syntax is to use the at()

    function:

    \snippet doc/src/snippets/qstring/main.cpp 3

    The at() function can be faster than \l operator[](), because it

    never causes a \l{deep copy} to occur. Alternatively, use the

    left(), right(), or mid() functions to extract several characters

    at a time.

    A QString can embed '\\0' characters (QChar::Null). The size()

    function always returns the size of the whole string, including

    embedded '\\0' characters.

    After a call to the resize() function, newly allocated characters

    have undefined values. To set all the characters in the string to

    a particular value, use the fill() function.

    QString provides dozens of overloads designed to simplify string

    usage. For example, if you want to compare a QString with a string

    literal, you can write code like this and it will work as expected:

    \snippet doc/src/snippets/qstring/main.cpp 4

    You can also pass string literals to functions that take QStrings

    as arguments, invoking the QString(const char *)

    constructor. Similarly, you can pass a QString to a function that

    takes a \c{const char *} argument using the \l qPrintable() macro

    which returns the given QString as a \c{const char *}. This is

    equivalent to calling <QString>.toLocal8Bit().constData().

    \section1 Manipulating String Data

    QString provides the following basic functions for modifying the

    character data: append(), prepend(), insert(), replace(), and

    remove(). For example:

    \snippet doc/src/snippets/qstring/main.cpp 5

    If you are building a QString gradually and know in advance

    approximately how many characters the QString will contain, you

    can call reserve(), asking QString to preallocate a certain amount

    of memory. You can also call capacity() to find out how much

    memory QString actually allocated.

    The replace() and remove() functions' first two arguments are the

    position from which to start erasing and the number of characters

    that should be erased.  If you want to replace all occurrences of

    a particular substring with another, use one of the two-parameter

    replace() overloads.

    A frequent requirement is to remove whitespace characters from a

    string ('\\n', '\\t', ' ', etc.). If you want to remove whitespace

    from both ends of a QString, use the trimmed() function. If you

    want to remove whitespace from both ends and replace multiple

    consecutive whitespaces with a single space character within the

    string, use simplified().

    If you want to find all occurrences of a particular character or

    substring in a QString, use the indexOf() or lastIndexOf()

    functions. The former searches forward starting from a given index

    position, the latter searches backward. Both return the index

    position of the character or substring if they find it; otherwise,

    they return -1.  For example, here's a typical loop that finds all

    occurrences of a particular substring:

    \snippet doc/src/snippets/qstring/main.cpp 6

    QString provides many functions for converting numbers into

    strings and strings into numbers. See the arg() functions, the