Phonon

lockfreequeue.cpp
1/* This file is part of the KDE project
2 Copyright (C) 2008 Matthias Kretz <kretz@kde.org>
3
4 This library is free software; you can redistribute it and/or
5 modify it under the terms of the GNU Lesser General Public
6 License as published by the Free Software Foundation; either
7 version 2.1 of the License, or (at your option) version 3, or any
8 later version accepted by the membership of KDE e.V. (or its
9 successor approved by the membership of KDE e.V.), Nokia Corporation
10 (or its successors, if any) and the KDE Free Qt Foundation, which shall
11 act as a proxy defined in Section 6 of version 3 of the license.
12
13 This library is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
17
18 You should have received a copy of the GNU Lesser General Public
19 License along with this library. If not, see <http://www.gnu.org/licenses/>.
20
21*/
22
23#include "lockfreequeue_p.h"
24#include <QHash>
25#include <QWriteLocker>
26#include <QReadWriteLock>
27#include <stdlib.h>
28#include "globalstatic_p.h"
29
30struct MemoryPool
31{
32 ~MemoryPool();
33 // Stack structure:
35 QAtomicInt count;
36 QAtomicInt size;
37
38 void clear();
39};
40
41void MemoryPool::clear()
42{
43 LockFreeQueueBase::NodeBase *node = stack;
44 while (node) {
45 if (stack.testAndSetAcquire(node, const_cast<LockFreeQueueBase::NodeBase *>(node->next))) {
46 count.deref();
47 free(node);
48 }
49 node = stack;
50 }
51}
52
53MemoryPool::~MemoryPool()
54{
55 LockFreeQueueBase::NodeBase *node = stack;
56 while (node) {
57 void *toDelete = node;
58 node = const_cast<LockFreeQueueBase::NodeBase *>(node->next);
59 ::free(toDelete);
60 }
61}
62
63struct MemoryPoolVector
64{
65 static const int POOL_COUNT = 16;
66 ~MemoryPoolVector() { delete next; }
67 inline MemoryPool &operator[](size_t s)
68 {
69 for (int i = 0; i < POOL_COUNT; ++i) {
70 if (m_pools[i].size == static_cast<int>(s)) {
71 return m_pools[i];
72 } else if (m_pools[i].size == 0) {
73 if (m_pools[i].size.testAndSetRelaxed(0, static_cast<int>(s))) {
74 return m_pools[i];
75 }
76 if (m_pools[i].size == static_cast<int>(s)) {
77 return m_pools[i];
78 }
79 }
80 }
81 if (!next) {
82 MemoryPoolVector *newPoolVector = new MemoryPoolVector;
83 if (!next.testAndSetRelaxed(0, newPoolVector)) {
84 delete newPoolVector;
85 }
86 }
87 return (*next)[s];
88 }
89
90 void clearAllPools()
91 {
92 for (int i = 0; i < POOL_COUNT; ++i) {
93 if (0 == m_pools[i].size) {
94 return;
95 }
96 m_pools[i].clear();
97 }
98 if (next) {
99 next->clearAllPools();
100 }
101 }
102
103 MemoryPool m_pools[POOL_COUNT];
105};
106
107static int s_poolSize = 128;
108PHONON_GLOBAL_STATIC(MemoryPoolVector, s_memoryPool)
109
110void *LockFreeQueueBase::NodeBaseKeepNodePool::operator new(size_t s)
111{
112 MemoryPool &p = (*s_memoryPool)[s];
113 NodeBase *node = p.stack;
114 if (node) {
115 if (!p.stack.testAndSetAcquire(node, const_cast<NodeBase *>(node->next))) {
116 return ::malloc(s);
117 }
118 p.count.deref();
119 return node;
120 }
121 return ::malloc(s);
122}
123
124void LockFreeQueueBase::NodeBaseKeepNodePool::operator delete(void *ptr, size_t s)
125{
126 MemoryPool &p = (*s_memoryPool)[s];
127 if (p.count > s_poolSize) {
128 ::free(ptr);
129 return;
130 }
131 NodeBase *node = static_cast<NodeBase *>(ptr);
132 NodeBase *next = p.stack;
133 node->next = next;
134 if (!p.stack.testAndSetOrdered(next, node)) {
135 ::free(ptr);
136 return;
137 }
138 p.count.ref();
139}
140
141void LockFreeQueueBase::NodeBaseKeepNodePool::clear()
142{
143 s_memoryPool->clearAllPools();
144}
145
146void LockFreeQueueBase::NodeBaseKeepNodePool::setPoolSize(int s)
147{
148 s_poolSize = s;
149}
150
151int LockFreeQueueBase::NodeBaseKeepNodePool::poolSize()
152{
153 return s_poolSize;
154}
155
156class LockFreeQueueBasePrivate
157{
158 public:
159 LockFreeQueueBasePrivate();
160 ~LockFreeQueueBasePrivate();
161 QReadWriteLock dataReadyHandlerMutex;
162 LockFreeQueueBase::NodeBase *sentinel; // end marker
163 LockFreeQueueBase::NodeBase *lastHeadNode;
166 QAtomicInt size;
167 LockFreeQueueBase::DataReadyHandler *dataReadyHandler;
168};
169
170LockFreeQueueBasePrivate::LockFreeQueueBasePrivate()
171 : sentinel(new LockFreeQueueBase::NodeBase(0)),
172 lastHeadNode(new LockFreeQueueBase::NodeBase(sentinel)),
173 queueHead(&lastHeadNode->next),
174 queueTail(&lastHeadNode->next),
175 size(0),
176 dataReadyHandler(0)
177{
178 // let d->sentinel point to itself so that we can use d->sentinel->next as
179 // QAtomicPointer<Node> for d->queueHead and d->queueTail
180 sentinel->next = sentinel;
181}
182
183LockFreeQueueBasePrivate::~LockFreeQueueBasePrivate()
184{
185 Q_ASSERT(queueHead);
186 LockFreeQueueBase::NodeBase *node = lastHeadNode;
187 while (node != sentinel) {
188 LockFreeQueueBase::NodeBase *toDelete = node;
189 node = const_cast<LockFreeQueueBase::NodeBase *>(node->next);
190 toDelete->deref();
191 }
192}
193
194LockFreeQueueBase::LockFreeQueueBase()
195 : d(new LockFreeQueueBasePrivate)
196{
197}
198
199LockFreeQueueBase::~LockFreeQueueBase()
200{
201 delete d;
202}
203
204void LockFreeQueueBase::setDataReadyHandler(DataReadyHandler *h)
205{
206 QWriteLocker lock(&d->dataReadyHandlerMutex);
207 d->dataReadyHandler = h;
208}
209
210void LockFreeQueueBase::_enqueue(NodeBase *newNode)
211{
212 newNode->ref();
213 newNode->next = d->sentinel;
214 /*if (d->size > 0 && newNode->priority > std::numeric_limits<int>::min()) {
215 NodeBasePointer *node = d->queueHead.fetchAndStoreRelaxed(&d->sentinel->next);
216 if (node == &d->sentinel->next) {
217 // Another thread got the real node, we just got the placeholder telling us to not touch
218 // anything. As we replaced &d->sentinel->next with &d->sentinel->next in
219 // d->queueHead we don't have to reset anything.
220 }
221 // node is a pointer to a Node::next member pointing to the first entry in
222 // the list
223 if (*node == d->sentinel) {
224 // the list is empty, good
225 }
226 } else {*/
227 // just append
228 NodeBasePointer &lastNextPointer = *d->queueTail.fetchAndStoreAcquire(&newNode->next);
229 lastNextPointer = newNode;
230 d->size.ref();
231
232 if (d->dataReadyHandler) {
233 QReadLocker lock(&d->dataReadyHandlerMutex);
234 if (d->dataReadyHandler) {
235 d->dataReadyHandler->dataReady();
236 }
237 }
238 //}
239}
240
241LockFreeQueueBase::NodeBase *LockFreeQueueBase::_acquireHeadNodeBlocking()
242{
243 NodeBasePointer *node = 0;
244 while (d->size > 0) {
245 if ((node = d->queueHead.fetchAndStoreRelaxed(&d->sentinel->next)) != &d->sentinel->next) {
246 // node is a pointer to a Node::next member pointing to the first entry in the list
247 if (*node != d->sentinel) {
248 d->size.deref();
249 NodeBase *_node = const_cast<NodeBase *>(*node); // cast volatile away
250 _node->ref();
251
252 NodeBase *toDeref = d->lastHeadNode;
253 d->lastHeadNode = _node;
254 const bool check = d->queueHead.testAndSetRelease(&d->sentinel->next, &_node->next);
255 Q_ASSERT(check); Q_UNUSED(check);
256 toDeref->deref();
257
258 return _node;
259 }
260 // empty (d->size == 0), put it back
261 const bool check = d->queueHead.testAndSetRelaxed(&d->sentinel->next, node);
262 Q_ASSERT(check); Q_UNUSED(check);
263 // try again, with some luck d->size is > 0 again
264 }
265 }
266 return 0;
267}
268
269LockFreeQueueBase::NodeBase *LockFreeQueueBase::_acquireHeadNode()
270{
271 if (*d->queueHead == d->sentinel || d->queueHead == &d->sentinel->next) {
272 return 0;
273 }
274 // setting d->queueHead to &d->sentinel->next makes the above check fail (i.e. all
275 // other threads in a dequeue function will exit). Also enqueue will not modify
276 // this as d->queueTail references d->lastHeadNode->next which != d->sentinel->next
277 NodeBasePointer *node = d->queueHead.fetchAndStoreRelaxed(&d->sentinel->next);
278 if (node == &d->sentinel->next) {
279 // Another thread got the real node, we just got the placeholder telling us to not touch
280 // anything. As we replaced &d->sentinel->next with &d->sentinel->next in
281 // d->queueHead we don't have to reset anything.
282 return 0;
283 }
284 // node is a pointer to a Node::next member pointing to the first entry in
285 // the list
286 if (*node == d->sentinel) {
287 //qDebug() << "empty, put it back";
288 const bool check = d->queueHead.testAndSetRelaxed(&d->sentinel->next, node);
289 Q_ASSERT(check); Q_UNUSED(check);
290 return 0;
291 }
292 d->size.deref();
293
294 NodeBase *_node = const_cast<NodeBase *>(*node);
295 _node->ref();
296
297 NodeBase *toDeref = d->lastHeadNode;
298 d->lastHeadNode = _node;
299 const bool check = d->queueHead.testAndSetRelease(&d->sentinel->next, &_node->next);
300 Q_ASSERT(check); Q_UNUSED(check);
301 toDeref->deref();
302
303 return _node;
304}
305
306int LockFreeQueueBase::size() const
307{
308 return d->size;
309}
QAction * next(const QObject *recvr, const char *slot, QObject *parent)
bool testAndSetAcquire(T *expectedValue, T *newValue)
bool testAndSetOrdered(T *expectedValue, T *newValue)
bool testAndSetRelaxed(T *expectedValue, T *newValue)
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Fri Oct 11 2024 12:10:22 by doxygen 1.12.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.