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