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

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