ConcurrentStack.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / clr / src / BCL / System / Collections / Concurrent / ConcurrentStack.cs / 1305376 / ConcurrentStack.cs

                            #pragma warning disable 0420 

// ==++==
//
//   Copyright (c) Microsoft Corporation.  All rights reserved. 
//
// ==--== 
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ 
//
// ConcurrentStack.cs 
//
// [....]
//
// A lock-free, concurrent stack primitive, and its associated debugger view type. 
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- 
 
using System;
using System.Collections; 
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.Runtime.ConstrainedExecution; 
using System.Runtime.Serialization;
using System.Security; 
using System.Security.Permissions; 
using System.Threading;
 
namespace System.Collections.Concurrent
{
    // A stack that uses CAS operations internally to maintain thread-safety in a lock-free
    // manner. Attempting to push or pop concurrently from the stack will not trigger waiting, 
    // although some optimistic concurrency and retry is used, possibly leading to lack of
    // fairness and/or livelock. The stack uses spinning and backoff to add some randomization, 
    // in hopes of statistically decreasing the possibility of livelock. 
    //
    // Note that we currently allocate a new node on every push. This avoids having to worry 
    // about potential ABA issues, since the CLR GC ensures that a memory address cannot be
    // reused before all references to it have died.

    ///  
    /// Represents a thread-safe last-in, first-out collection of objects.
    ///  
    /// Specifies the type of elements in the stack. 
    /// 
    /// All public and protected members of  are thread-safe and may be used 
    /// concurrently from multiple threads.
    /// 
    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(typeof(SystemCollectionsConcurrent_ProducerConsumerCollectionDebugView<>))] 
    [HostProtection(Synchronization = true, ExternalThreading = true)]
    [Serializable] 
    public class ConcurrentStack : IProducerConsumerCollection 
    {
        ///  
        /// A simple (internal) node type used to store elements of concurrent stacks and queues.
        /// 
        private class Node
        { 
            internal T m_value; // Value of the node.
            internal Node m_next; // Next pointer. 
 
            /// 
            /// Constructs a new node with the specified value and no next node. 
            /// 
            /// The value of the node.
            internal Node(T value)
            { 
                m_value = value;
                m_next = null; 
            } 
        }
 
        [NonSerialized]
        private volatile Node m_head; // The stack is a singly linked list, and only remembers the head.

        private T[] m_serializationArray; // Used for custom serialization. 

        private const int BACKOFF_MAX_YIELDS = 8; // Arbitrary number to cap backoff. 
 
        /// 
        /// Initializes a new instance of the  
        /// class.
        /// 
        public ConcurrentStack()
        { 
        }
 
        ///  
        /// Initializes a new instance of the 
        /// class that contains elements copied from the specified collection 
        /// 
        /// The collection whose elements are copied to the new .
        /// The  argument is 
        /// null.
        public ConcurrentStack(IEnumerable collection) 
        { 
            if (collection == null)
            { 
                throw new ArgumentNullException("collection");
            }
            InitializeFromCollection(collection);
        } 

        ///  
        /// Initializes the contents of the stack from an existing collection. 
        /// 
        /// A collection from which to copy elements. 
        private void InitializeFromCollection(IEnumerable collection)
        {
            // We just copy the contents of the collection to our stack.
            Node lastNode = null; 
            foreach (T element in collection)
            { 
                Node newNode = new Node(element); 
                newNode.m_next = lastNode;
                lastNode = newNode; 
            }

            m_head = lastNode;
        } 

        ///  
        /// Get the data array to be serialized 
        /// 
        [OnSerializing] 
        private void OnSerializing(StreamingContext context)
        {
            // save the data into the serialization array to be saved
            m_serializationArray = ToArray(); 
        }
 
        ///  
        /// Construct the stack from a previously seiralized one
        ///  
        [OnDeserialized]
        private void OnDeserialized(StreamingContext context)
        {
            Contract.Assert(m_serializationArray != null); 
            // Add the elements to our stack.  We need to add them from head-to-tail, to
            // preserve the original ordering of the stack before serialization. 
            Node prevNode = null; 
            Node head = null;
            for (int i = 0; i < m_serializationArray.Length; i++) 
            {
                Node currNode = new Node(m_serializationArray[i]);

                if (prevNode == null) 
                {
                    head = currNode; 
                } 
                else
                { 
                    prevNode.m_next = currNode;
                }

                prevNode = currNode; 
            }
 
            m_head = head; 
            m_serializationArray = null;
        } 


        /// 
        /// Gets a value that indicates whether the  is empty. 
        /// 
        /// true if the  is empty; otherwise, false. 
        ///  
        /// For determining whether the collection contains any items, use of this property is recommended
        /// rather than retrieving the number of items from the  property and comparing it 
        /// to 0.  However, as this collection is intended to be accessed concurrently, it may be the case
        /// that another thread will modify the collection after  returns, thus invalidating
        /// the result.
        ///  
        public bool IsEmpty
        { 
            // Checks whether the stack is empty. Clearly the answer may be out of date even prior to 
            // the function returning (i.e. if another thread concurrently adds to the stack). It does
            // guarantee, however, that, if another thread does not mutate the stack, a subsequent call 
            // to TryPop will return true -- i.e. it will also read the stack as non-empty.
            get { return m_head == null; }
        }
 
        /// 
        /// Gets the number of elements contained in the . 
        ///  
        /// The number of elements contained in the .
        ///  
        /// For determining whether the collection contains any items, use of the 
        /// property is recommended rather than retrieving the number of items from the 
        /// property and comparing it to 0.
        ///  
        public int Count
        { 
            // Counts the number of entries in the stack. This is an O(n) operation. The answer may be out 
            // of date before returning, but guarantees to return a count that was once valid. Conceptually,
            // the implementation snaps a copy of the list and then counts the entries, though physically 
            // this is not what actually happens.
            get
            {
                int count = 0; 

                // Just whip through the list and tally up the number of nodes. We rely on the fact that 
                // node next pointers are immutable after being enqueued for the first time, even as 
                // they are being dequeued. If we ever changed this (e.g. to pool nodes somehow),
                // we'd need to revisit this implementation. 

                for (Node curr = m_head; curr != null; curr = curr.m_next)
                {
                    count++; //we don't handle overflow, to be consistent with existing generic collection types in CLR 
                }
 
                return count; 
            }
        } 


        /// 
        /// Gets a value indicating whether access to the  is 
        /// synchronized with the SyncRoot.
        ///  
        /// true if access to the  is synchronized 
        /// with the SyncRoot; otherwise, false. For , this property always
        /// returns false. 
        bool ICollection.IsSynchronized
        {
            // Gets a value indicating whether access to this collection is synchronized. Always returns
            // false. The reason is subtle. While access is in face thread safe, it's not the case that 
            // locking on the SyncRoot would have prevented concurrent pushes and pops, as this property
            // would typically indicate; that's because we internally use CAS operations vs. true locks. 
            get { return false; } 
        }
 
        /// 
        /// Gets an object that can be used to synchronize access to the . This property is not supported.
        ///  
        /// The SyncRoot property is not supported
        object ICollection.SyncRoot 
        { 
            get
            { 
                throw new NotSupportedException(Environment.GetResourceString("ConcurrentCollection_SyncRoot_NotSupported"));
            }
        }
 
        /// 
        /// Removes all objects from the . 
        ///  
        public void Clear()
        { 
            // Clear the list by setting the head to null. We don't need to use an atomic
            // operation for this: anybody who is mutating the head by pushing or popping
            // will need to use an atomic operation to guarantee they serialize and don't
            // overwrite our setting of the head to null. 
            m_head = null;
        } 
 
        /// 
        /// Copies the elements of the  to an , starting at a particular
        ///  index.
        /// 
        /// The one-dimensional  that is the destination of 
        /// the elements copied from the
        /// . The  must 
        /// have zero-based indexing. 
        /// The zero-based index in  at which copying
        /// begins. 
        ///  is a null reference (Nothing in
        /// Visual Basic).
        ///  is less than
        /// zero. 
        /// 
        ///  is multidimensional. -or- 
        ///  does not have zero-based indexing. -or- 
        ///  is equal to or greater than the length of the 
        /// -or- The number of elements in the source  is 
        /// greater than the available space from  to the end of the destination
        /// . -or- The type of the source  cannot be cast automatically to the type of the
        /// destination . 
        /// 
        void ICollection.CopyTo(Array array, int index) 
        { 
            // Validate arguments.
            if (array == null) 
            {
                throw new ArgumentNullException("array");
            }
 
            // We must be careful not to corrupt the array, so we will first accumulate an
            // internal list of elements that we will then copy to the array. This requires 
            // some extra allocation, but is necessary since we don't know up front whether 
            // the array is sufficiently large to hold the stack's contents.
            ((ICollection)ToList()).CopyTo(array, index); 
        }

        /// 
        /// Copies the  elements to an existing one-dimensional , starting at the specified array index.
        ///  
        /// The one-dimensional  that is the destination of 
        /// the elements copied from the
        /// . The  must have zero-based 
        /// indexing.
        /// The zero-based index in  at which copying
        /// begins.
        ///  is a null reference (Nothing in 
        /// Visual Basic).
        ///  is less than 
        /// zero. 
        ///  is equal to or greater than the
        /// length of the  
        /// -or- The number of elements in the source  is greater than the
        /// available space from  to the end of the destination .
        ///  
        public void CopyTo(T[] array, int index)
        { 
            if (array == null) 
            {
                throw new ArgumentNullException("array"); 
            }

            // We must be careful not to corrupt the array, so we will first accumulate an
            // internal list of elements that we will then copy to the array. This requires 
            // some extra allocation, but is necessary since we don't know up front whether
            // the array is sufficiently large to hold the stack's contents. 
            ToList().CopyTo(array, index); 
        }
 

        /// 
        /// Inserts an object at the top of the .
        ///  
        /// The object to push onto the . The value can be
        /// a null reference (Nothing in Visual Basic) for reference types. 
        ///  
        public void Push(T item)
        { 
            // Pushes a node onto the front of the stack thread-safely. Internally, this simply
            // swaps the current head pointer using a (thread safe) CAS operation to accomplish
            // lock freedom. If the CAS fails, we add some back off to statistically decrease
            // contention at the head, and then go back around and retry. 

            Node newNode = new Node(item); 
            newNode.m_next = m_head; 
            if (Interlocked.CompareExchange(ref m_head, newNode, newNode.m_next) == newNode.m_next)
            { 
                return;
            }

            // If we failed, go to the slow path and loop around until we succeed. 
            PushCore(newNode, newNode);
        } 
 
        /// 
        /// Inserts multiple objects at the top of the  atomically. 
        /// 
        /// The objects to push onto the .
        ///  is a null reference
        /// (Nothing in Visual Basic). 
        /// 
        /// When adding multiple items to the stack, using PushRange is a more efficient 
        /// mechanism than using  one item at a time.  Additionally, PushRange 
        /// guarantees that all of the elements will be added atomically, meaning that no other threads will
        /// be able to inject elements between the elements being pushed.  Items at lower indices in 
        /// the  array will be pushed before items at higher indices.
        /// 
        public void PushRange(T[] items)
        { 
            if (items == null)
            { 
                throw new ArgumentNullException("items"); 
            }
            PushRange(items, 0, items.Length); 
        }

        /// 
        /// Inserts multiple objects at the top of the  atomically. 
        /// 
        /// The objects to push onto the . 
        /// The zero-based offset in  at which to begin 
        /// inserting elements onto the top of the .
        /// The number of elements to be inserted onto the top of the .
        ///  is a null reference
        /// (Nothing in Visual Basic).
        ///  or  is negative. Or  is greater than or equal to the length
        /// of . 
        ///  +  is 
        /// greater than the length of .
        ///  
        /// When adding multiple items to the stack, using PushRange is a more efficient
        /// mechanism than using  one item at a time. Additionally, PushRange
        /// guarantees that all of the elements will be added atomically, meaning that no other threads will
        /// be able to inject elements between the elements being pushed. Items at lower indices in the 
        ///  array will be pushed before items at higher indices.
        ///  
        public void PushRange(T[] items, int startIndex, int count) 
        {
            ValidatePushPopRangeInput(items, startIndex, count); 

            // No op if the count is zero
            if (count == 0)
                return; 

 
            Node head, tail; 
            head = tail = new Node(items[startIndex]);
            for (int i = startIndex + 1; i < startIndex + count; i++) 
            {
                Node node = new Node(items[i]);
                node.m_next = head;
                head = node; 
            }
 
            tail.m_next = m_head; 
            if (Interlocked.CompareExchange(ref m_head, head, tail.m_next) == tail.m_next)
            { 
                return;
            }

            // If we failed, go to the slow path and loop around until we succeed. 
            PushCore(head, tail);
 
        } 

 
        /// 
        /// Push one or many nodes into the stack, if head and tails are equal then push one node to the stack other wise push the list between head
        /// and tail to the stack
        ///  
        /// The head pointer to the new list
        /// The tail pointer to the new list 
        private void PushCore(Node head, Node tail) 
        {
            SpinWait spin = new SpinWait(); 

            // Keep trying to CAS the exising head with the new node until we succeed.
            do
            { 
                spin.SpinOnce();
                // Reread the head and link our new node. 
                tail.m_next = m_head; 
            }
            while (Interlocked.CompareExchange( 
                ref m_head, head, tail.m_next) != tail.m_next);

#if !FEATURE_PAL
            if (CDSCollectionETWBCLProvider.Log.IsEnabled()) 
            {
                CDSCollectionETWBCLProvider.Log.ConcurrentStack_FastPushFailed(spin.Count); 
            } 
#endif //!FEATURE_PAL
        } 

        /// 
        /// Local helper function to validate the Pop Push range methods input
        ///  
        private void ValidatePushPopRangeInput(T[] items, int startIndex, int count)
        { 
            if (items == null) 
            {
                throw new ArgumentNullException("items"); 
            }
            if (count < 0)
            {
                throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ConcurrentStack_PushPopRange_CountOutOfRange")); 
            }
            int length = items.Length; 
            if (startIndex >= length || startIndex < 0) 
            {
                throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ConcurrentStack_PushPopRange_StartOutOfRange")); 
            }
            if (length - count < startIndex) //instead of (startIndex + count > items.Length) to prevent overflow
            {
                throw new ArgumentException(Environment.GetResourceString("ConcurrentStack_PushPopRange_InvalidCount")); 
            }
        } 
 
        /// 
        /// Attempts to add an object to the .
        /// 
        /// The object to add to the . The value can be a null 
        /// reference (Nothing in Visual Basic) for reference types.
        ///  
        /// true if the object was added successfully; otherwise, false. 
        /// For , this operation
        /// will always insert the object onto the top of the  
        /// and return true.
        bool IProducerConsumerCollection.TryAdd(T item)
        {
            Push(item); 
            return true;
        } 
 
        /// 
        /// Attempts to return an object from the top of the  
        /// without removing it.
        /// 
        /// When this method returns,  contains an object from
        /// the top of the  or an 
        /// unspecified value if the operation failed.
        /// true if and object was returned successfully; otherwise, false. 
        public bool TryPeek(out T result) 
        {
            Node head = m_head; 

            // If the stack is empty, return false; else return the element and true.
            if (head == null)
            { 
                result = default(T);
                return false; 
            } 
            else
            { 
                result = head.m_value;
                return true;
            }
        } 

        ///  
        /// Attempts to pop and return the object at the top of the . 
        /// 
        ///  
        /// When this method returns, if the operation was successful,  contains the
        /// object removed. If no object was available to be removed, the value is unspecified.
        /// 
        /// true if an element was removed and returned from the top of the 
        /// succesfully; otherwise, false. 
        public bool TryPop(out T result) 
        {
            Node head = m_head; 
            //stack is empty
            if (head == null)
            {
                result = default(T); 
                return false;
            } 
            if (Interlocked.CompareExchange(ref m_head, head.m_next, head) == head) 
            {
                result = head.m_value; 
                return true;
            }

            // Fall through to the slow path. 
            return TryPopCore(out result);
        } 
 
        /// 
        /// Attempts to pop and return multiple objects from the top of the  
        /// atomically.
        /// 
        /// 
        /// The  to which objects popped from the top of the  will be added.
        ///  
        /// The number of objects successfully popped from the top of the  and inserted in
        /// . 
        ///  is a null argument (Nothing
        /// in Visual Basic).
        /// 
        /// When popping multiple items, if there is little contention on the stack, using 
        /// TryPopRange can be more efficient than using 
        /// once per item to be removed.  Nodes fill the  
        /// with the first node to be popped at the startIndex, the second node to be popped 
        /// at startIndex + 1, and so on.
        ///  
        public int TryPopRange(T[] items)
        {
            if (items == null)
            { 
                throw new ArgumentNullException("items");
            } 
 
            return TryPopRange(items, 0, items.Length);
        } 

        /// 
        /// Attempts to pop and return multiple objects from the top of the 
        /// atomically. 
        /// 
        ///  
        /// The  to which objects popped from the top of the  will be added.
        ///  
        /// The zero-based offset in  at which to begin
        /// inserting elements from the top of the .
        /// The number of elements to be popped from top of the  and inserted into . 
        ///  is a null reference
        /// (Nothing in Visual Basic). 
        ///  or  is negative. Or  is greater than or equal to the length
        /// of . 
        ///  +  is
        /// greater than the length of .
        /// 
        /// When popping multiple items, if there is little contention on the stack, using 
        /// TryPopRange can be more efficient than using 
        /// once per item to be removed.  Nodes fill the  
        /// with the first node to be popped at the startIndex, the second node to be popped 
        /// at startIndex + 1, and so on.
        ///  
        public int TryPopRange(T[] items, int startIndex, int count)
        {
            ValidatePushPopRangeInput(items, startIndex, count);
 
            // No op if the count is zero
            if (count == 0) 
                return 0; 

            Node poppedHead; 
            int nodesCount = TryPopCore(count, out poppedHead);
            if (nodesCount > 0)
            {
                CopyRemovedItems(poppedHead, items, startIndex, nodesCount); 

            } 
            return nodesCount; 

        } 

        /// 
        /// Local helper function to Pop an item from the stack, slow path
        ///  
        /// The popped item
        /// True if succeeded, false otherwise 
        private bool TryPopCore(out T result) 
        {
            Node poppedNode; 

            if (TryPopCore(1, out poppedNode) == 1)
            {
                result = poppedNode.m_value; 
                return true;
            } 
 
            result = default(T);
            return false; 

        }

        ///  
        /// Slow path helper for TryPop. This method assumes an initial attempt to pop an element
        /// has already occurred and failed, so it begins spinning right away. 
        ///  
        /// The number of items to pop.
        ///  
        /// When this method returns, if the pop succeeded, contains the removed object. If no object was
        /// available to be removed, the value is unspecified. This parameter is passed uninitialized.
        /// 
        /// True if an element was removed and returned; otherwise, false. 
        private int TryPopCore(int count, out Node poppedHead)
        { 
            SpinWait spin = new SpinWait(); 

            // Try to CAS the head with its current next.  We stop when we succeed or 
            // when we notice that the stack is empty, whichever comes first.
            Node head;
            Node next;
            int backoff = 1; 
            Random r = new Random(Environment.TickCount & Int32.MaxValue); // avoid the case where TickCount could return Int32.MinValue
            while (true) 
            { 
                head = m_head;
                // Is the stack empty? 
                if (head == null)
                {
#if !FEATURE_PAL
                    if (count == 1 && CDSCollectionETWBCLProvider.Log.IsEnabled()) 
                    {
                        CDSCollectionETWBCLProvider.Log.ConcurrentStack_FastPopFailed(spin.Count); 
                    } 
#endif //!FEATURE_PAL
                    poppedHead = null; 
                    return 0;
                }
                next = head;
                int nodesCount = 1; 
                for (; nodesCount < count && next.m_next != null; nodesCount++)
                { 
                    next = next.m_next; 
                }
 
                // Try to swap the new head.  If we succeed, break out of the loop.
                if (Interlocked.CompareExchange(ref m_head, next.m_next, head) == head)
                {
#if !FEATURE_PAL 
                    if (count == 1 && CDSCollectionETWBCLProvider.Log.IsEnabled())
                    { 
                        CDSCollectionETWBCLProvider.Log.ConcurrentStack_FastPopFailed(spin.Count); 
                    }
#endif //!FEATURE_PAL 
                    // Return the popped Node.
                    poppedHead = head;
                    return nodesCount;
                } 

                // We failed to CAS the new head.  Spin briefly and retry. 
                for (int i = 0; i < backoff; i++) 
                {
                    spin.SpinOnce(); 
                }

                backoff = spin.NextSpinWillYield ? r.Next(1, BACKOFF_MAX_YIELDS) : backoff * 2;
            } 
        }
 
 
        /// 
        /// Local helper function to copy the poped elements into a given collection 
        /// 
        /// The head of the list to be copied
        /// The collection to place the popped items in
        /// the beginning of index of where to place the popped items 
        /// The number of nodes.
        private void CopyRemovedItems(Node head, T[] collection, int startIndex, int nodesCount) 
        { 
            Node current = head;
            for (int i = startIndex; i < startIndex + nodesCount; i++) 
            {
                collection[i] = current.m_value;
                current = current.m_next;
            } 

        } 
 
        /// 
        /// Attempts to remove and return an object from the .
        /// 
        /// 
        /// When this method returns, if the operation was successful,  contains the 
        /// object removed. If no object was available to be removed, the value is unspecified.
        ///  
        /// true if an element was removed and returned succesfully; otherwise, false. 
        /// For , this operation will attempt to pope the object at
        /// the top of the . 
        /// 
        bool IProducerConsumerCollection.TryTake(out T item)
        {
            return TryPop(out item); 
        }
 
        ///  
        /// Copies the items stored in the  to a new array.
        ///  
        /// A new array containing a snapshot of elements copied from the .
        public T[] ToArray()
        { 
            return ToList().ToArray();
        } 
 
        /// 
        /// Returns an array containing a snapshot of the list's contents, using 
        /// the target list node as the head of a region in the list.
        /// 
        /// An array of the list's contents.
        private List ToList() 
        {
            List list = new List(); 
 
            Node curr = m_head;
            while (curr != null) 
            {
                list.Add(curr.m_value);
                curr = curr.m_next;
            } 

            return list; 
        } 

        ///  
        /// Returns an enumerator that iterates through the .
        /// 
        /// An enumerator for the .
        ///  
        /// The enumeration represents a moment-in-time snapshot of the contents
        /// of the stack.  It does not reflect any updates to the collection after 
        ///  was called.  The enumerator is safe to use 
        /// concurrently with reads from and writes to the stack.
        ///  
        public IEnumerator GetEnumerator()
        {
            // Returns an enumerator for the stack. This effectively takes a snapshot
            // of the stack's contents at the time of the call, i.e. subsequent modifications 
            // (pushes or pops) will not be reflected in the enumerator's contents.
 
            //If we put yield-return here, the iterator will be lazily evaluated. As a result a snapshot of 
            //the stack is not taken when GetEnumerator is initialized but when MoveNext() is first called.
            //This is inconsistent with existing generic collections. In order to prevent it, we capture the 
            //value of m_head in a buffer and call out to a helper method
            return GetEnumerator(m_head);
        }
 
        private IEnumerator GetEnumerator(Node head)
        { 
            Node current = head; 
            while (current != null)
            { 
                yield return current.m_value;
                current = current.m_next;
            }
        } 

        ///  
        /// Returns an enumerator that iterates through a collection. 
        /// 
        /// An  that can be used to iterate through 
        /// the collection.
        /// 
        /// The enumeration represents a moment-in-time snapshot of the contents of the stack. It does not
        /// reflect any updates to the collection after 
        ///  was called. The enumerator is safe to use concurrently with reads
        /// from and writes to the stack. 
        ///  
        IEnumerator IEnumerable.GetEnumerator()
        { 
            return ((IEnumerable)this).GetEnumerator();
        }
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
#pragma warning disable 0420 

// ==++==
//
//   Copyright (c) Microsoft Corporation.  All rights reserved. 
//
// ==--== 
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ 
//
// ConcurrentStack.cs 
//
// [....]
//
// A lock-free, concurrent stack primitive, and its associated debugger view type. 
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- 
 
using System;
using System.Collections; 
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.Runtime.ConstrainedExecution; 
using System.Runtime.Serialization;
using System.Security; 
using System.Security.Permissions; 
using System.Threading;
 
namespace System.Collections.Concurrent
{
    // A stack that uses CAS operations internally to maintain thread-safety in a lock-free
    // manner. Attempting to push or pop concurrently from the stack will not trigger waiting, 
    // although some optimistic concurrency and retry is used, possibly leading to lack of
    // fairness and/or livelock. The stack uses spinning and backoff to add some randomization, 
    // in hopes of statistically decreasing the possibility of livelock. 
    //
    // Note that we currently allocate a new node on every push. This avoids having to worry 
    // about potential ABA issues, since the CLR GC ensures that a memory address cannot be
    // reused before all references to it have died.

    ///  
    /// Represents a thread-safe last-in, first-out collection of objects.
    ///  
    /// Specifies the type of elements in the stack. 
    /// 
    /// All public and protected members of  are thread-safe and may be used 
    /// concurrently from multiple threads.
    /// 
    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(typeof(SystemCollectionsConcurrent_ProducerConsumerCollectionDebugView<>))] 
    [HostProtection(Synchronization = true, ExternalThreading = true)]
    [Serializable] 
    public class ConcurrentStack : IProducerConsumerCollection 
    {
        ///  
        /// A simple (internal) node type used to store elements of concurrent stacks and queues.
        /// 
        private class Node
        { 
            internal T m_value; // Value of the node.
            internal Node m_next; // Next pointer. 
 
            /// 
            /// Constructs a new node with the specified value and no next node. 
            /// 
            /// The value of the node.
            internal Node(T value)
            { 
                m_value = value;
                m_next = null; 
            } 
        }
 
        [NonSerialized]
        private volatile Node m_head; // The stack is a singly linked list, and only remembers the head.

        private T[] m_serializationArray; // Used for custom serialization. 

        private const int BACKOFF_MAX_YIELDS = 8; // Arbitrary number to cap backoff. 
 
        /// 
        /// Initializes a new instance of the  
        /// class.
        /// 
        public ConcurrentStack()
        { 
        }
 
        ///  
        /// Initializes a new instance of the 
        /// class that contains elements copied from the specified collection 
        /// 
        /// The collection whose elements are copied to the new .
        /// The  argument is 
        /// null.
        public ConcurrentStack(IEnumerable collection) 
        { 
            if (collection == null)
            { 
                throw new ArgumentNullException("collection");
            }
            InitializeFromCollection(collection);
        } 

        ///  
        /// Initializes the contents of the stack from an existing collection. 
        /// 
        /// A collection from which to copy elements. 
        private void InitializeFromCollection(IEnumerable collection)
        {
            // We just copy the contents of the collection to our stack.
            Node lastNode = null; 
            foreach (T element in collection)
            { 
                Node newNode = new Node(element); 
                newNode.m_next = lastNode;
                lastNode = newNode; 
            }

            m_head = lastNode;
        } 

        ///  
        /// Get the data array to be serialized 
        /// 
        [OnSerializing] 
        private void OnSerializing(StreamingContext context)
        {
            // save the data into the serialization array to be saved
            m_serializationArray = ToArray(); 
        }
 
        ///  
        /// Construct the stack from a previously seiralized one
        ///  
        [OnDeserialized]
        private void OnDeserialized(StreamingContext context)
        {
            Contract.Assert(m_serializationArray != null); 
            // Add the elements to our stack.  We need to add them from head-to-tail, to
            // preserve the original ordering of the stack before serialization. 
            Node prevNode = null; 
            Node head = null;
            for (int i = 0; i < m_serializationArray.Length; i++) 
            {
                Node currNode = new Node(m_serializationArray[i]);

                if (prevNode == null) 
                {
                    head = currNode; 
                } 
                else
                { 
                    prevNode.m_next = currNode;
                }

                prevNode = currNode; 
            }
 
            m_head = head; 
            m_serializationArray = null;
        } 


        /// 
        /// Gets a value that indicates whether the  is empty. 
        /// 
        /// true if the  is empty; otherwise, false. 
        ///  
        /// For determining whether the collection contains any items, use of this property is recommended
        /// rather than retrieving the number of items from the  property and comparing it 
        /// to 0.  However, as this collection is intended to be accessed concurrently, it may be the case
        /// that another thread will modify the collection after  returns, thus invalidating
        /// the result.
        ///  
        public bool IsEmpty
        { 
            // Checks whether the stack is empty. Clearly the answer may be out of date even prior to 
            // the function returning (i.e. if another thread concurrently adds to the stack). It does
            // guarantee, however, that, if another thread does not mutate the stack, a subsequent call 
            // to TryPop will return true -- i.e. it will also read the stack as non-empty.
            get { return m_head == null; }
        }
 
        /// 
        /// Gets the number of elements contained in the . 
        ///  
        /// The number of elements contained in the .
        ///  
        /// For determining whether the collection contains any items, use of the 
        /// property is recommended rather than retrieving the number of items from the 
        /// property and comparing it to 0.
        ///  
        public int Count
        { 
            // Counts the number of entries in the stack. This is an O(n) operation. The answer may be out 
            // of date before returning, but guarantees to return a count that was once valid. Conceptually,
            // the implementation snaps a copy of the list and then counts the entries, though physically 
            // this is not what actually happens.
            get
            {
                int count = 0; 

                // Just whip through the list and tally up the number of nodes. We rely on the fact that 
                // node next pointers are immutable after being enqueued for the first time, even as 
                // they are being dequeued. If we ever changed this (e.g. to pool nodes somehow),
                // we'd need to revisit this implementation. 

                for (Node curr = m_head; curr != null; curr = curr.m_next)
                {
                    count++; //we don't handle overflow, to be consistent with existing generic collection types in CLR 
                }
 
                return count; 
            }
        } 


        /// 
        /// Gets a value indicating whether access to the  is 
        /// synchronized with the SyncRoot.
        ///  
        /// true if access to the  is synchronized 
        /// with the SyncRoot; otherwise, false. For , this property always
        /// returns false. 
        bool ICollection.IsSynchronized
        {
            // Gets a value indicating whether access to this collection is synchronized. Always returns
            // false. The reason is subtle. While access is in face thread safe, it's not the case that 
            // locking on the SyncRoot would have prevented concurrent pushes and pops, as this property
            // would typically indicate; that's because we internally use CAS operations vs. true locks. 
            get { return false; } 
        }
 
        /// 
        /// Gets an object that can be used to synchronize access to the . This property is not supported.
        ///  
        /// The SyncRoot property is not supported
        object ICollection.SyncRoot 
        { 
            get
            { 
                throw new NotSupportedException(Environment.GetResourceString("ConcurrentCollection_SyncRoot_NotSupported"));
            }
        }
 
        /// 
        /// Removes all objects from the . 
        ///  
        public void Clear()
        { 
            // Clear the list by setting the head to null. We don't need to use an atomic
            // operation for this: anybody who is mutating the head by pushing or popping
            // will need to use an atomic operation to guarantee they serialize and don't
            // overwrite our setting of the head to null. 
            m_head = null;
        } 
 
        /// 
        /// Copies the elements of the  to an , starting at a particular
        ///  index.
        /// 
        /// The one-dimensional  that is the destination of 
        /// the elements copied from the
        /// . The  must 
        /// have zero-based indexing. 
        /// The zero-based index in  at which copying
        /// begins. 
        ///  is a null reference (Nothing in
        /// Visual Basic).
        ///  is less than
        /// zero. 
        /// 
        ///  is multidimensional. -or- 
        ///  does not have zero-based indexing. -or- 
        ///  is equal to or greater than the length of the 
        /// -or- The number of elements in the source  is 
        /// greater than the available space from  to the end of the destination
        /// . -or- The type of the source  cannot be cast automatically to the type of the
        /// destination . 
        /// 
        void ICollection.CopyTo(Array array, int index) 
        { 
            // Validate arguments.
            if (array == null) 
            {
                throw new ArgumentNullException("array");
            }
 
            // We must be careful not to corrupt the array, so we will first accumulate an
            // internal list of elements that we will then copy to the array. This requires 
            // some extra allocation, but is necessary since we don't know up front whether 
            // the array is sufficiently large to hold the stack's contents.
            ((ICollection)ToList()).CopyTo(array, index); 
        }

        /// 
        /// Copies the  elements to an existing one-dimensional , starting at the specified array index.
        ///  
        /// The one-dimensional  that is the destination of 
        /// the elements copied from the
        /// . The  must have zero-based 
        /// indexing.
        /// The zero-based index in  at which copying
        /// begins.
        ///  is a null reference (Nothing in 
        /// Visual Basic).
        ///  is less than 
        /// zero. 
        ///  is equal to or greater than the
        /// length of the  
        /// -or- The number of elements in the source  is greater than the
        /// available space from  to the end of the destination .
        ///  
        public void CopyTo(T[] array, int index)
        { 
            if (array == null) 
            {
                throw new ArgumentNullException("array"); 
            }

            // We must be careful not to corrupt the array, so we will first accumulate an
            // internal list of elements that we will then copy to the array. This requires 
            // some extra allocation, but is necessary since we don't know up front whether
            // the array is sufficiently large to hold the stack's contents. 
            ToList().CopyTo(array, index); 
        }
 

        /// 
        /// Inserts an object at the top of the .
        ///  
        /// The object to push onto the . The value can be
        /// a null reference (Nothing in Visual Basic) for reference types. 
        ///  
        public void Push(T item)
        { 
            // Pushes a node onto the front of the stack thread-safely. Internally, this simply
            // swaps the current head pointer using a (thread safe) CAS operation to accomplish
            // lock freedom. If the CAS fails, we add some back off to statistically decrease
            // contention at the head, and then go back around and retry. 

            Node newNode = new Node(item); 
            newNode.m_next = m_head; 
            if (Interlocked.CompareExchange(ref m_head, newNode, newNode.m_next) == newNode.m_next)
            { 
                return;
            }

            // If we failed, go to the slow path and loop around until we succeed. 
            PushCore(newNode, newNode);
        } 
 
        /// 
        /// Inserts multiple objects at the top of the  atomically. 
        /// 
        /// The objects to push onto the .
        ///  is a null reference
        /// (Nothing in Visual Basic). 
        /// 
        /// When adding multiple items to the stack, using PushRange is a more efficient 
        /// mechanism than using  one item at a time.  Additionally, PushRange 
        /// guarantees that all of the elements will be added atomically, meaning that no other threads will
        /// be able to inject elements between the elements being pushed.  Items at lower indices in 
        /// the  array will be pushed before items at higher indices.
        /// 
        public void PushRange(T[] items)
        { 
            if (items == null)
            { 
                throw new ArgumentNullException("items"); 
            }
            PushRange(items, 0, items.Length); 
        }

        /// 
        /// Inserts multiple objects at the top of the  atomically. 
        /// 
        /// The objects to push onto the . 
        /// The zero-based offset in  at which to begin 
        /// inserting elements onto the top of the .
        /// The number of elements to be inserted onto the top of the .
        ///  is a null reference
        /// (Nothing in Visual Basic).
        ///  or  is negative. Or  is greater than or equal to the length
        /// of . 
        ///  +  is 
        /// greater than the length of .
        ///  
        /// When adding multiple items to the stack, using PushRange is a more efficient
        /// mechanism than using  one item at a time. Additionally, PushRange
        /// guarantees that all of the elements will be added atomically, meaning that no other threads will
        /// be able to inject elements between the elements being pushed. Items at lower indices in the 
        ///  array will be pushed before items at higher indices.
        ///  
        public void PushRange(T[] items, int startIndex, int count) 
        {
            ValidatePushPopRangeInput(items, startIndex, count); 

            // No op if the count is zero
            if (count == 0)
                return; 

 
            Node head, tail; 
            head = tail = new Node(items[startIndex]);
            for (int i = startIndex + 1; i < startIndex + count; i++) 
            {
                Node node = new Node(items[i]);
                node.m_next = head;
                head = node; 
            }
 
            tail.m_next = m_head; 
            if (Interlocked.CompareExchange(ref m_head, head, tail.m_next) == tail.m_next)
            { 
                return;
            }

            // If we failed, go to the slow path and loop around until we succeed. 
            PushCore(head, tail);
 
        } 

 
        /// 
        /// Push one or many nodes into the stack, if head and tails are equal then push one node to the stack other wise push the list between head
        /// and tail to the stack
        ///  
        /// The head pointer to the new list
        /// The tail pointer to the new list 
        private void PushCore(Node head, Node tail) 
        {
            SpinWait spin = new SpinWait(); 

            // Keep trying to CAS the exising head with the new node until we succeed.
            do
            { 
                spin.SpinOnce();
                // Reread the head and link our new node. 
                tail.m_next = m_head; 
            }
            while (Interlocked.CompareExchange( 
                ref m_head, head, tail.m_next) != tail.m_next);

#if !FEATURE_PAL
            if (CDSCollectionETWBCLProvider.Log.IsEnabled()) 
            {
                CDSCollectionETWBCLProvider.Log.ConcurrentStack_FastPushFailed(spin.Count); 
            } 
#endif //!FEATURE_PAL
        } 

        /// 
        /// Local helper function to validate the Pop Push range methods input
        ///  
        private void ValidatePushPopRangeInput(T[] items, int startIndex, int count)
        { 
            if (items == null) 
            {
                throw new ArgumentNullException("items"); 
            }
            if (count < 0)
            {
                throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ConcurrentStack_PushPopRange_CountOutOfRange")); 
            }
            int length = items.Length; 
            if (startIndex >= length || startIndex < 0) 
            {
                throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ConcurrentStack_PushPopRange_StartOutOfRange")); 
            }
            if (length - count < startIndex) //instead of (startIndex + count > items.Length) to prevent overflow
            {
                throw new ArgumentException(Environment.GetResourceString("ConcurrentStack_PushPopRange_InvalidCount")); 
            }
        } 
 
        /// 
        /// Attempts to add an object to the .
        /// 
        /// The object to add to the . The value can be a null 
        /// reference (Nothing in Visual Basic) for reference types.
        ///  
        /// true if the object was added successfully; otherwise, false. 
        /// For , this operation
        /// will always insert the object onto the top of the  
        /// and return true.
        bool IProducerConsumerCollection.TryAdd(T item)
        {
            Push(item); 
            return true;
        } 
 
        /// 
        /// Attempts to return an object from the top of the  
        /// without removing it.
        /// 
        /// When this method returns,  contains an object from
        /// the top of the  or an 
        /// unspecified value if the operation failed.
        /// true if and object was returned successfully; otherwise, false. 
        public bool TryPeek(out T result) 
        {
            Node head = m_head; 

            // If the stack is empty, return false; else return the element and true.
            if (head == null)
            { 
                result = default(T);
                return false; 
            } 
            else
            { 
                result = head.m_value;
                return true;
            }
        } 

        ///  
        /// Attempts to pop and return the object at the top of the . 
        /// 
        ///  
        /// When this method returns, if the operation was successful,  contains the
        /// object removed. If no object was available to be removed, the value is unspecified.
        /// 
        /// true if an element was removed and returned from the top of the 
        /// succesfully; otherwise, false. 
        public bool TryPop(out T result) 
        {
            Node head = m_head; 
            //stack is empty
            if (head == null)
            {
                result = default(T); 
                return false;
            } 
            if (Interlocked.CompareExchange(ref m_head, head.m_next, head) == head) 
            {
                result = head.m_value; 
                return true;
            }

            // Fall through to the slow path. 
            return TryPopCore(out result);
        } 
 
        /// 
        /// Attempts to pop and return multiple objects from the top of the  
        /// atomically.
        /// 
        /// 
        /// The  to which objects popped from the top of the  will be added.
        ///  
        /// The number of objects successfully popped from the top of the  and inserted in
        /// . 
        ///  is a null argument (Nothing
        /// in Visual Basic).
        /// 
        /// When popping multiple items, if there is little contention on the stack, using 
        /// TryPopRange can be more efficient than using 
        /// once per item to be removed.  Nodes fill the  
        /// with the first node to be popped at the startIndex, the second node to be popped 
        /// at startIndex + 1, and so on.
        ///  
        public int TryPopRange(T[] items)
        {
            if (items == null)
            { 
                throw new ArgumentNullException("items");
            } 
 
            return TryPopRange(items, 0, items.Length);
        } 

        /// 
        /// Attempts to pop and return multiple objects from the top of the 
        /// atomically. 
        /// 
        ///  
        /// The  to which objects popped from the top of the  will be added.
        ///  
        /// The zero-based offset in  at which to begin
        /// inserting elements from the top of the .
        /// The number of elements to be popped from top of the  and inserted into . 
        ///  is a null reference
        /// (Nothing in Visual Basic). 
        ///  or  is negative. Or  is greater than or equal to the length
        /// of . 
        ///  +  is
        /// greater than the length of .
        /// 
        /// When popping multiple items, if there is little contention on the stack, using 
        /// TryPopRange can be more efficient than using 
        /// once per item to be removed.  Nodes fill the  
        /// with the first node to be popped at the startIndex, the second node to be popped 
        /// at startIndex + 1, and so on.
        ///  
        public int TryPopRange(T[] items, int startIndex, int count)
        {
            ValidatePushPopRangeInput(items, startIndex, count);
 
            // No op if the count is zero
            if (count == 0) 
                return 0; 

            Node poppedHead; 
            int nodesCount = TryPopCore(count, out poppedHead);
            if (nodesCount > 0)
            {
                CopyRemovedItems(poppedHead, items, startIndex, nodesCount); 

            } 
            return nodesCount; 

        } 

        /// 
        /// Local helper function to Pop an item from the stack, slow path
        ///  
        /// The popped item
        /// True if succeeded, false otherwise 
        private bool TryPopCore(out T result) 
        {
            Node poppedNode; 

            if (TryPopCore(1, out poppedNode) == 1)
            {
                result = poppedNode.m_value; 
                return true;
            } 
 
            result = default(T);
            return false; 

        }

        ///  
        /// Slow path helper for TryPop. This method assumes an initial attempt to pop an element
        /// has already occurred and failed, so it begins spinning right away. 
        ///  
        /// The number of items to pop.
        ///  
        /// When this method returns, if the pop succeeded, contains the removed object. If no object was
        /// available to be removed, the value is unspecified. This parameter is passed uninitialized.
        /// 
        /// True if an element was removed and returned; otherwise, false. 
        private int TryPopCore(int count, out Node poppedHead)
        { 
            SpinWait spin = new SpinWait(); 

            // Try to CAS the head with its current next.  We stop when we succeed or 
            // when we notice that the stack is empty, whichever comes first.
            Node head;
            Node next;
            int backoff = 1; 
            Random r = new Random(Environment.TickCount & Int32.MaxValue); // avoid the case where TickCount could return Int32.MinValue
            while (true) 
            { 
                head = m_head;
                // Is the stack empty? 
                if (head == null)
                {
#if !FEATURE_PAL
                    if (count == 1 && CDSCollectionETWBCLProvider.Log.IsEnabled()) 
                    {
                        CDSCollectionETWBCLProvider.Log.ConcurrentStack_FastPopFailed(spin.Count); 
                    } 
#endif //!FEATURE_PAL
                    poppedHead = null; 
                    return 0;
                }
                next = head;
                int nodesCount = 1; 
                for (; nodesCount < count && next.m_next != null; nodesCount++)
                { 
                    next = next.m_next; 
                }
 
                // Try to swap the new head.  If we succeed, break out of the loop.
                if (Interlocked.CompareExchange(ref m_head, next.m_next, head) == head)
                {
#if !FEATURE_PAL 
                    if (count == 1 && CDSCollectionETWBCLProvider.Log.IsEnabled())
                    { 
                        CDSCollectionETWBCLProvider.Log.ConcurrentStack_FastPopFailed(spin.Count); 
                    }
#endif //!FEATURE_PAL 
                    // Return the popped Node.
                    poppedHead = head;
                    return nodesCount;
                } 

                // We failed to CAS the new head.  Spin briefly and retry. 
                for (int i = 0; i < backoff; i++) 
                {
                    spin.SpinOnce(); 
                }

                backoff = spin.NextSpinWillYield ? r.Next(1, BACKOFF_MAX_YIELDS) : backoff * 2;
            } 
        }
 
 
        /// 
        /// Local helper function to copy the poped elements into a given collection 
        /// 
        /// The head of the list to be copied
        /// The collection to place the popped items in
        /// the beginning of index of where to place the popped items 
        /// The number of nodes.
        private void CopyRemovedItems(Node head, T[] collection, int startIndex, int nodesCount) 
        { 
            Node current = head;
            for (int i = startIndex; i < startIndex + nodesCount; i++) 
            {
                collection[i] = current.m_value;
                current = current.m_next;
            } 

        } 
 
        /// 
        /// Attempts to remove and return an object from the .
        /// 
        /// 
        /// When this method returns, if the operation was successful,  contains the 
        /// object removed. If no object was available to be removed, the value is unspecified.
        ///  
        /// true if an element was removed and returned succesfully; otherwise, false. 
        /// For , this operation will attempt to pope the object at
        /// the top of the . 
        /// 
        bool IProducerConsumerCollection.TryTake(out T item)
        {
            return TryPop(out item); 
        }
 
        ///  
        /// Copies the items stored in the  to a new array.
        ///  
        /// A new array containing a snapshot of elements copied from the .
        public T[] ToArray()
        { 
            return ToList().ToArray();
        } 
 
        /// 
        /// Returns an array containing a snapshot of the list's contents, using 
        /// the target list node as the head of a region in the list.
        /// 
        /// An array of the list's contents.
        private List ToList() 
        {
            List list = new List(); 
 
            Node curr = m_head;
            while (curr != null) 
            {
                list.Add(curr.m_value);
                curr = curr.m_next;
            } 

            return list; 
        } 

        ///  
        /// Returns an enumerator that iterates through the .
        /// 
        /// An enumerator for the .
        ///  
        /// The enumeration represents a moment-in-time snapshot of the contents
        /// of the stack.  It does not reflect any updates to the collection after 
        ///  was called.  The enumerator is safe to use 
        /// concurrently with reads from and writes to the stack.
        ///  
        public IEnumerator GetEnumerator()
        {
            // Returns an enumerator for the stack. This effectively takes a snapshot
            // of the stack's contents at the time of the call, i.e. subsequent modifications 
            // (pushes or pops) will not be reflected in the enumerator's contents.
 
            //If we put yield-return here, the iterator will be lazily evaluated. As a result a snapshot of 
            //the stack is not taken when GetEnumerator is initialized but when MoveNext() is first called.
            //This is inconsistent with existing generic collections. In order to prevent it, we capture the 
            //value of m_head in a buffer and call out to a helper method
            return GetEnumerator(m_head);
        }
 
        private IEnumerator GetEnumerator(Node head)
        { 
            Node current = head; 
            while (current != null)
            { 
                yield return current.m_value;
                current = current.m_next;
            }
        } 

        ///  
        /// Returns an enumerator that iterates through a collection. 
        /// 
        /// An  that can be used to iterate through 
        /// the collection.
        /// 
        /// The enumeration represents a moment-in-time snapshot of the contents of the stack. It does not
        /// reflect any updates to the collection after 
        ///  was called. The enumerator is safe to use concurrently with reads
        /// from and writes to the stack. 
        ///  
        IEnumerator IEnumerable.GetEnumerator()
        { 
            return ((IEnumerable)this).GetEnumerator();
        }
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK