summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools')
-rw-r--r--src/corelib/tools/qcontiguouscache.cpp435
-rw-r--r--src/corelib/tools/qcontiguouscache.h424
-rw-r--r--src/corelib/tools/qtimeline.cpp4
-rw-r--r--src/corelib/tools/qvector.h170
-rw-r--r--src/corelib/tools/tools.pri2
5 files changed, 944 insertions, 91 deletions
diff --git a/src/corelib/tools/qcontiguouscache.cpp b/src/corelib/tools/qcontiguouscache.cpp
new file mode 100644
index 0000000..7db3a5a
--- /dev/null
+++ b/src/corelib/tools/qcontiguouscache.cpp
@@ -0,0 +1,435 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain
+** additional rights. These rights are described in the Nokia Qt LGPL
+** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qcontiguouscache.h"
+#include <QDebug>
+
+QT_BEGIN_NAMESPACE
+
+void QContiguousCacheData::dump() const
+{
+ qDebug() << "capacity:" << alloc;
+ qDebug() << "count:" << count;
+ qDebug() << "start:" << start;
+ qDebug() << "offset:" << offset;
+}
+
+/*! \class QContiguousCache
+ \brief The QContiguousCache class is a template class that provides a contiguous cache.
+ \ingroup tools
+ \ingroup shared
+ \reentrant
+
+ The QContiguousCache class provides an efficient way of caching items for
+ display in a user interface view. Unlike QCache, it adds a restriction
+ that elements within the cache are contiguous. This has the advantage
+ of matching how user interface views most commonly request data, as
+ a set of rows localized around the current scrolled position. This
+ restriction allows the cache to consume less memory and processor
+ cycles than QCache. The QContiguousCache class also can provide
+ an upper bound on memory usage via setCapacity().
+
+ The simplest way of using a contiguous cache is to use the append()
+ and prepend().
+
+\code
+MyRecord record(int row) const
+{
+ Q_ASSERT(row >= 0 && row < count());
+
+ while(row > cache.lastIndex())
+ cache.append(slowFetchRecord(cache.lastIndex()+1));
+ while(row < cache.firstIndex())
+ cache.prepend(slowFetchRecord(cache.firstIndex()-1));
+
+ return cache.at(row);
+}
+\endcode
+
+ If the cache is full then the item at the opposite end of the cache from
+ where the new item is appended or prepended will be removed.
+
+ This usage can be further optimized by using the insert() function
+ in the case where the requested row is a long way from the currently cached
+ items. If there is a gap between where the new item is inserted and the currently
+ cached items then the existing cached items are first removed to retain
+ the contiguous nature of the cache. Hence it is important to take some care then
+ when using insert() in order to avoid unwanted clearing of the cache.
+
+ The range of valid indexes for the QContiguousCache class are from
+ 0 to INT_MAX. Calling prepend() such that the first index would become less
+ than 0 or append() such that the last index would become greater
+ than INT_MAX can result in the indexes of the cache being invalid.
+ When the cache indexes are invalid it is important to call
+ normalizeIndexes() before calling any of containsIndex(), firstIndex(),
+ lastIndex(), at() or the [] operator. Calling these
+ functions when the cache has invalid indexes will result in undefined
+ behavior. The indexes can be checked by using areIndexesValid()
+
+ In most cases the indexes will not exceed 0 to INT_MAX, and
+ normalizeIndexes() will not need to be used.
+
+ See the \l{Contiguous Cache Example}{Contiguous Cache} example.
+*/
+
+/*! \fn QContiguousCache::QContiguousCache(int capacity)
+
+ Constructs a cache with the given \a capacity.
+
+ \sa setCapacity()
+*/
+
+/*! \fn QContiguousCache::QContiguousCache(const QContiguousCache<T> &other)
+
+ Constructs a copy of \a other.
+
+ This operation takes \l{constant time}, because QContiguousCache is
+ \l{implicitly shared}. This makes returning a QContiguousCache from a
+ function very fast. If a shared instance is modified, it will be
+ copied (copy-on-write), and that takes \l{linear time}.
+
+ \sa operator=()
+*/
+
+/*! \fn QContiguousCache::~QContiguousCache()
+
+ Destroys the cache.
+*/
+
+/*! \fn void QContiguousCache::detach()
+
+ \internal
+*/
+
+/*! \fn bool QContiguousCache::isDetached() const
+
+ \internal
+*/
+
+/*! \fn void QContiguousCache::setSharable(bool sharable)
+
+ \internal
+*/
+
+/*! \fn QContiguousCache<T> &QContiguousCache::operator=(const QContiguousCache<T> &other)
+
+ Assigns \a other to this cache and returns a reference to this cache.
+*/
+
+/*! \fn bool QContiguousCache::operator==(const QContiguousCache<T> &other) const
+
+ Returns true if \a other is equal to this cache; otherwise returns false.
+
+ Two caches are considered equal if they contain the same values at the same
+ indexes. This function requires the value type to implement the \c operator==().
+
+ \sa operator!=()
+*/
+
+/*! \fn bool QContiguousCache::operator!=(const QContiguousCache<T> &other) const
+
+ Returns true if \a other is not equal to this cache; otherwise
+ returns false.
+
+ Two caches are considered equal if they contain the same values at the same
+ indexes. This function requires the value type to implement the \c operator==().
+
+ \sa operator==()
+*/
+
+/*! \fn int QContiguousCache::capacity() const
+
+ Returns the number of items the cache can store before it is full.
+ When a cache contains a number of items equal to its capacity, adding new
+ items will cause items farthest from the added item to be removed.
+
+ \sa setCapacity(), size()
+*/
+
+/*! \fn int QContiguousCache::count() const
+
+ \overload
+
+ Same as size().
+*/
+
+/*! \fn int QContiguousCache::size() const
+
+ Returns the number of items contained within the cache.
+
+ \sa capacity()
+*/
+
+/*! \fn bool QContiguousCache::isEmpty() const
+
+ Returns true if no items are stored within the cache.
+
+ \sa size(), capacity()
+*/
+
+/*! \fn bool QContiguousCache::isFull() const
+
+ Returns true if the number of items stored within the cache is equal
+ to the capacity of the cache.
+
+ \sa size(), capacity()
+*/
+
+/*! \fn int QContiguousCache::available() const
+
+ Returns the number of items that can be added to the cache before it becomes full.
+
+ \sa size(), capacity(), isFull()
+*/
+
+/*! \fn void QContiguousCache::clear()
+
+ Removes all items from the cache. The capacity is unchanged.
+*/
+
+/*! \fn void QContiguousCache::setCapacity(int size)
+
+ Sets the capacity of the cache to the given \a size. A cache can hold a
+ number of items equal to its capacity. When inserting, appending or prepending
+ items to the cache, if the cache is already full then the item farthest from
+ the added item will be removed.
+
+ If the given \a size is smaller than the current count of items in the cache
+ then only the last \a size items from the cache will remain.
+
+ \sa capacity(), isFull()
+*/
+
+/*! \fn const T &QContiguousCache::at(int i) const
+
+ Returns the item at index position \a i in the cache. \a i must
+ be a valid index position in the cache (i.e, firstIndex() <= \a i <= lastIndex()).
+
+ The indexes in the cache refer to the number of positions the item is from the
+ first item appended into the cache. That is to say a cache with a capacity of
+ 100, that has had 150 items appended will have a valid index range of
+ 50 to 149. This allows inserting and retrieving items into the cache based
+ on a theoretical infinite list
+
+ \sa firstIndex(), lastIndex(), insert(), operator[]()
+*/
+
+/*! \fn T &QContiguousCache::operator[](int i)
+
+ Returns the item at index position \a i as a modifiable reference. If
+ the cache does not contain an item at the given index position \a i
+ then it will first insert an empty item at that position.
+
+ In most cases it is better to use either at() or insert().
+
+ Note that using non-const operators can cause QContiguousCache to do a deep
+ copy.
+
+ \sa insert(), at()
+*/
+
+/*! \fn const T &QContiguousCache::operator[](int i) const
+
+ \overload
+
+ Same as at(\a i).
+*/
+
+/*! \fn void QContiguousCache::append(const T &value)
+
+ Inserts \a value at the end of the cache. If the cache is already full
+ the item at the start of the cache will be removed.
+
+ \sa prepend(), insert(), isFull()
+*/
+
+/*! \fn void QContiguousCache::prepend(const T &value)
+
+ Inserts \a value at the start of the cache. If the cache is already full
+ the item at the end of the cache will be removed.
+
+ \sa append(), insert(), isFull()
+*/
+
+/*! \fn void QContiguousCache::insert(int i, const T &value)
+
+ Inserts the \a value at the index position \a i. If the cache already contains
+ an item at \a i then that value is replaced. If \a i is either one more than
+ lastIndex() or one less than firstIndex() it is the equivalent to an append()
+ or a prepend().
+
+ If the given index \a i is not within the current range of the cache nor adjacent
+ to the bounds of the cache's index range, the cache is first cleared before
+ inserting the item. At this point the cache will have a size of 1. It is
+ worthwhile taking effort to insert items in an order that starts adjacent
+ to the current index range for the cache.
+
+ The range of valid indexes for the QContiguousCache class are from
+ 0 to INT_MAX. Inserting outside of this range has undefined behavior.
+
+
+ \sa prepend(), append(), isFull(), firstIndex(), lastIndex()
+*/
+
+/*! \fn bool QContiguousCache::containsIndex(int i) const
+
+ Returns true if the cache's index range includes the given index \a i.
+
+ \sa firstIndex(), lastIndex()
+*/
+
+/*! \fn int QContiguousCache::firstIndex() const
+
+ Returns the first valid index in the cache. The index will be invalid if the
+ cache is empty.
+
+ \sa capacity(), size(), lastIndex()
+*/
+
+/*! \fn int QContiguousCache::lastIndex() const
+
+ Returns the last valid index in the cache. The index will be invalid if the cache is empty.
+
+ \sa capacity(), size(), firstIndex()
+*/
+
+
+/*! \fn T &QContiguousCache::first()
+
+ Returns a reference to the first item in the cache. This function
+ assumes that the cache isn't empty.
+
+ \sa last(), isEmpty()
+*/
+
+/*! \fn T &QContiguousCache::last()
+
+ Returns a reference to the last item in the cache. This function
+ assumes that the cache isn't empty.
+
+ \sa first(), isEmpty()
+*/
+
+/*! \fn const T& QContiguousCache::first() const
+
+ \overload
+*/
+
+/*! \fn const T& QContiguousCache::last() const
+
+ \overload
+*/
+
+/*! \fn void QContiguousCache::removeFirst()
+
+ Removes the first item from the cache. This function assumes that
+ the cache isn't empty.
+
+ \sa removeLast()
+*/
+
+/*! \fn void QContiguousCache::removeLast()
+
+ Removes the last item from the cache. This function assumes that
+ the cache isn't empty.
+
+ \sa removeFirst()
+*/
+
+/*! \fn T QContiguousCache::takeFirst()
+
+ Removes the first item in the cache and returns it. This function
+ assumes that the cache isn't empty.
+
+ If you don't use the return value, removeFirst() is more efficient.
+
+ \sa takeLast(), removeFirst()
+*/
+
+/*! \fn T QContiguousCache::takeLast()
+
+ Removes the last item in the cache and returns it. This function
+ assumes that the cache isn't empty.
+
+ If you don't use the return value, removeLast() is more efficient.
+
+ \sa takeFirst(), removeLast()
+*/
+
+/*! \fn void QContiguousCache::normalizeIndexes()
+
+ Moves the first index and last index of the cache
+ such that they point to valid indexes. The function does not modify
+ the contents of the cache or the ordering of elements within the cache.
+
+ It is provided so that index overflows can be corrected when using the
+ cache as a circular buffer.
+
+ \code
+ QContiguousCache<int> cache(10);
+ cache.insert(INT_MAX, 1); // cache contains one value and has valid indexes, INT_MAX to INT_MAX
+ cache.append(2); // cache contains two values but does not have valid indexes.
+ cache.normalizeIndexes(); // cache has two values, 1 and 2. New first index will be in the range of 0 to capacity().
+ \endcode
+
+ \sa areIndexesValid(), append(), prepend()
+*/
+
+/*! \fn bool QContiguousCache::areIndexesValid() const
+
+ Returns whether the indexes for items stored in the cache are valid.
+ Indexes can become invalid if items are appended after the index position
+ INT_MAX or prepended before the index position 0. This is only expected
+ to occur in very long lived circular buffer style usage of the
+ contiguous cache. Indexes can be made valid again by calling
+ normalizeIndexs().
+
+ \sa normalizeIndexes(), append(), prepend()
+*/
+
+/*! \fn void QContiguousCache::dump() const
+
+ \internal
+
+ Sends information about the cache's internal structure to qDebug()
+*/
+
+QT_END_NAMESPACE
diff --git a/src/corelib/tools/qcontiguouscache.h b/src/corelib/tools/qcontiguouscache.h
new file mode 100644
index 0000000..5cd1582
--- /dev/null
+++ b/src/corelib/tools/qcontiguouscache.h
@@ -0,0 +1,424 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain
+** additional rights. These rights are described in the Nokia Qt LGPL
+** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QCONTIGUOUSCACHE_H
+#define QCONTIGUOUSCACHE_H
+
+#include <QtCore/qatomic.h>
+#include <limits.h>
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+QT_MODULE(Core)
+
+struct Q_CORE_EXPORT QContiguousCacheData
+{
+ QBasicAtomicInt ref;
+ int alloc;
+ int count;
+ int start;
+ int offset;
+ uint sharable : 1;
+
+ void dump() const;
+};
+
+template <typename T>
+struct QContiguousCacheTypedData
+{
+ QBasicAtomicInt ref;
+ int alloc;
+ int count;
+ int start;
+ int offset;
+ uint sharable : 1;
+
+ T array[1];
+};
+
+template<typename T>
+class QContiguousCache {
+ typedef QContiguousCacheTypedData<T> Data;
+ union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; };
+public:
+ explicit QContiguousCache(int capacity = 0);
+ QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
+
+ inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(d); }
+
+ inline void detach() { if (d->ref != 1) detach_helper(); }
+ inline bool isDetached() const { return d->ref == 1; }
+ inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
+
+ QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
+ bool operator==(const QContiguousCache<T> &other) const;
+ inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); }
+
+ inline int capacity() const {return d->alloc; }
+ inline int count() const { return d->count; }
+ inline int size() const { return d->count; }
+
+ inline bool isEmpty() const { return d->count == 0; }
+ inline bool isFull() const { return d->count == d->alloc; }
+ inline int available() const { return d->alloc - d->count; }
+
+ void clear();
+ void setCapacity(int size);
+
+ const T &at(int pos) const;
+ T &operator[](int i);
+ const T &operator[](int i) const;
+
+ void append(const T &value);
+ void prepend(const T &value);
+ void insert(int pos, const T &value);
+
+ inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; }
+ inline int firstIndex() const { return d->offset; }
+ inline int lastIndex() const { return d->offset + d->count - 1; }
+
+ inline const T &first() const { Q_ASSERT(!isEmpty()); return d->array[d->start]; }
+ inline const T &last() const { Q_ASSERT(!isEmpty()); return d->array[(d->start + d->count -1) % d->alloc]; }
+ inline T &first() { Q_ASSERT(!isEmpty()); detach(); return d->array[d->start]; }
+ inline T &last() { Q_ASSERT(!isEmpty()); detach(); return d->array[(d->start + d->count -1) % d->alloc]; }
+
+ void removeFirst();
+ T takeFirst();
+ void removeLast();
+ T takeLast();
+
+ inline bool areIndexesValid() const
+ { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }
+
+ inline void normalizeIndexes() { d->offset = d->start; }
+ // debug
+ void dump() const { p->dump(); }
+private:
+ void detach_helper();
+
+ QContiguousCacheData *malloc(int aalloc);
+ void free(Data *x);
+ int sizeOfTypedData() {
+ // this is more or less the same as sizeof(Data), except that it doesn't
+ // count the padding at the end
+ return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
+ }
+};
+
+template <typename T>
+void QContiguousCache<T>::detach_helper()
+{
+ union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+
+ x.p = malloc(d->alloc);
+ x.d->ref = 1;
+ x.d->count = d->count;
+ x.d->start = d->start;
+ x.d->offset = d->offset;
+ x.d->alloc = d->alloc;
+ x.d->sharable = true;
+
+ T *dest = x.d->array + x.d->start;
+ T *src = d->array + d->start;
+ int count = x.d->count;
+ while (count--) {
+ if (QTypeInfo<T>::isComplex) {
+ new (dest) T(*src);
+ } else {
+ *dest = *src;
+ }
+ dest++;
+ if (dest == x.d->array + x.d->alloc)
+ dest = x.d->array;
+ src++;
+ if (src == d->array + d->alloc)
+ src = d->array;
+ }
+
+ if (!d->ref.deref())
+ free(d);
+ d = x.d;
+}
+
+template <typename T>
+void QContiguousCache<T>::setCapacity(int asize)
+{
+ if (asize == d->alloc)
+ return;
+ detach();
+ union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+ x.p = malloc(asize);
+ x.d->alloc = asize;
+ x.d->count = qMin(d->count, asize);
+ x.d->offset = d->offset + d->count - x.d->count;
+ x.d->start = x.d->offset % x.d->alloc;
+ T *dest = x.d->array + (x.d->start + x.d->count-1) % x.d->alloc;
+ T *src = d->array + (d->start + d->count-1) % d->alloc;
+ int count = x.d->count;
+ while (count--) {
+ if (QTypeInfo<T>::isComplex) {
+ new (dest) T(*src);
+ } else {
+ *dest = *src;
+ }
+ if (dest == x.d->array)
+ dest = x.d->array + x.d->alloc;
+ dest--;
+ if (src == d->array)
+ src = d->array + d->alloc;
+ src--;
+ }
+ /* free old */
+ free(d);
+ d = x.d;
+}
+
+template <typename T>
+void QContiguousCache<T>::clear()
+{
+ if (d->ref == 1) {
+ if (QTypeInfo<T>::isComplex) {
+ int count = d->count;
+ T * i = d->array + d->start;
+ T * e = d->array + d->alloc;
+ while (count--) {
+ i->~T();
+ i++;
+ if (i == e)
+ i = d->array;
+ }
+ }
+ d->count = d->start = d->offset = 0;
+ } else {
+ union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+ x.p = malloc(d->alloc);
+ x.d->ref = 1;
+ x.d->alloc = d->alloc;
+ x.d->count = x.d->start = x.d->offset = 0;
+ x.d->sharable = true;
+ if (!d->ref.deref()) free(d);
+ d = x.d;
+ }
+}
+
+template <typename T>
+inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)
+{
+ return static_cast<QContiguousCacheData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
+}
+
+template <typename T>
+QContiguousCache<T>::QContiguousCache(int capacity)
+{
+ p = malloc(capacity);
+ d->ref = 1;
+ d->alloc = capacity;
+ d->count = d->start = d->offset = 0;
+ d->sharable = true;
+}
+
+template <typename T>
+QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
+{
+ other.d->ref.ref();
+ if (!d->ref.deref())
+ free(d);
+ d = other.d;
+ if (!d->sharable)
+ detach_helper();
+ return *this;
+}
+
+template <typename T>
+bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
+{
+ if (other.d == d)
+ return true;
+ if (other.d->start != d->start
+ || other.d->count != d->count
+ || other.d->offset != d->offset
+ || other.d->alloc != d->alloc)
+ return false;
+ for (int i = firstIndex(); i <= lastIndex(); ++i)
+ if (!(at(i) == other.at(i)))
+ return false;
+ return true;
+}
+
+template <typename T>
+void QContiguousCache<T>::free(Data *x)
+{
+ if (QTypeInfo<T>::isComplex) {
+ int count = d->count;
+ T * i = d->array + d->start;
+ T * e = d->array + d->alloc;
+ while (count--) {
+ i->~T();
+ i++;
+ if (i == e)
+ i = d->array;
+ }
+ }
+ qFree(x);
+}
+template <typename T>
+void QContiguousCache<T>::append(const T &value)
+{
+ detach();
+ if (QTypeInfo<T>::isComplex) {
+ if (d->count == d->alloc)
+ (d->array + (d->start+d->count) % d->alloc)->~T();
+ new (d->array + (d->start+d->count) % d->alloc) T(value);
+ } else {
+ d->array[(d->start+d->count) % d->alloc] = value;
+ }
+
+ if (d->count == d->alloc) {
+ d->start++;
+ d->start %= d->alloc;
+ d->offset++;
+ } else {
+ d->count++;
+ }
+}
+
+template<typename T>
+void QContiguousCache<T>::prepend(const T &value)
+{
+ detach();
+ if (d->start)
+ d->start--;
+ else
+ d->start = d->alloc-1;
+ d->offset--;
+
+ if (d->count != d->alloc)
+ d->count++;
+ else
+ if (d->count == d->alloc)
+ (d->array + d->start)->~T();
+
+ if (QTypeInfo<T>::isComplex)
+ new (d->array + d->start) T(value);
+ else
+ d->array[d->start] = value;
+}
+
+template<typename T>
+void QContiguousCache<T>::insert(int pos, const T &value)
+{
+ Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");
+ detach();
+ if (containsIndex(pos)) {
+ if(QTypeInfo<T>::isComplex)
+ new (d->array + pos % d->alloc) T(value);
+ else
+ d->array[pos % d->alloc] = value;
+ } else if (pos == d->offset-1)
+ prepend(value);
+ else if (pos == d->offset+d->count)
+ append(value);
+ else {
+ // we don't leave gaps.
+ clear();
+ d->offset = pos;
+ d->start = pos % d->alloc;
+ d->count = 1;
+ if (QTypeInfo<T>::isComplex)
+ new (d->array + d->start) T(value);
+ else
+ d->array[d->start] = value;
+ }
+}
+
+template <typename T>
+inline const T &QContiguousCache<T>::at(int pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
+template <typename T>
+inline const T &QContiguousCache<T>::operator[](int pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
+
+template <typename T>
+inline T &QContiguousCache<T>::operator[](int pos)
+{
+ detach();
+ if (!containsIndex(pos))
+ insert(pos, T());
+ return d->array[pos % d->alloc];
+}
+
+template <typename T>
+inline void QContiguousCache<T>::removeFirst()
+{
+ Q_ASSERT(d->count > 0);
+ detach();
+ d->count--;
+ if (QTypeInfo<T>::isComplex)
+ (d->array + d->start)->~T();
+ d->start = (d->start + 1) % d->alloc;
+ d->offset++;
+}
+
+template <typename T>
+inline void QContiguousCache<T>::removeLast()
+{
+ Q_ASSERT(d->count > 0);
+ detach();
+ d->count--;
+ if (QTypeInfo<T>::isComplex)
+ (d->array + (d->start + d->count) % d->alloc)->~T();
+}
+
+template <typename T>
+inline T QContiguousCache<T>::takeFirst()
+{ T t = first(); removeFirst(); return t; }
+
+template <typename T>
+inline T QContiguousCache<T>::takeLast()
+{ T t = last(); removeLast(); return t; }
+
+QT_END_NAMESPACE
+
+QT_END_HEADER
+
+#endif
diff --git a/src/corelib/tools/qtimeline.cpp b/src/corelib/tools/qtimeline.cpp
index 2979a09..3a03558 100644
--- a/src/corelib/tools/qtimeline.cpp
+++ b/src/corelib/tools/qtimeline.cpp
@@ -225,7 +225,9 @@ void QTimeLinePrivate::setCurrentTime(int msecs)
valueForTime() and emitting valueChanged(). By default, valueForTime()
applies an interpolation algorithm to generate these value. You can choose
from a set of predefined timeline algorithms by calling
- setCurveShape(). By default, QTimeLine uses the EaseInOut curve shape,
+ setCurveShape().
+
+ Note that by default, QTimeLine uses the EaseInOut curve shape,
which provides a value that grows slowly, then grows steadily, and
finally grows slowly. For a custom timeline, you can reimplement
valueForTime(), in which case QTimeLine's curveShape property is ignored.
diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h
index 1f047b8..7bdcba0 100644
--- a/src/corelib/tools/qvector.h
+++ b/src/corelib/tools/qvector.h
@@ -82,19 +82,9 @@ struct Q_CORE_EXPORT QVectorData
};
template <typename T>
-struct QVectorTypedData
-{
- QBasicAtomicInt ref;
- int alloc;
- int size;
-#if defined(QT_ARCH_SPARC) && defined(Q_CC_GNU) && defined(__LP64__) && defined(QT_BOOTSTRAPPED)
- // workaround for bug in gcc 3.4.2
- uint sharable;
- uint capacity;
-#else
- uint sharable : 1;
- uint capacity : 1;
-#endif
+struct QVectorTypedData : private QVectorData
+{ // private inheritance as we must not access QVectorData member thought QVectorTypedData
+ // as this would break strict aliasing rules. (in the case of shared_null)
T array[1];
};
@@ -104,14 +94,14 @@ template <typename T>
class QVector
{
typedef QVectorTypedData<T> Data;
- union { QVectorData *p; QVectorTypedData<T> *d; };
+ union { QVectorData *d; Data *p; };
public:
- inline QVector() : p(&QVectorData::shared_null) { d->ref.ref(); }
+ inline QVector() : d(&QVectorData::shared_null) { d->ref.ref(); }
explicit QVector(int size);
QVector(int size, const T &t);
inline QVector(const QVector<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
- inline ~QVector() { if (!d) return; if (!d->ref.deref()) free(d); }
+ inline ~QVector() { if (!d) return; if (!d->ref.deref()) free(p); }
QVector<T> &operator=(const QVector<T> &v);
bool operator==(const QVector<T> &v) const;
inline bool operator!=(const QVector<T> &v) const { return !(*this == v); }
@@ -130,9 +120,9 @@ public:
inline bool isDetached() const { return d->ref == 1; }
inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
- inline T *data() { detach(); return d->array; }
- inline const T *data() const { return d->array; }
- inline const T *constData() const { return d->array; }
+ inline T *data() { detach(); return p->array; }
+ inline const T *data() const { return p->array; }
+ inline const T *constData() const { return p->array; }
void clear();
const T &at(int i) const;
@@ -225,12 +215,12 @@ public:
typedef T* iterator;
typedef const T* const_iterator;
#endif
- inline iterator begin() { detach(); return d->array; }
- inline const_iterator begin() const { return d->array; }
- inline const_iterator constBegin() const { return d->array; }
- inline iterator end() { detach(); return d->array + d->size; }
- inline const_iterator end() const { return d->array + d->size; }
- inline const_iterator constEnd() const { return d->array + d->size; }
+ inline iterator begin() { detach(); return p->array; }
+ inline const_iterator begin() const { return p->array; }
+ inline const_iterator constBegin() const { return p->array; }
+ inline iterator end() { detach(); return p->array + d->size; }
+ inline const_iterator end() const { return p->array + d->size; }
+ inline const_iterator constEnd() const { return p->array + d->size; }
iterator insert(iterator before, int n, const T &x);
inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
iterator erase(iterator begin, iterator end);
@@ -327,11 +317,11 @@ inline void QVector<T>::clear()
template <typename T>
inline const T &QVector<T>::at(int i) const
{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range");
- return d->array[i]; }
+ return p->array[i]; }
template <typename T>
inline const T &QVector<T>::operator[](int i) const
{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
- return d->array[i]; }
+ return p->array[i]; }
template <typename T>
inline T &QVector<T>::operator[](int i)
{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
@@ -369,7 +359,7 @@ QVector<T> &QVector<T>::operator=(const QVector<T> &v)
{
v.d->ref.ref();
if (!d->ref.deref())
- free(d);
+ free(p);
d = v.d;
if (!d->sharable)
detach_helper();
@@ -385,31 +375,31 @@ inline QVectorData *QVector<T>::malloc(int aalloc)
template <typename T>
QVector<T>::QVector(int asize)
{
- p = malloc(asize);
+ d = malloc(asize);
d->ref = 1;
d->alloc = d->size = asize;
d->sharable = true;
d->capacity = false;
if (QTypeInfo<T>::isComplex) {
- T* b = d->array;
- T* i = d->array + d->size;
+ T* b = p->array;
+ T* i = p->array + d->size;
while (i != b)
new (--i) T;
} else {
- qMemSet(d->array, 0, asize * sizeof(T));
+ qMemSet(p->array, 0, asize * sizeof(T));
}
}
template <typename T>
QVector<T>::QVector(int asize, const T &t)
{
- p = malloc(asize);
+ d = malloc(asize);
d->ref = 1;
d->alloc = d->size = asize;
d->sharable = true;
d->capacity = false;
- T* i = d->array + d->size;
- while (i != d->array)
+ T* i = p->array + d->size;
+ while (i != p->array)
new (--i) T(t);
}
@@ -418,7 +408,7 @@ void QVector<T>::free(Data *x)
{
if (QTypeInfo<T>::isComplex) {
T* b = x->array;
- T* i = b + x->size;
+ T* i = b + reinterpret_cast<QVectorData *>(x)->size;
while (i-- != b)
i->~T();
}
@@ -429,13 +419,13 @@ template <typename T>
void QVector<T>::realloc(int asize, int aalloc)
{
T *j, *i, *b;
- union { QVectorData *p; Data *d; } x;
+ union { QVectorData *d; Data *p; } x;
x.d = d;
if (QTypeInfo<T>::isComplex && aalloc == d->alloc && d->ref == 1) {
// pure resize
- i = d->array + d->size;
- j = d->array + asize;
+ i = p->array + d->size;
+ j = p->array + asize;
if (i > j) {
while (i-- != j)
i->~T();
@@ -450,22 +440,22 @@ void QVector<T>::realloc(int asize, int aalloc)
if (aalloc != d->alloc || d->ref != 1) {
// (re)allocate memory
if (QTypeInfo<T>::isStatic) {
- x.p = malloc(aalloc);
+ x.d = malloc(aalloc);
} else if (d->ref != 1) {
- x.p = QVectorData::malloc(sizeOfTypedData(), aalloc, sizeof(T), p);
+ x.d = QVectorData::malloc(sizeOfTypedData(), aalloc, sizeof(T), d);
} else {
if (QTypeInfo<T>::isComplex) {
// call the destructor on all objects that need to be
// destroyed when shrinking
if (asize < d->size) {
- j = d->array + asize;
- i = d->array + d->size;
+ j = p->array + asize;
+ i = p->array + d->size;
while (i-- != j)
i->~T();
- i = d->array + asize;
+ i = p->array + asize;
}
}
- x.p = p = static_cast<QVectorData *>(qRealloc(p, sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
+ x.d = d = static_cast<QVectorData *>(qRealloc(d, sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
}
x.d->ref = 1;
x.d->sharable = true;
@@ -474,31 +464,31 @@ void QVector<T>::realloc(int asize, int aalloc)
}
if (QTypeInfo<T>::isComplex) {
if (asize < d->size) {
- j = d->array + asize;
- i = x.d->array + asize;
+ j = p->array + asize;
+ i = x.p->array + asize;
} else {
// construct all new objects when growing
- i = x.d->array + asize;
- j = x.d->array + d->size;
+ i = x.p->array + asize;
+ j = x.p->array + d->size;
while (i != j)
new (--i) T;
- j = d->array + d->size;
+ j = p->array + d->size;
}
if (i != j) {
// copy objects from the old array into the new array
- b = x.d->array;
+ b = x.p->array;
while (i != b)
new (--i) T(*--j);
}
} else if (asize > d->size) {
// initialize newly allocated memory to 0
- qMemSet(x.d->array + d->size, 0, (asize - d->size) * sizeof(T));
+ qMemSet(x.p->array + d->size, 0, (asize - d->size) * sizeof(T));
}
x.d->size = asize;
x.d->alloc = aalloc;
if (d != x.d) {
if (!d->ref.deref())
- free(d);
+ free(p);
d = x.d;
}
}
@@ -506,15 +496,15 @@ void QVector<T>::realloc(int asize, int aalloc)
template<typename T>
Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const
{
- if (i < 0 || i >= p->size) {
+ if (i < 0 || i >= d->size) {
return T();
}
- return d->array[i];
+ return p->array[i];
}
template<typename T>
Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const
{
- return ((i < 0 || i >= p->size) ? defaultValue : d->array[i]);
+ return ((i < 0 || i >= d->size) ? defaultValue : p->array[i]);
}
template <typename T>
@@ -525,14 +515,14 @@ void QVector<T>::append(const T &t)
realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + 1, sizeof(T),
QTypeInfo<T>::isStatic));
if (QTypeInfo<T>::isComplex)
- new (d->array + d->size) T(copy);
+ new (p->array + d->size) T(copy);
else
- d->array[d->size] = copy;
+ p->array[d->size] = copy;
} else {
if (QTypeInfo<T>::isComplex)
- new (d->array + d->size) T(t);
+ new (p->array + d->size) T(t);
else
- d->array[d->size] = t;
+ p->array[d->size] = t;
}
++d->size;
}
@@ -540,27 +530,27 @@ void QVector<T>::append(const T &t)
template <typename T>
Q_TYPENAME QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t)
{
- int offset = before - d->array;
+ int offset = before - p->array;
if (n != 0) {
const T copy(t);
if (d->ref != 1 || d->size + n > d->alloc)
realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + n, sizeof(T),
QTypeInfo<T>::isStatic));
if (QTypeInfo<T>::isStatic) {
- T *b = d->array + d->size;
- T *i = d->array + d->size + n;
+ T *b = p->array + d->size;
+ T *i = p->array + d->size + n;
while (i != b)
new (--i) T;
- i = d->array + d->size;
+ i = p->array + d->size;
T *j = i + n;
- b = d->array + offset;
+ b = p->array + offset;
while (i != b)
*--j = *--i;
i = b+n;
while (i != b)
*--i = copy;
} else {
- T *b = d->array + offset;
+ T *b = p->array + offset;
T *i = b + n;
memmove(i, b, (d->size - offset) * sizeof(T));
while (i != b)
@@ -568,29 +558,29 @@ Q_TYPENAME QVector<T>::iterator QVector<T>::insert(iterator before, size_type n,
}
d->size += n;
}
- return d->array + offset;
+ return p->array + offset;
}
template <typename T>
Q_TYPENAME QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend)
{
- int f = abegin - d->array;
- int l = aend - d->array;
+ int f = abegin - p->array;
+ int l = aend - p->array;
int n = l - f;
detach();
if (QTypeInfo<T>::isComplex) {
- qCopy(d->array+l, d->array+d->size, d->array+f);
- T *i = d->array+d->size;
- T* b = d->array+d->size-n;
+ qCopy(p->array+l, p->array+d->size, p->array+f);
+ T *i = p->array+d->size;
+ T* b = p->array+d->size-n;
while (i != b) {
--i;
i->~T();
}
} else {
- memmove(d->array + f, d->array + l, (d->size-l)*sizeof(T));
+ memmove(p->array + f, p->array + l, (d->size-l)*sizeof(T));
}
d->size -= n;
- return d->array + f;
+ return p->array + f;
}
template <typename T>
@@ -600,9 +590,9 @@ bool QVector<T>::operator==(const QVector<T> &v) const
return false;
if (d == v.d)
return true;
- T* b = d->array;
+ T* b = p->array;
T* i = b + d->size;
- T* j = v.d->array + d->size;
+ T* j = v.p->array + d->size;
while (i != b)
if (!(*--i == *--j))
return false;
@@ -615,8 +605,8 @@ QVector<T> &QVector<T>::fill(const T &from, int asize)
const T copy(from);
resize(asize < 0 ? d->size : asize);
if (d->size) {
- T *i = d->array + d->size;
- T *b = d->array;
+ T *i = p->array + d->size;
+ T *b = p->array;
while (i != b)
*--i = copy;
}
@@ -629,9 +619,9 @@ QVector<T> &QVector<T>::operator+=(const QVector &l)
int newSize = d->size + l.d->size;
realloc(d->size, newSize);
- T *w = d->array + newSize;
- T *i = l.d->array + l.d->size;
- T *b = l.d->array;
+ T *w = p->array + newSize;
+ T *i = l.p->array + l.d->size;
+ T *b = l.p->array;
while (i != b) {
if (QTypeInfo<T>::isComplex)
new (--w) T(*--i);
@@ -648,11 +638,11 @@ int QVector<T>::indexOf(const T &t, int from) const
if (from < 0)
from = qMax(from + d->size, 0);
if (from < d->size) {
- T* n = d->array + from - 1;
- T* e = d->array + d->size;
+ T* n = p->array + from - 1;
+ T* e = p->array + d->size;
while (++n != e)
if (*n == t)
- return n - d->array;
+ return n - p->array;
}
return -1;
}
@@ -665,8 +655,8 @@ int QVector<T>::lastIndexOf(const T &t, int from) const
else if (from >= d->size)
from = d->size-1;
if (from >= 0) {
- T* b = d->array;
- T* n = d->array + from + 1;
+ T* b = p->array;
+ T* n = p->array + from + 1;
while (n != b) {
if (*--n == t)
return n - b;
@@ -678,8 +668,8 @@ int QVector<T>::lastIndexOf(const T &t, int from) const
template <typename T>
bool QVector<T>::contains(const T &t) const
{
- T* b = d->array;
- T* i = d->array + d->size;
+ T* b = p->array;
+ T* i = p->array + d->size;
while (i != b)
if (*--i == t)
return true;
@@ -690,8 +680,8 @@ template <typename T>
int QVector<T>::count(const T &t) const
{
int c = 0;
- T* b = d->array;
- T* i = d->array + d->size;
+ T* b = p->array;
+ T* i = p->array + d->size;
while (i != b)
if (*--i == t)
++c;
diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri
index e5bf7e4..aaf3f21 100644
--- a/src/corelib/tools/tools.pri
+++ b/src/corelib/tools/tools.pri
@@ -19,6 +19,7 @@ HEADERS += \
tools/qlocale_p.h \
tools/qlocale_data_p.h \
tools/qmap.h \
+ tools/qcontiguouscache.h \
tools/qpodlist_p.h \
tools/qpoint.h \
tools/qqueue.h \
@@ -53,6 +54,7 @@ SOURCES += \
tools/qlocale.cpp \
tools/qpoint.cpp \
tools/qmap.cpp \
+ tools/qcontiguouscache.cpp \
tools/qrect.cpp \
tools/qregexp.cpp \
tools/qshareddata.cpp \
generated by cgit v0.12 at 2025-03-12 00:46:44 (GMT)