using System.Collections.Generic;
using System.Threading;
namespace NetcodeIO.NET.Utils
{
public class SingleLinkNode
{
// Note; the Next member cannot be a property since
// it participates in many CAS operations
public SingleLinkNode Next;
public T Item;
}
public static class SyncMethods
{
public static bool CAS(ref T location, T comparand, T newValue) where T : class
{
return
(object)comparand ==
(object)Interlocked.CompareExchange(ref location, newValue, comparand);
}
}
public class LockFreeLinkPool
{
private SingleLinkNode head;
public LockFreeLinkPool()
{
head = new SingleLinkNode();
}
public void Push(SingleLinkNode newNode)
{
newNode.Item = default(T);
do
{
newNode.Next = head.Next;
} while (!SyncMethods.CAS>(ref head.Next, newNode.Next, newNode));
return;
}
public bool Pop(out SingleLinkNode node)
{
do
{
node = head.Next;
if (node == null)
{
return false;
}
} while (!SyncMethods.CAS>(ref head.Next, node, node.Next));
return true;
}
}
public class LockFreeQueue
{
SingleLinkNode head;
SingleLinkNode tail;
LockFreeLinkPool trash;
public LockFreeQueue()
{
head = new SingleLinkNode();
tail = head;
trash = new LockFreeLinkPool();
}
public void Enqueue(T item)
{
SingleLinkNode oldTail = null;
SingleLinkNode oldTailNext;
SingleLinkNode newNode;
if (!trash.Pop(out newNode))
{
newNode = new SingleLinkNode();
}
else {
newNode.Next = null;
}
newNode.Item = item;
bool newNodeWasAdded = false;
while (!newNodeWasAdded)
{
oldTail = tail;
oldTailNext = oldTail.Next;
if (tail == oldTail)
{
if (oldTailNext == null)
newNodeWasAdded = SyncMethods.CAS>(ref tail.Next, null, newNode);
else
SyncMethods.CAS>(ref tail, oldTail, oldTailNext);
}
}
SyncMethods.CAS>(ref tail, oldTail, newNode);
}
public bool Dequeue(out T item)
{
item = default(T);
SingleLinkNode oldHead = null;
bool haveAdvancedHead = false;
while (!haveAdvancedHead)
{
oldHead = head;
SingleLinkNode oldTail = tail;
SingleLinkNode oldHeadNext = oldHead.Next;
if (oldHead == head)
{
if (oldHead == oldTail)
{
if (oldHeadNext == null)
{
return false;
}
SyncMethods.CAS>(ref tail, oldTail, oldHeadNext);
}
else {
item = oldHeadNext.Item;
haveAdvancedHead = SyncMethods.CAS>(ref head, oldHead, oldHeadNext);
if (haveAdvancedHead)
{
trash.Push(oldHead);
}
}
}
}
return true;
}
}
}