mcs/class/corlib/System.Collections.Concurrent/ConcurrentQueue.cs

   1 // ConcurrentQueue.cs
   2 //
   3 // Copyright (c) 2008 Jérémie "Garuma" Laval
   4 //
   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:
  11 //
  12 // The above copyright notice and this permission notice shall be included in
  13 // all copies or substantial portions of the Software.
  14 //
  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
  21 // THE SOFTWARE.
  22 //
  23 //
  24
  25 #if NET_4_0
  26
  27 using System;
  28 using System.Threading;
  29 using System.Collections;
  30 using System.Collections.Generic;
  31 using System.Runtime.Serialization;
  32
  33 namespace System.Collections.Concurrent
  34 {
  35
  36         [System.Diagnostics.DebuggerDisplay ("Count={Count}")]
  37         [System.Diagnostics.DebuggerTypeProxy (typeof (CollectionDebuggerView<>))]
  38         public class ConcurrentQueue<T> : IProducerConsumerCollection<T>, IEnumerable<T>, ICollection,
  39                                           IEnumerable
  40         {
  41                 class Node
  42                 {
  43                         public T Value;
  44                         public Node Next;
  45                 }
  46
  47                 Node head = new Node ();
  48                 Node tail;
  49                 int count;
  50
  51                 public ConcurrentQueue ()
  52                 {
  53                         tail = head;
  54                 }
  55
  56                 public ConcurrentQueue (IEnumerable<T> collection): this()
  57                 {
  58                         foreach (T item in collection)
  59                                 Enqueue (item);
  60                 }
  61
  62                 public void Enqueue (T item)
  63                 {
  64                         Node node = new Node ();
  65                         node.Value = item;
  66
  67                         Node oldTail = null;
  68                         Node oldNext = null;
  69
  70                         bool update = false;
  71                         while (!update) {
  72                                 oldTail = tail;
  73                                 oldNext = oldTail.Next;
  74
  75                                 Thread.MemoryBarrier ();
  76
  77                                 // Did tail was already updated ?
  78                                 if (tail == oldTail) {
  79                                         if (oldNext == null) {
  80                                                 // The place is for us
  81                                                 update = Interlocked.CompareExchange (ref tail.Next, node, null) == null;
  82                                         } else {
  83                                                 // another Thread already used the place so give him a hand by putting tail where it should be
  84                                                 Interlocked.CompareExchange (ref tail, oldNext, oldTail);
  85                                         }
  86                                 }
  87                         }
  88                         // 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
  89                         Interlocked.CompareExchange (ref tail, node, oldTail);
  90                         Interlocked.Increment (ref count);
  91                 }
  92
  93                 bool IProducerConsumerCollection<T>.TryAdd (T item)
  94                 {
  95                         Enqueue (item);
  96                         return true;
  97                 }
  98
  99                 public bool TryDequeue (out T result)
 100                 {
 101                         result = default (T);
 102                         Node oldNext = null;
 103                         bool advanced = false;
 104
 105                         while (!advanced) {
 106                                 Node oldHead = head;
 107                                 Node oldTail = tail;
 108                                 oldNext = oldHead.Next;
 109
 110                                 Thread.MemoryBarrier ();
 111
 112                                 if (oldHead == head) {
 113                                         // Empty case ?
 114                                         if (oldHead == oldTail) {
 115                                                 // This should be false then
 116                                                 if (oldNext != null) {
 117                                                         // If not then the linked list is mal formed, update tail
 118                                                         Interlocked.CompareExchange (ref tail, oldNext, oldTail);
 119                                                         continue;
 120                                                 }
 121                                                 result = default (T);
 122                                                 return false;
 123                                         } else {
 124                                                 result = oldNext.Value;
 125                                                 advanced = Interlocked.CompareExchange (ref head, oldNext, oldHead) == oldHead;
 126                                         }
 127                                 }
 128                         }
 129
 130                         oldNext.Value = default (T);
 131
 132                         Interlocked.Decrement (ref count);
 133
 134                         return true;
 135                 }
 136
 137                 public bool TryPeek (out T result)
 138                 {
 139                         result = default (T);
 140                         bool update = true;
 141
 142                         while (update)
 143                         {
 144                                 Node oldHead = head;
 145                                 Node oldNext = oldHead.Next;
 146
 147                                 if (oldNext == null) {
 148                                         result = default (T);
 149                                         return false;
 150                                 }
 151
 152                                 result = oldNext.Value;
 153
 154                                 Thread.MemoryBarrier ();
 155
 156                                 //check if head has been updated
 157                                 update = head != oldHead;
 158                         }
 159                         return true;
 160                 }
 161
 162                 internal void Clear ()
 163                 {
 164                         count = 0;
 165                         tail = head = new Node ();
 166                 }
 167
 168                 IEnumerator IEnumerable.GetEnumerator ()
 169                 {
 170                         return (IEnumerator)InternalGetEnumerator ();
 171                 }
 172
 173                 public IEnumerator<T> GetEnumerator ()
 174                 {
 175                         return InternalGetEnumerator ();
 176                 }
 177
 178                 IEnumerator<T> InternalGetEnumerator ()
 179                 {
 180                         Node my_head = head;
 181                         while ((my_head = my_head.Next) != null) {
 182                                 yield return my_head.Value;
 183                         }
 184                 }
 185
 186                 void ICollection.CopyTo (Array array, int index)
 187                 {
 188                         if (array == null)
 189                                 throw new ArgumentNullException ("array");
 190                         if (array.Rank > 1)
 191                                 throw new ArgumentException ("The array can't be multidimensional");
 192                         if (array.GetLowerBound (0) != 0)
 193                                 throw new ArgumentException ("The array needs to be 0-based");
 194
 195                         T[] dest = array as T[];
 196                         if (dest == null)
 197                                 throw new ArgumentException ("The array cannot be cast to the collection element type", "array");
 198                         CopyTo (dest, index);
 199                 }
 200
 201                 public void CopyTo (T[] array, int index)
 202                 {
 203                         if (array == null)
 204                                 throw new ArgumentNullException ("array");
 205                         if (index < 0)
 206                                 throw new ArgumentOutOfRangeException ("index");
 207                         if (index >= array.Length)
 208                                 throw new ArgumentException ("index is equals or greather than array length", "index");
 209
 210                         IEnumerator<T> e = InternalGetEnumerator ();
 211                         int i = index;
 212                         while (e.MoveNext ()) {
 213                                 if (i == array.Length - index)
 214                                         throw new ArgumentException ("The number of elememts in the collection exceeds the capacity of array", "array");
 215                                 array[i++] = e.Current;
 216                         }
 217                 }
 218
 219                 public T[] ToArray ()
 220                 {
 221                         return new List<T> (this).ToArray ();
 222                 }
 223
 224                 bool ICollection.IsSynchronized {
 225                         get { return true; }
 226                 }
 227
 228                 bool IProducerConsumerCollection<T>.TryTake (out T item)
 229                 {
 230                         return TryDequeue (out item);
 231                 }
 232
 233                 object syncRoot = new object();
 234                 object ICollection.SyncRoot {
 235                         get { return syncRoot; }
 236                 }
 237
 238                 public int Count {
 239                         get {
 240                                 return count;
 241                         }
 242                 }
 243
 244                 public bool IsEmpty {
 245                         get {
 246                                 return count == 0;
 247                         }
 248                 }
 249         }
 250 }
 251 #endif