Testing a Non-blocking Queue
- by jsw
I've ported the non-blocking queue psuedocode here to C#. The code below is meant as a near verbatim copy of the paper.
What approach would you take to test the implementation?
Note: I'm running in VS2010 so I don't have CHESS support yet.
using System.Threading;
#pragma warning disable 0420
namespace ConcurrentCollections
{
class QueueNodePointer<T>
{
internal QueueNode<T> ptr;
internal QueueNodePointer() : this(null) { }
internal QueueNodePointer(QueueNode<T> ptr) { this.ptr = ptr; }
}
class QueueNode<T>
{
internal T value;
internal QueueNodePointer<T> next;
internal QueueNode() : this(default(T)) { }
internal QueueNode(T value) { this.value = value; this.next = new QueueNodePointer<T>(); }
}
public class ConcurrentQueue<T>
{
private volatile int count = 0;
private QueueNodePointer<T> qhead = new QueueNodePointer<T>();
private QueueNodePointer<T> qtail = new QueueNodePointer<T>();
public ConcurrentQueue()
{
var node = new QueueNode<T>();
node.next.ptr = null;
this.qhead.ptr = this.qtail.ptr = node;
}
public int Count { get { return this.count; } }
public void Enqueue(T value)
{
var node = new QueueNode<T>(value);
node.next.ptr = null;
QueueNodePointer<T> tail;
QueueNodePointer<T> next;
while (true)
{
tail = this.qtail;
next = tail.ptr.next;
if (tail == this.qtail)
{
if (next.ptr == null)
{
var newtail = new QueueNodePointer<T>(node);
if (Interlocked.CompareExchange(ref tail.ptr.next, newtail, next) == next)
{
Interlocked.Increment(ref this.count);
break;
}
else
{
Interlocked.CompareExchange(ref this.qtail, new QueueNodePointer<T>(next.ptr), tail);
}
}
}
}
Interlocked.CompareExchange(ref this.qtail, new QueueNodePointer<T>(node), tail);
}
public T Dequeue()
{
T value;
while (true)
{
var head = this.qhead;
var tail = this.qtail;
var next = head.ptr.next;
if (head == this.qhead)
{
if (head.ptr == tail.ptr)
{
if (next.ptr == null)
{
return default(T);
}
Interlocked.CompareExchange(ref this.qtail, new QueueNodePointer<T>(next.ptr), tail);
}
else
{
value = next.ptr.value;
var newhead = new QueueNodePointer<T>(next.ptr);
if (Interlocked.CompareExchange(ref this.qhead, newhead, head) == head)
{
Interlocked.Decrement(ref this.count);
break;
}
}
}
}
return value;
}
}
}
#pragma warning restore 0420
