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

   1 // ConcurrentStack.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 ConcurrentStack<T> : IProducerConsumerCollection<T>, IEnumerable<T>,
  39                                           ICollection, IEnumerable
  40         {
  41                 class Node
  42                 {
  43                         public T Value = default (T);
  44                         public Node Next = null;
  45                 }
  46
  47                 Node head = null;
  48
  49                 int count;
  50
  51                 public ConcurrentStack ()
  52                 {
  53                 }
  54
  55                 public ConcurrentStack (IEnumerable<T> collection)
  56                 {
  57                         foreach (T item in collection)
  58                                 Push (item);
  59                 }
  60
  61                 bool IProducerConsumerCollection<T>.TryAdd (T elem)
  62                 {
  63                         Push (elem);
  64                         return true;
  65                 }
  66
  67                 public void Push (T item)
  68                 {
  69                         Node temp = new Node ();
  70                         temp.Value = item;
  71                         do {
  72                           temp.Next = head;
  73                         } while (Interlocked.CompareExchange (ref head, temp, temp.Next) != temp.Next);
  74
  75                         Interlocked.Increment (ref count);
  76                 }
  77
  78                 public void PushRange (T[] items)
  79                 {
  80                         PushRange (items, 0, items.Length);
  81                 }
  82
  83                 public void PushRange (T[] items, int startIndex, int count)
  84                 {
  85                         Node insert = null;
  86                         Node first = null;
  87
  88                         for (int i = startIndex; i < count; i++) {
  89                                 Node temp = new Node ();
  90                                 temp.Value = items[i];
  91                                 temp.Next = insert;
  92                                 insert = temp;
  93
  94                                 if (first == null)
  95                                         first = temp;
  96                         }
  97
  98                         do {
  99                                 first.Next = head;
 100                         } while (Interlocked.CompareExchange (ref head, insert, first.Next) != first.Next);
 101
 102                         Interlocked.Add (ref count, count);
 103                 }
 104
 105                 public bool TryPop (out T result)
 106                 {
 107                         Node temp;
 108                         do {
 109                                 temp = head;
 110                                 // The stak is empty
 111                                 if (temp == null) {
 112                                         result = default (T);
 113                                         return false;
 114                                 }
 115                         } while (Interlocked.CompareExchange (ref head, temp.Next, temp) != temp);
 116
 117                         Interlocked.Decrement (ref count);
 118
 119                         result = temp.Value;
 120
 121                         return true;
 122                 }
 123
 124                 public int TryPopRange (T[] items)
 125                 {
 126                         if (items == null)
 127                                 throw new ArgumentNullException ("items");
 128                         return TryPopRange (items, 0, items.Length);
 129                 }
 130
 131                 public int TryPopRange (T[] items, int startIndex, int count)
 132                 {
 133                         if (items == null)
 134                                 throw new ArgumentNullException ("items");
 135                         if (startIndex < 0 || startIndex >= items.Length)
 136                                 throw new ArgumentOutOfRangeException ("startIndex");
 137                         if (count < 0)
 138                                 throw new ArgumentOutOfRangeException ("count");
 139                         if (startIndex + count > items.Length)
 140                                 throw new ArgumentException ("startIndex + count is greater than the length of items.");
 141
 142                         Node temp;
 143                         Node end;
 144
 145                         do {
 146                                 temp = head;
 147                                 if (temp == null)
 148                                         return -1;
 149                                 end = temp;
 150                                 for (int j = 0; j < count; j++) {
 151                                         end = end.Next;
 152                                         if (end == null)
 153                                                 break;
 154                                 }
 155                         } while (Interlocked.CompareExchange (ref head, end, temp) != temp);
 156
 157                         int i;
 158                         for (i = startIndex; i < startIndex + count && temp != null; i++) {
 159                                 items[i] = temp.Value;
 160                                 end = temp;
 161                                 temp = temp.Next;
 162                         }
 163                         Interlocked.Add (ref this.count, -(i - startIndex));
 164
 165                         return i - startIndex;
 166                 }
 167
 168                 public bool TryPeek (out T result)
 169                 {
 170                         Node myHead = head;
 171                         if (myHead == null) {
 172                                 result = default (T);
 173                                 return false;
 174                         }
 175                         result = myHead.Value;
 176                         return true;
 177                 }
 178
 179                 public void Clear ()
 180                 {
 181                         // This is not satisfactory
 182                         count = 0;
 183                         head = null;
 184                 }
 185
 186                 IEnumerator IEnumerable.GetEnumerator ()
 187                 {
 188                         return (IEnumerator)InternalGetEnumerator ();
 189                 }
 190
 191                 public IEnumerator<T> GetEnumerator ()
 192                 {
 193                         return InternalGetEnumerator ();
 194                 }
 195
 196                 IEnumerator<T> InternalGetEnumerator ()
 197                 {
 198                         Node my_head = head;
 199                         if (my_head == null) {
 200                                 yield break;
 201                         } else {
 202                                 do {
 203                                         yield return my_head.Value;
 204                                 } while ((my_head = my_head.Next) != null);
 205                         }
 206                 }
 207
 208                 void ICollection.CopyTo (Array array, int index)
 209                 {
 210                         if (array == null)
 211                                 throw new ArgumentNullException ("array");
 212                         if (array.Rank > 1)
 213                                 throw new ArgumentException ("The array can't be multidimensional");
 214                         if (array.GetLowerBound (0) != 0)
 215                                 throw new ArgumentException ("The array needs to be 0-based");
 216
 217                         T[] dest = array as T[];
 218                         if (dest == null)
 219                                 throw new ArgumentException ("The array cannot be cast to the collection element type", "array");
 220                         CopyTo (dest, index);
 221                 }
 222
 223                 public void CopyTo (T[] array, int index)
 224                 {
 225                         if (array == null)
 226                                 throw new ArgumentNullException ("array");
 227                         if (index < 0)
 228                                 throw new ArgumentOutOfRangeException ("index");
 229                         if (index >= array.Length)
 230                                 throw new ArgumentException ("index is equals or greather than array length", "index");
 231
 232                         IEnumerator<T> e = InternalGetEnumerator ();
 233                         int i = index;
 234                         while (e.MoveNext ()) {
 235                                 if (i == array.Length - index)
 236                                         throw new ArgumentException ("The number of elememts in the collection exceeds the capacity of array", "array");
 237                                 array[i++] = e.Current;
 238                         }
 239                 }
 240
 241                 bool ICollection.IsSynchronized {
 242                         get { return true; }
 243                 }
 244
 245                 bool IProducerConsumerCollection<T>.TryTake (out T item)
 246                 {
 247                         return TryPop (out item);
 248                 }
 249
 250                 object syncRoot = new object ();
 251                 object ICollection.SyncRoot {
 252                         get { return syncRoot; }
 253                 }
 254
 255                 public T[] ToArray ()
 256                 {
 257                         return new List<T> (this).ToArray ();
 258                 }
 259
 260                 public int Count {
 261                         get {
 262                                 return count;
 263                         }
 264                 }
 265
 266                 public bool IsEmpty {
 267                         get {
 268                                 return count == 0;
 269                         }
 270                 }
 271         }
 272 }
 273 #endif