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 || BOOTSTRAP_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         public class ConcurrentQueue<T> : IProducerConsumerCollection<T>, IEnumerable<T>, ICollection,
  37                                           IEnumerable
  38         {
  39                 class Node
  40                 {
  41                         public T Value;
  42                         public Node Next;
  43                 }
  44
  45                 Node head = new Node ();
  46                 Node tail;
  47                 int count;
  48
  49                 public ConcurrentQueue ()
  50                 {
  51                         tail = head;
  52                 }
  53
  54                 public ConcurrentQueue (IEnumerable<T> enumerable): this()
  55                 {
  56                         foreach (T item in enumerable)
  57                                 Enqueue (item);
  58                 }
  59
  60                 public void Enqueue (T item)
  61                 {
  62                         Node node  = new Node ();
  63                         node.Value = item;
  64
  65                         Node oldTail = null;
  66                         Node oldNext = null;
  67
  68                         bool update = false;
  69                         while (!update) {
  70                                 oldTail = tail;
  71                                 oldNext = oldTail.Next;
  72
  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;
  78                                         } else {
  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);
  81                                         }
  82                                 }
  83                         }
  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);
  86
  87                         Interlocked.Increment (ref count);
  88                 }
  89
  90                 bool IProducerConsumerCollection<T>.TryAdd (T item)
  91                 {
  92                         Enqueue (item);
  93                         return true;
  94                 }
  95
  96                 public bool TryDequeue (out T value)
  97                 {
  98                         value = default (T);
  99                         bool advanced = false;
 100
 101                         while (!advanced) {
 102                                 Node oldHead = head;
 103                                 Node oldTail = tail;
 104                                 Node oldNext = oldHead.Next;
 105
 106                                 if (oldHead == head) {
 107                                         // Empty case ?
 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);
 113                                                 }
 114                                                 value = default (T);
 115                                                 return false;
 116                                         } else {
 117                                                 value = oldNext.Value;
 118                                                 advanced = Interlocked.CompareExchange (ref head, oldNext, oldHead) == oldHead;
 119                                         }
 120                                 }
 121                         }
 122
 123                         Interlocked.Decrement (ref count);
 124
 125                         return true;
 126                 }
 127
 128                 public bool TryPeek (out T value)
 129                 {
 130                         if (IsEmpty) {
 131                                 value = default (T);
 132                                 return false;
 133                         }
 134
 135                         Node first = head.Next;
 136                         value = first.Value;
 137                         return true;
 138                 }
 139
 140                 internal void Clear ()
 141                 {
 142                         count = 0;
 143                         tail = head = new Node ();
 144                 }
 145
 146                 IEnumerator IEnumerable.GetEnumerator ()
 147                 {
 148                         return (IEnumerator)InternalGetEnumerator ();
 149                 }
 150
 151                 public IEnumerator<T> GetEnumerator ()
 152                 {
 153                         return InternalGetEnumerator ();
 154                 }
 155
 156                 IEnumerator<T> InternalGetEnumerator ()
 157                 {
 158                         Node my_head = head;
 159                         while ((my_head = my_head.Next) != null) {
 160                                 yield return my_head.Value;
 161                         }
 162                 }
 163
 164                 void ICollection.CopyTo (Array array, int index)
 165                 {
 166                         T[] dest = array as T[];
 167                         if (dest == null)
 168                                 return;
 169                         CopyTo (dest, index);
 170                 }
 171
 172                 public void CopyTo (T[] dest, int index)
 173                 {
 174                         IEnumerator<T> e = InternalGetEnumerator ();
 175                         int i = index;
 176                         while (e.MoveNext ()) {
 177                                 dest [i++] = e.Current;
 178                         }
 179                 }
 180
 181                 public T[] ToArray ()
 182                 {
 183                         T[] dest = new T [count];
 184                         CopyTo (dest, 0);
 185                         return dest;
 186                 }
 187
 188                 bool ICollection.IsSynchronized {
 189                         get { return true; }
 190                 }
 191
 192                 bool IProducerConsumerCollection<T>.TryTake (out T item)
 193                 {
 194                         return TryDequeue (out item);
 195                 }
 196
 197                 object syncRoot = new object();
 198                 object ICollection.SyncRoot {
 199                         get { return syncRoot; }
 200                 }
 201
 202                 public int Count {
 203                         get {
 204                                 return count;
 205                         }
 206                 }
 207
 208                 public bool IsEmpty {
 209                         get {
 210                                 return count == 0;
 211                         }
 212                 }
 213         }
 214 }
 215 #endif