Merge branch 'master' of git@scm.dev.nokia.troll.no:qt/qt

9 files changed, 969 insertions, 96 deletions

diff --git a/src/corelib/concurrent/qfuturewatcher.cpp b/src/corelib/concurrent/qfuturewatcher.cpp
index ea35e9e..39d7698 100644
--- a/src/corelib/concurrent/qfuturewatcher.cpp
+++ b/src/corelib/concurrent/qfuturewatcher.cpp
@@ -465,7 +465,7 @@ void QFutureWatcherBasePrivate::sendCallOutEvent(QFutureCallOutEvent *event)
                 break;
 
             emit q->progressValueChanged(event->index1);
-            if (event->text != QString()) // ###
+            if (!event->text.isNull()) // ###
                 q->progressTextChanged(event->text);
         break;
         case QFutureCallOutEvent::ProgressRange:
diff --git a/src/corelib/io/qdebug.h b/src/corelib/io/qdebug.h
index 8334146..9b0fbe5 100644
--- a/src/corelib/io/qdebug.h
+++ b/src/corelib/io/qdebug.h
@@ -51,6 +51,7 @@
 #include <QtCore/qstring.h>
 #include <QtCore/qvector.h>
 #include <QtCore/qset.h>
+#include <QtCore/qcontiguouscache.h>
 
 QT_BEGIN_HEADER
 
@@ -232,6 +233,24 @@ inline QDebug operator<<(QDebug debug, const QSet<T> &set)
     return operator<<(debug, set.toList());
 }
 
+#if defined(FORCE_UREF)
+template <class T>
+inline QDebug &operator<<(QDebug debug, const QContiguousCache<T> &cache)
+#else
+template <class T>
+inline QDebug operator<<(QDebug debug, const QContiguousCache<T> &cache)
+#endif
+{
+    debug.nospace() << "QContiguousCache(";
+    for (int i = cache.firstIndex(); i <= cache.lastIndex(); ++i) {
+        debug << cache[i];
+        if (i != cache.lastIndex())
+            debug << ", ";
+    }
+    debug << ")";
+    return debug.space();
+}
+
 #if !defined(QT_NO_DEBUG_STREAM)
 Q_CORE_EXPORT_INLINE QDebug qDebug() { return QDebug(QtDebugMsg); }
 
diff --git a/src/corelib/kernel/qcoreapplication.cpp b/src/corelib/kernel/qcoreapplication.cpp
index c21cf87..77ef096 100644
--- a/src/corelib/kernel/qcoreapplication.cpp
+++ b/src/corelib/kernel/qcoreapplication.cpp
@@ -1710,7 +1710,7 @@ QString QCoreApplication::applicationDirPath()
     }
 
     QCoreApplicationPrivate *d = self->d_func();
-    if (d->cachedApplicationDirPath == QString())
+    if (d->cachedApplicationDirPath.isNull())
         d->cachedApplicationDirPath = QFileInfo(applicationFilePath()).path();
     return d->cachedApplicationDirPath;
 }
@@ -1738,7 +1738,7 @@ QString QCoreApplication::applicationFilePath()
     }
 
     QCoreApplicationPrivate *d = self->d_func();
-    if (d->cachedApplicationFilePath != QString())
+    if (!d->cachedApplicationFilePath.isNull())
         return d->cachedApplicationFilePath;
 
 #if defined( Q_WS_WIN )
diff --git a/src/corelib/kernel/qvariant.cpp b/src/corelib/kernel/qvariant.cpp
index b53e91f..b504604 100644
--- a/src/corelib/kernel/qvariant.cpp
+++ b/src/corelib/kernel/qvariant.cpp
@@ -1173,8 +1173,9 @@ const QVariant::Handler *QVariant::handler = &qt_kernel_variant_handler;
     and versatile, but may prove less memory and speed efficient than
     storing specific types in standard data structures.
 
-    QVariant also supports the notion of null values, where you have
-    a defined type with no value set.
+    QVariant also supports the notion of null values, where you can 
+    have a defined type with no value set. However, note that QVariant 
+    types can only be cast when they have had a value set.
 
     \snippet doc/src/snippets/code/src_corelib_kernel_qvariant.cpp 1
 
diff --git a/src/corelib/tools/qcontiguouscache.cpp b/src/corelib/tools/qcontiguouscache.cpp
new file mode 100644
index 0000000..7db3a5a
--- /dev/null
+++ b/src/corelib/tools/qcontiguouscache.cpp
@@ -0,0 +1,435 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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 qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qcontiguouscache.h"
+#include <QDebug>
+
+QT_BEGIN_NAMESPACE
+
+void QContiguousCacheData::dump() const
+{
+    qDebug() << "capacity:" << alloc;
+    qDebug() << "count:" << count;
+    qDebug() << "start:" << start;
+    qDebug() << "offset:" << offset;
+}
+
+/*! \class QContiguousCache
+    \brief The QContiguousCache class is a template class that provides a contiguous cache.
+    \ingroup tools
+    \ingroup shared
+    \reentrant
+
+    The QContiguousCache class provides an efficient way of caching items for
+    display in a user interface view.  Unlike QCache, it adds a restriction
+    that elements within the cache are contiguous.  This has the advantage
+    of matching how user interface views most commonly request data, as
+    a set of rows localized around the current scrolled position.  This
+    restriction allows the cache to consume less memory and processor
+    cycles than QCache.  The QContiguousCache class also can provide
+    an upper bound on memory usage via setCapacity().
+
+    The simplest way of using a contiguous cache is to use the append()
+    and prepend().
+
+\code
+MyRecord record(int row) const
+{
+    Q_ASSERT(row >= 0 && row < count());
+
+    while(row > cache.lastIndex())
+        cache.append(slowFetchRecord(cache.lastIndex()+1));
+    while(row < cache.firstIndex())
+        cache.prepend(slowFetchRecord(cache.firstIndex()-1));
+
+    return cache.at(row);
+}
+\endcode
+
+    If the cache is full then the item at the opposite end of the cache from
+    where the new item is appended or prepended will be removed.
+
+    This usage can be further optimized by using the insert() function
+    in the case where the requested row is a long way from the currently cached
+    items. If there is a gap between where the new item is inserted and the currently
+    cached items then the existing cached items are first removed to retain
+    the contiguous nature of the cache.  Hence it is important to take some care then
+    when using insert() in order to avoid unwanted clearing of the cache.
+
+    The range of valid indexes for the QContiguousCache class are from
+    0 to INT_MAX.  Calling prepend() such that the first index would become less
+    than 0 or append() such that the last index would become greater
+    than INT_MAX can result in the indexes of the cache being invalid.
+    When the cache indexes are invalid it is important to call
+    normalizeIndexes() before calling any of containsIndex(), firstIndex(),
+    lastIndex(), at() or the [] operator.  Calling these
+    functions when the cache has invalid indexes will result in undefined
+    behavior.  The indexes can be checked by using areIndexesValid()
+
+    In most cases the indexes will not exceed 0 to INT_MAX, and
+    normalizeIndexes() will not need to be used.
+
+    See the \l{Contiguous Cache Example}{Contiguous Cache} example.
+*/
+
+/*! \fn QContiguousCache::QContiguousCache(int capacity)
+
+    Constructs a cache with the given \a capacity.
+
+    \sa setCapacity()
+*/
+
+/*! \fn QContiguousCache::QContiguousCache(const QContiguousCache<T> &other)
+
+    Constructs a copy of \a other.
+
+    This operation takes \l{constant time}, because QContiguousCache is
+    \l{implicitly shared}.  This makes returning a QContiguousCache 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=()
+*/
+
+/*! \fn QContiguousCache::~QContiguousCache()
+
+    Destroys the cache.
+*/
+
+/*! \fn void QContiguousCache::detach()
+
+    \internal
+*/
+
+/*! \fn bool QContiguousCache::isDetached() const
+
+    \internal
+*/
+
+/*! \fn void QContiguousCache::setSharable(bool sharable)
+
+    \internal
+*/
+
+/*! \fn QContiguousCache<T> &QContiguousCache::operator=(const QContiguousCache<T> &other)
+
+    Assigns \a other to this cache and returns a reference to this cache.
+*/
+
+/*! \fn bool QContiguousCache::operator==(const QContiguousCache<T> &other) const
+
+    Returns true if \a other is equal to this cache; otherwise returns false.
+
+    Two caches are considered equal if they contain the same values at the same
+    indexes.  This function requires the value type to implement the \c operator==().
+
+    \sa operator!=()
+*/
+
+/*! \fn bool QContiguousCache::operator!=(const QContiguousCache<T> &other) const
+
+    Returns true if \a other is not equal to this cache; otherwise
+    returns false.
+
+    Two caches are considered equal if they contain the same values at the same
+    indexes.  This function requires the value type to implement the \c operator==().
+
+    \sa operator==()
+*/
+
+/*! \fn int QContiguousCache::capacity() const
+
+    Returns the number of items the cache can store before it is full.
+    When a cache contains a number of items equal to its capacity, adding new
+    items will cause items farthest from the added item to be removed.
+
+    \sa setCapacity(), size()
+*/
+
+/*! \fn int QContiguousCache::count() const
+
+    \overload
+
+    Same as size().
+*/
+
+/*! \fn int QContiguousCache::size() const
+
+    Returns the number of items contained within the cache.
+
+    \sa capacity()
+*/
+
+/*! \fn bool QContiguousCache::isEmpty() const
+
+    Returns true if no items are stored within the cache.
+
+    \sa size(), capacity()
+*/
+
+/*! \fn bool QContiguousCache::isFull() const
+
+    Returns true if the number of items stored within the cache is equal
+    to the capacity of the cache.
+
+    \sa size(), capacity()
+*/
+
+/*! \fn int QContiguousCache::available() const
+
+    Returns the number of items that can be added to the cache before it becomes full.
+
+    \sa size(), capacity(), isFull()
+*/
+
+/*! \fn void QContiguousCache::clear()
+
+    Removes all items from the cache.  The capacity is unchanged.
+*/
+
+/*! \fn void QContiguousCache::setCapacity(int size)
+
+    Sets the capacity of the cache to the given \a size.  A cache can hold a
+    number of items equal to its capacity.  When inserting, appending or prepending
+    items to the cache, if the cache is already full then the item farthest from
+    the added item will be removed.
+
+    If the given \a size is smaller than the current count of items in the cache
+    then only the last \a size items from the cache will remain.
+
+    \sa capacity(), isFull()
+*/
+
+/*! \fn const T &QContiguousCache::at(int i) const
+
+    Returns the item at index position \a i in the cache.  \a i must
+    be a valid index position in the cache (i.e, firstIndex() <= \a i <= lastIndex()).
+
+    The indexes in the cache refer to the number of positions the item is from the
+    first item appended into the cache.  That is to say a cache with a capacity of
+    100, that has had 150 items appended will have a valid index range of
+    50 to 149.  This allows inserting and retrieving items into the cache based
+    on a theoretical infinite list
+
+    \sa firstIndex(), lastIndex(), insert(), operator[]()
+*/
+
+/*! \fn T &QContiguousCache::operator[](int i)
+
+    Returns the item at index position \a i as a modifiable reference.  If
+    the cache does not contain an item at the given index position \a i
+    then it will first insert an empty item at that position.
+
+    In most cases it is better to use either at() or insert().
+
+    Note that using non-const operators can cause QContiguousCache to do a deep
+    copy.
+
+    \sa insert(), at()
+*/
+
+/*! \fn const T &QContiguousCache::operator[](int i) const
+
+    \overload
+
+    Same as at(\a i).
+*/
+
+/*! \fn void QContiguousCache::append(const T &value)
+
+    Inserts \a value at the end of the cache.  If the cache is already full
+    the item at the start of the cache will be removed.
+
+    \sa prepend(), insert(), isFull()
+*/
+
+/*! \fn void QContiguousCache::prepend(const T &value)
+
+    Inserts \a value at the start of the cache.  If the cache is already full
+    the item at the end of the cache will be removed.
+
+    \sa append(), insert(), isFull()
+*/
+
+/*! \fn void QContiguousCache::insert(int i, const T &value)
+
+    Inserts the \a value at the index position \a i.  If the cache already contains
+    an item at \a i then that value is replaced.  If \a i is either one more than
+    lastIndex() or one less than firstIndex() it is the equivalent to an append()
+    or a prepend().
+
+    If the given index \a i is not within the current range of the cache nor adjacent
+    to the bounds of the cache's index range, the cache is first cleared before
+    inserting the item.  At this point the cache will have a size of 1.  It is
+    worthwhile taking effort to insert items in an order that starts adjacent
+    to the current index range for the cache.
+
+    The range of valid indexes for the QContiguousCache class are from
+    0 to INT_MAX. Inserting outside of this range has undefined behavior.
+
+
+    \sa prepend(), append(), isFull(), firstIndex(), lastIndex()
+*/
+
+/*! \fn bool QContiguousCache::containsIndex(int i) const
+
+    Returns true if the cache's index range includes the given index \a i.
+
+    \sa firstIndex(), lastIndex()
+*/
+
+/*! \fn int QContiguousCache::firstIndex() const
+
+    Returns the first valid index in the cache.  The index will be invalid if the
+    cache is empty.
+
+    \sa capacity(), size(), lastIndex()
+*/
+
+/*! \fn int QContiguousCache::lastIndex() const
+
+    Returns the last valid index in the cache.  The index will be invalid if the cache is empty.
+
+    \sa capacity(), size(), firstIndex()
+*/
+
+
+/*! \fn T &QContiguousCache::first()
+
+    Returns a reference to the first item in the cache.  This function
+    assumes that the cache isn't empty.
+
+    \sa last(), isEmpty()
+*/
+
+/*! \fn T &QContiguousCache::last()
+
+    Returns a reference to the last item in the cache.  This function
+    assumes that the cache isn't empty.
+
+    \sa first(), isEmpty()
+*/
+
+/*! \fn const T& QContiguousCache::first() const
+
+    \overload
+*/
+
+/*! \fn const T& QContiguousCache::last() const
+
+    \overload
+*/
+
+/*! \fn void QContiguousCache::removeFirst()
+
+    Removes the first item from the cache.  This function assumes that
+    the cache isn't empty.
+
+    \sa removeLast()
+*/
+
+/*! \fn void QContiguousCache::removeLast()
+
+    Removes the last item from the cache.  This function assumes that
+    the cache isn't empty.
+
+    \sa removeFirst()
+*/
+
+/*! \fn T QContiguousCache::takeFirst()
+
+    Removes the first item in the cache and returns it.  This function
+    assumes that the cache isn't empty.
+
+    If you don't use the return value, removeFirst() is more efficient.
+
+    \sa takeLast(), removeFirst()
+*/
+
+/*! \fn T QContiguousCache::takeLast()
+
+    Removes the last item in the cache and returns it. This function
+    assumes that the cache isn't empty.
+
+    If you don't use the return value, removeLast() is more efficient.
+
+    \sa takeFirst(), removeLast()
+*/
+
+/*! \fn void QContiguousCache::normalizeIndexes()
+
+    Moves the first index and last index of the cache
+    such that they point to valid indexes.  The function does not modify
+    the contents of the cache or the ordering of elements within the cache.
+
+    It is provided so that index overflows can be corrected when using the
+    cache as a circular buffer.
+
+    \code
+    QContiguousCache<int> cache(10);
+    cache.insert(INT_MAX, 1); // cache contains one value and has valid indexes, INT_MAX to INT_MAX
+    cache.append(2); // cache contains two values but does not have valid indexes.
+    cache.normalizeIndexes(); // cache has two values, 1 and 2.  New first index will be in the range of 0 to capacity().
+    \endcode
+
+    \sa areIndexesValid(), append(), prepend()
+*/
+
+/*! \fn bool QContiguousCache::areIndexesValid() const
+
+    Returns whether the indexes for items stored in the cache are valid.
+    Indexes can become invalid if items are appended after the index position
+    INT_MAX or prepended before the index position 0.  This is only expected
+    to occur in very long lived circular buffer style usage of the
+    contiguous cache.  Indexes can be made valid again by calling
+    normalizeIndexs().
+
+    \sa normalizeIndexes(), append(), prepend()
+*/
+
+/*! \fn void QContiguousCache::dump() const
+
+    \internal
+
+    Sends information about the cache's internal structure to qDebug()
+*/
+
+QT_END_NAMESPACE
diff --git a/src/corelib/tools/qcontiguouscache.h b/src/corelib/tools/qcontiguouscache.h
new file mode 100644
index 0000000..5cd1582
--- /dev/null
+++ b/src/corelib/tools/qcontiguouscache.h
@@ -0,0 +1,424 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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 qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QCONTIGUOUSCACHE_H
+#define QCONTIGUOUSCACHE_H
+
+#include <QtCore/qatomic.h>
+#include <limits.h>
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+QT_MODULE(Core)
+
+struct Q_CORE_EXPORT QContiguousCacheData
+{
+    QBasicAtomicInt ref;
+    int alloc;
+    int count;
+    int start;
+    int offset;
+    uint sharable : 1;
+
+    void dump() const;
+};
+
+template <typename T>
+struct QContiguousCacheTypedData
+{
+    QBasicAtomicInt ref;
+    int alloc;
+    int count;
+    int start;
+    int offset;
+    uint sharable : 1;
+
+    T array[1];
+};
+
+template<typename T>
+class QContiguousCache {
+    typedef QContiguousCacheTypedData<T> Data;
+    union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; };
+public:
+    explicit QContiguousCache(int capacity = 0);
+    QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
+
+    inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(d); }
+
+    inline void detach() { if (d->ref != 1) detach_helper(); }
+    inline bool isDetached() const { return d->ref == 1; }
+    inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
+
+    QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
+    bool operator==(const QContiguousCache<T> &other) const;
+    inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); }
+
+    inline int capacity() const {return d->alloc; }
+    inline int count() const { return d->count; }
+    inline int size() const { return d->count; }
+
+    inline bool isEmpty() const { return d->count == 0; }
+    inline bool isFull() const { return d->count == d->alloc; }
+    inline int available() const { return d->alloc - d->count; }
+
+    void clear();
+    void setCapacity(int size);
+
+    const T &at(int pos) const;
+    T &operator[](int i);
+    const T &operator[](int i) const;
+
+    void append(const T &value);
+    void prepend(const T &value);
+    void insert(int pos, const T &value);
+
+    inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; }
+    inline int firstIndex() const { return d->offset; }
+    inline int lastIndex() const { return d->offset + d->count - 1; }
+
+    inline const T &first() const { Q_ASSERT(!isEmpty()); return d->array[d->start]; }
+    inline const T &last() const { Q_ASSERT(!isEmpty()); return d->array[(d->start + d->count -1) % d->alloc]; }
+    inline T &first() { Q_ASSERT(!isEmpty()); detach(); return d->array[d->start]; }
+    inline T &last() { Q_ASSERT(!isEmpty()); detach(); return d->array[(d->start + d->count -1) % d->alloc]; }
+
+    void removeFirst();
+    T takeFirst();
+    void removeLast();
+    T takeLast();
+
+    inline bool areIndexesValid() const
+    { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }
+
+    inline void normalizeIndexes() { d->offset = d->start; }
+    // debug
+    void dump() const { p->dump(); }
+private:
+    void detach_helper();
+
+    QContiguousCacheData *malloc(int aalloc);
+    void free(Data *x);
+    int sizeOfTypedData() {
+        // this is more or less the same as sizeof(Data), except that it doesn't
+        // count the padding at the end
+        return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
+    }
+};
+
+template <typename T>
+void QContiguousCache<T>::detach_helper()
+{
+    union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+
+    x.p = malloc(d->alloc);
+    x.d->ref = 1;
+    x.d->count = d->count;
+    x.d->start = d->start;
+    x.d->offset = d->offset;
+    x.d->alloc = d->alloc;
+    x.d->sharable = true;
+
+    T *dest = x.d->array + x.d->start;
+    T *src = d->array + d->start;
+    int count = x.d->count;
+    while (count--) {
+        if (QTypeInfo<T>::isComplex) {
+            new (dest) T(*src);
+        } else {
+            *dest = *src;
+        }
+        dest++;
+        if (dest == x.d->array + x.d->alloc)
+            dest = x.d->array;
+        src++;
+        if (src == d->array + d->alloc)
+            src = d->array;
+    }
+
+    if (!d->ref.deref())
+        free(d);
+    d = x.d;
+}
+
+template <typename T>
+void QContiguousCache<T>::setCapacity(int asize)
+{
+    if (asize == d->alloc)
+        return;
+    detach();
+    union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+    x.p = malloc(asize);
+    x.d->alloc = asize;
+    x.d->count = qMin(d->count, asize);
+    x.d->offset = d->offset + d->count - x.d->count;
+    x.d->start = x.d->offset % x.d->alloc;
+    T *dest = x.d->array + (x.d->start + x.d->count-1) % x.d->alloc;
+    T *src = d->array + (d->start + d->count-1) % d->alloc;
+    int count = x.d->count;
+    while (count--) {
+        if (QTypeInfo<T>::isComplex) {
+            new (dest) T(*src);
+        } else {
+            *dest = *src;
+        }
+        if (dest == x.d->array)
+            dest = x.d->array + x.d->alloc;
+        dest--;
+        if (src == d->array)
+            src = d->array + d->alloc;
+        src--;
+    }
+    /* free old */
+    free(d);
+    d = x.d;
+}
+
+template <typename T>
+void QContiguousCache<T>::clear()
+{
+    if (d->ref == 1) {
+        if (QTypeInfo<T>::isComplex) {
+            int count = d->count;
+            T * i = d->array + d->start;
+            T * e = d->array + d->alloc;
+            while (count--) {
+                i->~T();
+                i++;
+                if (i == e)
+                    i = d->array;
+            }
+        }
+        d->count = d->start = d->offset = 0;
+    } else {
+        union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+        x.p = malloc(d->alloc);
+        x.d->ref = 1;
+        x.d->alloc = d->alloc;
+        x.d->count = x.d->start = x.d->offset = 0;
+        x.d->sharable = true;
+        if (!d->ref.deref()) free(d);
+        d = x.d;
+    }
+}
+
+template <typename T>
+inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)
+{
+    return static_cast<QContiguousCacheData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
+}
+
+template <typename T>
+QContiguousCache<T>::QContiguousCache(int capacity)
+{
+    p = malloc(capacity);
+    d->ref = 1;
+    d->alloc = capacity;
+    d->count = d->start = d->offset = 0;
+    d->sharable = true;
+}
+
+template <typename T>
+QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
+{
+    other.d->ref.ref();
+    if (!d->ref.deref())
+        free(d);
+    d = other.d;
+    if (!d->sharable)
+        detach_helper();
+    return *this;
+}
+
+template <typename T>
+bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
+{
+    if (other.d == d)
+        return true;
+    if (other.d->start != d->start
+            || other.d->count != d->count
+            || other.d->offset != d->offset
+            || other.d->alloc != d->alloc)
+        return false;
+    for (int i = firstIndex(); i <= lastIndex(); ++i)
+        if (!(at(i) == other.at(i)))
+            return false;
+    return true;
+}
+
+template <typename T>
+void QContiguousCache<T>::free(Data *x)
+{
+    if (QTypeInfo<T>::isComplex) {
+        int count = d->count;
+        T * i = d->array + d->start;
+        T * e = d->array + d->alloc;
+        while (count--) {
+            i->~T();
+            i++;
+            if (i == e)
+                i = d->array;
+        }
+    }
+    qFree(x);
+}
+template <typename T>
+void QContiguousCache<T>::append(const T &value)
+{
+    detach();
+    if (QTypeInfo<T>::isComplex) {
+        if (d->count == d->alloc)
+            (d->array + (d->start+d->count) % d->alloc)->~T();
+        new (d->array + (d->start+d->count) % d->alloc) T(value);
+    } else {
+        d->array[(d->start+d->count) % d->alloc] = value;
+    }
+
+    if (d->count == d->alloc) {
+        d->start++;
+        d->start %= d->alloc;
+        d->offset++;
+    } else {
+        d->count++;
+    }
+}
+
+template<typename T>
+void QContiguousCache<T>::prepend(const T &value)
+{
+    detach();
+    if (d->start)
+        d->start--;
+    else
+        d->start = d->alloc-1;
+    d->offset--;
+
+    if (d->count != d->alloc)
+        d->count++;
+    else
+        if (d->count == d->alloc)
+            (d->array + d->start)->~T();
+
+    if (QTypeInfo<T>::isComplex)
+        new (d->array + d->start) T(value);
+    else
+        d->array[d->start] = value;
+}
+
+template<typename T>
+void QContiguousCache<T>::insert(int pos, const T &value)
+{
+    Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");
+    detach();
+    if (containsIndex(pos)) {
+        if(QTypeInfo<T>::isComplex)
+            new (d->array + pos % d->alloc) T(value);
+        else
+            d->array[pos % d->alloc] = value;
+    } else if (pos == d->offset-1)
+        prepend(value);
+    else if (pos == d->offset+d->count)
+        append(value);
+    else {
+        // we don't leave gaps.
+        clear();
+        d->offset = pos;
+        d->start = pos % d->alloc;
+        d->count = 1;
+        if (QTypeInfo<T>::isComplex)
+            new (d->array + d->start) T(value);
+        else
+            d->array[d->start] = value;
+    }
+}
+
+template <typename T>
+inline const T &QContiguousCache<T>::at(int pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
+template <typename T>
+inline const T &QContiguousCache<T>::operator[](int pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
+
+template <typename T>
+inline T &QContiguousCache<T>::operator[](int pos)
+{
+    detach();
+    if (!containsIndex(pos))
+        insert(pos, T());
+    return d->array[pos % d->alloc];
+}
+
+template <typename T>
+inline void QContiguousCache<T>::removeFirst()
+{
+    Q_ASSERT(d->count > 0);
+    detach();
+    d->count--;
+    if (QTypeInfo<T>::isComplex)
+        (d->array + d->start)->~T();
+    d->start = (d->start + 1) % d->alloc;
+    d->offset++;
+}
+
+template <typename T>
+inline void QContiguousCache<T>::removeLast()
+{
+    Q_ASSERT(d->count > 0);
+    detach();
+    d->count--;
+    if (QTypeInfo<T>::isComplex)
+        (d->array + (d->start + d->count) % d->alloc)->~T();
+}
+
+template <typename T>
+inline T QContiguousCache<T>::takeFirst()
+{ T t = first(); removeFirst(); return t; }
+
+template <typename T>
+inline T QContiguousCache<T>::takeLast()
+{ T t = last(); removeLast(); return t; }
+
+QT_END_NAMESPACE
+
+QT_END_HEADER
+
+#endif
diff --git a/src/corelib/tools/qtimeline.cpp b/src/corelib/tools/qtimeline.cpp
index 2979a09..3a03558 100644
--- a/src/corelib/tools/qtimeline.cpp
+++ b/src/corelib/tools/qtimeline.cpp
@@ -225,7 +225,9 @@ void QTimeLinePrivate::setCurrentTime(int msecs)
     valueForTime() and emitting valueChanged(). By default, valueForTime()
     applies an interpolation algorithm to generate these value. You can choose
     from a set of predefined timeline algorithms by calling
-    setCurveShape(). By default, QTimeLine uses the EaseInOut curve shape,
+    setCurveShape().
+   
+    Note that by default, QTimeLine uses the EaseInOut curve shape,
     which provides a value that grows slowly, then grows steadily, and
     finally grows slowly. For a custom timeline, you can reimplement
     valueForTime(), in which case QTimeLine's curveShape property is ignored.
diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h
index 1f047b8..7bdcba0 100644
--- a/src/corelib/tools/qvector.h
+++ b/src/corelib/tools/qvector.h
@@ -82,19 +82,9 @@ struct Q_CORE_EXPORT QVectorData
 };
 
 template <typename T>
-struct QVectorTypedData
-{
-    QBasicAtomicInt ref;
-    int alloc;
-    int size;
-#if defined(QT_ARCH_SPARC) && defined(Q_CC_GNU) && defined(__LP64__) && defined(QT_BOOTSTRAPPED)
-    // workaround for bug in gcc 3.4.2
-    uint sharable;
-    uint capacity;
-#else
-    uint sharable : 1;
-    uint capacity : 1;
-#endif
+struct QVectorTypedData : private QVectorData
+{ // private inheritance as we must not access QVectorData member thought QVectorTypedData
+  // as this would break strict aliasing rules. (in the case of shared_null)
     T array[1];
 };
 
@@ -104,14 +94,14 @@ template <typename T>
 class QVector
 {
     typedef QVectorTypedData<T> Data;
-    union { QVectorData *p; QVectorTypedData<T> *d; };
+    union { QVectorData *d; Data *p; };
 
 public:
-    inline QVector() : p(&QVectorData::shared_null) { d->ref.ref(); }
+    inline QVector() : d(&QVectorData::shared_null) { d->ref.ref(); }
     explicit QVector(int size);
     QVector(int size, const T &t);
     inline QVector(const QVector<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
-    inline ~QVector() { if (!d) return; if (!d->ref.deref()) free(d); }
+    inline ~QVector() { if (!d) return; if (!d->ref.deref()) free(p); }
     QVector<T> &operator=(const QVector<T> &v);
     bool operator==(const QVector<T> &v) const;
     inline bool operator!=(const QVector<T> &v) const { return !(*this == v); }
@@ -130,9 +120,9 @@ public:
     inline bool isDetached() const { return d->ref == 1; }
     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
 
-    inline T *data() { detach(); return d->array; }
-    inline const T *data() const { return d->array; }
-    inline const T *constData() const { return d->array; }
+    inline T *data() { detach(); return p->array; }
+    inline const T *data() const { return p->array; }
+    inline const T *constData() const { return p->array; }
     void clear();
 
     const T &at(int i) const;
@@ -225,12 +215,12 @@ public:
     typedef T* iterator;
     typedef const T* const_iterator;
 #endif
-    inline iterator begin() { detach(); return d->array; }
-    inline const_iterator begin() const { return d->array; }
-    inline const_iterator constBegin() const { return d->array; }
-    inline iterator end() { detach(); return d->array + d->size; }
-    inline const_iterator end() const { return d->array + d->size; }
-    inline const_iterator constEnd() const { return d->array + d->size; }
+    inline iterator begin() { detach(); return p->array; }
+    inline const_iterator begin() const { return p->array; }
+    inline const_iterator constBegin() const { return p->array; }
+    inline iterator end() { detach(); return p->array + d->size; }
+    inline const_iterator end() const { return p->array + d->size; }
+    inline const_iterator constEnd() const { return p->array + d->size; }
     iterator insert(iterator before, int n, const T &x);
     inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
     iterator erase(iterator begin, iterator end);
@@ -327,11 +317,11 @@ inline void QVector<T>::clear()
 template <typename T>
 inline const T &QVector<T>::at(int i) const
 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range");
-  return d->array[i]; }
+  return p->array[i]; }
 template <typename T>
 inline const T &QVector<T>::operator[](int i) const
 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
-  return d->array[i]; }
+  return p->array[i]; }
 template <typename T>
 inline T &QVector<T>::operator[](int i)
 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
@@ -369,7 +359,7 @@ QVector<T> &QVector<T>::operator=(const QVector<T> &v)
 {
     v.d->ref.ref();
     if (!d->ref.deref())
-        free(d);
+        free(p);
     d = v.d;
     if (!d->sharable)
         detach_helper();
@@ -385,31 +375,31 @@ inline QVectorData *QVector<T>::malloc(int aalloc)
 template <typename T>
 QVector<T>::QVector(int asize)
 {
-    p = malloc(asize);
+    d = malloc(asize);
     d->ref = 1;
     d->alloc = d->size = asize;
     d->sharable = true;
     d->capacity = false;
     if (QTypeInfo<T>::isComplex) {
-        T* b = d->array;
-        T* i = d->array + d->size;
+        T* b = p->array;
+        T* i = p->array + d->size;
         while (i != b)
             new (--i) T;
     } else {
-        qMemSet(d->array, 0, asize * sizeof(T));
+        qMemSet(p->array, 0, asize * sizeof(T));
     }
 }
 
 template <typename T>
 QVector<T>::QVector(int asize, const T &t)
 {
-    p = malloc(asize);
+    d = malloc(asize);
     d->ref = 1;
     d->alloc = d->size = asize;
     d->sharable = true;
     d->capacity = false;
-    T* i = d->array + d->size;
-    while (i != d->array)
+    T* i = p->array + d->size;
+    while (i != p->array)
         new (--i) T(t);
 }
 
@@ -418,7 +408,7 @@ void QVector<T>::free(Data *x)
 {
     if (QTypeInfo<T>::isComplex) {
         T* b = x->array;
-        T* i = b + x->size;
+        T* i = b + reinterpret_cast<QVectorData *>(x)->size;
         while (i-- != b)
              i->~T();
     }
@@ -429,13 +419,13 @@ template <typename T>
 void QVector<T>::realloc(int asize, int aalloc)
 {
     T *j, *i, *b;
-    union { QVectorData *p; Data *d; } x;
+    union { QVectorData *d; Data *p; } x;
     x.d = d;
 
     if (QTypeInfo<T>::isComplex && aalloc == d->alloc && d->ref == 1) {
         // pure resize
-        i = d->array + d->size;
-        j = d->array + asize;
+        i = p->array + d->size;
+        j = p->array + asize;
         if (i > j) {
             while (i-- != j)
                 i->~T();
@@ -450,22 +440,22 @@ void QVector<T>::realloc(int asize, int aalloc)
     if (aalloc != d->alloc || d->ref != 1) {
         // (re)allocate memory
         if (QTypeInfo<T>::isStatic) {
-            x.p = malloc(aalloc);
+            x.d = malloc(aalloc);
         } else if (d->ref != 1) {
-            x.p = QVectorData::malloc(sizeOfTypedData(), aalloc, sizeof(T), p);
+            x.d = QVectorData::malloc(sizeOfTypedData(), aalloc, sizeof(T), d);
         } else {
             if (QTypeInfo<T>::isComplex) {
                 // call the destructor on all objects that need to be
                 // destroyed when shrinking
                 if (asize < d->size) {
-                    j = d->array + asize;
-                    i = d->array + d->size;
+                    j = p->array + asize;
+                    i = p->array + d->size;
                     while (i-- != j)
                         i->~T();
-                    i = d->array + asize;
+                    i = p->array + asize;
                 }
             }
-            x.p = p = static_cast<QVectorData *>(qRealloc(p, sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
+            x.d = d = static_cast<QVectorData *>(qRealloc(d, sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
         }
         x.d->ref = 1;
         x.d->sharable = true;
@@ -474,31 +464,31 @@ void QVector<T>::realloc(int asize, int aalloc)
     }
     if (QTypeInfo<T>::isComplex) {
         if (asize < d->size) {
-            j = d->array + asize;
-            i = x.d->array + asize;
+            j = p->array + asize;
+            i = x.p->array + asize;
         } else {
             // construct all new objects when growing
-            i = x.d->array + asize;
-            j = x.d->array + d->size;
+            i = x.p->array + asize;
+            j = x.p->array + d->size;
             while (i != j)
                 new (--i) T;
-            j = d->array + d->size;
+            j = p->array + d->size;
         }
         if (i != j) {
             // copy objects from the old array into the new array
-            b = x.d->array;
+            b = x.p->array;
             while (i != b)
                 new (--i) T(*--j);
         }
     } else if (asize > d->size) {
         // initialize newly allocated memory to 0
-        qMemSet(x.d->array + d->size, 0, (asize - d->size) * sizeof(T));
+        qMemSet(x.p->array + d->size, 0, (asize - d->size) * sizeof(T));
     }
     x.d->size = asize;
     x.d->alloc = aalloc;
     if (d != x.d) {
         if (!d->ref.deref())
-            free(d);
+            free(p);
         d = x.d;
     }
 }
@@ -506,15 +496,15 @@ void QVector<T>::realloc(int asize, int aalloc)
 template<typename T>
 Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const
 {
-    if (i < 0 || i >= p->size) {
+    if (i < 0 || i >= d->size) {
         return T();
     }
-    return d->array[i];
+    return p->array[i];
 }
 template<typename T>
 Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const
 {
-    return ((i < 0 || i >= p->size) ? defaultValue : d->array[i]);
+    return ((i < 0 || i >= d->size) ? defaultValue : p->array[i]);
 }
 
 template <typename T>
@@ -525,14 +515,14 @@ void QVector<T>::append(const T &t)
         realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + 1, sizeof(T),
                                            QTypeInfo<T>::isStatic));
         if (QTypeInfo<T>::isComplex)
-            new (d->array + d->size) T(copy);
+            new (p->array + d->size) T(copy);
         else
-            d->array[d->size] = copy;
+            p->array[d->size] = copy;
     } else {
         if (QTypeInfo<T>::isComplex)
-            new (d->array + d->size) T(t);
+            new (p->array + d->size) T(t);
         else
-            d->array[d->size] = t;
+            p->array[d->size] = t;
     }
     ++d->size;
 }
@@ -540,27 +530,27 @@ void QVector<T>::append(const T &t)
 template <typename T>
 Q_TYPENAME QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t)
 {
-    int offset = before - d->array;
+    int offset = before - p->array;
     if (n != 0) {
         const T copy(t);
         if (d->ref != 1 || d->size + n > d->alloc)
             realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + n, sizeof(T),
                                                QTypeInfo<T>::isStatic));
         if (QTypeInfo<T>::isStatic) {
-            T *b = d->array + d->size;
-            T *i = d->array + d->size + n;
+            T *b = p->array + d->size;
+            T *i = p->array + d->size + n;
             while (i != b)
                 new (--i) T;
-            i = d->array + d->size;
+            i = p->array + d->size;
             T *j = i + n;
-            b = d->array + offset;
+            b = p->array + offset;
             while (i != b)
                 *--j = *--i;
             i = b+n;
             while (i != b)
                 *--i = copy;
         } else {
-            T *b = d->array + offset;
+            T *b = p->array + offset;
             T *i = b + n;
             memmove(i, b, (d->size - offset) * sizeof(T));
             while (i != b)
@@ -568,29 +558,29 @@ Q_TYPENAME QVector<T>::iterator QVector<T>::insert(iterator before, size_type n,
         }
         d->size += n;
     }
-    return d->array + offset;
+    return p->array + offset;
 }
 
 template <typename T>
 Q_TYPENAME QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend)
 {
-    int f = abegin - d->array;
-    int l = aend - d->array;
+    int f = abegin - p->array;
+    int l = aend - p->array;
     int n = l - f;
     detach();
     if (QTypeInfo<T>::isComplex) {
-        qCopy(d->array+l, d->array+d->size, d->array+f);
-        T *i = d->array+d->size;
-        T* b = d->array+d->size-n;
+        qCopy(p->array+l, p->array+d->size, p->array+f);
+        T *i = p->array+d->size;
+        T* b = p->array+d->size-n;
         while (i != b) {
             --i;
             i->~T();
         }
     } else {
-        memmove(d->array + f, d->array + l, (d->size-l)*sizeof(T));
+        memmove(p->array + f, p->array + l, (d->size-l)*sizeof(T));
     }
     d->size -= n;
-    return d->array + f;
+    return p->array + f;
 }
 
 template <typename T>
@@ -600,9 +590,9 @@ bool QVector<T>::operator==(const QVector<T> &v) const
         return false;
     if (d == v.d)
         return true;
-    T* b = d->array;
+    T* b = p->array;
     T* i = b + d->size;
-    T* j = v.d->array + d->size;
+    T* j = v.p->array + d->size;
     while (i != b)
         if (!(*--i == *--j))
             return false;
@@ -615,8 +605,8 @@ QVector<T> &QVector<T>::fill(const T &from, int asize)
     const T copy(from);
     resize(asize < 0 ? d->size : asize);
     if (d->size) {
-        T *i = d->array + d->size;
-        T *b = d->array;
+        T *i = p->array + d->size;
+        T *b = p->array;
         while (i != b)
             *--i = copy;
     }
@@ -629,9 +619,9 @@ QVector<T> &QVector<T>::operator+=(const QVector &l)
     int newSize = d->size + l.d->size;
     realloc(d->size, newSize);
 
-    T *w = d->array + newSize;
-    T *i = l.d->array + l.d->size;
-    T *b = l.d->array;
+    T *w = p->array + newSize;
+    T *i = l.p->array + l.d->size;
+    T *b = l.p->array;
     while (i != b) {
         if (QTypeInfo<T>::isComplex)
             new (--w) T(*--i);
@@ -648,11 +638,11 @@ int QVector<T>::indexOf(const T &t, int from) const
     if (from < 0)
         from = qMax(from + d->size, 0);
     if (from < d->size) {
-        T* n = d->array + from - 1;
-        T* e = d->array + d->size;
+        T* n = p->array + from - 1;
+        T* e = p->array + d->size;
         while (++n != e)
             if (*n == t)
-                return n - d->array;
+                return n - p->array;
     }
     return -1;
 }
@@ -665,8 +655,8 @@ int QVector<T>::lastIndexOf(const T &t, int from) const
     else if (from >= d->size)
         from = d->size-1;
     if (from >= 0) {
-        T* b = d->array;
-        T* n = d->array + from + 1;
+        T* b = p->array;
+        T* n = p->array + from + 1;
         while (n != b) {
             if (*--n == t)
                 return n - b;
@@ -678,8 +668,8 @@ int QVector<T>::lastIndexOf(const T &t, int from) const
 template <typename T>
 bool QVector<T>::contains(const T &t) const
 {
-    T* b = d->array;
-    T* i = d->array + d->size;
+    T* b = p->array;
+    T* i = p->array + d->size;
     while (i != b)
         if (*--i == t)
             return true;
@@ -690,8 +680,8 @@ template <typename T>
 int QVector<T>::count(const T &t) const
 {
     int c = 0;
-    T* b = d->array;
-    T* i = d->array + d->size;
+    T* b = p->array;
+    T* i = p->array + d->size;
     while (i != b)
         if (*--i == t)
             ++c;
diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri
index e5bf7e4..aaf3f21 100644
--- a/src/corelib/tools/tools.pri
+++ b/src/corelib/tools/tools.pri
@@ -19,6 +19,7 @@ HEADERS +=  \
 	tools/qlocale_p.h \
 	tools/qlocale_data_p.h \
 	tools/qmap.h \
+        tools/qcontiguouscache.h \
         tools/qpodlist_p.h \
         tools/qpoint.h \
 	tools/qqueue.h \
@@ -53,6 +54,7 @@ SOURCES += \
 	tools/qlocale.cpp \
         tools/qpoint.cpp \
 	tools/qmap.cpp \
+	tools/qcontiguouscache.cpp \
         tools/qrect.cpp \
 	tools/qregexp.cpp \
 	tools/qshareddata.cpp \