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