156 this->capacity = size;
157 this->storage.Resize(size);
160 Node* prev =
nullptr;
161 for (
IndexT i = 0; i < this->storage.Size(); i++)
164 prev->
next = &this->storage[i];
165 prev = &this->storage[i];
167 this->freeHead = this->storage.Begin();
168 this->freeTail = this->storage.End() - 1;
183 Node* newNode = this->Alloc();
184 newNode->
data = item;
185 newNode->
next =
nullptr;
187 Node* oldTail =
nullptr;
190 oldTail = this->tail;
192 if (CompareAndSwap(&this->tail, oldTail, newNode))
196 if (oldTail !=
nullptr)
197 oldTail->
next = newNode;
200 CompareAndSwap(&this->head,
nullptr, newNode);
201 CompareAndSwap(&this->tail,
nullptr, newNode);
215 oldHead = this->head;
216 if (oldHead ==
nullptr)
219 newHead = oldHead->
next;
220 if (CompareAndSwap(&this->head, oldHead, newHead))
225 oldHead->
next =
nullptr;
228 item = oldHead->
data;
231 this->Dealloc(oldHead);
256 return this->size == 0;
267 Node* oldHead =
nullptr;
268 Node* newHead =
nullptr;
271 oldHead = this->freeHead;
272 if (oldHead ==
nullptr)
274 newHead = oldHead->
next;
276 if (CompareAndSwap(&this->freeHead, oldHead, newHead))
281 oldHead->
next =
nullptr;
295 Node* oldTail =
nullptr;
298 oldTail = this->freeTail;
300 if (CompareAndSwap(&this->freeTail, oldTail, node))
304 if (oldTail !=
nullptr)
305 oldTail->
next = node;
308 CompareAndSwap(&this->freeHead,
nullptr, node);
309 CompareAndSwap(&this->freeTail,
nullptr, node);
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