NaiveStack.cs

using System.Runtime.InteropServices;
using System.Threading;

namespace Foo
{
    /// <summary>
    /// Naive SPMC stack.
    /// </summary>
    public class NaiveStack
    {
        private readonly int[] _items;
        private VersionAndPosition _versionAndPosition;

        public NaiveStack(int capacity)
        {
            _items = new int[capacity];
        }

        public bool TryPush(int value)
        {
            var versionAndPosition = new VersionAndPosition();
            while (true)
            {
                var originalVersionAndPosition = Volatile.Read(ref _versionAndPosition.Value);

                versionAndPosition.Value = originalVersionAndPosition;
                if (versionAndPosition.Position == _items.Length)
                    return false;

                // single producer => the CompareExchange can only fail if the position is decremented by a consumer
                //                 => the value can be safely writen in the item array

                _items[versionAndPosition.Position] = value;

                versionAndPosition.Position++;
                versionAndPosition.Version++;

                if (Interlocked.CompareExchange(ref _versionAndPosition.Value, versionAndPosition.Value, originalVersionAndPosition) == originalVersionAndPosition)
                    return true;
            }
        }

        public bool TryPop(out int value)
        {
            var versionAndPosition = new VersionAndPosition();
            while (true)
            {
                var originalVersionAndPosition = Volatile.Read(ref _versionAndPosition.Value);

                versionAndPosition.Value = originalVersionAndPosition;
                if (versionAndPosition.Position == 0)
                {
                    value = 0;
                    return false;
                }

                versionAndPosition.Position--;
                versionAndPosition.Version++;

                // reads a value after loading _versionAndPosition
                var readValue = _items[versionAndPosition.Position];

                if (Interlocked.CompareExchange(ref _versionAndPosition.Value, versionAndPosition.Value, originalVersionAndPosition) == originalVersionAndPosition)
                {
                    // CompareExchange succeeded => the read value matches the version and position
                    value = readValue;
                    return true;
                }
            }
        }

        [StructLayout(LayoutKind.Explicit)]
        private struct VersionAndPosition
        {
            [FieldOffset(0)]
            public int Version;
            [FieldOffset(4)]
            public int Position;
            [FieldOffset(0)]
            public long Value;
        }
    }
}