The Labs \ Source Viewer \ SSCLI \ System.Collections.Generic \ Dictionary

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

Developer Fusion