From 423d6052844b2026c8acc8826d6546d3afc494d3 Mon Sep 17 00:00:00 2001 From: Ian Walters Date: Fri, 3 Apr 2009 12:44:38 +1000 Subject: Rename OffsetVector to ContiguousCache --- doc/src/examples/contiguouscache.qdoc | 69 ++++ doc/src/examples/offsetvector.qdoc | 70 ---- examples/tools/contiguouscache/contiguouscache.pro | 9 + examples/tools/contiguouscache/main.cpp | 15 + examples/tools/contiguouscache/randomlistmodel.cpp | 56 +++ examples/tools/contiguouscache/randomlistmodel.h | 26 ++ examples/tools/offsetvector/main.cpp | 15 - examples/tools/offsetvector/offsetvector.pro | 9 - examples/tools/offsetvector/randomlistmodel.cpp | 56 --- examples/tools/offsetvector/randomlistmodel.h | 26 -- examples/tools/tools.pro | 2 +- src/corelib/tools/qcontiguouscache.cpp | 359 +++++++++++++++++++ src/corelib/tools/qcontiguouscache.h | 386 +++++++++++++++++++++ src/corelib/tools/qoffsetvector.cpp | 360 ------------------- src/corelib/tools/qoffsetvector.h | 386 --------------------- src/corelib/tools/tools.pri | 4 +- tests/auto/qcontiguouscache/qcontiguouscache.pro | 8 + .../auto/qcontiguouscache/tst_qcontiguouscache.cpp | 361 +++++++++++++++++++ tests/auto/qoffsetvector/qoffsetvector.pro | 8 - tests/auto/qoffsetvector/tst_qoffsetvector.cpp | 361 ------------------- 20 files changed, 1292 insertions(+), 1294 deletions(-) create mode 100644 doc/src/examples/contiguouscache.qdoc delete mode 100644 doc/src/examples/offsetvector.qdoc create mode 100644 examples/tools/contiguouscache/contiguouscache.pro create mode 100644 examples/tools/contiguouscache/main.cpp create mode 100644 examples/tools/contiguouscache/randomlistmodel.cpp create mode 100644 examples/tools/contiguouscache/randomlistmodel.h delete mode 100644 examples/tools/offsetvector/main.cpp delete mode 100644 examples/tools/offsetvector/offsetvector.pro delete mode 100644 examples/tools/offsetvector/randomlistmodel.cpp delete mode 100644 examples/tools/offsetvector/randomlistmodel.h create mode 100644 src/corelib/tools/qcontiguouscache.cpp create mode 100644 src/corelib/tools/qcontiguouscache.h delete mode 100644 src/corelib/tools/qoffsetvector.cpp delete mode 100644 src/corelib/tools/qoffsetvector.h create mode 100644 tests/auto/qcontiguouscache/qcontiguouscache.pro create mode 100644 tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp delete mode 100644 tests/auto/qoffsetvector/qoffsetvector.pro delete mode 100644 tests/auto/qoffsetvector/tst_qoffsetvector.cpp diff --git a/doc/src/examples/contiguouscache.qdoc b/doc/src/examples/contiguouscache.qdoc new file mode 100644 index 0000000..22c97fa --- /dev/null +++ b/doc/src/examples/contiguouscache.qdoc @@ -0,0 +1,69 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the $MODULE$ of the Qt Toolkit. +** +** $TROLLTECH_DUAL_LICENSE$ +** +****************************************************************************/ + +/*! + \example tools/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_words.lastIndex()) + m_words.append(fetchWord(m_words.lastIndex()+1); + while (row < m_words.firstIndex()) + m_words.prepend(fetchWord(m_words.firstIndex()-1); + \endcode + + However a list will often jump rows if the scroll bar is used directly, resulting in + the code above to cause every row between where the cache was last centered + to the requested row to be fetched before the requested row is fetched. + + Using QContiguousCache::lastIndex() and QContiguousCache::firstIndex() allows + the example to determine where in the list the cache is currently over. These values + don't represent the indexes into the cache 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 cache: + + \snippet examples/tools/contiguouscache/randomlistmodel.cpp 1 + + Generates random information rather than fixed information. This allows you + to see how the cache range is kept for a local number of rows when running the + example. + + It is also worth considering pre-fetching items into the cache outside of the + applications paint routine. This can be done either with a separate thread + or using a QTimer to incrementally expand the range of the thread prior to + rows being requested out of the current cache range. +*/ diff --git a/doc/src/examples/offsetvector.qdoc b/doc/src/examples/offsetvector.qdoc deleted file mode 100644 index 256569e..0000000 --- a/doc/src/examples/offsetvector.qdoc +++ /dev/null @@ -1,70 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). -** Contact: Qt Software Information (qt-info@nokia.com) -** -** This file is part of the $MODULE$ of the Qt Toolkit. -** -** $TROLLTECH_DUAL_LICENSE$ -** -****************************************************************************/ - -/*! - \example tools/offsetvector - \title Offset Vector Example - - The Offset Vector example shows how to use QOffsetVector to manage memory usage for - very large models. In some environments memory is limited, and even when it - isn't users still dislike an application using - excessive memory. Using QOffsetVector to manage a list rather than loading - the entire list into memory allows the application to limit the amount - of memory it uses regardless of the size of the data set it accesses - - The simplest way to use QOffsetVector is to cache as items are requested. When - a view requests an item at row N it is also likely to ask for items at rows near - to N. - - \snippet examples/tools/offsetvector/randomlistmodel.cpp 0 - - After getting the row the class determines if the row is in the bounds - of the offset vector's current range. It would have been equally valid to - simply have the following code instead. - - \code - while (row > m_words.lastIndex()) - m_words.append(fetchWord(m_words.lastIndex()+1); - while (row < m_words.firstIndex()) - m_words.prepend(fetchWord(m_words.firstIndex()-1); - \endcode - - However a list will often jump rows if the scroll bar is used directly, and - the above code would cause every row between where the cache was last centered - to where the cache is currently centered to be cached before the requested - row is reached. - - Using QOffsetVector::lastIndex() and QOffsetVector::firstIndex() allows - the example to determine where the list the vector is currently over. These values - don't represent the indexes into the vector own memory, but rather a virtual - infinite array that the vector represents. - - By using QOffsetVector::append() and QOffsetVector::prepend() the code ensures - that items that may be still on the screen are not lost when the requested row - has not moved far from the current vector range. QOffsetVector::insert() can - potentially remove more than one item from the cache as QOffsetVector does not - allow for gaps. If your cache needs to quickly jump back and forth between - rows with significant gaps between them consider using QCache instead. - - And thats it. A perfectly reasonable cache, using minimal memory for a very large - list. In this case the accessor for getting the words into cache: - - \snippet examples/tools/offsetvector/randomlistmodel.cpp 1 - - Generates random information rather than fixed information. This allows you - to see how the cache range is kept for a local number of rows when running the - example. - - It is also worth considering pre-fetching items into the cache outside of the - applications paint routine. This can be done either with a separate thread - or using a QTimer to incrementally expand the range of the thread prior to - rows being requested out of the current vector range. -*/ diff --git a/examples/tools/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..bdeb3f3 --- /dev/null +++ b/examples/tools/contiguouscache/main.cpp @@ -0,0 +1,15 @@ +#include "randomlistmodel.h" +#include +#include + +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..5c0953b --- /dev/null +++ b/examples/tools/contiguouscache/randomlistmodel.cpp @@ -0,0 +1,56 @@ +#include "randomlistmodel.h" + +static const int bufferSize(500); +static const int lookAhead(100); +static const int halfLookAhead(lookAhead/2); + +RandomListModel::RandomListModel(QObject *parent) +: QAbstractListModel(parent), m_rows(bufferSize), m_count(10000) +{ +} + +RandomListModel::~RandomListModel() +{ +} + +int RandomListModel::rowCount(const QModelIndex &) const +{ + return m_count; +} + +//! [0] +QVariant RandomListModel::data(const QModelIndex &index, int role) const +{ + if (role != Qt::DisplayRole) + return QVariant(); + + int row = index.row(); + + if (row > m_rows.lastIndex()) { + if (row - m_rows.lastIndex() > lookAhead) + cacheRows(row-halfLookAhead, qMin(m_count, row+halfLookAhead)); + else while (row > m_rows.lastIndex()) + m_rows.append(fetchRow(m_rows.lastIndex()+1)); + } else if (row < m_rows.firstIndex()) { + if (m_rows.firstIndex() - row > lookAhead) + cacheRows(qMax(0, row-halfLookAhead), row+halfLookAhead); + else while (row < m_rows.firstIndex()) + m_rows.prepend(fetchRow(m_rows.firstIndex()-1)); + } + + return m_rows.at(row); +} + +void RandomListModel::cacheRows(int from, int to) const +{ + for (int i = from; i <= to; ++i) + m_rows.insert(i, fetchRow(i)); +} +//![0] + +//![1] +QString RandomListModel::fetchRow(int position) const +{ + return QString::number(rand() % ++position); +} +//![1] diff --git a/examples/tools/contiguouscache/randomlistmodel.h b/examples/tools/contiguouscache/randomlistmodel.h new file mode 100644 index 0000000..ad8cfad --- /dev/null +++ b/examples/tools/contiguouscache/randomlistmodel.h @@ -0,0 +1,26 @@ +#ifndef RANDOMLISTMODEL_H +#define RANDOMLISTMODEL_H + +#include +#include + +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 m_rows; + const int m_count; +}; + +#endif diff --git a/examples/tools/offsetvector/main.cpp b/examples/tools/offsetvector/main.cpp deleted file mode 100644 index bdeb3f3..0000000 --- a/examples/tools/offsetvector/main.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#include "randomlistmodel.h" -#include -#include - -int main(int c, char **v) -{ - QApplication a(c, v); - - QListView view; - view.setUniformItemSizes(true); - view.setModel(new RandomListModel(&view)); - view.show(); - - return a.exec(); -} diff --git a/examples/tools/offsetvector/offsetvector.pro b/examples/tools/offsetvector/offsetvector.pro deleted file mode 100644 index f329bb9..0000000 --- a/examples/tools/offsetvector/offsetvector.pro +++ /dev/null @@ -1,9 +0,0 @@ -HEADERS = randomlistmodel.h -SOURCES = randomlistmodel.cpp \ - main.cpp - -# install -target.path = $$[QT_INSTALL_EXAMPLES]/tools/offsetvector -sources.files = $$SOURCES $$HEADERS $$RESOURCES $$FORMS offsetvector.pro -sources.path = $$[QT_INSTALL_EXAMPLES]/tools/offsetvector -INSTALLS += target sources diff --git a/examples/tools/offsetvector/randomlistmodel.cpp b/examples/tools/offsetvector/randomlistmodel.cpp deleted file mode 100644 index 5c0953b..0000000 --- a/examples/tools/offsetvector/randomlistmodel.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include "randomlistmodel.h" - -static const int bufferSize(500); -static const int lookAhead(100); -static const int halfLookAhead(lookAhead/2); - -RandomListModel::RandomListModel(QObject *parent) -: QAbstractListModel(parent), m_rows(bufferSize), m_count(10000) -{ -} - -RandomListModel::~RandomListModel() -{ -} - -int RandomListModel::rowCount(const QModelIndex &) const -{ - return m_count; -} - -//! [0] -QVariant RandomListModel::data(const QModelIndex &index, int role) const -{ - if (role != Qt::DisplayRole) - return QVariant(); - - int row = index.row(); - - if (row > m_rows.lastIndex()) { - if (row - m_rows.lastIndex() > lookAhead) - cacheRows(row-halfLookAhead, qMin(m_count, row+halfLookAhead)); - else while (row > m_rows.lastIndex()) - m_rows.append(fetchRow(m_rows.lastIndex()+1)); - } else if (row < m_rows.firstIndex()) { - if (m_rows.firstIndex() - row > lookAhead) - cacheRows(qMax(0, row-halfLookAhead), row+halfLookAhead); - else while (row < m_rows.firstIndex()) - m_rows.prepend(fetchRow(m_rows.firstIndex()-1)); - } - - return m_rows.at(row); -} - -void RandomListModel::cacheRows(int from, int to) const -{ - for (int i = from; i <= to; ++i) - m_rows.insert(i, fetchRow(i)); -} -//![0] - -//![1] -QString RandomListModel::fetchRow(int position) const -{ - return QString::number(rand() % ++position); -} -//![1] diff --git a/examples/tools/offsetvector/randomlistmodel.h b/examples/tools/offsetvector/randomlistmodel.h deleted file mode 100644 index e102255..0000000 --- a/examples/tools/offsetvector/randomlistmodel.h +++ /dev/null @@ -1,26 +0,0 @@ -#ifndef RANDOMLISTMODEL_H -#define RANDOMLISTMODEL_H - -#include -#include - -class QTimer; -class RandomListModel : public QAbstractListModel -{ - Q_OBJECT -public: - RandomListModel(QObject *parent = 0); - ~RandomListModel(); - - int rowCount(const QModelIndex & = QModelIndex()) const; - QVariant data(const QModelIndex &, int) const; - -private: - void cacheRows(int, int) const; - QString fetchRow(int) const; - - mutable QOffsetVector m_rows; - const int m_count; -}; - -#endif diff --git a/examples/tools/tools.pro b/examples/tools/tools.pro index 424f286..c694dd8 100644 --- a/examples/tools/tools.pro +++ b/examples/tools/tools.pro @@ -5,7 +5,7 @@ SUBDIRS = codecs \ customcompleter \ echoplugin \ i18n \ - offsetvector \ + contiguouscache \ plugandpaintplugins \ plugandpaint \ regexp \ diff --git a/src/corelib/tools/qcontiguouscache.cpp b/src/corelib/tools/qcontiguouscache.cpp new file mode 100644 index 0000000..5046912 --- /dev/null +++ b/src/corelib/tools/qcontiguouscache.cpp @@ -0,0 +1,359 @@ +/**************************************************************************** +** +** 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 "qcontiguouscache.h" +#include + +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 though it adds a restriction + that elements within the cache are contiguous. This has the advantage that + 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 use less overhead than QCache both in terms of + performance and memory. + + The simplest way of using an 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 with the furthest index from where + the new item is appended or prepended is 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 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 to unwanted clearing of the cache. + + See the 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 &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 &QContiguousCache::operator=(const QContiguousCache &other) + + Assigns \a other to this cache and returns a reference to this cache. +*/ + +/*! \fn bool QContiguousCache::operator==(const QContiguousCache &other) const + + Returns true if \a other is equal to this cache; otherwise returns false. + + Two cache 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 &other) const + + Returns true if \a other is not equal to this cache; otherwise + returns false. + + Two cache 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 furthest 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 furthest 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 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 an 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 worth + while then taking effort to insert items in an order that starts adjacent to the + current index range for the cache. + + \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. 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 + + \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 + + \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. + + If you don't sue the return value, removeFirst() is more efficient. + + \sa takeLast(), removeFirst() +*/ + +/*! \fn T QContiguousCache::takeLast() + + Removes the last item in the cache and returns it. + + If you don't sue the return value, removeLast() is more efficient. + + \sa takeFirst(), removeLast() +*/ + +/*! \fn void QContiguousCache::dump() const + + \internal + + Sends information about the cache's internal structure to qDebug() +*/ diff --git a/src/corelib/tools/qcontiguouscache.h b/src/corelib/tools/qcontiguouscache.h new file mode 100644 index 0000000..03012a2 --- /dev/null +++ b/src/corelib/tools/qcontiguouscache.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 QCONTIGUOUSCACHE_H +#define QCONTIGUOUSCACHE_H + +#include + +struct QContiguousCacheData +{ + QBasicAtomicInt ref; + int alloc; + int count; + int start; + int offset; + uint sharable : 1; + + void dump() const; +}; + +template +struct QContiguousCacheTypedData +{ + QBasicAtomicInt ref; + int alloc; + int count; + int start; + int offset; + uint sharable : 1; + + T array[1]; +}; + +class QContiguousCacheDevice; + +template +class QContiguousCache { + typedef QContiguousCacheTypedData Data; + union { QContiguousCacheData *p; QContiguousCacheTypedData *d; }; +public: + explicit QContiguousCache(int capacity = 0); + QContiguousCache(const QContiguousCache &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 &operator=(const QContiguousCache &other); + bool operator==(const QContiguousCache &other) const; + inline bool operator!=(const QContiguousCache &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(); + + QContiguousCacheData *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(&(reinterpret_cast(this))->array[1]) - reinterpret_cast(this); + } +}; + +template +void QContiguousCache::detach_helper() +{ + union { QContiguousCacheData *p; QContiguousCacheTypedData *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::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 +void QContiguousCache::setCapacity(int asize) +{ + if (asize == d->alloc) + return; + detach(); + union { QContiguousCacheData *p; QContiguousCacheTypedData *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::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 +void QContiguousCache::clear() +{ + if (d->ref == 1) { + if (QTypeInfo::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 *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 +inline QContiguousCacheData *QContiguousCache::malloc(int aalloc) +{ + return static_cast(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T))); +} + +template +QContiguousCache::QContiguousCache(int asize) +{ + p = malloc(asize); + d->ref = 1; + d->alloc = asize; + d->count = d->start = d->offset = 0; + d->sharable = true; +} + +template +QContiguousCache &QContiguousCache::operator=(const QContiguousCache &other) +{ + other.d->ref.ref(); + if (!d->ref.deref()) + free(d); + d = other.d; + if (!d->sharable) + detach_helper(); + return *this; +} + +template +bool QContiguousCache::operator==(const QContiguousCache &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 +void QContiguousCache::free(Data *x) +{ + if (QTypeInfo::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 +void QContiguousCache::append(const T &value) +{ + detach(); + if (QTypeInfo::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 +void QContiguousCache::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::isComplex) + new (d->array + d->start) T(value); + else + d->array[d->start] = value; +} + +template +void QContiguousCache::insert(int pos, const T &value) +{ + detach(); + if (containsIndex(pos)) { + if(QTypeInfo::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::isComplex) + new (d->array + d->start) T(value); + else + d->array[d->start] = value; + } +} + +template +inline const T &QContiguousCache::at(int pos) const +{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache::at", "index out of range"); return d->array[pos % d->alloc]; } +template +inline const T &QContiguousCache::operator[](int pos) const +{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache::at", "index out of range"); return d->array[pos % d->alloc]; } +template + +// can use the non-inline one to modify the index range. +inline T &QContiguousCache::operator[](int pos) +{ + detach(); + if (!containsIndex(pos)) + insert(pos, T()); + return d->array[pos % d->alloc]; +} + +template +inline void QContiguousCache::removeFirst() +{ + Q_ASSERT(d->count > 0); + detach(); + d->count--; + if (QTypeInfo::isComplex) + (d->array + d->start)->~T(); + d->start = (d->start + 1) % d->alloc; + d->offset++; +} + +template +inline void QContiguousCache::removeLast() +{ + Q_ASSERT(d->count > 0); + detach(); + d->count--; + if (QTypeInfo::isComplex) + (d->array + (d->start + d->count) % d->alloc)->~T(); +} + +template +inline T QContiguousCache::takeFirst() +{ T t = first(); removeFirst(); return t; } + +template +inline T QContiguousCache::takeLast() +{ T t = last(); removeLast(); return t; } + +#endif diff --git a/src/corelib/tools/qoffsetvector.cpp b/src/corelib/tools/qoffsetvector.cpp deleted file mode 100644 index 32d2872..0000000 --- a/src/corelib/tools/qoffsetvector.cpp +++ /dev/null @@ -1,360 +0,0 @@ -/**************************************************************************** -** -** 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 - -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 &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 &QOffsetVector::operator=(const QOffsetVector &other) - - Assigns \a other to this vector and returns a reference to this vector. -*/ - -/*! \fn bool QOffsetVector::operator==(const QOffsetVector &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 &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 deleted file mode 100644 index 7030862..0000000 --- a/src/corelib/tools/qoffsetvector.h +++ /dev/null @@ -1,386 +0,0 @@ -/**************************************************************************** -** -** 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 - -struct QOffsetVectorData -{ - QBasicAtomicInt ref; - int alloc; - int count; - int start; - int offset; - uint sharable : 1; - - void dump() const; -}; - -template -struct QOffsetVectorTypedData -{ - QBasicAtomicInt ref; - int alloc; - int count; - int start; - int offset; - uint sharable : 1; - - T array[1]; -}; - -class QOffsetVectorDevice; - -template -class QOffsetVector { - typedef QOffsetVectorTypedData Data; - union { QOffsetVectorData *p; QOffsetVectorTypedData *d; }; -public: - explicit QOffsetVector(int capacity = 0); - QOffsetVector(const QOffsetVector &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 &operator=(const QOffsetVector &other); - bool operator==(const QOffsetVector &other) const; - inline bool operator!=(const QOffsetVector &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(&(reinterpret_cast(this))->array[1]) - reinterpret_cast(this); - } -}; - -template -void QOffsetVector::detach_helper() -{ - union { QOffsetVectorData *p; QOffsetVectorTypedData *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::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 -void QOffsetVector::setCapacity(int asize) -{ - if (asize == d->alloc) - return; - detach(); - union { QOffsetVectorData *p; QOffsetVectorTypedData *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::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 -void QOffsetVector::clear() -{ - if (d->ref == 1) { - if (QTypeInfo::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 *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 -inline QOffsetVectorData *QOffsetVector::malloc(int aalloc) -{ - return static_cast(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T))); -} - -template -QOffsetVector::QOffsetVector(int asize) -{ - p = malloc(asize); - d->ref = 1; - d->alloc = asize; - d->count = d->start = d->offset = 0; - d->sharable = true; -} - -template -QOffsetVector &QOffsetVector::operator=(const QOffsetVector &other) -{ - other.d->ref.ref(); - if (!d->ref.deref()) - free(d); - d = other.d; - if (!d->sharable) - detach_helper(); - return *this; -} - -template -bool QOffsetVector::operator==(const QOffsetVector &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 -void QOffsetVector::free(Data *x) -{ - if (QTypeInfo::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 -void QOffsetVector::append(const T &value) -{ - detach(); - if (QTypeInfo::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 -void QOffsetVector::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::isComplex) - new (d->array + d->start) T(value); - else - d->array[d->start] = value; -} - -template -void QOffsetVector::insert(int pos, const T &value) -{ - detach(); - if (containsIndex(pos)) { - if(QTypeInfo::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::isComplex) - new (d->array + d->start) T(value); - else - d->array[d->start] = value; - } -} - -template -inline const T &QOffsetVector::at(int pos) const -{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QOffsetVector::at", "index out of range"); return d->array[pos % d->alloc]; } -template -inline const T &QOffsetVector::operator[](int pos) const -{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QOffsetVector::at", "index out of range"); return d->array[pos % d->alloc]; } -template - -// can use the non-inline one to modify the index range. -inline T &QOffsetVector::operator[](int pos) -{ - detach(); - if (!containsIndex(pos)) - insert(pos, T()); - return d->array[pos % d->alloc]; -} - -template -inline void QOffsetVector::removeFirst() -{ - Q_ASSERT(d->count > 0); - detach(); - d->count--; - if (QTypeInfo::isComplex) - (d->array + d->start)->~T(); - d->start = (d->start + 1) % d->alloc; - d->offset++; -} - -template -inline void QOffsetVector::removeLast() -{ - Q_ASSERT(d->count > 0); - detach(); - d->count--; - if (QTypeInfo::isComplex) - (d->array + (d->start + d->count) % d->alloc)->~T(); -} - -template -inline T QOffsetVector::takeFirst() -{ T t = first(); removeFirst(); return t; } - -template -inline T QOffsetVector::takeLast() -{ T t = last(); removeLast(); return t; } - -#endif diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri index 626c9e5..aaf3f21 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -19,7 +19,7 @@ HEADERS += \ tools/qlocale_p.h \ tools/qlocale_data_p.h \ tools/qmap.h \ - tools/qoffsetvector.h \ + tools/qcontiguouscache.h \ tools/qpodlist_p.h \ tools/qpoint.h \ tools/qqueue.h \ @@ -54,7 +54,7 @@ SOURCES += \ tools/qlocale.cpp \ tools/qpoint.cpp \ tools/qmap.cpp \ - tools/qoffsetvector.cpp \ + tools/qcontiguouscache.cpp \ tools/qrect.cpp \ tools/qregexp.cpp \ tools/qshareddata.cpp \ 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..493032a --- /dev/null +++ b/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp @@ -0,0 +1,361 @@ +/**************************************************************************** +** +** This file is part of the $PACKAGE_NAME$. +** +** Copyright (C) $THISYEAR$ $COMPANY_NAME$. +** +** $QT_EXTENDED_DUAL_LICENSE$ +** +****************************************************************************/ + +#include +#include +#include +#include +#include +#include + +#include +#include + + +#if defined(FORCE_UREF) +template +inline QDebug &operator<<(QDebug debug, const QContiguousCache &contiguousCache) +#else +template +inline QDebug operator<<(QDebug debug, const QContiguousCache &contiguousCache) +#endif +{ + debug.nospace() << "QContiguousCache("; + for (int i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) { + debug << contiguousCache[i]; + if (i != contiguousCache.lastIndex()) + debug << ", "; + } + debug << ")"; + return debug.space(); +} + +#if defined(NO_BENCHMARK) and defined(QBENCHMARK) +#undef QBENCHMARK +#define QBENCHMARK +#endif + +class tst_QContiguousCache : public QObject +{ + Q_OBJECT +public: + tst_QContiguousCache() {} + virtual ~tst_QContiguousCache() {} +private slots: + void empty(); + void forwardBuffer(); + void scrollingList(); + + void complexType(); + + void operatorAt(); + + void cacheBenchmark(); + void contiguousCacheBenchmark(); + + void setCapacity(); +}; + +QTEST_MAIN(tst_QContiguousCache) + +void tst_QContiguousCache::empty() +{ + QContiguousCache c(10); + QCOMPARE(c.capacity(), 10); + QCOMPARE(c.count(), 0); + QVERIFY(c.isEmpty()); + c.append(1); + QVERIFY(!c.isEmpty()); + c.clear(); + QCOMPARE(c.capacity(), 10); + QCOMPARE(c.count(), 0); + QVERIFY(c.isEmpty()); + c.prepend(1); + QVERIFY(!c.isEmpty()); + c.clear(); + QCOMPARE(c.count(), 0); + QVERIFY(c.isEmpty()); + QCOMPARE(c.capacity(), 10); +} + +void tst_QContiguousCache::forwardBuffer() +{ + int i; + QContiguousCache c(10); + for(i = 1; i < 30; ++i) { + c.append(i); + QCOMPARE(c.first(), qMax(1, i-9)); + QCOMPARE(c.last(), i); + QCOMPARE(c.count(), qMin(i, 10)); + } + + c.clear(); + + for(i = 1; i < 30; ++i) { + c.prepend(i); + QCOMPARE(c.last(), qMax(1, i-9)); + QCOMPARE(c.first(), i); + QCOMPARE(c.count(), qMin(i, 10)); + } +} + +void tst_QContiguousCache::scrollingList() +{ + int i; + QContiguousCache 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) + c.append(i); + + QCOMPARE(c.firstIndex(), 0); + QCOMPARE(c.lastIndex(), 9); + QVERIFY(c.containsIndex(0)); + QVERIFY(c.containsIndex(9)); + QVERIFY(!c.containsIndex(10)); + + for (i = 0; i < 10; ++i) + QCOMPARE(c.at(i), i); + + for (i = 10; i < 30; ++i) + c.append(i); + + QCOMPARE(c.firstIndex(), 20); + QCOMPARE(c.lastIndex(), 29); + QVERIFY(c.containsIndex(20)); + QVERIFY(c.containsIndex(29)); + QVERIFY(!c.containsIndex(30)); + + for (i = 20; i < 30; ++i) + QCOMPARE(c.at(i), i); + + for (i = 19; i >= 10; --i) + c.prepend(i); + + QCOMPARE(c.firstIndex(), 10); + QCOMPARE(c.lastIndex(), 19); + QVERIFY(c.containsIndex(10)); + QVERIFY(c.containsIndex(19)); + QVERIFY(!c.containsIndex(20)); + + for (i = 10; i < 20; ++i) + QCOMPARE(c.at(i), i); + + for (i = 200; i < 220; ++i) + c.insert(i, i); + + QCOMPARE(c.firstIndex(), 210); + QCOMPARE(c.lastIndex(), 219); + QVERIFY(c.containsIndex(210)); + QVERIFY(c.containsIndex(219)); + QVERIFY(!c.containsIndex(300)); + QVERIFY(!c.containsIndex(209)); + + for (i = 220; i < 220; ++i) { + QVERIFY(c.containsIndex(i)); + QCOMPARE(c.at(i), i); + } + c.clear(); // needed to reset benchmark + } + + // from a specific bug that was encountered. 100 to 299 cached, attempted to cache 250 - 205 via insert, failed. + // bug was that item at 150 would instead be item that should have been inserted at 250 + c.setCapacity(200); + for(i = 100; i < 300; ++i) + c.insert(i, i); + for (i = 250; i <= 306; ++i) + c.insert(i, 1000+i); + for (i = 107; i <= 306; ++i) { + QVERIFY(c.containsIndex(i)); + QCOMPARE(c.at(i), i < 250 ? i : 1000+i); + } +} + +struct RefCountingClassData +{ + QBasicAtomicInt ref; + static RefCountingClassData shared_null; +}; + +RefCountingClassData RefCountingClassData::shared_null = { + Q_BASIC_ATOMIC_INITIALIZER(1) +}; + +class RefCountingClass +{ +public: + RefCountingClass() : d(&RefCountingClassData::shared_null) { d->ref.ref(); } + + RefCountingClass(const RefCountingClass &other) + { + d = other.d; + d->ref.ref(); + } + + ~RefCountingClass() + { + if (!d->ref.deref()) + delete d; + } + + RefCountingClass &operator=(const RefCountingClass &other) + { + if (!d->ref.deref()) + delete d; + d = other.d; + d->ref.ref(); + return *this; + } + + int refCount() const { return d->ref; } +private: + RefCountingClassData *d; +}; + +void tst_QContiguousCache::complexType() +{ + RefCountingClass original; + + QContiguousCache 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 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 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 cache; + cache.setMaxCost(100); + + for (int i = 0; i < 1000; i++) + cache.insert(i, new int(i)); + } +} + +void tst_QContiguousCache::contiguousCacheBenchmark() +{ + QBENCHMARK { + QContiguousCache contiguousCache(100); + for (int i = 0; i < 1000; i++) + contiguousCache.insert(i, i); + } +} + +void tst_QContiguousCache::setCapacity() +{ + int i; + QContiguousCache 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" diff --git a/tests/auto/qoffsetvector/qoffsetvector.pro b/tests/auto/qoffsetvector/qoffsetvector.pro deleted file mode 100644 index 0b801f3..0000000 --- a/tests/auto/qoffsetvector/qoffsetvector.pro +++ /dev/null @@ -1,8 +0,0 @@ -load(qttest_p4) - -QT = core - -SOURCES += tst_qoffsetvector.cpp - - - diff --git a/tests/auto/qoffsetvector/tst_qoffsetvector.cpp b/tests/auto/qoffsetvector/tst_qoffsetvector.cpp deleted file mode 100644 index 439ea2c..0000000 --- a/tests/auto/qoffsetvector/tst_qoffsetvector.cpp +++ /dev/null @@ -1,361 +0,0 @@ -/**************************************************************************** -** -** This file is part of the $PACKAGE_NAME$. -** -** Copyright (C) $THISYEAR$ $COMPANY_NAME$. -** -** $QT_EXTENDED_DUAL_LICENSE$ -** -****************************************************************************/ - -#include -#include -#include -#include -#include -#include - -#include -#include - - -#if defined(FORCE_UREF) -template -inline QDebug &operator<<(QDebug debug, const QOffsetVector &offsetVector) -#else -template -inline QDebug operator<<(QDebug debug, const QOffsetVector &offsetVector) -#endif -{ - debug.nospace() << "QOffsetVector("; - for (int i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) { - debug << offsetVector[i]; - if (i != offsetVector.lastIndex()) - debug << ", "; - } - debug << ")"; - return debug.space(); -} - -#if defined(NO_BENCHMARK) and defined(QBENCHMARK) -#undef QBENCHMARK -#define QBENCHMARK -#endif - -class tst_QOffsetVector : public QObject -{ - Q_OBJECT -public: - tst_QOffsetVector() {} - virtual ~tst_QOffsetVector() {} -private slots: - void empty(); - void forwardBuffer(); - void scrollingList(); - - void complexType(); - - void operatorAt(); - - void cacheBenchmark(); - void offsetVectorBenchmark(); - - void setCapacity(); -}; - -QTEST_MAIN(tst_QOffsetVector) - -void tst_QOffsetVector::empty() -{ - QOffsetVector c(10); - QCOMPARE(c.capacity(), 10); - QCOMPARE(c.count(), 0); - QVERIFY(c.isEmpty()); - c.append(1); - QVERIFY(!c.isEmpty()); - c.clear(); - QCOMPARE(c.capacity(), 10); - QCOMPARE(c.count(), 0); - QVERIFY(c.isEmpty()); - c.prepend(1); - QVERIFY(!c.isEmpty()); - c.clear(); - QCOMPARE(c.count(), 0); - QVERIFY(c.isEmpty()); - QCOMPARE(c.capacity(), 10); -} - -void tst_QOffsetVector::forwardBuffer() -{ - int i; - QOffsetVector c(10); - for(i = 1; i < 30; ++i) { - c.append(i); - QCOMPARE(c.first(), qMax(1, i-9)); - QCOMPARE(c.last(), i); - QCOMPARE(c.count(), qMin(i, 10)); - } - - c.clear(); - - for(i = 1; i < 30; ++i) { - c.prepend(i); - QCOMPARE(c.last(), qMax(1, i-9)); - QCOMPARE(c.first(), i); - QCOMPARE(c.count(), qMin(i, 10)); - } -} - -void tst_QOffsetVector::scrollingList() -{ - int i; - QOffsetVector c(10); - - // Once allocated QOffsetVector should not - // allocate any additional memory for non - // complex data types. - QBENCHMARK { - // simulate scrolling in a list of items; - for(i = 0; i < 10; ++i) - c.append(i); - - QCOMPARE(c.firstIndex(), 0); - QCOMPARE(c.lastIndex(), 9); - QVERIFY(c.containsIndex(0)); - QVERIFY(c.containsIndex(9)); - QVERIFY(!c.containsIndex(10)); - - for (i = 0; i < 10; ++i) - QCOMPARE(c.at(i), i); - - for (i = 10; i < 30; ++i) - c.append(i); - - QCOMPARE(c.firstIndex(), 20); - QCOMPARE(c.lastIndex(), 29); - QVERIFY(c.containsIndex(20)); - QVERIFY(c.containsIndex(29)); - QVERIFY(!c.containsIndex(30)); - - for (i = 20; i < 30; ++i) - QCOMPARE(c.at(i), i); - - for (i = 19; i >= 10; --i) - c.prepend(i); - - QCOMPARE(c.firstIndex(), 10); - QCOMPARE(c.lastIndex(), 19); - QVERIFY(c.containsIndex(10)); - QVERIFY(c.containsIndex(19)); - QVERIFY(!c.containsIndex(20)); - - for (i = 10; i < 20; ++i) - QCOMPARE(c.at(i), i); - - for (i = 200; i < 220; ++i) - c.insert(i, i); - - QCOMPARE(c.firstIndex(), 210); - QCOMPARE(c.lastIndex(), 219); - QVERIFY(c.containsIndex(210)); - QVERIFY(c.containsIndex(219)); - QVERIFY(!c.containsIndex(300)); - QVERIFY(!c.containsIndex(209)); - - for (i = 220; i < 220; ++i) { - QVERIFY(c.containsIndex(i)); - QCOMPARE(c.at(i), i); - } - c.clear(); // needed to reset benchmark - } - - // from a specific bug that was encountered. 100 to 299 cached, attempted to cache 250 - 205 via insert, failed. - // bug was that item at 150 would instead be item that should have been inserted at 250 - c.setCapacity(200); - for(i = 100; i < 300; ++i) - c.insert(i, i); - for (i = 250; i <= 306; ++i) - c.insert(i, 1000+i); - for (i = 107; i <= 306; ++i) { - QVERIFY(c.containsIndex(i)); - QCOMPARE(c.at(i), i < 250 ? i : 1000+i); - } -} - -struct RefCountingClassData -{ - QBasicAtomicInt ref; - static RefCountingClassData shared_null; -}; - -RefCountingClassData RefCountingClassData::shared_null = { - Q_BASIC_ATOMIC_INITIALIZER(1) -}; - -class RefCountingClass -{ -public: - RefCountingClass() : d(&RefCountingClassData::shared_null) { d->ref.ref(); } - - RefCountingClass(const RefCountingClass &other) - { - d = other.d; - d->ref.ref(); - } - - ~RefCountingClass() - { - if (!d->ref.deref()) - delete d; - } - - RefCountingClass &operator=(const RefCountingClass &other) - { - if (!d->ref.deref()) - delete d; - d = other.d; - d->ref.ref(); - return *this; - } - - int refCount() const { return d->ref; } -private: - RefCountingClassData *d; -}; - -void tst_QOffsetVector::complexType() -{ - RefCountingClass original; - - QOffsetVector offsetVector(10); - offsetVector.append(original); - QCOMPARE(original.refCount(), 3); - offsetVector.removeFirst(); - QCOMPARE(original.refCount(), 2); // shared null, 'original'. - offsetVector.append(original); - QCOMPARE(original.refCount(), 3); - offsetVector.clear(); - QCOMPARE(original.refCount(), 2); - - for(int i = 0; i < 100; ++i) - offsetVector.insert(i, original); - - QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector. - - offsetVector.clear(); - QCOMPARE(original.refCount(), 2); - for (int i = 0; i < 100; i++) - offsetVector.append(original); - - QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector. - offsetVector.clear(); - QCOMPARE(original.refCount(), 2); - - for (int i = 0; i < 100; i++) - offsetVector.prepend(original); - - QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector. - offsetVector.clear(); - QCOMPARE(original.refCount(), 2); - - for (int i = 0; i < 100; i++) - offsetVector.append(original); - - offsetVector.takeLast(); - QCOMPARE(original.refCount(), 11); - - offsetVector.takeFirst(); - QCOMPARE(original.refCount(), 10); -} - -void tst_QOffsetVector::operatorAt() -{ - RefCountingClass original; - QOffsetVector offsetVector(10); - - for (int i = 25; i < 35; ++i) - offsetVector[i] = original; - - QCOMPARE(original.refCount(), 12); // shared null, orig, items in vector - - // verify const access does not copy items. - const QOffsetVector copy(offsetVector); - for (int i = 25; i < 35; ++i) - QCOMPARE(copy[i].refCount(), 12); - - // verify modifying the original increments ref count (e.g. does a detach) - offsetVector[25] = original; - QCOMPARE(original.refCount(), 22); -} - -/* - Benchmarks must be near identical in tasks to be fair. - QCache uses pointers to ints as its a requirement of QCache, - whereas QOffsetVector doesn't support pointers (won't free them). - Given the ability to use simple data types is a benefit, its - fair. Although this obviously must take into account we are - testing QOffsetVector use cases here, QCache has its own - areas where it is the more sensible class to use. -*/ -void tst_QOffsetVector::cacheBenchmark() -{ - QBENCHMARK { - QCache cache; - cache.setMaxCost(100); - - for (int i = 0; i < 1000; i++) - cache.insert(i, new int(i)); - } -} - -void tst_QOffsetVector::offsetVectorBenchmark() -{ - QBENCHMARK { - QOffsetVector offsetVector(100); - for (int i = 0; i < 1000; i++) - offsetVector.insert(i, i); - } -} - -void tst_QOffsetVector::setCapacity() -{ - int i; - QOffsetVector offsetVector(100); - for (i = 280; i < 310; ++i) - offsetVector.insert(i, i); - QCOMPARE(offsetVector.capacity(), 100); - QCOMPARE(offsetVector.count(), 30); - QCOMPARE(offsetVector.firstIndex(), 280); - QCOMPARE(offsetVector.lastIndex(), 309); - - for (i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) { - QVERIFY(offsetVector.containsIndex(i)); - QCOMPARE(offsetVector.at(i), i); - } - - offsetVector.setCapacity(150); - - QCOMPARE(offsetVector.capacity(), 150); - QCOMPARE(offsetVector.count(), 30); - QCOMPARE(offsetVector.firstIndex(), 280); - QCOMPARE(offsetVector.lastIndex(), 309); - - for (i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) { - QVERIFY(offsetVector.containsIndex(i)); - QCOMPARE(offsetVector.at(i), i); - } - - offsetVector.setCapacity(20); - - QCOMPARE(offsetVector.capacity(), 20); - QCOMPARE(offsetVector.count(), 20); - QCOMPARE(offsetVector.firstIndex(), 290); - QCOMPARE(offsetVector.lastIndex(), 309); - - for (i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) { - QVERIFY(offsetVector.containsIndex(i)); - QCOMPARE(offsetVector.at(i), i); - } -} - -#include "tst_qoffsetvector.moc" -- cgit v0.12