qfreelist_p.h

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $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/private/qglobal_p.h>
#include <QtCore/qatomic.h>
 
QT_BEGIN_NAMESPACE
 
template <typename T>
struct QFreeListElement
{
    typedef const T &ConstReferenceType;
    typedef T &ReferenceType;
 
    T _t;
    QAtomicInt next;
 
    inline ConstReferenceType t() const { return _t; }
    inline ReferenceType t() { return _t; }
};
 
template <>
struct QFreeListElement<void>
{
    typedef void ConstReferenceType;
    typedef void ReferenceType;
 
    QAtomicInt next;
 
    inline void t() const { }
    inline void t() { }
};
 
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];
};
 
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_UNREACHABLE();
        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.storeRelaxed(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 int((uint(n) & ConstantsType::IndexMask) | ((uint(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_MOVE(QFreeList)
 
public:
    constexpr 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>
constexpr inline QFreeList<T, ConstantsType>::QFreeList()
    :
      _v{}, // uniform initialization required
      _next(ConstantsType::InitialNextValue)
{ }
 
template <typename T, typename ConstantsType>
inline QFreeList<T, ConstantsType>::~QFreeList()
{
    for (int i = 0; i < ConstantsType::BlockCount; ++i)
        delete [] _v[i].loadAcquire();
}
 
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].loadRelaxed())[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].loadRelaxed())[x].t();
}
 
template <typename T, typename ConstantsType>
inline int QFreeList<T, ConstantsType>::next()
{
    int id, newid, at;
    ElementType *v;
    do {
        id = _next.loadAcquire();
 
        at = id & ConstantsType::IndexMask;
        const int block = blockfor(at);
        v = _v[block].loadAcquire();
 
        if (!v) {
            v = allocate((id & ConstantsType::IndexMask) - at, ConstantsType::Sizes[block]);
            if (!_v[block].testAndSetRelease(nullptr, v)) {
                // race with another thread lost
                delete[] v;
                v = _v[block].loadAcquire();
                Q_ASSERT(v != nullptr);
            }
        }
 
        newid = v[at].next.loadRelaxed() | (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].loadRelaxed();
 
    int x, newid;
    do {
        x = _next.loadAcquire();
        v[at].next.storeRelaxed(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
 
#endif // QFREELIST_P_H