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 class NodeObjectPool : ObjectPool<Node> {
52 protected override Node Creator ()
57 static readonly NodeObjectPool pool = new NodeObjectPool ();
59 static Node ZeroOut (Node node)
61 node.Value = default(T);
66 public ConcurrentQueue ()
71 public ConcurrentQueue (IEnumerable<T> collection): this()
73 foreach (T item in collection)
77 public void Enqueue (T item)
79 Node node = pool.Take ();
88 oldNext = oldTail.Next;
90 // Did tail was already updated ?
91 if (tail == oldTail) {
92 if (oldNext == null) {
93 // The place is for us
94 update = Interlocked.CompareExchange (ref tail.Next, node, null) == null;
96 // another Thread already used the place so give him a hand by putting tail where it should be
97 Interlocked.CompareExchange (ref tail, oldNext, oldTail);
101 // 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
102 Interlocked.CompareExchange (ref tail, node, oldTail);
104 Interlocked.Increment (ref count);
107 bool IProducerConsumerCollection<T>.TryAdd (T item)
113 public bool TryDequeue (out T result)
115 result = default (T);
116 bool advanced = false;
121 Node oldNext = oldHead.Next;
123 if (oldHead == head) {
125 if (oldHead == oldTail) {
126 // This should be false then
127 if (oldNext != null) {
128 // If not then the linked list is mal formed, update tail
129 Interlocked.CompareExchange (ref tail, oldNext, oldTail);
131 result = default (T);
134 result = oldNext.Value;
135 advanced = Interlocked.CompareExchange (ref head, oldNext, oldHead) == oldHead;
137 pool.Release (ZeroOut (oldHead));
142 Interlocked.Decrement (ref count);
147 public bool TryPeek (out T result)
150 result = default (T);
154 Node first = head.Next;
155 result = first.Value;
159 internal void Clear ()
162 tail = head = new Node ();
165 IEnumerator IEnumerable.GetEnumerator ()
167 return (IEnumerator)InternalGetEnumerator ();
170 public IEnumerator<T> GetEnumerator ()
172 return InternalGetEnumerator ();
175 IEnumerator<T> InternalGetEnumerator ()
178 while ((my_head = my_head.Next) != null) {
179 yield return my_head.Value;
183 void ICollection.CopyTo (Array array, int index)
186 throw new ArgumentNullException ("array");
188 throw new ArgumentException ("The array can't be multidimensional");
189 if (array.GetLowerBound (0) != 0)
190 throw new ArgumentException ("The array needs to be 0-based");
192 T[] dest = array as T[];
194 throw new ArgumentException ("The array cannot be cast to the collection element type", "array");
195 CopyTo (dest, index);
198 public void CopyTo (T[] array, int index)
201 throw new ArgumentNullException ("array");
203 throw new ArgumentOutOfRangeException ("index");
204 if (index >= array.Length)
205 throw new ArgumentException ("index is equals or greather than array length", "index");
207 IEnumerator<T> e = InternalGetEnumerator ();
209 while (e.MoveNext ()) {
210 if (i == array.Length - index)
211 throw new ArgumentException ("The number of elememts in the collection exceeds the capacity of array", "array");
212 array[i++] = e.Current;
216 public T[] ToArray ()
218 return new List<T> (this).ToArray ();
221 bool ICollection.IsSynchronized {
225 bool IProducerConsumerCollection<T>.TryTake (out T item)
227 return TryDequeue (out item);
230 object syncRoot = new object();
231 object ICollection.SyncRoot {
232 get { return syncRoot; }
241 public bool IsEmpty {