From 0d00798f6bdd098dbb59c6f1da5be5efd6c283fa Mon Sep 17 00:00:00 2001 From: Rhys Weatherley Date: Tue, 24 Mar 2009 11:07:00 +1000 Subject: Squashed commit of the following: commit 39de3862f5678b3226b4932eeb342c4a023d2f2b Author: Ian Walters Date: Thu Feb 19 14:16:05 2009 +1000 Fixes: Test runs (and passes), doc links. Task: QT-308 Details: Minor changes related to the code having moved. commit 5a8910dd1018fb228d0e2e2819ea429577bfa834 Author: Ian Walters Date: Thu Feb 19 09:47:20 2009 +1000 Fixes: Checkin of QOffsetVector stuff for branch Task: QT-308 Details: Files originally from research/qcircularbuffer This checkin likely won't compile. Just a copy for now. --- doc/src/examples/offsetvector.qdoc | 70 +++++ 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 | 1 + src/corelib/tools/qoffsetvector.cpp | 360 ++++++++++++++++++++++ src/corelib/tools/qoffsetvector.h | 386 ++++++++++++++++++++++++ src/corelib/tools/tools.pri | 2 + tests/auto/auto.pro | 1 + tests/auto/qoffsetvector/qoffsetvector.pro | 8 + tests/auto/qoffsetvector/tst_qoffsetvector.cpp | 361 ++++++++++++++++++++++ 12 files changed, 1295 insertions(+) create mode 100644 doc/src/examples/offsetvector.qdoc create mode 100644 examples/tools/offsetvector/main.cpp create mode 100644 examples/tools/offsetvector/offsetvector.pro create mode 100644 examples/tools/offsetvector/randomlistmodel.cpp create mode 100644 examples/tools/offsetvector/randomlistmodel.h create mode 100644 src/corelib/tools/qoffsetvector.cpp create mode 100644 src/corelib/tools/qoffsetvector.h create mode 100644 tests/auto/qoffsetvector/qoffsetvector.pro create mode 100644 tests/auto/qoffsetvector/tst_qoffsetvector.cpp diff --git a/doc/src/examples/offsetvector.qdoc b/doc/src/examples/offsetvector.qdoc new file mode 100644 index 0000000..256569e --- /dev/null +++ b/doc/src/examples/offsetvector.qdoc @@ -0,0 +1,70 @@ +/**************************************************************************** +** +** 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/offsetvector/main.cpp b/examples/tools/offsetvector/main.cpp new file mode 100644 index 0000000..bdeb3f3 --- /dev/null +++ b/examples/tools/offsetvector/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/offsetvector/offsetvector.pro b/examples/tools/offsetvector/offsetvector.pro new file mode 100644 index 0000000..f329bb9 --- /dev/null +++ b/examples/tools/offsetvector/offsetvector.pro @@ -0,0 +1,9 @@ +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 new file mode 100644 index 0000000..5c0953b --- /dev/null +++ b/examples/tools/offsetvector/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/offsetvector/randomlistmodel.h b/examples/tools/offsetvector/randomlistmodel.h new file mode 100644 index 0000000..e102255 --- /dev/null +++ b/examples/tools/offsetvector/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 QOffsetVector m_rows; + const int m_count; +}; + +#endif diff --git a/examples/tools/tools.pro b/examples/tools/tools.pro index 79f0faa..424f286 100644 --- a/examples/tools/tools.pro +++ b/examples/tools/tools.pro @@ -5,6 +5,7 @@ SUBDIRS = codecs \ customcompleter \ echoplugin \ i18n \ + offsetvector \ plugandpaintplugins \ plugandpaint \ regexp \ diff --git a/src/corelib/tools/qoffsetvector.cpp b/src/corelib/tools/qoffsetvector.cpp new file mode 100644 index 0000000..32d2872 --- /dev/null +++ b/src/corelib/tools/qoffsetvector.cpp @@ -0,0 +1,360 @@ +/**************************************************************************** +** +** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the $MODULE$ of the Qt Toolkit. +** +** $TROLLTECH_DUAL_LICENSE$ +** +****************************************************************************/ + +#include "qoffsetvector.h" +#include + +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 new file mode 100644 index 0000000..7030862 --- /dev/null +++ b/src/corelib/tools/qoffsetvector.h @@ -0,0 +1,386 @@ +/**************************************************************************** +** +** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the $MODULE$ of the Qt Toolkit. +** +** $TROLLTECH_DUAL_LICENSE$ +** +****************************************************************************/ + +#ifndef QCIRCULARBUFFER_H +#define QCIRCULARBUFFER_H + +#include + +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 e5bf7e4..626c9e5 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -19,6 +19,7 @@ HEADERS += \ tools/qlocale_p.h \ tools/qlocale_data_p.h \ tools/qmap.h \ + tools/qoffsetvector.h \ tools/qpodlist_p.h \ tools/qpoint.h \ tools/qqueue.h \ @@ -53,6 +54,7 @@ SOURCES += \ tools/qlocale.cpp \ tools/qpoint.cpp \ tools/qmap.cpp \ + tools/qoffsetvector.cpp \ tools/qrect.cpp \ tools/qregexp.cpp \ tools/qshareddata.cpp \ diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro index 19f6b43..5d71e79 100644 --- a/tests/auto/auto.pro +++ b/tests/auto/auto.pro @@ -209,6 +209,7 @@ SUBDIRS += bic \ qnumeric \ qobject \ qobjectrace \ + qoffsetvector \ qpaintengine \ qpainter \ qpainterpath \ diff --git a/tests/auto/qoffsetvector/qoffsetvector.pro b/tests/auto/qoffsetvector/qoffsetvector.pro new file mode 100644 index 0000000..0b801f3 --- /dev/null +++ b/tests/auto/qoffsetvector/qoffsetvector.pro @@ -0,0 +1,8 @@ +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 new file mode 100644 index 0000000..439ea2c --- /dev/null +++ b/tests/auto/qoffsetvector/tst_qoffsetvector.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 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