Lock Free Stack Implementation in C#

This method compares destination to currentValue, and if they're equal sets destination to newValue and returns currentValue unchanged.

If they aren't equal it just returns the value of destination.

This is done in an atomic fashion i.e. no other thread can interrupt it.  In carrys out this in atomic fashion becasue its executed at hardware level with a single nstruction CMPXCH instruction.


public class LockFreeStack<T> {
    private volatile StackNode<T> m_head;

private static bool CAS(ref Node<T> destination, Node<T> currentValue, Node<T> newValue)
{
   return
         currentValue== Interlocked.CompareExchange<Node<T>>(ref destination, newValue, currentValue);
 }


    public void Push(T item) {
        StackNode<T> node = new StackNode<T>(item);
        StackNode<T> head;
        do {
            head = m_head;
            node.m_next = head;
        } while (m_head != head || CAS(ref m_head, node, head) != head);
    }

    public T Pop() {
        StackNode<T> head;
        SpinWait s = new SpinWait();

        while (true) {
            StackNode<T> next;
            do {
                head = m_head;
                if (head == null) goto emptySpin;
                next = head.m_next;
            } while (m_head != head || CAS(ref m_head, next, head) != head);
            break;

        emptySpin:
            s.Spin();
        }

        return head.m_value;
    }
}

class StackNode<T> {
    internal T m_value;
    internal StackNode<T> m_next;
    internal StackNode(T val) { m_value = val; }
}

Comments

Popular posts from this blog

Basic Send Message to MQ with Java and IBM MQ JMS

Basic Receive Message to MQ with Java and IBM MQ JMS

Creating a simple Alert / Success Message with ASP.NET/VB using Bootstrap