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 || MOBILE
  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                 class NodeObjectPool : ObjectPool<Node> {
  52                         protected override Node Creator ()
  53                         {
  54                                 return new Node ();
  55                         }
  56                 }
  57                 static readonly NodeObjectPool pool = new NodeObjectPool ();
  58
  59                 static Node ZeroOut (Node node)
  60                 {
  61                         node.Value = default(T);
  62                         node.Next = null;
  63                         return node;
  64                 }
  65
  66                 public ConcurrentStack ()
  67                 {
  68                 }
  69
  70                 public ConcurrentStack (IEnumerable<T> collection)
  71                 {
  72                         foreach (T item in collection)
  73                                 Push (item);
  74                 }
  75
  76                 bool IProducerConsumerCollection<T>.TryAdd (T elem)
  77                 {
  78                         Push (elem);
  79                         return true;
  80                 }
  81
  82                 public void Push (T item)
  83                 {
  84                         Node temp = pool.Take ();
  85                         temp.Value = item;
  86                         do {
  87                           temp.Next = head;
  88                         } while (Interlocked.CompareExchange (ref head, temp, temp.Next) != temp.Next);
  89
  90                         Interlocked.Increment (ref count);
  91                 }
  92
  93                 public void PushRange (T[] items)
  94                 {
  95                         PushRange (items, 0, items.Length);
  96                 }
  97
  98                 public void PushRange (T[] items, int startIndex, int count)
  99                 {
 100                         Node insert = null;
 101                         Node first = null;
 102
 103                         for (int i = startIndex; i < count; i++) {
 104                                 Node temp = pool.Take ();
 105                                 temp.Value = items[i];
 106                                 temp.Next = insert;
 107                                 insert = temp;
 108
 109                                 if (first == null)
 110                                         first = temp;
 111                         }
 112
 113                         do {
 114                                 first.Next = head;
 115                         } while (Interlocked.CompareExchange (ref head, insert, first.Next) != first.Next);
 116
 117                         Interlocked.Add (ref count, count);
 118                 }
 119
 120                 public bool TryPop (out T result)
 121                 {
 122                         Node temp;
 123                         do {
 124                                 temp = head;
 125                                 // The stak is empty
 126                                 if (temp == null) {
 127                                         result = default (T);
 128                                         return false;
 129                                 }
 130                         } while (Interlocked.CompareExchange (ref head, temp.Next, temp) != temp);
 131
 132                         Interlocked.Decrement (ref count);
 133
 134                         result = temp.Value;
 135                         pool.Release (ZeroOut (temp));
 136
 137                         return true;
 138                 }
 139
 140                 public int TryPopRange (T[] items)
 141                 {
 142                         return TryPopRange (items, 0, items.Length);
 143                 }
 144
 145                 public int TryPopRange (T[] items, int startIndex, int count)
 146                 {
 147                         Node temp;
 148                         Node end;
 149
 150                         do {
 151                                 temp = head;
 152                                 if (temp == null)
 153                                         return -1;
 154                                 end = temp;
 155                                 for (int j = 0; j < count - 1; 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 < count && temp != null; i++) {
 164                                 items[i] = temp.Value;
 165                                 end = temp;
 166                                 temp = temp.Next;
 167                                 pool.Release (ZeroOut (end));
 168                         }
 169
 170                         return i - 1;
 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                         T[] dest = array as T[];
 216                         if (dest == null)
 217                                 return;
 218                         CopyTo (dest, index);
 219                 }
 220
 221                 public void CopyTo (T[] array, int index)
 222                 {
 223                         IEnumerator<T> e = InternalGetEnumerator ();
 224                         int i = index;
 225                         while (e.MoveNext ()) {
 226                                 array[i++] = e.Current;
 227                         }
 228                 }
 229
 230                 bool ICollection.IsSynchronized {
 231                         get { return true; }
 232                 }
 233
 234                 bool IProducerConsumerCollection<T>.TryTake (out T item)
 235                 {
 236                         return TryPop (out item);
 237                 }
 238
 239                 object syncRoot = new object ();
 240                 object ICollection.SyncRoot {
 241                         get { return syncRoot; }
 242                 }
 243
 244                 public T[] ToArray ()
 245                 {
 246                         T[] dest = new T [count];
 247                         CopyTo (dest, 0);
 248                         return dest;
 249                 }
 250
 251                 public int Count {
 252                         get {
 253                                 return count;
 254                         }
 255                 }
 256
 257                 public bool IsEmpty {
 258                         get {
 259                                 return count == 0;
 260                         }
 261                 }
 262         }
 263 }
 264 #endif