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

**

** 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 <new>

#include "qlist.h"

#include "qtools_p.h"

#include <string.h>

QT_BEGIN_NAMESPACE

/*

    QList as an array-list combines the easy-of-use of a random

    access interface with fast list operations and the low memory

    management overhead of an array. Accessing elements by index,

    appending, prepending, and removing elements from both the front

    and the back all happen in constant time O(1). Inserting or

    removing elements at random index positions \ai happens in linear

    time, or more precisly in O(min{i,n-i}) <= O(n/2), with n being

    the number of elements in the list.

*/

QListData::Data QListData::shared_null = { Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, true, { 0 } };

static int grow(int size)

{

    // dear compiler: don't optimize me out.

    volatile int x = qAllocMore(size * sizeof(void *), QListData::DataHeaderSize) / sizeof(void *);

    return x;

}

#if QT_VERSION >= 0x050000

#  error "Remove QListData::detach(), it is only required for binary compatibility for 4.0.x to 4.2.x"

#endif

QListData::Data *QListData::detach()

{

    Data *x = static_cast<Data *>(qMalloc(DataHeaderSize + d->alloc * sizeof(void *)));

    Q_CHECK_PTR(x);

    x->ref = 1;

    x->sharable = true;

    x->alloc = d->alloc;

    if (!x->alloc) {

        x->begin = 0;

        x->end = 0;

    } else {

        x->begin = d->begin;

        x->end   = d->end;

    }

    qSwap(d, x);

    if (!x->ref.deref())

        return x;

    return 0;

}

/*!

 *  Detaches the QListData by reallocating new memory.

 *  Returns the old (shared) data, it is up to the caller to deref() and free()

 *  For the new data node_copy needs to be called.

 *

 *  \internal

 */

#if QT_VERSION >= 0x050000

#  error "Remove QListData::detach2(), it is only required for binary compatibility for 4.3.x to 4.5.x"

#endif

QListData::Data *QListData::detach2()

{

    Data *x = d;

    Data* t = static_cast<Data *>(qMalloc(DataHeaderSize + x->alloc * sizeof(void *)));

    Q_CHECK_PTR(t);

    ::memcpy(t, d, DataHeaderSize + d->alloc * sizeof(void *));

    t->ref = 1;

    t->sharable = true;

    t->alloc = x->alloc;

    if (!t->alloc) {

        t->begin = 0;

        t->end = 0;

    } else {

        t->begin = x->begin;

        t->end   = x->end;

    }

    d = t;

    return x;

}

/*!

 *  Detaches the QListData by reallocating new memory.

 *  Returns the old (shared) data, it is up to the caller to deref() and free()

 *  For the new data node_copy needs to be called.

 *

 *  \internal

 */

QListData::Data *QListData::detach3()

{

    Data *x = d;

    Data* t = static_cast<Data *>(qMalloc(DataHeaderSize + x->alloc * sizeof(void *)));

    Q_CHECK_PTR(t);

    t->ref = 1;

    t->sharable = true;

    t->alloc = x->alloc;

    if (!t->alloc) {

        t->begin = 0;

        t->end = 0;

    } else {

        t->begin = x->begin;

        t->end   = x->end;

    }

    d = t;

    return x;

}

void QListData::realloc(int alloc)

{

    Q_ASSERT(d->ref == 1);

    Data *x = static_cast<Data *>(qRealloc(d, DataHeaderSize + alloc * sizeof(void *)));

    Q_CHECK_PTR(x);

    d = x;

    d->alloc = alloc;

    if (!alloc)

        d->begin = d->end = 0;

}

// ensures that enough space is available to append one element

void **QListData::append()

{

    Q_ASSERT(d->ref == 1);

    if (d->end == d->alloc) {

        int n = d->end - d->begin;

        if (d->begin > 2 * d->alloc / 3) {

            // we have enough space. Just not at the end -> move it.

            ::memcpy(d->array + n, d->array + d->begin, n * sizeof(void *));

            d->begin = n;

            d->end = n * 2;

        } else {

            realloc(grow(d->alloc + 1));

        }

    }

    return d->array + d->end++;

}

// ensures that enough space is available to append the list

#if QT_VERSION >= 0x050000

#  error "Remove QListData::append(), it is only required for binary compatibility up to 4.5.x"

#endif

void **QListData::append(const QListData& l)

{

    Q_ASSERT(d->ref == 1);

    int e = d->end;

    int n = l.d->end - l.d->begin;

    if (n) {

        if (e + n > d->alloc)

            realloc(grow(e + l.d->end - l.d->begin));

        ::memcpy(d->array + d->end, l.d->array + l.d->begin, n*sizeof(void*));

        d->end += n;

    }

    return d->array + e;

}

// ensures that enough space is available to append the list

void **QListData::append2(const QListData& l)

{

    Q_ASSERT(d->ref == 1);

    int e = d->end;

    int n = l.d->end - l.d->begin;

    if (n) {

        if (e + n > d->alloc)

        d->end += n;

    }

    return d->array + e;

}

void **QListData::prepend()

{

    Q_ASSERT(d->ref == 1);

    if (d->begin == 0) {

        if (d->end >= d->alloc / 3)

            realloc(grow(d->alloc + 1));

        if (d->end < d->alloc / 3)

            d->begin = d->alloc - 2 * d->end;

        else

            d->begin = d->alloc - d->end;

        ::memmove(d->array + d->begin, d->array, d->end * sizeof(void *));

        d->end += d->begin;

    }

    return d->array + --d->begin;

}

void **QListData::insert(int i)

{

    Q_ASSERT(d->ref == 1);

    if (i <= 0)

        return prepend();

    if (i >= d->end - d->begin)

        return append();

    bool leftward = false;

    int size = d->end - d->begin;

    if (d->begin == 0) {

        if (d->end == d->alloc) {

            // If the array is full, we expand it and move some items rightward

            realloc(grow(d->alloc + 1));

        } else {

            // If there is free space at the end of the array, we move some items rightward

        }

    } else {

        if (d->end == d->alloc) {

            // If there is free space at the beginning of the array, we move some items leftward

            leftward = true;

        } else {

            // If there is free space at both ends, we move as few items as possible

            leftward = (i < size - i);

        }

    }

    if (leftward) {

        --d->begin;

        ::memmove(d->array + d->begin, d->array + d->begin + 1, i * sizeof(void *));

    } else {

        ::memmove(d->array + d->begin + i + 1, d->array + d->begin + i,

                  (size - i) * sizeof(void *));

        ++d->end;

    }

    return d->array + d->begin + i;

}

void QListData::remove(int i)

{

    Q_ASSERT(d->ref == 1);

    i += d->begin;

    if (i - d->begin < d->end - i) {

        if (int offset = i - d->begin)

            ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));

        d->begin++;

    } else {

        if (int offset = d->end - i - 1)

            ::memmove(d->array + i, d->array + i + 1, offset * sizeof(void *));

        d->end--;

    }

}

void QListData::remove(int i, int n)

{

    Q_ASSERT(d->ref == 1);

    i += d->begin;

    int middle = i + n/2;

    if (middle - d->begin < d->end - middle) {

        ::memmove(d->array + d->begin + n, d->array + d->begin,

                   (i - d->begin) * sizeof(void*));

        d->begin += n;

    } else {

        ::memmove(d->array + i, d->array + i + n,

                   (d->end - i - n) * sizeof(void*));

        d->end -= n;

    }

}

void QListData::move(int from, int to)

{

    Q_ASSERT(d->ref == 1);

    if (from == to)

        return;

    from += d->begin;

    to += d->begin;

    void *t = d->array[from];

    if (from < to) {

        if (d->end == d->alloc || 3 * (to - from) < 2 * (d->end - d->begin)) {

            ::memmove(d->array + from, d->array + from + 1, (to - from) * sizeof(void *));

        } else {

            // optimization

            if (int offset = from - d->begin)

                ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));

            if (int offset = d->end - (to + 1))

                ::memmove(d->array + to + 2, d->array + to + 1, offset * sizeof(void *));

            ++d->begin;

            ++d->end;

            ++to;

        }

    } else {

        if (d->begin == 0 || 3 * (from - to) < 2 * (d->end - d->begin)) {

            ::memmove(d->array + to + 1, d->array + to, (from - to) * sizeof(void *));

        } else {

            // optimization

            if (int offset = to - d->begin)

                ::memmove(d->array + d->begin - 1, d->array + d->begin, offset * sizeof(void *));

            if (int offset = d->end - (from + 1))

                ::memmove(d->array + from, d->array + from + 1, offset * sizeof(void *));

            --d->begin;

            --d->end;

            --to;

        }

    }

    d->array[to] = t;

}

void **QListData::erase(void **xi)

{

    Q_ASSERT(d->ref == 1);

    int i = xi - (d->array + d->begin);

    remove(i);

    return d->array + d->begin + i;

}

/*! \class QList

    \brief The QList class is a template class that provides lists.

    \ingroup tools

    \ingroup shared

    \reentrant

    QList\<T\> is one of Qt's generic \l{container classes}. It

    stores a list of values and provides fast index-based access as

    well as fast insertions and removals.

    QList\<T\>, QLinkedList\<T\>, and QVector\<T\> provide similar

    functionality. Here's an overview:

    \list

    \i For most purposes, QList is the right class to use. Its

       index-based API is more convenient than QLinkedList's

       iterator-based API, and it is usually faster than

       QVector because of the way it stores its items in

       memory. It also expands to less code in your executable.

    \i If you need a real linked list, with guarantees of \l{constant

       time} insertions in the middle of the list and iterators to

       items rather than indexes, use QLinkedList.

    \i If you want the items to occupy adjacent memory positions,

       use QVector.

    \endlist

    Internally, QList\<T\> is represented as an array of pointers to

    items of type T. If T is itself a pointer type or a basic type

    that is no larger than a pointer, or if T is one of Qt's \l{shared

    classes}, then QList\<T\> stores the items directly in the pointer

    array. For lists under a thousand items, this array representation

    allows for very fast insertions in the middle, and it allows

    index-based access. Furthermore, operations like prepend() and

    append() are very fast, because QList preallocates memory at both

    ends of its internal array. (See \l{Algorithmic Complexity} for

    details.) Note, however, that for unshared list items that are

    larger than a pointer, each append or insert of a new item

    requires allocating the new item on the heap, and this per item

    allocation might make QVector a better choice in cases that do

    lots of appending or inserting, since QVector allocates memory for

    its items in a single heap allocation.

    Note that the internal array only ever gets bigger over the life

    of the list. It never shrinks. The internal array is deallocated

    by the destructor and by the assignment operator, when one list

    is assigned to another.

    Here's an example of a QList that stores integers and

    a QList that stores QDate values:

    \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 0

    Qt includes a QStringList class that inherits QList\<QString\>

    and adds a few convenience functions, such as QStringList::join()

    and QStringList::find(). (QString::split() creates QStringLists

    from strings.)

    QList stores a list of items. The default constructor creates an

    empty list. To insert items into the list, you can use

    operator<<():

    \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 1

    QList provides these basic functions to add, move, and remove

    items: insert(), replace(), removeAt(), move(), and swap(). In

    addition, it provides the following convenience functions:

    append(), prepend(), removeFirst(), and removeLast().

    QList uses 0-based indexes, just like C++ arrays. To access the

    item at a particular index position, you can use operator[](). On

    non-const lists, operator[]() returns a reference to the item and

    can be used on the left side of an assignment:

    \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 2

    Because QList is implemented as an array of pointers, this

    operation is very fast (\l{constant time}). For read-only access,

    an alternative syntax is to use at():

    \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 3

    at() can be faster than operator[](), because it never causes a

    \l{deep copy} to occur.

    A common requirement is to remove an item from a list and do

    something with it. For this, QList provides takeAt(), takeFirst(),

    and takeLast(). Here's a loop that removes the items from a list

    one at a time and calls \c delete on them:

    \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 4

    Inserting and removing items at either ends of the list is very

    fast (\l{constant time} in most cases), because QList

    preallocates extra space on both sides of its internal buffer to

    allow for fast growth at both ends of the list.

    If you want to find all occurrences of a particular value in a

    list, use indexOf() or lastIndexOf(). The former searches forward

    starting from a given index position, the latter searches

    backward. Both return the index of a matching item if they find

    it; otherwise, they return -1. For example:

    \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 5

    If you simply want to check whether a list contains a particular

    value, use contains(). If you want to find out how many times a

    particular value occurs in the list, use count(). If you want to

    replace all occurrences of a particular value with another, use

    replace().

    QList's value type must be an \l{assignable data type}. This

    covers most data types that are commonly used, but the compiler

    won't let you, for example, store a QWidget as a value; instead,

    store a QWidget *. A few functions have additional requirements;

    for example, indexOf() and lastIndexOf() expect the value type to

    support \c operator==().  These requirements are documented on a

    per-function basis.

    Like the other container classes, QList provides \l{Java-style

    iterators} (QListIterator and QMutableListIterator) and

    \l{STL-style iterators} (QList::const_iterator and

    QList::iterator). In practice, these are rarely used, because you

    can use indexes into the QList. QList is implemented in such a way

    that direct index-based access is just as fast as using iterators.

    QList does \e not support inserting, prepending, appending or

    replacing with references to its own values. Doing so will cause

    your application to abort with an error message.

    To make QList as efficient as possible, its member functions don't

    validate their input before using it. Except for isEmpty(), member

    functions always assume the list is \e not empty. Member functions

    that take index values as parameters always assume their index

    value parameters are in the valid range. This means QList member

    functions can fail. If you define QT_NO_DEBUG when you compile,

    failures will not be detected. If you \e don't define QT_NO_DEBUG,

    failures will be detected using Q_ASSERT() or Q_ASSERT_X() with an

    appropriate message.

    To avoid failures when your list can be empty, call isEmpty()

    before calling other member functions. If you must pass an index

    value that might not be in the valid range, check that it is less

    than the value returned by size() but \e not less than 0.

    \sa QListIterator, QMutableListIterator, QLinkedList, QVector

*/

/*!

    \fn QList<T> QList<T>::mid(int pos, int length) const

    Returns a list whose elements are copied from this list,

    starting at position \a pos. If \a length is -1 (the default), all

    elements from \a pos are copied; otherwise \a length elements (or

    all remaining elements if there are less than \a length elements)

    are copied.

*/

/*! \fn QList::QList()

    Constructs an empty list.

*/

/*! \fn QList::QList(const QList<T> &other)

    Constructs a copy of \a other.

    This operation takes \l{constant time}, because QList is

    \l{implicitly shared}. This makes returning a QList from a

    function very fast. If a shared instance is modified, it will be

    copied (copy-on-write), and that takes \l{linear time}.

    \sa operator=()

*/