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