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 x = x & ConstantsType::IndexMask;
122 for (int i = 0; i < ConstantsType::BlockCount; ++i) {
123 int size = ConstantsType::Sizes[i];
124 if (x < size)
125 return i;
126 x -= size;
127 }
128 Q_UNREACHABLE_RETURN(-1);
129 }
130
131 // allocate a block of the given \a size, initialized starting with the given \a offset
132 static inline ElementType *allocate(int offset, int size)
133 {
134 // qDebug("QFreeList: allocating %d elements (%ld bytes) with offset %d", size, size * sizeof(ElementType), offset);
135 ElementType *v = new ElementType[size];
136 for (int i = 0; i < size; ++i)
137 v[i].next.storeRelaxed(offset + i + 1);
138 return v;
139 }
140
141 // take the current serial number from \a o, increment it, and store it in \a n
142 static inline int incrementserial(int o, int n)
143 {
144 return int((uint(n) & ConstantsType::IndexMask) | ((uint(o) + ConstantsType::SerialCounter) & ConstantsType::SerialMask));
145 }
146
147 // the blocks
148 QAtomicPointer<ElementType> _v[ConstantsType::BlockCount];
149 // the next free id
150 QAtomicInt _next;
151
152 // QFreeList is not copyable
153 Q_DISABLE_COPY_MOVE(QFreeList)
154
155public:
156 constexpr inline QFreeList();
157 inline ~QFreeList();
158
159 // returns the payload for the given index \a x
160 inline ConstReferenceType at(int x) const;
161 inline ReferenceType operator[](int x);
162
163 /*
164 Return the next free id. Use this id to access the payload (see above).
165 Call release(id) when done using the id.
166 */
167 inline int next();
168 inline void release(int id);
169};
170
171template <typename T, typename ConstantsType>
172constexpr inline QFreeList<T, ConstantsType>::QFreeList()
173 :
174 _v{}, // uniform initialization required
175 _next(ConstantsType::InitialNextValue)
176{ }
177
178template <typename T, typename ConstantsType>
179inline QFreeList<T, ConstantsType>::~QFreeList()
180{
181 for (int i = 0; i < ConstantsType::BlockCount; ++i)
182 delete [] _v[i].loadAcquire();
183}
184
185template <typename T, typename ConstantsType>
186inline typename QFreeList<T, ConstantsType>::ConstReferenceType QFreeList<T, ConstantsType>::at(int x) const
187{
188 const int block = blockfor(x);
189 return (_v[block].loadRelaxed())[x].t();
190}
191
192template <typename T, typename ConstantsType>
193inline typename QFreeList<T, ConstantsType>::ReferenceType QFreeList<T, ConstantsType>::operator[](int x)
194{
195 const int block = blockfor(x);
196 return (_v[block].loadRelaxed())[x].t();
197}
198
199template <typename T, typename ConstantsType>
200inline int QFreeList<T, ConstantsType>::next()
201{
202 int id, newid, at;
203 ElementType *v;
204 do {
205 id = _next.loadAcquire();
206
207 at = id & ConstantsType::IndexMask;
208 const int block = blockfor(x&: at);
209 v = _v[block].loadAcquire();
210
211 if (!v) {
212 v = allocate(offset: (id & ConstantsType::IndexMask) - at, size: ConstantsType::Sizes[block]);
213 if (!_v[block].testAndSetRelease(nullptr, v)) {
214 // race with another thread lost
215 delete[] v;
216 v = _v[block].loadAcquire();
217 Q_ASSERT(v != nullptr);
218 }
219 }
220
221 newid = v[at].next.loadRelaxed() | (id & ~ConstantsType::IndexMask);
222 } while (!_next.testAndSetRelease(expectedValue: id, newValue: newid));
223 // qDebug("QFreeList::next(): returning %d (_next now %d, serial %d)",
224 // id & ConstantsType::IndexMask,
225 // newid & ConstantsType::IndexMask,
226 // (newid & ~ConstantsType::IndexMask) >> 24);
227 return id;
228}
229
230template <typename T, typename ConstantsType>
231inline void QFreeList<T, ConstantsType>::release(int id)
232{
233 int at = id & ConstantsType::IndexMask;
234 const int block = blockfor(x&: at);
235 ElementType *v = _v[block].loadRelaxed();
236
237 int x, newid;
238 do {
239 x = _next.loadAcquire();
240 v[at].next.storeRelaxed(x & ConstantsType::IndexMask);
241
242 newid = incrementserial(o: x, n: id);
243 } while (!_next.testAndSetRelease(expectedValue: x, newValue: newid));
244 // qDebug("QFreeList::release(%d): _next now %d (was %d), serial %d",
245 // id & ConstantsType::IndexMask,
246 // newid & ConstantsType::IndexMask,
247 // x & ConstantsType::IndexMask,
248 // (newid & ~ConstantsType::IndexMask) >> 24);
249}
250
251QT_END_NAMESPACE
252
253#endif // QFREELIST_P_H
254

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