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

   1 // ConcurrentDictionary.cs
   2 //
   3 // Copyright (c) 2009 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 using System.Diagnostics;
  33
  34 namespace System.Collections.Concurrent
  35 {
  36         [DebuggerDisplay ("Count={Count}")]
  37         [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
  38         public class ConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>,
  39           ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>,
  40           IDictionary, ICollection, IEnumerable
  41         {
  42                 IEqualityComparer<TKey> comparer;
  43
  44                 SplitOrderedList<TKey, KeyValuePair<TKey, TValue>> internalDictionary;
  45
  46                 public ConcurrentDictionary () : this (EqualityComparer<TKey>.Default)
  47                 {
  48                 }
  49
  50                 public ConcurrentDictionary (IEnumerable<KeyValuePair<TKey, TValue>> collection)
  51                         : this (collection, EqualityComparer<TKey>.Default)
  52                 {
  53                         foreach (KeyValuePair<TKey, TValue> pair in collection)
  54                                 Add (pair.Key, pair.Value);
  55                 }
  56
  57                 public ConcurrentDictionary (IEqualityComparer<TKey> comparer)
  58                 {
  59                         this.comparer = comparer;
  60                         this.internalDictionary = new SplitOrderedList<TKey, KeyValuePair<TKey, TValue>> (comparer);
  61                 }
  62
  63                 public ConcurrentDictionary (IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer)
  64                         : this (comparer)
  65                 {
  66                         foreach (KeyValuePair<TKey, TValue> pair in collection)
  67                                 Add (pair.Key, pair.Value);
  68                 }
  69
  70                 // Parameters unused
  71                 public ConcurrentDictionary (int concurrencyLevel, int capacity)
  72                         : this (EqualityComparer<TKey>.Default)
  73                 {
  74
  75                 }
  76
  77                 public ConcurrentDictionary (int concurrencyLevel,
  78                                              IEnumerable<KeyValuePair<TKey, TValue>> collection,
  79                                              IEqualityComparer<TKey> comparer)
  80                         : this (collection, comparer)
  81                 {
  82
  83                 }
  84
  85                 // Parameters unused
  86                 public ConcurrentDictionary (int concurrencyLevel, int capacity, IEqualityComparer<TKey> comparer)
  87                         : this (comparer)
  88                 {
  89
  90                 }
  91
  92                 void Add (TKey key, TValue value)
  93                 {
  94                         while (!TryAdd (key, value));
  95                 }
  96
  97                 void IDictionary<TKey, TValue>.Add (TKey key, TValue value)
  98                 {
  99                         Add (key, value);
 100                 }
 101
 102                 public bool TryAdd (TKey key, TValue value)
 103                 {
 104                         return internalDictionary.Insert (Hash (key), key, Make (key, value));
 105                 }
 106
 107                 void ICollection<KeyValuePair<TKey,TValue>>.Add (KeyValuePair<TKey, TValue> pair)
 108                 {
 109                         Add (pair.Key, pair.Value);
 110                 }
 111
 112                 public TValue AddOrUpdate (TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory)
 113                 {
 114                         return internalDictionary.InsertOrUpdate (Hash (key),
 115                                                                   key,
 116                                                                   () => Make (key, addValueFactory (key)),
 117                                                                   (e) => Make (key, updateValueFactory (key, e.Value))).Value;
 118                 }
 119
 120                 public TValue AddOrUpdate (TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory)
 121                 {
 122                         return AddOrUpdate (key, (_) => addValue, updateValueFactory);
 123                 }
 124
 125                 TValue AddOrUpdate (TKey key, TValue addValue, TValue updateValue)
 126                 {
 127                         return internalDictionary.InsertOrUpdate (Hash (key),
 128                                                                   key,
 129                                                                   Make (key, addValue),
 130                                                                   Make (key, updateValue)).Value;
 131                 }
 132
 133                 TValue GetValue (TKey key)
 134                 {
 135                         TValue temp;
 136                         if (!TryGetValue (key, out temp))
 137                                 throw new KeyNotFoundException (key.ToString ());
 138                         return temp;
 139                 }
 140
 141                 public bool TryGetValue (TKey key, out TValue value)
 142                 {
 143                         KeyValuePair<TKey, TValue> pair;
 144                         bool result = internalDictionary.Find (Hash (key), key, out pair);
 145                         value = pair.Value;
 146
 147                         return result;
 148                 }
 149
 150                 public bool TryUpdate (TKey key, TValue newValue, TValue comparisonValue)
 151                 {
 152                         return internalDictionary.CompareExchange (Hash (key), key, Make (key, newValue), (e) => e.Value.Equals (comparisonValue));
 153                 }
 154
 155                 public TValue this[TKey key] {
 156                         get {
 157                                 return GetValue (key);
 158                         }
 159                         set {
 160                                 AddOrUpdate (key, value, value);
 161                         }
 162                 }
 163
 164                 public TValue GetOrAdd (TKey key, Func<TKey, TValue> valueFactory)
 165                 {
 166                         return internalDictionary.InsertOrGet (Hash (key), key, Make (key, default(TValue)), () => Make (key, valueFactory (key))).Value;
 167                 }
 168
 169                 public TValue GetOrAdd (TKey key, TValue value)
 170                 {
 171                         return internalDictionary.InsertOrGet (Hash (key), key, Make (key, value), null).Value;
 172                 }
 173
 174                 public bool TryRemove (TKey key, out TValue value)
 175                 {
 176                         KeyValuePair<TKey, TValue> data;
 177                         bool result = internalDictionary.Delete (Hash (key), key, out data);
 178                         value = data.Value;
 179                         return result;
 180                 }
 181
 182                 bool Remove (TKey key)
 183                 {
 184                         TValue dummy;
 185
 186                         return TryRemove (key, out dummy);
 187                 }
 188
 189                 bool IDictionary<TKey, TValue>.Remove (TKey key)
 190                 {
 191                         return Remove (key);
 192                 }
 193
 194                 bool ICollection<KeyValuePair<TKey,TValue>>.Remove (KeyValuePair<TKey,TValue> pair)
 195                 {
 196                         return Remove (pair.Key);
 197                 }
 198
 199                 public bool ContainsKey (TKey key)
 200                 {
 201                         KeyValuePair<TKey, TValue> dummy;
 202                         return internalDictionary.Find (Hash (key), key, out dummy);
 203                 }
 204
 205                 bool IDictionary.Contains (object key)
 206                 {
 207                         if (!(key is TKey))
 208                                 return false;
 209
 210                         return ContainsKey ((TKey)key);
 211                 }
 212
 213                 void IDictionary.Remove (object key)
 214                 {
 215                         if (!(key is TKey))
 216                                 return;
 217
 218                         Remove ((TKey)key);
 219                 }
 220
 221                 object IDictionary.this [object key]
 222                 {
 223                         get {
 224                                 if (!(key is TKey))
 225                                         throw new ArgumentException ("key isn't of correct type", "key");
 226
 227                                 return this[(TKey)key];
 228                         }
 229                         set {
 230                                 if (!(key is TKey) || !(value is TValue))
 231                                         throw new ArgumentException ("key or value aren't of correct type");
 232
 233                                 this[(TKey)key] = (TValue)value;
 234                         }
 235                 }
 236
 237                 void IDictionary.Add (object key, object value)
 238                 {
 239                         if (!(key is TKey) || !(value is TValue))
 240                                 throw new ArgumentException ("key or value aren't of correct type");
 241
 242                         Add ((TKey)key, (TValue)value);
 243                 }
 244
 245                 bool ICollection<KeyValuePair<TKey,TValue>>.Contains (KeyValuePair<TKey, TValue> pair)
 246                 {
 247                         return ContainsKey (pair.Key);
 248                 }
 249
 250                 public KeyValuePair<TKey,TValue>[] ToArray ()
 251                 {
 252                         // This is most certainly not optimum but there is
 253                         // not a lot of possibilities
 254
 255                         return new List<KeyValuePair<TKey,TValue>> (this).ToArray ();
 256                 }
 257
 258                 public void Clear()
 259                 {
 260                         // Pronk
 261                         internalDictionary = new SplitOrderedList<TKey, KeyValuePair<TKey, TValue>> (comparer);
 262                 }
 263
 264                 public int Count {
 265                         get {
 266                                 return internalDictionary.Count;
 267                         }
 268                 }
 269
 270                 public bool IsEmpty {
 271                         get {
 272                                 return Count == 0;
 273                         }
 274                 }
 275
 276                 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 277                         get {
 278                                 return false;
 279                         }
 280                 }
 281
 282                 bool IDictionary.IsReadOnly {
 283                         get {
 284                                 return false;
 285                         }
 286                 }
 287
 288                 public ICollection<TKey> Keys {
 289                         get {
 290                                 return GetPart<TKey> ((kvp) => kvp.Key);
 291                         }
 292                 }
 293
 294                 public ICollection<TValue> Values {
 295                         get {
 296                                 return GetPart<TValue> ((kvp) => kvp.Value);
 297                         }
 298                 }
 299
 300                 ICollection IDictionary.Keys {
 301                         get {
 302                                 return (ICollection)Keys;
 303                         }
 304                 }
 305
 306                 ICollection IDictionary.Values {
 307                         get {
 308                                 return (ICollection)Values;
 309                         }
 310                 }
 311
 312                 ICollection<T> GetPart<T> (Func<KeyValuePair<TKey, TValue>, T> extractor)
 313                 {
 314                         List<T> temp = new List<T> ();
 315
 316                         foreach (KeyValuePair<TKey, TValue> kvp in this)
 317                                 temp.Add (extractor (kvp));
 318
 319                         return temp.AsReadOnly ();
 320                 }
 321
 322                 void ICollection.CopyTo (Array array, int startIndex)
 323                 {
 324                         KeyValuePair<TKey, TValue>[] arr = array as KeyValuePair<TKey, TValue>[];
 325                         if (arr == null)
 326                                 return;
 327
 328                         CopyTo (arr, startIndex, Count);
 329                 }
 330
 331                 void CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex)
 332                 {
 333                         CopyTo (array, startIndex, Count);
 334                 }
 335
 336                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex)
 337                 {
 338                         CopyTo (array, startIndex);
 339                 }
 340
 341                 void CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex, int num)
 342                 {
 343                         foreach (var kvp in this) {
 344                                 array [startIndex++] = kvp;
 345
 346                                 if (--num <= 0)
 347                                         return;
 348                         }
 349                 }
 350
 351                 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
 352                 {
 353                         return GetEnumeratorInternal ();
 354                 }
 355
 356                 IEnumerator IEnumerable.GetEnumerator ()
 357                 {
 358                         return (IEnumerator)GetEnumeratorInternal ();
 359                 }
 360
 361                 IEnumerator<KeyValuePair<TKey, TValue>> GetEnumeratorInternal ()
 362                 {
 363                         return internalDictionary.GetEnumerator ();
 364                 }
 365
 366                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 367                 {
 368                         return new ConcurrentDictionaryEnumerator (GetEnumeratorInternal ());
 369                 }
 370
 371                 class ConcurrentDictionaryEnumerator : IDictionaryEnumerator
 372                 {
 373                         IEnumerator<KeyValuePair<TKey, TValue>> internalEnum;
 374
 375                         public ConcurrentDictionaryEnumerator (IEnumerator<KeyValuePair<TKey, TValue>> internalEnum)
 376                         {
 377                                 this.internalEnum = internalEnum;
 378                         }
 379
 380                         public bool MoveNext ()
 381                         {
 382                                 return internalEnum.MoveNext ();
 383                         }
 384
 385                         public void Reset ()
 386                         {
 387                                 internalEnum.Reset ();
 388                         }
 389
 390                         public object Current {
 391                                 get {
 392                                         return Entry;
 393                                 }
 394                         }
 395
 396                         public DictionaryEntry Entry {
 397                                 get {
 398                                         KeyValuePair<TKey, TValue> current = internalEnum.Current;
 399                                         return new DictionaryEntry (current.Key, current.Value);
 400                                 }
 401                         }
 402
 403                         public object Key {
 404                                 get {
 405                                         return internalEnum.Current.Key;
 406                                 }
 407                         }
 408
 409                         public object Value {
 410                                 get {
 411                                         return internalEnum.Current.Value;
 412                                 }
 413                         }
 414                 }
 415
 416                 object ICollection.SyncRoot {
 417                         get {
 418                                 return this;
 419                         }
 420                 }
 421
 422                 bool IDictionary.IsFixedSize {
 423                         get {
 424                                 return false;
 425                         }
 426                 }
 427
 428                 bool ICollection.IsSynchronized {
 429                         get { return true; }
 430                 }
 431
 432                 static KeyValuePair<U, V> Make<U, V> (U key, V value)
 433                 {
 434                         return new KeyValuePair<U, V> (key, value);
 435                 }
 436
 437                 uint Hash (TKey key)
 438                 {
 439                         return (uint)comparer.GetHashCode (key);
 440                 }
 441         }
 442 }
 443 #endif