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                         KeyValuePair<TKey, TValue> [] data = null;
 505                         data = new KeyValuePair<TKey,TValue> [count];
 506                         if (count > 0)
 507                                 CopyTo (data, 0);
 508                         info.AddValue ("HashSize", table.Length);
 509                         info.AddValue ("KeyValuePairs", data);
 510                 }
 511
 512                 public virtual void OnDeserialization (object sender)
 513                 {
 514                         if (serialization_info == null)
 515                                 return;
 516
 517                         generation = serialization_info.GetInt32 ("Version");
 518                         hcp = (IEqualityComparer<TKey>) serialization_info.GetValue ("Comparer", typeof (IEqualityComparer<TKey>));
 519
 520                         int hashSize = serialization_info.GetInt32 ("HashSize");
 521                         KeyValuePair<TKey, TValue> [] data =
 522                                 (KeyValuePair<TKey, TValue> [])
 523                                 serialization_info.GetValue ("KeyValuePairs", typeof (KeyValuePair<TKey, TValue> []));
 524
 525                         if (hashSize < INITIAL_SIZE)
 526                                 hashSize = INITIAL_SIZE;
 527                         InitArrays (hashSize);
 528                         count = 0;
 529
 530                         if (data != null) {
 531                                 for (int i = 0; i < data.Length; ++i)
 532                                         Add (data [i].Key, data [i].Value);
 533                         }
 534                         generation++;
 535                         serialization_info = null;
 536                 }
 537
 538                 public bool Remove (TKey key)
 539                 {
 540                         if (key == null)
 541                                 throw new ArgumentNullException ("key");
 542
 543                         // get first item of linked list corresponding to given key
 544                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 545                         int index = (hashCode & int.MaxValue) % table.Length;
 546                         int cur = table [index] - 1;
 547
 548                         // if there is no linked list, return false
 549                         if (cur == NO_SLOT)
 550                                 return false;
 551
 552                         // walk linked list until right slot (and its predecessor) is
 553                         // found or end is reached
 554                         int prev = NO_SLOT;
 555                         do {
 556                                 // The ordering is important for compatibility with MS and strange
 557                                 // Object.Equals () implementations
 558                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 559                                         break;
 560                                 prev = cur;
 561                                 cur = linkSlots [cur].Next;
 562                         } while (cur != NO_SLOT);
 563
 564                         // if we reached the end of the chain, return false
 565                         if (cur == NO_SLOT)
 566                                 return false;
 567
 568                         count--;
 569                         // remove slot from linked list
 570                         // is slot at beginning of linked list?
 571                         if (prev == NO_SLOT)
 572                                 table [index] = linkSlots [cur].Next + 1;
 573                         else
 574                                 linkSlots [prev].Next = linkSlots [cur].Next;
 575
 576                         // mark slot as empty and prepend it to "empty slots chain"
 577                         linkSlots [cur].Next = emptySlot;
 578                         emptySlot = cur;
 579
 580                         linkSlots [cur].HashCode = 0;
 581                         // clear empty key and value slots
 582                         keySlots [cur] = default (TKey);
 583                         valueSlots [cur] = default (TValue);
 584
 585                         generation++;
 586                         return true;
 587                 }
 588
 589                 public bool TryGetValue (TKey key, out TValue value)
 590                 {
 591                         if (key == null)
 592                                 throw new ArgumentNullException ("key");
 593
 594                         // get first item of linked list corresponding to given key
 595                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 596                         int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
 597
 598                         // walk linked list until right slot is found or end is reached
 599                         while (cur != NO_SLOT) {
 600                                 // The ordering is important for compatibility with MS and strange
 601                                 // Object.Equals () implementations
 602                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key)) {
 603                                         value = valueSlots [cur];
 604                                         return true;
 605                                 }
 606                                 cur = linkSlots [cur].Next;
 607                         }
 608
 609                         // we did not find the slot
 610                         value = default (TValue);
 611                         return false;
 612                 }
 613
 614                 ICollection<TKey> IDictionary<TKey, TValue>.Keys {
 615                         get { return Keys; }
 616                 }
 617
 618                 ICollection<TValue> IDictionary<TKey, TValue>.Values {
 619                         get { return Values; }
 620                 }
 621
 622                 public KeyCollection Keys {
 623                         get { return new KeyCollection (this); }
 624                 }
 625
 626                 public ValueCollection Values {
 627                         get { return new ValueCollection (this); }
 628                 }
 629
 630                 ICollection IDictionary.Keys {
 631                         get { return Keys; }
 632                 }
 633
 634                 ICollection IDictionary.Values {
 635                         get { return Values; }
 636                 }
 637
 638                 bool IDictionary.IsFixedSize {
 639                         get { return false; }
 640                 }
 641
 642                 bool IDictionary.IsReadOnly {
 643                         get { return false; }
 644                 }
 645
 646                 TKey ToTKey (object key)
 647                 {
 648                         if (key == null)
 649                                 throw new ArgumentNullException ("key");
 650                         if (!(key is TKey))
 651                                 throw new ArgumentException ("not of type: " + typeof (TKey).ToString (), "key");
 652                         return (TKey) key;
 653                 }
 654
 655                 TValue ToTValue (object value)
 656                 {
 657                         if (value == null && !typeof (TValue).IsValueType)
 658                                 return default (TValue);
 659                         if (!(value is TValue))
 660                                 throw new ArgumentException ("not of type: " + typeof (TValue).ToString (), "value");
 661                         return (TValue) value;
 662                 }
 663
 664                 object IDictionary.this [object key] {
 665                         get {
 666                                 if (key is TKey && ContainsKey((TKey) key))
 667                                         return this [ToTKey (key)];
 668                                 return null;
 669                         }
 670                         set { this [ToTKey (key)] = ToTValue (value); }
 671                 }
 672
 673                 void IDictionary.Add (object key, object value)
 674                 {
 675                         this.Add (ToTKey (key), ToTValue (value));
 676                 }
 677
 678                 bool IDictionary.Contains (object key)
 679                 {
 680                         if (key == null)
 681                                 throw new ArgumentNullException ("key");
 682                         if (key is TKey)
 683                                 return ContainsKey ((TKey) key);
 684                         return false;
 685                 }
 686
 687                 void IDictionary.Remove (object key)
 688                 {
 689                         if (key == null)
 690                                 throw new ArgumentNullException ("key");
 691                         if (key is TKey)
 692                                 Remove ((TKey) key);
 693                 }
 694
 695                 bool ICollection.IsSynchronized {
 696                         get { return false; }
 697                 }
 698
 699                 object ICollection.SyncRoot {
 700                         get { return this; }
 701                 }
 702
 703                 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 704                         get { return false; }
 705                 }
 706
 707                 void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair)
 708                 {
 709                         Add (keyValuePair.Key, keyValuePair.Value);
 710                 }
 711
 712                 bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> keyValuePair)
 713                 {
 714                         return ContainsKeyValuePair (keyValuePair);
 715                 }
 716
 717                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
 718                 {
 719                         this.CopyTo (array, index);
 720                 }
 721
 722                 bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> keyValuePair)
 723                 {
 724                         if (!ContainsKeyValuePair (keyValuePair))
 725                                 return false;
 726
 727                         return Remove (keyValuePair.Key);
 728                 }
 729
 730                 bool ContainsKeyValuePair (KeyValuePair<TKey, TValue> pair)
 731                 {
 732                         TValue value;
 733                         if (!TryGetValue (pair.Key, out value))
 734                                 return false;
 735
 736                         return EqualityComparer<TValue>.Default.Equals (pair.Value, value);
 737                 }
 738
 739                 void ICollection.CopyTo (Array array, int index)
 740                 {
 741                         KeyValuePair<TKey, TValue> [] pairs = array as KeyValuePair<TKey, TValue> [];
 742                         if (pairs != null) {
 743                                 this.CopyTo (pairs, index);
 744                                 return;
 745                         }
 746
 747                         CopyToCheck (array, index);
 748                         DictionaryEntry [] entries = array as DictionaryEntry [];
 749                         if (entries != null) {
 750                                 Do_CopyTo (entries, index, delegate (TKey key, TValue value) { return new DictionaryEntry (key, value); });
 751                                 return;
 752                         }
 753
 754                         Do_ICollectionCopyTo<KeyValuePair<TKey, TValue>> (array, index, make_pair);
 755                 }
 756
 757                 IEnumerator IEnumerable.GetEnumerator ()
 758                 {
 759                         return new Enumerator (this);
 760                 }
 761
 762                 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator ()
 763                 {
 764                         return new Enumerator (this);
 765                 }
 766
 767                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 768                 {
 769                         return new ShimEnumerator (this);
 770                 }
 771
 772                 public Enumerator GetEnumerator ()
 773                 {
 774                         return new Enumerator (this);
 775                 }
 776
 777                 [Serializable]
 778                 private class ShimEnumerator : IDictionaryEnumerator, IEnumerator
 779                 {
 780                         Enumerator host_enumerator;
 781                         public ShimEnumerator (Dictionary<TKey, TValue> host)
 782                         {
 783                                 host_enumerator = host.GetEnumerator ();
 784                         }
 785
 786                         public void Dispose ()
 787                         {
 788                                 host_enumerator.Dispose ();
 789                         }
 790
 791                         public bool MoveNext ()
 792                         {
 793                                 return host_enumerator.MoveNext ();
 794                         }
 795
 796                         public DictionaryEntry Entry {
 797                                 get { return ((IDictionaryEnumerator) host_enumerator).Entry; }
 798                         }
 799
 800                         public object Key {
 801                                 get { return host_enumerator.Current.Key; }
 802                         }
 803
 804                         public object Value {
 805                                 get { return host_enumerator.Current.Value; }
 806                         }
 807
 808                         // This is the raison d' etre of this $%!@$%@^@ class.
 809                         // We want: IDictionary.GetEnumerator ().Current is DictionaryEntry
 810                         public object Current {
 811                                 get { return Entry; }
 812                         }
 813
 814                         public void Reset ()
 815                         {
 816                                 host_enumerator.Reset ();
 817                         }
 818                 }
 819
 820                 [Serializable]
 821                 public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>,
 822                         IDisposable, IDictionaryEnumerator, IEnumerator
 823                 {
 824                         Dictionary<TKey, TValue> dictionary;
 825                         int next;
 826                         int stamp;
 827
 828                         internal KeyValuePair<TKey, TValue> current;
 829
 830                         internal Enumerator (Dictionary<TKey, TValue> dictionary)
 831                                 : this ()
 832                         {
 833                                 this.dictionary = dictionary;
 834                                 stamp = dictionary.generation;
 835                         }
 836
 837                         public bool MoveNext ()
 838                         {
 839                                 VerifyState ();
 840
 841                                 if (next < 0)
 842                                         return false;
 843
 844                                 while (next < dictionary.touchedSlots) {
 845                                         int cur = next++;
 846                                         if ((dictionary.linkSlots [cur].HashCode & HASH_FLAG) != 0) {
 847                                                 current = new KeyValuePair <TKey, TValue> (
 848                                                         dictionary.keySlots [cur],
 849                                                         dictionary.valueSlots [cur]
 850                                                         );
 851                                                 return true;
 852                                         }
 853                                 }
 854
 855                                 next = -1;
 856                                 return false;
 857                         }
 858
 859                         // No error checking happens.  Usually, Current is immediately preceded by a MoveNext(), so it's wasteful to check again
 860                         public KeyValuePair<TKey, TValue> Current {
 861                                 get { return current; }
 862                         }
 863
 864                         internal TKey CurrentKey {
 865                                 get {
 866                                         VerifyCurrent ();
 867                                         return current.Key;
 868                                 }
 869                         }
 870
 871                         internal TValue CurrentValue {
 872                                 get {
 873                                         VerifyCurrent ();
 874                                         return current.Value;
 875                                 }
 876                         }
 877
 878                         object IEnumerator.Current {
 879                                 get {
 880                                         VerifyCurrent ();
 881                                         return current;
 882                                 }
 883                         }
 884
 885                         void IEnumerator.Reset ()
 886                         {
 887                                 Reset ();
 888                         }
 889
 890                         internal void Reset ()
 891                         {
 892                                 VerifyState ();
 893                                 next = 0;
 894                         }
 895
 896                         DictionaryEntry IDictionaryEnumerator.Entry {
 897                                 get {
 898                                         VerifyCurrent ();
 899                                         return new DictionaryEntry (current.Key, current.Value);
 900                                 }
 901                         }
 902
 903                         object IDictionaryEnumerator.Key {
 904                                 get { return CurrentKey; }
 905                         }
 906
 907                         object IDictionaryEnumerator.Value {
 908                                 get { return CurrentValue; }
 909                         }
 910
 911                         void VerifyState ()
 912                         {
 913                                 if (dictionary == null)
 914                                         throw new ObjectDisposedException (null);
 915                                 if (dictionary.generation != stamp)
 916                                         throw new InvalidOperationException ("out of sync");
 917                         }
 918
 919                         void VerifyCurrent ()
 920                         {
 921                                 VerifyState ();
 922                                 if (next <= 0)
 923                                         throw new InvalidOperationException ("Current is not valid");
 924                         }
 925
 926                         public void Dispose ()
 927                         {
 928                                 dictionary = null;
 929                         }
 930                 }
 931
 932                 // This collection is a read only collection
 933                 [Serializable]
 934                 [DebuggerDisplay ("Count={Count}")]
 935                 [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
 936                 public sealed class KeyCollection : ICollection<TKey>, IEnumerable<TKey>, ICollection, IEnumerable {
 937                         Dictionary<TKey, TValue> dictionary;
 938
 939                         public KeyCollection (Dictionary<TKey, TValue> dictionary)
 940                         {
 941                                 if (dictionary == null)
 942                                         throw new ArgumentNullException ("dictionary");
 943                                 this.dictionary = dictionary;
 944                         }
 945
 946
 947                         public void CopyTo (TKey [] array, int index)
 948                         {
 949                                 dictionary.CopyToCheck (array, index);
 950                                 dictionary.Do_CopyTo<TKey, TKey> (array, index, pick_key);
 951                         }
 952
 953                         public Enumerator GetEnumerator ()
 954                         {
 955                                 return new Enumerator (dictionary);
 956                         }
 957
 958                         void ICollection<TKey>.Add (TKey item)
 959                         {
 960                                 throw new NotSupportedException ("this is a read-only collection");
 961                         }
 962
 963                         void ICollection<TKey>.Clear ()
 964                         {
 965                                 throw new NotSupportedException ("this is a read-only collection");
 966                         }
 967
 968                         bool ICollection<TKey>.Contains (TKey item)
 969                         {
 970                                 return dictionary.ContainsKey (item);
 971                         }
 972
 973                         bool ICollection<TKey>.Remove (TKey item)
 974                         {
 975                                 throw new NotSupportedException ("this is a read-only collection");
 976                         }
 977
 978                         IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
 979                         {
 980                                 return this.GetEnumerator ();
 981                         }
 982
 983                         void ICollection.CopyTo (Array array, int index)
 984                         {
 985                                 var target = array as TKey [];
 986                                 if (target != null) {
 987                                         CopyTo (target, index);
 988                                         return;
 989                                 }
 990
 991                                 dictionary.CopyToCheck (array, index);
 992                                 dictionary.Do_ICollectionCopyTo<TKey> (array, index, pick_key);
 993                         }
 994
 995                         IEnumerator IEnumerable.GetEnumerator ()
 996                         {
 997                                 return this.GetEnumerator ();
 998                         }
 999
1000                         public int Count {
1001                                 get { return dictionary.Count; }
1002                         }
1003
1004                         bool ICollection<TKey>.IsReadOnly {
1005                                 get { return true; }
1006                         }
1007
1008                         bool ICollection.IsSynchronized {
1009                                 get { return false; }
1010                         }
1011
1012                         object ICollection.SyncRoot {
1013                                 get { return ((ICollection) dictionary).SyncRoot; }
1014                         }
1015
1016                         [Serializable]
1017                         public struct Enumerator : IEnumerator<TKey>, IDisposable, IEnumerator {
1018                                 Dictionary<TKey, TValue>.Enumerator host_enumerator;
1019
1020                                 internal Enumerator (Dictionary<TKey, TValue> host)
1021                                 {
1022                                         host_enumerator = host.GetEnumerator ();
1023                                 }
1024
1025                                 public void Dispose ()
1026                                 {
1027                                         host_enumerator.Dispose ();
1028                                 }
1029
1030                                 public bool MoveNext ()
1031                                 {
1032                                         return host_enumerator.MoveNext ();
1033                                 }
1034
1035                                 public TKey Current {
1036                                         get { return host_enumerator.current.Key; }
1037                                 }
1038
1039                                 object IEnumerator.Current {
1040                                         get { return host_enumerator.CurrentKey; }
1041                                 }
1042
1043                                 void IEnumerator.Reset ()
1044                                 {
1045                                         host_enumerator.Reset ();
1046                                 }
1047                         }
1048                 }
1049
1050                 // This collection is a read only collection
1051                 [Serializable]
1052                 [DebuggerDisplay ("Count={Count}")]
1053                 [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
1054                 public sealed class ValueCollection : ICollection<TValue>, IEnumerable<TValue>, ICollection, IEnumerable {
1055                         Dictionary<TKey, TValue> dictionary;
1056
1057                         public ValueCollection (Dictionary<TKey, TValue> dictionary)
1058                         {
1059                                 if (dictionary == null)
1060                                         throw new ArgumentNullException ("dictionary");
1061                                 this.dictionary = dictionary;
1062                         }
1063
1064                         public void CopyTo (TValue [] array, int index)
1065                         {
1066                                 dictionary.CopyToCheck (array, index);
1067                                 dictionary.Do_CopyTo<TValue, TValue> (array, index, pick_value);
1068                         }
1069
1070                         public Enumerator GetEnumerator ()
1071                         {
1072                                 return new Enumerator (dictionary);
1073                         }
1074
1075                         void ICollection<TValue>.Add (TValue item)
1076                         {
1077                                 throw new NotSupportedException ("this is a read-only collection");
1078                         }
1079
1080                         void ICollection<TValue>.Clear ()
1081                         {
1082                                 throw new NotSupportedException ("this is a read-only collection");
1083                         }
1084
1085                         bool ICollection<TValue>.Contains (TValue item)
1086                         {
1087                                 return dictionary.ContainsValue (item);
1088                         }
1089
1090                         bool ICollection<TValue>.Remove (TValue item)
1091                         {
1092                                 throw new NotSupportedException ("this is a read-only collection");
1093                         }
1094
1095                         IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
1096                         {
1097                                 return this.GetEnumerator ();
1098                         }
1099
1100                         void ICollection.CopyTo (Array array, int index)
1101                         {
1102                                 var target = array as TValue [];
1103                                 if (target != null) {
1104                                         CopyTo (target, index);
1105                                         return;
1106                                 }
1107
1108                                 dictionary.CopyToCheck (array, index);
1109                                 dictionary.Do_ICollectionCopyTo<TValue> (array, index, pick_value);
1110                         }
1111
1112                         IEnumerator IEnumerable.GetEnumerator ()
1113                         {
1114                                 return this.GetEnumerator ();
1115                         }
1116
1117                         public int Count {
1118                                 get { return dictionary.Count; }
1119                         }
1120
1121                         bool ICollection<TValue>.IsReadOnly {
1122                                 get { return true; }
1123                         }
1124
1125                         bool ICollection.IsSynchronized {
1126                                 get { return false; }
1127                         }
1128
1129                         object ICollection.SyncRoot {
1130                                 get { return ((ICollection) dictionary).SyncRoot; }
1131                         }
1132
1133                         [Serializable]
1134                         public struct Enumerator : IEnumerator<TValue>, IDisposable, IEnumerator {
1135                                 Dictionary<TKey, TValue>.Enumerator host_enumerator;
1136
1137                                 internal Enumerator (Dictionary<TKey,TValue> host)
1138                                 {
1139                                         host_enumerator = host.GetEnumerator ();
1140                                 }
1141
1142                                 public void Dispose ()
1143                                 {
1144                                         host_enumerator.Dispose ();
1145                                 }
1146
1147                                 public bool MoveNext ()
1148                                 {
1149                                         return host_enumerator.MoveNext ();
1150                                 }
1151
1152                                 public TValue Current {
1153                                         get { return host_enumerator.current.Value; }
1154                                 }
1155
1156                                 object IEnumerator.Current {
1157                                         get { return host_enumerator.CurrentValue; }
1158                                 }
1159
1160                                 void IEnumerator.Reset ()
1161                                 {
1162                                         host_enumerator.Reset ();
1163                                 }
1164                         }
1165                 }
1166         }
1167 }