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                 int stamp = int.MinValue;
  70                 IEqualityComparer<TKey> comparer;
  71
  72                 public ConcurrentDictionary () : this (EqualityComparer<TKey>.Default)
  73                 {
  74                 }
  75
  76                 public ConcurrentDictionary (IEnumerable<KeyValuePair<TKey, TValue>> values)
  77                         : this (values, EqualityComparer<TKey>.Default)
  78                 {
  79                         foreach (KeyValuePair<TKey, TValue> pair in values)
  80                                 Add (pair.Key, pair.Value);
  81                 }
  82
  83                 public ConcurrentDictionary (IEqualityComparer<TKey> comparer)
  84                 {
  85                         this.comparer = comparer;
  86                 }
  87
  88                 public ConcurrentDictionary (IEnumerable<KeyValuePair<TKey, TValue>> values, IEqualityComparer<TKey> comparer)
  89                         : this (comparer)
  90                 {
  91                         foreach (KeyValuePair<TKey, TValue> pair in values)
  92                                 Add (pair.Key, pair.Value);
  93                 }
  94
  95                 // Parameters unused
  96                 public ConcurrentDictionary (int concurrencyLevel, int capacity)
  97                         : this (EqualityComparer<TKey>.Default)
  98                 {
  99
 100                 }
 101
 102                 public ConcurrentDictionary (int concurrencyLevel,
 103                                              IEnumerable<KeyValuePair<TKey, TValue>> values,
 104                                              IEqualityComparer<TKey> comparer)
 105                         : this (values, comparer)
 106                 {
 107
 108                 }
 109
 110                 // Parameters unused
 111                 public ConcurrentDictionary (int concurrencyLevel, int capacity, IEqualityComparer<TKey> comparer)
 112                         : this (comparer)
 113                 {
 114
 115                 }
 116
 117                 void Add (TKey key, TValue value)
 118                 {
 119                         while (!TryAdd (key, value));
 120                 }
 121
 122                 void IDictionary<TKey, TValue>.Add (TKey key, TValue value)
 123                 {
 124                         Add (key, value);
 125                 }
 126
 127                 public bool TryAdd (TKey key, TValue value)
 128                 {
 129                         Interlocked.Increment (ref count);
 130                         Interlocked.Increment (ref stamp);
 131
 132                         Basket basket;
 133                         // Add a value to an existing basket
 134                         if (TryGetBasket (key, out basket)) {
 135                                 // Find a maybe more sexy locking scheme later
 136                                 lock (basket) {
 137                                         foreach (var p in basket) {
 138                                                 if (comparer.Equals (p.Key, key))
 139                                                         throw new ArgumentException ("An element with the same key already exists");
 140                                         }
 141                                         basket.Add (new Pair (key, value));
 142                                 }
 143                         } else {
 144                                 // Add a new basket
 145                                 basket = new Basket ();
 146                                 basket.Add (new Pair (key, value));
 147                                 return container.TryAdd (basket);
 148                         }
 149
 150                         return true;
 151                 }
 152
 153                 void ICollection<KeyValuePair<TKey,TValue>>.Add (KeyValuePair<TKey, TValue> pair)
 154                 {
 155                         Add (pair.Key, pair.Value);
 156                 }
 157
 158                 TValue GetValue (TKey key)
 159                 {
 160                         TValue temp;
 161                         if (!TryGetValue (key, out temp))
 162                                 // TODO: find a correct Exception
 163                                 throw new ArgumentException ("Not a valid key for this dictionary", "key");
 164                         return temp;
 165                 }
 166
 167                 public bool TryGetValue (TKey key, out TValue value)
 168                 {
 169                         Basket basket;
 170                         value = default (TValue);
 171
 172                         if (!TryGetBasket (key, out basket))
 173                                 return false;
 174
 175                         lock (basket) {
 176                                 Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
 177                                 if (pair == null)
 178                                         return false;
 179                                 value = pair.Value;
 180                         }
 181
 182                         return true;
 183                 }
 184
 185                 public bool TryUpdate (TKey key, TValue newValue, TValue comparand)
 186                 {
 187                         Basket basket;
 188                         if (!TryGetBasket (key, out basket))
 189                                 return false;
 190
 191                         lock (basket) {
 192                                 Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
 193                                 if (pair.Value.Equals (comparand)) {
 194                                         pair.Value = newValue;
 195
 196                                         return true;
 197                                 }
 198                         }
 199
 200                         return false;
 201                 }
 202
 203                 public TValue this[TKey key] {
 204                         get {
 205                                 return GetValue (key);
 206                         }
 207                         set {
 208                                 Basket basket;
 209                                 if (!TryGetBasket (key, out basket)) {
 210                                         Add (key, value);
 211                                         return;
 212                                 }
 213                                 lock (basket) {
 214                                         Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
 215                                         if (pair == null)
 216                                                 throw new InvalidOperationException ("pair is null, shouldn't be");
 217                                         pair.Value = value;
 218                                         Interlocked.Increment (ref stamp);
 219                                 }
 220                         }
 221                 }
 222
 223                 public bool TryRemove(TKey key, out TValue value)
 224                 {
 225                         value = default (TValue);
 226                         Basket b;
 227
 228                         if (!TryGetBasket (key, out b))
 229                                 return false;
 230
 231                         lock (b) {
 232                                 TValue temp = default (TValue);
 233                                 // Should always be == 1 but who know
 234                                 bool result = b.RemoveAll ((p) => {
 235                                         bool r = comparer.Equals (p.Key, key);
 236                                         if (r) temp = p.Value;
 237                                         return r;
 238                                 }) >= 1;
 239                                 value = temp;
 240
 241                                 if (result)
 242                                         Interlocked.Decrement (ref count);
 243
 244                                 return result;
 245                         }
 246                 }
 247
 248                 bool Remove (TKey key)
 249                 {
 250                         TValue dummy;
 251
 252                         return TryRemove (key, out dummy);
 253                 }
 254
 255                 bool IDictionary<TKey, TValue>.Remove (TKey key)
 256                 {
 257                         return Remove (key);
 258                 }
 259
 260                 bool ICollection<KeyValuePair<TKey,TValue>>.Remove (KeyValuePair<TKey,TValue> pair)
 261                 {
 262                         return Remove (pair.Key);
 263                 }
 264
 265                 public bool ContainsKey (TKey key)
 266                 {
 267                         return container.ContainsFromHash (key.GetHashCode ());
 268                 }
 269
 270                 bool IDictionary.Contains (object key)
 271                 {
 272                         if (!(key is TKey))
 273                                 return false;
 274
 275                         return ContainsKey ((TKey)key);
 276                 }
 277
 278                 void IDictionary.Remove (object key)
 279                 {
 280                         if (!(key is TKey))
 281                                 return;
 282
 283                         Remove ((TKey)key);
 284                 }
 285
 286                 object IDictionary.this [object key]
 287                 {
 288                         get {
 289                                 if (!(key is TKey))
 290                                         throw new ArgumentException ("key isn't of correct type", "key");
 291
 292                                 return this[(TKey)key];
 293                         }
 294                         set {
 295                                 if (!(key is TKey) || !(value is TValue))
 296                                         throw new ArgumentException ("key or value aren't of correct type");
 297
 298                                 this[(TKey)key] = (TValue)value;
 299                         }
 300                 }
 301
 302                 void IDictionary.Add (object key, object value)
 303                 {
 304                         if (!(key is TKey) || !(value is TValue))
 305                                 throw new ArgumentException ("key or value aren't of correct type");
 306
 307                         Add ((TKey)key, (TValue)value);
 308                 }
 309
 310                 bool ICollection<KeyValuePair<TKey,TValue>>.Contains (KeyValuePair<TKey, TValue> pair)
 311                 {
 312                         return ContainsKey (pair.Key);
 313                 }
 314
 315                 public KeyValuePair<TKey,TValue>[] ToArray ()
 316                 {
 317                         // This is most certainly not optimum but there is
 318                         // not a lot of possibilities
 319
 320                         return new List<KeyValuePair<TKey,TValue>> (this).ToArray ();
 321                 }
 322
 323                 public void Clear()
 324                 {
 325                         // Pronk
 326                         container = new ConcurrentSkipList<Basket> ((value) => value [0].GetHashCode ());
 327                 }
 328
 329                 public int Count {
 330                         get {
 331                                 return count;
 332                         }
 333                 }
 334
 335                 public bool IsEmpty {
 336                         get {
 337                                 return count == 0;
 338                         }
 339                 }
 340
 341                 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 342                         get {
 343                                 return false;
 344                         }
 345                 }
 346
 347                 bool IDictionary.IsReadOnly {
 348                         get {
 349                                 return false;
 350                         }
 351                 }
 352
 353                 public ICollection<TKey> Keys {
 354                         get {
 355                                 return GetPart<TKey> ((kvp) => kvp.Key);
 356                         }
 357                 }
 358
 359                 public ICollection<TValue> Values {
 360                         get {
 361                                 return GetPart<TValue> ((kvp) => kvp.Value);
 362                         }
 363                 }
 364
 365                 ICollection IDictionary.Keys {
 366                         get {
 367                                 return (ICollection)Keys;
 368                         }
 369                 }
 370
 371                 ICollection IDictionary.Values {
 372                         get {
 373                                 return (ICollection)Values;
 374                         }
 375                 }
 376
 377                 ICollection<T> GetPart<T> (Func<KeyValuePair<TKey, TValue>, T> extractor)
 378                 {
 379                         List<T> temp = new List<T> ();
 380
 381                         foreach (KeyValuePair<TKey, TValue> kvp in this)
 382                                 temp.Add (extractor (kvp));
 383
 384                         return temp.AsReadOnly ();
 385                 }
 386
 387                 void ICollection.CopyTo (Array array, int startIndex)
 388                 {
 389                         KeyValuePair<TKey, TValue>[] arr = array as KeyValuePair<TKey, TValue>[];
 390                         if (arr == null)
 391                                 return;
 392
 393                         CopyTo (arr, startIndex, count);
 394                 }
 395
 396                 void CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex)
 397                 {
 398                         CopyTo (array, startIndex, count);
 399                 }
 400
 401                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex)
 402                 {
 403                         CopyTo (array, startIndex);
 404                 }
 405
 406                 void CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex, int num)
 407                 {
 408                         // TODO: This is quite unsafe as the count value will likely change during
 409                         // the copying. Watchout for IndexOutOfRange thingies
 410                         if (array.Length <= count + startIndex)
 411                                 throw new InvalidOperationException ("The array isn't big enough");
 412
 413                         int i = startIndex;
 414
 415                         foreach (Basket b in container) {
 416                                 lock (b) {
 417                                         foreach (Pair p in b) {
 418                                                 if (i >= num)
 419                                                         break;
 420                                                 array[i++] = new KeyValuePair<TKey, TValue> (p.Key, p.Value);
 421                                         }
 422                                 }
 423                         }
 424                 }
 425
 426                 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
 427                 {
 428                         return GetEnumeratorInternal ();
 429                 }
 430
 431                 IEnumerator IEnumerable.GetEnumerator ()
 432                 {
 433                         return (IEnumerator)GetEnumeratorInternal ();
 434                 }
 435
 436                 IEnumerator<KeyValuePair<TKey, TValue>> GetEnumeratorInternal ()
 437                 {
 438                         foreach (Basket b in container) {
 439                                 lock (b) {
 440                                         foreach (Pair p in b)
 441                                                 yield return new KeyValuePair<TKey, TValue> (p.Key, p.Value);
 442                                 }
 443                         }
 444                 }
 445
 446                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 447                 {
 448                         return new ConcurrentDictionaryEnumerator (GetEnumeratorInternal ());
 449                 }
 450
 451                 class ConcurrentDictionaryEnumerator : IDictionaryEnumerator
 452                 {
 453                         IEnumerator<KeyValuePair<TKey, TValue>> internalEnum;
 454
 455                         public ConcurrentDictionaryEnumerator (IEnumerator<KeyValuePair<TKey, TValue>> internalEnum)
 456                         {
 457                                 this.internalEnum = internalEnum;
 458                         }
 459
 460                         public bool MoveNext ()
 461                         {
 462                                 return internalEnum.MoveNext ();
 463                         }
 464
 465                         public void Reset ()
 466                         {
 467                                 internalEnum.Reset ();
 468                         }
 469
 470                         public object Current {
 471                                 get {
 472                                         return Entry;
 473                                 }
 474                         }
 475
 476                         public DictionaryEntry Entry {
 477                                 get {
 478                                         KeyValuePair<TKey, TValue> current = internalEnum.Current;
 479                                         return new DictionaryEntry (current.Key, current.Value);
 480                                 }
 481                         }
 482
 483                         public object Key {
 484                                 get {
 485                                         return internalEnum.Current.Key;
 486                                 }
 487                         }
 488
 489                         public object Value {
 490                                 get {
 491                                         return internalEnum.Current.Value;
 492                                 }
 493                         }
 494                 }
 495
 496                 object ICollection.SyncRoot {
 497                         get {
 498                                 return this;
 499                         }
 500                 }
 501
 502
 503                 bool IDictionary.IsFixedSize {
 504                         get {
 505                                 return false;
 506                         }
 507                 }
 508
 509                 bool ICollection.IsSynchronized {
 510                         get { return true; }
 511                 }
 512
 513                 bool TryGetBasket (TKey key, out Basket basket)
 514                 {
 515                         basket = null;
 516                         if (!container.GetFromHash (key.GetHashCode (), out basket))
 517                                 return false;
 518
 519                         return true;
 520                 }
 521         }
 522 }
 523 #endif