diff options
-rw-r--r-- | src/corelib/tools/qfreelist.cpp | 62 | ||||
-rw-r--r-- | src/corelib/tools/qfreelist_p.h | 294 | ||||
-rw-r--r-- | src/corelib/tools/tools.pri | 2 | ||||
-rw-r--r-- | tests/auto/corelib.pro | 1 | ||||
-rw-r--r-- | tests/auto/qfreelist/qfreelist.pro | 6 | ||||
-rw-r--r-- | tests/auto/qfreelist/tst_qfreelist.cpp | 179 |
6 files changed, 544 insertions, 0 deletions
diff --git a/src/corelib/tools/qfreelist.cpp b/src/corelib/tools/qfreelist.cpp new file mode 100644 index 0000000000..63e37ec249 --- /dev/null +++ b/src/corelib/tools/qfreelist.cpp @@ -0,0 +1,62 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** 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.1, 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. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qfreelist_p.h" + +// default sizes and offsets (no need to define these when customizing) +enum { + Offset0 = 0x00000000, + Offset1 = 0x00008000, + Offset2 = 0x00080000, + Offset3 = 0x00800000, + + Size0 = Offset1 - Offset0, + Size1 = Offset2 - Offset1, + Size2 = Offset3 - Offset2, + Size3 = QFreeListDefaultConstants::MaxIndex - Offset3 +}; + +const int QFreeListDefaultConstants::Sizes[QFreeListDefaultConstants::BlockCount] = { + Size0, + Size1, + Size2, + Size3 +}; diff --git a/src/corelib/tools/qfreelist_p.h b/src/corelib/tools/qfreelist_p.h new file mode 100644 index 0000000000..74ba3b587e --- /dev/null +++ b/src/corelib/tools/qfreelist_p.h @@ -0,0 +1,294 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** 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.1, 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. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QFREELIST_P_H +#define QFREELIST_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/qatomic.h> + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Core) + +/*! \internal + + Element in a QFreeList. ConstReferenceType and ReferenceType are used as + the return values for QFreeList::at() and QFreeList::operator[](). Contains + the real data storage (_t) and the id of the next free element (next). + + Note: the t() functions should be used to access the data, not _t. +*/ +template <typename T> +struct QFreeListElement +{ + typedef const T &ConstReferenceType; + typedef T &ReferenceType; + + T _t; + int next; + + inline ConstReferenceType t() const { return _t; } + inline ReferenceType t() { return _t; } +}; + +/*! \internal + + Element in a QFreeList without a paylout. ConstReferenceType and + ReferenceType are void, the t() functions return void and are empty. +*/ +template <> +struct QFreeListElement<void> +{ + typedef void ConstReferenceType; + typedef void ReferenceType; + + int next; + + inline void t() const { } + inline void t() { } +}; + +/*! \internal + + Defines default constants used by QFreeList: + + - The initial value returned by QFreeList::next() is zero. + + - QFreeList allows for up to 16777216 elements in QFreeList and uses the top + 8 bits to store a serial counter for ABA protection. + + - QFreeList will make a maximum of 4 allocations (blocks), with each + successive block larger than the previous. + + - Sizes static int[] array to define the size of each block. + + It is possible to define your own constants struct/class and give this to + QFreeList to customize/tune the behavior. +*/ +struct Q_AUTOTEST_EXPORT QFreeListDefaultConstants +{ + // used by QFreeList, make sure to define all of when customizing + enum { + InitialNextValue = 0, + IndexMask = 0x00ffffff, + SerialMask = ~IndexMask & ~0x80000000, + SerialCounter = IndexMask + 1, + MaxIndex = IndexMask, + BlockCount = 4, + }; + + static const int Sizes[BlockCount]; +}; + +/*! \internal + + This is a generic implementation of a lock-free free list. Use next() to + get the next free entry in the list, and release(id) when done with the id. + + This version is templated and allows having a payload of type T which can + be accessed using the id returned by next(). The payload is allocated and + deallocated automatically by the free list, but *NOT* when calling + next()/release(). Initialization should be done by code needing it after + next() returns. Likewise, cleanup() should happen before calling release(). + It is possible to have use 'void' as the payload type, in which case the + free list only contains indexes to the next free entry. + + The ConstantsType type defaults to QFreeListDefaultConstants above. You can + define your custom ConstantsType, see above for details on what needs to be + available. +*/ +template <typename T, typename ConstantsType = QFreeListDefaultConstants> +class QFreeList +{ + typedef T ValueType; + typedef QFreeListElement<T> ElementType; + typedef typename ElementType::ConstReferenceType ConstReferenceType; + typedef typename ElementType::ReferenceType ReferenceType; + + // return which block the index \a x falls in, and modify \a x to be the index into that block + static inline int blockfor(int &x) + { + for (int i = 0; i < ConstantsType::BlockCount; ++i) { + int size = ConstantsType::Sizes[i]; + if (x < size) + return i; + x -= size; + } + Q_ASSERT(false); + return -1; + } + + // allocate a block of the given \a size, initialized starting with the given \a offset + static inline ElementType *allocate(int offset, int size) + { + // qDebug("QFreeList: allocating %d elements (%ld bytes) with offset %d", size, size * sizeof(ElementType), offset); + ElementType *v = new ElementType[size]; + for (int i = 0; i < size; ++i) + v[i].next = offset + i + 1; + return v; + } + + // take the current serial number from \a o, increment it, and store it in \a n + static inline int incrementserial(int o, int n) + { + return (n & ConstantsType::IndexMask) | ((o + ConstantsType::SerialCounter) & ConstantsType::SerialMask); + } + + // the blocks + QAtomicPointer<ElementType> _v[ConstantsType::BlockCount]; + // the next free id + QAtomicInt _next; + + // QFreeList is not copyable + Q_DISABLE_COPY(QFreeList) + +public: + inline QFreeList(); + inline ~QFreeList(); + + // returns the payload for the given index \a x + inline ConstReferenceType at(int x) const; + inline ReferenceType operator[](int x); + + /* + Return the next free id. Use this id to access the payload (see above). + Call release(id) when done using the id. + */ + inline int next(); + inline void release(int id); +}; + +template <typename T, typename ConstantsType> +inline QFreeList<T, ConstantsType>::QFreeList() + : _next(ConstantsType::InitialNextValue) +{ } + +template <typename T, typename ConstantsType> +inline QFreeList<T, ConstantsType>::~QFreeList() +{ + for (int i = 0; i < ConstantsType::BlockCount; ++i) + delete [] static_cast<ElementType *>(_v[i]); +} + +template <typename T, typename ConstantsType> +inline typename QFreeList<T, ConstantsType>::ConstReferenceType QFreeList<T, ConstantsType>::at(int x) const +{ + const int block = blockfor(x); + return _v[block][x].t(); +} + +template <typename T, typename ConstantsType> +inline typename QFreeList<T, ConstantsType>::ReferenceType QFreeList<T, ConstantsType>::operator[](int x) +{ + const int block = blockfor(x); + return _v[block][x].t(); +} + +template <typename T, typename ConstantsType> +inline int QFreeList<T, ConstantsType>::next() +{ + int id, newid, at; + ElementType *v; + do { + id = _next; // .loadAqcuire(); + + at = id & ConstantsType::IndexMask; + const int block = blockfor(at); + v = _v[block]; + + if (!v) { + v = allocate((id & ConstantsType::IndexMask) - at, ConstantsType::Sizes[block]); + if (!_v[block].testAndSetRelease(0, v)) { + // race with another thread lost + delete [] v; + v = _v[block]; + Q_ASSERT(v != 0); + } + } + + newid = v[at].next | (id & ~ConstantsType::IndexMask); + } while (!_next.testAndSetRelease(id, newid)); + // qDebug("QFreeList::next(): returning %d (_next now %d, serial %d)", + // id & ConstantsType::IndexMask, + // newid & ConstantsType::IndexMask, + // (newid & ~ConstantsType::IndexMask) >> 24); + return id & ConstantsType::IndexMask; +} + +template <typename T, typename ConstantsType> +inline void QFreeList<T, ConstantsType>::release(int id) +{ + int at = id & ConstantsType::IndexMask; + const int block = blockfor(at); + ElementType *v = _v[block]; + + int x, newid; + do { + x = _next; // .loadAcquire(); + v[at].next = x & ConstantsType::IndexMask; + + newid = incrementserial(x, id); + } while (!_next.testAndSetRelease(x, newid)); + // qDebug("QFreeList::release(%d): _next now %d (was %d), serial %d", + // id & ConstantsType::IndexMask, + // newid & ConstantsType::IndexMask, + // x & ConstantsType::IndexMask, + // (newid & ~ConstantsType::IndexMask) >> 24); +} + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QFREELIST_P_H diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri index f5b38eb1c0..13b597d513 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -13,6 +13,7 @@ HEADERS += \ tools/qdatetime.h \ tools/qdatetime_p.h \ tools/qeasingcurve.h \ + tools/qfreelist_p.h \ tools/qhash.h \ tools/qline.h \ tools/qlinkedlist.h \ @@ -61,6 +62,7 @@ SOURCES += \ tools/qdatetime.cpp \ tools/qeasingcurve.cpp \ tools/qelapsedtimer.cpp \ + tools/qfreelist.cpp \ tools/qhash.cpp \ tools/qline.cpp \ tools/qlinkedlist.cpp \ diff --git a/tests/auto/corelib.pro b/tests/auto/corelib.pro index 95a16f67d9..7a655d6208 100644 --- a/tests/auto/corelib.pro +++ b/tests/auto/corelib.pro @@ -30,6 +30,7 @@ SUBDIRS=\ qfileinfo \ qfilesystemwatcher \ qflags \ + qfreelist \ qfuture \ qfuturewatcher \ qgetputenv \ diff --git a/tests/auto/qfreelist/qfreelist.pro b/tests/auto/qfreelist/qfreelist.pro new file mode 100644 index 0000000000..b7f2b3d38f --- /dev/null +++ b/tests/auto/qfreelist/qfreelist.pro @@ -0,0 +1,6 @@ +load(qttest_p4) +SOURCES += tst_qfreelist.cpp +QT += core-private +QT -= gui + +!private_tests:SOURCES += $$QT_SOURCE_TREE/src/corelib/tools/qfreelist.cpp diff --git a/tests/auto/qfreelist/tst_qfreelist.cpp b/tests/auto/qfreelist/tst_qfreelist.cpp new file mode 100644 index 0000000000..139d76e64a --- /dev/null +++ b/tests/auto/qfreelist/tst_qfreelist.cpp @@ -0,0 +1,179 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the test suite of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** 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.1, 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. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + + +#include <QtCore/QCoreApplication> +#include <QtCore/QElapsedTimer> +#include <QtCore/QList> +#include <QtCore/QThread> +#include <private/qfreelist_p.h> +#include <QtTest/QtTest> + +//TESTED_CLASS=QFreeList +//TESTED_FILES=corelib/tools/qfreelist_p.h + +class tst_QFreeList : public QObject +{ + Q_OBJECT + +private slots: + void basicTest(); + void customized(); + void threadedTest(); +}; + +void tst_QFreeList::basicTest() +{ + { + QFreeList<void> voidFreeList; + int zero = voidFreeList.next(); + int one = voidFreeList.next(); + int two = voidFreeList.next(); + QCOMPARE(zero, 0); + QCOMPARE(one, 1); + QCOMPARE(two, 2); + voidFreeList[zero]; + voidFreeList[one]; + voidFreeList[two]; + voidFreeList.at(zero); + voidFreeList.at(one); + voidFreeList.at(two); + voidFreeList.release(one); + int next = voidFreeList.next(); + QCOMPARE(next, 1); + voidFreeList[next]; + voidFreeList.at(next); + } + + { + QFreeList<int> intFreeList; + int zero = intFreeList.next(); + int one = intFreeList.next(); + int two = intFreeList.next(); + QCOMPARE(zero, 0); + QCOMPARE(one, 1); + QCOMPARE(two, 2); + intFreeList[zero] = zero; + intFreeList[one] = one; + intFreeList[two] = two; + QCOMPARE(intFreeList.at(zero), zero); + QCOMPARE(intFreeList.at(one), one); + QCOMPARE(intFreeList.at(two), two); + intFreeList.release(one); + int next = intFreeList.next(); + QCOMPARE(next, 1); + QCOMPARE(intFreeList.at(next), one); + intFreeList[next] = -one; + QCOMPARE(intFreeList.at(next), -one); + } +} + +struct CustomFreeListConstants : public QFreeListDefaultConstants +{ + enum { + InitialNextValue = 50, + BlockCount = 10 + }; + + static const int Sizes[10]; +}; + +const int CustomFreeListConstants::Sizes[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 16777216 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 }; + +void tst_QFreeList::customized() +{ + QFreeList<void, CustomFreeListConstants> customFreeList; + int next = customFreeList.next(); + QCOMPARE(next, int(CustomFreeListConstants::InitialNextValue)); + customFreeList[next]; + customFreeList.at(next); + customFreeList.release(next); +} + +enum { TimeLimit = 3000 }; + +class FreeListThread : public QThread +{ + static QFreeList<void> freelist; + +public: + inline FreeListThread() : QThread() { } + inline void run() + { + QElapsedTimer t; + t.start(); + QList<int> needToRelease; + do { + int i = freelist.next(); + int j = freelist.next(); + int k = freelist.next(); + int l = freelist.next(); + freelist.release(k); + int n = freelist.next(); + int m = freelist.next(); + freelist.release(l); + freelist.release(m); + freelist.release(n); + freelist.release(j); + // freelist.release(i); + needToRelease << i; + } while (t.elapsed() < TimeLimit); + + foreach (int x, needToRelease) + freelist.release(x); + } +}; + +QFreeList<void> FreeListThread::freelist; + +void tst_QFreeList::threadedTest() +{ + const int ThreadCount = QThread::idealThreadCount(); + FreeListThread *threads = new FreeListThread[ThreadCount]; + for (int i = 0; i < ThreadCount; ++i) + threads[i].start(); + for (int i = 0; i < ThreadCount; ++i) + threads[i].wait(); + delete [] threads; +} + +QTEST_MAIN(tst_QFreeList) +#include "tst_qfreelist.moc" |