src/mscorlib/shared/System/Collections/Generic/Dictionary.cs

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 using System;
   6 using System.Collections;
   7 using System.Diagnostics;
   8 using System.Runtime.CompilerServices;
   9 using System.Runtime.Serialization;
  10
  11 namespace System.Collections.Generic
  12 {
  13     /// <summary>
  14     /// Used internally to control behavior of insertion into a <see cref="Dictionary{TKey, TValue}"/>.
  15     /// </summary>
  16     internal enum InsertionBehavior : byte
  17     {
  18         /// <summary>
  19         /// The default insertion behavior.
  20         /// </summary>
  21         None = 0,
  22
  23         /// <summary>
  24         /// Specifies that an existing entry with the same key should be overwritten if encountered.
  25         /// </summary>
  26         OverwriteExisting = 1,
  27
  28         /// <summary>
  29         /// Specifies that if an existing entry with the same key is encountered, an exception should be thrown.
  30         /// </summary>
  31         ThrowOnExisting = 2
  32     }
  33
  34     [DebuggerTypeProxy(typeof(IDictionaryDebugView<,>))]
  35     [DebuggerDisplay("Count = {Count}")]
  36     [Serializable]
  37     [System.Runtime.CompilerServices.TypeForwardedFrom("mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
  38     public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback
  39     {
  40         private struct Entry
  41         {
  42             public int hashCode;    // Lower 31 bits of hash code, -1 if unused
  43             public int next;        // Index of next entry, -1 if last
  44             public TKey key;           // Key of entry
  45             public TValue value;         // Value of entry
  46         }
  47
  48         private int[] _buckets;
  49         private Entry[] _entries;
  50         private int _count;
  51         private int _freeList;
  52         private int _freeCount;
  53         private int _version;
  54         private IEqualityComparer<TKey> _comparer;
  55         private KeyCollection _keys;
  56         private ValueCollection _values;
  57         private object _syncRoot;
  58
  59         // constants for serialization
  60         private const string VersionName = "Version"; // Do not rename (binary serialization)
  61         private const string HashSizeName = "HashSize"; // Do not rename (binary serialization). Must save buckets.Length
  62         private const string KeyValuePairsName = "KeyValuePairs"; // Do not rename (binary serialization)
  63         private const string ComparerName = "Comparer"; // Do not rename (binary serialization)
  64
  65         public Dictionary() : this(0, null) { }
  66
  67         public Dictionary(int capacity) : this(capacity, null) { }
  68
  69         public Dictionary(IEqualityComparer<TKey> comparer) : this(0, comparer) { }
  70
  71         public Dictionary(int capacity, IEqualityComparer<TKey> comparer)
  72         {
  73             if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
  74             if (capacity > 0) Initialize(capacity);
  75             _comparer = comparer ?? EqualityComparer<TKey>.Default;
  76
  77             if (_comparer == EqualityComparer<string>.Default)
  78             {
  79                 _comparer = (IEqualityComparer<TKey>)NonRandomizedStringEqualityComparer.Default;
  80             }
  81         }
  82
  83         public Dictionary(IDictionary<TKey, TValue> dictionary) : this(dictionary, null) { }
  84
  85         public Dictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) :
  86             this(dictionary != null ? dictionary.Count : 0, comparer)
  87         {
  88             if (dictionary == null)
  89             {
  90                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
  91             }
  92
  93             // It is likely that the passed-in dictionary is Dictionary<TKey,TValue>. When this is the case,
  94             // avoid the enumerator allocation and overhead by looping through the entries array directly.
  95             // We only do this when dictionary is Dictionary<TKey,TValue> and not a subclass, to maintain
  96             // back-compat with subclasses that may have overridden the enumerator behavior.
  97             if (dictionary.GetType() == typeof(Dictionary<TKey, TValue>))
  98             {
  99                 Dictionary<TKey, TValue> d = (Dictionary<TKey, TValue>)dictionary;
 100                 int count = d._count;
 101                 Entry[] entries = d._entries;
 102                 for (int i = 0; i < count; i++)
 103                 {
 104                     if (entries[i].hashCode >= 0)
 105                     {
 106                         Add(entries[i].key, entries[i].value);
 107                     }
 108                 }
 109                 return;
 110             }
 111
 112             foreach (KeyValuePair<TKey, TValue> pair in dictionary)
 113             {
 114                 Add(pair.Key, pair.Value);
 115             }
 116         }
 117
 118         public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection) : this(collection, null) { }
 119
 120         public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer) :
 121             this((collection as ICollection<KeyValuePair<TKey, TValue>>)?.Count ?? 0, comparer)
 122         {
 123             if (collection == null)
 124             {
 125                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
 126             }
 127
 128             foreach (KeyValuePair<TKey, TValue> pair in collection)
 129             {
 130                 Add(pair.Key, pair.Value);
 131             }
 132         }
 133
 134         protected Dictionary(SerializationInfo info, StreamingContext context)
 135         {
 136             // We can't do anything with the keys and values until the entire graph has been deserialized
 137             // and we have a resonable estimate that GetHashCode is not going to fail.  For the time being,
 138             // we'll just cache this.  The graph is not valid until OnDeserialization has been called.
 139             HashHelpers.SerializationInfoTable.Add(this, info);
 140         }
 141
 142         public IEqualityComparer<TKey> Comparer
 143         {
 144             get
 145             {
 146                 return _comparer;
 147             }
 148         }
 149
 150         public int Count
 151         {
 152             get { return _count - _freeCount; }
 153         }
 154
 155         public KeyCollection Keys
 156         {
 157             get
 158             {
 159                 if (_keys == null) _keys = new KeyCollection(this);
 160                 return _keys;
 161             }
 162         }
 163
 164         ICollection<TKey> IDictionary<TKey, TValue>.Keys
 165         {
 166             get
 167             {
 168                 if (_keys == null) _keys = new KeyCollection(this);
 169                 return _keys;
 170             }
 171         }
 172
 173         IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys
 174         {
 175             get
 176             {
 177                 if (_keys == null) _keys = new KeyCollection(this);
 178                 return _keys;
 179             }
 180         }
 181
 182         public ValueCollection Values
 183         {
 184             get
 185             {
 186                 if (_values == null) _values = new ValueCollection(this);
 187                 return _values;
 188             }
 189         }
 190
 191         ICollection<TValue> IDictionary<TKey, TValue>.Values
 192         {
 193             get
 194             {
 195                 if (_values == null) _values = new ValueCollection(this);
 196                 return _values;
 197             }
 198         }
 199
 200         IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values
 201         {
 202             get
 203             {
 204                 if (_values == null) _values = new ValueCollection(this);
 205                 return _values;
 206             }
 207         }
 208
 209         public TValue this[TKey key]
 210         {
 211             get
 212             {
 213                 int i = FindEntry(key);
 214                 if (i >= 0) return _entries[i].value;
 215                 ThrowHelper.ThrowKeyNotFoundException(key);
 216                 return default(TValue);
 217             }
 218             set
 219             {
 220                 bool modified = TryInsert(key, value, InsertionBehavior.OverwriteExisting);
 221                 Debug.Assert(modified);
 222             }
 223         }
 224
 225         public void Add(TKey key, TValue value)
 226         {
 227             bool modified = TryInsert(key, value, InsertionBehavior.ThrowOnExisting);
 228             Debug.Assert(modified); // If there was an existing key and the Add failed, an exception will already have been thrown.
 229         }
 230
 231         void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair)
 232         {
 233             Add(keyValuePair.Key, keyValuePair.Value);
 234         }
 235
 236         bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair)
 237         {
 238             int i = FindEntry(keyValuePair.Key);
 239             if (i >= 0 && EqualityComparer<TValue>.Default.Equals(_entries[i].value, keyValuePair.Value))
 240             {
 241                 return true;
 242             }
 243             return false;
 244         }
 245
 246         bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair)
 247         {
 248             int i = FindEntry(keyValuePair.Key);
 249             if (i >= 0 && EqualityComparer<TValue>.Default.Equals(_entries[i].value, keyValuePair.Value))
 250             {
 251                 Remove(keyValuePair.Key);
 252                 return true;
 253             }
 254             return false;
 255         }
 256
 257         public void Clear()
 258         {
 259             int count = _count;
 260             if (count > 0)
 261             {
 262                 int[] buckets = _buckets;
 263                 for (int i = 0; i < buckets.Length; i++)
 264                 {
 265                     buckets[i] = -1;
 266                 }
 267
 268                 _count = 0;
 269                 _freeList = -1;
 270                 _freeCount = 0;
 271                 _version++;
 272                 Array.Clear(_entries, 0, count);
 273             }
 274         }
 275
 276         public bool ContainsKey(TKey key)
 277         {
 278             return FindEntry(key) >= 0;
 279         }
 280
 281         public bool ContainsValue(TValue value)
 282         {
 283             if (value == null)
 284             {
 285                 for (int i = 0; i < _count; i++)
 286                 {
 287                     if (_entries[i].hashCode >= 0 && _entries[i].value == null) return true;
 288                 }
 289             }
 290             else
 291             {
 292                 EqualityComparer<TValue> c = EqualityComparer<TValue>.Default;
 293                 for (int i = 0; i < _count; i++)
 294                 {
 295                     if (_entries[i].hashCode >= 0 && c.Equals(_entries[i].value, value)) return true;
 296                 }
 297             }
 298             return false;
 299         }
 300
 301         private void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
 302         {
 303             if (array == null)
 304             {
 305                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 306             }
 307
 308             if (index < 0 || index > array.Length)
 309             {
 310                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
 311             }
 312
 313             if (array.Length - index < Count)
 314             {
 315                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
 316             }
 317
 318             int count = _count;
 319             Entry[] entries = _entries;
 320             for (int i = 0; i < count; i++)
 321             {
 322                 if (entries[i].hashCode >= 0)
 323                 {
 324                     array[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value);
 325                 }
 326             }
 327         }
 328
 329         public Enumerator GetEnumerator()
 330         {
 331             return new Enumerator(this, Enumerator.KeyValuePair);
 332         }
 333
 334         IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
 335         {
 336             return new Enumerator(this, Enumerator.KeyValuePair);
 337         }
 338
 339         public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
 340         {
 341             if (info == null)
 342             {
 343                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info);
 344             }
 345
 346             info.AddValue(VersionName, _version);
 347             info.AddValue(ComparerName, _comparer, typeof(IEqualityComparer<TKey>));
 348             info.AddValue(HashSizeName, _buckets == null ? 0 : _buckets.Length); // This is the length of the bucket array
 349
 350             if (_buckets != null)
 351             {
 352                 var array = new KeyValuePair<TKey, TValue>[Count];
 353                 CopyTo(array, 0);
 354                 info.AddValue(KeyValuePairsName, array, typeof(KeyValuePair<TKey, TValue>[]));
 355             }
 356         }
 357
 358         private int FindEntry(TKey key)
 359         {
 360             if (key == null)
 361             {
 362                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 363             }
 364
 365             if (_buckets != null)
 366             {
 367                 int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF;
 368                 for (int i = _buckets[hashCode % _buckets.Length]; i >= 0; i = _entries[i].next)
 369                 {
 370                     if (_entries[i].hashCode == hashCode && _comparer.Equals(_entries[i].key, key)) return i;
 371                 }
 372             }
 373             return -1;
 374         }
 375
 376         private int Initialize(int capacity)
 377         {
 378             int size = HashHelpers.GetPrime(capacity);
 379             int[] buckets = new int[size];
 380             for (int i = 0; i < buckets.Length; i++)
 381             {
 382                 buckets[i] = -1;
 383             }
 384
 385             _freeList = -1;
 386             _buckets = buckets;
 387             _entries = new Entry[size];
 388
 389             return size;
 390         }
 391
 392         private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
 393         {
 394             if (key == null)
 395             {
 396                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 397             }
 398
 399             if (_buckets == null) Initialize(0);
 400             int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF;
 401             int targetBucket = hashCode % _buckets.Length;
 402             int collisionCount = 0;
 403
 404             for (int i = _buckets[targetBucket]; i >= 0; i = _entries[i].next)
 405             {
 406                 if (_entries[i].hashCode == hashCode && _comparer.Equals(_entries[i].key, key))
 407                 {
 408                     if (behavior == InsertionBehavior.OverwriteExisting)
 409                     {
 410                         _entries[i].value = value;
 411                         _version++;
 412                         return true;
 413                     }
 414
 415                     if (behavior == InsertionBehavior.ThrowOnExisting)
 416                     {
 417                         ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
 418                     }
 419
 420                     return false;
 421                 }
 422                 collisionCount++;
 423             }
 424
 425             int index;
 426             if (_freeCount > 0)
 427             {
 428                 index = _freeList;
 429                 _freeList = _entries[index].next;
 430                 _freeCount--;
 431             }
 432             else
 433             {
 434                 if (_count == _entries.Length)
 435                 {
 436                     Resize();
 437                     targetBucket = hashCode % _buckets.Length;
 438                 }
 439                 index = _count;
 440                 _count++;
 441             }
 442
 443             _entries[index].hashCode = hashCode;
 444             _entries[index].next = _buckets[targetBucket];
 445             _entries[index].key = key;
 446             _entries[index].value = value;
 447             _buckets[targetBucket] = index;
 448             _version++;
 449
 450             // If we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
 451             // i.e. EqualityComparer<string>.Default.
 452
 453             if (collisionCount > HashHelpers.HashCollisionThreshold && _comparer is NonRandomizedStringEqualityComparer)
 454             {
 455                 _comparer = (IEqualityComparer<TKey>)EqualityComparer<string>.Default;
 456                 Resize(_entries.Length, true);
 457             }
 458
 459             return true;
 460         }
 461
 462         public virtual void OnDeserialization(object sender)
 463         {
 464             SerializationInfo siInfo;
 465             HashHelpers.SerializationInfoTable.TryGetValue(this, out siInfo);
 466
 467             if (siInfo == null)
 468             {
 469                 // We can return immediately if this function is called twice.
 470                 // Note we remove the serialization info from the table at the end of this method.
 471                 return;
 472             }
 473
 474             int realVersion = siInfo.GetInt32(VersionName);
 475             int hashsize = siInfo.GetInt32(HashSizeName);
 476             _comparer = (IEqualityComparer<TKey>)siInfo.GetValue(ComparerName, typeof(IEqualityComparer<TKey>));
 477
 478             if (hashsize != 0)
 479             {
 480                 Initialize(hashsize);
 481
 482                 KeyValuePair<TKey, TValue>[] array = (KeyValuePair<TKey, TValue>[])
 483                     siInfo.GetValue(KeyValuePairsName, typeof(KeyValuePair<TKey, TValue>[]));
 484
 485                 if (array == null)
 486                 {
 487                     ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingKeys);
 488                 }
 489
 490                 for (int i = 0; i < array.Length; i++)
 491                 {
 492                     if (array[i].Key == null)
 493                     {
 494                         ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_NullKey);
 495                     }
 496                     Add(array[i].Key, array[i].Value);
 497                 }
 498             }
 499             else
 500             {
 501                 _buckets = null;
 502             }
 503
 504             _version = realVersion;
 505             HashHelpers.SerializationInfoTable.Remove(this);
 506         }
 507
 508         private void Resize()
 509         {
 510             Resize(HashHelpers.ExpandPrime(_count), false);
 511         }
 512
 513         private void Resize(int newSize, bool forceNewHashCodes)
 514         {
 515             Debug.Assert(newSize >= _entries.Length);
 516
 517             int[] buckets = new int[newSize];
 518             for (int i = 0; i < buckets.Length; i++)
 519             {
 520                 buckets[i] = -1;
 521             }
 522             Entry[] entries = new Entry[newSize];
 523
 524             int count = _count;
 525             Array.Copy(_entries, 0, entries, 0, count);
 526
 527             if (forceNewHashCodes)
 528             {
 529                 for (int i = 0; i < count; i++)
 530                 {
 531                     if (entries[i].hashCode != -1)
 532                     {
 533                         entries[i].hashCode = (_comparer.GetHashCode(entries[i].key) & 0x7FFFFFFF);
 534                     }
 535                 }
 536             }
 537
 538             for (int i = 0; i < count; i++)
 539             {
 540                 if (entries[i].hashCode >= 0)
 541                 {
 542                     int bucket = entries[i].hashCode % newSize;
 543                     entries[i].next = buckets[bucket];
 544                     buckets[bucket] = i;
 545                 }
 546             }
 547
 548             _buckets = buckets;
 549             _entries = entries;
 550         }
 551
 552         // The overload Remove(TKey key, out TValue value) is a copy of this method with one additional
 553         // statement to copy the value for entry being removed into the output parameter.
 554         // Code has been intentionally duplicated for performance reasons.
 555         public bool Remove(TKey key)
 556         {
 557             if (key == null)
 558             {
 559                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 560             }
 561
 562             if (_buckets != null)
 563             {
 564                 int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF;
 565                 int bucket = hashCode % _buckets.Length;
 566                 int last = -1;
 567                 int i = _buckets[bucket];
 568                 while (i >= 0)
 569                 {
 570                     ref Entry entry = ref _entries[i];
 571
 572                     if (entry.hashCode == hashCode && _comparer.Equals(entry.key, key))
 573                     {
 574                         if (last < 0)
 575                         {
 576                             _buckets[bucket] = entry.next;
 577                         }
 578                         else
 579                         {
 580                             _entries[last].next = entry.next;
 581                         }
 582                         entry.hashCode = -1;
 583                         entry.next = _freeList;
 584
 585                         if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>())
 586                         {
 587                             entry.key = default(TKey);
 588                         }
 589                         if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>())
 590                         {
 591                             entry.value = default(TValue);
 592                         }
 593                         _freeList = i;
 594                         _freeCount++;
 595                         _version++;
 596                         return true;
 597                     }
 598
 599                     last = i;
 600                     i = entry.next;
 601                 }
 602             }
 603             return false;
 604         }
 605
 606         // This overload is a copy of the overload Remove(TKey key) with one additional
 607         // statement to copy the value for entry being removed into the output parameter.
 608         // Code has been intentionally duplicated for performance reasons.
 609         public bool Remove(TKey key, out TValue value)
 610         {
 611             if (key == null)
 612             {
 613                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 614             }
 615
 616             if (_buckets != null)
 617             {
 618                 int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF;
 619                 int bucket = hashCode % _buckets.Length;
 620                 int last = -1;
 621                 int i = _buckets[bucket];
 622                 while (i >= 0)
 623                 {
 624                     ref Entry entry = ref _entries[i];
 625
 626                     if (entry.hashCode == hashCode && _comparer.Equals(entry.key, key))
 627                     {
 628                         if (last < 0)
 629                         {
 630                             _buckets[bucket] = entry.next;
 631                         }
 632                         else
 633                         {
 634                             _entries[last].next = entry.next;
 635                         }
 636
 637                         value = entry.value;
 638
 639                         entry.hashCode = -1;
 640                         entry.next = _freeList;
 641
 642                         if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>())
 643                         {
 644                             entry.key = default(TKey);
 645                         }
 646                         if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>())
 647                         {
 648                             entry.value = default(TValue);
 649                         }
 650                         _freeList = i;
 651                         _freeCount++;
 652                         _version++;
 653                         return true;
 654                     }
 655
 656                     last = i;
 657                     i = entry.next;
 658                 }
 659             }
 660             value = default(TValue);
 661             return false;
 662         }
 663
 664         public bool TryGetValue(TKey key, out TValue value)
 665         {
 666             int i = FindEntry(key);
 667             if (i >= 0)
 668             {
 669                 value = _entries[i].value;
 670                 return true;
 671             }
 672             value = default(TValue);
 673             return false;
 674         }
 675
 676         public bool TryAdd(TKey key, TValue value) => TryInsert(key, value, InsertionBehavior.None);
 677
 678         bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
 679         {
 680             get { return false; }
 681         }
 682
 683         void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
 684         {
 685             CopyTo(array, index);
 686         }
 687
 688         void ICollection.CopyTo(Array array, int index)
 689         {
 690             if (array == null)
 691             {
 692                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 693             }
 694
 695             if (array.Rank != 1)
 696             {
 697                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
 698             }
 699
 700             if (array.GetLowerBound(0) != 0)
 701             {
 702                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
 703             }
 704
 705             if (index < 0 || index > array.Length)
 706             {
 707                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
 708             }
 709
 710             if (array.Length - index < Count)
 711             {
 712                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
 713             }
 714
 715             KeyValuePair<TKey, TValue>[] pairs = array as KeyValuePair<TKey, TValue>[];
 716             if (pairs != null)
 717             {
 718                 CopyTo(pairs, index);
 719             }
 720             else if (array is DictionaryEntry[])
 721             {
 722                 DictionaryEntry[] dictEntryArray = array as DictionaryEntry[];
 723                 Entry[] entries = _entries;
 724                 for (int i = 0; i < _count; i++)
 725                 {
 726                     if (entries[i].hashCode >= 0)
 727                     {
 728                         dictEntryArray[index++] = new DictionaryEntry(entries[i].key, entries[i].value);
 729                     }
 730                 }
 731             }
 732             else
 733             {
 734                 object[] objects = array as object[];
 735                 if (objects == null)
 736                 {
 737                     ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
 738                 }
 739
 740                 try
 741                 {
 742                     int count = _count;
 743                     Entry[] entries = _entries;
 744                     for (int i = 0; i < count; i++)
 745                     {
 746                         if (entries[i].hashCode >= 0)
 747                         {
 748                             objects[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value);
 749                         }
 750                     }
 751                 }
 752                 catch (ArrayTypeMismatchException)
 753                 {
 754                     ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
 755                 }
 756             }
 757         }
 758
 759         IEnumerator IEnumerable.GetEnumerator()
 760         {
 761             return new Enumerator(this, Enumerator.KeyValuePair);
 762         }
 763
 764         /// <summary>
 765         /// Ensures that the dictionary can hold up to 'capacity' entries without any further expansion of its backing storage
 766         /// </summary>
 767         public int EnsureCapacity(int capacity)
 768         {
 769             if (capacity < 0)
 770                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
 771             int currentCapacity = _entries == null ? 0 : _entries.Length;
 772             if (currentCapacity >= capacity)
 773                 return currentCapacity;
 774             if (_buckets == null)
 775                 return Initialize(capacity);
 776             int newSize = HashHelpers.GetPrime(capacity);
 777             Resize(newSize, forceNewHashCodes: false);
 778             return newSize;
 779         }
 780
 781         /// <summary>
 782         /// Sets the capacity of this dictionary to what it would be if it had been originally initialized with all its entries
 783         ///
 784         /// This method can be used to minimize the memory overhead
 785         /// once it is known that no new elements will be added.
 786         ///
 787         /// To allocate minimum size storage array, execute the following statements:
 788         ///
 789         /// dictionary.Clear();
 790         /// dictionary.TrimExcess();
 791         /// </summary>
 792         public void TrimExcess()
 793         {
 794             TrimExcess(Count);
 795         }
 796
 797         /// <summary>
 798         /// Sets the capacity of this dictionary to hold up 'capacity' entries without any further expansion of its backing storage
 799         ///
 800         /// This method can be used to minimize the memory overhead
 801         /// once it is known that no new elements will be added.
 802         /// </summary>
 803         public void TrimExcess(int capacity)
 804         {
 805             if (capacity < Count)
 806                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
 807             int newSize = HashHelpers.GetPrime(capacity);
 808
 809             Entry[] oldEntries = _entries;
 810             int currentCapacity = oldEntries == null ? 0 : oldEntries.Length;
 811             if (newSize >= currentCapacity)
 812                 return;
 813
 814             int oldCount = _count;
 815             Initialize(newSize);
 816             Entry[] entries = _entries;
 817             int[] buckets = _buckets;
 818             int count = 0;
 819             for (int i = 0; i < oldCount; i++)
 820             {
 821                 int hashCode = oldEntries[i].hashCode;
 822                 if (hashCode >= 0)
 823                 {
 824                     ref Entry entry = ref entries[count];
 825                     entry = oldEntries[i];
 826                     int bucket = hashCode % newSize;
 827                     entry.next = buckets[bucket];
 828                     buckets[bucket] = count;
 829                     count++;
 830                 }
 831             }
 832             _count = count;
 833             _freeCount = 0;
 834         }
 835
 836         bool ICollection.IsSynchronized
 837         {
 838             get { return false; }
 839         }
 840
 841         object ICollection.SyncRoot
 842         {
 843             get
 844             {
 845                 if (_syncRoot == null)
 846                 {
 847                     System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
 848                 }
 849                 return _syncRoot;
 850             }
 851         }
 852
 853         bool IDictionary.IsFixedSize
 854         {
 855             get { return false; }
 856         }
 857
 858         bool IDictionary.IsReadOnly
 859         {
 860             get { return false; }
 861         }
 862
 863         ICollection IDictionary.Keys
 864         {
 865             get { return (ICollection)Keys; }
 866         }
 867
 868         ICollection IDictionary.Values
 869         {
 870             get { return (ICollection)Values; }
 871         }
 872
 873         object IDictionary.this[object key]
 874         {
 875             get
 876             {
 877                 if (IsCompatibleKey(key))
 878                 {
 879                     int i = FindEntry((TKey)key);
 880                     if (i >= 0)
 881                     {
 882                         return _entries[i].value;
 883                     }
 884                 }
 885                 return null;
 886             }
 887             set
 888             {
 889                 if (key == null)
 890                 {
 891                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 892                 }
 893                 ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value);
 894
 895                 try
 896                 {
 897                     TKey tempKey = (TKey)key;
 898                     try
 899                     {
 900                         this[tempKey] = (TValue)value;
 901                     }
 902                     catch (InvalidCastException)
 903                     {
 904                         ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
 905                     }
 906                 }
 907                 catch (InvalidCastException)
 908                 {
 909                     ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey));
 910                 }
 911             }
 912         }
 913
 914         private static bool IsCompatibleKey(object key)
 915         {
 916             if (key == null)
 917             {
 918                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 919             }
 920             return (key is TKey);
 921         }
 922
 923         void IDictionary.Add(object key, object value)
 924         {
 925             if (key == null)
 926             {
 927                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 928             }
 929             ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value);
 930
 931             try
 932             {
 933                 TKey tempKey = (TKey)key;
 934
 935                 try
 936                 {
 937                     Add(tempKey, (TValue)value);
 938                 }
 939                 catch (InvalidCastException)
 940                 {
 941                     ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
 942                 }
 943             }
 944             catch (InvalidCastException)
 945             {
 946                 ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey));
 947             }
 948         }
 949
 950         bool IDictionary.Contains(object key)
 951         {
 952             if (IsCompatibleKey(key))
 953             {
 954                 return ContainsKey((TKey)key);
 955             }
 956
 957             return false;
 958         }
 959
 960         IDictionaryEnumerator IDictionary.GetEnumerator()
 961         {
 962             return new Enumerator(this, Enumerator.DictEntry);
 963         }
 964
 965         void IDictionary.Remove(object key)
 966         {
 967             if (IsCompatibleKey(key))
 968             {
 969                 Remove((TKey)key);
 970             }
 971         }
 972
 973         public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>,
 974             IDictionaryEnumerator
 975         {
 976             private Dictionary<TKey, TValue> _dictionary;
 977             private int _version;
 978             private int _index;
 979             private KeyValuePair<TKey, TValue> _current;
 980             private int _getEnumeratorRetType;  // What should Enumerator.Current return?
 981
 982             internal const int DictEntry = 1;
 983             internal const int KeyValuePair = 2;
 984
 985             internal Enumerator(Dictionary<TKey, TValue> dictionary, int getEnumeratorRetType)
 986             {
 987                 _dictionary = dictionary;
 988                 _version = dictionary._version;
 989                 _index = 0;
 990                 _getEnumeratorRetType = getEnumeratorRetType;
 991                 _current = new KeyValuePair<TKey, TValue>();
 992             }
 993
 994             public bool MoveNext()
 995             {
 996                 if (_version != _dictionary._version)
 997                 {
 998                     ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
 999                 }
1000
1001                 // Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends.
1002                 // dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue
1003                 while ((uint)_index < (uint)_dictionary._count)
1004                 {
1005                     ref Entry entry = ref _dictionary._entries[_index++];
1006
1007                     if (entry.hashCode >= 0)
1008                     {
1009                         _current = new KeyValuePair<TKey, TValue>(entry.key, entry.value);
1010                         return true;
1011                     }
1012                 }
1013
1014                 _index = _dictionary._count + 1;
1015                 _current = new KeyValuePair<TKey, TValue>();
1016                 return false;
1017             }
1018
1019             public KeyValuePair<TKey, TValue> Current
1020             {
1021                 get { return _current; }
1022             }
1023
1024             public void Dispose()
1025             {
1026             }
1027
1028             object IEnumerator.Current
1029             {
1030                 get
1031                 {
1032                     if (_index == 0 || (_index == _dictionary._count + 1))
1033                     {
1034                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1035                     }
1036
1037                     if (_getEnumeratorRetType == DictEntry)
1038                     {
1039                         return new System.Collections.DictionaryEntry(_current.Key, _current.Value);
1040                     }
1041                     else
1042                     {
1043                         return new KeyValuePair<TKey, TValue>(_current.Key, _current.Value);
1044                     }
1045                 }
1046             }
1047
1048             void IEnumerator.Reset()
1049             {
1050                 if (_version != _dictionary._version)
1051                 {
1052                     ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1053                 }
1054
1055                 _index = 0;
1056                 _current = new KeyValuePair<TKey, TValue>();
1057             }
1058
1059             DictionaryEntry IDictionaryEnumerator.Entry
1060             {
1061                 get
1062                 {
1063                     if (_index == 0 || (_index == _dictionary._count + 1))
1064                     {
1065                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1066                     }
1067
1068                     return new DictionaryEntry(_current.Key, _current.Value);
1069                 }
1070             }
1071
1072             object IDictionaryEnumerator.Key
1073             {
1074                 get
1075                 {
1076                     if (_index == 0 || (_index == _dictionary._count + 1))
1077                     {
1078                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1079                     }
1080
1081                     return _current.Key;
1082                 }
1083             }
1084
1085             object IDictionaryEnumerator.Value
1086             {
1087                 get
1088                 {
1089                     if (_index == 0 || (_index == _dictionary._count + 1))
1090                     {
1091                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1092                     }
1093
1094                     return _current.Value;
1095                 }
1096             }
1097         }
1098
1099         [DebuggerTypeProxy(typeof(DictionaryKeyCollectionDebugView<,>))]
1100         [DebuggerDisplay("Count = {Count}")]
1101         public sealed class KeyCollection : ICollection<TKey>, ICollection, IReadOnlyCollection<TKey>
1102         {
1103             private Dictionary<TKey, TValue> _dictionary;
1104
1105             public KeyCollection(Dictionary<TKey, TValue> dictionary)
1106             {
1107                 if (dictionary == null)
1108                 {
1109                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
1110                 }
1111                 _dictionary = dictionary;
1112             }
1113
1114             public Enumerator GetEnumerator()
1115             {
1116                 return new Enumerator(_dictionary);
1117             }
1118
1119             public void CopyTo(TKey[] array, int index)
1120             {
1121                 if (array == null)
1122                 {
1123                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1124                 }
1125
1126                 if (index < 0 || index > array.Length)
1127                 {
1128                     ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1129                 }
1130
1131                 if (array.Length - index < _dictionary.Count)
1132                 {
1133                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
1134                 }
1135
1136                 int count = _dictionary._count;
1137                 Entry[] entries = _dictionary._entries;
1138                 for (int i = 0; i < count; i++)
1139                 {
1140                     if (entries[i].hashCode >= 0) array[index++] = entries[i].key;
1141                 }
1142             }
1143
1144             public int Count
1145             {
1146                 get { return _dictionary.Count; }
1147             }
1148
1149             bool ICollection<TKey>.IsReadOnly
1150             {
1151                 get { return true; }
1152             }
1153
1154             void ICollection<TKey>.Add(TKey item)
1155             {
1156                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
1157             }
1158
1159             void ICollection<TKey>.Clear()
1160             {
1161                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
1162             }
1163
1164             bool ICollection<TKey>.Contains(TKey item)
1165             {
1166                 return _dictionary.ContainsKey(item);
1167             }
1168
1169             bool ICollection<TKey>.Remove(TKey item)
1170             {
1171                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
1172                 return false;
1173             }
1174
1175             IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator()
1176             {
1177                 return new Enumerator(_dictionary);
1178             }
1179
1180             IEnumerator IEnumerable.GetEnumerator()
1181             {
1182                 return new Enumerator(_dictionary);
1183             }
1184
1185             void ICollection.CopyTo(Array array, int index)
1186             {
1187                 if (array == null)
1188                 {
1189                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1190                 }
1191
1192                 if (array.Rank != 1)
1193                 {
1194                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
1195                 }
1196
1197                 if (array.GetLowerBound(0) != 0)
1198                 {
1199                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
1200                 }
1201
1202                 if (index < 0 || index > array.Length)
1203                 {
1204                     ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1205                 }
1206
1207                 if (array.Length - index < _dictionary.Count)
1208                 {
1209                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
1210                 }
1211
1212                 TKey[] keys = array as TKey[];
1213                 if (keys != null)
1214                 {
1215                     CopyTo(keys, index);
1216                 }
1217                 else
1218                 {
1219                     object[] objects = array as object[];
1220                     if (objects == null)
1221                     {
1222                         ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
1223                     }
1224
1225                     int count = _dictionary._count;
1226                     Entry[] entries = _dictionary._entries;
1227                     try
1228                     {
1229                         for (int i = 0; i < count; i++)
1230                         {
1231                             if (entries[i].hashCode >= 0) objects[index++] = entries[i].key;
1232                         }
1233                     }
1234                     catch (ArrayTypeMismatchException)
1235                     {
1236                         ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
1237                     }
1238                 }
1239             }
1240
1241             bool ICollection.IsSynchronized
1242             {
1243                 get { return false; }
1244             }
1245
1246             object ICollection.SyncRoot
1247             {
1248                 get { return ((ICollection)_dictionary).SyncRoot; }
1249             }
1250
1251             public struct Enumerator : IEnumerator<TKey>, System.Collections.IEnumerator
1252             {
1253                 private Dictionary<TKey, TValue> _dictionary;
1254                 private int _index;
1255                 private int _version;
1256                 private TKey _currentKey;
1257
1258                 internal Enumerator(Dictionary<TKey, TValue> dictionary)
1259                 {
1260                     _dictionary = dictionary;
1261                     _version = dictionary._version;
1262                     _index = 0;
1263                     _currentKey = default(TKey);
1264                 }
1265
1266                 public void Dispose()
1267                 {
1268                 }
1269
1270                 public bool MoveNext()
1271                 {
1272                     if (_version != _dictionary._version)
1273                     {
1274                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1275                     }
1276
1277                     while ((uint)_index < (uint)_dictionary._count)
1278                     {
1279                         ref Entry entry = ref _dictionary._entries[_index++];
1280
1281                         if (entry.hashCode >= 0)
1282                         {
1283                             _currentKey = entry.key;
1284                             return true;
1285                         }
1286                     }
1287
1288                     _index = _dictionary._count + 1;
1289                     _currentKey = default(TKey);
1290                     return false;
1291                 }
1292
1293                 public TKey Current
1294                 {
1295                     get
1296                     {
1297                         return _currentKey;
1298                     }
1299                 }
1300
1301                 object System.Collections.IEnumerator.Current
1302                 {
1303                     get
1304                     {
1305                         if (_index == 0 || (_index == _dictionary._count + 1))
1306                         {
1307                             ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1308                         }
1309
1310                         return _currentKey;
1311                     }
1312                 }
1313
1314                 void System.Collections.IEnumerator.Reset()
1315                 {
1316                     if (_version != _dictionary._version)
1317                     {
1318                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1319                     }
1320
1321                     _index = 0;
1322                     _currentKey = default(TKey);
1323                 }
1324             }
1325         }
1326
1327         [DebuggerTypeProxy(typeof(DictionaryValueCollectionDebugView<,>))]
1328         [DebuggerDisplay("Count = {Count}")]
1329         public sealed class ValueCollection : ICollection<TValue>, ICollection, IReadOnlyCollection<TValue>
1330         {
1331             private Dictionary<TKey, TValue> _dictionary;
1332
1333             public ValueCollection(Dictionary<TKey, TValue> dictionary)
1334             {
1335                 if (dictionary == null)
1336                 {
1337                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
1338                 }
1339                 _dictionary = dictionary;
1340             }
1341
1342             public Enumerator GetEnumerator()
1343             {
1344                 return new Enumerator(_dictionary);
1345             }
1346
1347             public void CopyTo(TValue[] array, int index)
1348             {
1349                 if (array == null)
1350                 {
1351                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1352                 }
1353
1354                 if (index < 0 || index > array.Length)
1355                 {
1356                     ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1357                 }
1358
1359                 if (array.Length - index < _dictionary.Count)
1360                 {
1361                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
1362                 }
1363
1364                 int count = _dictionary._count;
1365                 Entry[] entries = _dictionary._entries;
1366                 for (int i = 0; i < count; i++)
1367                 {
1368                     if (entries[i].hashCode >= 0) array[index++] = entries[i].value;
1369                 }
1370             }
1371
1372             public int Count
1373             {
1374                 get { return _dictionary.Count; }
1375             }
1376
1377             bool ICollection<TValue>.IsReadOnly
1378             {
1379                 get { return true; }
1380             }
1381
1382             void ICollection<TValue>.Add(TValue item)
1383             {
1384                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
1385             }
1386
1387             bool ICollection<TValue>.Remove(TValue item)
1388             {
1389                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
1390                 return false;
1391             }
1392
1393             void ICollection<TValue>.Clear()
1394             {
1395                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
1396             }
1397
1398             bool ICollection<TValue>.Contains(TValue item)
1399             {
1400                 return _dictionary.ContainsValue(item);
1401             }
1402
1403             IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator()
1404             {
1405                 return new Enumerator(_dictionary);
1406             }
1407
1408             IEnumerator IEnumerable.GetEnumerator()
1409             {
1410                 return new Enumerator(_dictionary);
1411             }
1412
1413             void ICollection.CopyTo(Array array, int index)
1414             {
1415                 if (array == null)
1416                 {
1417                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1418                 }
1419
1420                 if (array.Rank != 1)
1421                 {
1422                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
1423                 }
1424
1425                 if (array.GetLowerBound(0) != 0)
1426                 {
1427                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
1428                 }
1429
1430                 if (index < 0 || index > array.Length)
1431                 {
1432                     ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1433                 }
1434
1435                 if (array.Length - index < _dictionary.Count)
1436                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
1437
1438                 TValue[] values = array as TValue[];
1439                 if (values != null)
1440                 {
1441                     CopyTo(values, index);
1442                 }
1443                 else
1444                 {
1445                     object[] objects = array as object[];
1446                     if (objects == null)
1447                     {
1448                         ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
1449                     }
1450
1451                     int count = _dictionary._count;
1452                     Entry[] entries = _dictionary._entries;
1453                     try
1454                     {
1455                         for (int i = 0; i < count; i++)
1456                         {
1457                             if (entries[i].hashCode >= 0) objects[index++] = entries[i].value;
1458                         }
1459                     }
1460                     catch (ArrayTypeMismatchException)
1461                     {
1462                         ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
1463                     }
1464                 }
1465             }
1466
1467             bool ICollection.IsSynchronized
1468             {
1469                 get { return false; }
1470             }
1471
1472             object ICollection.SyncRoot
1473             {
1474                 get { return ((ICollection)_dictionary).SyncRoot; }
1475             }
1476
1477             public struct Enumerator : IEnumerator<TValue>, System.Collections.IEnumerator
1478             {
1479                 private Dictionary<TKey, TValue> _dictionary;
1480                 private int _index;
1481                 private int _version;
1482                 private TValue _currentValue;
1483
1484                 internal Enumerator(Dictionary<TKey, TValue> dictionary)
1485                 {
1486                     _dictionary = dictionary;
1487                     _version = dictionary._version;
1488                     _index = 0;
1489                     _currentValue = default(TValue);
1490                 }
1491
1492                 public void Dispose()
1493                 {
1494                 }
1495
1496                 public bool MoveNext()
1497                 {
1498                     if (_version != _dictionary._version)
1499                     {
1500                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1501                     }
1502
1503                     while ((uint)_index < (uint)_dictionary._count)
1504                     {
1505                         ref Entry entry = ref _dictionary._entries[_index++];
1506
1507                         if (entry.hashCode >= 0)
1508                         {
1509                             _currentValue = entry.value;
1510                             return true;
1511                         }
1512                     }
1513                     _index = _dictionary._count + 1;
1514                     _currentValue = default(TValue);
1515                     return false;
1516                 }
1517
1518                 public TValue Current
1519                 {
1520                     get
1521                     {
1522                         return _currentValue;
1523                     }
1524                 }
1525
1526                 object System.Collections.IEnumerator.Current
1527                 {
1528                     get
1529                     {
1530                         if (_index == 0 || (_index == _dictionary._count + 1))
1531                         {
1532                             ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
1533                         }
1534
1535                         return _currentValue;
1536                     }
1537                 }
1538
1539                 void System.Collections.IEnumerator.Reset()
1540                 {
1541                     if (_version != _dictionary._version)
1542                     {
1543                         ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
1544                     }
1545                     _index = 0;
1546                     _currentValue = default(TValue);
1547                 }
1548             }
1549         }
1550     }
1551 }