qfreelist_p.h

Go to the documentation of this file.

// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#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