mcs/class/Mono.Parallel/Mono.Collections.Concurrent/ConcurrentOrderedList.cs

   1 // ConcurrentOrderedList.cs
   2 //
   3 // Copyright (c) 2010 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
  26 using System;
  27 using System.Threading;
  28 using System.Collections;
  29 using System.Collections.Generic;
  30 using System.Runtime.Serialization;
  31
  32 #if INSIDE_MONO_PARALLEL
  33 using System.Collections.Concurrent;
  34
  35 namespace Mono.Collections.Concurrent
  36 #else
  37 namespace System.Collections.Concurrent
  38 #endif
  39 {
  40 #if INSIDE_MONO_PARALLEL
  41         public
  42 #endif
  43         class ConcurrentOrderedList<T>: ICollection<T>, IEnumerable<T>
  44         {
  45                 class Node
  46                 {
  47                         public T Data;
  48                         public int Key;
  49                         public Node Next;
  50                         public bool Marked;
  51
  52                         public Node ()
  53                         {
  54
  55                         }
  56
  57                         public Node (Node wrapped)
  58                         {
  59                                 Marked = true;
  60                                 Next = wrapped;
  61                         }
  62                 }
  63
  64                 Node head;
  65                 Node tail;
  66
  67                 IEqualityComparer<T> comparer;
  68
  69                 int count;
  70
  71                 public ConcurrentOrderedList () : this (EqualityComparer<T>.Default)
  72                 {
  73
  74                 }
  75
  76                 public ConcurrentOrderedList (IEqualityComparer<T> comparer)
  77                 {
  78                         if (comparer == null)
  79                                 throw new ArgumentNullException ("comparer");
  80
  81                         this.comparer = comparer;
  82
  83                         head = new Node ();
  84                         tail = new Node ();
  85                         head.Next = tail;
  86                 }
  87
  88                 public bool TryAdd (T data)
  89                 {
  90                         Node node = new Node ();
  91                         node.Data = data;
  92                         node.Key = comparer.GetHashCode (data);
  93
  94                         if (ListInsert (node)) {
  95                                 Interlocked.Increment (ref count);
  96                                 return true;
  97                         }
  98
  99                         return false;
 100                 }
 101
 102                 public bool TryRemove (T data)
 103                 {
 104                         T dummy;
 105                         return TryRemoveHash (comparer.GetHashCode (data), out dummy);
 106                 }
 107
 108                 public bool TryRemoveHash (int key, out T data)
 109                 {
 110                         if (ListDelete (key, out data)) {
 111                                 Interlocked.Decrement (ref count);
 112                                 return true;
 113                         }
 114
 115                         return false;
 116                 }
 117
 118                 public bool TryPop (out T data)
 119                 {
 120                         return ListPop (out data);
 121                 }
 122
 123                 public bool Contains (T data)
 124                 {
 125                         return ContainsHash (comparer.GetHashCode (data));
 126                 }
 127
 128                 public bool ContainsHash (int key)
 129                 {
 130                         Node node;
 131
 132                         if (!ListFind (key, out node))
 133                                 return false;
 134
 135                         return true;
 136
 137                 }
 138
 139                 public bool TryGetFromHash (int key, out T data)
 140                 {
 141                         data = default (T);
 142                         Node node;
 143
 144                         if (!ListFind (key, out node))
 145                                 return false;
 146
 147                         data = node.Data;
 148                         return true;
 149                 }
 150
 151                 public void Clear ()
 152                 {
 153                         head.Next = tail;
 154                 }
 155
 156                 public void CopyTo (T[] array, int startIndex)
 157                 {
 158                         if (array == null)
 159                                 throw new ArgumentNullException ("array");
 160                         if (startIndex < 0)
 161                                 throw new ArgumentOutOfRangeException ("startIndex");
 162                         if (count > array.Length - startIndex)
 163                                 throw new ArgumentException ("array", "The number of elements is greater than the available space from startIndex to the end of the destination array.");
 164
 165                         foreach (T item in this) {
 166                                 if (startIndex >= array.Length)
 167                                         break;
 168
 169                                 array[startIndex++] = item;
 170                         }
 171                 }
 172
 173                 public IEqualityComparer<T> Comparer {
 174                         get {
 175                                 return comparer;
 176                         }
 177                 }
 178
 179                 public int Count {
 180                         get {
 181                                 return count;
 182                         }
 183                 }
 184
 185                 Node ListSearch (int key, ref Node left)
 186                 {
 187                         Node leftNodeNext = null, rightNode = null;
 188
 189                         do {
 190                                 Node t = head;
 191                                 Node tNext = t.Next;
 192                                 do {
 193                                         if (!tNext.Marked) {
 194                                                 left = t;
 195                                                 leftNodeNext = tNext;
 196                                         }
 197                                         t = tNext.Marked ? tNext.Next : tNext;
 198                                         if (t == tail)
 199                                                 break;
 200
 201                                         tNext = t.Next;
 202                                 } while (tNext.Marked || t.Key < key);
 203
 204                                 rightNode = t;
 205
 206                                 if (leftNodeNext == rightNode) {
 207                                         if (rightNode != tail && rightNode.Next.Marked)
 208                                                 continue;
 209                                         else
 210                                                 return rightNode;
 211                                 }
 212
 213                                 if (Interlocked.CompareExchange (ref left.Next, rightNode, leftNodeNext) == leftNodeNext) {
 214                                         if (rightNode != tail && rightNode.Next.Marked)
 215                                                 continue;
 216                                         else
 217                                                 return rightNode;
 218                                 }
 219                         } while (true);
 220                 }
 221
 222                 bool ListDelete (int key, out T data)
 223                 {
 224                         Node rightNode = null, rightNodeNext = null, leftNode = null;
 225                         data = default (T);
 226
 227                         do {
 228                                 rightNode = ListSearch (key, ref leftNode);
 229                                 if (rightNode == tail || rightNode.Key != key)
 230                                         return false;
 231
 232                                 data = rightNode.Data;
 233
 234                                 rightNodeNext = rightNode.Next;
 235                                 if (!rightNodeNext.Marked)
 236                                         if (Interlocked.CompareExchange (ref rightNode.Next, new Node (rightNodeNext), rightNodeNext) == rightNodeNext)
 237                                                 break;
 238                         } while (true);
 239
 240                         if (Interlocked.CompareExchange (ref leftNode.Next, rightNodeNext, rightNode) != rightNodeNext)
 241                                 ListSearch (rightNode.Key, ref leftNode);
 242
 243                         return true;
 244                 }
 245
 246                 bool ListPop (out T data)
 247                 {
 248                         Node rightNode = null, rightNodeNext = null, leftNode = head;
 249                         data = default (T);
 250
 251                         do {
 252                                 rightNode = head.Next;
 253                                 if (rightNode == tail)
 254                                         return false;
 255
 256                                 data = rightNode.Data;
 257
 258                                 rightNodeNext = rightNode.Next;
 259                                 if (!rightNodeNext.Marked)
 260                                         if (Interlocked.CompareExchange (ref rightNode.Next, new Node (rightNodeNext), rightNodeNext) == rightNodeNext)
 261                                                 break;
 262                         } while (true);
 263
 264                         if (Interlocked.CompareExchange (ref leftNode.Next, rightNodeNext, rightNode) != rightNodeNext)
 265                                 ListSearch (rightNode.Key, ref leftNode);
 266
 267                         return true;
 268                 }
 269
 270                 bool ListInsert (Node newNode)
 271                 {
 272                         int key = newNode.Key;
 273                         Node rightNode = null, leftNode = null;
 274
 275                         do {
 276                                 rightNode = ListSearch (key, ref leftNode);
 277                                 if (rightNode != tail && rightNode.Key == key)
 278                                         return false;
 279
 280                                 newNode.Next = rightNode;
 281                                 if (Interlocked.CompareExchange (ref leftNode.Next, newNode, rightNode) == rightNode)
 282                                         return true;
 283                         } while (true);
 284                 }
 285
 286                 bool ListFind (int key, out Node data)
 287                 {
 288                         Node rightNode = null, leftNode = null;
 289                         data = null;
 290
 291                         data = rightNode = ListSearch (key, ref leftNode);
 292
 293                         return rightNode != tail && rightNode.Key == key;
 294                 }
 295
 296                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 297                 {
 298                         return GetEnumeratorInternal ();
 299                 }
 300
 301                 IEnumerator IEnumerable.GetEnumerator ()
 302                 {
 303                         return GetEnumeratorInternal ();
 304                 }
 305
 306                 IEnumerator<T> GetEnumeratorInternal ()
 307                 {
 308                         Node node = head.Next;
 309
 310                         while (node != tail) {
 311                                 while (node.Marked) {
 312                                         node = node.Next;
 313                                         if (node == tail)
 314                                                 yield break;
 315                                 }
 316                                 yield return node.Data;
 317                                 node = node.Next;
 318                         }
 319                 }
 320
 321                 bool ICollection<T>.IsReadOnly {
 322                         get {
 323                                 return false;
 324                         }
 325                 }
 326
 327                 void ICollection<T>.Add (T item)
 328                 {
 329                         TryAdd (item);
 330                 }
 331
 332                 bool ICollection<T>.Remove (T item)
 333                 {
 334                         return TryRemove (item);
 335                 }
 336         }
 337 }
 338