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