summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--doc/src/examples/offsetvector.qdoc70
-rw-r--r--examples/tools/offsetvector/main.cpp15
-rw-r--r--examples/tools/offsetvector/offsetvector.pro9
-rw-r--r--examples/tools/offsetvector/randomlistmodel.cpp56
-rw-r--r--examples/tools/offsetvector/randomlistmodel.h26
-rw-r--r--examples/tools/tools.pro1
-rw-r--r--src/corelib/tools/qoffsetvector.cpp360
-rw-r--r--src/corelib/tools/qoffsetvector.h386
-rw-r--r--src/corelib/tools/tools.pri2
-rw-r--r--tests/auto/auto.pro1
-rw-r--r--tests/auto/qoffsetvector/qoffsetvector.pro8
-rw-r--r--tests/auto/qoffsetvector/tst_qoffsetvector.cpp361
12 files changed, 1295 insertions, 0 deletions
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 <QListView>
+#include <QApplication>
+
+int main(int c, char **v)
+{
+ QApplication a(c, v);
+
+ QListView view;
+ view.setUniformItemSizes(true);
+ view.setModel(new RandomListModel(&view));
+ view.show();
+
+ return a.exec();
+}
diff --git a/examples/tools/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 <QOffsetVector>
+#include <QAbstractListModel>
+
+class QTimer;
+class RandomListModel : public QAbstractListModel
+{
+ Q_OBJECT
+public:
+ RandomListModel(QObject *parent = 0);
+ ~RandomListModel();
+
+ int rowCount(const QModelIndex & = QModelIndex()) const;
+ QVariant data(const QModelIndex &, int) const;
+
+private:
+ void cacheRows(int, int) const;
+ QString fetchRow(int) const;
+
+ mutable QOffsetVector<QString> 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 <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/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 <QtCore/qatomic.h>
+
+struct QOffsetVectorData
+{
+ QBasicAtomicInt ref;
+ int alloc;
+ int count;
+ int start;
+ int offset;
+ uint sharable : 1;
+
+ void dump() const;
+};
+
+template <typename T>
+struct QOffsetVectorTypedData
+{
+ QBasicAtomicInt ref;
+ int alloc;
+ int count;
+ int start;
+ int offset;
+ uint sharable : 1;
+
+ T array[1];
+};
+
+class QOffsetVectorDevice;
+
+template<typename T>
+class QOffsetVector {
+ typedef QOffsetVectorTypedData<T> Data;
+ union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; };
+public:
+ explicit QOffsetVector(int capacity = 0);
+ QOffsetVector(const QOffsetVector<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 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); }
+
+ 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<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
+ }
+};
+
+template <typename T>
+void QOffsetVector<T>::detach_helper()
+{
+ union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; } x;
+
+ x.p = malloc(d->alloc);
+ x.d->ref = 1;
+ x.d->count = d->count;
+ x.d->start = d->start;
+ x.d->offset = d->offset;
+ x.d->alloc = d->alloc;
+ x.d->sharable = true;
+
+ T *dest = x.d->array + x.d->start;
+ T *src = d->array + d->start;
+ int count = x.d->count;
+ while (count--) {
+ if (QTypeInfo<T>::isComplex) {
+ new (dest) T(*src);
+ } else {
+ *dest = *src;
+ }
+ dest++;
+ if (dest == x.d->array + x.d->alloc)
+ dest = x.d->array;
+ src++;
+ if (src == d->array + d->alloc)
+ src = d->array;
+ }
+
+ if (!d->ref.deref())
+ free(d);
+ d = x.d;
+}
+
+template <typename T>
+void QOffsetVector<T>::setCapacity(int asize)
+{
+ if (asize == d->alloc)
+ return;
+ detach();
+ union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; } x;
+ x.p = malloc(asize);
+ x.d->alloc = asize;
+ x.d->count = qMin(d->count, asize);
+ x.d->offset = d->offset + d->count - x.d->count;
+ x.d->start = x.d->offset % x.d->alloc;
+ /* 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<T>::isComplex) {
+ new (dest) T(*src);
+ } else {
+ *dest = *src;
+ }
+ if (dest == x.d->array)
+ dest = x.d->array + x.d->alloc;
+ dest--;
+ if (src == d->array)
+ src = d->array + d->alloc;
+ src--;
+ }
+ /* free old */
+ free(d);
+ d = x.d;
+}
+
+template <typename T>
+void QOffsetVector<T>::clear()
+{
+ if (d->ref == 1) {
+ if (QTypeInfo<T>::isComplex) {
+ int count = d->count;
+ T * i = d->array + d->start;
+ T * e = d->array + d->alloc;
+ while (count--) {
+ i->~T();
+ i++;
+ if (i == e)
+ i = d->array;
+ }
+ }
+ d->count = d->start = d->offset = 0;
+ } else {
+ union { QOffsetVectorData *p; QOffsetVectorTypedData<T> *d; } x;
+ x.p = malloc(d->alloc);
+ x.d->ref = 1;
+ x.d->alloc = d->alloc;
+ x.d->count = x.d->start = x.d->offset = 0;
+ x.d->sharable = true;
+ if (!d->ref.deref()) free(d);
+ d = x.d;
+ }
+}
+
+template <typename T>
+inline QOffsetVectorData *QOffsetVector<T>::malloc(int aalloc)
+{
+ return static_cast<QOffsetVectorData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
+}
+
+template <typename T>
+QOffsetVector<T>::QOffsetVector(int asize)
+{
+ p = malloc(asize);
+ d->ref = 1;
+ d->alloc = asize;
+ d->count = d->start = d->offset = 0;
+ d->sharable = true;
+}
+
+template <typename T>
+QOffsetVector<T> &QOffsetVector<T>::operator=(const QOffsetVector<T> &other)
+{
+ other.d->ref.ref();
+ if (!d->ref.deref())
+ free(d);
+ d = other.d;
+ if (!d->sharable)
+ detach_helper();
+ return *this;
+}
+
+template <typename T>
+bool QOffsetVector<T>::operator==(const QOffsetVector<T> &other) const
+{
+ if (other.d == d)
+ return true;
+ if (other.d->start != d->start
+ || other.d->count != d->count
+ || other.d->offset != d->offset
+ || other.d->alloc != d->alloc)
+ return false;
+ for (int i = firstIndex(); i <= lastIndex(); ++i)
+ if (!(at(i) == other.at(i)))
+ return false;
+ return true;
+}
+
+template <typename T>
+void QOffsetVector<T>::free(Data *x)
+{
+ if (QTypeInfo<T>::isComplex) {
+ int count = d->count;
+ T * i = d->array + d->start;
+ T * e = d->array + d->alloc;
+ while (count--) {
+ i->~T();
+ i++;
+ if (i == e)
+ i = d->array;
+ }
+ }
+ qFree(x);
+}
+
+template <typename T>
+void QOffsetVector<T>::append(const T &value)
+{
+ detach();
+ if (QTypeInfo<T>::isComplex) {
+ if (d->count == d->alloc)
+ (d->array + (d->start+d->count) % d->alloc)->~T();
+ new (d->array + (d->start+d->count) % d->alloc) T(value);
+ } else {
+ d->array[(d->start+d->count) % d->alloc] = value;
+ }
+
+ if (d->count == d->alloc) {
+ d->start++;
+ d->start %= d->alloc;
+ d->offset++;
+ } else {
+ d->count++;
+ }
+}
+
+template<typename T>
+void QOffsetVector<T>::prepend(const T &value)
+{
+ detach();
+ if (d->start)
+ d->start--;
+ else
+ d->start = d->alloc-1;
+ d->offset--;
+
+ if (d->count != d->alloc)
+ d->count++;
+ else
+ if (d->count == d->alloc)
+ (d->array + d->start)->~T();
+
+ if (QTypeInfo<T>::isComplex)
+ new (d->array + d->start) T(value);
+ else
+ d->array[d->start] = value;
+}
+
+template<typename T>
+void QOffsetVector<T>::insert(int pos, const T &value)
+{
+ detach();
+ if (containsIndex(pos)) {
+ if(QTypeInfo<T>::isComplex)
+ new (d->array + pos % d->alloc) T(value);
+ else
+ d->array[pos % d->alloc] = value;
+ } else if (pos == d->offset-1)
+ prepend(value);
+ else if (pos == d->offset+d->count)
+ append(value);
+ else {
+ // we don't leave gaps.
+ clear();
+ d->offset = d->start = pos;
+ d->start %= d->alloc;
+ d->count = 1;
+ if (QTypeInfo<T>::isComplex)
+ new (d->array + d->start) T(value);
+ else
+ d->array[d->start] = value;
+ }
+}
+
+template <typename T>
+inline const T &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]; }
+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]; }
+template <typename T>
+
+// can use the non-inline one to modify the index range.
+inline T &QOffsetVector<T>::operator[](int pos)
+{
+ detach();
+ if (!containsIndex(pos))
+ insert(pos, T());
+ return d->array[pos % d->alloc];
+}
+
+template <typename T>
+inline void QOffsetVector<T>::removeFirst()
+{
+ Q_ASSERT(d->count > 0);
+ detach();
+ d->count--;
+ if (QTypeInfo<T>::isComplex)
+ (d->array + d->start)->~T();
+ d->start = (d->start + 1) % d->alloc;
+ d->offset++;
+}
+
+template <typename T>
+inline void QOffsetVector<T>::removeLast()
+{
+ Q_ASSERT(d->count > 0);
+ detach();
+ d->count--;
+ if (QTypeInfo<T>::isComplex)
+ (d->array + (d->start + d->count) % d->alloc)->~T();
+}
+
+template <typename T>
+inline T QOffsetVector<T>::takeFirst()
+{ T t = first(); removeFirst(); return t; }
+
+template <typename T>
+inline T QOffsetVector<T>::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 <QObject>
+#include <QTest>
+#include <QList>
+#include <QString>
+#include <QCache>
+#include <QOffsetVector>
+
+#include <QDebug>
+#include <stdio.h>
+
+
+#if defined(FORCE_UREF)
+template <class aT>
+inline QDebug &operator<<(QDebug debug, const QOffsetVector<aT> &offsetVector)
+#else
+template <class aT>
+inline QDebug operator<<(QDebug debug, const QOffsetVector<aT> &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<int> 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<int> 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<int> 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<RefCountingClass> 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<RefCountingClass> 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<RefCountingClass> 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<int, int> cache;
+ cache.setMaxCost(100);
+
+ for (int i = 0; i < 1000; i++)
+ cache.insert(i, new int(i));
+ }
+}
+
+void tst_QOffsetVector::offsetVectorBenchmark()
+{
+ QBENCHMARK {
+ QOffsetVector<int> offsetVector(100);
+ for (int i = 0; i < 1000; i++)
+ offsetVector.insert(i, i);
+ }
+}
+
+void tst_QOffsetVector::setCapacity()
+{
+ int i;
+ QOffsetVector<int> 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"
generated by cgit v0.12 at 2024-09-16 03:49:40 (GMT)