3 // Copyright (c) 2008 Jérémie "Garuma" Laval
5 // Permission is hereby granted, free of charge, to any person obtaining a copy
6 // of this software and associated documentation files (the "Software"), to deal
7 // in the Software without restriction, including without limitation the rights
8 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 // copies of the Software, and to permit persons to whom the Software is
10 // furnished to do so, subject to the following conditions:
12 // The above copyright notice and this permission notice shall be included in
13 // all copies or substantial portions of the Software.
15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
28 using System.Threading;
29 using System.Collections;
30 using System.Collections.Generic;
31 using System.Runtime.Serialization;
33 namespace System.Collections.Concurrent
36 [System.Diagnostics.DebuggerDisplay ("Count={Count}")]
37 [System.Diagnostics.DebuggerTypeProxy (typeof (CollectionDebuggerView<>))]
38 public class ConcurrentQueue<T> : IProducerConsumerCollection<T>, IEnumerable<T>, ICollection,
47 Node head = new Node ();
51 public ConcurrentQueue ()
56 public ConcurrentQueue (IEnumerable<T> collection): this()
58 foreach (T item in collection)
62 public void Enqueue (T item)
64 Node node = new Node ();
73 oldNext = oldTail.Next;
75 // Did tail was already updated ?
76 if (tail == oldTail) {
77 if (oldNext == null) {
78 // The place is for us
79 update = Interlocked.CompareExchange (ref tail.Next, node, null) == null;
81 // another Thread already used the place so give him a hand by putting tail where it should be
82 Interlocked.CompareExchange (ref tail, oldNext, oldTail);
86 // At this point we added correctly our node, now we have to update tail. If it fails then it will be done by another thread
87 Interlocked.CompareExchange (ref tail, node, oldTail);
88 Interlocked.Increment (ref count);
91 bool IProducerConsumerCollection<T>.TryAdd (T item)
97 public bool TryDequeue (out T result)
100 bool advanced = false;
105 Node oldNext = oldHead.Next;
107 if (oldHead == head) {
109 if (oldHead == oldTail) {
110 // This should be false then
111 if (oldNext != null) {
112 // If not then the linked list is mal formed, update tail
113 Interlocked.CompareExchange (ref tail, oldNext, oldTail);
116 result = default (T);
119 result = oldNext.Value;
120 advanced = Interlocked.CompareExchange (ref head, oldNext, oldHead) == oldHead;
125 Interlocked.Decrement (ref count);
130 public bool TryPeek (out T result)
132 Node first = head.Next;
135 result = default (T);
139 result = first.Value;
143 internal void Clear ()
146 tail = head = new Node ();
149 IEnumerator IEnumerable.GetEnumerator ()
151 return (IEnumerator)InternalGetEnumerator ();
154 public IEnumerator<T> GetEnumerator ()
156 return InternalGetEnumerator ();
159 IEnumerator<T> InternalGetEnumerator ()
162 while ((my_head = my_head.Next) != null) {
163 yield return my_head.Value;
167 void ICollection.CopyTo (Array array, int index)
170 throw new ArgumentNullException ("array");
172 throw new ArgumentException ("The array can't be multidimensional");
173 if (array.GetLowerBound (0) != 0)
174 throw new ArgumentException ("The array needs to be 0-based");
176 T[] dest = array as T[];
178 throw new ArgumentException ("The array cannot be cast to the collection element type", "array");
179 CopyTo (dest, index);
182 public void CopyTo (T[] array, int index)
185 throw new ArgumentNullException ("array");
187 throw new ArgumentOutOfRangeException ("index");
188 if (index >= array.Length)
189 throw new ArgumentException ("index is equals or greather than array length", "index");
191 IEnumerator<T> e = InternalGetEnumerator ();
193 while (e.MoveNext ()) {
194 if (i == array.Length - index)
195 throw new ArgumentException ("The number of elememts in the collection exceeds the capacity of array", "array");
196 array[i++] = e.Current;
200 public T[] ToArray ()
202 return new List<T> (this).ToArray ();
205 bool ICollection.IsSynchronized {
209 bool IProducerConsumerCollection<T>.TryTake (out T item)
211 return TryDequeue (out item);
214 object syncRoot = new object();
215 object ICollection.SyncRoot {
216 get { return syncRoot; }
225 public bool IsEmpty {