|
|
using System.Threading;
|
|
|
using System.Collections.Generic;
|
|
|
using System;
|
|
|
using System.Collections;
|
|
|
|
|
|
namespace Implab.Parallels {
|
|
|
public class SimpleAsyncQueue<T> : IEnumerable<T> {
|
|
|
class Node {
|
|
|
public Node(T value) {
|
|
|
this.value = value;
|
|
|
}
|
|
|
public readonly T value;
|
|
|
public volatile Node next;
|
|
|
}
|
|
|
|
|
|
// the reader and the writer are mainteined completely independent,
|
|
|
// the reader can read next item when m_first.next is not null
|
|
|
// the writer creates a new node, moves m_last to this node and
|
|
|
// only after that restores the reference from the previous node
|
|
|
// making the reader be able to read the new node.
|
|
|
|
|
|
volatile Node m_first; // position on the node which is already read
|
|
|
volatile Node m_last; // position on the node which is already written
|
|
|
|
|
|
public SimpleAsyncQueue() {
|
|
|
m_first = m_last = new Node(default(T));
|
|
|
}
|
|
|
|
|
|
public void Enqueue(T value) {
|
|
|
var next = new Node(value);
|
|
|
|
|
|
// Interlocaked.CompareExchange implies Thread.MemoryBarrier();
|
|
|
// to ensure that the next node is completely constructed
|
|
|
var last = Interlocked.Exchange(ref m_last, next);
|
|
|
|
|
|
// release-fence
|
|
|
last.next = next;
|
|
|
|
|
|
}
|
|
|
|
|
|
public bool TryDequeue(out T value) {
|
|
|
Node first = m_first; ;
|
|
|
Node next = first.next; ;
|
|
|
|
|
|
if (next == null) {
|
|
|
value = default(T);
|
|
|
return false;
|
|
|
}
|
|
|
|
|
|
var first2 = Interlocked.CompareExchange(ref m_first, next, first);
|
|
|
|
|
|
if (first != first2) {
|
|
|
// head is updated by someone else
|
|
|
|
|
|
SpinWait spin = new SpinWait();
|
|
|
do {
|
|
|
first = first2;
|
|
|
next = first.next;
|
|
|
if (next == null) {
|
|
|
value = default(T);
|
|
|
return false;
|
|
|
}
|
|
|
|
|
|
first2 = Interlocked.CompareExchange(ref m_first, next, first);
|
|
|
if (first == first2)
|
|
|
break;
|
|
|
spin.SpinOnce();
|
|
|
} while (true);
|
|
|
}
|
|
|
|
|
|
value = next.value;
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
#region IEnumerable implementation
|
|
|
|
|
|
class Enumerator : IEnumerator<T> {
|
|
|
Node m_current;
|
|
|
Node m_first;
|
|
|
|
|
|
public Enumerator(Node first) {
|
|
|
m_first = first;
|
|
|
}
|
|
|
|
|
|
#region IEnumerator implementation
|
|
|
|
|
|
public bool MoveNext() {
|
|
|
m_current = m_current == null ? m_first : m_current.next;
|
|
|
return m_current != null;
|
|
|
}
|
|
|
|
|
|
public void Reset() {
|
|
|
m_current = null;
|
|
|
}
|
|
|
|
|
|
object IEnumerator.Current {
|
|
|
get {
|
|
|
if (m_current == null)
|
|
|
throw new InvalidOperationException();
|
|
|
return m_current.value;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
#endregion
|
|
|
|
|
|
#region IDisposable implementation
|
|
|
|
|
|
public void Dispose() {
|
|
|
}
|
|
|
|
|
|
#endregion
|
|
|
|
|
|
#region IEnumerator implementation
|
|
|
|
|
|
public T Current {
|
|
|
get {
|
|
|
if (m_current == null)
|
|
|
throw new InvalidOperationException();
|
|
|
return m_current.value;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
#endregion
|
|
|
}
|
|
|
|
|
|
public IEnumerator<T> GetEnumerator() {
|
|
|
return new Enumerator(m_first);
|
|
|
}
|
|
|
|
|
|
#endregion
|
|
|
|
|
|
#region IEnumerable implementation
|
|
|
|
|
|
IEnumerator IEnumerable.GetEnumerator() {
|
|
|
return GetEnumerator();
|
|
|
}
|
|
|
|
|
|
#endregion
|
|
|
}
|
|
|
}
|
|
|
|
