mcs/class/corlib/System.Collections.Generic/Dictionary.cs

   1 //
   2 // System.Collections.Generic.Dictionary
   3 //
   4 // Authors:
   5 //      Sureshkumar T (tsureshkumar@novell.com)
   6 //      Marek Safar (marek.safar@gmail.com)
   7 //      Ankit Jain (radical@corewars.org)
   8 //      David Waite (mass@akuma.org)
   9 //      Juraj Skripsky (js@hotfeet.ch)
  10 //
  11 //
  12 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  13 // Copyright (C) 2005 David Waite
  14 // Copyright (C) 2007 HotFeet GmbH (http://www.hotfeet.ch)
  15 //
  16 // Permission is hereby granted, free of charge, to any person obtaining
  17 // a copy of this software and associated documentation files (the
  18 // "Software"), to deal in the Software without restriction, including
  19 // without limitation the rights to use, copy, modify, merge, publish,
  20 // distribute, sublicense, and/or sell copies of the Software, and to
  21 // permit persons to whom the Software is furnished to do so, subject to
  22 // the following conditions:
  23 //
  24 // The above copyright notice and this permission notice shall be
  25 // included in all copies or substantial portions of the Software.
  26 //
  27 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  28 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  29 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  30 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  31 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  32 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  33 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  34 //
  35
  36
  37 using System;
  38 using System.Collections;
  39 using System.Collections.Generic;
  40 using System.Runtime.Serialization;
  41 using System.Security.Permissions;
  42 using System.Runtime.InteropServices;
  43 using System.Diagnostics;
  44
  45 namespace System.Collections.Generic {
  46
  47         /*
  48          * Declare this outside the main class so it doesn't have to be inflated for each
  49          * instantiation of Dictionary.
  50          */
  51         internal struct Link {
  52                 public int HashCode;
  53                 public int Next;
  54         }
  55
  56         [ComVisible(false)]
  57         [Serializable]
  58         [DebuggerDisplay ("Count={Count}")]
  59         [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
  60         public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>,
  61                 IDictionary,
  62                 ICollection,
  63                 ICollection<KeyValuePair<TKey, TValue>>,
  64                 IEnumerable<KeyValuePair<TKey, TValue>>,
  65                 ISerializable,
  66                 IDeserializationCallback
  67         {
  68                 // The implementation of this class uses a hash table and linked lists
  69                 // (see: http://msdn2.microsoft.com/en-us/library/ms379571(VS.80).aspx).
  70                 //
  71                 // We use a kind of "mini-heap" instead of reference-based linked lists:
  72                 // "keySlots" and "valueSlots" is the heap itself, it stores the data
  73                 // "linkSlots" contains information about how the slots in the heap
  74                 //             are connected into linked lists
  75                 //             In addition, the HashCode field can be used to check if the
  76                 //             corresponding key and value are present (HashCode has the
  77                 //             HASH_FLAG bit set in this case), so, to iterate over all the
  78                 //             items in the dictionary, simply iterate the linkSlots array
  79                 //             and check for the HASH_FLAG bit in the HashCode field.
  80                 //             For this reason, each time a hashcode is calculated, it needs
  81                 //             to be ORed with HASH_FLAG before comparing it with the save hashcode.
  82                 // "touchedSlots" and "emptySlot" manage the free space in the heap
  83
  84                 const int INITIAL_SIZE = 10;
  85                 const float DEFAULT_LOAD_FACTOR = (90f / 100);
  86                 const int NO_SLOT = -1;
  87                 const int HASH_FLAG = -2147483648;
  88
  89                 // The hash table contains indices into the linkSlots array
  90                 int [] table;
  91
  92                 // All (key,value) pairs are chained into linked lists. The connection
  93                 // information is stored in "linkSlots" along with the key's hash code
  94                 // (for performance reasons).
  95                 // TODO: get rid of the hash code in Link (this depends on a few
  96                 // JIT-compiler optimizations)
  97                 // Every link in "linkSlots" corresponds to the (key,value) pair
  98                 // in "keySlots"/"valueSlots" with the same index.
  99                 Link [] linkSlots;
 100                 TKey [] keySlots;
 101                 TValue [] valueSlots;
 102
 103                 // The number of slots in "linkSlots" and "keySlots"/"valueSlots" that
 104                 // are in use (i.e. filled with data) or have been used and marked as
 105                 // "empty" later on.
 106                 int touchedSlots;
 107
 108                 // The index of the first slot in the "empty slots chain".
 109                 // "Remove()" prepends the cleared slots to the empty chain.
 110                 // "Add()" fills the first slot in the empty slots chain with the
 111                 // added item (or increases "touchedSlots" if the chain itself is empty).
 112                 int emptySlot;
 113
 114                 // The number of (key,value) pairs in this dictionary.
 115                 int count;
 116
 117                 // The number of (key,value) pairs the dictionary can hold without
 118                 // resizing the hash table and the slots arrays.
 119                 int threshold;
 120
 121                 IEqualityComparer<TKey> hcp;
 122                 SerializationInfo serialization_info;
 123
 124                 // The number of changes made to this dictionary. Used by enumerators
 125                 // to detect changes and invalidate themselves.
 126                 int generation;
 127
 128                 public int Count {
 129                         get { return count; }
 130                 }
 131
 132                 public TValue this [TKey key] {
 133                         get {
 134                                 if (key == null)
 135                                         throw new ArgumentNullException ("key");
 136
 137                                 // get first item of linked list corresponding to given key
 138                                 int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 139                                 int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
 140
 141                                 // walk linked list until right slot is found or end is reached
 142                                 while (cur != NO_SLOT) {
 143                                         // The ordering is important for compatibility with MS and strange
 144                                         // Object.Equals () implementations
 145                                         if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 146                                                 return valueSlots [cur];
 147                                         cur = linkSlots [cur].Next;
 148                                 }
 149                                 throw new KeyNotFoundException ();
 150                         }
 151
 152                         set {
 153                                 if (key == null)
 154                                         throw new ArgumentNullException ("key");
 155
 156                                 // get first item of linked list corresponding to given key
 157                                 int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 158                                 int index = (hashCode & int.MaxValue) % table.Length;
 159                                 int cur = table [index] - 1;
 160
 161                                 // walk linked list until right slot (and its predecessor) is
 162                                 // found or end is reached
 163                                 int prev = NO_SLOT;
 164                                 if (cur != NO_SLOT) {
 165                                         do {
 166                                                 // The ordering is important for compatibility with MS and strange
 167                                                 // Object.Equals () implementations
 168                                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 169                                                         break;
 170                                                 prev = cur;
 171                                                 cur = linkSlots [cur].Next;
 172                                         } while (cur != NO_SLOT);
 173                                 }
 174
 175                                 // is there no slot for the given key yet?
 176                                 if (cur == NO_SLOT) {
 177                                         // there is no existing slot for the given key,
 178                                         // allocate one and prepend it to its corresponding linked
 179                                         // list
 180
 181                                         if (++count > threshold) {
 182                                                 Resize ();
 183                                                 index = (hashCode & int.MaxValue) % table.Length;
 184                                         }
 185
 186                                         // find an empty slot
 187                                         cur = emptySlot;
 188                                         if (cur == NO_SLOT)
 189                                                 cur = touchedSlots++;
 190                                         else
 191                                                 emptySlot = linkSlots [cur].Next;
 192
 193                                         // prepend the added item to its linked list,
 194                                         // update the hash table
 195                                         linkSlots [cur].Next = table [index] - 1;
 196                                         table [index] = cur + 1;
 197
 198                                         // store the new item and its hash code
 199                                         linkSlots [cur].HashCode = hashCode;
 200                                         keySlots [cur] = key;
 201                                 } else {
 202                                         // we already have a slot for the given key,
 203                                         // update the existing slot
 204
 205                                         // if the slot is not at the front of its linked list,
 206                                         // we move it there
 207                                         if (prev != NO_SLOT) {
 208                                                 linkSlots [prev].Next = linkSlots [cur].Next;
 209                                                 linkSlots [cur].Next = table [index] - 1;
 210                                                 table [index] = cur + 1;
 211                                         }
 212                                 }
 213
 214                                 // store the item's data itself
 215                                 valueSlots [cur] = value;
 216
 217                                 generation++;
 218                         }
 219                 }
 220
 221                 public Dictionary ()
 222                 {
 223                         Init (INITIAL_SIZE, null);
 224                 }
 225
 226                 public Dictionary (IEqualityComparer<TKey> comparer)
 227                 {
 228                         Init (INITIAL_SIZE, comparer);
 229                 }
 230
 231                 public Dictionary (IDictionary<TKey, TValue> dictionary)
 232                         : this (dictionary, null)
 233                 {
 234                 }
 235
 236                 public Dictionary (int capacity)
 237                 {
 238                         Init (capacity, null);
 239                 }
 240
 241                 public Dictionary (IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer)
 242                 {
 243                         if (dictionary == null)
 244                                 throw new ArgumentNullException ("dictionary");
 245                         int capacity = dictionary.Count;
 246                         Init (capacity, comparer);
 247                         foreach (KeyValuePair<TKey, TValue> entry in dictionary)
 248                                 this.Add (entry.Key, entry.Value);
 249                 }
 250
 251                 public Dictionary (int capacity, IEqualityComparer<TKey> comparer)
 252                 {
 253                         Init (capacity, comparer);
 254                 }
 255
 256                 protected Dictionary (SerializationInfo info, StreamingContext context)
 257                 {
 258                         serialization_info = info;
 259                 }
 260
 261                 private void Init (int capacity, IEqualityComparer<TKey> hcp)
 262                 {
 263                         if (capacity < 0)
 264                                 throw new ArgumentOutOfRangeException ("capacity");
 265                         this.hcp = (hcp != null) ? hcp : EqualityComparer<TKey>.Default;
 266                         if (capacity == 0)
 267                                 capacity = INITIAL_SIZE;
 268
 269                         /* Modify capacity so 'capacity' elements can be added without resizing */
 270                         capacity = (int)(capacity / DEFAULT_LOAD_FACTOR) + 1;
 271
 272                         InitArrays (capacity);
 273                         generation = 0;
 274                 }
 275
 276                 private void InitArrays (int size) {
 277                         table = new int [size];
 278
 279                         linkSlots = new Link [size];
 280                         emptySlot = NO_SLOT;
 281
 282                         keySlots = new TKey [size];
 283                         valueSlots = new TValue [size];
 284                         touchedSlots = 0;
 285
 286                         threshold = (int)(table.Length * DEFAULT_LOAD_FACTOR);
 287                         if (threshold == 0 && table.Length > 0)
 288                                 threshold = 1;
 289                 }
 290
 291                 void CopyToCheck (Array array, int index)
 292                 {
 293                         if (array == null)
 294                                 throw new ArgumentNullException ("array");
 295                         if (index < 0)
 296                                 throw new ArgumentOutOfRangeException ("index");
 297                         // we want no exception for index==array.Length && Count == 0
 298                         if (index > array.Length)
 299                                 throw new ArgumentException ("index larger than largest valid index of array");
 300                         if (array.Length - index < Count)
 301                                 throw new ArgumentException ("Destination array cannot hold the requested elements!");
 302                 }
 303
 304                 delegate TRet Transform<TRet> (TKey key, TValue value);
 305
 306                 void Do_CopyTo<TRet, TElem> (TElem [] array, int index, Transform<TRet> transform)
 307                         where TRet : TElem
 308                 {
 309                         for (int i = 0; i < touchedSlots; i++) {
 310                                 if ((linkSlots [i].HashCode & HASH_FLAG) != 0)
 311                                         array [index++] = transform (keySlots [i], valueSlots [i]);
 312                         }
 313                 }
 314
 315                 static KeyValuePair<TKey, TValue> make_pair (TKey key, TValue value)
 316                 {
 317                         return new KeyValuePair<TKey, TValue> (key, value);
 318                 }
 319
 320                 static TKey pick_key (TKey key, TValue value)
 321                 {
 322                         return key;
 323                 }
 324
 325                 static TValue pick_value (TKey key, TValue value)
 326                 {
 327                         return value;
 328                 }
 329
 330                 void CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
 331                 {
 332                         CopyToCheck (array, index);
 333                         Do_CopyTo<KeyValuePair<TKey, TValue>, KeyValuePair<TKey, TValue>> (array, index, make_pair);
 334                 }
 335
 336                 void Do_ICollectionCopyTo<TRet> (Array array, int index, Transform<TRet> transform)
 337                 {
 338                         Type src = typeof (TRet);
 339                         Type tgt = array.GetType ().GetElementType ();
 340
 341                         try {
 342                                 if ((src.IsPrimitive || tgt.IsPrimitive) && !tgt.IsAssignableFrom (src))
 343                                         throw new Exception (); // we don't care.  it'll get transformed to an ArgumentException below
 344
 345 #if BOOTSTRAP_BASIC
 346                                 // BOOTSTRAP: gmcs 2.4.x seems to have trouble compiling the alternative
 347                                 throw new Exception ();
 348 #else
 349                                 Do_CopyTo ((object []) array, index, transform);
 350 #endif
 351
 352                         } catch (Exception e) {
 353                                 throw new ArgumentException ("Cannot copy source collection elements to destination array", "array", e);
 354                         }
 355                 }
 356
 357                 private void Resize ()
 358                 {
 359                         // From the SDK docs:
 360                         //       Hashtable is automatically increased
 361                         //       to the smallest prime number that is larger
 362                         //       than twice the current number of Hashtable buckets
 363                         int newSize = Hashtable.ToPrime ((table.Length << 1) | 1);
 364
 365                         // allocate new hash table and link slots array
 366                         int [] newTable = new int [newSize];
 367                         Link [] newLinkSlots = new Link [newSize];
 368
 369                         for (int i = 0; i < table.Length; i++) {
 370                                 int cur = table [i] - 1;
 371                                 while (cur != NO_SLOT) {
 372                                         int hashCode = newLinkSlots [cur].HashCode = hcp.GetHashCode(keySlots [cur]) | HASH_FLAG;
 373                                         int index = (hashCode & int.MaxValue) % newSize;
 374                                         newLinkSlots [cur].Next = newTable [index] - 1;
 375                                         newTable [index] = cur + 1;
 376                                         cur = linkSlots [cur].Next;
 377                                 }
 378                         }
 379                         table = newTable;
 380                         linkSlots = newLinkSlots;
 381
 382                         // allocate new data slots, copy data
 383                         TKey [] newKeySlots = new TKey [newSize];
 384                         TValue [] newValueSlots = new TValue [newSize];
 385                         Array.Copy (keySlots, 0, newKeySlots, 0, touchedSlots);
 386                         Array.Copy (valueSlots, 0, newValueSlots, 0, touchedSlots);
 387                         keySlots = newKeySlots;
 388                         valueSlots = newValueSlots;
 389
 390                         threshold = (int)(newSize * DEFAULT_LOAD_FACTOR);
 391                 }
 392
 393                 public void Add (TKey key, TValue value)
 394                 {
 395                         if (key == null)
 396                                 throw new ArgumentNullException ("key");
 397
 398                         // get first item of linked list corresponding to given key
 399                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 400                         int index = (hashCode & int.MaxValue) % table.Length;
 401                         int cur = table [index] - 1;
 402
 403                         // walk linked list until end is reached (throw an exception if a
 404                         // existing slot is found having an equivalent key)
 405                         while (cur != NO_SLOT) {
 406                                 // The ordering is important for compatibility with MS and strange
 407                                 // Object.Equals () implementations
 408                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 409                                         throw new ArgumentException ("An element with the same key already exists in the dictionary.");
 410                                 cur = linkSlots [cur].Next;
 411                         }
 412
 413                         if (++count > threshold) {
 414                                 Resize ();
 415                                 index = (hashCode & int.MaxValue) % table.Length;
 416                         }
 417
 418                         // find an empty slot
 419                         cur = emptySlot;
 420                         if (cur == NO_SLOT)
 421                                 cur = touchedSlots++;
 422                         else
 423                                 emptySlot = linkSlots [cur].Next;
 424
 425                         // store the hash code of the added item,
 426                         // prepend the added item to its linked list,
 427                         // update the hash table
 428                         linkSlots [cur].HashCode = hashCode;
 429                         linkSlots [cur].Next = table [index] - 1;
 430                         table [index] = cur + 1;
 431
 432                         // store item's data
 433                         keySlots [cur] = key;
 434                         valueSlots [cur] = value;
 435
 436                         generation++;
 437                 }
 438
 439                 public IEqualityComparer<TKey> Comparer {
 440                         get { return hcp; }
 441                 }
 442
 443                 public void Clear ()
 444                 {
 445                         count = 0;
 446                         // clear the hash table
 447                         Array.Clear (table, 0, table.Length);
 448                         // clear arrays
 449                         Array.Clear (keySlots, 0, keySlots.Length);
 450                         Array.Clear (valueSlots, 0, valueSlots.Length);
 451                         Array.Clear (linkSlots, 0, linkSlots.Length);
 452
 453                         // empty the "empty slots chain"
 454                         emptySlot = NO_SLOT;
 455
 456                         touchedSlots = 0;
 457                         generation++;
 458                 }
 459
 460                 public bool ContainsKey (TKey key)
 461                 {
 462                         if (key == null)
 463                                 throw new ArgumentNullException ("key");
 464
 465                         // get first item of linked list corresponding to given key
 466                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 467                         int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
 468
 469                         // walk linked list until right slot is found or end is reached
 470                         while (cur != NO_SLOT) {
 471                                 // The ordering is important for compatibility with MS and strange
 472                                 // Object.Equals () implementations
 473                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 474                                         return true;
 475                                 cur = linkSlots [cur].Next;
 476                         }
 477
 478                         return false;
 479                 }
 480
 481                 public bool ContainsValue (TValue value)
 482                 {
 483                         IEqualityComparer<TValue> cmp = EqualityComparer<TValue>.Default;
 484
 485                         for (int i = 0; i < table.Length; i++) {
 486                                 int cur = table [i] - 1;
 487                                 while (cur != NO_SLOT) {
 488                                         if (cmp.Equals (valueSlots [cur], value))
 489                                                 return true;
 490                                         cur = linkSlots [cur].Next;
 491                                 }
 492                         }
 493                         return false;
 494                 }
 495
 496                 [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
 497                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 498                 {
 499                         if (info == null)
 500                                 throw new ArgumentNullException ("info");
 501
 502                         info.AddValue ("Version", generation);
 503                         info.AddValue ("Comparer", hcp);
 504                         // MS.NET expects either *no* KeyValuePairs field (when count = 0)
 505                         // or a non-null KeyValuePairs field. We don't omit the field to
 506                         // remain compatible with older monos, but we also doesn't serialize
 507                         // it as null to make MS.NET happy.
 508                         KeyValuePair<TKey, TValue> [] data = new KeyValuePair<TKey,TValue> [count];
 509                         if (count > 0)
 510                                 CopyTo (data, 0);
 511                         info.AddValue ("HashSize", table.Length);
 512                         info.AddValue ("KeyValuePairs", data);
 513                 }
 514
 515                 public virtual void OnDeserialization (object sender)
 516                 {
 517                         if (serialization_info == null)
 518                                 return;
 519
 520                         int hashSize = 0;
 521                         KeyValuePair<TKey, TValue> [] data = null;
 522
 523                         // We must use the enumerator because MS.NET doesn't
 524                         // serialize "KeyValuePairs" for count = 0.
 525                         SerializationInfoEnumerator e = serialization_info.GetEnumerator ();
 526                         while (e.MoveNext ()) {
 527                                 switch (e.Name) {
 528                                 case "Version":
 529                                         generation = (int) e.Value;
 530                                         break;
 531
 532                                 case "Comparer":
 533                                         hcp = (IEqualityComparer<TKey>) e.Value;
 534                                         break;
 535
 536                                 case "HashSize":
 537                                         hashSize = (int) e.Value;
 538                                         break;
 539
 540                                 case "KeyValuePairs":
 541                                         data = (KeyValuePair<TKey, TValue> []) e.Value;
 542                                         break;
 543                                 }
 544                         }
 545
 546                         if (hcp == null)
 547                                 hcp = EqualityComparer<TKey>.Default;
 548                         if (hashSize < INITIAL_SIZE)
 549                                 hashSize = INITIAL_SIZE;
 550                         InitArrays (hashSize);
 551                         count = 0;
 552
 553                         if (data != null) {
 554                                 for (int i = 0; i < data.Length; ++i)
 555                                         Add (data [i].Key, data [i].Value);
 556                         }
 557                         generation++;
 558                         serialization_info = null;
 559                 }
 560
 561                 public bool Remove (TKey key)
 562                 {
 563                         if (key == null)
 564                                 throw new ArgumentNullException ("key");
 565
 566                         // get first item of linked list corresponding to given key
 567                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 568                         int index = (hashCode & int.MaxValue) % table.Length;
 569                         int cur = table [index] - 1;
 570
 571                         // if there is no linked list, return false
 572                         if (cur == NO_SLOT)
 573                                 return false;
 574
 575                         // walk linked list until right slot (and its predecessor) is
 576                         // found or end is reached
 577                         int prev = NO_SLOT;
 578                         do {
 579                                 // The ordering is important for compatibility with MS and strange
 580                                 // Object.Equals () implementations
 581                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 582                                         break;
 583                                 prev = cur;
 584                                 cur = linkSlots [cur].Next;
 585                         } while (cur != NO_SLOT);
 586
 587                         // if we reached the end of the chain, return false
 588                         if (cur == NO_SLOT)
 589                                 return false;
 590
 591                         count--;
 592                         // remove slot from linked list
 593                         // is slot at beginning of linked list?
 594                         if (prev == NO_SLOT)
 595                                 table [index] = linkSlots [cur].Next + 1;
 596                         else
 597                                 linkSlots [prev].Next = linkSlots [cur].Next;
 598
 599                         // mark slot as empty and prepend it to "empty slots chain"
 600                         linkSlots [cur].Next = emptySlot;
 601                         emptySlot = cur;
 602
 603                         linkSlots [cur].HashCode = 0;
 604                         // clear empty key and value slots
 605                         keySlots [cur] = default (TKey);
 606                         valueSlots [cur] = default (TValue);
 607
 608                         generation++;
 609                         return true;
 610                 }
 611
 612                 public bool TryGetValue (TKey key, out TValue value)
 613                 {
 614                         if (key == null)
 615                                 throw new ArgumentNullException ("key");
 616
 617                         // get first item of linked list corresponding to given key
 618                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 619                         int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
 620
 621                         // walk linked list until right slot is found or end is reached
 622                         while (cur != NO_SLOT) {
 623                                 // The ordering is important for compatibility with MS and strange
 624                                 // Object.Equals () implementations
 625                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key)) {
 626                                         value = valueSlots [cur];
 627                                         return true;
 628                                 }
 629                                 cur = linkSlots [cur].Next;
 630                         }
 631
 632                         // we did not find the slot
 633                         value = default (TValue);
 634                         return false;
 635                 }
 636
 637                 ICollection<TKey> IDictionary<TKey, TValue>.Keys {
 638                         get { return Keys; }
 639                 }
 640
 641                 ICollection<TValue> IDictionary<TKey, TValue>.Values {
 642                         get { return Values; }
 643                 }
 644
 645                 public KeyCollection Keys {
 646                         get { return new KeyCollection (this); }
 647                 }
 648
 649                 public ValueCollection Values {
 650                         get { return new ValueCollection (this); }
 651                 }
 652
 653                 ICollection IDictionary.Keys {
 654                         get { return Keys; }
 655                 }
 656
 657                 ICollection IDictionary.Values {
 658                         get { return Values; }
 659                 }
 660
 661                 bool IDictionary.IsFixedSize {
 662                         get { return false; }
 663                 }
 664
 665                 bool IDictionary.IsReadOnly {
 666                         get { return false; }
 667                 }
 668
 669                 TKey ToTKey (object key)
 670                 {
 671                         if (key == null)
 672                                 throw new ArgumentNullException ("key");
 673                         if (!(key is TKey))
 674                                 throw new ArgumentException ("not of type: " + typeof (TKey).ToString (), "key");
 675                         return (TKey) key;
 676                 }
 677
 678                 TValue ToTValue (object value)
 679                 {
 680                         if (value == null && !typeof (TValue).IsValueType)
 681                                 return default (TValue);
 682                         if (!(value is TValue))
 683                                 throw new ArgumentException ("not of type: " + typeof (TValue).ToString (), "value");
 684                         return (TValue) value;
 685                 }
 686
 687                 object IDictionary.this [object key] {
 688                         get {
 689                                 if (key is TKey && ContainsKey((TKey) key))
 690                                         return this [ToTKey (key)];
 691                                 return null;
 692                         }
 693                         set { this [ToTKey (key)] = ToTValue (value); }
 694                 }
 695
 696                 void IDictionary.Add (object key, object value)
 697                 {
 698                         this.Add (ToTKey (key), ToTValue (value));
 699                 }
 700
 701                 bool IDictionary.Contains (object key)
 702                 {
 703                         if (key == null)
 704                                 throw new ArgumentNullException ("key");
 705                         if (key is TKey)
 706                                 return ContainsKey ((TKey) key);
 707                         return false;
 708                 }
 709
 710                 void IDictionary.Remove (object key)
 711                 {
 712                         if (key == null)
 713                                 throw new ArgumentNullException ("key");
 714                         if (key is TKey)
 715                                 Remove ((TKey) key);
 716                 }
 717
 718                 bool ICollection.IsSynchronized {
 719                         get { return false; }
 720                 }
 721
 722                 object ICollection.SyncRoot {
 723                         get { return this; }
 724                 }
 725
 726                 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 727                         get { return false; }
 728                 }
 729
 730                 void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair)
 731                 {
 732                         Add (keyValuePair.Key, keyValuePair.Value);
 733                 }
 734
 735                 bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> keyValuePair)
 736                 {
 737                         return ContainsKeyValuePair (keyValuePair);
 738                 }
 739
 740                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
 741                 {
 742                         this.CopyTo (array, index);
 743                 }
 744
 745                 bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> keyValuePair)
 746                 {
 747                         if (!ContainsKeyValuePair (keyValuePair))
 748                                 return false;
 749
 750                         return Remove (keyValuePair.Key);
 751                 }
 752
 753                 bool ContainsKeyValuePair (KeyValuePair<TKey, TValue> pair)
 754                 {
 755                         TValue value;
 756                         if (!TryGetValue (pair.Key, out value))
 757                                 return false;
 758
 759                         return EqualityComparer<TValue>.Default.Equals (pair.Value, value);
 760                 }
 761
 762                 void ICollection.CopyTo (Array array, int index)
 763                 {
 764                         KeyValuePair<TKey, TValue> [] pairs = array as KeyValuePair<TKey, TValue> [];
 765                         if (pairs != null) {
 766                                 this.CopyTo (pairs, index);
 767                                 return;
 768                         }
 769
 770                         CopyToCheck (array, index);
 771                         DictionaryEntry [] entries = array as DictionaryEntry [];
 772                         if (entries != null) {
 773                                 Do_CopyTo (entries, index, delegate (TKey key, TValue value) { return new DictionaryEntry (key, value); });
 774                                 return;
 775                         }
 776
 777                         Do_ICollectionCopyTo<KeyValuePair<TKey, TValue>> (array, index, make_pair);
 778                 }
 779
 780                 IEnumerator IEnumerable.GetEnumerator ()
 781                 {
 782                         return new Enumerator (this);
 783                 }
 784
 785                 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator ()
 786                 {
 787                         return new Enumerator (this);
 788                 }
 789
 790                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 791                 {
 792                         return new ShimEnumerator (this);
 793                 }
 794
 795                 public Enumerator GetEnumerator ()
 796                 {
 797                         return new Enumerator (this);
 798                 }
 799
 800                 [Serializable]
 801                 private class ShimEnumerator : IDictionaryEnumerator, IEnumerator
 802                 {
 803                         Enumerator host_enumerator;
 804                         public ShimEnumerator (Dictionary<TKey, TValue> host)
 805                         {
 806                                 host_enumerator = host.GetEnumerator ();
 807                         }
 808
 809                         public void Dispose ()
 810                         {
 811                                 host_enumerator.Dispose ();
 812                         }
 813
 814                         public bool MoveNext ()
 815                         {
 816                                 return host_enumerator.MoveNext ();
 817                         }
 818
 819                         public DictionaryEntry Entry {
 820                                 get { return ((IDictionaryEnumerator) host_enumerator).Entry; }
 821                         }
 822
 823                         public object Key {
 824                                 get { return host_enumerator.Current.Key; }
 825                         }
 826
 827                         public object Value {
 828                                 get { return host_enumerator.Current.Value; }
 829                         }
 830
 831                         // This is the raison d' etre of this $%!@$%@^@ class.
 832                         // We want: IDictionary.GetEnumerator ().Current is DictionaryEntry
 833                         public object Current {
 834                                 get { return Entry; }
 835                         }
 836
 837                         public void Reset ()
 838                         {
 839                                 host_enumerator.Reset ();
 840                         }
 841                 }
 842
 843                 [Serializable]
 844                 public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>,
 845                         IDisposable, IDictionaryEnumerator, IEnumerator
 846                 {
 847                         Dictionary<TKey, TValue> dictionary;
 848                         int next;
 849                         int stamp;
 850
 851                         internal KeyValuePair<TKey, TValue> current;
 852
 853                         internal Enumerator (Dictionary<TKey, TValue> dictionary)
 854                                 : this ()
 855                         {
 856                                 this.dictionary = dictionary;
 857                                 stamp = dictionary.generation;
 858                         }
 859
 860                         public bool MoveNext ()
 861                         {
 862                                 VerifyState ();
 863
 864                                 if (next < 0)
 865                                         return false;
 866
 867                                 while (next < dictionary.touchedSlots) {
 868                                         int cur = next++;
 869                                         if ((dictionary.linkSlots [cur].HashCode & HASH_FLAG) != 0) {
 870                                                 current = new KeyValuePair <TKey, TValue> (
 871                                                         dictionary.keySlots [cur],
 872                                                         dictionary.valueSlots [cur]
 873                                                         );
 874                                                 return true;
 875                                         }
 876                                 }
 877
 878                                 next = -1;
 879                                 return false;
 880                         }
 881
 882                         // No error checking happens.  Usually, Current is immediately preceded by a MoveNext(), so it's wasteful to check again
 883                         public KeyValuePair<TKey, TValue> Current {
 884                                 get { return current; }
 885                         }
 886
 887                         internal TKey CurrentKey {
 888                                 get {
 889                                         VerifyCurrent ();
 890                                         return current.Key;
 891                                 }
 892                         }
 893
 894                         internal TValue CurrentValue {
 895                                 get {
 896                                         VerifyCurrent ();
 897                                         return current.Value;
 898                                 }
 899                         }
 900
 901                         object IEnumerator.Current {
 902                                 get {
 903                                         VerifyCurrent ();
 904                                         return current;
 905                                 }
 906                         }
 907
 908                         void IEnumerator.Reset ()
 909                         {
 910                                 Reset ();
 911                         }
 912
 913                         internal void Reset ()
 914                         {
 915                                 VerifyState ();
 916                                 next = 0;
 917                         }
 918
 919                         DictionaryEntry IDictionaryEnumerator.Entry {
 920                                 get {
 921                                         VerifyCurrent ();
 922                                         return new DictionaryEntry (current.Key, current.Value);
 923                                 }
 924                         }
 925
 926                         object IDictionaryEnumerator.Key {
 927                                 get { return CurrentKey; }
 928                         }
 929
 930                         object IDictionaryEnumerator.Value {
 931                                 get { return CurrentValue; }
 932                         }
 933
 934                         void VerifyState ()
 935                         {
 936                                 if (dictionary == null)
 937                                         throw new ObjectDisposedException (null);
 938                                 if (dictionary.generation != stamp)
 939                                         throw new InvalidOperationException ("out of sync");
 940                         }
 941
 942                         void VerifyCurrent ()
 943                         {
 944                                 VerifyState ();
 945                                 if (next <= 0)
 946                                         throw new InvalidOperationException ("Current is not valid");
 947                         }
 948
 949                         public void Dispose ()
 950                         {
 951                                 dictionary = null;
 952                         }
 953                 }
 954
 955                 // This collection is a read only collection
 956                 [Serializable]
 957                 [DebuggerDisplay ("Count={Count}")]
 958                 [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
 959                 public sealed class KeyCollection : ICollection<TKey>, IEnumerable<TKey>, ICollection, IEnumerable {
 960                         Dictionary<TKey, TValue> dictionary;
 961
 962                         public KeyCollection (Dictionary<TKey, TValue> dictionary)
 963                         {
 964                                 if (dictionary == null)
 965                                         throw new ArgumentNullException ("dictionary");
 966                                 this.dictionary = dictionary;
 967                         }
 968
 969
 970                         public void CopyTo (TKey [] array, int index)
 971                         {
 972                                 dictionary.CopyToCheck (array, index);
 973                                 dictionary.Do_CopyTo<TKey, TKey> (array, index, pick_key);
 974                         }
 975
 976                         public Enumerator GetEnumerator ()
 977                         {
 978                                 return new Enumerator (dictionary);
 979                         }
 980
 981                         void ICollection<TKey>.Add (TKey item)
 982                         {
 983                                 throw new NotSupportedException ("this is a read-only collection");
 984                         }
 985
 986                         void ICollection<TKey>.Clear ()
 987                         {
 988                                 throw new NotSupportedException ("this is a read-only collection");
 989                         }
 990
 991                         bool ICollection<TKey>.Contains (TKey item)
 992                         {
 993                                 return dictionary.ContainsKey (item);
 994                         }
 995
 996                         bool ICollection<TKey>.Remove (TKey item)
 997                         {
 998                                 throw new NotSupportedException ("this is a read-only collection");
 999                         }
1000
1001                         IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
1002                         {
1003                                 return this.GetEnumerator ();
1004                         }
1005
1006                         void ICollection.CopyTo (Array array, int index)
1007                         {
1008                                 var target = array as TKey [];
1009                                 if (target != null) {
1010                                         CopyTo (target, index);
1011                                         return;
1012                                 }
1013
1014                                 dictionary.CopyToCheck (array, index);
1015                                 dictionary.Do_ICollectionCopyTo<TKey> (array, index, pick_key);
1016                         }
1017
1018                         IEnumerator IEnumerable.GetEnumerator ()
1019                         {
1020                                 return this.GetEnumerator ();
1021                         }
1022
1023                         public int Count {
1024                                 get { return dictionary.Count; }
1025                         }
1026
1027                         bool ICollection<TKey>.IsReadOnly {
1028                                 get { return true; }
1029                         }
1030
1031                         bool ICollection.IsSynchronized {
1032                                 get { return false; }
1033                         }
1034
1035                         object ICollection.SyncRoot {
1036                                 get { return ((ICollection) dictionary).SyncRoot; }
1037                         }
1038
1039                         [Serializable]
1040                         public struct Enumerator : IEnumerator<TKey>, IDisposable, IEnumerator {
1041                                 Dictionary<TKey, TValue>.Enumerator host_enumerator;
1042
1043                                 internal Enumerator (Dictionary<TKey, TValue> host)
1044                                 {
1045                                         host_enumerator = host.GetEnumerator ();
1046                                 }
1047
1048                                 public void Dispose ()
1049                                 {
1050                                         host_enumerator.Dispose ();
1051                                 }
1052
1053                                 public bool MoveNext ()
1054                                 {
1055                                         return host_enumerator.MoveNext ();
1056                                 }
1057
1058                                 public TKey Current {
1059                                         get { return host_enumerator.current.Key; }
1060                                 }
1061
1062                                 object IEnumerator.Current {
1063                                         get { return host_enumerator.CurrentKey; }
1064                                 }
1065
1066                                 void IEnumerator.Reset ()
1067                                 {
1068                                         host_enumerator.Reset ();
1069                                 }
1070                         }
1071                 }
1072
1073                 // This collection is a read only collection
1074                 [Serializable]
1075                 [DebuggerDisplay ("Count={Count}")]
1076                 [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
1077                 public sealed class ValueCollection : ICollection<TValue>, IEnumerable<TValue>, ICollection, IEnumerable {
1078                         Dictionary<TKey, TValue> dictionary;
1079
1080                         public ValueCollection (Dictionary<TKey, TValue> dictionary)
1081                         {
1082                                 if (dictionary == null)
1083                                         throw new ArgumentNullException ("dictionary");
1084                                 this.dictionary = dictionary;
1085                         }
1086
1087                         public void CopyTo (TValue [] array, int index)
1088                         {
1089                                 dictionary.CopyToCheck (array, index);
1090                                 dictionary.Do_CopyTo<TValue, TValue> (array, index, pick_value);
1091                         }
1092
1093                         public Enumerator GetEnumerator ()
1094                         {
1095                                 return new Enumerator (dictionary);
1096                         }
1097
1098                         void ICollection<TValue>.Add (TValue item)
1099                         {
1100                                 throw new NotSupportedException ("this is a read-only collection");
1101                         }
1102
1103                         void ICollection<TValue>.Clear ()
1104                         {
1105                                 throw new NotSupportedException ("this is a read-only collection");
1106                         }
1107
1108                         bool ICollection<TValue>.Contains (TValue item)
1109                         {
1110                                 return dictionary.ContainsValue (item);
1111                         }
1112
1113                         bool ICollection<TValue>.Remove (TValue item)
1114                         {
1115                                 throw new NotSupportedException ("this is a read-only collection");
1116                         }
1117
1118                         IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
1119                         {
1120                                 return this.GetEnumerator ();
1121                         }
1122
1123                         void ICollection.CopyTo (Array array, int index)
1124                         {
1125                                 var target = array as TValue [];
1126                                 if (target != null) {
1127                                         CopyTo (target, index);
1128                                         return;
1129                                 }
1130
1131                                 dictionary.CopyToCheck (array, index);
1132                                 dictionary.Do_ICollectionCopyTo<TValue> (array, index, pick_value);
1133                         }
1134
1135                         IEnumerator IEnumerable.GetEnumerator ()
1136                         {
1137                                 return this.GetEnumerator ();
1138                         }
1139
1140                         public int Count {
1141                                 get { return dictionary.Count; }
1142                         }
1143
1144                         bool ICollection<TValue>.IsReadOnly {
1145                                 get { return true; }
1146                         }
1147
1148                         bool ICollection.IsSynchronized {
1149                                 get { return false; }
1150                         }
1151
1152                         object ICollection.SyncRoot {
1153                                 get { return ((ICollection) dictionary).SyncRoot; }
1154                         }
1155
1156                         [Serializable]
1157                         public struct Enumerator : IEnumerator<TValue>, IDisposable, IEnumerator {
1158                                 Dictionary<TKey, TValue>.Enumerator host_enumerator;
1159
1160                                 internal Enumerator (Dictionary<TKey,TValue> host)
1161                                 {
1162                                         host_enumerator = host.GetEnumerator ();
1163                                 }
1164
1165                                 public void Dispose ()
1166                                 {
1167                                         host_enumerator.Dispose ();
1168                                 }
1169
1170                                 public bool MoveNext ()
1171                                 {
1172                                         return host_enumerator.MoveNext ();
1173                                 }
1174
1175                                 public TValue Current {
1176                                         get { return host_enumerator.current.Value; }
1177                                 }
1178
1179                                 object IEnumerator.Current {
1180                                         get { return host_enumerator.CurrentValue; }
1181                                 }
1182
1183                                 void IEnumerator.Reset ()
1184                                 {
1185                                         host_enumerator.Reset ();
1186                                 }
1187                         }
1188                 }
1189         }
1190 }