Squashed commit of the following:

commit 39de3862f5678b3226b4932eeb342c4a023d2f2b
Author: Ian Walters <ian.walters@nokia.com>
Date:   Thu Feb 19 14:16:05 2009 +1000

    Fixes:    Test runs (and passes), doc links.

    Task:     QT-308
    Details:  Minor changes related to the code
    having moved.

commit 5a8910dd1018fb228d0e2e2819ea429577bfa834
Author: Ian Walters <ian.walters@nokia.com>
Date:   Thu Feb 19 09:47:20 2009 +1000

    Fixes:    Checkin of QOffsetVector stuff for branch

    Task:     QT-308
    Details:  Files originally from research/qcircularbuffer
    This checkin likely won't compile. Just a copy for now.

12 files changed, 1295 insertions, 0 deletions

diff --git a/doc/src/examples/offsetvector.qdoc b/doc/src/examples/offsetvector.qdoc
new file mode 100644
index 0000000..256569e
--- /dev/null
+++ b/doc/src/examples/offsetvector.qdoc
@@ -0,0 +1,70 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the $MODULE$ of the Qt Toolkit.
+**
+** $TROLLTECH_DUAL_LICENSE$
+**
+****************************************************************************/
+
+/*!
+    \example tools/offsetvector
+    \title Offset Vector Example
+
+    The Offset Vector example shows how to use QOffsetVector to manage memory usage for
+    very large models.  In some environments memory is limited, and even when it
+    isn't users still dislike an application using
+    excessive memory.  Using QOffsetVector to manage a list rather than loading
+    the entire list into memory allows the application to limit the amount
+    of memory it uses regardless of the size of the data set it accesses
+
+    The simplest way to use QOffsetVector is to cache as items are requested. When
+    a view requests an item at row N it is also likely to ask for items at rows near
+    to N.
+
+    \snippet examples/tools/offsetvector/randomlistmodel.cpp 0
+
+    After getting the row the class determines if the row is in the bounds
+    of the offset vector's current range.  It would have been equally valid to
+    simply have the following code instead.
+
+    \code
+    while (row > m_words.lastIndex())
+        m_words.append(fetchWord(m_words.lastIndex()+1);
+    while (row < m_words.firstIndex())
+        m_words.prepend(fetchWord(m_words.firstIndex()-1);
+    \endcode
+
+    However a list will often jump rows if the scroll bar is used directly, and
+    the above code would cause every row between where the cache was last centered
+    to where the cache is currently centered to be cached before the requested
+    row is reached.
+
+    Using QOffsetVector::lastIndex() and QOffsetVector::firstIndex() allows
+    the example to determine where the list the vector is currently over.  These values
+    don't represent the indexes into the vector own memory, but rather a virtual
+    infinite array that the vector represents.
+
+    By using QOffsetVector::append() and QOffsetVector::prepend() the code ensures
+    that items that may be still on the screen are not lost when the requested row
+    has not moved far from the current vector range.  QOffsetVector::insert() can
+    potentially remove more than one item from the cache as QOffsetVector does not
+    allow for gaps.  If your cache needs to quickly jump back and forth between
+    rows with significant gaps between them consider using QCache instead.
+
+    And thats it.  A perfectly reasonable cache, using minimal memory for a very large
+    list.  In this case the accessor for getting the words into cache:
+
+    \snippet examples/tools/offsetvector/randomlistmodel.cpp 1
+
+    Generates random information rather than fixed information.  This allows you 
+    to see how the cache range is kept for a local number of rows when running the
+    example.
+
+    It is also worth considering pre-fetching items into the cache outside of the
+    applications paint routine.  This can be done either with a separate thread
+    or using a QTimer to incrementally expand the range of the thread prior to
+    rows being requested out of the current vector range.
+*/
diff --git a/examples/tools/offsetvector/main.cpp b/examples/tools/offsetvector/main.cpp
new file mode 100644
index 0000000..bdeb3f3
--- /dev/null
+++ b/examples/tools/offsetvector/main.cpp
@@ -0,0 +1,15 @@
+#include "randomlistmodel.h"
+#include <QListView>
+#include <QApplication>
+
+int main(int c, char **v)
+{
+    QApplication a(c, v);
+
+    QListView view;
+    view.setUniformItemSizes(true);
+    view.setModel(new RandomListModel(&view));
+    view.show();
+
+    return a.exec();
+}
diff --git a/examples/tools/offsetvector/offsetvector.pro b/examples/tools/offsetvector/offsetvector.pro
new file mode 100644
index 0000000..f329bb9
--- /dev/null
+++ b/examples/tools/offsetvector/offsetvector.pro
@@ -0,0 +1,9 @@
+HEADERS       = randomlistmodel.h
+SOURCES       = randomlistmodel.cpp \
+                main.cpp
+
+# install
+target.path = $$[QT_INSTALL_EXAMPLES]/tools/offsetvector
+sources.files = $$SOURCES $$HEADERS $$RESOURCES $$FORMS offsetvector.pro
+sources.path = $$[QT_INSTALL_EXAMPLES]/tools/offsetvector
+INSTALLS += target sources
diff --git a/examples/tools/offsetvector/randomlistmodel.cpp b/examples/tools/offsetvector/randomlistmodel.cpp
new file mode 100644
index 0000000..5c0953b
--- /dev/null
+++ b/examples/tools/offsetvector/randomlistmodel.cpp
@@ -0,0 +1,56 @@
+#include "randomlistmodel.h"
+
+static const int bufferSize(500);
+static const int lookAhead(100);
+static const int halfLookAhead(lookAhead/2);
+
+RandomListModel::RandomListModel(QObject *parent)
+: QAbstractListModel(parent), m_rows(bufferSize), m_count(10000)
+{
+}
+
+RandomListModel::~RandomListModel()
+{
+}
+
+int RandomListModel::rowCount(const QModelIndex &) const
+{
+    return m_count;
+}
+
+//! [0]
+QVariant RandomListModel::data(const QModelIndex &index, int role) const
+{
+    if (role != Qt::DisplayRole)
+        return QVariant();
+
+    int row = index.row();
+
+    if (row > m_rows.lastIndex()) {
+        if (row - m_rows.lastIndex() > lookAhead)
+            cacheRows(row-halfLookAhead, qMin(m_count, row+halfLookAhead));
+        else while (row > m_rows.lastIndex())
+            m_rows.append(fetchRow(m_rows.lastIndex()+1));
+    } else if (row < m_rows.firstIndex()) {
+        if (m_rows.firstIndex() - row > lookAhead)
+            cacheRows(qMax(0, row-halfLookAhead), row+halfLookAhead);
+        else while (row < m_rows.firstIndex())
+            m_rows.prepend(fetchRow(m_rows.firstIndex()-1));
+    }
+
+    return m_rows.at(row);
+}
+
+void RandomListModel::cacheRows(int from, int to) const
+{
+    for (int i = from; i <= to; ++i)
+        m_rows.insert(i, fetchRow(i));
+}
+//![0]
+
+//![1]
+QString RandomListModel::fetchRow(int position) const
+{
+    return QString::number(rand() % ++position);
+}
+//![1]
diff --git a/examples/tools/offsetvector/randomlistmodel.h b/examples/tools/offsetvector/randomlistmodel.h
new file mode 100644
index 0000000..e102255
--- /dev/null
+++ b/examples/tools/offsetvector/randomlistmodel.h
@@ -0,0 +1,26 @@
+#ifndef RANDOMLISTMODEL_H
+#define RANDOMLISTMODEL_H
+
+#include <QOffsetVector>
+#include <QAbstractListModel>
+
+class QTimer;
+class RandomListModel : public QAbstractListModel
+{
+    Q_OBJECT
+public:
+    RandomListModel(QObject *parent = 0);
+    ~RandomListModel();
+
+    int rowCount(const QModelIndex & = QModelIndex()) const;
+    QVariant data(const QModelIndex &, int) const;
+
+private:
+    void cacheRows(int, int) const;
+    QString fetchRow(int) const;
+
+    mutable QOffsetVector<QString> m_rows;
+    const int m_count;
+};
+
+#endif
diff --git a/examples/tools/tools.pro b/examples/tools/tools.pro
index 79f0faa..424f286 100644
--- a/examples/tools/tools.pro
+++ b/examples/tools/tools.pro
@@ -5,6 +5,7 @@ SUBDIRS       = codecs \
                 customcompleter \
                 echoplugin \
                 i18n \
+                offsetvector \
                 plugandpaintplugins \
                 plugandpaint \
                 regexp \
diff --git a/src/corelib/tools/qoffsetvector.cpp b/src/corelib/tools/qoffsetvector.cpp
new file mode 100644
index 0000000..32d2872
--- /dev/null
+++ b/src/corelib/tools/qoffsetvector.cpp
@@ -0,0 +1,360 @@
+/****************************************************************************
+**
+** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the $MODULE$ of the Qt Toolkit.
+**
+** $TROLLTECH_DUAL_LICENSE$
+**
+****************************************************************************/
+
+#include "qoffsetvector.h"
+#include <QDebug>
+
+void QOffsetVectorData::dump() const
+{
+    qDebug() << "capacity:" << alloc;
+    qDebug() << "count:" << count;
+    qDebug() << "start:" << start;
+    qDebug() << "offset:" << offset;
+}
+
+/*! \class QOffsetVector
+    \brief The QOffsetVector class is a template class that provides a offset vector.
+    \ingroup tools
+    \ingroup shared
+    \reentrant
+
+    The QOffsetVector class provides an efficient way of caching items for
+    display in a user interface view.  It does this by providing a window
+    into a theoretical infinite sized vector.  This has the advantage that
+    it matches how user interface views most commonly request the data, in
+    a set of rows localized around the current scrolled position.  It also
+    allows the cache to use less overhead than QCache both in terms of
+    performance and memory.  In turn, unlike a QCache, the key has to be
+    an int and has to be contiguous.  That is to say if an item is inserted
+    at index 85, then if there were no previous items at 84 or 86 then the
+    cache will be cleared before the new item at 85 is inserted.  If this
+    restriction is not suitable consider using QCache instead.
+
+    The simplest way of using an offset vector is to use the append()
+    and prepend() functions to slide the window to where it is needed.
+
+\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
+    
+    The append() and prepend() functions cause the vector window to move to
+    where the current row is requested from.  This usage can be further
+    optimized by using the insert() function to reset the vector window to
+    a row in the case where the row is a long way from the current row.  It
+    may also be worth while to fetch multiple records into the cache if
+    it is faster to retrieve them in a batch operation.
+
+    See the The \l{Offset Vector Example}{Offset Vector} example.
+*/
+
+/*! \fn QOffsetVector::QOffsetVector(int capacity)
+
+    Constructs a vector with the given \a capacity.
+
+    \sa setCapacity()
+*/
+
+/*! \fn QOffsetVector::QOffsetVector(const QOffsetVector<T> &other)
+
+    Constructs a copy of \a other.
+
+    This operation takes \l{constant time}, because QOffsetVector is
+    \l{implicitly shared}.  This makes returning a QOffsetVector 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 QOffsetVector::~QOffsetVector()
+    Destorys the vector.
+*/
+
+/*! \fn void QOffsetVector::detach()
+
+    \internal
+*/
+
+/*! \fn bool QOffsetVector::isDetached() const
+
+    \internal
+*/
+
+/*! \fn void QOffsetVector::setSharable(bool sharable)
+
+    \internal
+*/
+
+
+/*! \fn QOffsetVector<T> &QOffsetVector::operator=(const QOffsetVector<T> &other)
+
+    Assigns \a other to this vector and returns a reference to this vector.
+*/
+
+/*! \fn bool QOffsetVector::operator==(const QOffsetVector<T> &other) const
+
+    Returns true if \a other is equal to this vector; otherwise returns false.
+
+    Two vectors 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 QOffsetVector::operator!=(const QOffsetVector<T> &other) const
+
+    Returns true if \a other is not equal to this vector; otherwise
+    returns false.
+
+    Two vector 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 QOffsetVector::capacity() const
+    
+    Returns the number of items the vector can store before it is full.
+    When a vector contains a number of items equal to its capacity, adding new
+    items will cause items furthest from the added item to be removed.
+
+    \sa setCapacity(), size()
+*/
+
+/*! \fn int QOffsetVector::count() const
+
+    \overload
+
+    Same as size().
+*/
+
+/*! \fn int QOffsetVector::size() const
+
+    Returns the number of items contained within the vector.
+
+    \sa capacity()
+*/
+
+/*! \fn bool QOffsetVector::isEmpty() const
+
+    Returns true if no items are stored within the vector.
+
+    \sa size(), capacity()
+*/
+
+/*! \fn bool QOffsetVector::isFull() const
+
+    Returns true if the number of items stored within the vector is equal
+    to the capacity of the vector.
+
+    \sa size(), capacity()
+*/
+
+/*! \fn int QOffsetVector::available() const
+
+    Returns the number of items that can be added to the vector before it becomes full.
+
+    \sa size(), capacity(), isFull()
+*/
+
+/*! \fn void QOffsetVector::clear()
+
+    Removes all items from the vector.  The capacity is unchanged.
+*/
+
+/*! \fn void QOffsetVector::setCapacity(int size)
+
+    Sets the capacity of the vector to the given \a size.  A vector can hold a
+    number of items equal to its capacity.  When inserting, appending or prepending
+    items to the vector, if the vector is already full then the item furthest from
+    the added item will be removed.
+
+    If the given \a size is smaller than the current count of items in the vector
+    then only the last \a size items from the vector will remain.
+
+    \sa capacity(), isFull()
+*/
+
+/*! \fn const T &QOffsetVector::at(int i) const
+
+    Returns the item at index position \a i in the vector.  \a i must
+    be a valid index position in the vector (i.e, firstIndex() <= \a i <= lastIndex()).
+
+    The indexes in the vector refer to number of positions the item is from the
+    first item appended into the vector.  That is to say a vector with a capacity of
+    100, that has had 150 items appended will have a valid index range of
+    50 to 149.  This allows inserting an retrieving items into the vector based
+    on a theoretical infinite list
+
+    \sa firstIndex(), lastIndex(), insert(), operator[]()
+*/
+
+/*! \fn T &QOffsetVector::operator[](int i)
+
+    Returns the item at index position \a i as a modifiable reference.  If
+    the vector 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 QOffsetVector to do a deep
+    copy.
+
+    \sa insert(), at()
+*/
+
+/*! \fn const T &QOffsetVector::operator[](int i) const
+
+    \overload
+
+    Same as at(\a i).
+*/
+
+/*! \fn void QOffsetVector::append(const T &value)
+
+    Inserts \a value at the end of the vector.  If the vector is already full
+    the item at the start of the vector will be removed.
+
+    \sa prepend(), insert(), isFull()
+*/
+
+/*! \fn void QOffsetVector::prepend(const T &value)
+
+    Inserts \a value at the start of the vector.  If the vector is already full
+    the item at the end of the vector will be removed.
+
+    \sa append(), insert(), isFull()
+*/
+
+/*! \fn void QOffsetVector::insert(int i, const T &value)
+
+    Inserts the \a value at the index position \a i.  If the vector 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 vector nor adjacent
+    to the bounds of the vector's index range the vector is first cleared before
+    inserting the item.  At this point the vector will have a size of 1.  It is worth
+    while then taking effort to insert items in an order than starts adjacent to the
+    current index range for the vector.
+
+    \sa prepend(), append(), isFull(), firstIndex(), lastIndex()
+*/
+
+/*! \fn bool QOffsetVector::containsIndex(int i) const
+
+    Returns true if the vector's index range includes the given index \a i.
+
+    \sa firstIndex(), lastIndex()
+*/
+
+/*! \fn int QOffsetVector::firstIndex() const
+    Returns the first valid index in the vector.  The index will be invalid if the
+    vector is empty.  However the following code is valid even when the vector is empty:
+
+    \code
+    for (int i = vector.firstIndex(); i <= vector.lastIndex(); ++i)
+        qDebug() << "Item" << i << "of the vector is" << vector.at(i);
+    \endcode
+
+    \sa capacity(), size(), lastIndex()
+*/
+
+/*! \fn int QOffsetVector::lastIndex() const
+
+    Returns the last valid index in the vector.  If the vector is empty will return -1.
+
+    \code
+    for (int i = vector.firstIndex(); i <= vector.lastIndex(); ++i)
+        qDebug() << "Item" << i << "of the vector is" << vector.at(i);
+    \endcode
+
+    \sa capacity(), size(), firstIndex()
+*/
+
+
+/*! \fn T &QOffsetVector::first()
+
+    Returns a reference to the first item in the vector.  This function
+    assumes that the vector isn't empty.
+
+    \sa last(), isEmpty()
+*/
+
+/*! \fn T &QOffsetVector::last()
+
+    Returns a reference to the last item in the vector.  This function
+    assumes that the vector isn't empty.
+
+    \sa first(), isEmpty()
+*/
+
+/*! \fn const T& QOffsetVector::first() const
+
+    \overload
+*/
+
+/*! \fn const T& QOffsetVector::last() const
+
+    \overload
+*/
+
+/*! \fn void QOffsetVector::removeFirst()
+    
+    Removes the first item from the vector.  This function assumes that
+    the vector isn't empty.
+
+    \sa removeLast()
+*/
+
+/*! \fn void QOffsetVector::removeLast()
+    
+    Removes the last item from the vector.  This function assumes that
+    the vector isn't empty.
+
+    \sa removeFirst()
+*/
+
+/*! \fn T QOffsetVector::takeFirst()
+    
+    Removes the first item in the vector and returns it.
+
+    If you don't sue the return value, removeFirst() is more efficient.
+
+    \sa takeLast(), removeFirst()
+*/
+
+/*! \fn T QOffsetVector::takeLast()
+    
+    Removes the last item in the vector and returns it.
+
+    If you don't sue the return value, removeLast() is more efficient.
+
+    \sa takeFirst(), removeLast()
+*/
+
+/*! \fn void QOffsetVector::dump() const
+
+    \internal
+
+    Sends information about the vector's internal structure to qDebug()
+*/
diff --git a/src/corelib/tools/qoffsetvector.h b/src/corelib/tools/qoffsetvector.h
new file mode 100644
index 0000000..7030862
--- /dev/null
+++ b/src/corelib/tools/qoffsetvector.h
@@ -0,0 +1,386 @@
+/****************************************************************************
+**
+** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the $MODULE$ of the Qt Toolkit.
+**
+** $TROLLTECH_DUAL_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QCIRCULARBUFFER_H
+#define QCIRCULARBUFFER_H
+
+#include <QtCore/qatomic.h>
+
+struct QOffsetVectorData
+{
+    QBasicAtomicInt ref;
+    int alloc;
+    int count;
+    int start;
+    int offset;
+    uint sharable : 1;
+
+    void dump() const;
+};
+
+template <typename T>
+struct QOffsetVectorTypedData
+{
+    QBasicAtomicInt ref;
+    int alloc;
+    int count;
+    int start;
+    int offset;
+    uint sharable : 1;
+
+    T array[1];
+};
+
+class QOffsetVectorDevice;
+
+template<typename T>
+class QOffsetVector {
+    typedef QOffsetVectorTypedData<T> Data;
+    union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; };
+public:
+    explicit QOffsetVector(int capacity = 0);
+    QOffsetVector(const QOffsetVector<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
+
+    inline ~QOffsetVector() { 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; }
+
+    QOffsetVector<T> &operator=(const QOffsetVector<T> &other);
+    bool operator==(const QOffsetVector<T> &other) const;
+    inline bool operator!=(const QOffsetVector<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();
+
+    // debug
+    void dump() const { p->dump(); }
+private:
+    void detach_helper();
+
+    QOffsetVectorData *malloc(int alloc);
+    void free(Data *d);
+    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 QOffsetVector<T>::detach_helper()
+{
+    union { QOffsetVectorData *p; QOffsetVectorTypedData<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 QOffsetVector<T>::setCapacity(int asize)
+{
+    if (asize == d->alloc)
+        return;
+    detach();
+    union { QOffsetVectorData *p; QOffsetVectorTypedData<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;
+    /*  deep copy -
+        slow way now, get unit test working, then
+        improve performance if need be. (e.g. memcpy)
+    */
+    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 QOffsetVector<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 { QOffsetVectorData *p; QOffsetVectorTypedData<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 QOffsetVectorData *QOffsetVector<T>::malloc(int aalloc)
+{
+    return static_cast<QOffsetVectorData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
+}
+
+template <typename T>
+QOffsetVector<T>::QOffsetVector(int asize)
+{
+    p = malloc(asize);
+    d->ref = 1;
+    d->alloc = asize;
+    d->count = d->start = d->offset = 0;
+    d->sharable = true;
+}
+
+template <typename T>
+QOffsetVector<T> &QOffsetVector<T>::operator=(const QOffsetVector<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 QOffsetVector<T>::operator==(const QOffsetVector<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 QOffsetVector<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 QOffsetVector<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 QOffsetVector<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 QOffsetVector<T>::insert(int pos, const T &value)
+{
+    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 = d->start = pos;
+        d->start %= 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 &QOffsetVector<T>::at(int pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QOffsetVector<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
+template <typename T>
+inline const T &QOffsetVector<T>::operator[](int pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QOffsetVector<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
+template <typename T>
+
+// can use the non-inline one to modify the index range.
+inline T &QOffsetVector<T>::operator[](int pos)
+{
+    detach();
+    if (!containsIndex(pos))
+        insert(pos, T());
+    return d->array[pos % d->alloc];
+}
+
+template <typename T>
+inline void QOffsetVector<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 QOffsetVector<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 QOffsetVector<T>::takeFirst()
+{ T t = first(); removeFirst(); return t; }
+
+template <typename T>
+inline T QOffsetVector<T>::takeLast()
+{ T t = last(); removeLast(); return t; }
+
+#endif
diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri
index e5bf7e4..626c9e5 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/qoffsetvector.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/qoffsetvector.cpp \
         tools/qrect.cpp \
 	tools/qregexp.cpp \
 	tools/qshareddata.cpp \
diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro
index 19f6b43..5d71e79 100644
--- a/tests/auto/auto.pro
+++ b/tests/auto/auto.pro
@@ -209,6 +209,7 @@ SUBDIRS += bic \
            qnumeric \
            qobject \
            qobjectrace \
+           qoffsetvector \
            qpaintengine \
            qpainter \
            qpainterpath \
diff --git a/tests/auto/qoffsetvector/qoffsetvector.pro b/tests/auto/qoffsetvector/qoffsetvector.pro
new file mode 100644
index 0000000..0b801f3
--- /dev/null
+++ b/tests/auto/qoffsetvector/qoffsetvector.pro
@@ -0,0 +1,8 @@
+load(qttest_p4)
+
+QT = core
+
+SOURCES  += tst_qoffsetvector.cpp
+
+
+
diff --git a/tests/auto/qoffsetvector/tst_qoffsetvector.cpp b/tests/auto/qoffsetvector/tst_qoffsetvector.cpp
new file mode 100644
index 0000000..439ea2c
--- /dev/null
+++ b/tests/auto/qoffsetvector/tst_qoffsetvector.cpp
@@ -0,0 +1,361 @@
+/****************************************************************************
+**
+** This file is part of the $PACKAGE_NAME$.
+**
+** Copyright (C) $THISYEAR$ $COMPANY_NAME$.
+**
+** $QT_EXTENDED_DUAL_LICENSE$
+**
+****************************************************************************/
+
+#include <QObject>
+#include <QTest>
+#include <QList>
+#include <QString>
+#include <QCache>
+#include <QOffsetVector>
+
+#include <QDebug>
+#include <stdio.h>
+
+
+#if defined(FORCE_UREF)
+template <class aT>
+inline QDebug &operator<<(QDebug debug, const QOffsetVector<aT> &offsetVector)
+#else
+template <class aT>
+inline QDebug operator<<(QDebug debug, const QOffsetVector<aT> &offsetVector)
+#endif
+{
+    debug.nospace() << "QOffsetVector(";
+    for (int i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) {
+        debug << offsetVector[i];
+        if (i != offsetVector.lastIndex())
+            debug << ", ";
+    }
+    debug << ")";
+    return debug.space();
+}
+
+#if defined(NO_BENCHMARK) and defined(QBENCHMARK)
+#undef QBENCHMARK
+#define QBENCHMARK
+#endif
+
+class tst_QOffsetVector : public QObject
+{
+    Q_OBJECT
+public:
+    tst_QOffsetVector() {}
+    virtual ~tst_QOffsetVector() {}
+private slots:
+    void empty();
+    void forwardBuffer();
+    void scrollingList();
+
+    void complexType();
+
+    void operatorAt();
+
+    void cacheBenchmark();
+    void offsetVectorBenchmark();
+
+    void setCapacity();
+};
+
+QTEST_MAIN(tst_QOffsetVector)
+
+void tst_QOffsetVector::empty()
+{
+    QOffsetVector<int> c(10);
+    QCOMPARE(c.capacity(), 10);
+    QCOMPARE(c.count(), 0);
+    QVERIFY(c.isEmpty());
+    c.append(1);
+    QVERIFY(!c.isEmpty());
+    c.clear();
+    QCOMPARE(c.capacity(), 10);
+    QCOMPARE(c.count(), 0);
+    QVERIFY(c.isEmpty());
+    c.prepend(1);
+    QVERIFY(!c.isEmpty());
+    c.clear();
+    QCOMPARE(c.count(), 0);
+    QVERIFY(c.isEmpty());
+    QCOMPARE(c.capacity(), 10);
+}
+
+void tst_QOffsetVector::forwardBuffer()
+{
+    int i;
+    QOffsetVector<int> c(10);
+    for(i = 1; i < 30; ++i) {
+        c.append(i);
+        QCOMPARE(c.first(), qMax(1, i-9));
+        QCOMPARE(c.last(), i);
+        QCOMPARE(c.count(), qMin(i, 10));
+    }
+
+    c.clear();
+
+    for(i = 1; i < 30; ++i) {
+        c.prepend(i);
+        QCOMPARE(c.last(), qMax(1, i-9));
+        QCOMPARE(c.first(), i);
+        QCOMPARE(c.count(), qMin(i, 10));
+    }
+}
+
+void tst_QOffsetVector::scrollingList()
+{
+    int i;
+    QOffsetVector<int> c(10);
+
+    // Once allocated QOffsetVector should not
+    // allocate any additional memory for non
+    // complex data types.
+    QBENCHMARK {
+        // simulate scrolling in a list of items;
+        for(i = 0; i < 10; ++i)
+            c.append(i);
+
+        QCOMPARE(c.firstIndex(), 0);
+        QCOMPARE(c.lastIndex(), 9);
+        QVERIFY(c.containsIndex(0));
+        QVERIFY(c.containsIndex(9));
+        QVERIFY(!c.containsIndex(10));
+
+        for (i = 0; i < 10; ++i)
+            QCOMPARE(c.at(i), i);
+
+        for (i = 10; i < 30; ++i)
+            c.append(i);
+
+        QCOMPARE(c.firstIndex(), 20);
+        QCOMPARE(c.lastIndex(), 29);
+        QVERIFY(c.containsIndex(20));
+        QVERIFY(c.containsIndex(29));
+        QVERIFY(!c.containsIndex(30));
+
+        for (i = 20; i < 30; ++i)
+            QCOMPARE(c.at(i), i);
+
+        for (i = 19; i >= 10; --i)
+            c.prepend(i);
+
+        QCOMPARE(c.firstIndex(), 10);
+        QCOMPARE(c.lastIndex(), 19);
+        QVERIFY(c.containsIndex(10));
+        QVERIFY(c.containsIndex(19));
+        QVERIFY(!c.containsIndex(20));
+
+        for (i = 10; i < 20; ++i)
+            QCOMPARE(c.at(i), i);
+
+        for (i = 200; i < 220; ++i)
+            c.insert(i, i);
+
+        QCOMPARE(c.firstIndex(), 210);
+        QCOMPARE(c.lastIndex(), 219);
+        QVERIFY(c.containsIndex(210));
+        QVERIFY(c.containsIndex(219));
+        QVERIFY(!c.containsIndex(300));
+        QVERIFY(!c.containsIndex(209));
+
+        for (i = 220; i < 220; ++i) {
+            QVERIFY(c.containsIndex(i));
+            QCOMPARE(c.at(i), i);
+        }
+        c.clear(); // needed to reset benchmark
+    }
+
+    // from a specific bug that was encountered.  100 to 299 cached, attempted to cache 250 - 205 via insert, failed.
+    // bug was that item at 150 would instead be item that should have been inserted at 250
+    c.setCapacity(200);
+    for(i = 100; i < 300; ++i)
+        c.insert(i, i);
+    for (i = 250; i <= 306; ++i)
+        c.insert(i, 1000+i);
+    for (i = 107; i <= 306; ++i) {
+        QVERIFY(c.containsIndex(i));
+        QCOMPARE(c.at(i), i < 250 ? i : 1000+i);
+    }
+}
+
+struct RefCountingClassData
+{
+    QBasicAtomicInt ref;
+    static RefCountingClassData shared_null;
+};
+
+RefCountingClassData RefCountingClassData::shared_null = {
+    Q_BASIC_ATOMIC_INITIALIZER(1)
+};
+
+class RefCountingClass
+{
+public:
+    RefCountingClass() : d(&RefCountingClassData::shared_null) { d->ref.ref(); }
+
+    RefCountingClass(const RefCountingClass &other)
+    {
+        d = other.d;
+        d->ref.ref();
+    }
+
+    ~RefCountingClass()
+    {
+        if (!d->ref.deref())
+            delete d;
+    }
+
+    RefCountingClass &operator=(const RefCountingClass &other)
+    {
+        if (!d->ref.deref())
+            delete d;
+        d = other.d;
+        d->ref.ref();
+        return *this;
+    }
+
+    int refCount() const { return d->ref; }
+private:
+    RefCountingClassData *d;
+};
+
+void tst_QOffsetVector::complexType()
+{
+    RefCountingClass original;
+
+    QOffsetVector<RefCountingClass> offsetVector(10);
+    offsetVector.append(original);
+    QCOMPARE(original.refCount(), 3);
+    offsetVector.removeFirst();
+    QCOMPARE(original.refCount(), 2); // shared null, 'original'.
+    offsetVector.append(original);
+    QCOMPARE(original.refCount(), 3);
+    offsetVector.clear();
+    QCOMPARE(original.refCount(), 2);
+
+    for(int i = 0; i < 100; ++i)
+        offsetVector.insert(i, original);
+
+    QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector.
+
+    offsetVector.clear();
+    QCOMPARE(original.refCount(), 2);
+    for (int i = 0; i < 100; i++)
+        offsetVector.append(original);
+
+    QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector.
+    offsetVector.clear();
+    QCOMPARE(original.refCount(), 2);
+
+    for (int i = 0; i < 100; i++)
+        offsetVector.prepend(original);
+
+    QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector.
+    offsetVector.clear();
+    QCOMPARE(original.refCount(), 2);
+
+    for (int i = 0; i < 100; i++)
+        offsetVector.append(original);
+
+    offsetVector.takeLast();
+    QCOMPARE(original.refCount(), 11);
+
+    offsetVector.takeFirst();
+    QCOMPARE(original.refCount(), 10);
+}
+
+void tst_QOffsetVector::operatorAt()
+{
+    RefCountingClass original;
+    QOffsetVector<RefCountingClass> offsetVector(10);
+
+    for (int i = 25; i < 35; ++i)
+        offsetVector[i] = original;
+
+    QCOMPARE(original.refCount(), 12); // shared null, orig, items in vector
+
+    // verify const access does not copy items.
+    const QOffsetVector<RefCountingClass> copy(offsetVector);
+    for (int i = 25; i < 35; ++i)
+        QCOMPARE(copy[i].refCount(), 12);
+
+    // verify modifying the original increments ref count (e.g. does a detach)
+    offsetVector[25] = original;
+    QCOMPARE(original.refCount(), 22);
+}
+
+/*
+    Benchmarks must be near identical in tasks to be fair.
+    QCache uses pointers to ints as its a requirement of QCache,
+    whereas QOffsetVector doesn't support pointers (won't free them).
+    Given the ability to use simple data types is a benefit, its
+    fair.  Although this obviously must take into account we are
+    testing QOffsetVector use cases here, QCache has its own
+    areas where it is the more sensible class to use.
+*/
+void tst_QOffsetVector::cacheBenchmark()
+{
+    QBENCHMARK {
+        QCache<int, int> cache;
+        cache.setMaxCost(100);
+
+        for (int i = 0; i < 1000; i++)
+            cache.insert(i, new int(i));
+    }
+}
+
+void tst_QOffsetVector::offsetVectorBenchmark()
+{
+    QBENCHMARK {
+        QOffsetVector<int> offsetVector(100);
+        for (int i = 0; i < 1000; i++)
+            offsetVector.insert(i, i);
+    }
+}
+
+void tst_QOffsetVector::setCapacity()
+{
+    int i;
+    QOffsetVector<int> offsetVector(100);
+    for (i = 280; i < 310; ++i)
+        offsetVector.insert(i, i);
+    QCOMPARE(offsetVector.capacity(), 100);
+    QCOMPARE(offsetVector.count(), 30);
+    QCOMPARE(offsetVector.firstIndex(), 280);
+    QCOMPARE(offsetVector.lastIndex(), 309);
+
+    for (i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) {
+        QVERIFY(offsetVector.containsIndex(i));
+        QCOMPARE(offsetVector.at(i), i);
+    }
+
+    offsetVector.setCapacity(150);
+
+    QCOMPARE(offsetVector.capacity(), 150);
+    QCOMPARE(offsetVector.count(), 30);
+    QCOMPARE(offsetVector.firstIndex(), 280);
+    QCOMPARE(offsetVector.lastIndex(), 309);
+
+    for (i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) {
+        QVERIFY(offsetVector.containsIndex(i));
+        QCOMPARE(offsetVector.at(i), i);
+    }
+
+    offsetVector.setCapacity(20);
+
+    QCOMPARE(offsetVector.capacity(), 20);
+    QCOMPARE(offsetVector.count(), 20);
+    QCOMPARE(offsetVector.firstIndex(), 290);
+    QCOMPARE(offsetVector.lastIndex(), 309);
+
+    for (i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) {
+        QVERIFY(offsetVector.containsIndex(i));
+        QCOMPARE(offsetVector.at(i), i);
+    }
+}
+
+#include "tst_qoffsetvector.moc"