1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QFREELIST_P_H
5#define QFREELIST_P_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists purely as an
12// implementation detail. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include <QtCore/private/qglobal_p.h>
19#include <QtCore/qatomic.h>
20
21QT_BEGIN_NAMESPACE
22
23/*! \internal
24
25 Element in a QFreeList. ConstReferenceType and ReferenceType are used as
26 the return values for QFreeList::at() and QFreeList::operator[](). Contains
27 the real data storage (_t) and the id of the next free element (next).
28
29 Note: the t() functions should be used to access the data, not _t.
30*/
31template <typename T>
32struct QFreeListElement
33{
34 typedef const T &ConstReferenceType;
35 typedef T &ReferenceType;
36
37 T _t;
38 QAtomicInt next;
39
40 inline ConstReferenceType t() const { return _t; }
41 inline ReferenceType t() { return _t; }
42};
43
44/*! \internal
45
46 Element in a QFreeList without a payload. ConstReferenceType and
47 ReferenceType are void, the t() functions return void and are empty.
48*/
49template <>
50struct QFreeListElement<void>
51{
52 typedef void ConstReferenceType;
53 typedef void ReferenceType;
54
55 QAtomicInt next;
56
57 inline void t() const { }
58 inline void t() { }
59};
60
61/*! \internal
62
63 Defines default constants used by QFreeList:
64
65 - The initial value returned by QFreeList::next() is zero.
66
67 - QFreeList allows for up to 16777216 elements in QFreeList and uses the top
68 8 bits to store a serial counter for ABA protection.
69
70 - QFreeList will make a maximum of 4 allocations (blocks), with each
71 successive block larger than the previous.
72
73 - Sizes static int[] array to define the size of each block.
74
75 It is possible to define your own constants struct/class and give this to
76 QFreeList to customize/tune the behavior.
77*/
78struct Q_AUTOTEST_EXPORT QFreeListDefaultConstants
79{
80 // used by QFreeList, make sure to define all of when customizing
81 enum {
82 InitialNextValue = 0,
83 IndexMask = 0x00ffffff,
84 SerialMask = ~IndexMask & ~0x80000000,
85 SerialCounter = IndexMask + 1,
86 MaxIndex = IndexMask,
87 BlockCount = 4
88 };
89
90 static const int Sizes[BlockCount];
91};
92
93/*! \internal
94
95 This is a generic implementation of a lock-free free list. Use next() to
96 get the next free entry in the list, and release(id) when done with the id.
97
98 This version is templated and allows having a payload of type T which can
99 be accessed using the id returned by next(). The payload is allocated and
100 deallocated automatically by the free list, but *NOT* when calling
101 next()/release(). Initialization should be done by code needing it after
102 next() returns. Likewise, cleanup() should happen before calling release().
103 It is possible to have use 'void' as the payload type, in which case the
104 free list only contains indexes to the next free entry.
105
106 The ConstantsType type defaults to QFreeListDefaultConstants above. You can
107 define your custom ConstantsType, see above for details on what needs to be
108 available.
109*/
110template <typename T, typename ConstantsType = QFreeListDefaultConstants>
111class QFreeList
112{
113 typedef T ValueType;
114 typedef QFreeListElement<T> ElementType;
115 typedef typename ElementType::ConstReferenceType ConstReferenceType;
116 typedef typename ElementType::ReferenceType ReferenceType;
117
118 // return which block the index \a x falls in, and modify \a x to be the index into that block
119 static inline int blockfor(int &x)
120 {
121 for (int i = 0; i < ConstantsType::BlockCount; ++i) {
122 int size = ConstantsType::Sizes[i];
123 if (x < size)
124 return i;
125 x -= size;
126 }
127 Q_UNREACHABLE_RETURN(-1);
128 }
129
130 // allocate a block of the given \a size, initialized starting with the given \a offset
131 static inline ElementType *allocate(int offset, int size)
132 {
133 // qDebug("QFreeList: allocating %d elements (%ld bytes) with offset %d", size, size * sizeof(ElementType), offset);
134 ElementType *v = new ElementType[size];
135 for (int i = 0; i < size; ++i)
136 v[i].next.storeRelaxed(offset + i + 1);
137 return v;
138 }
139
140 // take the current serial number from \a o, increment it, and store it in \a n
141 static inline int incrementserial(int o, int n)
142 {
143 return int((uint(n) & ConstantsType::IndexMask) | ((uint(o) + ConstantsType::SerialCounter) & ConstantsType::SerialMask));
144 }
145
146 // the blocks
147 QAtomicPointer<ElementType> _v[ConstantsType::BlockCount];
148 // the next free id
149 QAtomicInt _next;
150
151 // QFreeList is not copyable
152 Q_DISABLE_COPY_MOVE(QFreeList)
153
154public:
155 constexpr inline QFreeList();
156 inline ~QFreeList();
157
158 // returns the payload for the given index \a x
159 inline ConstReferenceType at(int x) const;
160 inline ReferenceType operator[](int x);
161
162 /*
163 Return the next free id. Use this id to access the payload (see above).
164 Call release(id) when done using the id.
165 */
166 inline int next();
167 inline void release(int id);
168};
169
170template <typename T, typename ConstantsType>
171constexpr inline QFreeList<T, ConstantsType>::QFreeList()
172 :
173 _v{}, // uniform initialization required
174 _next(ConstantsType::InitialNextValue)
175{ }
176
177template <typename T, typename ConstantsType>
178inline QFreeList<T, ConstantsType>::~QFreeList()
179{
180 for (int i = 0; i < ConstantsType::BlockCount; ++i)
181 delete [] _v[i].loadAcquire();
182}
183
184template <typename T, typename ConstantsType>
185inline typename QFreeList<T, ConstantsType>::ConstReferenceType QFreeList<T, ConstantsType>::at(int x) const
186{
187 const int block = blockfor(x);
188 return (_v[block].loadRelaxed())[x].t();
189}
190
191template <typename T, typename ConstantsType>
192inline typename QFreeList<T, ConstantsType>::ReferenceType QFreeList<T, ConstantsType>::operator[](int x)
193{
194 const int block = blockfor(x);
195 return (_v[block].loadRelaxed())[x].t();
196}
197
198template <typename T, typename ConstantsType>
199inline int QFreeList<T, ConstantsType>::next()
200{
201 int id, newid, at;
202 ElementType *v;
203 do {
204 id = _next.loadAcquire();
205
206 at = id & ConstantsType::IndexMask;
207 const int block = blockfor(x&: at);
208 v = _v[block].loadAcquire();
209
210 if (!v) {
211 v = allocate(offset: (id & ConstantsType::IndexMask) - at, size: ConstantsType::Sizes[block]);
212 if (!_v[block].testAndSetRelease(nullptr, v)) {
213 // race with another thread lost
214 delete[] v;
215 v = _v[block].loadAcquire();
216 Q_ASSERT(v != nullptr);
217 }
218 }
219
220 newid = v[at].next.loadRelaxed() | (id & ~ConstantsType::IndexMask);
221 } while (!_next.testAndSetRelease(expectedValue: id, newValue: newid));
222 // qDebug("QFreeList::next(): returning %d (_next now %d, serial %d)",
223 // id & ConstantsType::IndexMask,
224 // newid & ConstantsType::IndexMask,
225 // (newid & ~ConstantsType::IndexMask) >> 24);
226 return id & ConstantsType::IndexMask;
227}
228
229template <typename T, typename ConstantsType>
230inline void QFreeList<T, ConstantsType>::release(int id)
231{
232 int at = id & ConstantsType::IndexMask;
233 const int block = blockfor(x&: at);
234 ElementType *v = _v[block].loadRelaxed();
235
236 int x, newid;
237 do {
238 x = _next.loadAcquire();
239 v[at].next.storeRelaxed(x & ConstantsType::IndexMask);
240
241 newid = incrementserial(o: x, n: id);
242 } while (!_next.testAndSetRelease(expectedValue: x, newValue: newid));
243 // qDebug("QFreeList::release(%d): _next now %d (was %d), serial %d",
244 // id & ConstantsType::IndexMask,
245 // newid & ConstantsType::IndexMask,
246 // x & ConstantsType::IndexMask,
247 // (newid & ~ConstantsType::IndexMask) >> 24);
248}
249
250QT_END_NAMESPACE
251
252#endif // QFREELIST_P_H
253

source code of qtbase/src/corelib/tools/qfreelist_p.h