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