C# LockFreeStack类

LockFreeStack

SpinWait

/// <summary>
    /// SpinWait只有在SMP或多核CPU下才具有使用意义。在单处理器下，旋转非常浪费CPU时间，没有任何意义。
    /// 自旋锁特性导致其比较适用一些轻量级，极短时间的多核cpu系统上的锁保护。
    /// </summary>
    public struct SpinWait
    {
        public static readonly bool IsSingleProcessor;
        private const int yieldFrequency = 4000;
        private const int yieldOneFrequency = 3 * yieldFrequency;

        static SpinWait()
        {
            IsSingleProcessor = (Environment.ProcessorCount == 1);
        }

        private int count;

        public int Count
        {
            get { return count; }
        }

        public int Spin()
        {
            int oldCount = 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.
            count += (IsSingleProcessor ? yieldFrequency : 1);
            // If not a multiple of �s_yieldFrequency� spin (w/ backoff).
            int countModFrequency = count % yieldFrequency;
            if (countModFrequency > 0)
            {
                Thread.SpinWait((int)(1 + (countModFrequency * 0.05f)));
            }
            else
            {
                Thread.Sleep(count <= yieldOneFrequency ? 0 : 1);
            }
            return oldCount;
        }

        public void Yield()
        {
            Thread.Sleep(count < yieldOneFrequency ? 0 : 1);
        }

        public void Reset()
        {
            count = 0;
        }
    }

public class LockFreeStack : IEnumerable
    {
        private class SingleLinkedNode
        {
            public object Value;
            public SingleLinkedNode Next;
        }

        private SingleLinkedNode m_head;
        private int count;

        public int Count
        {
            get { return count; }
        }

        public void Push(object item)
        {
            SingleLinkedNode node = new SingleLinkedNode();
            node.Value = item;
            SingleLinkedNode head;
            do
            {
                head = m_head;
                node.Next = head;
            }
            while (m_head != head || Interlocked.CompareExchange(ref m_head, node, head) != head);
            Interlocked.Increment(ref count);
        }

        public object Peek()
        {
            SingleLinkedNode head = m_head;
            if (head == null)
            {
                throw new InvalidOperationException("Stack Empty!");
            }
            return head.Value;
        }

        public object Pop()
        {
            object result;
            if (TryPop(out result))
            {
                return result;
            }
            throw new InvalidOperationException("Stack Empty!");
        }

        /// <summary>
        /// 考虑到在多线程环境中，这里不抛出异常。我们需要人为判断其是否为空，即 !TryPop() or result != null
        /// </summary>
        /// <returns></returns>
        public bool TryPop(out object item)
        {
            SingleLinkedNode head;
            SingleLinkedNode next;
            do
            {
                head = m_head;
                if (head == null)
                {
                    item = null;
                    return false;
                }
                next = m_head.Next;
            }
            while (Interlocked.CompareExchange(ref m_head, next, head) != head);
            Interlocked.Decrement(ref count);
            item = head.Value;
            return true;
        }

        public object SpinPop()
        {
            SingleLinkedNode head;
            SpinWait spin = new SpinWait();
            while (true)
            {
                SingleLinkedNode next;
                do
                {
                    head = m_head;
                    if (head == null)
                    {
                        goto emptySpin;
                    }
                    next = head.Next;
                }
                while (m_head != head || Interlocked.CompareExchange(ref m_head, next, head) != head);
                break;
            emptySpin:
                spin.Spin();
            }
            Interlocked.Decrement(ref count);
            return head.Value;
        }

        public bool Contains(object item)
        {
            SingleLinkedNode head = m_head;
            while (m_head != null && head != null)
            {
                if (head.Value.Equals(item))
                {
                    return true;
                }
                head = head.Next;
            }
            return false;
        }

        public void Clear()
        {
            Interlocked.Exchange(ref m_head, null);
            Interlocked.Exchange(ref count, 0);
        }

        public IEnumerator GetEnumerator()
        {
            SingleLinkedNode head = m_head;
            while (m_head != null && head != null)
            {
                yield return head.Value;
                head = head.Next;
            }
        }
    }