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

   1 #if NET_4_0
   2 // ConcurrentSkipList.cs
   3 //
   4 // Copyright (c) 2009 Jérémie "Garuma" Laval
   5 //
   6 // Permission is hereby granted, free of charge, to any person obtaining a copy
   7 // of this software and associated documentation files (the "Software"), to deal
   8 // in the Software without restriction, including without limitation the rights
   9 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10 // copies of the Software, and to permit persons to whom the Software is
  11 // furnished to do so, subject to the following conditions:
  12 //
  13 // The above copyright notice and this permission notice shall be included in
  14 // all copies or substantial portions of the Software.
  15 //
  16 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22 // THE SOFTWARE.
  23 //
  24 //
  25
  26 using System;
  27 using System.Threading;
  28 using System.Collections;
  29 using System.Collections.Generic;
  30 using System.Runtime.Serialization;
  31
  32 namespace System.Collections.Concurrent
  33 {
  34         public class ConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>,
  35           ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>,
  36           IDictionary, ICollection, IEnumerable
  37         {
  38                 class Pair
  39                 {
  40                         public readonly TKey Key;
  41                         public TValue Value;
  42
  43                         public Pair (TKey key, TValue value)
  44                         {
  45                                 Key = key;
  46                                 Value = value;
  47                         }
  48
  49                         public override bool Equals (object obj)
  50                         {
  51                                 Pair rhs = obj as Pair;
  52                                 return rhs == null ? false : Key.Equals (rhs.Key) && Value.Equals (rhs.Value);
  53                         }
  54
  55                         public override int GetHashCode ()
  56                         {
  57                                 return Key.GetHashCode ();
  58                         }
  59                 }
  60
  61                 class Basket: List<Pair>
  62                 {
  63                 }
  64
  65                 // Assumption: a List<T> is never empty
  66                 ConcurrentSkipList<Basket> container
  67                         = new ConcurrentSkipList<Basket> ((value) => value[0].GetHashCode ());
  68                 int count;
  69                 IEqualityComparer<TKey> comparer;
  70
  71                 public ConcurrentDictionary () : this (EqualityComparer<TKey>.Default)
  72                 {
  73                 }
  74
  75                 public ConcurrentDictionary (IEnumerable<KeyValuePair<TKey, TValue>> values)
  76                         : this (values, EqualityComparer<TKey>.Default)
  77                 {
  78                         foreach (KeyValuePair<TKey, TValue> pair in values)
  79                                 Add (pair.Key, pair.Value);
  80                 }
  81
  82                 public ConcurrentDictionary (IEqualityComparer<TKey> comparer)
  83                 {
  84                         this.comparer = comparer;
  85                 }
  86
  87                 public ConcurrentDictionary (IEnumerable<KeyValuePair<TKey, TValue>> values, IEqualityComparer<TKey> comparer)
  88                         : this (comparer)
  89                 {
  90                         foreach (KeyValuePair<TKey, TValue> pair in values)
  91                                 Add (pair.Key, pair.Value);
  92                 }
  93
  94                 // Parameters unused
  95                 public ConcurrentDictionary (int concurrencyLevel, int capacity)
  96                         : this (EqualityComparer<TKey>.Default)
  97                 {
  98
  99                 }
 100
 101                 public ConcurrentDictionary (int concurrencyLevel,
 102                                              IEnumerable<KeyValuePair<TKey, TValue>> values,
 103                                              IEqualityComparer<TKey> comparer)
 104                         : this (values, comparer)
 105                 {
 106
 107                 }
 108
 109                 // Parameters unused
 110                 public ConcurrentDictionary (int concurrencyLevel, int capacity, IEqualityComparer<TKey> comparer)
 111                         : this (comparer)
 112                 {
 113
 114                 }
 115
 116                 void Add (TKey key, TValue value)
 117                 {
 118                         while (!TryAdd (key, value));
 119                 }
 120
 121                 void IDictionary<TKey, TValue>.Add (TKey key, TValue value)
 122                 {
 123                         Add (key, value);
 124                 }
 125
 126                 public bool TryAdd (TKey key, TValue value)
 127                 {
 128                         Basket basket;
 129                         // Add a value to an existing basket
 130                         if (TryGetBasket (key, out basket)) {
 131                                 // Find a maybe more sexy locking scheme later
 132                                 lock (basket) {
 133                                         foreach (var p in basket) {
 134                                                 if (comparer.Equals (p.Key, key))
 135                                                         throw new ArgumentException ("An element with the same key already exists");
 136                                         }
 137                                         basket.Add (new Pair (key, value));
 138                                 }
 139                         } else {
 140                                 // Add a new basket
 141                                 basket = new Basket ();
 142                                 basket.Add (new Pair (key, value));
 143
 144                                 if (container.TryAdd (basket)) {
 145                                         Interlocked.Increment (ref count);
 146                                         return true;
 147                                 } else {
 148                                         return false;
 149                                 }
 150                         }
 151
 152                         Interlocked.Increment (ref count);
 153
 154                         return true;
 155                 }
 156
 157                 void ICollection<KeyValuePair<TKey,TValue>>.Add (KeyValuePair<TKey, TValue> pair)
 158                 {
 159                         Add (pair.Key, pair.Value);
 160                 }
 161
 162                 public TValue AddOrUpdate (TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory)
 163                 {
 164                         Basket basket;
 165                         TValue temp;
 166
 167                         if (!TryGetBasket (key, out basket)) {
 168                                 Add (key, (temp = addValueFactory (key)));
 169                         } else {
 170                                 lock (basket) {
 171                                         Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
 172                                         if (pair == null)
 173                                                 throw new InvalidOperationException ("pair is null, shouldn't be");
 174                                         pair.Value = (temp = updateValueFactory (key, pair.Value));
 175                                 }
 176                         }
 177
 178                         return temp;
 179                 }
 180
 181                 public TValue AddOrUpdate (TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory)
 182                 {
 183                         return AddOrUpdate (key, (_) => addValue, updateValueFactory);
 184                 }
 185
 186                 TValue GetValue (TKey key)
 187                 {
 188                         TValue temp;
 189                         if (!TryGetValue (key, out temp))
 190                                 // TODO: find a correct Exception
 191                                 throw new ArgumentException ("Not a valid key for this dictionary", "key");
 192                         return temp;
 193                 }
 194
 195                 public bool TryGetValue (TKey key, out TValue value)
 196                 {
 197                         Basket basket;
 198                         value = default (TValue);
 199
 200                         if (!TryGetBasket (key, out basket))
 201                                 return false;
 202
 203                         lock (basket) {
 204                                 Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
 205                                 if (pair == null)
 206                                         return false;
 207                                 value = pair.Value;
 208                         }
 209
 210                         return true;
 211                 }
 212
 213                 public bool TryUpdate (TKey key, TValue newValue, TValue comparand)
 214                 {
 215                         Basket basket;
 216                         if (!TryGetBasket (key, out basket))
 217                                 return false;
 218
 219                         lock (basket) {
 220                                 Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
 221                                 if (pair.Value.Equals (comparand)) {
 222                                         pair.Value = newValue;
 223
 224                                         return true;
 225                                 }
 226                         }
 227
 228                         return false;
 229                 }
 230
 231                 public TValue this[TKey key] {
 232                         get {
 233                                 return GetValue (key);
 234                         }
 235                         set {
 236                                 Basket basket;
 237                                 if (!TryGetBasket (key, out basket)) {
 238                                         Add (key, value);
 239                                         return;
 240                                 }
 241                                 lock (basket) {
 242                                         Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
 243                                         if (pair == null)
 244                                                 throw new InvalidOperationException ("pair is null, shouldn't be");
 245                                         pair.Value = value;
 246                                 }
 247                         }
 248                 }
 249
 250                 public TValue GetOrAdd (TKey key, Func<TKey, TValue> valueFactory)
 251                 {
 252                         Basket basket;
 253                         TValue temp = default (TValue);
 254
 255                         if (TryGetBasket (key, out basket)) {
 256                                 Pair pair = null;
 257                                 lock (basket) {
 258                                         pair = basket.Find ((p) => comparer.Equals (p.Key, key));
 259                                         if (pair != null)
 260                                                 temp = pair.Value;
 261                                 }
 262
 263                                 if (pair == null)
 264                                         Add (key, (temp = valueFactory (key)));
 265                         } else {
 266                                 Add (key, (temp = valueFactory (key)));
 267                         }
 268
 269                         return temp;
 270                 }
 271
 272                 public TValue GetOrAdd (TKey key, TValue value)
 273                 {
 274                         return GetOrAdd (key, (_) => value);
 275                 }
 276
 277                 public bool TryRemove(TKey key, out TValue value)
 278                 {
 279                         value = default (TValue);
 280                         Basket b;
 281
 282                         if (!TryGetBasket (key, out b))
 283                                 return false;
 284
 285                         lock (b) {
 286                                 TValue temp = default (TValue);
 287                                 // Should always be == 1 but who know
 288                                 bool result = b.RemoveAll ((p) => {
 289                                         bool r = comparer.Equals (p.Key, key);
 290                                         if (r) temp = p.Value;
 291                                         return r;
 292                                 }) >= 1;
 293                                 value = temp;
 294
 295                                 if (result)
 296                                         Interlocked.Decrement (ref count);
 297
 298                                 return result;
 299                         }
 300                 }
 301
 302                 bool Remove (TKey key)
 303                 {
 304                         TValue dummy;
 305
 306                         return TryRemove (key, out dummy);
 307                 }
 308
 309                 bool IDictionary<TKey, TValue>.Remove (TKey key)
 310                 {
 311                         return Remove (key);
 312                 }
 313
 314                 bool ICollection<KeyValuePair<TKey,TValue>>.Remove (KeyValuePair<TKey,TValue> pair)
 315                 {
 316                         return Remove (pair.Key);
 317                 }
 318
 319                 public bool ContainsKey (TKey key)
 320                 {
 321                         return container.ContainsFromHash (key.GetHashCode ());
 322                 }
 323
 324                 bool IDictionary.Contains (object key)
 325                 {
 326                         if (!(key is TKey))
 327                                 return false;
 328
 329                         return ContainsKey ((TKey)key);
 330                 }
 331
 332                 void IDictionary.Remove (object key)
 333                 {
 334                         if (!(key is TKey))
 335                                 return;
 336
 337                         Remove ((TKey)key);
 338                 }
 339
 340                 object IDictionary.this [object key]
 341                 {
 342                         get {
 343                                 if (!(key is TKey))
 344                                         throw new ArgumentException ("key isn't of correct type", "key");
 345
 346                                 return this[(TKey)key];
 347                         }
 348                         set {
 349                                 if (!(key is TKey) || !(value is TValue))
 350                                         throw new ArgumentException ("key or value aren't of correct type");
 351
 352                                 this[(TKey)key] = (TValue)value;
 353                         }
 354                 }
 355
 356                 void IDictionary.Add (object key, object value)
 357                 {
 358                         if (!(key is TKey) || !(value is TValue))
 359                                 throw new ArgumentException ("key or value aren't of correct type");
 360
 361                         Add ((TKey)key, (TValue)value);
 362                 }
 363
 364                 bool ICollection<KeyValuePair<TKey,TValue>>.Contains (KeyValuePair<TKey, TValue> pair)
 365                 {
 366                         return ContainsKey (pair.Key);
 367                 }
 368
 369                 public KeyValuePair<TKey,TValue>[] ToArray ()
 370                 {
 371                         // This is most certainly not optimum but there is
 372                         // not a lot of possibilities
 373
 374                         return new List<KeyValuePair<TKey,TValue>> (this).ToArray ();
 375                 }
 376
 377                 public void Clear()
 378                 {
 379                         // Pronk
 380                         container = new ConcurrentSkipList<Basket> ((value) => value [0].GetHashCode ());
 381                 }
 382
 383                 public int Count {
 384                         get {
 385                                 return count;
 386                         }
 387                 }
 388
 389                 public bool IsEmpty {
 390                         get {
 391                                 return count == 0;
 392                         }
 393                 }
 394
 395                 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 396                         get {
 397                                 return false;
 398                         }
 399                 }
 400
 401                 bool IDictionary.IsReadOnly {
 402                         get {
 403                                 return false;
 404                         }
 405                 }
 406
 407                 public ICollection<TKey> Keys {
 408                         get {
 409                                 return GetPart<TKey> ((kvp) => kvp.Key);
 410                         }
 411                 }
 412
 413                 public ICollection<TValue> Values {
 414                         get {
 415                                 return GetPart<TValue> ((kvp) => kvp.Value);
 416                         }
 417                 }
 418
 419                 ICollection IDictionary.Keys {
 420                         get {
 421                                 return (ICollection)Keys;
 422                         }
 423                 }
 424
 425                 ICollection IDictionary.Values {
 426                         get {
 427                                 return (ICollection)Values;
 428                         }
 429                 }
 430
 431                 ICollection<T> GetPart<T> (Func<KeyValuePair<TKey, TValue>, T> extractor)
 432                 {
 433                         List<T> temp = new List<T> ();
 434
 435                         foreach (KeyValuePair<TKey, TValue> kvp in this)
 436                                 temp.Add (extractor (kvp));
 437
 438                         return temp.AsReadOnly ();
 439                 }
 440
 441                 void ICollection.CopyTo (Array array, int startIndex)
 442                 {
 443                         KeyValuePair<TKey, TValue>[] arr = array as KeyValuePair<TKey, TValue>[];
 444                         if (arr == null)
 445                                 return;
 446
 447                         CopyTo (arr, startIndex, count);
 448                 }
 449
 450                 void CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex)
 451                 {
 452                         CopyTo (array, startIndex, count);
 453                 }
 454
 455                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex)
 456                 {
 457                         CopyTo (array, startIndex);
 458                 }
 459
 460                 void CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex, int num)
 461                 {
 462                         // TODO: This is quite unsafe as the count value will likely change during
 463                         // the copying. Watchout for IndexOutOfRange thingies
 464                         if (array.Length <= count + startIndex)
 465                                 throw new InvalidOperationException ("The array isn't big enough");
 466
 467                         int i = startIndex;
 468
 469                         foreach (Basket b in container) {
 470                                 lock (b) {
 471                                         foreach (Pair p in b) {
 472                                                 if (i >= num)
 473                                                         break;
 474                                                 array[i++] = new KeyValuePair<TKey, TValue> (p.Key, p.Value);
 475                                         }
 476                                 }
 477                         }
 478                 }
 479
 480                 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
 481                 {
 482                         return GetEnumeratorInternal ();
 483                 }
 484
 485                 IEnumerator IEnumerable.GetEnumerator ()
 486                 {
 487                         return (IEnumerator)GetEnumeratorInternal ();
 488                 }
 489
 490                 IEnumerator<KeyValuePair<TKey, TValue>> GetEnumeratorInternal ()
 491                 {
 492                         foreach (Basket b in container) {
 493                                 lock (b) {
 494                                         foreach (Pair p in b)
 495                                                 yield return new KeyValuePair<TKey, TValue> (p.Key, p.Value);
 496                                 }
 497                         }
 498                 }
 499
 500                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 501                 {
 502                         return new ConcurrentDictionaryEnumerator (GetEnumeratorInternal ());
 503                 }
 504
 505                 class ConcurrentDictionaryEnumerator : IDictionaryEnumerator
 506                 {
 507                         IEnumerator<KeyValuePair<TKey, TValue>> internalEnum;
 508
 509                         public ConcurrentDictionaryEnumerator (IEnumerator<KeyValuePair<TKey, TValue>> internalEnum)
 510                         {
 511                                 this.internalEnum = internalEnum;
 512                         }
 513
 514                         public bool MoveNext ()
 515                         {
 516                                 return internalEnum.MoveNext ();
 517                         }
 518
 519                         public void Reset ()
 520                         {
 521                                 internalEnum.Reset ();
 522                         }
 523
 524                         public object Current {
 525                                 get {
 526                                         return Entry;
 527                                 }
 528                         }
 529
 530                         public DictionaryEntry Entry {
 531                                 get {
 532                                         KeyValuePair<TKey, TValue> current = internalEnum.Current;
 533                                         return new DictionaryEntry (current.Key, current.Value);
 534                                 }
 535                         }
 536
 537                         public object Key {
 538                                 get {
 539                                         return internalEnum.Current.Key;
 540                                 }
 541                         }
 542
 543                         public object Value {
 544                                 get {
 545                                         return internalEnum.Current.Value;
 546                                 }
 547                         }
 548                 }
 549
 550                 object ICollection.SyncRoot {
 551                         get {
 552                                 return this;
 553                         }
 554                 }
 555
 556
 557                 bool IDictionary.IsFixedSize {
 558                         get {
 559                                 return false;
 560                         }
 561                 }
 562
 563                 bool ICollection.IsSynchronized {
 564                         get { return true; }
 565                 }
 566
 567                 bool TryGetBasket (TKey key, out Basket basket)
 568                 {
 569                         basket = null;
 570                         if (!container.GetFromHash (key.GetHashCode (), out basket))
 571                                 return false;
 572
 573                         return true;
 574                 }
 575         }
 576 }
 577 #endif