public class CountdownLatch {
    private int m_remain;
    private EventWaitHandle m_event;

    public CountdownLatch(int count) {
        m_remain = count;
        m_event = new ManualResetEvent(false);
    }

    public void Signal() {
        // The last thread to signal also sets the event.
        if (Interlocked.Decrement(ref m_remain) == 0)
            m_event.Set();
    }

    public void Wait() {
        m_event.WaitOne();
    }
}

public struct SpinWait {
    private int m_count;
    private static readonly bool s_isSingleProc =
        (Environment.ProcessorCount == 1);
    private const int s_yieldFrequency = 4000;
    private const int s_yieldOneFrequency = 3*s_yieldFrequency;

    public int Spin() {
        int oldCount = m_count;

        // On a single-CPU machine, we ensure our counter is always
        // a multiple of ‘s_yieldFrequency’, so we yield every time.
        // Else, we just increment by one.
        m_count += (s_isSingleProc ? s_yieldFrequency : 1);

        // If not a multiple of ‘s_yieldFrequency’ spin (w/ backoff).
        int countModFrequency = m_count % s_yieldFrequency;
        if (countModFrequency > 0)
            Thread.SpinWait((int)(1 + (countModFrequency * 0.05f)));
        else
            Thread.Sleep(m_count <= s_yieldOneFrequency ? 0 : 1);

        return oldCount;
    }

    private void Yield() {
        Thread.Sleep(m_count < s_yieldOneFrequency ? 0 : 1);
    }
}

using System;
using System.Threading;

public class Barrier {
    private volatile int m_count;
    private int m_originalCount;
    private EventWaitHandle m_oddEvent;
    private EventWaitHandle m_evenEvent;
    private volatile bool m_sense = false; // false==even, true==odd.

    public Barrier(int count) {
        m_count = count;
        m_originalCount = count;
        m_oddEvent = new ManualResetEvent(false);
        m_evenEvent = new ManualResetEvent(false);
    }

    public void Await() {
        bool sense = m_sense;

        // The last thread to signal also sets the event.
        if (m_count == 1 || Interlocked.Decrement(ref m_count) == 0) {
            m_count = m_originalCount;
            m_sense = !sense; // Reverse the sense.
            if (sense == true) { // odd
                m_evenEvent.Reset();
                m_oddEvent.Set();
             } else { // even
                m_oddEvent.Reset();
                m_evenEvent.Set();

            }
        } else {
            if (sense == true) m_oddEvent.WaitOne();
            else               m_evenEvent.WaitOne();
        }

    }
}

public void Await() {
    bool sense = m_sense;

    // The last thread to signal also sets the event.
    if (m_count == 1 || Interlocked.Decrement(ref m_count) == 0) {
        m_count = m_originalCount;
        m_sense = !sense; // Reverse the sense.
        if (sense == true) { // odd
            m_evenEvent.Set();
            m_oddEvent.Reset();
        } else { // even
            m_oddEvent.Set();
            m_evenEvent.Reset();
        }
    } else {
        SpinWait s = new SpinWait();
        while (sense == m_sense) {
            if (s.Spin() >= s_spinCount) {
                if (sense == true) m_oddEvent.WaitOne();
                else               m_evenEvent.WaitOne();
            }
        }
    }
}

class Cell<T> {
    internal T m_obj;
    internal Cell(T obj) { m_obj = obj; }
}
 
public class BlockingQueue<T> {
    private Queue<Cell<T>> m_queue = new Queue<Cell<T>>();
    public void Enqueue(T obj) {
        Cell<T> c = new Cell<T>(obj);
        lock (m_queue) {
            m_queue.Enqueue(c);
            Monitor.Pulse(m_queue);
            Monitor.Wait(m_queue);
        }
    }
    public T Dequeue() {
        Cell<T> c;
        lock (m_queue) {
            while (m_queue.Count == 0)
                Monitor.Wait(m_queue);
            c = m_queue.Dequeue();
            Monitor.Pulse(m_queue);
        }
        return c.m_obj;
    }
}

public class BoundedBuffer<T> {
    private Queue<T> m_queue = new Queue<T>();
    private int m_consumersWaiting;
    private int m_producersWaiting;
    private const int s_maxBufferSize = 128;

    public void Enqueue(T obj) {
        lock (m_queue) {
            while (m_queue.Count == (s_maxBufferSize - 1)) {
                m_producersWaiting++;
                Monitor.Wait(m_queue);
                m_producersWaiting--;
            }
            m_queue.Enqueue(obj);
            if (m_consumersWaiting > 0)
                Monitor.PulseAll(m_queue);
        }
    }

    public T Dequeue() {
        T e;
        lock (m_queue) {
            while (m_queue.Count == 0) {
                m_consumersWaiting++;
                Monitor.Wait(m_queue);
                m_consumersWaiting--;
            }
            e = m_queue.Dequeue();
            if (m_producersWaiting > 0)
                Monitor.PulseAll(m_queue);
        }
        return e;
    }
}

public struct ThinEvent {
    private int m_state; // 0 means unset, 1 means set.
    private EventWaitHandle m_eventObj;
    private const int s_spinCount = 4000;

    public void Set() {
        m_state = 1;
        Thread.MemoryBarrier(); // required.
        if (m_eventObj != null)
            m_eventObj.Set();
    }

    public void Reset() {
        m_state = 0;
        if (m_eventObj != null)
            m_eventObj.Reset();
    }

    public void Wait() {
        SpinWait s = new SpinWait();
        while (m_state == 0) {
            if (s.Spin() >= s_spinCount) {
                if (m_eventObj == null) {
                    ManualResetEvent newEvent =
                        new ManualResetEvent(m_state == 1);
                    if (Interlocked.CompareExchange<EventWaitHandle>(
                            ref m_eventObj, newEvent, null) == null) {
                       // If someone set the flag before seeing the new
                       // event obj, we must ensure it’s been set.
                       if (m_state == 1)
                           m_eventObj.Set();
                    } else {
                        // Lost the race w/ another thread. Just use
                        // its event.
                        newEvent.Close();
                    }
                }
                m_eventObj.WaitOne();
            }
        }
    }
}

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

    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 || Interlocked.CompareExchange(
                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 || Interlocked.CompareExchange(
                    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; }
}