summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--doc/src/examples/contiguouscache.qdoc97
-rw-r--r--examples/tools/contiguouscache/contiguouscache.pro9
-rw-r--r--examples/tools/contiguouscache/main.cpp56
-rw-r--r--examples/tools/contiguouscache/randomlistmodel.cpp96
-rw-r--r--examples/tools/contiguouscache/randomlistmodel.h66
-rw-r--r--examples/tools/tools.pro1
-rw-r--r--src/corelib/io/qdebug.h19
-rw-r--r--src/corelib/tools/qcontiguouscache.cpp435
-rw-r--r--src/corelib/tools/qcontiguouscache.h424
-rw-r--r--src/corelib/tools/tools.pri2
-rw-r--r--tests/auto/auto.pro1
-rw-r--r--tests/auto/qcontiguouscache/qcontiguouscache.pro8
-rw-r--r--tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp479
13 files changed, 1693 insertions, 0 deletions
diff --git a/doc/src/examples/contiguouscache.qdoc b/doc/src/examples/contiguouscache.qdoc
new file mode 100644
index 0000000..fbfde3f
--- /dev/null
+++ b/doc/src/examples/contiguouscache.qdoc
@@ -0,0 +1,97 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the documentation 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$
+**
+****************************************************************************/
+
+/*!
+ \example tools/contiguouscache
+ \title Contiguous Cache Example
+
+ The Contiguous Cache example shows how to use QContiguousCache 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 QContiguousCache 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 QContiguousCache 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/contiguouscache/randomlistmodel.cpp 0
+
+ After getting the row, the class determines if the row is in the bounds
+ of the contiguous cache's current range. It would have been equally valid to
+ simply have the following code instead.
+
+ \code
+ 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
+ the code above causing every row between the old and new rows to be fetched.
+
+ Using QContiguousCache::lastIndex() and QContiguousCache::firstIndex() allows
+ the example to determine what part of the list the cache is currently caching.
+ These values don't represent the indexes into the cache's own memory, but rather
+ a virtual infinite array that the cache represents.
+
+ By using QContiguousCache::append() and QContiguousCache::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 cache range. QContiguousCache::insert() can
+ potentially remove more than one item from the cache as QContiguousCache 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 the cache
+ 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.
+
+ \snippet examples/tools/contiguouscache/randomlistmodel.cpp 1
+
+ It is also worth considering pre-fetching items into the cache outside of the
+ application's paint routine. This can be done either with a separate thread
+ or using a QTimer to incrementally expand the range of the cache prior to
+ rows being requested out of the current cache range.
+*/
diff --git a/examples/tools/contiguouscache/contiguouscache.pro b/examples/tools/contiguouscache/contiguouscache.pro
new file mode 100644
index 0000000..f840514
--- /dev/null
+++ b/examples/tools/contiguouscache/contiguouscache.pro
@@ -0,0 +1,9 @@
+HEADERS = randomlistmodel.h
+SOURCES = randomlistmodel.cpp \
+ main.cpp
+
+# install
+target.path = $$[QT_INSTALL_EXAMPLES]/tools/contiguouscache
+sources.files = $$SOURCES $$HEADERS $$RESOURCES $$FORMS contiguouscache.pro
+sources.path = $$[QT_INSTALL_EXAMPLES]/tools/contiguouscache
+INSTALLS += target sources
diff --git a/examples/tools/contiguouscache/main.cpp b/examples/tools/contiguouscache/main.cpp
new file mode 100644
index 0000000..291aaf4
--- /dev/null
+++ b/examples/tools/contiguouscache/main.cpp
@@ -0,0 +1,56 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the examples 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 "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/contiguouscache/randomlistmodel.cpp b/examples/tools/contiguouscache/randomlistmodel.cpp
new file mode 100644
index 0000000..0f58c0e
--- /dev/null
+++ b/examples/tools/contiguouscache/randomlistmodel.cpp
@@ -0,0 +1,96 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the examples 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 "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/contiguouscache/randomlistmodel.h b/examples/tools/contiguouscache/randomlistmodel.h
new file mode 100644
index 0000000..d32bf16
--- /dev/null
+++ b/examples/tools/contiguouscache/randomlistmodel.h
@@ -0,0 +1,66 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the examples 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 RANDOMLISTMODEL_H
+#define RANDOMLISTMODEL_H
+
+#include <QContiguousCache>
+#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 QContiguousCache<QString> m_rows;
+ const int m_count;
+};
+
+#endif
diff --git a/examples/tools/tools.pro b/examples/tools/tools.pro
index 79f0faa..c694dd8 100644
--- a/examples/tools/tools.pro
+++ b/examples/tools/tools.pro
@@ -5,6 +5,7 @@ SUBDIRS = codecs \
customcompleter \
echoplugin \
i18n \
+ contiguouscache \
plugandpaintplugins \
plugandpaint \
regexp \
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/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/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 \
diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro
index a3a6916..714e19d 100644
--- a/tests/auto/auto.pro
+++ b/tests/auto/auto.pro
@@ -209,6 +209,7 @@ SUBDIRS += bic \
qnumeric \
qobject \
qobjectrace \
+ qcontiguouscache \
qpaintengine \
qpainter \
qpainterpath \
diff --git a/tests/auto/qcontiguouscache/qcontiguouscache.pro b/tests/auto/qcontiguouscache/qcontiguouscache.pro
new file mode 100644
index 0000000..618efed
--- /dev/null
+++ b/tests/auto/qcontiguouscache/qcontiguouscache.pro
@@ -0,0 +1,8 @@
+load(qttest_p4)
+
+QT = core
+
+SOURCES += tst_qcontiguouscache.cpp
+
+
+
diff --git a/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp b/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp
new file mode 100644
index 0000000..6d59390
--- /dev/null
+++ b/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp
@@ -0,0 +1,479 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the test suite 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 <QObject>
+#include <QTest>
+#include <QCache>
+#include <QContiguousCache>
+
+#include <QDebug>
+#include <stdio.h>
+
+class tst_QContiguousCache : public QObject
+{
+ Q_OBJECT
+public:
+ tst_QContiguousCache() {}
+ virtual ~tst_QContiguousCache() {}
+private slots:
+ void empty();
+ void append_data();
+ void append();
+
+ void prepend_data();
+ void prepend();
+
+ void asScrollingList();
+
+ void complexType();
+
+ void operatorAt();
+
+ void cacheBenchmark();
+ void contiguousCacheBenchmark();
+
+ void setCapacity();
+};
+
+QTEST_MAIN(tst_QContiguousCache)
+
+void tst_QContiguousCache::empty()
+{
+ QContiguousCache<int> c(10);
+ QCOMPARE(c.capacity(), 10);
+ 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);
+ QVERIFY(c.isEmpty());
+ QCOMPARE(c.capacity(), 10);
+}
+
+void tst_QContiguousCache::append_data()
+{
+ 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.available(), qMax(0, cacheSize - i));
+ QCOMPARE(c.first(), qMax(1, i-cacheSize+1));
+ QCOMPARE(c.last(), i);
+ 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 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;
+}
+
+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.available(), qMax(0, cacheSize - i));
+ QCOMPARE(c.last(), qMax(1, i-cacheSize+1));
+ QCOMPARE(c.first(), i);
+ 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::asScrollingList()
+{
+ int i;
+ QContiguousCache<int> c(10);
+
+ // Once allocated QContiguousCache 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) {
+ QCOMPARE(c.available(), 10-i);
+ c.append(i);
+ }
+
+ QCOMPARE(c.firstIndex(), 0);
+ QCOMPARE(c.lastIndex(), 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) {
+ 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);
+ 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) {
+ 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);
+ 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) {
+ 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);
+ QCOMPARE(c.first(), 210);
+ QCOMPARE(c.last(), 219);
+ QVERIFY(!c.containsIndex(209));
+ QVERIFY(!c.containsIndex(300));
+ QCOMPARE(c.available(), 0);
+
+ 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
+ }
+
+ // 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_QContiguousCache::complexType()
+{
+ RefCountingClass original;
+
+ QContiguousCache<RefCountingClass> contiguousCache(10);
+ contiguousCache.append(original);
+ QCOMPARE(original.refCount(), 3);
+ contiguousCache.removeFirst();
+ QCOMPARE(original.refCount(), 2); // shared null, 'original'.
+ contiguousCache.append(original);
+ QCOMPARE(original.refCount(), 3);
+ contiguousCache.clear();
+ QCOMPARE(original.refCount(), 2);
+
+ for(int i = 0; i < 100; ++i)
+ contiguousCache.insert(i, original);
+
+ QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache.
+
+ contiguousCache.clear();
+ QCOMPARE(original.refCount(), 2);
+ for (int i = 0; i < 100; i++)
+ contiguousCache.append(original);
+
+ QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache.
+ contiguousCache.clear();
+ QCOMPARE(original.refCount(), 2);
+
+ for (int i = 0; i < 100; i++)
+ contiguousCache.prepend(original);
+
+ QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache.
+ contiguousCache.clear();
+ QCOMPARE(original.refCount(), 2);
+
+ for (int i = 0; i < 100; i++)
+ contiguousCache.append(original);
+
+ contiguousCache.takeLast();
+ QCOMPARE(original.refCount(), 11);
+
+ contiguousCache.takeFirst();
+ QCOMPARE(original.refCount(), 10);
+}
+
+void tst_QContiguousCache::operatorAt()
+{
+ RefCountingClass original;
+ QContiguousCache<RefCountingClass> contiguousCache(10);
+
+ for (int i = 25; i < 35; ++i)
+ contiguousCache[i] = original;
+
+ QCOMPARE(original.refCount(), 12); // shared null, orig, items in cache
+
+ // verify const access does not copy items.
+ const QContiguousCache<RefCountingClass> copy(contiguousCache);
+ for (int i = 25; i < 35; ++i)
+ QCOMPARE(copy[i].refCount(), 12);
+
+ // verify modifying the original increments ref count (e.g. does a detach)
+ contiguousCache[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 QContiguousCache 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 QContiguousCache use cases here, QCache has its own
+ areas where it is the more sensible class to use.
+*/
+void tst_QContiguousCache::cacheBenchmark()
+{
+ QBENCHMARK {
+ QCache<int, int> cache;
+ cache.setMaxCost(100);
+
+ for (int i = 0; i < 1000; i++)
+ cache.insert(i, new int(i));
+ }
+}
+
+void tst_QContiguousCache::contiguousCacheBenchmark()
+{
+ QBENCHMARK {
+ QContiguousCache<int> contiguousCache(100);
+ for (int i = 0; i < 1000; i++)
+ contiguousCache.insert(i, i);
+ }
+}
+
+void tst_QContiguousCache::setCapacity()
+{
+ int i;
+ QContiguousCache<int> contiguousCache(100);
+ for (i = 280; i < 310; ++i)
+ contiguousCache.insert(i, i);
+ QCOMPARE(contiguousCache.capacity(), 100);
+ QCOMPARE(contiguousCache.count(), 30);
+ QCOMPARE(contiguousCache.firstIndex(), 280);
+ QCOMPARE(contiguousCache.lastIndex(), 309);
+
+ for (i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) {
+ QVERIFY(contiguousCache.containsIndex(i));
+ QCOMPARE(contiguousCache.at(i), i);
+ }
+
+ contiguousCache.setCapacity(150);
+
+ QCOMPARE(contiguousCache.capacity(), 150);
+ QCOMPARE(contiguousCache.count(), 30);
+ QCOMPARE(contiguousCache.firstIndex(), 280);
+ QCOMPARE(contiguousCache.lastIndex(), 309);
+
+ for (i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) {
+ QVERIFY(contiguousCache.containsIndex(i));
+ QCOMPARE(contiguousCache.at(i), i);
+ }
+
+ contiguousCache.setCapacity(20);
+
+ QCOMPARE(contiguousCache.capacity(), 20);
+ QCOMPARE(contiguousCache.count(), 20);
+ QCOMPARE(contiguousCache.firstIndex(), 290);
+ QCOMPARE(contiguousCache.lastIndex(), 309);
+
+ for (i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) {
+ QVERIFY(contiguousCache.containsIndex(i));
+ QCOMPARE(contiguousCache.at(i), i);
+ }
+}
+
+#include "tst_qcontiguouscache.moc"
generated by cgit v0.12 at 2025-08-21 01:51:02 (GMT)