1 // ==++== 2 // 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // 5 // ==--== 6 /*============================================================ 7 ** 8 ** Class: Dictionary 9 ** 10 ** <OWNER>Microsoft</OWNER> 11 ** 12 ** Purpose: Generic hash table implementation 13 ** 14 ** #DictionaryVersusHashtableThreadSafety 15 ** Hashtable has multiple reader/single writer (MR/SW) thread safety built into 16 ** certain methods and properties, whereas Dictionary doesn't. If you're 17 ** converting framework code that formerly used Hashtable to Dictionary, it's 18 ** important to consider whether callers may have taken a dependence on MR/SW 19 ** thread safety. If a reader writer lock is available, then that may be used 20 ** with a Dictionary to get the same thread safety guarantee. 21 ** 22 ** Reader writer locks don't exist in silverlight, so we do the following as a 23 ** result of removing non-generic collections from silverlight: 24 ** 1. If the Hashtable was fully synchronized, then we replace it with a 25 ** Dictionary with full locks around reads/writes (same thread safety 26 ** guarantee). 27 ** 2. Otherwise, the Hashtable has the default MR/SW thread safety behavior, 28 ** so we do one of the following on a case-by-case basis: 29 ** a. If the ---- can be addressed by rearranging the code and using a temp 30 ** variable (for example, it's only populated immediately after created) 31 ** then we address the ---- this way and use Dictionary. 32 ** b. If there's concern about degrading performance with the increased 33 ** locking, we ifdef with FEATURE_NONGENERIC_COLLECTIONS so we can at 34 ** least use Hashtable in the desktop build, but Dictionary with full 35 ** locks in silverlight builds. Note that this is heavier locking than 36 ** MR/SW, but this is the only option without rewriting (or adding back) 37 ** the reader writer lock. 38 ** c. If there's no performance concern (e.g. debug-only code) we 39 ** consistently replace Hashtable with Dictionary plus full locks to 40 ** reduce complexity. 41 ** d. Most of serialization is dead code in silverlight. Instead of updating 42 ** those Hashtable occurences in serialization, we carved out references 43 ** to serialization such that this code doesn't need to build in 44 ** silverlight. 45 ===========================================================*/ 46 namespace System.Collections.Generic { 47 48 using System; 49 using System.Collections; 50 using System.Diagnostics; 51 using System.Diagnostics.Contracts; 52 using System.Runtime.Serialization; 53 using System.Security.Permissions; 54 55 [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))] 56 [DebuggerDisplay("Count = {Count}")] 57 [Serializable] 58 [System.Runtime.InteropServices.ComVisible(false)] 59 public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback { 60 61 private struct Entry { 62 public int hashCode; // Lower 31 bits of hash code, -1 if unused 63 public int next; // Index of next entry, -1 if last 64 public TKey key; // Key of entry 65 public TValue value; // Value of entry 66 } 67 68 private int[] buckets; 69 private Entry[] entries; 70 private int count; 71 private int version; 72 private int freeList; 73 private int freeCount; 74 private IEqualityComparer<TKey> comparer; 75 private KeyCollection keys; 76 private ValueCollection values; 77 private Object _syncRoot; 78 79 // constants for serialization 80 private const String VersionName = "Version"; 81 private const String HashSizeName = "HashSize"; // Must save buckets.Length 82 private const String KeyValuePairsName = "KeyValuePairs"; 83 private const String ComparerName = "Comparer"; 84 Dictionary()85 public Dictionary(): this(0, null) {} 86 Dictionary(int capacity)87 public Dictionary(int capacity): this(capacity, null) {} 88 Dictionary(IEqualityComparer<TKey> comparer)89 public Dictionary(IEqualityComparer<TKey> comparer): this(0, comparer) {} 90 Dictionary(int capacity, IEqualityComparer<TKey> comparer)91 public Dictionary(int capacity, IEqualityComparer<TKey> comparer) { 92 if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity); 93 if (capacity > 0) Initialize(capacity); 94 this.comparer = comparer ?? EqualityComparer<TKey>.Default; 95 96 #if FEATURE_CORECLR 97 if (HashHelpers.s_UseRandomizedStringHashing && comparer == EqualityComparer<string>.Default) 98 { 99 this.comparer = (IEqualityComparer<TKey>) NonRandomizedStringEqualityComparer.Default; 100 } 101 #endif // FEATURE_CORECLR 102 } 103 Dictionary(IDictionary<TKey,TValue> dictionary)104 public Dictionary(IDictionary<TKey,TValue> dictionary): this(dictionary, null) {} 105 Dictionary(IDictionary<TKey,TValue> dictionary, IEqualityComparer<TKey> comparer)106 public Dictionary(IDictionary<TKey,TValue> dictionary, IEqualityComparer<TKey> comparer): 107 this(dictionary != null? dictionary.Count: 0, comparer) { 108 109 if( dictionary == null) { 110 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); 111 } 112 113 foreach (KeyValuePair<TKey,TValue> pair in dictionary) { 114 Add(pair.Key, pair.Value); 115 } 116 } 117 Dictionary(SerializationInfo info, StreamingContext context)118 protected Dictionary(SerializationInfo info, StreamingContext context) { 119 //We can't do anything with the keys and values until the entire graph has been deserialized 120 //and we have a resonable estimate that GetHashCode is not going to fail. For the time being, 121 //we'll just cache this. The graph is not valid until OnDeserialization has been called. 122 HashHelpers.SerializationInfoTable.Add(this, info); 123 } 124 125 public IEqualityComparer<TKey> Comparer { 126 get { 127 return comparer; 128 } 129 } 130 131 public int Count { 132 get { return count - freeCount; } 133 } 134 135 public KeyCollection Keys { 136 get { 137 Contract.Ensures(Contract.Result<KeyCollection>() != null); 138 if (keys == null) keys = new KeyCollection(this); 139 return keys; 140 } 141 } 142 143 ICollection<TKey> IDictionary<TKey, TValue>.Keys { 144 get { 145 if (keys == null) keys = new KeyCollection(this); 146 return keys; 147 } 148 } 149 150 IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys { 151 get { 152 if (keys == null) keys = new KeyCollection(this); 153 return keys; 154 } 155 } 156 157 public ValueCollection Values { 158 get { 159 Contract.Ensures(Contract.Result<ValueCollection>() != null); 160 if (values == null) values = new ValueCollection(this); 161 return values; 162 } 163 } 164 165 ICollection<TValue> IDictionary<TKey, TValue>.Values { 166 get { 167 if (values == null) values = new ValueCollection(this); 168 return values; 169 } 170 } 171 172 IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values { 173 get { 174 if (values == null) values = new ValueCollection(this); 175 return values; 176 } 177 } 178 179 public TValue this[TKey key] { 180 get { 181 int i = FindEntry(key); 182 if (i >= 0) return entries[i].value; 183 ThrowHelper.ThrowKeyNotFoundException(); 184 return default(TValue); 185 } 186 set { 187 Insert(key, value, false); 188 } 189 } 190 Add(TKey key, TValue value)191 public void Add(TKey key, TValue value) { 192 Insert(key, value, true); 193 } 194 Add(KeyValuePair<TKey, TValue> keyValuePair)195 void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair) { 196 Add(keyValuePair.Key, keyValuePair.Value); 197 } 198 Contains(KeyValuePair<TKey, TValue> keyValuePair)199 bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair) { 200 int i = FindEntry(keyValuePair.Key); 201 if( i >= 0 && EqualityComparer<TValue>.Default.Equals(entries[i].value, keyValuePair.Value)) { 202 return true; 203 } 204 return false; 205 } 206 Remove(KeyValuePair<TKey, TValue> keyValuePair)207 bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair) { 208 int i = FindEntry(keyValuePair.Key); 209 if( i >= 0 && EqualityComparer<TValue>.Default.Equals(entries[i].value, keyValuePair.Value)) { 210 Remove(keyValuePair.Key); 211 return true; 212 } 213 return false; 214 } 215 Clear()216 public void Clear() { 217 if (count > 0) { 218 for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; 219 Array.Clear(entries, 0, count); 220 freeList = -1; 221 count = 0; 222 freeCount = 0; 223 version++; 224 } 225 } 226 ContainsKey(TKey key)227 public bool ContainsKey(TKey key) { 228 return FindEntry(key) >= 0; 229 } 230 ContainsValue(TValue value)231 public bool ContainsValue(TValue value) { 232 if (value == null) { 233 for (int i = 0; i < count; i++) { 234 if (entries[i].hashCode >= 0 && entries[i].value == null) return true; 235 } 236 } 237 else { 238 EqualityComparer<TValue> c = EqualityComparer<TValue>.Default; 239 for (int i = 0; i < count; i++) { 240 if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true; 241 } 242 } 243 return false; 244 } 245 CopyTo(KeyValuePair<TKey,TValue>[] array, int index)246 private void CopyTo(KeyValuePair<TKey,TValue>[] array, int index) { 247 if (array == null) { 248 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); 249 } 250 251 if (index < 0 || index > array.Length ) { 252 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); 253 } 254 255 if (array.Length - index < Count) { 256 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 257 } 258 259 int count = this.count; 260 Entry[] entries = this.entries; 261 for (int i = 0; i < count; i++) { 262 if (entries[i].hashCode >= 0) { 263 array[index++] = new KeyValuePair<TKey,TValue>(entries[i].key, entries[i].value); 264 } 265 } 266 } 267 GetEnumerator()268 public Enumerator GetEnumerator() { 269 return new Enumerator(this, Enumerator.KeyValuePair); 270 } 271 GetEnumerator()272 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() { 273 return new Enumerator(this, Enumerator.KeyValuePair); 274 } 275 276 [System.Security.SecurityCritical] // auto-generated_required GetObjectData(SerializationInfo info, StreamingContext context)277 public virtual void GetObjectData(SerializationInfo info, StreamingContext context) { 278 if (info==null) { 279 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info); 280 } 281 info.AddValue(VersionName, version); 282 283 #if FEATURE_RANDOMIZED_STRING_HASHING 284 info.AddValue(ComparerName, HashHelpers.GetEqualityComparerForSerialization(comparer), typeof(IEqualityComparer<TKey>)); 285 #else 286 info.AddValue(ComparerName, comparer, typeof(IEqualityComparer<TKey>)); 287 #endif 288 289 info.AddValue(HashSizeName, buckets == null ? 0 : buckets.Length); //This is the length of the bucket array. 290 if( buckets != null) { 291 KeyValuePair<TKey, TValue>[] array = new KeyValuePair<TKey, TValue>[Count]; 292 CopyTo(array, 0); 293 info.AddValue(KeyValuePairsName, array, typeof(KeyValuePair<TKey, TValue>[])); 294 } 295 } 296 FindEntry(TKey key)297 private int FindEntry(TKey key) { 298 if( key == null) { 299 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 300 } 301 302 if (buckets != null) { 303 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; 304 for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) { 305 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i; 306 } 307 } 308 return -1; 309 } 310 Initialize(int capacity)311 private void Initialize(int capacity) { 312 int size = HashHelpers.GetPrime(capacity); 313 buckets = new int[size]; 314 for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; 315 entries = new Entry[size]; 316 freeList = -1; 317 } 318 Insert(TKey key, TValue value, bool add)319 private void Insert(TKey key, TValue value, bool add) { 320 321 if( key == null ) { 322 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 323 } 324 325 if (buckets == null) Initialize(0); 326 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; 327 int targetBucket = hashCode % buckets.Length; 328 329 #if FEATURE_RANDOMIZED_STRING_HASHING 330 int collisionCount = 0; 331 #endif 332 333 for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) { 334 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { 335 if (add) { 336 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); 337 } 338 entries[i].value = value; 339 version++; 340 return; 341 } 342 343 #if FEATURE_RANDOMIZED_STRING_HASHING 344 collisionCount++; 345 #endif 346 } 347 int index; 348 if (freeCount > 0) { 349 index = freeList; 350 freeList = entries[index].next; 351 freeCount--; 352 } 353 else { 354 if (count == entries.Length) 355 { 356 Resize(); 357 targetBucket = hashCode % buckets.Length; 358 } 359 index = count; 360 count++; 361 } 362 363 entries[index].hashCode = hashCode; 364 entries[index].next = buckets[targetBucket]; 365 entries[index].key = key; 366 entries[index].value = value; 367 buckets[targetBucket] = index; 368 version++; 369 370 #if FEATURE_RANDOMIZED_STRING_HASHING 371 372 #if FEATURE_CORECLR 373 // In case we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing 374 // in this case will be EqualityComparer<string>.Default. 375 // Note, randomized string hashing is turned on by default on coreclr so EqualityComparer<string>.Default will 376 // be using randomized string hashing 377 378 if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default) 379 { 380 comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default; 381 Resize(entries.Length, true); 382 } 383 #else 384 if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 385 { 386 comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer); 387 Resize(entries.Length, true); 388 } 389 #endif // FEATURE_CORECLR 390 391 #endif 392 393 } 394 OnDeserialization(Object sender)395 public virtual void OnDeserialization(Object sender) { 396 SerializationInfo siInfo; 397 HashHelpers.SerializationInfoTable.TryGetValue(this, out siInfo); 398 399 if (siInfo==null) { 400 // It might be necessary to call OnDeserialization from a container if the container object also implements 401 // OnDeserialization. However, remoting will call OnDeserialization again. 402 // We can return immediately if this function is called twice. 403 // Note we set remove the serialization info from the table at the end of this method. 404 return; 405 } 406 407 int realVersion = siInfo.GetInt32(VersionName); 408 int hashsize = siInfo.GetInt32(HashSizeName); 409 comparer = (IEqualityComparer<TKey>)siInfo.GetValue(ComparerName, typeof(IEqualityComparer<TKey>)); 410 411 if( hashsize != 0) { 412 buckets = new int[hashsize]; 413 for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; 414 entries = new Entry[hashsize]; 415 freeList = -1; 416 417 KeyValuePair<TKey, TValue>[] array = (KeyValuePair<TKey, TValue>[]) 418 siInfo.GetValue(KeyValuePairsName, typeof(KeyValuePair<TKey, TValue>[])); 419 420 if (array==null) { 421 ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingKeys); 422 } 423 424 for (int i=0; i<array.Length; i++) { 425 if ( array[i].Key == null) { 426 ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_NullKey); 427 } 428 Insert(array[i].Key, array[i].Value, true); 429 } 430 } 431 else { 432 buckets = null; 433 } 434 435 version = realVersion; 436 HashHelpers.SerializationInfoTable.Remove(this); 437 } 438 Resize()439 private void Resize() { 440 Resize(HashHelpers.ExpandPrime(count), false); 441 } 442 Resize(int newSize, bool forceNewHashCodes)443 private void Resize(int newSize, bool forceNewHashCodes) { 444 Contract.Assert(newSize >= entries.Length); 445 int[] newBuckets = new int[newSize]; 446 for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1; 447 Entry[] newEntries = new Entry[newSize]; 448 Array.Copy(entries, 0, newEntries, 0, count); 449 if(forceNewHashCodes) { 450 for (int i = 0; i < count; i++) { 451 if(newEntries[i].hashCode != -1) { 452 newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF); 453 } 454 } 455 } 456 for (int i = 0; i < count; i++) { 457 if (newEntries[i].hashCode >= 0) { 458 int bucket = newEntries[i].hashCode % newSize; 459 newEntries[i].next = newBuckets[bucket]; 460 newBuckets[bucket] = i; 461 } 462 } 463 buckets = newBuckets; 464 entries = newEntries; 465 } 466 Remove(TKey key)467 public bool Remove(TKey key) { 468 if(key == null) { 469 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 470 } 471 472 if (buckets != null) { 473 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; 474 int bucket = hashCode % buckets.Length; 475 int last = -1; 476 for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) { 477 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { 478 if (last < 0) { 479 buckets[bucket] = entries[i].next; 480 } 481 else { 482 entries[last].next = entries[i].next; 483 } 484 entries[i].hashCode = -1; 485 entries[i].next = freeList; 486 entries[i].key = default(TKey); 487 entries[i].value = default(TValue); 488 freeList = i; 489 freeCount++; 490 version++; 491 return true; 492 } 493 } 494 } 495 return false; 496 } 497 TryGetValue(TKey key, out TValue value)498 public bool TryGetValue(TKey key, out TValue value) { 499 int i = FindEntry(key); 500 if (i >= 0) { 501 value = entries[i].value; 502 return true; 503 } 504 value = default(TValue); 505 return false; 506 } 507 508 // This is a convenience method for the internal callers that were converted from using Hashtable. 509 // Many were combining key doesn't exist and key exists but null value (for non-value types) checks. 510 // This allows them to continue getting that behavior with minimal code delta. This is basically 511 // TryGetValue without the out param GetValueOrDefault(TKey key)512 internal TValue GetValueOrDefault(TKey key) { 513 int i = FindEntry(key); 514 if (i >= 0) { 515 return entries[i].value; 516 } 517 return default(TValue); 518 } 519 520 bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly { 521 get { return false; } 522 } 523 CopyTo(KeyValuePair<TKey,TValue>[] array, int index)524 void ICollection<KeyValuePair<TKey,TValue>>.CopyTo(KeyValuePair<TKey,TValue>[] array, int index) { 525 CopyTo(array, index); 526 } 527 ICollection.CopyTo(Array array, int index)528 void ICollection.CopyTo(Array array, int index) { 529 if (array == null) { 530 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); 531 } 532 533 if (array.Rank != 1) { 534 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); 535 } 536 537 if( array.GetLowerBound(0) != 0 ) { 538 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); 539 } 540 541 if (index < 0 || index > array.Length) { 542 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); 543 } 544 545 if (array.Length - index < Count) { 546 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 547 } 548 549 KeyValuePair<TKey,TValue>[] pairs = array as KeyValuePair<TKey,TValue>[]; 550 if (pairs != null) { 551 CopyTo(pairs, index); 552 } 553 else if( array is DictionaryEntry[]) { 554 DictionaryEntry[] dictEntryArray = array as DictionaryEntry[]; 555 Entry[] entries = this.entries; 556 for (int i = 0; i < count; i++) { 557 if (entries[i].hashCode >= 0) { 558 dictEntryArray[index++] = new DictionaryEntry(entries[i].key, entries[i].value); 559 } 560 } 561 } 562 else { 563 object[] objects = array as object[]; 564 if (objects == null) { 565 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); 566 } 567 568 try { 569 int count = this.count; 570 Entry[] entries = this.entries; 571 for (int i = 0; i < count; i++) { 572 if (entries[i].hashCode >= 0) { 573 objects[index++] = new KeyValuePair<TKey,TValue>(entries[i].key, entries[i].value); 574 } 575 } 576 } 577 catch(ArrayTypeMismatchException) { 578 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); 579 } 580 } 581 } 582 IEnumerable.GetEnumerator()583 IEnumerator IEnumerable.GetEnumerator() { 584 return new Enumerator(this, Enumerator.KeyValuePair); 585 } 586 587 bool ICollection.IsSynchronized { 588 get { return false; } 589 } 590 591 object ICollection.SyncRoot { 592 get { 593 if( _syncRoot == null) { 594 System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); 595 } 596 return _syncRoot; 597 } 598 } 599 600 bool IDictionary.IsFixedSize { 601 get { return false; } 602 } 603 604 bool IDictionary.IsReadOnly { 605 get { return false; } 606 } 607 608 ICollection IDictionary.Keys { 609 get { return (ICollection)Keys; } 610 } 611 612 ICollection IDictionary.Values { 613 get { return (ICollection)Values; } 614 } 615 616 object IDictionary.this[object key] { 617 get { 618 if( IsCompatibleKey(key)) { 619 int i = FindEntry((TKey)key); 620 if (i >= 0) { 621 return entries[i].value; 622 } 623 } 624 return null; 625 } 626 set { 627 if (key == null) 628 { 629 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 630 } 631 ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value); 632 633 try { 634 TKey tempKey = (TKey)key; 635 try { 636 this[tempKey] = (TValue)value; 637 } 638 catch (InvalidCastException) { 639 ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); 640 } 641 } 642 catch (InvalidCastException) { 643 ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); 644 } 645 } 646 } 647 IsCompatibleKey(object key)648 private static bool IsCompatibleKey(object key) { 649 if( key == null) { 650 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 651 } 652 return (key is TKey); 653 } 654 IDictionary.Add(object key, object value)655 void IDictionary.Add(object key, object value) { 656 if (key == null) 657 { 658 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 659 } 660 ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value); 661 662 try { 663 TKey tempKey = (TKey)key; 664 665 try { 666 Add(tempKey, (TValue)value); 667 } 668 catch (InvalidCastException) { 669 ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); 670 } 671 } 672 catch (InvalidCastException) { 673 ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); 674 } 675 } 676 IDictionary.Contains(object key)677 bool IDictionary.Contains(object key) { 678 if(IsCompatibleKey(key)) { 679 return ContainsKey((TKey)key); 680 } 681 682 return false; 683 } 684 IDictionary.GetEnumerator()685 IDictionaryEnumerator IDictionary.GetEnumerator() { 686 return new Enumerator(this, Enumerator.DictEntry); 687 } 688 IDictionary.Remove(object key)689 void IDictionary.Remove(object key) { 690 if(IsCompatibleKey(key)) { 691 Remove((TKey)key); 692 } 693 } 694 695 [Serializable] 696 public struct Enumerator: IEnumerator<KeyValuePair<TKey,TValue>>, 697 IDictionaryEnumerator 698 { 699 private Dictionary<TKey,TValue> dictionary; 700 private int version; 701 private int index; 702 private KeyValuePair<TKey,TValue> current; 703 private int getEnumeratorRetType; // What should Enumerator.Current return? 704 705 internal const int DictEntry = 1; 706 internal const int KeyValuePair = 2; 707 EnumeratorSystem.Collections.Generic.Dictionary.Enumerator708 internal Enumerator(Dictionary<TKey,TValue> dictionary, int getEnumeratorRetType) { 709 this.dictionary = dictionary; 710 version = dictionary.version; 711 index = 0; 712 this.getEnumeratorRetType = getEnumeratorRetType; 713 current = new KeyValuePair<TKey, TValue>(); 714 } 715 MoveNextSystem.Collections.Generic.Dictionary.Enumerator716 public bool MoveNext() { 717 if (version != dictionary.version) { 718 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 719 } 720 721 // Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends. 722 // dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue 723 while ((uint)index < (uint)dictionary.count) { 724 if (dictionary.entries[index].hashCode >= 0) { 725 current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value); 726 index++; 727 return true; 728 } 729 index++; 730 } 731 732 index = dictionary.count + 1; 733 current = new KeyValuePair<TKey, TValue>(); 734 return false; 735 } 736 737 public KeyValuePair<TKey,TValue> Current { 738 get { return current; } 739 } 740 DisposeSystem.Collections.Generic.Dictionary.Enumerator741 public void Dispose() { 742 } 743 744 object IEnumerator.Current { 745 get { 746 if( index == 0 || (index == dictionary.count + 1)) { 747 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 748 } 749 750 if (getEnumeratorRetType == DictEntry) { 751 return new System.Collections.DictionaryEntry(current.Key, current.Value); 752 } else { 753 return new KeyValuePair<TKey, TValue>(current.Key, current.Value); 754 } 755 } 756 } 757 IEnumerator.ResetSystem.Collections.Generic.Dictionary.Enumerator758 void IEnumerator.Reset() { 759 if (version != dictionary.version) { 760 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 761 } 762 763 index = 0; 764 current = new KeyValuePair<TKey, TValue>(); 765 } 766 767 DictionaryEntry IDictionaryEnumerator.Entry { 768 get { 769 if( index == 0 || (index == dictionary.count + 1)) { 770 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 771 } 772 773 return new DictionaryEntry(current.Key, current.Value); 774 } 775 } 776 777 object IDictionaryEnumerator.Key { 778 get { 779 if( index == 0 || (index == dictionary.count + 1)) { 780 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 781 } 782 783 return current.Key; 784 } 785 } 786 787 object IDictionaryEnumerator.Value { 788 get { 789 if( index == 0 || (index == dictionary.count + 1)) { 790 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 791 } 792 793 return current.Value; 794 } 795 } 796 } 797 798 [DebuggerTypeProxy(typeof(Mscorlib_DictionaryKeyCollectionDebugView<,>))] 799 [DebuggerDisplay("Count = {Count}")] 800 [Serializable] 801 public sealed class KeyCollection: ICollection<TKey>, ICollection, IReadOnlyCollection<TKey> 802 { 803 private Dictionary<TKey,TValue> dictionary; 804 KeyCollection(Dictionary<TKey,TValue> dictionary)805 public KeyCollection(Dictionary<TKey,TValue> dictionary) { 806 if (dictionary == null) { 807 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); 808 } 809 this.dictionary = dictionary; 810 } 811 GetEnumerator()812 public Enumerator GetEnumerator() { 813 return new Enumerator(dictionary); 814 } 815 CopyTo(TKey[] array, int index)816 public void CopyTo(TKey[] array, int index) { 817 if (array == null) { 818 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); 819 } 820 821 if (index < 0 || index > array.Length) { 822 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); 823 } 824 825 if (array.Length - index < dictionary.Count) { 826 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 827 } 828 829 int count = dictionary.count; 830 Entry[] entries = dictionary.entries; 831 for (int i = 0; i < count; i++) { 832 if (entries[i].hashCode >= 0) array[index++] = entries[i].key; 833 } 834 } 835 836 public int Count { 837 get { return dictionary.Count; } 838 } 839 840 bool ICollection<TKey>.IsReadOnly { 841 get { return true; } 842 } 843 Add(TKey item)844 void ICollection<TKey>.Add(TKey item){ 845 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); 846 } 847 Clear()848 void ICollection<TKey>.Clear(){ 849 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); 850 } 851 Contains(TKey item)852 bool ICollection<TKey>.Contains(TKey item){ 853 return dictionary.ContainsKey(item); 854 } 855 Remove(TKey item)856 bool ICollection<TKey>.Remove(TKey item){ 857 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); 858 return false; 859 } 860 GetEnumerator()861 IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator() { 862 return new Enumerator(dictionary); 863 } 864 IEnumerable.GetEnumerator()865 IEnumerator IEnumerable.GetEnumerator() { 866 return new Enumerator(dictionary); 867 } 868 ICollection.CopyTo(Array array, int index)869 void ICollection.CopyTo(Array array, int index) { 870 if (array==null) { 871 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); 872 } 873 874 if (array.Rank != 1) { 875 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); 876 } 877 878 if( array.GetLowerBound(0) != 0 ) { 879 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); 880 } 881 882 if (index < 0 || index > array.Length) { 883 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); 884 } 885 886 if (array.Length - index < dictionary.Count) { 887 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 888 } 889 890 TKey[] keys = array as TKey[]; 891 if (keys != null) { 892 CopyTo(keys, index); 893 } 894 else { 895 object[] objects = array as object[]; 896 if (objects == null) { 897 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); 898 } 899 900 int count = dictionary.count; 901 Entry[] entries = dictionary.entries; 902 try { 903 for (int i = 0; i < count; i++) { 904 if (entries[i].hashCode >= 0) objects[index++] = entries[i].key; 905 } 906 } 907 catch(ArrayTypeMismatchException) { 908 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); 909 } 910 } 911 } 912 913 bool ICollection.IsSynchronized { 914 get { return false; } 915 } 916 917 Object ICollection.SyncRoot { 918 get { return ((ICollection)dictionary).SyncRoot; } 919 } 920 921 [Serializable] 922 public struct Enumerator : IEnumerator<TKey>, System.Collections.IEnumerator 923 { 924 private Dictionary<TKey, TValue> dictionary; 925 private int index; 926 private int version; 927 private TKey currentKey; 928 EnumeratorSystem.Collections.Generic.Dictionary.KeyCollection.Enumerator929 internal Enumerator(Dictionary<TKey, TValue> dictionary) { 930 this.dictionary = dictionary; 931 version = dictionary.version; 932 index = 0; 933 currentKey = default(TKey); 934 } 935 DisposeSystem.Collections.Generic.Dictionary.KeyCollection.Enumerator936 public void Dispose() { 937 } 938 MoveNextSystem.Collections.Generic.Dictionary.KeyCollection.Enumerator939 public bool MoveNext() { 940 if (version != dictionary.version) { 941 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 942 } 943 944 while ((uint)index < (uint)dictionary.count) { 945 if (dictionary.entries[index].hashCode >= 0) { 946 currentKey = dictionary.entries[index].key; 947 index++; 948 return true; 949 } 950 index++; 951 } 952 953 index = dictionary.count + 1; 954 currentKey = default(TKey); 955 return false; 956 } 957 958 public TKey Current { 959 get { 960 return currentKey; 961 } 962 } 963 964 Object System.Collections.IEnumerator.Current { 965 get { 966 if( index == 0 || (index == dictionary.count + 1)) { 967 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 968 } 969 970 return currentKey; 971 } 972 } 973 System.Collections.IEnumerator.ResetSystem.Collections.Generic.Dictionary.KeyCollection.Enumerator974 void System.Collections.IEnumerator.Reset() { 975 if (version != dictionary.version) { 976 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 977 } 978 979 index = 0; 980 currentKey = default(TKey); 981 } 982 } 983 } 984 985 [DebuggerTypeProxy(typeof(Mscorlib_DictionaryValueCollectionDebugView<,>))] 986 [DebuggerDisplay("Count = {Count}")] 987 [Serializable] 988 public sealed class ValueCollection: ICollection<TValue>, ICollection, IReadOnlyCollection<TValue> 989 { 990 private Dictionary<TKey,TValue> dictionary; 991 ValueCollection(Dictionary<TKey,TValue> dictionary)992 public ValueCollection(Dictionary<TKey,TValue> dictionary) { 993 if (dictionary == null) { 994 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); 995 } 996 this.dictionary = dictionary; 997 } 998 GetEnumerator()999 public Enumerator GetEnumerator() { 1000 return new Enumerator(dictionary); 1001 } 1002 CopyTo(TValue[] array, int index)1003 public void CopyTo(TValue[] array, int index) { 1004 if (array == null) { 1005 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); 1006 } 1007 1008 if (index < 0 || index > array.Length) { 1009 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); 1010 } 1011 1012 if (array.Length - index < dictionary.Count) { 1013 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 1014 } 1015 1016 int count = dictionary.count; 1017 Entry[] entries = dictionary.entries; 1018 for (int i = 0; i < count; i++) { 1019 if (entries[i].hashCode >= 0) array[index++] = entries[i].value; 1020 } 1021 } 1022 1023 public int Count { 1024 get { return dictionary.Count; } 1025 } 1026 1027 bool ICollection<TValue>.IsReadOnly { 1028 get { return true; } 1029 } 1030 Add(TValue item)1031 void ICollection<TValue>.Add(TValue item){ 1032 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); 1033 } 1034 Remove(TValue item)1035 bool ICollection<TValue>.Remove(TValue item){ 1036 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); 1037 return false; 1038 } 1039 Clear()1040 void ICollection<TValue>.Clear(){ 1041 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); 1042 } 1043 Contains(TValue item)1044 bool ICollection<TValue>.Contains(TValue item){ 1045 return dictionary.ContainsValue(item); 1046 } 1047 GetEnumerator()1048 IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator() { 1049 return new Enumerator(dictionary); 1050 } 1051 IEnumerable.GetEnumerator()1052 IEnumerator IEnumerable.GetEnumerator() { 1053 return new Enumerator(dictionary); 1054 } 1055 ICollection.CopyTo(Array array, int index)1056 void ICollection.CopyTo(Array array, int index) { 1057 if (array == null) { 1058 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); 1059 } 1060 1061 if (array.Rank != 1) { 1062 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); 1063 } 1064 1065 if( array.GetLowerBound(0) != 0 ) { 1066 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); 1067 } 1068 1069 if (index < 0 || index > array.Length) { 1070 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); 1071 } 1072 1073 if (array.Length - index < dictionary.Count) 1074 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); 1075 1076 TValue[] values = array as TValue[]; 1077 if (values != null) { 1078 CopyTo(values, index); 1079 } 1080 else { 1081 object[] objects = array as object[]; 1082 if (objects == null) { 1083 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); 1084 } 1085 1086 int count = dictionary.count; 1087 Entry[] entries = dictionary.entries; 1088 try { 1089 for (int i = 0; i < count; i++) { 1090 if (entries[i].hashCode >= 0) objects[index++] = entries[i].value; 1091 } 1092 } 1093 catch(ArrayTypeMismatchException) { 1094 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); 1095 } 1096 } 1097 } 1098 1099 bool ICollection.IsSynchronized { 1100 get { return false; } 1101 } 1102 1103 Object ICollection.SyncRoot { 1104 get { return ((ICollection)dictionary).SyncRoot; } 1105 } 1106 1107 [Serializable] 1108 public struct Enumerator : IEnumerator<TValue>, System.Collections.IEnumerator 1109 { 1110 private Dictionary<TKey, TValue> dictionary; 1111 private int index; 1112 private int version; 1113 private TValue currentValue; 1114 EnumeratorSystem.Collections.Generic.Dictionary.ValueCollection.Enumerator1115 internal Enumerator(Dictionary<TKey, TValue> dictionary) { 1116 this.dictionary = dictionary; 1117 version = dictionary.version; 1118 index = 0; 1119 currentValue = default(TValue); 1120 } 1121 DisposeSystem.Collections.Generic.Dictionary.ValueCollection.Enumerator1122 public void Dispose() { 1123 } 1124 MoveNextSystem.Collections.Generic.Dictionary.ValueCollection.Enumerator1125 public bool MoveNext() { 1126 if (version != dictionary.version) { 1127 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 1128 } 1129 1130 while ((uint)index < (uint)dictionary.count) { 1131 if (dictionary.entries[index].hashCode >= 0) { 1132 currentValue = dictionary.entries[index].value; 1133 index++; 1134 return true; 1135 } 1136 index++; 1137 } 1138 index = dictionary.count + 1; 1139 currentValue = default(TValue); 1140 return false; 1141 } 1142 1143 public TValue Current { 1144 get { 1145 return currentValue; 1146 } 1147 } 1148 1149 Object System.Collections.IEnumerator.Current { 1150 get { 1151 if( index == 0 || (index == dictionary.count + 1)) { 1152 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 1153 } 1154 1155 return currentValue; 1156 } 1157 } 1158 System.Collections.IEnumerator.ResetSystem.Collections.Generic.Dictionary.ValueCollection.Enumerator1159 void System.Collections.IEnumerator.Reset() { 1160 if (version != dictionary.version) { 1161 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 1162 } 1163 index = 0; 1164 currentValue = default(TValue); 1165 } 1166 } 1167 } 1168 } 1169 } 1170