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
25 #if NET_4_0 || BOOTSTRAP_NET_4_0
28 using System.Threading;
29 using System.Collections;
30 using System.Collections.Generic;
31 using System.Runtime.Serialization;
33 namespace System.Collections.Concurrent
36 public class ConcurrentQueue<T> : IProducerConsumerCollection<T>, IEnumerable<T>, ICollection,
45 Node head = new Node ();
49 public ConcurrentQueue ()
54 public ConcurrentQueue (IEnumerable<T> enumerable): this()
56 foreach (T item in enumerable)
60 public void Enqueue (T item)
62 Node node = new Node ();
71 oldNext = oldTail.Next;
73 // Did tail was already updated ?
74 if (tail == oldTail) {
75 if (oldNext == null) {
76 // The place is for us
77 update = Interlocked.CompareExchange (ref tail.Next, node, null) == null;
79 // another Thread already used the place so give him a hand by putting tail where it should be
80 Interlocked.CompareExchange (ref tail, oldNext, oldTail);
84 // 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
85 Interlocked.CompareExchange (ref tail, node, oldTail);
87 Interlocked.Increment (ref count);
90 bool IProducerConsumerCollection<T>.TryAdd (T item)
96 public bool TryDequeue (out T value)
99 bool advanced = false;
104 Node oldNext = oldHead.Next;
106 if (oldHead == head) {
108 if (oldHead == oldTail) {
109 // This should be false then
110 if (oldNext != null) {
111 // If not then the linked list is mal formed, update tail
112 Interlocked.CompareExchange (ref tail, oldNext, oldTail);
117 value = oldNext.Value;
118 advanced = Interlocked.CompareExchange (ref head, oldNext, oldHead) == oldHead;
123 Interlocked.Decrement (ref count);
128 public bool TryPeek (out T value)
135 Node first = head.Next;
140 internal void Clear ()
143 tail = head = new Node ();
146 IEnumerator IEnumerable.GetEnumerator ()
148 return (IEnumerator)InternalGetEnumerator ();
151 public IEnumerator<T> GetEnumerator ()
153 return InternalGetEnumerator ();
156 IEnumerator<T> InternalGetEnumerator ()
159 while ((my_head = my_head.Next) != null) {
160 yield return my_head.Value;
164 void ICollection.CopyTo (Array array, int index)
166 T[] dest = array as T[];
169 CopyTo (dest, index);
172 public void CopyTo (T[] dest, int index)
174 IEnumerator<T> e = InternalGetEnumerator ();
176 while (e.MoveNext ()) {
177 dest [i++] = e.Current;
181 public T[] ToArray ()
183 T[] dest = new T [count];
188 bool ICollection.IsSynchronized {
192 bool IProducerConsumerCollection<T>.TryTake (out T item)
194 return TryDequeue (out item);
197 object syncRoot = new object();
198 object ICollection.SyncRoot {
199 get { return syncRoot; }
208 public bool IsEmpty {