File indexing completed on 2024-05-05 04:44:41
0001 /* This file is part of the KDE project 0002 Copyright (C) 2008 Matthias Kretz <kretz@kde.org> 0003 0004 This library is free software; you can redistribute it and/or 0005 modify it under the terms of the GNU Lesser General Public 0006 License as published by the Free Software Foundation; either 0007 version 2.1 of the License, or (at your option) version 3, or any 0008 later version accepted by the membership of KDE e.V. (or its 0009 successor approved by the membership of KDE e.V.), Nokia Corporation 0010 (or its successors, if any) and the KDE Free Qt Foundation, which shall 0011 act as a proxy defined in Section 6 of version 3 of the license. 0012 0013 This library is distributed in the hope that it will be useful, 0014 but WITHOUT ANY WARRANTY; without even the implied warranty of 0015 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0016 Lesser General Public License for more details. 0017 0018 You should have received a copy of the GNU Lesser General Public 0019 License along with this library. If not, see <http://www.gnu.org/licenses/>. 0020 0021 */ 0022 0023 #ifndef LOCKFREEQUEUE_P_H 0024 #define LOCKFREEQUEUE_P_H 0025 0026 #include <QVector> 0027 0028 class LockFreeQueueBasePrivate; 0029 struct MemoryPool; 0030 class LockFreeQueueBase 0031 { 0032 friend class LockFreeQueueBasePrivate; 0033 public: 0034 struct DataReadyHandler 0035 { 0036 virtual ~DataReadyHandler() {} 0037 virtual void dataReady() = 0; 0038 }; 0039 0040 void setDataReadyHandler(DataReadyHandler *); 0041 0042 int size() const; 0043 bool isEmpty() const { return 0 == size(); } 0044 0045 protected: 0046 friend struct MemoryPool; 0047 LockFreeQueueBase(); 0048 ~LockFreeQueueBase(); 0049 0050 public: 0051 class NodeBase; 0052 typedef volatile NodeBase * NodeBasePointer; 0053 class NodeBase 0054 { 0055 public: 0056 inline NodeBase(int p) : priority(p) {} 0057 inline NodeBase(NodeBase *n) : next(n), priority(0) {} 0058 NodeBasePointer next; 0059 int priority; 0060 0061 inline void ref() { refCount.ref(); } 0062 inline void deref() { if (!refCount.deref()) delete this; } 0063 0064 protected: 0065 ~NodeBase() { Q_ASSERT(refCount == 0); } 0066 private: 0067 QAtomicInt refCount; 0068 }; 0069 0070 struct NodeBaseKeepNodePool : public NodeBase 0071 { 0072 inline NodeBaseKeepNodePool(int priority) : NodeBase(priority) {} 0073 // allocation is a bottleneck in _enqueue 0074 void *operator new(size_t s); 0075 void operator delete(void *p, size_t s); 0076 0077 static void clear(); 0078 static void setPoolSize(int); 0079 static int poolSize(); 0080 }; 0081 0082 typedef NodeBase StdNewDeleteMemoryManagement; 0083 typedef NodeBaseKeepNodePool KeepNodePoolMemoryManagement; 0084 protected: 0085 0086 void _enqueue(NodeBase *); 0087 NodeBase *_acquireHeadNode(); 0088 NodeBase *_acquireHeadNodeBlocking(); 0089 0090 LockFreeQueueBasePrivate *const d; 0091 0092 }; 0093 0094 template<class T, class MemoryManagementNodeBase = LockFreeQueueBase::StdNewDeleteMemoryManagement> 0095 class LockFreeQueue : public LockFreeQueueBase 0096 { 0097 public: 0098 enum BlockingSwitch { 0099 BlockUnlessEmpty, 0100 NeverBlock 0101 }; 0102 0103 struct Node : public MemoryManagementNodeBase 0104 { 0105 inline Node(const T &d, int priority) : MemoryManagementNodeBase(priority), data(d) {} 0106 T data; 0107 }; 0108 0109 inline void enqueue(const T &data, int priority = 0) 0110 { 0111 _enqueue(new Node(data, 0)); 0112 } 0113 0114 inline void dequeue(QVector<T> &data, BlockingSwitch block = BlockUnlessEmpty) 0115 { 0116 int count = 0; 0117 while (count < data.capacity()) { 0118 NodeBase *node = (block == NeverBlock) ? _acquireHeadNode() : _acquireHeadNodeBlocking(); 0119 if (!node) { 0120 break; 0121 } 0122 if (count < data.size()) { 0123 data[count] = static_cast<Node *>(node)->data; 0124 } else { 0125 data << static_cast<Node *>(node)->data; 0126 } 0127 ++count; 0128 node->deref(); 0129 } 0130 data.resize(count); 0131 } 0132 0133 inline bool dequeue(T *data, BlockingSwitch block = BlockUnlessEmpty) 0134 { 0135 NodeBase *node = (block == NeverBlock) ? _acquireHeadNode() : _acquireHeadNodeBlocking(); 0136 if (node) { 0137 *data = static_cast<Node *>(node)->data; 0138 node->deref(); 0139 return true; 0140 } 0141 return false; 0142 } 0143 0144 inline LockFreeQueue<T> &operator<<(const T &data) { enqueue(data); return *this; } 0145 inline LockFreeQueue<T> &operator>>(T &data) 0146 { 0147 NodeBase *node = _acquireHeadNodeBlocking(); 0148 if (node) { 0149 data = static_cast<Node *>(node)->data; 0150 node->deref(); 0151 } 0152 return *this; 0153 } 0154 }; 0155 0156 #endif // LOCKFREEQUEUE_P_H