Following up on the previous post we are now going to modify the LocklessQueue<T> to allocate a class for an array of items rather than just a single item. Most of this work will be in the Item class itself with a few changes to the Enqueue method. Again we have to ensure that both the variables are written to by only one of the threads. Time for more code:

    class LocklessQueue<T>
    {
        class Item
        {
            public Item Next;
            int _pos, _count;
            readonly T[] _values;
            public Item(int capacity)
            {
                _pos = _count = 0;
                _values = new T[capacity];
                Next = null;
            }
            public bool IsValid { get { return _pos < _count; } }
            public bool PutValue(T value)
            {
                if (_count < _values.Length)
                {
                    _values[_count++] = value;
                    return true;
                }
                return false;
            }
            public T TakeValue()
            {
                int ix = _pos++;
                T value = _values[ix];
                _values[ix] = default(T);
                return value;
            }
        }

        readonly int _allocSize;
        Item _first;
        Item _last;

        public LocklessQueue(int allocSize)
        {
            _allocSize = Math.Max(1, allocSize);
            _first = _last = new Item(_allocSize);
        }

        public bool IsEmpty
        {
            get
            {
                while (!_first.IsValid && _first.Next != null)
                    _first = _first.Next;
                return false == _first.IsValid;
            }
        }

        public void Enqueue(T value)
        {
            if (!_last.PutValue(value))
            {
                Item i = new Item(_allocSize);
                i.PutValue(value);
                _last.Next = i;
                _last = i;
            }
        }

        public T Dequeue()
        {
            while (!_first.IsValid && _first.Next != null)
                _first = _first.Next;

            if (!_first.IsValid)
                throw new InvalidOperationException();//queue is empty

            return _first.TakeValue();
        }
    }
Comments