Various fixes resulting from QA code review.

Some documentation fixes.
More clear handling of what is and isn't a valid indexes.
Added functions for the 'really long lived circular buffer use case'
Improved unit tests.

6 files changed, 217 insertions, 69 deletions

diff --git a/doc/src/examples/contiguouscache.qdoc b/doc/src/examples/contiguouscache.qdoc
index 71e7740..fbfde3f 100644
--- a/doc/src/examples/contiguouscache.qdoc
+++ b/doc/src/examples/contiguouscache.qdoc
@@ -61,10 +61,10 @@
     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);
+    while (row > m_rows.lastIndex())
+        m_rows.append(fetchWord(m_rows.lastIndex()+1);
+    while (row < m_rows.firstIndex())
+        m_rows.prepend(fetchWord(m_rows.firstIndex()-1);
     \endcode
 
     However a list will often jump rows if the scroll bar is used directly, resulting in
diff --git a/src/corelib/io/qdebug.h b/src/corelib/io/qdebug.h
index 6c05756..9b0fbe5 100644
--- a/src/corelib/io/qdebug.h
+++ b/src/corelib/io/qdebug.h
@@ -235,7 +235,7 @@ inline QDebug operator<<(QDebug debug, const QSet<T> &set)
 
 #if defined(FORCE_UREF)
 template <class T>
-inline QDebug &operator<<(QDebug debug, const QContiguousCache<T> &contiguousCache)
+inline QDebug &operator<<(QDebug debug, const QContiguousCache<T> &cache)
 #else
 template <class T>
 inline QDebug operator<<(QDebug debug, const QContiguousCache<T> &cache)
diff --git a/src/corelib/tools/qcontiguouscache.cpp b/src/corelib/tools/qcontiguouscache.cpp
index 95fa9e7..6671982 100644
--- a/src/corelib/tools/qcontiguouscache.cpp
+++ b/src/corelib/tools/qcontiguouscache.cpp
@@ -62,9 +62,10 @@ void QContiguousCacheData::dump() const
     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.  It also
-    allows the cache to consume less memory and processor cycles than QCache
-    for this use-case.
+    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().
@@ -83,8 +84,8 @@ MyRecord record(int row) const
 }
 \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.
+    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
@@ -93,6 +94,19 @@ MyRecord record(int row) const
     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 be used.
+
     See the \l{Contiguous Cache Example}{Contiguous Cache} example.
 */
 
@@ -288,6 +302,10 @@ MyRecord record(int row) const
     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()
 */
 
@@ -301,24 +319,14 @@ MyRecord record(int row) const
 /*! \fn int QContiguousCache::firstIndex() const
 
     Returns the first valid index in the cache.  The index will be invalid if the
-    cache is empty.  However the following code is valid even when the cache is empty:
-
-    \code
-    for (int i = cache.firstIndex(); i <= cache.lastIndex(); ++i)
-        qDebug() << "Item" << i << "of the cache is" << cache.at(i);
-    \endcode
+    cache is empty.
 
     \sa capacity(), size(), lastIndex()
 */
 
 /*! \fn int QContiguousCache::lastIndex() const
 
-    Returns the last valid index in the cache.  If the cache is empty will return -1.
-
-    \code
-    for (int i = cache.firstIndex(); i <= cache.lastIndex(); ++i)
-        qDebug() << "Item" << i << "of the cache is" << cache.at(i);
-    \endcode
+    Returns the last valid index in the cache.  The index will be invalid if the cache is empty.
 
     \sa capacity(), size(), firstIndex()
 */
@@ -386,6 +394,37 @@ MyRecord record(int row) const
     \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
diff --git a/src/corelib/tools/qcontiguouscache.h b/src/corelib/tools/qcontiguouscache.h
index 5250a79..5cd1582 100644
--- a/src/corelib/tools/qcontiguouscache.h
+++ b/src/corelib/tools/qcontiguouscache.h
@@ -43,6 +43,7 @@
 #define QCONTIGUOUSCACHE_H
 
 #include <QtCore/qatomic.h>
+#include <limits.h>
 
 QT_BEGIN_HEADER
 
@@ -50,7 +51,7 @@ QT_BEGIN_NAMESPACE
 
 QT_MODULE(Core)
 
-struct QContiguousCacheData
+struct Q_CORE_EXPORT QContiguousCacheData
 {
     QBasicAtomicInt ref;
     int alloc;
@@ -75,8 +76,6 @@ struct QContiguousCacheTypedData
     T array[1];
 };
 
-class QContiguousCacheDevice;
-
 template<typename T>
 class QContiguousCache {
     typedef QContiguousCacheTypedData<T> Data;
@@ -128,13 +127,17 @@ public:
     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 alloc);
-    void free(Data *d);
+    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
@@ -189,10 +192,6 @@ void QContiguousCache<T>::setCapacity(int 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;
@@ -249,11 +248,11 @@ inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)
 }
 
 template <typename T>
-QContiguousCache<T>::QContiguousCache(int asize)
+QContiguousCache<T>::QContiguousCache(int capacity)
 {
-    p = malloc(asize);
+    p = malloc(capacity);
     d->ref = 1;
-    d->alloc = asize;
+    d->alloc = capacity;
     d->count = d->start = d->offset = 0;
     d->sharable = true;
 }
@@ -302,7 +301,6 @@ void QContiguousCache<T>::free(Data *x)
     }
     qFree(x);
 }
-
 template <typename T>
 void QContiguousCache<T>::append(const T &value)
 {
@@ -349,6 +347,7 @@ void QContiguousCache<T>::prepend(const T &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)
@@ -362,8 +361,8 @@ void QContiguousCache<T>::insert(int pos, const T &value)
     else {
         // we don't leave gaps.
         clear();
-        d->offset = d->start = pos;
-        d->start %= d->alloc;
+        d->offset = pos;
+        d->start = pos % d->alloc;
         d->count = 1;
         if (QTypeInfo<T>::isComplex)
             new (d->array + d->start) T(value);
@@ -378,9 +377,8 @@ inline const T &QContiguousCache<T>::at(int pos) const
 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>
 
-// can use the non-inline one to modify the index range.
+template <typename T>
 inline T &QContiguousCache<T>::operator[](int pos)
 {
     detach();
diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro
index cfd9525..1f972bf 100644
--- a/tests/auto/auto.pro
+++ b/tests/auto/auto.pro
@@ -209,7 +209,7 @@ SUBDIRS += bic \
            qnumeric \
            qobject \
            qobjectrace \
-           qoffsetvector \
+           qcontiguouscache \
            qpaintengine \
            qpainter \
            qpainterpath \
diff --git a/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp b/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp
index 91f6a9c..6d59390 100644
--- a/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp
+++ b/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp
@@ -41,8 +41,6 @@
 
 #include <QObject>
 #include <QTest>
-#include <QList>
-#include <QString>
 #include <QCache>
 #include <QContiguousCache>
 
@@ -57,8 +55,13 @@ public:
     virtual ~tst_QContiguousCache() {}
 private slots:
     void empty();
-    void forwardBuffer();
-    void scrollingList();
+    void append_data();
+    void append();
+
+    void prepend_data();
+    void prepend();
+
+    void asScrollingList();
 
     void complexType();
 
@@ -79,12 +82,14 @@ void tst_QContiguousCache::empty()
     QCOMPARE(c.count(), 0);
     QVERIFY(c.isEmpty());
     c.append(1);
+    QCOMPARE(c.count(), 1);
     QVERIFY(!c.isEmpty());
     c.clear();
     QCOMPARE(c.capacity(), 10);
     QCOMPARE(c.count(), 0);
     QVERIFY(c.isEmpty());
     c.prepend(1);
+    QCOMPARE(c.count(), 1);
     QVERIFY(!c.isEmpty());
     c.clear();
     QCOMPARE(c.count(), 0);
@@ -92,28 +97,111 @@ void tst_QContiguousCache::empty()
     QCOMPARE(c.capacity(), 10);
 }
 
-void tst_QContiguousCache::forwardBuffer()
+void tst_QContiguousCache::append_data()
 {
-    int i;
-    QContiguousCache<int> c(10);
-    for(i = 1; i < 30; ++i) {
+    QTest::addColumn<int>("start");
+    QTest::addColumn<int>("count");
+    QTest::addColumn<int>("cacheSize");
+    QTest::addColumn<bool>("invalidIndexes");
+
+    QTest::newRow("0+30[10]") << 0 << 30 << 10 << false;
+    QTest::newRow("300+30[10]") << 300 << 30 << 10 << false;
+    QTest::newRow("MAX-10+30[10]") << INT_MAX-10 << 30 << 10 << true;
+}
+
+void tst_QContiguousCache::append()
+{
+    QFETCH(int, start);
+    QFETCH(int, count);
+    QFETCH(int, cacheSize);
+    QFETCH(bool, invalidIndexes);
+
+    int i, j;
+    QContiguousCache<int> c(cacheSize);
+
+    i = 1;
+    QCOMPARE(c.available(), cacheSize);
+    if (start == 0)
+        c.append(i++);
+    else
+        c.insert(start, i++);
+    while (i < count) {
         c.append(i);
-        QCOMPARE(c.first(), qMax(1, i-9));
+        QCOMPARE(c.available(), qMax(0, cacheSize - i));
+        QCOMPARE(c.first(), qMax(1, i-cacheSize+1));
         QCOMPARE(c.last(), i);
-        QCOMPARE(c.count(), qMin(i, 10));
+        QCOMPARE(c.count(), qMin(i, cacheSize));
+        QCOMPARE(c.isFull(), i >= cacheSize);
+        i++;
     }
 
-    c.clear();
+    QCOMPARE(c.areIndexesValid(), !invalidIndexes);
+    if (invalidIndexes)
+        c.normalizeIndexes();
+    QVERIFY(c.areIndexesValid());
+
+    // test taking from end until empty.
+    for (j = 0; j < cacheSize; j++, i--) {
+        QCOMPARE(c.takeLast(), i-1);
+        QCOMPARE(c.count(), cacheSize-j-1);
+        QCOMPARE(c.available(), j+1);
+        QVERIFY(!c.isFull());
+        QCOMPARE(c.isEmpty(), j==cacheSize-1);
+    }
+
+}
+
+void tst_QContiguousCache::prepend_data()
+{
+    QTest::addColumn<int>("start");
+    QTest::addColumn<int>("count");
+    QTest::addColumn<int>("cacheSize");
+    QTest::addColumn<bool>("invalidIndexes");
+
+    QTest::newRow("30-30[10]") << 30 << 30 << 10 << false;
+    QTest::newRow("300-30[10]") << 300 << 30 << 10 << false;
+    QTest::newRow("10-30[10]") << 10 << 30 << 10 << true;
+}
 
-    for(i = 1; i < 30; ++i) {
+void tst_QContiguousCache::prepend()
+{
+    QFETCH(int, start);
+    QFETCH(int, count);
+    QFETCH(int, cacheSize);
+    QFETCH(bool, invalidIndexes);
+
+    int i, j;
+    QContiguousCache<int> c(cacheSize);
+
+    i = 1;
+    QCOMPARE(c.available(), cacheSize);
+    c.insert(start, i++);
+    while(i < count) {
         c.prepend(i);
-        QCOMPARE(c.last(), qMax(1, i-9));
+        QCOMPARE(c.available(), qMax(0, cacheSize - i));
+        QCOMPARE(c.last(), qMax(1, i-cacheSize+1));
         QCOMPARE(c.first(), i);
-        QCOMPARE(c.count(), qMin(i, 10));
+        QCOMPARE(c.count(), qMin(i, cacheSize));
+        QCOMPARE(c.isFull(), i >= cacheSize);
+        i++;
+    }
+
+    QCOMPARE(c.areIndexesValid(), !invalidIndexes);
+    if (invalidIndexes)
+        c.normalizeIndexes();
+    QVERIFY(c.areIndexesValid());
+
+    // test taking from start until empty.
+    for (j = 0; j < cacheSize; j++, i--) {
+        QCOMPARE(c.takeFirst(), i-1);
+        QCOMPARE(c.count(), cacheSize-j-1);
+        QCOMPARE(c.available(), j+1);
+        QVERIFY(!c.isFull());
+        QCOMPARE(c.isEmpty(), j==cacheSize-1);
     }
 }
 
-void tst_QContiguousCache::scrollingList()
+void tst_QContiguousCache::asScrollingList()
 {
     int i;
     QContiguousCache<int> c(10);
@@ -123,55 +211,78 @@ void tst_QContiguousCache::scrollingList()
     // complex data types.
     QBENCHMARK {
         // simulate scrolling in a list of items;
-        for(i = 0; i < 10; ++i)
+        for(i = 0; i < 10; ++i) {
+            QCOMPARE(c.available(), 10-i);
             c.append(i);
+        }
 
         QCOMPARE(c.firstIndex(), 0);
         QCOMPARE(c.lastIndex(), 9);
-        QVERIFY(c.containsIndex(0));
-        QVERIFY(c.containsIndex(9));
+        QCOMPARE(c.first(), 0);
+        QCOMPARE(c.last(), 9);
+        QVERIFY(!c.containsIndex(-1));
         QVERIFY(!c.containsIndex(10));
+        QCOMPARE(c.available(), 0);
 
-        for (i = 0; i < 10; ++i)
+        for (i = 0; i < 10; ++i) {
+            QVERIFY(c.containsIndex(i));
             QCOMPARE(c.at(i), i);
+            QCOMPARE(c[i], i);
+            QCOMPARE(((const QContiguousCache<int>)c)[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));
+        QCOMPARE(c.first(), 20);
+        QCOMPARE(c.last(), 29);
+        QVERIFY(!c.containsIndex(19));
         QVERIFY(!c.containsIndex(30));
+        QCOMPARE(c.available(), 0);
 
-        for (i = 20; i < 30; ++i)
+        for (i = 20; i < 30; ++i) {
+            QVERIFY(c.containsIndex(i));
             QCOMPARE(c.at(i), i);
+            QCOMPARE(c[i], i);
+            QCOMPARE(((const QContiguousCache<int> )c)[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));
+        QCOMPARE(c.first(), 10);
+        QCOMPARE(c.last(), 19);
+        QVERIFY(!c.containsIndex(9));
         QVERIFY(!c.containsIndex(20));
+        QCOMPARE(c.available(), 0);
 
-        for (i = 10; i < 20; ++i)
+        for (i = 10; i < 20; ++i) {
+            QVERIFY(c.containsIndex(i));
             QCOMPARE(c.at(i), i);
+            QCOMPARE(c[i], i);
+            QCOMPARE(((const QContiguousCache<int> )c)[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));
+        QCOMPARE(c.first(), 210);
+        QCOMPARE(c.last(), 219);
         QVERIFY(!c.containsIndex(209));
+        QVERIFY(!c.containsIndex(300));
+        QCOMPARE(c.available(), 0);
 
-        for (i = 220; i < 220; ++i) {
+        for (i = 210; i < 220; ++i) {
             QVERIFY(c.containsIndex(i));
             QCOMPARE(c.at(i), i);
+            QCOMPARE(c[i], i);
+            QCOMPARE(((const QContiguousCache<int> )c)[i], i);
         }
         c.clear(); // needed to reset benchmark
     }