Nebula
Loading...
Searching...
No Matches
lockfreequeue.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
70//------------------------------------------------------------------------------
71#include "interlocked.h"
72#include "util/fixedarray.h"
73namespace Threading
74{
75
76template <class TYPE>
78{
79public:
84
86 void Resize(const SizeT size);
87
89 void Enqueue(const TYPE& item);
91 bool Dequeue(TYPE& item);
92
96 bool IsEmpty();
97
98private:
99
100 struct Node
101 {
102 TYPE data;
104
106 : data(TYPE())
107 , next(nullptr)
108 {};
109 };
110
113 volatile SizeT size;
114
116 Node* Alloc();
118 void Dealloc(Node* node);
119
121 bool CompareAndSwap(Node** currentValue, Node* expectValue, Node* newValue);
122
127};
128
129//------------------------------------------------------------------------------
132template<class TYPE>
133inline
135 : size(0)
136 , capacity(0)
137{
138}
139
140//------------------------------------------------------------------------------
143template<class TYPE>
144inline
148
149//------------------------------------------------------------------------------
152template<class TYPE>
153inline void
155{
156 this->capacity = size;
157 this->storage.Resize(size);
158
159 // setup free list
160 Node* prev = nullptr;
161 for (IndexT i = 0; i < this->storage.Size(); i++)
162 {
163 if (prev != nullptr)
164 prev->next = &this->storage[i];
165 prev = &this->storage[i];
166 }
167 this->freeHead = this->storage.Begin();
168 this->freeTail = this->storage.End() - 1;
169}
170
171//------------------------------------------------------------------------------
174template<class TYPE>
175inline void
177{
178 // increase size
179 int size = Interlocked::Increment(&this->size);
180 n_assert(size <= this->capacity);
181
182 // allocate a new node from storage
183 Node* newNode = this->Alloc();
184 newNode->data = item;
185 newNode->next = nullptr;
186
187 Node* oldTail = nullptr;
188 while (true)
189 {
190 oldTail = this->tail;
191
192 if (CompareAndSwap(&this->tail, oldTail, newNode))
193 break;
194 }
195
196 if (oldTail != nullptr)
197 oldTail->next = newNode;
198
199 // if head is null, set head to new node
200 CompareAndSwap(&this->head, nullptr, newNode);
201 CompareAndSwap(&this->tail, nullptr, newNode);
202}
203
204//------------------------------------------------------------------------------
207template<class TYPE>
208inline bool
210{
211 Node* oldHead;
212 Node* newHead;
213 while (true)
214 {
215 oldHead = this->head;
216 if (oldHead == nullptr)
217 return false;
218
219 newHead = oldHead->next;
220 if (CompareAndSwap(&this->head, oldHead, newHead))
221 break;
222 }
223
224 // set tail to nullptr if head became tail
225 oldHead->next = nullptr;
226
227 // copy return value here, if we dealloc and someone else allocs, they might have time to change the value
228 item = oldHead->data;
229
230 // make sure to return this node to the free list
231 this->Dealloc(oldHead);
232
233 int size = Interlocked::Decrement(&this->size);
234 n_assert(size >= 0);
235
236 return true;
237}
238
239//------------------------------------------------------------------------------
242template<class TYPE>
243inline SizeT
245{
246 return this->size;
247}
248
249//------------------------------------------------------------------------------
252template<class TYPE>
253inline bool
255{
256 return this->size == 0;
257}
258
259//------------------------------------------------------------------------------
263template<class TYPE>
264__forceinline typename LockFreeQueue<TYPE>::Node*
266{
267 Node* oldHead = nullptr;
268 Node* newHead = nullptr;
269 while (true)
270 {
271 oldHead = this->freeHead;
272 if (oldHead == nullptr)
273 continue;
274 newHead = oldHead->next;
275
276 if (CompareAndSwap(&this->freeHead, oldHead, newHead))
277 break;
278 }
279
280 n_assert(oldHead != nullptr);
281 oldHead->next = nullptr;
282
283 return oldHead;
284}
285
286//------------------------------------------------------------------------------
290template<class TYPE>
291__forceinline void
293{
294 n_assert(node != nullptr);
295 Node* oldTail = nullptr;
296 while (true)
297 {
298 oldTail = this->freeTail;
299
300 if (CompareAndSwap(&this->freeTail, oldTail, node))
301 break;
302 }
303
304 if (oldTail != nullptr)
305 oldTail->next = node;
306
307 // if null, set both iterators to the same node
308 CompareAndSwap(&this->freeHead, nullptr, node);
309 CompareAndSwap(&this->freeTail, nullptr, node);
310}
311
312//------------------------------------------------------------------------------
315template<class TYPE>
316inline bool
317LockFreeQueue<TYPE>::CompareAndSwap(Node** currentValue, Node* expectValue, Node* newValue)
318{
319 return Interlocked::CompareExchangePointer((void* volatile*)currentValue, (void*)newValue, (void*)expectValue) == expectValue;
320}
321
322} // namespace Threading
Definition lockfreequeue.h:78
Util::FixedArray< Node > storage
Definition lockfreequeue.h:125
volatile SizeT size
Definition lockfreequeue.h:113
SizeT capacity
Definition lockfreequeue.h:126
void Enqueue(const TYPE &item)
enqueue item
Definition lockfreequeue.h:176
bool Dequeue(TYPE &item)
dequeue item
Definition lockfreequeue.h:209
bool CompareAndSwap(Node **currentValue, Node *expectValue, Node *newValue)
does a compare-and-swap
Definition lockfreequeue.h:317
void Dealloc(Node *node)
deallocs a node and puts it back into storage
Definition lockfreequeue.h:292
~LockFreeQueue()
destructor
Definition lockfreequeue.h:145
SizeT Size()
get size
Definition lockfreequeue.h:244
Node * head
Definition lockfreequeue.h:111
Node * freeTail
Definition lockfreequeue.h:124
LockFreeQueue()
constructor
Definition lockfreequeue.h:134
Node * Alloc()
allocates a new node from the storage
Definition lockfreequeue.h:265
Node * freeHead
Definition lockfreequeue.h:123
bool IsEmpty()
returns true if empty
Definition lockfreequeue.h:254
Node * tail
Definition lockfreequeue.h:112
void Resize(const SizeT size)
resizes the queue to hold N elements
Definition lockfreequeue.h:154
Implements a fixed size one-dimensional array.
Definition fixedarray.h:20
#define n_assert(exp)
Definition debug.h:50
int Decrement(int volatile *var)
interlocked decrement, return result
Definition gccinterlocked.cc:157
int Increment(int volatile *var)
interlocked increment, return result
Definition gccinterlocked.cc:148
void * CompareExchangePointer(void *volatile *dest, void *exchange, void *comparand)
interlocked compare-exchange pointer
Definition gccinterlocked.cc:139
The Jobs2 system provides a set of threads and a pool of jobs from which threads can pickup work.
Definition jobs2.h:16
Definition lockfreequeue.h:101
Node * next
Definition lockfreequeue.h:103
Node()
Definition lockfreequeue.h:105
TYPE data
Definition lockfreequeue.h:102
int SizeT
Definition types.h:49
int IndexT
Definition types.h:48