The Labs \ Source Viewer \ SSCLI \ System.Collections \ ValueCollection

  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:  Hashtable
  18. **
  19. **
  20. ** Purpose: Hash table implementation
  21. **
  22. **
  23. ===========================================================*/
  24. namespace System.Collections
  25. {
  26.     using System;
  27.     using System.Runtime.Serialization;
  28.     using System.Security.Permissions;
  29.     using System.Diagnostics;
  30.     using System.Threading;
  31.     using System.Runtime.CompilerServices;
  32.     using System.Runtime.ConstrainedExecution;
  33.    
  34.     //
  35.     //
  36.     //
  37.     //
  38.     [DebuggerTypeProxy(typeof(System.Collections.Hashtable.HashtableDebugView))]
  39.     [DebuggerDisplay("Count = {Count}")]
  40.     [System.Runtime.InteropServices.ComVisible(true)]
  41.     [Serializable()]
  42.     public class Hashtable : IDictionary, ISerializable, IDeserializationCallback, ICloneable
  43.     {
  44. /*
  45.           Implementation Notes:
  46.           The generic Dictionary was copied from Hashtable's source - any bug
  47.           fixes here probably need to be made to the generic Dictionary as well.
  48.    
  49.           This Hashtable uses double hashing.  There are hashsize buckets in the
  50.           table, and each bucket can contain 0 or 1 element.  We a bit to mark
  51.           whether there's been a collision when we inserted multiple elements
  52.           (ie, an inserted item was hashed at least a second time and we probed
  53.           this bucket, but it was already in use).  Using the collision bit, we
  54.           can terminate lookups & removes for elements that aren't in the hash
  55.           table more quickly.  We steal the most significant bit from the hash code
  56.           to store the collision bit.
  57.           Our hash function is of the following form:
  58.    
  59.           h(key, n) = h1(key) + n*h2(key)
  60.    
  61.           where n is the number of times we've hit a collided bucket and rehashed
  62.           (on this particular lookup).  Here are our hash functions:
  63.    
  64.           h1(key) = GetHash(key);  // default implementation calls key.GetHashCode();
  65.           h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1));
  66.    
  67.           The h1 can return any number.  h2 must return a number between 1 and
  68.           hashsize - 1 that is relatively prime to hashsize (not a problem if
  69.           hashsize is prime).  (Knuth's Art of Computer Programming, Vol. 3, p. 528-9)
  70.           If this is true, then we are guaranteed to visit every bucket in exactly
  71.           hashsize probes, since the least common multiple of hashsize and h2(key)
  72.           will be hashsize * h2(key).  (This is the first number where adding h2 to
  73.           h1 mod hashsize will be 0 and we will search the same bucket twice).
  74.          
  75.           We previously used a different h2(key, n) that was not constant.  That is a
  76.           horrifically bad idea, unless you can prove that series will never produce
  77.           any identical numbers that overlap when you mod them by hashsize, for all
  78.           subranges from i to i+hashsize, for all i.  It's not worth investigating,
  79.           since there was no clear benefit from using that hash function, and it was
  80.           broken.
  81.    
  82.           For efficiency reasons, we've implemented this by storing h1 and h2 in a
  83.           temporary, and setting a variable called seed equal to h1.  We do a probe,
  84.           and if we collided, we simply add h2 to seed each time through the loop.
  85.    
  86.           A good test for h2() is to subclass Hashtable, provide your own implementation
  87.           of GetHash() that returns a constant, then add many items to the hash table.
  88.           Make sure Count equals the number of items you inserted.
  89.           Note that when we remove an item from the hash table, we set the key
  90.           equal to buckets, if there was a collision in this bucket.  Otherwise
  91.           we'd either wipe out the collision bit, or we'd still have an item in
  92.           the hash table.
  93.           --
  94.         */       
  95.        
  96.         private const string LoadFactorName = "LoadFactor";
  97.         private const string VersionName = "Version";
  98.         private const string ComparerName = "Comparer";
  99.         private const string HashCodeProviderName = "HashCodeProvider";
  100.         private const string HashSizeName = "HashSize";
  101.         // Must save buckets.Length
  102.         private const string KeysName = "Keys";
  103.         private const string ValuesName = "Values";
  104.         private const string KeyComparerName = "KeyComparer";
  105.        
  106.         // Deleted entries have their key set to buckets
  107.        
  108.         // The hash table data.
  109.         // This cannot be serialised
  110.         private struct bucket
  111.         {
  112.             public object key;
  113.             public object val;
  114.             public int hash_coll;
  115.             // Store hash code; sign bit means there was a collision.
  116.         }
  117.        
  118.         private bucket[] buckets;
  119.        
  120.         // The total number of entries in the hash table.
  121.         private int count;
  122.        
  123.         // The total number of collision bits set in the hashtable
  124.         private int occupancy;
  125.        
  126.         private int loadsize;
  127.         private float loadFactor;
  128.        
  129.         private volatile int version;
  130.         private volatile bool isWriterInProgress;
  131.        
  132.         private ICollection keys;
  133.         private ICollection values;
  134.        
  135.         private IEqualityComparer _keycomparer;
  136.         private object _syncRoot;
  137.        
  138.         [Obsolete("Please use EqualityComparer property.")]
  139.         protected IHashCodeProvider hcp {
  140.             get {
  141.                 if (_keycomparer is CompatibleComparer) {
  142.                     return ((CompatibleComparer)_keycomparer).HashCodeProvider;
  143.                 }
  144.                 else if (_keycomparer == null) {
  145.                     return null;
  146.                 }
  147.                 else {
  148.                     throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure"));
  149.                 }
  150.             }
  151.             set {
  152.                 if (_keycomparer is CompatibleComparer) {
  153.                     CompatibleComparer keyComparer = (CompatibleComparer)_keycomparer;
  154.                     _keycomparer = new CompatibleComparer(keyComparer.Comparer, value);
  155.                 }
  156.                 else if (_keycomparer == null) {
  157.                     _keycomparer = new CompatibleComparer((IComparer)null, value);
  158.                 }
  159.                 else {
  160.                     throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure"));
  161.                 }
  162.             }
  163.         }
  164.        
  165.        
  166.         [Obsolete("Please use KeyComparer properties.")]
  167.         protected IComparer comparer {
  168.             get {
  169.                 if (_keycomparer is CompatibleComparer) {
  170.                     return ((CompatibleComparer)_keycomparer).Comparer;
  171.                 }
  172.                 else if (_keycomparer == null) {
  173.                     return null;
  174.                 }
  175.                 else {
  176.                     throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure"));
  177.                 }
  178.             }
  179.             set {
  180.                 if (_keycomparer is CompatibleComparer) {
  181.                     CompatibleComparer keyComparer = (CompatibleComparer)_keycomparer;
  182.                     _keycomparer = new CompatibleComparer(value, keyComparer.HashCodeProvider);
  183.                 }
  184.                 else if (_keycomparer == null) {
  185.                     _keycomparer = new CompatibleComparer(value, (IHashCodeProvider)null);
  186.                 }
  187.                 else {
  188.                     throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure"));
  189.                 }
  190.             }
  191.         }
  192.        
  193.         protected IEqualityComparer EqualityComparer {
  194.             get { return _keycomparer; }
  195.         }
  196.        
  197.        
  198.         private SerializationInfo m_siInfo;
  199.         //A temporary variable which we need during deserialization.
  200.         // Note: this constructor is a bogus constructor that does nothing
  201.         // and is for use only with SyncHashtable.
  202.         internal Hashtable(bool trash)
  203.         {
  204.         }
  205.        
  206.         // Constructs a new hashtable. The hashtable is created with an initial
  207.         // capacity of zero and a load factor of 1.0.
  208.         public Hashtable() : this(0, 1f)
  209.         {
  210.         }
  211.        
  212.         // Constructs a new hashtable with the given initial capacity and a load
  213.         // factor of 1.0. The capacity argument serves as an indication of
  214.         // the number of entries the hashtable will contain. When this number (or
  215.         // an approximation) is known, specifying it in the constructor can
  216.         // eliminate a number of resizing operations that would otherwise be
  217.         // performed when elements are added to the hashtable.
  218.         //
  219.         public Hashtable(int capacity) : this(capacity, 1f)
  220.         {
  221.         }
  222.        
  223.         // Constructs a new hashtable with the given initial capacity and load
  224.         // factor. The capacity argument serves as an indication of the
  225.         // number of entries the hashtable will contain. When this number (or an
  226.         // approximation) is known, specifying it in the constructor can eliminate
  227.         // a number of resizing operations that would otherwise be performed when
  228.         // elements are added to the hashtable. The loadFactor argument
  229.         // indicates the maximum ratio of hashtable entries to hashtable buckets.
  230.         // Smaller load factors cause faster average lookup times at the cost of
  231.         // increased memory consumption. A load factor of 1.0 generally provides
  232.         // the best balance between speed and size.
  233.         //
  234.         public Hashtable(int capacity, float loadFactor)
  235.         {
  236.             if (capacity < 0)
  237.                 throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  238.             if (!(loadFactor >= 0.1f && loadFactor <= 1f))
  239.                 throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", 0.1, 1.0));
  240.            
  241.             // Based on perf work, .72 is the optimal load factor for this table.
  242.             this.loadFactor = 0.72f * loadFactor;
  243.            
  244.             double rawsize = capacity / this.loadFactor;
  245.             if (rawsize > Int32.MaxValue)
  246.                 throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
  247.            
  248.             // Avoid awfully small sizes
  249.             int hashsize = (rawsize > 11) ? HashHelpers.GetPrime((int)rawsize) : 11;
  250.             buckets = new bucket[hashsize];
  251.            
  252.             loadsize = (int)(this.loadFactor * hashsize);
  253.             isWriterInProgress = false;
  254.             // Based on the current algorithm, loadsize must be less than hashsize.
  255.             BCLDebug.Assert(loadsize < hashsize, "Invalid hashtable loadsize!");
  256.         }
  257.        
  258.         // Constructs a new hashtable with the given initial capacity and load
  259.         // factor. The capacity argument serves as an indication of the
  260.         // number of entries the hashtable will contain. When this number (or an
  261.         // approximation) is known, specifying it in the constructor can eliminate
  262.         // a number of resizing operations that would otherwise be performed when
  263.         // elements are added to the hashtable. The loadFactor argument
  264.         // indicates the maximum ratio of hashtable entries to hashtable buckets.
  265.         // Smaller load factors cause faster average lookup times at the cost of
  266.         // increased memory consumption. A load factor of 1.0 generally provides
  267.         // the best balance between speed and size. The hcp argument
  268.         // is used to specify an Object that will provide hash codes for all
  269.         // the Objects in the table. Using this, you can in effect override
  270.         // GetHashCode() on each Object using your own hash function. The
  271.         // comparer argument will let you specify a custom function for
  272.         // comparing keys. By specifying user-defined objects for hcp
  273.         // and comparer, users could make a hash table using strings
  274.         // as keys do case-insensitive lookups.
  275.         //
  276.         [Obsolete("Please use Hashtable(int, float, IEqualityComparer) instead.")]
  277.         public Hashtable(int capacity, float loadFactor, IHashCodeProvider hcp, IComparer comparer) : this(capacity, loadFactor)
  278.         {
  279.             if (hcp == null && comparer == null) {
  280.                 this._keycomparer = null;
  281.             }
  282.             else {
  283.                 this._keycomparer = new CompatibleComparer(comparer, hcp);
  284.             }
  285.         }
  286.        
  287.         public Hashtable(int capacity, float loadFactor, IEqualityComparer equalityComparer) : this(capacity, loadFactor)
  288.         {
  289.             this._keycomparer = equalityComparer;
  290.         }
  291.        
  292.         // Constructs a new hashtable using a custom hash function
  293.         // and a custom comparison function for keys. This will enable scenarios
  294.         // such as doing lookups with case-insensitive strings.
  295.         //
  296.         [Obsolete("Please use Hashtable(IEqualityComparer) instead.")]
  297.         public Hashtable(IHashCodeProvider hcp, IComparer comparer) : this(0, 1f, hcp, comparer)
  298.         {
  299.         }
  300.        
  301.         public Hashtable(IEqualityComparer equalityComparer) : this(0, 1f, equalityComparer)
  302.         {
  303.         }
  304.        
  305.         // Constructs a new hashtable using a custom hash function
  306.         // and a custom comparison function for keys. This will enable scenarios
  307.         // such as doing lookups with case-insensitive strings.
  308.         //
  309.         [Obsolete("Please use Hashtable(int, IEqualityComparer) instead.")]
  310.         public Hashtable(int capacity, IHashCodeProvider hcp, IComparer comparer) : this(capacity, 1f, hcp, comparer)
  311.         {
  312.         }
  313.        
  314.         public Hashtable(int capacity, IEqualityComparer equalityComparer) : this(capacity, 1f, equalityComparer)
  315.         {
  316.         }
  317.        
  318.         // Constructs a new hashtable containing a copy of the entries in the given
  319.         // dictionary. The hashtable is created with a load factor of 1.0.
  320.         //
  321.         public Hashtable(IDictionary d) : this(d, 1f)
  322.         {
  323.         }
  324.        
  325.         // Constructs a new hashtable containing a copy of the entries in the given
  326.         // dictionary. The hashtable is created with the given load factor.
  327.         //
  328.         public Hashtable(IDictionary d, float loadFactor) : this(d, loadFactor, (IEqualityComparer)null)
  329.         {
  330.         }
  331.        
  332.         [Obsolete("Please use Hashtable(IDictionary, IEqualityComparer) instead.")]
  333.         public Hashtable(IDictionary d, IHashCodeProvider hcp, IComparer comparer) : this(d, 1f, hcp, comparer)
  334.         {
  335.         }
  336.        
  337.         public Hashtable(IDictionary d, IEqualityComparer equalityComparer) : this(d, 1f, equalityComparer)
  338.         {
  339.         }
  340.        
  341.         [Obsolete("Please use Hashtable(IDictionary, float, IEqualityComparer) instead.")]
  342.         public Hashtable(IDictionary d, float loadFactor, IHashCodeProvider hcp, IComparer comparer) : this((d != null ? d.Count : 0), loadFactor, hcp, comparer)
  343.         {
  344.             if (d == null)
  345.                 throw new ArgumentNullException("d", Environment.GetResourceString("ArgumentNull_Dictionary"));
  346.            
  347.             IDictionaryEnumerator e = d.GetEnumerator();
  348.             while (e.MoveNext())
  349.                 Add(e.Key, e.Value);
  350.         }
  351.        
  352.         public Hashtable(IDictionary d, float loadFactor, IEqualityComparer equalityComparer) : this((d != null ? d.Count : 0), loadFactor, equalityComparer)
  353.         {
  354.             if (d == null)
  355.                 throw new ArgumentNullException("d", Environment.GetResourceString("ArgumentNull_Dictionary"));
  356.            
  357.             IDictionaryEnumerator e = d.GetEnumerator();
  358.             while (e.MoveNext())
  359.                 Add(e.Key, e.Value);
  360.         }
  361.        
  362.         protected Hashtable(SerializationInfo info, StreamingContext context)
  363.         {
  364.             //We can't do anything with the keys and values until the entire graph has been deserialized
  365.             //and we have a resonable estimate that GetHashCode is not going to fail. For the time being,
  366.             //we'll just cache this. The graph is not valid until OnDeserialization has been called.
  367.             m_siInfo = info;
  368.         }
  369.        
  370.         // Computes the hash function: H(key, i) = h1(key) + i*h2(key, hashSize).
  371.         // The out parameter seed is h1(key), while the out parameter
  372.         // incr is h2(key, hashSize). Callers of this function should
  373.         // add incr each time through a loop.
  374.         private uint InitHash(object key, int hashsize, out uint seed, out uint incr)
  375.         {
  376.             // Hashcode must be positive. Also, we must not use the sign bit, since
  377.             // that is used for the collision bit.
  378.             uint hashcode = (uint)GetHash(key) & 2147483647;
  379.             seed = (uint)hashcode;
  380.             // Restriction: incr MUST be between 1 and hashsize - 1, inclusive for
  381.             // the modular arithmetic to work correctly. This guarantees you'll
  382.             // visit every bucket in the table exactly once within hashsize
  383.             // iterations. Violate this and it'll cause obscure bugs forever.
  384.             // If you change this calculation for h2(key), update putEntry too!
  385.             incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)hashsize - 1)));
  386.             return hashcode;
  387.         }
  388.        
  389.         // Adds an entry with the given key and value to this hashtable. An
  390.         // ArgumentException is thrown if the key is null or if the key is already
  391.         // present in the hashtable.
  392.         //
  393.         public virtual void Add(object key, object value)
  394.         {
  395.             Insert(key, value, true);
  396.         }
  397.        
  398.         // Removes all entries from this hashtable.
  399.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  400.         public virtual void Clear()
  401.         {
  402.             if (count == 0)
  403.                 return;
  404.            
  405.             Thread.BeginCriticalRegion();
  406.             isWriterInProgress = true;
  407.             for (int i = 0; i < buckets.Length; i++) {
  408.                 buckets[i].hash_coll = 0;
  409.                 buckets[i].key = null;
  410.                 buckets[i].val = null;
  411.             }
  412.            
  413.             count = 0;
  414.             occupancy = 0;
  415.             UpdateVersion();
  416.             isWriterInProgress = false;
  417.             Thread.EndCriticalRegion();
  418.         }
  419.        
  420.         // Clone returns a virtually identical copy of this hash table. This does
  421.         // a shallow copy - the Objects in the table aren't cloned, only the references
  422.         // to those Objects.
  423.         public virtual object Clone()
  424.         {
  425.             bucket[] lbuckets = buckets;
  426.             Hashtable ht = new Hashtable(count, _keycomparer);
  427.             ht.version = version;
  428.             ht.loadFactor = loadFactor;
  429.             ht.count = 0;
  430.            
  431.             int bucket = lbuckets.Length;
  432.             while (bucket > 0) {
  433.                 bucket--;
  434.                 object keyv = lbuckets[bucket].key;
  435.                 if ((keyv != null) && (keyv != lbuckets)) {
  436.                     ht[keyv] = lbuckets[bucket].val;
  437.                 }
  438.             }
  439.            
  440.             return ht;
  441.         }
  442.        
  443.         // Checks if this hashtable contains the given key.
  444.         public virtual bool Contains(object key)
  445.         {
  446.             return ContainsKey(key);
  447.         }
  448.        
  449.         // Checks if this hashtable contains an entry with the given key. This is
  450.         // an O(1) operation.
  451.         //
  452.         public virtual bool ContainsKey(object key)
  453.         {
  454.             if (key == null) {
  455.                 throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
  456.             }
  457.            
  458.             uint seed;
  459.             uint incr;
  460.             // Take a snapshot of buckets, in case another thread resizes table
  461.             bucket[] lbuckets = buckets;
  462.             uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr);
  463.             int ntry = 0;
  464.            
  465.             bucket b;
  466.             int bucketNumber = (int)(seed % (uint)lbuckets.Length);
  467.             do {
  468.                 b = lbuckets[bucketNumber];
  469.                 if (b.key == null) {
  470.                     return false;
  471.                 }
  472.                 if (((b.hash_coll & 2147483647) == hashcode) && KeyEquals(b.key, key))
  473.                     return true;
  474.                 bucketNumber = (int)(((long)bucketNumber + incr) % (uint)lbuckets.Length);
  475.             }
  476.             while (b.hash_coll < 0 && ++ntry < lbuckets.Length);
  477.             return false;
  478.         }
  479.        
  480.        
  481.        
  482.         // Checks if this hashtable contains an entry with the given value. The
  483.         // values of the entries of the hashtable are compared to the given value
  484.         // using the Object.Equals method. This method performs a linear
  485.         // search and is thus be substantially slower than the ContainsKey
  486.         // method.
  487.         //
  488.         public virtual bool ContainsValue(object value)
  489.         {
  490.             if (value == null) {
  491.                 for (int i = buckets.Length; --i >= 0;) {
  492.                     if (buckets[i].key != null && buckets[i].key != buckets && buckets[i].val == null)
  493.                         return true;
  494.                 }
  495.             }
  496.             else {
  497.                 for (int i = buckets.Length; --i >= 0;) {
  498.                     object val = buckets[i].val;
  499.                     if (val != null && val.Equals(value))
  500.                         return true;
  501.                 }
  502.             }
  503.             return false;
  504.         }
  505.        
  506.         // Copies the keys of this hashtable to a given array starting at a given
  507.         // index. This method is used by the implementation of the CopyTo method in
  508.         // the KeyCollection class.
  509.         private void CopyKeys(Array array, int arrayIndex)
  510.         {
  511.             bucket[] lbuckets = buckets;
  512.             for (int i = lbuckets.Length; --i >= 0;) {
  513.                 object keyv = lbuckets[i].key;
  514.                 if ((keyv != null) && (keyv != buckets)) {
  515.                     array.SetValue(keyv, arrayIndex++);
  516.                 }
  517.             }
  518.         }
  519.        
  520.         // Copies the keys of this hashtable to a given array starting at a given
  521.         // index. This method is used by the implementation of the CopyTo method in
  522.         // the KeyCollection class.
  523.         private void CopyEntries(Array array, int arrayIndex)
  524.         {
  525.             bucket[] lbuckets = buckets;
  526.             for (int i = lbuckets.Length; --i >= 0;) {
  527.                 object keyv = lbuckets[i].key;
  528.                 if ((keyv != null) && (keyv != buckets)) {
  529.                     DictionaryEntry entry = new DictionaryEntry(keyv, lbuckets[i].val);
  530.                     array.SetValue(entry, arrayIndex++);
  531.                 }
  532.             }
  533.         }
  534.        
  535.         // Copies the values in this hash table to an array at
  536.         // a given index. Note that this only copies values, and not keys.
  537.         public virtual void CopyTo(Array array, int arrayIndex)
  538.         {
  539.             if (array == null)
  540.                 throw new ArgumentNullException("array", Environment.GetResourceString("ArgumentNull_Array"));
  541.             if (array.Rank != 1)
  542.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
  543.             if (arrayIndex < 0)
  544.                 throw new ArgumentOutOfRangeException("arrayIndex", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  545.             if (array.Length - arrayIndex < count)
  546.                 throw new ArgumentException(Environment.GetResourceString("Arg_ArrayPlusOffTooSmall"));
  547.             CopyEntries(array, arrayIndex);
  548.         }
  549.        
  550.         // Copies the values in this Hashtable to an KeyValuePairs array.
  551.         // KeyValuePairs is different from Dictionary Entry in that it has special
  552.         // debugger attributes on its fields.
  553.        
  554.         internal virtual KeyValuePairs[] ToKeyValuePairsArray()
  555.         {
  556.             KeyValuePairs[] array = new KeyValuePairs[count];
  557.             int index = 0;
  558.             bucket[] lbuckets = buckets;
  559.             for (int i = lbuckets.Length; --i >= 0;) {
  560.                 object keyv = lbuckets[i].key;
  561.                 if ((keyv != null) && (keyv != buckets)) {
  562.                     array[index++] = new KeyValuePairs(keyv, lbuckets[i].val);
  563.                 }
  564.             }
  565.            
  566.             return array;
  567.         }
  568.        
  569.        
  570.         // Copies the values of this hashtable to a given array starting at a given
  571.         // index. This method is used by the implementation of the CopyTo method in
  572.         // the ValueCollection class.
  573.         private void CopyValues(Array array, int arrayIndex)
  574.         {
  575.             bucket[] lbuckets = buckets;
  576.             for (int i = lbuckets.Length; --i >= 0;) {
  577.                 object keyv = lbuckets[i].key;
  578.                 if ((keyv != null) && (keyv != buckets)) {
  579.                     array.SetValue(lbuckets[i].val, arrayIndex++);
  580.                 }
  581.             }
  582.         }
  583.        
  584.         // Returns the value associated with the given key. If an entry with the
  585.         // given key is not found, the returned value is null.
  586.         //
  587.         public virtual object this[object key]
  588.         {
  589.             get {
  590.                 if (key == null) {
  591.                     throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
  592.                 }
  593.                 uint seed;
  594.                 uint incr;
  595.                
  596.                
  597.                 // Take a snapshot of buckets, in case another thread does a resize
  598.                 bucket[] lbuckets = buckets;
  599.                 uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr);
  600.                 int ntry = 0;
  601.                
  602.                 bucket b;
  603.                 int bucketNumber = (int)(seed % (uint)lbuckets.Length);
  604.                 do {
  605.                     int currentversion;
  606.                    
  607.                     // A read operation on hashtable has three steps:
  608.                     // (1) calculate the hash and find the slot number.
  609.                     // (2) compare the hashcode, if equal, go to step 3. Otherwise end.
  610.                     // (3) compare the key, if equal, go to step 4. Otherwise end.
  611.                     // (4) return the value contained in the bucket.
  612.                     // After step 3 and before step 4. A writer can kick in a remove the old item and add a new one
  613.                     // in the same bukcet. So in the reader we need to check if the hash table is modified during above steps.
  614.                     //
  615.                     // Writers (Insert, Remove, Clear) will set 'isWriterInProgress' flag before it starts modifying
  616.                     // the hashtable and will ckear the flag when it is done. When the flag is cleared, the 'version'
  617.                     // will be increased. We will repeat the reading if a writer is in progress or done with the modification
  618.                     // during the read.
  619.                     //
  620.                     // Our memory model guarantee if we pick up the change in bucket from another processor,
  621.                     // we will see the 'isWriterProgress' flag to be true or 'version' is changed in the reader.
  622.                     //
  623.                     int spinCount = 0;
  624.                     do {
  625.                         // this is violate read, following memory accesses can not be moved ahead of it.
  626.                         currentversion = version;
  627.                         b = lbuckets[bucketNumber];
  628.                        
  629.                         // The contention between reader and writer shouldn't happen frequently.
  630.                         // But just in case this will burn CPU, yield the control of CPU if we spinned a few times.
  631.                         // 8 is just a random number I pick.
  632.                         if ((++spinCount) % 8 == 0) {
  633.                             Thread.Sleep(1);
  634.                             // 1 means we are yeilding control to all threads, including low-priority ones.
  635.                         }
  636.                     }
  637.                     while (isWriterInProgress || (currentversion != version));
  638.                    
  639.                     if (b.key == null) {
  640.                         return null;
  641.                     }
  642.                     if (((b.hash_coll & 2147483647) == hashcode) && KeyEquals(b.key, key))
  643.                         return b.val;
  644.                     bucketNumber = (int)(((long)bucketNumber + incr) % (uint)lbuckets.Length);
  645.                 }
  646.                 while (b.hash_coll < 0 && ++ntry < lbuckets.Length);
  647.                 return null;
  648.             }
  649.            
  650.             set { Insert(key, value, false); }
  651.         }
  652.        
  653.         // Increases the bucket count of this hashtable. This method is called from
  654.         // the Insert method when the actual load factor of the hashtable reaches
  655.         // the upper limit specified when the hashtable was constructed. The number
  656.         // of buckets in the hashtable is increased to the smallest prime number
  657.         // that is larger than twice the current number of buckets, and the entries
  658.         // in the hashtable are redistributed into the new buckets using the cached
  659.         // hashcodes.
  660.         private void expand()
  661.         {
  662.            
  663.             int rawsize = HashHelpers.GetPrime(buckets.Length * 2);
  664.             // buckets.Length*2 will not overflow
  665.             rehash(rawsize);
  666.         }
  667.        
  668.         // We occationally need to rehash the table to clean up the collision bits.
  669.         private void rehash()
  670.         {
  671.             rehash(buckets.Length);
  672.         }
  673.        
  674.         private void UpdateVersion()
  675.         {
  676.             // Version might become negative when version is Int32.MaxValue, but the oddity will be still be correct.
  677.             // So we don't need to special case this.
  678.             version++;
  679.         }
  680.        
  681.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  682.         private void rehash(int newsize)
  683.         {
  684.            
  685.             // reset occupancy
  686.             occupancy = 0;
  687.            
  688.             // Don't replace any internal state until we've finished adding to the
  689.             // new bucket[]. This serves two purposes:
  690.             // 1) Allow concurrent readers to see valid hashtable contents
  691.             // at all times
  692.             // 2) Protect against an OutOfMemoryException while allocating this
  693.             // new bucket[].
  694.             bucket[] newBuckets = new bucket[newsize];
  695.            
  696.             // rehash table into new buckets
  697.             int nb;
  698.             for (nb = 0; nb < buckets.Length; nb++) {
  699.                 bucket oldb = buckets[nb];
  700.                 if ((oldb.key != null) && (oldb.key != buckets)) {
  701.                     putEntry(newBuckets, oldb.key, oldb.val, oldb.hash_coll & 2147483647);
  702.                 }
  703.             }
  704.            
  705.             // New bucket[] is good to go - replace buckets and other internal state.
  706.             Thread.BeginCriticalRegion();
  707.             isWriterInProgress = true;
  708.             buckets = newBuckets;
  709.             loadsize = (int)(loadFactor * newsize);
  710.             UpdateVersion();
  711.             isWriterInProgress = false;
  712.             Thread.EndCriticalRegion();
  713.             // minimun size of hashtable is 11 now and maximum loadFactor is 0.72 now.
  714.             BCLDebug.Assert(loadsize < newsize, "Our current implementaion means this is not possible.");
  715.             return;
  716.         }
  717.        
  718.         // Returns an enumerator for this hashtable.
  719.         // If modifications made to the hashtable while an enumeration is
  720.         // in progress, the MoveNext and Current methods of the
  721.         // enumerator will throw an exception.
  722.         //
  723.         IEnumerator IEnumerable.GetEnumerator()
  724.         {
  725.             return new HashtableEnumerator(this, HashtableEnumerator.DictEntry);
  726.         }
  727.        
  728.         // Returns a dictionary enumerator for this hashtable.
  729.         // If modifications made to the hashtable while an enumeration is
  730.         // in progress, the MoveNext and Current methods of the
  731.         // enumerator will throw an exception.
  732.         //
  733.         public virtual IDictionaryEnumerator GetEnumerator()
  734.         {
  735.             return new HashtableEnumerator(this, HashtableEnumerator.DictEntry);
  736.         }
  737.        
  738.         // Internal method to get the hash code for an Object. This will call
  739.         // GetHashCode() on each object if you haven't provided an IHashCodeProvider
  740.         // instance. Otherwise, it calls hcp.GetHashCode(obj).
  741.         protected virtual int GetHash(object key)
  742.         {
  743.             if (_keycomparer != null)
  744.                 return _keycomparer.GetHashCode(key);
  745.             return key.GetHashCode();
  746.         }
  747.        
  748.         // Is this Hashtable read-only?
  749.         public virtual bool IsReadOnly {
  750.             get { return false; }
  751.         }
  752.        
  753.         public virtual bool IsFixedSize {
  754.             get { return false; }
  755.         }
  756.        
  757.         // Is this Hashtable synchronized? See SyncRoot property
  758.         public virtual bool IsSynchronized {
  759.             get { return false; }
  760.         }
  761.        
  762.         // Internal method to compare two keys. If you have provided an IComparer
  763.         // instance in the constructor, this method will call comparer.Compare(item, key).
  764.         // Otherwise, it will call item.Equals(key).
  765.         //
  766.         protected virtual bool KeyEquals(object item, object key)
  767.         {
  768.             BCLDebug.Assert(key != null, "key can't be null here!");
  769.             if (Object.ReferenceEquals(buckets, item)) {
  770.                 return false;
  771.             }
  772.            
  773.             if (_keycomparer != null)
  774.                 return _keycomparer.Equals(item, key);
  775.             return item == null ? false : item.Equals(key);
  776.         }
  777.        
  778.         // Returns a collection representing the keys of this hashtable. The order
  779.         // in which the returned collection represents the keys is unspecified, but
  780.         // it is guaranteed to be buckets = newBuckets; the same order in which a collection returned by
  781.         // GetValues represents the values of the hashtable.
  782.         //
  783.         // The returned collection is live in the sense that any changes
  784.         // to the hash table are reflected in this collection. It is not
  785.         // a static copy of all the keys in the hash table.
  786.         //
  787.         public virtual ICollection Keys {
  788.             get {
  789.                 if (keys == null)
  790.                     keys = new KeyCollection(this);
  791.                 return keys;
  792.             }
  793.         }
  794.        
  795.         // Returns a collection representing the values of this hashtable. The
  796.         // order in which the returned collection represents the values is
  797.         // unspecified, but it is guaranteed to be the same order in which a
  798.         // collection returned by GetKeys represents the keys of the
  799.         // hashtable.
  800.         //
  801.         // The returned collection is live in the sense that any changes
  802.         // to the hash table are reflected in this collection. It is not
  803.         // a static copy of all the keys in the hash table.
  804.         //
  805.         public virtual ICollection Values {
  806.             get {
  807.                 if (values == null)
  808.                     values = new ValueCollection(this);
  809.                 return values;
  810.             }
  811.         }
  812.        
  813.         // Inserts an entry into this hashtable. This method is called from the Set
  814.         // and Add methods. If the add parameter is true and the given key already
  815.         // exists in the hashtable, an exception is thrown.
  816.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  817.         private void Insert(object key, object nvalue, bool add)
  818.         {
  819.             if (key == null) {
  820.                 throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
  821.             }
  822.             if (count >= loadsize) {
  823.                 expand();
  824.             }
  825.             else if (occupancy > loadsize && count > 100) {
  826.                 rehash();
  827.             }
  828.            
  829.             uint seed;
  830.             uint incr;
  831.             // Assume we only have one thread writing concurrently. Modify
  832.             // buckets to contain new data, as long as we insert in the right order.
  833.             uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
  834.             int ntry = 0;
  835.             int emptySlotNumber = -1;
  836.             // We use the empty slot number to cache the first empty slot. We chose to reuse slots
  837.             // create by remove that have the collision bit set over using up new slots.
  838.             int bucketNumber = (int)(seed % (uint)buckets.Length);
  839.             do {
  840.                
  841.                 // Set emptySlot number to current bucket if it is the first available bucket that we have seen
  842.                 // that once contained an entry and also has had a collision.
  843.                 // We need to search this entire collision chain because we have to ensure that there are no
  844.                 // duplicate entries in the table.
  845.                 if (emptySlotNumber == -1 && (buckets[bucketNumber].key == buckets) && (buckets[bucketNumber].hash_coll < 0))
  846.                     //(((buckets[bucketNumber].hash_coll & unchecked(0x80000000))!=0)))
  847.                     emptySlotNumber = bucketNumber;
  848.                
  849.                 // Insert the key/value pair into this bucket if this bucket is empty and has never contained an entry
  850.                 // OR
  851.                 // This bucket once contained an entry but there has never been a collision
  852.                 if ((buckets[bucketNumber].key == null) || (buckets[bucketNumber].key == buckets && ((buckets[bucketNumber].hash_coll & unchecked(2147483648u)) == 0))) {
  853.                    
  854.                     // If we have found an available bucket that has never had a collision, but we've seen an available
  855.                     // bucket in the past that has the collision bit set, use the previous bucket instead
  856.                     if (emptySlotNumber != -1)
  857.                         // Reuse slot
  858.                         bucketNumber = emptySlotNumber;
  859.                    
  860.                     // We pretty much have to insert in this order. Don't set hash
  861.                     // code until the value & key are set appropriately.
  862.                     Thread.BeginCriticalRegion();
  863.                     isWriterInProgress = true;
  864.                     buckets[bucketNumber].val = nvalue;
  865.                     buckets[bucketNumber].key = key;
  866.                     buckets[bucketNumber].hash_coll |= (int)hashcode;
  867.                     count++;
  868.                     UpdateVersion();
  869.                     isWriterInProgress = false;
  870.                     Thread.EndCriticalRegion();
  871.                     return;
  872.                 }
  873.                
  874.                 // The current bucket is in use
  875.                 // OR
  876.                 // it is available, but has had the collision bit set and we have already found an available bucket
  877.                 if (((buckets[bucketNumber].hash_coll & 2147483647) == hashcode) && KeyEquals(buckets[bucketNumber].key, key)) {
  878.                     if (add) {
  879.                         throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", buckets[bucketNumber].key, key));
  880.                     }
  881.                     Thread.BeginCriticalRegion();
  882.                     isWriterInProgress = true;
  883.                     buckets[bucketNumber].val = nvalue;
  884.                     UpdateVersion();
  885.                     isWriterInProgress = false;
  886.                     Thread.EndCriticalRegion();
  887.                     return;
  888.                 }
  889.                
  890.                 // The current bucket is full, and we have therefore collided. We need to set the collision bit
  891.                 // UNLESS
  892.                 // we have remembered an available slot previously.
  893.                 if (emptySlotNumber == -1) {
  894.                     // We don't need to set the collision bit here since we already have an empty slot
  895.                     if (buckets[bucketNumber].hash_coll >= 0) {
  896.                         buckets[bucketNumber].hash_coll |= unchecked((int)2147483648u);
  897.                         occupancy++;
  898.                     }
  899.                 }
  900.                 bucketNumber = (int)(((long)bucketNumber + incr) % (uint)buckets.Length);
  901.             }
  902.             while (++ntry < buckets.Length);
  903.            
  904.             // This code is here if and only if there were no buckets without a collision bit set in the entire table
  905.             if (emptySlotNumber != -1) {
  906.                 // We pretty much have to insert in this order. Don't set hash
  907.                 // code until the value & key are set appropriately.
  908.                 Thread.BeginCriticalRegion();
  909.                 isWriterInProgress = true;
  910.                 buckets[emptySlotNumber].val = nvalue;
  911.                 buckets[emptySlotNumber].key = key;
  912.                 buckets[emptySlotNumber].hash_coll |= (int)hashcode;
  913.                 count++;
  914.                 UpdateVersion();
  915.                 isWriterInProgress = false;
  916.                 Thread.EndCriticalRegion();
  917.                 return;
  918.             }
  919.            
  920.             // If you see this assert, make sure load factor & count are reasonable.
  921.             // Then verify that our double hash function (h2, described at top of file)
  922.             // meets the requirements described above. You should never see this assert.
  923.             BCLDebug.Assert(false, "hash table insert failed! Load factor too high, or our double hashing function is incorrect.");
  924.             throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_HashInsertFailed"));
  925.         }
  926.        
  927.         private void putEntry(bucket[] newBuckets, object key, object nvalue, int hashcode)
  928.         {
  929.             BCLDebug.Assert(hashcode >= 0, "hashcode >= 0");
  930.             // make sure collision bit (sign bit) wasn't set.
  931.             uint seed = (uint)hashcode;
  932.             uint incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)newBuckets.Length - 1)));
  933.             int bucketNumber = (int)(seed % (uint)newBuckets.Length);
  934.             do {
  935.                
  936.                 if ((newBuckets[bucketNumber].key == null) || (newBuckets[bucketNumber].key == buckets)) {
  937.                     newBuckets[bucketNumber].val = nvalue;
  938.                     newBuckets[bucketNumber].key = key;
  939.                     newBuckets[bucketNumber].hash_coll |= hashcode;
  940.                     return;
  941.                 }
  942.                
  943.                 if (newBuckets[bucketNumber].hash_coll >= 0) {
  944.                     newBuckets[bucketNumber].hash_coll |= unchecked((int)2147483648u);
  945.                     occupancy++;
  946.                 }
  947.                 bucketNumber = (int)(((long)bucketNumber + incr) % (uint)newBuckets.Length);
  948.             }
  949.             while (true);
  950.         }
  951.        
  952.         // Removes an entry from this hashtable. If an entry with the specified
  953.         // key exists in the hashtable, it is removed. An ArgumentException is
  954.         // thrown if the key is null.
  955.         //
  956.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  957.         public virtual void Remove(object key)
  958.         {
  959.             if (key == null) {
  960.                 throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
  961.             }
  962.             uint seed;
  963.             uint incr;
  964.             // Assuming only one concurrent writer, write directly into buckets.
  965.             uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
  966.             int ntry = 0;
  967.            
  968.             bucket b;
  969.             int bn = (int)(seed % (uint)buckets.Length);
  970.             // bucketNumber
  971.             do {
  972.                 b = buckets[bn];
  973.                 if (((b.hash_coll & 2147483647) == hashcode) && KeyEquals(b.key, key)) {
  974.                     Thread.BeginCriticalRegion();
  975.                     isWriterInProgress = true;
  976.                     // Clear hash_coll field, then key, then value
  977.                     buckets[bn].hash_coll &= unchecked((int)2147483648u);
  978.                     if (buckets[bn].hash_coll != 0) {
  979.                         buckets[bn].key = buckets;
  980.                     }
  981.                     else {
  982.                         buckets[bn].key = null;
  983.                     }
  984.                     buckets[bn].val = null;
  985.                     // Free object references sooner & simplify ContainsValue.
  986.                     count--;
  987.                     UpdateVersion();
  988.                     isWriterInProgress = false;
  989.                     Thread.EndCriticalRegion();
  990.                     return;
  991.                 }
  992.                 bn = (int)(((long)bn + incr) % (uint)buckets.Length);
  993.             }
  994.             while (b.hash_coll < 0 && ++ntry < buckets.Length);
  995.            
  996.             //throw new ArgumentException(Environment.GetResourceString("Arg_RemoveArgNotFound"));
  997.         }
  998.        
  999.         // Returns the object to synchronize on for this hash table.
  1000.         public virtual object SyncRoot {
  1001.             get {
  1002.                 if (_syncRoot == null) {
  1003.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  1004.                 }
  1005.                 return _syncRoot;
  1006.             }
  1007.         }
  1008.        
  1009.         // Returns the number of associations in this hashtable.
  1010.         //
  1011.         public virtual int Count {
  1012.             get { return count; }
  1013.         }
  1014.        
  1015.         // Returns a thread-safe wrapper for a Hashtable.
  1016.         //
  1017.         [HostProtection(Synchronization = true)]
  1018.         public static Hashtable Synchronized(Hashtable table)
  1019.         {
  1020.             if (table == null)
  1021.                 throw new ArgumentNullException("table");
  1022.             return new SyncHashtable(table);
  1023.         }
  1024.        
  1025.         //
  1026.         // The ISerializable Implementation
  1027.         //
  1028.        
  1029.         public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
  1030.         {
  1031.             if (info == null) {
  1032.                 throw new ArgumentNullException("info");
  1033.             }
  1034.             info.AddValue(LoadFactorName, loadFactor);
  1035.             info.AddValue(VersionName, version);
  1036.            
  1037.             #pragma warning disable 618
  1038.             if (_keycomparer == null) {
  1039.                 info.AddValue(ComparerName, null, typeof(IComparer));
  1040.                 info.AddValue(HashCodeProviderName, null, typeof(IHashCodeProvider));
  1041.             }
  1042.             else if (_keycomparer is CompatibleComparer) {
  1043.                 CompatibleComparer c = _keycomparer as CompatibleComparer;
  1044.                 info.AddValue(ComparerName, c.Comparer, typeof(IComparer));
  1045.                 info.AddValue(HashCodeProviderName, c.HashCodeProvider, typeof(IHashCodeProvider));
  1046.             }
  1047.             else {
  1048.                 info.AddValue(KeyComparerName, _keycomparer, typeof(IEqualityComparer));
  1049.             }
  1050.             #pragma warning restore 618
  1051.            
  1052.             info.AddValue(HashSizeName, buckets.Length);
  1053.             //This is the length of the bucket array.
  1054.             object[] serKeys = new object[count];
  1055.             object[] serValues = new object[count];
  1056.             CopyKeys(serKeys, 0);
  1057.             CopyValues(serValues, 0);
  1058.             info.AddValue(KeysName, serKeys, typeof(object[]));
  1059.             info.AddValue(ValuesName, serValues, typeof(object[]));
  1060.         }
  1061.        
  1062.         //
  1063.         // DeserializationEvent Listener
  1064.         //
  1065.         public virtual void OnDeserialization(object sender)
  1066.         {
  1067.             if (buckets != null) {
  1068.                 return;
  1069.                 //Somebody had a dependency on this hashtable and fixed us up before the ObjectManager got to it.
  1070.             }
  1071.             if (m_siInfo == null) {
  1072.                 throw new SerializationException(Environment.GetResourceString("Serialization_InvalidOnDeser"));
  1073.             }
  1074.            
  1075.             int hashsize = 0;
  1076.             IComparer c = null;
  1077.            
  1078.             #pragma warning disable 618
  1079.             IHashCodeProvider hcp = null;
  1080.             #pragma warning restore 618
  1081.            
  1082.             object[] serKeys = null;
  1083.             object[] serValues = null;
  1084.            
  1085.             SerializationInfoEnumerator enumerator = m_siInfo.GetEnumerator();
  1086.            
  1087.             while (enumerator.MoveNext()) {
  1088.                 switch (enumerator.Name) {
  1089.                     case LoadFactorName:
  1090.                         loadFactor = m_siInfo.GetSingle(LoadFactorName);
  1091.                         break;
  1092.                     case HashSizeName:
  1093.                         hashsize = m_siInfo.GetInt32(HashSizeName);
  1094.                         break;
  1095.                     case KeyComparerName:
  1096.                         _keycomparer = (IEqualityComparer)m_siInfo.GetValue(KeyComparerName, typeof(IEqualityComparer));
  1097.                         break;
  1098.                     case ComparerName:
  1099.                         c = (IComparer)m_siInfo.GetValue(ComparerName, typeof(IComparer));
  1100.                         break;
  1101.                     case HashCodeProviderName:
  1102.                         #pragma warning disable 618
  1103.                         hcp = (IHashCodeProvider)m_siInfo.GetValue(HashCodeProviderName, typeof(IHashCodeProvider));
  1104.                         #pragma warning restore 618
  1105.                         break;
  1106.                     case KeysName:
  1107.                         serKeys = (object[])m_siInfo.GetValue(KeysName, typeof(object[]));
  1108.                         break;
  1109.                     case ValuesName:
  1110.                         serValues = (object[])m_siInfo.GetValue(ValuesName, typeof(object[]));
  1111.                         break;
  1112.                 }
  1113.             }
  1114.            
  1115.             loadsize = (int)(loadFactor * hashsize);
  1116.            
  1117.             // V1 object doesn't has _keycomparer field.
  1118.             if ((_keycomparer == null) && ((c != null) || (hcp != null))) {
  1119.                 _keycomparer = new CompatibleComparer(c, hcp);
  1120.             }
  1121.            
  1122.             buckets = new bucket[hashsize];
  1123.            
  1124.             if (serKeys == null) {
  1125.                 throw new SerializationException(Environment.GetResourceString("Serialization_MissingKeys"));
  1126.             }
  1127.             if (serValues == null) {
  1128.                 throw new SerializationException(Environment.GetResourceString("Serialization_MissingValues"));
  1129.             }
  1130.             if (serKeys.Length != serValues.Length) {
  1131.                 throw new SerializationException(Environment.GetResourceString("Serialization_KeyValueDifferentSizes"));
  1132.             }
  1133.             for (int i = 0; i < serKeys.Length; i++) {
  1134.                 if (serKeys[i] == null) {
  1135.                     throw new SerializationException(Environment.GetResourceString("Serialization_NullKey"));
  1136.                 }
  1137.                 Insert(serKeys[i], serValues[i], true);
  1138.             }
  1139.            
  1140.             version = m_siInfo.GetInt32(VersionName);
  1141.            
  1142.             m_siInfo = null;
  1143.         }
  1144.        
  1145.        
  1146.         // Implements a Collection for the keys of a hashtable. An instance of this
  1147.         // class is created by the GetKeys method of a hashtable.
  1148.         [Serializable()]
  1149.         private class KeyCollection : ICollection
  1150.         {
  1151.             private Hashtable _hashtable;
  1152.            
  1153.             internal KeyCollection(Hashtable hashtable)
  1154.             {
  1155.                 _hashtable = hashtable;
  1156.             }
  1157.            
  1158.             public virtual void CopyTo(Array array, int arrayIndex)
  1159.             {
  1160.                 if (array == null)
  1161.                     throw new ArgumentNullException("array");
  1162.                 if (array.Rank != 1)
  1163.                     throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
  1164.                 if (arrayIndex < 0)
  1165.                     throw new ArgumentOutOfRangeException("arrayIndex", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  1166.                 if (array.Length - arrayIndex < _hashtable.count)
  1167.                     throw new ArgumentException(Environment.GetResourceString("Arg_ArrayPlusOffTooSmall"));
  1168.                 _hashtable.CopyKeys(array, arrayIndex);
  1169.             }
  1170.            
  1171.             public virtual IEnumerator GetEnumerator()
  1172.             {
  1173.                 return new HashtableEnumerator(_hashtable, HashtableEnumerator.Keys);
  1174.             }
  1175.            
  1176.             public virtual bool IsSynchronized {
  1177.                 get { return _hashtable.IsSynchronized; }
  1178.             }
  1179.            
  1180.             public virtual object SyncRoot {
  1181.                 get { return _hashtable.SyncRoot; }
  1182.             }
  1183.            
  1184.             public virtual int Count {
  1185.                 get { return _hashtable.count; }
  1186.             }
  1187.         }
  1188.        
  1189.         // Implements a Collection for the values of a hashtable. An instance of
  1190.         // this class is created by the GetValues method of a hashtable.
  1191.         [Serializable()]
  1192.         private class ValueCollection : ICollection
  1193.         {
  1194.             private Hashtable _hashtable;
  1195.            
  1196.             internal ValueCollection(Hashtable hashtable)
  1197.             {
  1198.                 _hashtable = hashtable;
  1199.             }
  1200.            
  1201.             public virtual void CopyTo(Array array, int arrayIndex)
  1202.             {
  1203.                 if (array == null)
  1204.                     throw new ArgumentNullException("array");
  1205.                 if (array.Rank != 1)
  1206.                     throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
  1207.                 if (arrayIndex < 0)
  1208.                     throw new ArgumentOutOfRangeException("arrayIndex", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  1209.                 if (array.Length - arrayIndex < _hashtable.count)
  1210.                     throw new ArgumentException(Environment.GetResourceString("Arg_ArrayPlusOffTooSmall"));
  1211.                 _hashtable.CopyValues(array, arrayIndex);
  1212.             }
  1213.            
  1214.             public virtual IEnumerator GetEnumerator()
  1215.             {
  1216.                 return new HashtableEnumerator(_hashtable, HashtableEnumerator.Values);
  1217.             }
  1218.            
  1219.             public virtual bool IsSynchronized {
  1220.                 get { return _hashtable.IsSynchronized; }
  1221.             }
  1222.            
  1223.             public virtual object SyncRoot {
  1224.                 get { return _hashtable.SyncRoot; }
  1225.             }
  1226.            
  1227.             public virtual int Count {
  1228.                 get { return _hashtable.count; }
  1229.             }
  1230.         }
  1231.        
  1232.         // Synchronized wrapper for hashtable
  1233.         [Serializable()]
  1234.         private class SyncHashtable : Hashtable
  1235.         {
  1236.             protected Hashtable _table;
  1237.            
  1238.             internal SyncHashtable(Hashtable table) : base(false)
  1239.             {
  1240.                 _table = table;
  1241.             }
  1242.            
  1243.             internal SyncHashtable(SerializationInfo info, StreamingContext context) : base(info, context)
  1244.             {
  1245.                 _table = (Hashtable)info.GetValue("ParentTable", typeof(Hashtable));
  1246.                 if (_table == null) {
  1247.                     throw new SerializationException(Environment.GetResourceString("Serialization_InsufficientState"));
  1248.                 }
  1249.             }
  1250.            
  1251.            
  1252. /*================================GetObjectData=================================
  1253.             **Action: Return a serialization info containing a reference to _table.  We need
  1254.             **        to implement this because our parent HT does and we don't want to actually
  1255.             **        serialize all of it's values (just a reference to the table, which will then
  1256.             **        be serialized separately.)
  1257.             **Returns: void
  1258.             **Arguments: info -- the SerializationInfo into which to store the data.
  1259.             **          context -- the StreamingContext for the current serialization (ignored)
  1260.             **Exceptions: ArgumentNullException if info is null.
  1261.             ==============================================================================*/           
  1262.             public override void GetObjectData(SerializationInfo info, StreamingContext context)
  1263.             {
  1264.                 if (info == null) {
  1265.                     throw new ArgumentNullException("info");
  1266.                 }
  1267.                 info.AddValue("ParentTable", _table, typeof(Hashtable));
  1268.             }
  1269.            
  1270.             public override int Count {
  1271.                 get { return _table.Count; }
  1272.             }
  1273.            
  1274.             public override bool IsReadOnly {
  1275.                 get { return _table.IsReadOnly; }
  1276.             }
  1277.            
  1278.             public override bool IsFixedSize {
  1279.                 get { return _table.IsFixedSize; }
  1280.             }
  1281.            
  1282.             public override bool IsSynchronized {
  1283.                 get { return true; }
  1284.             }
  1285.            
  1286.             public override object this[object key]
  1287.             {
  1288.                 get { return _table[key]; }
  1289.                 set {
  1290.                     lock (_table.SyncRoot) {
  1291.                         _table[key] = value;
  1292.                     }
  1293.                 }
  1294.             }
  1295.            
  1296.             public override object SyncRoot {
  1297.                 get { return _table.SyncRoot; }
  1298.             }
  1299.            
  1300.             public override void Add(object key, object value)
  1301.             {
  1302.                 lock (_table.SyncRoot) {
  1303.                     _table.Add(key, value);
  1304.                 }
  1305.             }
  1306.            
  1307.             public override void Clear()
  1308.             {
  1309.                 lock (_table.SyncRoot) {
  1310.                     _table.Clear();
  1311.                 }
  1312.             }
  1313.            
  1314.             public override bool Contains(object key)
  1315.             {
  1316.                 return _table.Contains(key);
  1317.             }
  1318.            
  1319.             public override bool ContainsKey(object key)
  1320.             {
  1321.                 return _table.ContainsKey(key);
  1322.             }
  1323.            
  1324.             public override bool ContainsValue(object key)
  1325.             {
  1326.                 lock (_table.SyncRoot) {
  1327.                     return _table.ContainsValue(key);
  1328.                 }
  1329.             }
  1330.            
  1331.             public override void CopyTo(Array array, int arrayIndex)
  1332.             {
  1333.                 lock (_table.SyncRoot) {
  1334.                     _table.CopyTo(array, arrayIndex);
  1335.                 }
  1336.             }
  1337.            
  1338.             public override object Clone()
  1339.             {
  1340.                 lock (_table.SyncRoot) {
  1341.                     return Hashtable.Synchronized((Hashtable)_table.Clone());
  1342.                 }
  1343.             }
  1344.            
  1345.             public override IDictionaryEnumerator GetEnumerator()
  1346.             {
  1347.                 return _table.GetEnumerator();
  1348.             }
  1349.            
  1350.             public override ICollection Keys {
  1351.                 get {
  1352.                     lock (_table.SyncRoot) {
  1353.                         return _table.Keys;
  1354.                     }
  1355.                 }
  1356.             }
  1357.            
  1358.             public override ICollection Values {
  1359.                 get {
  1360.                     lock (_table.SyncRoot) {
  1361.                         return _table.Values;
  1362.                     }
  1363.                 }
  1364.             }
  1365.            
  1366.             public override void Remove(object key)
  1367.             {
  1368.                 lock (_table.SyncRoot) {
  1369.                     _table.Remove(key);
  1370.                 }
  1371.             }
  1372.            
  1373. /*==============================OnDeserialization===============================
  1374.             **Action: Does nothing.  We have to implement this because our parent HT implements it,
  1375.             **        but it doesn't do anything meaningful.  The real work will be done when we
  1376.             **        call OnDeserialization on our parent table.
  1377.             **Returns: void
  1378.             **Arguments: None
  1379.             **Exceptions: None
  1380.             ==============================================================================*/           
  1381.             public override void OnDeserialization(object sender)
  1382.             {
  1383.                 return;
  1384.             }
  1385.            
  1386.             internal override KeyValuePairs[] ToKeyValuePairsArray()
  1387.             {
  1388.                 return _table.ToKeyValuePairsArray();
  1389.             }
  1390.            
  1391.         }
  1392.        
  1393.        
  1394.         // Implements an enumerator for a hashtable. The enumerator uses the
  1395.         // internal version number of the hashtabke to ensure that no modifications
  1396.         // are made to the hashtable while an enumeration is in progress.
  1397.         [Serializable()]
  1398.         private class HashtableEnumerator : IDictionaryEnumerator, ICloneable
  1399.         {
  1400.             private Hashtable hashtable;
  1401.             private int bucket;
  1402.             private int version;
  1403.             private bool current;
  1404.             private int getObjectRetType;
  1405.             // What should GetObject return?
  1406.             private object currentKey;
  1407.             private object currentValue;
  1408.            
  1409.             internal const int Keys = 1;
  1410.             internal const int Values = 2;
  1411.             internal const int DictEntry = 3;
  1412.            
  1413.             internal HashtableEnumerator(Hashtable hashtable, int getObjRetType)
  1414.             {
  1415.                 this.hashtable = hashtable;
  1416.                 bucket = hashtable.buckets.Length;
  1417.                 version = hashtable.version;
  1418.                 current = false;
  1419.                 getObjectRetType = getObjRetType;
  1420.             }
  1421.            
  1422.             public object Clone()
  1423.             {
  1424.                 return MemberwiseClone();
  1425.             }
  1426.            
  1427.             public virtual object Key {
  1428.                 get {
  1429.                     if (current == false)
  1430.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
  1431.                     return currentKey;
  1432.                 }
  1433.             }
  1434.            
  1435.             public virtual bool MoveNext()
  1436.             {
  1437.                 if (version != hashtable.version)
  1438.                     throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
  1439.                 while (bucket > 0) {
  1440.                     bucket--;
  1441.                     object keyv = hashtable.buckets[bucket].key;
  1442.                     if ((keyv != null) && (keyv != hashtable.buckets)) {
  1443.                         currentKey = keyv;
  1444.                         currentValue = hashtable.buckets[bucket].val;
  1445.                         current = true;
  1446.                         return true;
  1447.                     }
  1448.                 }
  1449.                 current = false;
  1450.                 return false;
  1451.             }
  1452.            
  1453.             public virtual DictionaryEntry Entry {
  1454.                 get {
  1455.                     if (current == false)
  1456.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumOpCantHappen));
  1457.                     return new DictionaryEntry(currentKey, currentValue);
  1458.                 }
  1459.             }
  1460.            
  1461.            
  1462.             public virtual object Current {
  1463.                 get {
  1464.                     if (current == false)
  1465.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumOpCantHappen));
  1466.                    
  1467.                     if (getObjectRetType == Keys)
  1468.                         return currentKey;
  1469.                     else if (getObjectRetType == Values)
  1470.                         return currentValue;
  1471.                     else
  1472.                         return new DictionaryEntry(currentKey, currentValue);
  1473.                 }
  1474.             }
  1475.            
  1476.             public virtual object Value {
  1477.                 get {
  1478.                     if (current == false)
  1479.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumOpCantHappen));
  1480.                     return currentValue;
  1481.                 }
  1482.             }
  1483.            
  1484.             public virtual void Reset()
  1485.             {
  1486.                 if (version != hashtable.version)
  1487.                     throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
  1488.                 current = false;
  1489.                 bucket = hashtable.buckets.Length;
  1490.                 currentKey = null;
  1491.                 currentValue = null;
  1492.             }
  1493.         }
  1494.        
  1495.         // internal debug view class for hashtable
  1496.         internal class HashtableDebugView
  1497.         {
  1498.             private Hashtable hashtable;
  1499.            
  1500.             public HashtableDebugView(Hashtable hashtable)
  1501.             {
  1502.                 if (hashtable == null) {
  1503.                     throw new ArgumentNullException("hashtable");
  1504.                 }
  1505.                
  1506.                 this.hashtable = hashtable;
  1507.             }
  1508.            
  1509.            
  1510.             [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
  1511.             public KeyValuePairs[] Items {
  1512.                 get { return hashtable.ToKeyValuePairsArray(); }
  1513.             }
  1514.         }
  1515.     }
  1516.    
  1517.     static internal class HashHelpers
  1518.     {
  1519.         // Table of prime numbers to use as hash table sizes.
  1520.         // The entry used for capacity is the smallest prime number in this aaray
  1521.         // that is larger than twice the previous capacity.
  1522.        
  1523.         static internal readonly int[] primes = {3, 7, 11, 17, 23, 29, 37, 47, 59, 71,
  1524.         89, 107, 131, 163, 197, 239, 293, 353, 431, 521,
  1525.         631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371,
  1526.         4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023,
  1527.         25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363,
  1528.         156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403,
  1529.         968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559,
  1530.         5999471, 7199369};
  1531.        
  1532.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  1533.         static internal bool IsPrime(int candidate)
  1534.         {
  1535.             if ((candidate & 1) != 0) {
  1536.                 int limit = (int)Math.Sqrt(candidate);
  1537.                 for (int divisor = 3; divisor <= limit; divisor += 2) {
  1538.                     if ((candidate % divisor) == 0)
  1539.                         return false;
  1540.                 }
  1541.                 return true;
  1542.             }
  1543.             return (candidate == 2);
  1544.         }
  1545.        
  1546.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  1547.         static internal int GetPrime(int min)
  1548.         {
  1549.             if (min < 0)
  1550.                 throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
  1551.            
  1552.             for (int i = 0; i < primes.Length; i++) {
  1553.                 int prime = primes[i];
  1554.                 if (prime >= min)
  1555.                     return prime;
  1556.             }
  1557.            
  1558.             //outside of our predefined table.
  1559.             //compute the hard way.
  1560.             for (int i = (min | 1); i < Int32.MaxValue; i += 2) {
  1561.                 if (IsPrime(i))
  1562.                     return i;
  1563.             }
  1564.             return min;
  1565.         }
  1566.     }
  1567. }

Developer Fusion