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.

3 files changed, 748 insertions, 0 deletions

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 \