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
  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                 public bool TryPop (out T value)
 104                 {
 105                         Node temp;
 106                         do {
 107                                 temp = head;
 108                                 // The stak is empty
 109                                 if (temp == null) {
 110                                         value = default (T);
 111                                         return false;
 112                                 }
 113                         } while (Interlocked.CompareExchange (ref head, temp.Next, temp) != temp);
 114
 115                         Interlocked.Decrement (ref count);
 116
 117                         value = temp.Value;
 118                         return true;
 119                 }
 120
 121                 public int TryPopRange (T[] values)
 122                 {
 123                         return TryPopRange (values, 0, values.Length);
 124                 }
 125
 126                 public int TryPopRange (T[] values, int startIndex, int count)
 127                 {
 128                         Node temp;
 129                         Node end;
 130
 131                         do {
 132                                 temp = head;
 133                                 if (temp == null)
 134                                         return -1;
 135                                 end = temp;
 136                                 for (int j = 0; j < count - 1; j++) {
 137                                         end = end.Next;
 138                                         if (end == null)
 139                                                 break;
 140                                 }
 141                         } while (Interlocked.CompareExchange (ref head, end, temp) != temp);
 142
 143                         int i;
 144                         for (i = startIndex; i < count && temp != null; i++) {
 145                                 values[i] = temp.Value;
 146                                 temp = temp.Next;
 147                         }
 148
 149                         return i - 1;
 150                 }
 151
 152                 public bool TryPeek (out T value)
 153                 {
 154                         Node myHead = head;
 155                         if (myHead == null) {
 156                                 value = default (T);
 157                                 return false;
 158                         }
 159                         value = myHead.Value;
 160                         return true;
 161                 }
 162
 163                 public void Clear ()
 164                 {
 165                         // This is not satisfactory
 166                         count = 0;
 167                         head = null;
 168                 }
 169
 170                 IEnumerator IEnumerable.GetEnumerator ()
 171                 {
 172                         return (IEnumerator)InternalGetEnumerator ();
 173                 }
 174
 175                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 176                 {
 177                         return InternalGetEnumerator ();
 178                 }
 179
 180                 public IEnumerator<T> GetEnumerator ()
 181                 {
 182                         return InternalGetEnumerator ();
 183                 }
 184
 185                 IEnumerator<T> InternalGetEnumerator ()
 186                 {
 187                         Node my_head = head;
 188                         if (my_head == null) {
 189                                 yield break;
 190                         } else {
 191                                 do {
 192                                         yield return my_head.Value;
 193                                 } while ((my_head = my_head.Next) != null);
 194                         }
 195                 }
 196
 197                 void ICollection.CopyTo (Array array, int index)
 198                 {
 199                         T[] dest = array as T[];
 200                         if (dest == null)
 201                                 return;
 202                         CopyTo (dest, index);
 203                 }
 204
 205                 public void CopyTo (T[] dest, int index)
 206                 {
 207                         IEnumerator<T> e = InternalGetEnumerator ();
 208                         int i = index;
 209                         while (e.MoveNext ()) {
 210                                 dest[i++] = e.Current;
 211                         }
 212                 }
 213
 214                 bool ICollection.IsSynchronized {
 215                         get { return true; }
 216                 }
 217
 218                 bool IProducerConsumerCollection<T>.TryTake (out T item)
 219                 {
 220                         return TryPop (out item);
 221                 }
 222
 223                 object syncRoot = new object ();
 224                 object ICollection.SyncRoot {
 225                         get { return syncRoot; }
 226                 }
 227
 228                 public T[] ToArray ()
 229                 {
 230                         T[] dest = new T [count];
 231                         CopyTo (dest, 0);
 232                         return dest;
 233                 }
 234
 235                 public int Count {
 236                         get {
 237                                 return count;
 238                         }
 239                 }
 240
 241                 public bool IsEmpty {
 242                         get {
 243                                 return count == 0;
 244                         }
 245                 }
 246         }
 247 }
 248 #endif