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
);
89 Interlocked
.Increment (ref count
);
92 bool IProducerConsumerCollection
<T
>.TryAdd (T item
)
98 public bool TryDequeue (out T result
)
100 result
= default (T
);
101 bool advanced
= false;
106 Node oldNext
= oldHead
.Next
;
108 if (oldHead
== head
) {
110 if (oldHead
== oldTail
) {
111 // This should be false then
112 if (oldNext
!= null) {
113 // If not then the linked list is mal formed, update tail
114 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
)
133 result
= default (T
);
137 Node first
= head
.Next
;
138 result
= first
.Value
;
142 internal void Clear ()
145 tail
= head
= new Node ();
148 IEnumerator IEnumerable
.GetEnumerator ()
150 return (IEnumerator
)InternalGetEnumerator ();
153 public IEnumerator
<T
> GetEnumerator ()
155 return InternalGetEnumerator ();
158 IEnumerator
<T
> InternalGetEnumerator ()
161 while ((my_head
= my_head
.Next
) != null) {
162 yield return my_head
.Value
;
166 void ICollection
.CopyTo (Array array
, int index
)
168 T
[] dest
= array
as T
[];
171 CopyTo (dest
, index
);
174 public void CopyTo (T
[] array
, int index
)
176 IEnumerator
<T
> e
= InternalGetEnumerator ();
178 while (e
.MoveNext ()) {
179 array
[i
++] = e
.Current
;
183 public T
[] ToArray ()
185 T
[] dest
= new T
[count
];
190 bool ICollection
.IsSynchronized
{
194 bool IProducerConsumerCollection
<T
>.TryTake (out T item
)
196 return TryDequeue (out item
);
199 object syncRoot
= new object();
200 object ICollection
.SyncRoot
{
201 get { return syncRoot; }
210 public bool IsEmpty
{