diff options
14 files changed, 516 insertions, 518 deletions
diff --git a/doc/src/examples/offsetvector.qdoc b/doc/src/examples/contiguouscache.qdoc index 256569e..22c97fa 100644 --- a/doc/src/examples/offsetvector.qdoc +++ b/doc/src/examples/contiguouscache.qdoc @@ -10,24 +10,24 @@ ****************************************************************************/ /*! - \example tools/offsetvector - \title Offset Vector Example + \example tools/contiguouscache + \title Contiguous Cache Example - The Offset Vector example shows how to use QOffsetVector to manage memory usage for + 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 QOffsetVector to manage a list rather than loading + 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 QOffsetVector is to cache as items are requested. When + 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/offsetvector/randomlistmodel.cpp 0 + \snippet examples/tools/contiguouscache/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 + of the contiguous cache's current range. It would have been equally valid to simply have the following code instead. \code @@ -37,27 +37,26 @@ 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. + 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 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. + 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 QOffsetVector::append() and QOffsetVector::prepend() the code ensures + 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 vector range. QOffsetVector::insert() can - potentially remove more than one item from the cache as QOffsetVector does not + 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/offsetvector/randomlistmodel.cpp 1 + \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 @@ -66,5 +65,5 @@ 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. + 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/offsetvector/main.cpp b/examples/tools/contiguouscache/main.cpp index bdeb3f3..bdeb3f3 100644 --- a/examples/tools/offsetvector/main.cpp +++ b/examples/tools/contiguouscache/main.cpp diff --git a/examples/tools/offsetvector/randomlistmodel.cpp b/examples/tools/contiguouscache/randomlistmodel.cpp index 5c0953b..5c0953b 100644 --- a/examples/tools/offsetvector/randomlistmodel.cpp +++ b/examples/tools/contiguouscache/randomlistmodel.cpp diff --git a/examples/tools/offsetvector/randomlistmodel.h b/examples/tools/contiguouscache/randomlistmodel.h index e102255..ad8cfad 100644 --- a/examples/tools/offsetvector/randomlistmodel.h +++ b/examples/tools/contiguouscache/randomlistmodel.h @@ -1,7 +1,7 @@ #ifndef RANDOMLISTMODEL_H #define RANDOMLISTMODEL_H -#include <QOffsetVector> +#include <QContiguousCache> #include <QAbstractListModel> class QTimer; @@ -19,7 +19,7 @@ private: void cacheRows(int, int) const; QString fetchRow(int) const; - mutable QOffsetVector<QString> m_rows; + mutable QContiguousCache<QString> m_rows; const int m_count; }; 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/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 <QDebug> + +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<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 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<T> &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/qoffsetvector.h b/src/corelib/tools/qcontiguouscache.h index 7030862..03012a2 100644 --- a/src/corelib/tools/qoffsetvector.h +++ b/src/corelib/tools/qcontiguouscache.h @@ -9,12 +9,12 @@ ** ****************************************************************************/ -#ifndef QCIRCULARBUFFER_H -#define QCIRCULARBUFFER_H +#ifndef QCONTIGUOUSCACHE_H +#define QCONTIGUOUSCACHE_H #include <QtCore/qatomic.h> -struct QOffsetVectorData +struct QContiguousCacheData { QBasicAtomicInt ref; int alloc; @@ -27,7 +27,7 @@ struct QOffsetVectorData }; template <typename T> -struct QOffsetVectorTypedData +struct QContiguousCacheTypedData { QBasicAtomicInt ref; int alloc; @@ -39,25 +39,25 @@ struct QOffsetVectorTypedData T array[1]; }; -class QOffsetVectorDevice; +class QContiguousCacheDevice; template<typename T> -class QOffsetVector { - typedef QOffsetVectorTypedData<T> Data; - union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; }; +class QContiguousCache { + typedef QContiguousCacheTypedData<T> Data; + union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; }; public: - explicit QOffsetVector(int capacity = 0); - QOffsetVector(const QOffsetVector<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } + explicit QContiguousCache(int capacity = 0); + QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } - inline ~QOffsetVector() { if (!d) return; if (!d->ref.deref()) free(d); } + inline ~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; } - QOffsetVector<T> &operator=(const QOffsetVector<T> &other); - bool operator==(const QOffsetVector<T> &other) const; - inline bool operator!=(const QOffsetVector<T> &other) const { return !(*this == other); } + 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; } @@ -97,7 +97,7 @@ public: private: void detach_helper(); - QOffsetVectorData *malloc(int alloc); + 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 @@ -107,9 +107,9 @@ private: }; template <typename T> -void QOffsetVector<T>::detach_helper() +void QContiguousCache<T>::detach_helper() { - union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; } x; + union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x; x.p = malloc(d->alloc); x.d->ref = 1; @@ -142,12 +142,12 @@ void QOffsetVector<T>::detach_helper() } template <typename T> -void QOffsetVector<T>::setCapacity(int asize) +void QContiguousCache<T>::setCapacity(int asize) { if (asize == d->alloc) return; detach(); - union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; } x; + union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x; x.p = malloc(asize); x.d->alloc = asize; x.d->count = qMin(d->count, asize); @@ -179,7 +179,7 @@ void QOffsetVector<T>::setCapacity(int asize) } template <typename T> -void QOffsetVector<T>::clear() +void QContiguousCache<T>::clear() { if (d->ref == 1) { if (QTypeInfo<T>::isComplex) { @@ -195,7 +195,7 @@ void QOffsetVector<T>::clear() } d->count = d->start = d->offset = 0; } else { - union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; } x; + union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x; x.p = malloc(d->alloc); x.d->ref = 1; x.d->alloc = d->alloc; @@ -207,13 +207,13 @@ void QOffsetVector<T>::clear() } template <typename T> -inline QOffsetVectorData *QOffsetVector<T>::malloc(int aalloc) +inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc) { - return static_cast<QOffsetVectorData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T))); + return static_cast<QContiguousCacheData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T))); } template <typename T> -QOffsetVector<T>::QOffsetVector(int asize) +QContiguousCache<T>::QContiguousCache(int asize) { p = malloc(asize); d->ref = 1; @@ -223,7 +223,7 @@ QOffsetVector<T>::QOffsetVector(int asize) } template <typename T> -QOffsetVector<T> &QOffsetVector<T>::operator=(const QOffsetVector<T> &other) +QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other) { other.d->ref.ref(); if (!d->ref.deref()) @@ -235,7 +235,7 @@ QOffsetVector<T> &QOffsetVector<T>::operator=(const QOffsetVector<T> &other) } template <typename T> -bool QOffsetVector<T>::operator==(const QOffsetVector<T> &other) const +bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const { if (other.d == d) return true; @@ -251,7 +251,7 @@ bool QOffsetVector<T>::operator==(const QOffsetVector<T> &other) const } template <typename T> -void QOffsetVector<T>::free(Data *x) +void QContiguousCache<T>::free(Data *x) { if (QTypeInfo<T>::isComplex) { int count = d->count; @@ -268,7 +268,7 @@ void QOffsetVector<T>::free(Data *x) } template <typename T> -void QOffsetVector<T>::append(const T &value) +void QContiguousCache<T>::append(const T &value) { detach(); if (QTypeInfo<T>::isComplex) { @@ -289,7 +289,7 @@ void QOffsetVector<T>::append(const T &value) } template<typename T> -void QOffsetVector<T>::prepend(const T &value) +void QContiguousCache<T>::prepend(const T &value) { detach(); if (d->start) @@ -311,7 +311,7 @@ void QOffsetVector<T>::prepend(const T &value) } template<typename T> -void QOffsetVector<T>::insert(int pos, const T &value) +void QContiguousCache<T>::insert(int pos, const T &value) { detach(); if (containsIndex(pos)) { @@ -337,15 +337,15 @@ void QOffsetVector<T>::insert(int pos, const T &value) } template <typename T> -inline const T &QOffsetVector<T>::at(int pos) const -{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QOffsetVector<T>::at", "index out of range"); return d->array[pos % d->alloc]; } +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 &QOffsetVector<T>::operator[](int pos) const -{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QOffsetVector<T>::at", "index out of range"); return d->array[pos % d->alloc]; } +inline const T &QContiguousCache<T>::operator[](int pos) const +{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; } template <typename T> // can use the non-inline one to modify the index range. -inline T &QOffsetVector<T>::operator[](int pos) +inline T &QContiguousCache<T>::operator[](int pos) { detach(); if (!containsIndex(pos)) @@ -354,7 +354,7 @@ inline T &QOffsetVector<T>::operator[](int pos) } template <typename T> -inline void QOffsetVector<T>::removeFirst() +inline void QContiguousCache<T>::removeFirst() { Q_ASSERT(d->count > 0); detach(); @@ -366,7 +366,7 @@ inline void QOffsetVector<T>::removeFirst() } template <typename T> -inline void QOffsetVector<T>::removeLast() +inline void QContiguousCache<T>::removeLast() { Q_ASSERT(d->count > 0); detach(); @@ -376,11 +376,11 @@ inline void QOffsetVector<T>::removeLast() } template <typename T> -inline T QOffsetVector<T>::takeFirst() +inline T QContiguousCache<T>::takeFirst() { T t = first(); removeFirst(); return t; } template <typename T> -inline T QOffsetVector<T>::takeLast() +inline T QContiguousCache<T>::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 <QDebug> - -void QOffsetVectorData::dump() const -{ - qDebug() << "capacity:" << alloc; - qDebug() << "count:" << count; - qDebug() << "start:" << start; - qDebug() << "offset:" << offset; -} - -/*! \class QOffsetVector - \brief The QOffsetVector class is a template class that provides a offset vector. - \ingroup tools - \ingroup shared - \reentrant - - The QOffsetVector class provides an efficient way of caching items for - display in a user interface view. It does this by providing a window - into a theoretical infinite sized vector. This has the advantage that - it matches how user interface views most commonly request the data, in - a set of rows localized around the current scrolled position. It also - allows the cache to use less overhead than QCache both in terms of - performance and memory. In turn, unlike a QCache, the key has to be - an int and has to be contiguous. That is to say if an item is inserted - at index 85, then if there were no previous items at 84 or 86 then the - cache will be cleared before the new item at 85 is inserted. If this - restriction is not suitable consider using QCache instead. - - The simplest way of using an offset vector is to use the append() - and prepend() functions to slide the window to where it is needed. - -\code -MyRecord record(int row) const -{ - Q_ASSERT(row >= 0 && row < count()); - - while(row > cache.lastIndex()) - cache.append(slowFetchRecord(cache.lastIndex()+1)); - while(row < cache.firstIndex()) - cache.prepend(slowFetchRecord(cache.firstIndex()-1)); - - return cache.at(row); -} -\endcode - - The append() and prepend() functions cause the vector window to move to - where the current row is requested from. This usage can be further - optimized by using the insert() function to reset the vector window to - a row in the case where the row is a long way from the current row. It - may also be worth while to fetch multiple records into the cache if - it is faster to retrieve them in a batch operation. - - See the The \l{Offset Vector Example}{Offset Vector} example. -*/ - -/*! \fn QOffsetVector::QOffsetVector(int capacity) - - Constructs a vector with the given \a capacity. - - \sa setCapacity() -*/ - -/*! \fn QOffsetVector::QOffsetVector(const QOffsetVector<T> &other) - - Constructs a copy of \a other. - - This operation takes \l{constant time}, because QOffsetVector is - \l{implicitly shared}. This makes returning a QOffsetVector from a - function very fast. If a shared instance is modified, it will be - copied (copy-on-write), and that takes \l{linear time}. - - \sa operator=() -*/ - -/*! \fn QOffsetVector::~QOffsetVector() - Destorys the vector. -*/ - -/*! \fn void QOffsetVector::detach() - - \internal -*/ - -/*! \fn bool QOffsetVector::isDetached() const - - \internal -*/ - -/*! \fn void QOffsetVector::setSharable(bool sharable) - - \internal -*/ - - -/*! \fn QOffsetVector<T> &QOffsetVector::operator=(const QOffsetVector<T> &other) - - Assigns \a other to this vector and returns a reference to this vector. -*/ - -/*! \fn bool QOffsetVector::operator==(const QOffsetVector<T> &other) const - - Returns true if \a other is equal to this vector; otherwise returns false. - - Two vectors are considered equal if they contain the same values at the same - indexes. This function requires the value type to implement the \c operator==(). - - \sa operator!=() -*/ - -/*! \fn bool QOffsetVector::operator!=(const QOffsetVector<T> &other) const - - Returns true if \a other is not equal to this vector; otherwise - returns false. - - Two vector are considered equal if they contain the same values at the same - indexes. This function requires the value type to implement the \c operator==(). - - \sa operator==() -*/ - -/*! \fn int QOffsetVector::capacity() const - - Returns the number of items the vector can store before it is full. - When a vector contains a number of items equal to its capacity, adding new - items will cause items furthest from the added item to be removed. - - \sa setCapacity(), size() -*/ - -/*! \fn int QOffsetVector::count() const - - \overload - - Same as size(). -*/ - -/*! \fn int QOffsetVector::size() const - - Returns the number of items contained within the vector. - - \sa capacity() -*/ - -/*! \fn bool QOffsetVector::isEmpty() const - - Returns true if no items are stored within the vector. - - \sa size(), capacity() -*/ - -/*! \fn bool QOffsetVector::isFull() const - - Returns true if the number of items stored within the vector is equal - to the capacity of the vector. - - \sa size(), capacity() -*/ - -/*! \fn int QOffsetVector::available() const - - Returns the number of items that can be added to the vector before it becomes full. - - \sa size(), capacity(), isFull() -*/ - -/*! \fn void QOffsetVector::clear() - - Removes all items from the vector. The capacity is unchanged. -*/ - -/*! \fn void QOffsetVector::setCapacity(int size) - - Sets the capacity of the vector to the given \a size. A vector can hold a - number of items equal to its capacity. When inserting, appending or prepending - items to the vector, if the vector is already full then the item furthest from - the added item will be removed. - - If the given \a size is smaller than the current count of items in the vector - then only the last \a size items from the vector will remain. - - \sa capacity(), isFull() -*/ - -/*! \fn const T &QOffsetVector::at(int i) const - - Returns the item at index position \a i in the vector. \a i must - be a valid index position in the vector (i.e, firstIndex() <= \a i <= lastIndex()). - - The indexes in the vector refer to number of positions the item is from the - first item appended into the vector. That is to say a vector with a capacity of - 100, that has had 150 items appended will have a valid index range of - 50 to 149. This allows inserting an retrieving items into the vector based - on a theoretical infinite list - - \sa firstIndex(), lastIndex(), insert(), operator[]() -*/ - -/*! \fn T &QOffsetVector::operator[](int i) - - Returns the item at index position \a i as a modifiable reference. If - the vector does not contain an item at the given index position \a i - then it will first insert an empty item at that position. - - In most cases it is better to use either at() or insert(). - - Note that using non-const operators can cause QOffsetVector to do a deep - copy. - - \sa insert(), at() -*/ - -/*! \fn const T &QOffsetVector::operator[](int i) const - - \overload - - Same as at(\a i). -*/ - -/*! \fn void QOffsetVector::append(const T &value) - - Inserts \a value at the end of the vector. If the vector is already full - the item at the start of the vector will be removed. - - \sa prepend(), insert(), isFull() -*/ - -/*! \fn void QOffsetVector::prepend(const T &value) - - Inserts \a value at the start of the vector. If the vector is already full - the item at the end of the vector will be removed. - - \sa append(), insert(), isFull() -*/ - -/*! \fn void QOffsetVector::insert(int i, const T &value) - - Inserts the \a value at the index position \a i. If the vector already contains - an item at \a i then that value is replaced. If \a i is either one more than - lastIndex() or one less than firstIndex() it is the equivalent to an append() - or a prepend(). - - If the given index \a i is not within the current range of the vector nor adjacent - to the bounds of the vector's index range the vector is first cleared before - inserting the item. At this point the vector will have a size of 1. It is worth - while then taking effort to insert items in an order than starts adjacent to the - current index range for the vector. - - \sa prepend(), append(), isFull(), firstIndex(), lastIndex() -*/ - -/*! \fn bool QOffsetVector::containsIndex(int i) const - - Returns true if the vector's index range includes the given index \a i. - - \sa firstIndex(), lastIndex() -*/ - -/*! \fn int QOffsetVector::firstIndex() const - Returns the first valid index in the vector. The index will be invalid if the - vector is empty. However the following code is valid even when the vector is empty: - - \code - for (int i = vector.firstIndex(); i <= vector.lastIndex(); ++i) - qDebug() << "Item" << i << "of the vector is" << vector.at(i); - \endcode - - \sa capacity(), size(), lastIndex() -*/ - -/*! \fn int QOffsetVector::lastIndex() const - - Returns the last valid index in the vector. If the vector is empty will return -1. - - \code - for (int i = vector.firstIndex(); i <= vector.lastIndex(); ++i) - qDebug() << "Item" << i << "of the vector is" << vector.at(i); - \endcode - - \sa capacity(), size(), firstIndex() -*/ - - -/*! \fn T &QOffsetVector::first() - - Returns a reference to the first item in the vector. This function - assumes that the vector isn't empty. - - \sa last(), isEmpty() -*/ - -/*! \fn T &QOffsetVector::last() - - Returns a reference to the last item in the vector. This function - assumes that the vector isn't empty. - - \sa first(), isEmpty() -*/ - -/*! \fn const T& QOffsetVector::first() const - - \overload -*/ - -/*! \fn const T& QOffsetVector::last() const - - \overload -*/ - -/*! \fn void QOffsetVector::removeFirst() - - Removes the first item from the vector. This function assumes that - the vector isn't empty. - - \sa removeLast() -*/ - -/*! \fn void QOffsetVector::removeLast() - - Removes the last item from the vector. This function assumes that - the vector isn't empty. - - \sa removeFirst() -*/ - -/*! \fn T QOffsetVector::takeFirst() - - Removes the first item in the vector and returns it. - - If you don't sue the return value, removeFirst() is more efficient. - - \sa takeLast(), removeFirst() -*/ - -/*! \fn T QOffsetVector::takeLast() - - Removes the last item in the vector and returns it. - - If you don't sue the return value, removeLast() is more efficient. - - \sa takeFirst(), removeLast() -*/ - -/*! \fn void QOffsetVector::dump() const - - \internal - - Sends information about the vector's internal structure to qDebug() -*/ diff --git a/src/corelib/tools/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/qoffsetvector/tst_qoffsetvector.cpp b/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp index 439ea2c..493032a 100644 --- a/tests/auto/qoffsetvector/tst_qoffsetvector.cpp +++ b/tests/auto/qcontiguouscache/tst_qcontiguouscache.cpp @@ -13,7 +13,7 @@ #include <QList> #include <QString> #include <QCache> -#include <QOffsetVector> +#include <QContiguousCache> #include <QDebug> #include <stdio.h> @@ -21,16 +21,16 @@ #if defined(FORCE_UREF) template <class aT> -inline QDebug &operator<<(QDebug debug, const QOffsetVector<aT> &offsetVector) +inline QDebug &operator<<(QDebug debug, const QContiguousCache<aT> &contiguousCache) #else template <class aT> -inline QDebug operator<<(QDebug debug, const QOffsetVector<aT> &offsetVector) +inline QDebug operator<<(QDebug debug, const QContiguousCache<aT> &contiguousCache) #endif { - debug.nospace() << "QOffsetVector("; - for (int i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) { - debug << offsetVector[i]; - if (i != offsetVector.lastIndex()) + debug.nospace() << "QContiguousCache("; + for (int i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) { + debug << contiguousCache[i]; + if (i != contiguousCache.lastIndex()) debug << ", "; } debug << ")"; @@ -42,12 +42,12 @@ inline QDebug operator<<(QDebug debug, const QOffsetVector<aT> &offsetVector) #define QBENCHMARK #endif -class tst_QOffsetVector : public QObject +class tst_QContiguousCache : public QObject { Q_OBJECT public: - tst_QOffsetVector() {} - virtual ~tst_QOffsetVector() {} + tst_QContiguousCache() {} + virtual ~tst_QContiguousCache() {} private slots: void empty(); void forwardBuffer(); @@ -58,16 +58,16 @@ private slots: void operatorAt(); void cacheBenchmark(); - void offsetVectorBenchmark(); + void contiguousCacheBenchmark(); void setCapacity(); }; -QTEST_MAIN(tst_QOffsetVector) +QTEST_MAIN(tst_QContiguousCache) -void tst_QOffsetVector::empty() +void tst_QContiguousCache::empty() { - QOffsetVector<int> c(10); + QContiguousCache<int> c(10); QCOMPARE(c.capacity(), 10); QCOMPARE(c.count(), 0); QVERIFY(c.isEmpty()); @@ -85,10 +85,10 @@ void tst_QOffsetVector::empty() QCOMPARE(c.capacity(), 10); } -void tst_QOffsetVector::forwardBuffer() +void tst_QContiguousCache::forwardBuffer() { int i; - QOffsetVector<int> c(10); + QContiguousCache<int> c(10); for(i = 1; i < 30; ++i) { c.append(i); QCOMPARE(c.first(), qMax(1, i-9)); @@ -106,12 +106,12 @@ void tst_QOffsetVector::forwardBuffer() } } -void tst_QOffsetVector::scrollingList() +void tst_QContiguousCache::scrollingList() { int i; - QOffsetVector<int> c(10); + QContiguousCache<int> c(10); - // Once allocated QOffsetVector should not + // Once allocated QContiguousCache should not // allocate any additional memory for non // complex data types. QBENCHMARK { @@ -223,81 +223,81 @@ private: RefCountingClassData *d; }; -void tst_QOffsetVector::complexType() +void tst_QContiguousCache::complexType() { RefCountingClass original; - QOffsetVector<RefCountingClass> offsetVector(10); - offsetVector.append(original); + QContiguousCache<RefCountingClass> contiguousCache(10); + contiguousCache.append(original); QCOMPARE(original.refCount(), 3); - offsetVector.removeFirst(); + contiguousCache.removeFirst(); QCOMPARE(original.refCount(), 2); // shared null, 'original'. - offsetVector.append(original); + contiguousCache.append(original); QCOMPARE(original.refCount(), 3); - offsetVector.clear(); + contiguousCache.clear(); QCOMPARE(original.refCount(), 2); for(int i = 0; i < 100; ++i) - offsetVector.insert(i, original); + contiguousCache.insert(i, original); - QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector. + QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache. - offsetVector.clear(); + contiguousCache.clear(); QCOMPARE(original.refCount(), 2); for (int i = 0; i < 100; i++) - offsetVector.append(original); + contiguousCache.append(original); - QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector. - offsetVector.clear(); + QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache. + contiguousCache.clear(); QCOMPARE(original.refCount(), 2); for (int i = 0; i < 100; i++) - offsetVector.prepend(original); + contiguousCache.prepend(original); - QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in offsetVector. - offsetVector.clear(); + QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache. + contiguousCache.clear(); QCOMPARE(original.refCount(), 2); for (int i = 0; i < 100; i++) - offsetVector.append(original); + contiguousCache.append(original); - offsetVector.takeLast(); + contiguousCache.takeLast(); QCOMPARE(original.refCount(), 11); - offsetVector.takeFirst(); + contiguousCache.takeFirst(); QCOMPARE(original.refCount(), 10); } -void tst_QOffsetVector::operatorAt() +void tst_QContiguousCache::operatorAt() { RefCountingClass original; - QOffsetVector<RefCountingClass> offsetVector(10); + QContiguousCache<RefCountingClass> contiguousCache(10); for (int i = 25; i < 35; ++i) - offsetVector[i] = original; + contiguousCache[i] = original; - QCOMPARE(original.refCount(), 12); // shared null, orig, items in vector + QCOMPARE(original.refCount(), 12); // shared null, orig, items in cache // verify const access does not copy items. - const QOffsetVector<RefCountingClass> copy(offsetVector); + 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) - offsetVector[25] = original; + 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 QOffsetVector doesn't support pointers (won't free them). + 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 QOffsetVector use cases here, QCache has its own + testing QContiguousCache use cases here, QCache has its own areas where it is the more sensible class to use. */ -void tst_QOffsetVector::cacheBenchmark() +void tst_QContiguousCache::cacheBenchmark() { QBENCHMARK { QCache<int, int> cache; @@ -308,54 +308,54 @@ void tst_QOffsetVector::cacheBenchmark() } } -void tst_QOffsetVector::offsetVectorBenchmark() +void tst_QContiguousCache::contiguousCacheBenchmark() { QBENCHMARK { - QOffsetVector<int> offsetVector(100); + QContiguousCache<int> contiguousCache(100); for (int i = 0; i < 1000; i++) - offsetVector.insert(i, i); + contiguousCache.insert(i, i); } } -void tst_QOffsetVector::setCapacity() +void tst_QContiguousCache::setCapacity() { int i; - QOffsetVector<int> offsetVector(100); + QContiguousCache<int> contiguousCache(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); + 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); } - offsetVector.setCapacity(150); + contiguousCache.setCapacity(150); - QCOMPARE(offsetVector.capacity(), 150); - QCOMPARE(offsetVector.count(), 30); - QCOMPARE(offsetVector.firstIndex(), 280); - QCOMPARE(offsetVector.lastIndex(), 309); + QCOMPARE(contiguousCache.capacity(), 150); + QCOMPARE(contiguousCache.count(), 30); + QCOMPARE(contiguousCache.firstIndex(), 280); + QCOMPARE(contiguousCache.lastIndex(), 309); - for (i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) { - QVERIFY(offsetVector.containsIndex(i)); - QCOMPARE(offsetVector.at(i), i); + for (i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) { + QVERIFY(contiguousCache.containsIndex(i)); + QCOMPARE(contiguousCache.at(i), i); } - offsetVector.setCapacity(20); + contiguousCache.setCapacity(20); - QCOMPARE(offsetVector.capacity(), 20); - QCOMPARE(offsetVector.count(), 20); - QCOMPARE(offsetVector.firstIndex(), 290); - QCOMPARE(offsetVector.lastIndex(), 309); + QCOMPARE(contiguousCache.capacity(), 20); + QCOMPARE(contiguousCache.count(), 20); + QCOMPARE(contiguousCache.firstIndex(), 290); + QCOMPARE(contiguousCache.lastIndex(), 309); - for (i = offsetVector.firstIndex(); i <= offsetVector.lastIndex(); ++i) { - QVERIFY(offsetVector.containsIndex(i)); - QCOMPARE(offsetVector.at(i), i); + for (i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) { + QVERIFY(contiguousCache.containsIndex(i)); + QCOMPARE(contiguousCache.at(i), i); } } -#include "tst_qoffsetvector.moc" +#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 - - - |