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

   1 // ConcurrentStack.cs
   2 //
   3 // Authors:
   4 //      Marek Safar  <marek.safar@gmail.com>
   5 //
   6 // Copyright (c) 2008 Jérémie "Garuma" Laval
   7 // Copyright (C) 2014 Xamarin Inc (http://www.xamarin.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining a copy
  10 // of this software and associated documentation files (the "Software"), to deal
  11 // in the Software without restriction, including without limitation the rights
  12 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  13 // copies of the Software, and to permit persons to whom the Software is
  14 // furnished to do so, subject to the following conditions:
  15 //
  16 // The above copyright notice and this permission notice shall be included in
  17 // all copies or substantial portions of the Software.
  18 //
  19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  22 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  23 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  24 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  25 // THE SOFTWARE.
  26 //
  27 //
  28
  29 #if NET_4_0
  30
  31 using System;
  32 using System.Threading;
  33 using System.Collections;
  34 using System.Collections.Generic;
  35 using System.Runtime.Serialization;
  36
  37 namespace System.Collections.Concurrent
  38 {
  39
  40         [System.Diagnostics.DebuggerDisplay ("Count = {Count}")]
  41         [System.Diagnostics.DebuggerTypeProxy (typeof (CollectionDebuggerView<>))]
  42         public class ConcurrentStack<T> : IProducerConsumerCollection<T>, IEnumerable<T>,
  43                                           ICollection, IEnumerable
  44         {
  45                 class Node
  46                 {
  47                         public T Value = default (T);
  48                         public Node Next;
  49                 }
  50
  51                 Node head;
  52
  53                 int count;
  54
  55                 public ConcurrentStack ()
  56                 {
  57                 }
  58
  59                 public ConcurrentStack (IEnumerable<T> collection)
  60                 {
  61                         if (collection == null)
  62                                 throw new ArgumentNullException ("collection");
  63
  64                         foreach (T item in collection)
  65                                 Push (item);
  66                 }
  67
  68                 bool IProducerConsumerCollection<T>.TryAdd (T elem)
  69                 {
  70                         Push (elem);
  71                         return true;
  72                 }
  73
  74                 public void Push (T item)
  75                 {
  76                         Node temp = new Node ();
  77                         temp.Value = item;
  78                         do {
  79                           temp.Next = head;
  80                         } while (Interlocked.CompareExchange (ref head, temp, temp.Next) != temp.Next);
  81
  82                         Interlocked.Increment (ref count);
  83                 }
  84
  85                 public void PushRange (T[] items)
  86                 {
  87                         if (items == null)
  88                                 throw new ArgumentNullException ("items");
  89
  90                         PushRange (items, 0, items.Length);
  91                 }
  92
  93                 public void PushRange (T[] items, int startIndex, int count)
  94                 {
  95                         RangeArgumentsCheck (items, startIndex, count);
  96
  97                         Node insert = null;
  98                         Node first = null;
  99
 100                         for (int i = startIndex; i < count; i++) {
 101                                 Node temp = new Node ();
 102                                 temp.Value = items[i];
 103                                 temp.Next = insert;
 104                                 insert = temp;
 105
 106                                 if (first == null)
 107                                         first = temp;
 108                         }
 109
 110                         do {
 111                                 first.Next = head;
 112                         } while (Interlocked.CompareExchange (ref head, insert, first.Next) != first.Next);
 113
 114                         Interlocked.Add (ref count, count);
 115                 }
 116
 117                 public bool TryPop (out T result)
 118                 {
 119                         Node temp;
 120                         do {
 121                                 temp = head;
 122                                 // The stak is empty
 123                                 if (temp == null) {
 124                                         result = default (T);
 125                                         return false;
 126                                 }
 127                         } while (Interlocked.CompareExchange (ref head, temp.Next, temp) != temp);
 128
 129                         Interlocked.Decrement (ref count);
 130
 131                         result = temp.Value;
 132
 133                         return true;
 134                 }
 135
 136                 public int TryPopRange (T[] items)
 137                 {
 138                         if (items == null)
 139                                 throw new ArgumentNullException ("items");
 140                         return TryPopRange (items, 0, items.Length);
 141                 }
 142
 143                 public int TryPopRange (T[] items, int startIndex, int count)
 144                 {
 145                         RangeArgumentsCheck (items, startIndex, count);
 146
 147                         Node temp;
 148                         Node end;
 149
 150                         do {
 151                                 temp = head;
 152                                 if (temp == null)
 153                                         return 0;
 154                                 end = temp;
 155                                 for (int j = 0; j < count; j++) {
 156                                         end = end.Next;
 157                                         if (end == null)
 158                                                 break;
 159                                 }
 160                         } while (Interlocked.CompareExchange (ref head, end, temp) != temp);
 161
 162                         int i;
 163                         for (i = startIndex; i < startIndex + count && temp != null; i++) {
 164                                 items[i] = temp.Value;
 165                                 end = temp;
 166                                 temp = temp.Next;
 167                         }
 168                         Interlocked.Add (ref this.count, -(i - startIndex));
 169
 170                         return i - startIndex;
 171                 }
 172
 173                 public bool TryPeek (out T result)
 174                 {
 175                         Node myHead = head;
 176                         if (myHead == null) {
 177                                 result = default (T);
 178                                 return false;
 179                         }
 180                         result = myHead.Value;
 181                         return true;
 182                 }
 183
 184                 public void Clear ()
 185                 {
 186                         // This is not satisfactory
 187                         count = 0;
 188                         head = null;
 189                 }
 190
 191                 IEnumerator IEnumerable.GetEnumerator ()
 192                 {
 193                         return (IEnumerator)InternalGetEnumerator ();
 194                 }
 195
 196                 public IEnumerator<T> GetEnumerator ()
 197                 {
 198                         return InternalGetEnumerator ();
 199                 }
 200
 201                 IEnumerator<T> InternalGetEnumerator ()
 202                 {
 203                         Node my_head = head;
 204                         if (my_head == null) {
 205                                 yield break;
 206                         } else {
 207                                 do {
 208                                         yield return my_head.Value;
 209                                 } while ((my_head = my_head.Next) != null);
 210                         }
 211                 }
 212
 213                 void ICollection.CopyTo (Array array, int index)
 214                 {
 215                         ICollection ic = new List<T> (this);
 216                         ic.CopyTo (array, index);
 217                 }
 218
 219                 public void CopyTo (T[] array, int index)
 220                 {
 221                         if (array == null)
 222                                 throw new ArgumentNullException ("array");
 223                         if (index < 0)
 224                                 throw new ArgumentOutOfRangeException ("index");
 225                         if (index > array.Length)
 226                                 throw new ArgumentException ("index is equals or greather than array length", "index");
 227
 228                         IEnumerator<T> e = InternalGetEnumerator ();
 229                         int i = index;
 230                         while (e.MoveNext ()) {
 231                                 if (i == array.Length - index)
 232                                         throw new ArgumentException ("The number of elememts in the collection exceeds the capacity of array", "array");
 233                                 array[i++] = e.Current;
 234                         }
 235                 }
 236
 237                 bool ICollection.IsSynchronized {
 238                         get { return false; }
 239                 }
 240
 241                 bool IProducerConsumerCollection<T>.TryTake (out T item)
 242                 {
 243                         return TryPop (out item);
 244                 }
 245
 246                 object ICollection.SyncRoot {
 247                         get {
 248                                 throw new NotSupportedException ();
 249                         }
 250                 }
 251
 252                 public T[] ToArray ()
 253                 {
 254                         return new List<T> (this).ToArray ();
 255                 }
 256
 257                 public int Count {
 258                         get {
 259                                 return count;
 260                         }
 261                 }
 262
 263                 public bool IsEmpty {
 264                         get {
 265                                 return count == 0;
 266                         }
 267                 }
 268
 269                 static void RangeArgumentsCheck (T[] items, int startIndex, int count)
 270                 {
 271                         if (items == null)
 272                                 throw new ArgumentNullException ("items");
 273                         if (startIndex < 0 || startIndex >= items.Length)
 274                                 throw new ArgumentOutOfRangeException ("startIndex");
 275                         if (count < 0)
 276                                 throw new ArgumentOutOfRangeException ("count");
 277                         if (startIndex + count > items.Length)
 278                                 throw new ArgumentException ("startIndex + count is greater than the length of items.");
 279                 }
 280         }
 281 }
 282 #endif