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

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