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/*! \internal
60
61 Element in a QFreeList. ConstReferenceType and ReferenceType are used as
62 the return values for QFreeList::at() and QFreeList::operator[](). Contains
63 the real data storage (_t) and the id of the next free element (next).
64
65 Note: the t() functions should be used to access the data, not _t.
66*/
67template <typename T>
68struct QFreeListElement
69{
70 typedef const T &ConstReferenceType;
71 typedef T &ReferenceType;
72
73 T _t;
74 QAtomicInt next;
75
76 inline ConstReferenceType t() const { return _t; }
77 inline ReferenceType t() { return _t; }
78};
79
80/*! \internal
81
82 Element in a QFreeList without a payload. ConstReferenceType and
83 ReferenceType are void, the t() functions return void and are empty.
84*/
85template <>
86struct QFreeListElement<void>
87{
88 typedef void ConstReferenceType;
89 typedef void ReferenceType;
90
91 QAtomicInt next;
92
93 inline void t() const { }
94 inline void t() { }
95};
96
97/*! \internal
98
99 Defines default constants used by QFreeList:
100
101 - The initial value returned by QFreeList::next() is zero.
102
103 - QFreeList allows for up to 16777216 elements in QFreeList and uses the top
104 8 bits to store a serial counter for ABA protection.
105
106 - QFreeList will make a maximum of 4 allocations (blocks), with each
107 successive block larger than the previous.
108
109 - Sizes static int[] array to define the size of each block.
110
111 It is possible to define your own constants struct/class and give this to
112 QFreeList to customize/tune the behavior.
113*/
114struct Q_AUTOTEST_EXPORT QFreeListDefaultConstants
115{
116 // used by QFreeList, make sure to define all of when customizing
117 enum {
118 InitialNextValue = 0,
119 IndexMask = 0x00ffffff,
120 SerialMask = ~IndexMask & ~0x80000000,
121 SerialCounter = IndexMask + 1,
122 MaxIndex = IndexMask,
123 BlockCount = 4
124 };
125
126 static const int Sizes[BlockCount];
127};
128
129/*! \internal
130
131 This is a generic implementation of a lock-free free list. Use next() to
132 get the next free entry in the list, and release(id) when done with the id.
133
134 This version is templated and allows having a payload of type T which can
135 be accessed using the id returned by next(). The payload is allocated and
136 deallocated automatically by the free list, but *NOT* when calling
137 next()/release(). Initialization should be done by code needing it after
138 next() returns. Likewise, cleanup() should happen before calling release().
139 It is possible to have use 'void' as the payload type, in which case the
140 free list only contains indexes to the next free entry.
141
142 The ConstantsType type defaults to QFreeListDefaultConstants above. You can
143 define your custom ConstantsType, see above for details on what needs to be
144 available.
145*/
146template <typename T, typename ConstantsType = QFreeListDefaultConstants>
147class QFreeList
148{
149 typedef T ValueType;
150 typedef QFreeListElement<T> ElementType;
151 typedef typename ElementType::ConstReferenceType ConstReferenceType;
152 typedef typename ElementType::ReferenceType ReferenceType;
153
154 // return which block the index \a x falls in, and modify \a x to be the index into that block
155 static inline int blockfor(int &x)
156 {
157 for (int i = 0; i < ConstantsType::BlockCount; ++i) {
158 int size = ConstantsType::Sizes[i];
159 if (x < size)
160 return i;
161 x -= size;
162 }
163 Q_ASSERT(false);
164 return -1;
165 }
166
167 // allocate a block of the given \a size, initialized starting with the given \a offset
168 static inline ElementType *allocate(int offset, int size)
169 {
170 // qDebug("QFreeList: allocating %d elements (%ld bytes) with offset %d", size, size * sizeof(ElementType), offset);
171 ElementType *v = new ElementType[size];
172 for (int i = 0; i < size; ++i)
173 v[i].next.storeRelaxed(offset + i + 1);
174 return v;
175 }
176
177 // take the current serial number from \a o, increment it, and store it in \a n
178 static inline int incrementserial(int o, int n)
179 {
180 return int((uint(n) & ConstantsType::IndexMask) | ((uint(o) + ConstantsType::SerialCounter) & ConstantsType::SerialMask));
181 }
182
183 // the blocks
184 QAtomicPointer<ElementType> _v[ConstantsType::BlockCount];
185 // the next free id
186 QAtomicInt _next;
187
188 // QFreeList is not copyable
189 Q_DISABLE_COPY_MOVE(QFreeList)
190
191public:
192 constexpr inline QFreeList();
193 inline ~QFreeList();
194
195 // returns the payload for the given index \a x
196 inline ConstReferenceType at(int x) const;
197 inline ReferenceType operator[](int x);
198
199 /*
200 Return the next free id. Use this id to access the payload (see above).
201 Call release(id) when done using the id.
202 */
203 inline int next();
204 inline void release(int id);
205};
206
207template <typename T, typename ConstantsType>
208constexpr inline QFreeList<T, ConstantsType>::QFreeList()
209 :
210#if defined(Q_COMPILER_CONSTEXPR)
211 _v{}, // uniform initialization required
212#endif
213 _next(ConstantsType::InitialNextValue)
214{ }
215
216template <typename T, typename ConstantsType>
217inline QFreeList<T, ConstantsType>::~QFreeList()
218{
219 for (int i = 0; i < ConstantsType::BlockCount; ++i)
220 delete [] _v[i].loadAcquire();
221}
222
223template <typename T, typename ConstantsType>
224inline typename QFreeList<T, ConstantsType>::ConstReferenceType QFreeList<T, ConstantsType>::at(int x) const
225{
226 const int block = blockfor(x);
227 return (_v[block].loadRelaxed())[x].t();
228}
229
230template <typename T, typename ConstantsType>
231inline typename QFreeList<T, ConstantsType>::ReferenceType QFreeList<T, ConstantsType>::operator[](int x)
232{
233 const int block = blockfor(x);
234 return (_v[block].loadRelaxed())[x].t();
235}
236
237template <typename T, typename ConstantsType>
238inline int QFreeList<T, ConstantsType>::next()
239{
240 int id, newid, at;
241 ElementType *v;
242 do {
243 id = _next.loadAcquire();
244
245 at = id & ConstantsType::IndexMask;
246 const int block = blockfor(at);
247 v = _v[block].loadAcquire();
248
249 if (!v) {
250 v = allocate((id & ConstantsType::IndexMask) - at, ConstantsType::Sizes[block]);
251 if (!_v[block].testAndSetRelease(nullptr, v)) {
252 // race with another thread lost
253 delete[] v;
254 v = _v[block].loadAcquire();
255 Q_ASSERT(v != nullptr);
256 }
257 }
258
259 newid = v[at].next.loadRelaxed() | (id & ~ConstantsType::IndexMask);
260 } while (!_next.testAndSetRelease(id, newid));
261 // qDebug("QFreeList::next(): returning %d (_next now %d, serial %d)",
262 // id & ConstantsType::IndexMask,
263 // newid & ConstantsType::IndexMask,
264 // (newid & ~ConstantsType::IndexMask) >> 24);
265 return id & ConstantsType::IndexMask;
266}
267
268template <typename T, typename ConstantsType>
269inline void QFreeList<T, ConstantsType>::release(int id)
270{
271 int at = id & ConstantsType::IndexMask;
272 const int block = blockfor(at);
273 ElementType *v = _v[block].loadRelaxed();
274
275 int x, newid;
276 do {
277 x = _next.loadAcquire();
278 v[at].next.storeRelaxed(x & ConstantsType::IndexMask);
279
280 newid = incrementserial(x, id);
281 } while (!_next.testAndSetRelease(x, newid));
282 // qDebug("QFreeList::release(%d): _next now %d (was %d), serial %d",
283 // id & ConstantsType::IndexMask,
284 // newid & ConstantsType::IndexMask,
285 // x & ConstantsType::IndexMask,
286 // (newid & ~ConstantsType::IndexMask) >> 24);
287}
288
289QT_END_NAMESPACE
290
291#endif // QFREELIST_P_H
292