Code:
/ FXUpdate3074 / FXUpdate3074 / 1.1 / untmp / whidbey / QFE / ndp / clr / src / BCL / System / Collections / Hashtable.cs / 1 / Hashtable.cs
// ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== /*============================================================ ** ** Class: Hashtable ** ** ** Purpose: Hash table implementation ** ** ===========================================================*/ namespace System.Collections { using System; using System.Runtime.Serialization; using System.Security.Permissions; using System.Diagnostics; using System.Threading; using System.Runtime.CompilerServices; using System.Runtime.ConstrainedExecution; // The Hashtable class represents a dictionary of associated keys and values // with constant lookup time. // // Objects used as keys in a hashtable must implement the GetHashCode // and Equals methods (or they can rely on the default implementations // inherited from Object if key equality is simply reference // equality). Furthermore, the GetHashCode and Equals methods of // a key object must produce the same results given the same parameters for the // entire time the key is present in the hashtable. In practical terms, this // means that key objects should be immutable, at least for the time they are // used as keys in a hashtable. // // When entries are added to a hashtable, they are placed into // buckets based on the hashcode of their keys. Subsequent lookups of // keys will use the hashcode of the keys to only search a particular bucket, // thus substantially reducing the number of key comparisons required to find // an entry. A hashtable's maximum load factor, which can be specified // when the hashtable is instantiated, determines the maximum ratio of // hashtable entries to hashtable buckets. Smaller load factors cause faster // average lookup times at the cost of increased memory consumption. The // default maximum load factor of 1.0 generally provides the best balance // between speed and size. As entries are added to a hashtable, the hashtable's // actual load factor increases, and when the actual load factor reaches the // maximum load factor value, the number of buckets in the hashtable is // automatically increased by approximately a factor of two (to be precise, the // number of hashtable buckets is increased to the smallest prime number that // is larger than twice the current number of hashtable buckets). // // Each object provides their own hash function, accessed by calling // GetHashCode(). However, one can write their own object // implementing IEqualityComparer and pass it to a constructor on // the Hashtable. That hash function (and the equals method on the // IEqualityComparer) would be used for all objects in the table. // // Changes since V1 during Whidbey: // *) Deprecated IHashCodeProvider, use IEqualityComparer instead. This will // allow better performance for objects where equality checking can be // done much faster than establishing an ordering between two objects, // such as an ordinal string equality [DebuggerTypeProxy(typeof(System.Collections.Hashtable.HashtableDebugView))] [DebuggerDisplay("Count = {Count}")] [System.Runtime.InteropServices.ComVisible(true)] [Serializable()] public class Hashtable : IDictionary, ISerializable, IDeserializationCallback, ICloneable { /* Implementation Notes: The generic Dictionary was copied from Hashtable's source - any */ private const String LoadFactorName = "LoadFactor"; private const String VersionName = "Version"; private const String ComparerName = "Comparer"; private const String HashCodeProviderName = "HashCodeProvider"; private const String HashSizeName = "HashSize"; // Must save buckets.Length private const String KeysName = "Keys"; private const String ValuesName = "Values"; private const String KeyComparerName = "KeyComparer"; // Deleted entries have their key set to buckets // The hash table data. // This cannot be serialised private struct bucket { public Object key; public Object val; public int hash_coll; // Store hash code; sign bit means there was a collision. } private bucket[] buckets; // The total number of entries in the hash table. private int count; // The total number of collision bits set in the hashtable private int occupancy; private int loadsize; private float loadFactor; private volatile int version; private volatile bool isWriterInProgress; private ICollection keys; private ICollection values; private IEqualityComparer _keycomparer; private Object _syncRoot; [Obsolete("Please use EqualityComparer property.")] protected IHashCodeProvider hcp { get { if( _keycomparer is CompatibleComparer) { return ((CompatibleComparer)_keycomparer).HashCodeProvider; } else if( _keycomparer == null) { return null; } else { throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure")); } } set { if (_keycomparer is CompatibleComparer) { CompatibleComparer keyComparer = (CompatibleComparer)_keycomparer; _keycomparer = new CompatibleComparer(keyComparer.Comparer, value); } else if( _keycomparer == null) { _keycomparer = new CompatibleComparer((IComparer)null, value); } else { throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure")); } } } [Obsolete("Please use KeyComparer properties.")] protected IComparer comparer { get { if( _keycomparer is CompatibleComparer) { return ((CompatibleComparer)_keycomparer).Comparer; } else if( _keycomparer == null) { return null; } else { throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure")); } } set { if (_keycomparer is CompatibleComparer) { CompatibleComparer keyComparer = (CompatibleComparer)_keycomparer; _keycomparer = new CompatibleComparer(value, keyComparer.HashCodeProvider); } else if( _keycomparer == null) { _keycomparer = new CompatibleComparer(value, (IHashCodeProvider)null); } else { throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure")); } } } protected IEqualityComparer EqualityComparer { get { return _keycomparer; } } private SerializationInfo m_siInfo; //A temporary variable which we need during deserialization. // Note: this constructor is a bogus constructor that does nothing // and is for use only with SyncHashtable. internal Hashtable( bool trash ) { } // Constructs a new hashtable. The hashtable is created with an initial // capacity of zero and a load factor of 1.0. public Hashtable() : this(0, 1.0f) { } // Constructs a new hashtable with the given initial capacity and a load // factor of 1.0. The capacity argument serves as an indication of // the number of entries the hashtable will contain. When this number (or // an approximation) is known, specifying it in the constructor can // eliminate a number of resizing operations that would otherwise be // performed when elements are added to the hashtable. // public Hashtable(int capacity) : this(capacity, 1.0f) { } // Constructs a new hashtable with the given initial capacity and load // factor. The capacity argument serves as an indication of the // number of entries the hashtable will contain. When this number (or an // approximation) is known, specifying it in the constructor can eliminate // a number of resizing operations that would otherwise be performed when // elements are added to the hashtable. The loadFactor argument // indicates the maximum ratio of hashtable entries to hashtable buckets. // Smaller load factors cause faster average lookup times at the cost of // increased memory consumption. A load factor of 1.0 generally provides // the best balance between speed and size. // public Hashtable(int capacity, float loadFactor) { if (capacity < 0) throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); if (!(loadFactor >= 0.1f && loadFactor <= 1.0f)) throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", .1, 1.0)); // Based on perf work, .72 is the optimal load factor for this table. this.loadFactor = 0.72f * loadFactor; double rawsize = capacity / this.loadFactor; if (rawsize > Int32.MaxValue) throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow")); // Avoid awfully small sizes int hashsize = (rawsize > 11) ? HashHelpers.GetPrime((int)rawsize) : 11; buckets = new bucket[hashsize]; loadsize = (int)(this.loadFactor * hashsize); isWriterInProgress = false; // Based on the current algorithm, loadsize must be less than hashsize. BCLDebug.Assert( loadsize < hashsize, "Invalid hashtable loadsize!"); } // Constructs a new hashtable with the given initial capacity and load // factor. The capacity argument serves as an indication of the // number of entries the hashtable will contain. When this number (or an // approximation) is known, specifying it in the constructor can eliminate // a number of resizing operations that would otherwise be performed when // elements are added to the hashtable. The loadFactor argument // indicates the maximum ratio of hashtable entries to hashtable buckets. // Smaller load factors cause faster average lookup times at the cost of // increased memory consumption. A load factor of 1.0 generally provides // the best balance between speed and size. The hcp argument // is used to specify an Object that will provide hash codes for all // the Objects in the table. Using this, you can in effect override // GetHashCode() on each Object using your own hash function. The // comparer argument will let you specify a custom function for // comparing keys. By specifying user-defined objects for hcp // and comparer, users could make a hash table using strings // as keys do case-insensitive lookups. // [Obsolete("Please use Hashtable(int, float, IEqualityComparer) instead.")] public Hashtable(int capacity, float loadFactor, IHashCodeProvider hcp, IComparer comparer) : this(capacity, loadFactor) { if (hcp == null && comparer == null) { this._keycomparer = null; } else { this._keycomparer = new CompatibleComparer(comparer,hcp); } } public Hashtable(int capacity, float loadFactor, IEqualityComparer equalityComparer) : this(capacity, loadFactor) { this._keycomparer = equalityComparer; } // Constructs a new hashtable using a custom hash function // and a custom comparison function for keys. This will enable scenarios // such as doing lookups with case-insensitive strings. // [Obsolete("Please use Hashtable(IEqualityComparer) instead.")] public Hashtable(IHashCodeProvider hcp, IComparer comparer) : this(0, 1.0f, hcp, comparer) { } public Hashtable(IEqualityComparer equalityComparer) : this(0, 1.0f, equalityComparer) { } // Constructs a new hashtable using a custom hash function // and a custom comparison function for keys. This will enable scenarios // such as doing lookups with case-insensitive strings. // [Obsolete("Please use Hashtable(int, IEqualityComparer) instead.")] public Hashtable(int capacity, IHashCodeProvider hcp, IComparer comparer) : this(capacity, 1.0f, hcp, comparer) { } public Hashtable(int capacity, IEqualityComparer equalityComparer) : this(capacity, 1.0f, equalityComparer) { } // Constructs a new hashtable containing a copy of the entries in the given // dictionary. The hashtable is created with a load factor of 1.0. // public Hashtable(IDictionary d) : this(d, 1.0f) { } // Constructs a new hashtable containing a copy of the entries in the given // dictionary. The hashtable is created with the given load factor. // public Hashtable(IDictionary d, float loadFactor) : this(d, loadFactor, (IEqualityComparer)null) { } [Obsolete("Please use Hashtable(IDictionary, IEqualityComparer) instead.")] public Hashtable(IDictionary d, IHashCodeProvider hcp, IComparer comparer) : this(d, 1.0f, hcp, comparer) { } public Hashtable(IDictionary d, IEqualityComparer equalityComparer) : this(d, 1.0f, equalityComparer) { } [Obsolete("Please use Hashtable(IDictionary, float, IEqualityComparer) instead.")] public Hashtable(IDictionary d, float loadFactor, IHashCodeProvider hcp, IComparer comparer) : this((d != null ? d.Count : 0), loadFactor, hcp, comparer) { if (d==null) throw new ArgumentNullException("d", Environment.GetResourceString("ArgumentNull_Dictionary")); IDictionaryEnumerator e = d.GetEnumerator(); while (e.MoveNext()) Add(e.Key, e.Value); } public Hashtable(IDictionary d, float loadFactor, IEqualityComparer equalityComparer) : this((d != null ? d.Count : 0), loadFactor, equalityComparer) { if (d==null) throw new ArgumentNullException("d", Environment.GetResourceString("ArgumentNull_Dictionary")); IDictionaryEnumerator e = d.GetEnumerator(); while (e.MoveNext()) Add(e.Key, e.Value); } protected Hashtable(SerializationInfo info, StreamingContext context) { //We can't do anything with the keys and values until the entire graph has been deserialized //and we have a resonable estimate that GetHashCode is not going to fail. For the time being, //we'll just cache this. The graph is not valid until OnDeserialization has been called. m_siInfo = info; } // Computes the hash function: H(key, i) = h1(key) + i*h2(key, hashSize). // The out parameter seed is h1(key), while the out parameter // incr is h2(key, hashSize). Callers of this function should // add incr each time through a loop. private uint InitHash(Object key, int hashsize, out uint seed, out uint incr) { // Hashcode must be positive. Also, we must not use the sign bit, since // that is used for the collision bit. uint hashcode = (uint) GetHash(key) & 0x7FFFFFFF; seed = (uint) hashcode; // Restriction: incr MUST be between 1 and hashsize - 1, inclusive for // the modular arithmetic to work correctly. This guarantees you'll // visit every bucket in the table exactly once within hashsize // iterations. Violate this and it'll cause obscure bugs forever. // If you change this calculation for h2(key), update putEntry too! incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)hashsize - 1))); return hashcode; } // Adds an entry with the given key and value to this hashtable. An // ArgumentException is thrown if the key is null or if the key is already // present in the hashtable. // public virtual void Add(Object key, Object value) { Insert(key, value, true); } // Removes all entries from this hashtable. [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)] public virtual void Clear() { if (count == 0) return; Thread.BeginCriticalRegion(); isWriterInProgress = true; for (int i = 0; i < buckets.Length; i++){ buckets[i].hash_coll = 0; buckets[i].key = null; buckets[i].val = null; } count = 0; occupancy = 0; UpdateVersion(); isWriterInProgress = false; Thread.EndCriticalRegion(); } // Clone returns a virtually identical copy of this hash table. This does // a shallow copy - the Objects in the table aren't cloned, only the references // to those Objects. public virtual Object Clone() { bucket[] lbuckets = buckets; Hashtable ht = new Hashtable(count,_keycomparer); ht.version = version; ht.loadFactor = loadFactor; ht.count = 0; int bucket = lbuckets.Length; while (bucket > 0) { bucket--; Object keyv = lbuckets[bucket].key; if ((keyv!= null) && (keyv != lbuckets)) { ht[keyv] = lbuckets[bucket].val; } } return ht; } // Checks if this hashtable contains the given key. public virtual bool Contains(Object key) { return ContainsKey(key); } // Checks if this hashtable contains an entry with the given key. This is // an O(1) operation. // public virtual bool ContainsKey(Object key) { if (key == null) { throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key")); } uint seed; uint incr; // Take a snapshot of buckets, in case another thread resizes table bucket[] lbuckets = buckets; uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr); int ntry = 0; bucket b; int bucketNumber = (int) (seed % (uint)lbuckets.Length); do { b = lbuckets[bucketNumber]; if (b.key == null) { return false; } if (((b.hash_coll & 0x7FFFFFFF) == hashcode) && KeyEquals (b.key, key)) return true; bucketNumber = (int) (((long)bucketNumber + incr)% (uint)lbuckets.Length); } while (b.hash_coll < 0 && ++ntry < lbuckets.Length); return false; } // Checks if this hashtable contains an entry with the given value. The // values of the entries of the hashtable are compared to the given value // using the Object.Equals method. This method performs a linear // search and is thus be substantially slower than the ContainsKey // method. // public virtual bool ContainsValue(Object value) { if (value == null) { for (int i = buckets.Length; --i >= 0;) { if (buckets[i].key != null && buckets[i].key != buckets && buckets[i].val == null) return true; } } else { for (int i = buckets.Length; --i >= 0;) { Object val = buckets[i].val; if (val!=null && val.Equals(value)) return true; } } return false; } // Copies the keys of this hashtable to a given array starting at a given // index. This method is used by the implementation of the CopyTo method in // the KeyCollection class. private void CopyKeys(Array array, int arrayIndex) { bucket[] lbuckets = buckets; for (int i = lbuckets.Length; --i >= 0;) { Object keyv = lbuckets[i].key; if ((keyv != null) && (keyv != buckets)){ array.SetValue(keyv, arrayIndex++); } } } // Copies the keys of this hashtable to a given array starting at a given // index. This method is used by the implementation of the CopyTo method in // the KeyCollection class. private void CopyEntries(Array array, int arrayIndex) { bucket[] lbuckets = buckets; for (int i = lbuckets.Length; --i >= 0;) { Object keyv = lbuckets[i].key; if ((keyv != null) && (keyv != buckets)){ DictionaryEntry entry = new DictionaryEntry(keyv,lbuckets[i].val); array.SetValue(entry, arrayIndex++); } } } // Copies the values in this hash table to an array at // a given index. Note that this only copies values, and not keys. public virtual void CopyTo(Array array, int arrayIndex) { if (array == null) throw new ArgumentNullException("array", Environment.GetResourceString("ArgumentNull_Array")); if (array.Rank != 1) throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); if (arrayIndex < 0) throw new ArgumentOutOfRangeException("arrayIndex", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); if (array.Length - arrayIndex < count) throw new ArgumentException(Environment.GetResourceString("Arg_ArrayPlusOffTooSmall")); CopyEntries(array, arrayIndex); } // Copies the values in this Hashtable to an KeyValuePairs array. // KeyValuePairs is different from Dictionary Entry in that it has special // debugger attributes on its fields. internal virtual KeyValuePairs[] ToKeyValuePairsArray() { KeyValuePairs[] array = new KeyValuePairs[count]; int index = 0; bucket[] lbuckets = buckets; for (int i = lbuckets.Length; --i >= 0;) { Object keyv = lbuckets[i].key; if ((keyv != null) && (keyv != buckets)){ array[index++] = new KeyValuePairs(keyv,lbuckets[i].val); } } return array; } // Copies the values of this hashtable to a given array starting at a given // index. This method is used by the implementation of the CopyTo method in // the ValueCollection class. private void CopyValues(Array array, int arrayIndex) { bucket[] lbuckets = buckets; for (int i = lbuckets.Length; --i >= 0;) { Object keyv = lbuckets[i].key; if ((keyv != null) && (keyv != buckets)){ array.SetValue(lbuckets[i].val, arrayIndex++); } } } // Returns the value associated with the given key. If an entry with the // given key is not found, the returned value is null. // public virtual Object this[Object key] { get { if (key == null) { throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key")); } uint seed; uint incr; // Take a snapshot of buckets, in case another thread does a resize bucket[] lbuckets = buckets; uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr); int ntry = 0; bucket b; int bucketNumber = (int) (seed % (uint)lbuckets.Length); do { int currentversion; // A read operation on hashtable has three steps: // (1) calculate the hash and find the slot number. // (2) compare the hashcode, if equal, go to step 3. Otherwise end. // (3) compare the key, if equal, go to step 4. Otherwise end. // (4) return the value contained in the bucket. // After step 3 and before step 4. A writer can kick in a remove the old item and add a new one // in the same bukcet. So in the reader we need to int spinCount = 0; do { // this is violate read, following memory accesses can not be moved ahead of it. currentversion = version; b = lbuckets[bucketNumber]; // The contention between reader and writer shouldn't happen frequently. // But just in case this will burn CPU, yield the control of CPU if we spinned a few times. // 8 is just a random number I pick. if( (++spinCount) % 8 == 0 ) { Thread.Sleep(1); // 1 means we are yeilding control to all threads, including low-priority ones. } } while ( isWriterInProgress || (currentversion != version) ); if (b.key == null) { return null; } if (((b.hash_coll & 0x7FFFFFFF) == hashcode) && KeyEquals (b.key, key)) return b.val; bucketNumber = (int) (((long)bucketNumber + incr)% (uint)lbuckets.Length); } while (b.hash_coll < 0 && ++ntry < lbuckets.Length); return null; } set { Insert(key, value, false); } } // Increases the bucket count of this hashtable. This method is called from // the Insert method when the actual load factor of the hashtable reaches // the upper limit specified when the hashtable was constructed. The number // of buckets in the hashtable is increased to the smallest prime number // that is larger than twice the current number of buckets, and the entries // in the hashtable are redistributed into the new buckets using the cached // hashcodes. private void expand() { int rawsize = HashHelpers.GetPrime(buckets.Length*2); // buckets.Length*2 will not overflow rehash(rawsize); } // We occationally need to rehash the table to clean up the collision bits. private void rehash() { rehash( buckets.Length ); } private void UpdateVersion() { // Version might become negative when version is Int32.MaxValue, but the oddity will be still be correct. // So we don't need to special case this. version++; } [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] private void rehash( int newsize ) { // reset occupancy occupancy=0; // Don't replace any internal state until we've finished adding to the // new bucket[]. This serves two purposes: // 1) Allow concurrent readers to see valid hashtable contents // at all times // 2) Protect against an OutOfMemoryException while allocating this // new bucket[]. bucket[] newBuckets = new bucket[newsize]; // rehash table into new buckets int nb; for (nb = 0; nb < buckets.Length; nb++){ bucket oldb = buckets[nb]; if ((oldb.key != null) && (oldb.key != buckets)){ putEntry(newBuckets, oldb.key, oldb.val, oldb.hash_coll & 0x7FFFFFFF); } } // New bucket[] is good to go - replace buckets and other internal state. Thread.BeginCriticalRegion(); isWriterInProgress = true; buckets = newBuckets; loadsize = (int)(loadFactor * newsize); UpdateVersion(); isWriterInProgress = false; Thread.EndCriticalRegion(); // minimun size of hashtable is 11 now and maximum loadFactor is 0.72 now. BCLDebug.Assert(loadsize < newsize, "Our current implementaion means this is not possible."); return; } // Returns an enumerator for this hashtable. // If modifications made to the hashtable while an enumeration is // in progress, the MoveNext and Current methods of the // enumerator will throw an exception. // IEnumerator IEnumerable.GetEnumerator() { return new HashtableEnumerator(this, HashtableEnumerator.DictEntry); } // Returns a dictionary enumerator for this hashtable. // If modifications made to the hashtable while an enumeration is // in progress, the MoveNext and Current methods of the // enumerator will throw an exception. // public virtual IDictionaryEnumerator GetEnumerator() { return new HashtableEnumerator(this, HashtableEnumerator.DictEntry); } // Internal method to get the hash code for an Object. This will call // GetHashCode() on each object if you haven't provided an IHashCodeProvider // instance. Otherwise, it calls hcp.GetHashCode(obj). protected virtual int GetHash(Object key) { if (_keycomparer != null) return _keycomparer.GetHashCode(key); return key.GetHashCode(); } // Is this Hashtable read-only? public virtual bool IsReadOnly { get { return false; } } public virtual bool IsFixedSize { get { return false; } } // Is this Hashtable synchronized? See SyncRoot property public virtual bool IsSynchronized { get { return false; } } // Internal method to compare two keys. If you have provided an IComparer // instance in the constructor, this method will call comparer.Compare(item, key). // Otherwise, it will call item.Equals(key). // protected virtual bool KeyEquals(Object item, Object key) { BCLDebug.Assert(key != null, "key can't be null here!"); if( Object.ReferenceEquals(buckets, item)) { return false; } if (_keycomparer != null) return _keycomparer.Equals(item, key); return item == null ? false : item.Equals(key); } // Returns a collection representing the keys of this hashtable. The order // in which the returned collection represents the keys is unspecified, but // it is guaranteed to be buckets = newBuckets; the same order in which a collection returned by // GetValues represents the values of the hashtable. // // The returned collection is live in the sense that any changes // to the hash table are reflected in this collection. It is not // a static copy of all the keys in the hash table. // public virtual ICollection Keys { get { if (keys == null) keys = new KeyCollection(this); return keys; } } // Returns a collection representing the values of this hashtable. The // order in which the returned collection represents the values is // unspecified, but it is guaranteed to be the same order in which a // collection returned by GetKeys represents the keys of the // hashtable. // // The returned collection is live in the sense that any changes // to the hash table are reflected in this collection. It is not // a static copy of all the keys in the hash table. // public virtual ICollection Values { get { if (values == null) values = new ValueCollection(this); return values; } } // Inserts an entry into this hashtable. This method is called from the Set // and Add methods. If the add parameter is true and the given key already // exists in the hashtable, an exception is thrown. [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] private void Insert (Object key, Object nvalue, bool add) { if (key == null) { throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key")); } if (count >= loadsize) { expand(); } else if(occupancy > loadsize && count > 100) { rehash(); } uint seed; uint incr; // Assume we only have one thread writing concurrently. Modify // buckets to contain new data, as long as we insert in the right order. uint hashcode = InitHash(key, buckets.Length, out seed, out incr); int ntry = 0; int emptySlotNumber = -1; // We use the empty slot number to cache the first empty slot. We chose to reuse slots // create by remove that have the collision bit set over using up new slots. int bucketNumber = (int) (seed % (uint)buckets.Length); do { // Set emptySlot number to current bucket if it is the first available bucket that we have seen // that once contained an entry and also has had a collision. // We need to search this entire collision chain because we have to ensure that there are no // duplicate entries in the table. if (emptySlotNumber == -1 && (buckets[bucketNumber].key == buckets) && (buckets[bucketNumber].hash_coll < 0))//(((buckets[bucketNumber].hash_coll & unchecked(0x80000000))!=0))) emptySlotNumber = bucketNumber; // Insert the key/value pair into this bucket if this bucket is empty and has never contained an entry // OR // This bucket once contained an entry but there has never been a collision if ((buckets[bucketNumber].key == null) || (buckets[bucketNumber].key == buckets && ((buckets[bucketNumber].hash_coll & unchecked(0x80000000))==0))) { // If we have found an available bucket that has never had a collision, but we've seen an available // bucket in the past that has the collision bit set, use the previous bucket instead if (emptySlotNumber != -1) // Reuse slot bucketNumber = emptySlotNumber; // We pretty much have to insert in this order. Don't set hash // code until the value & key are set appropriately. Thread.BeginCriticalRegion(); isWriterInProgress = true; buckets[bucketNumber].val = nvalue; buckets[bucketNumber].key = key; buckets[bucketNumber].hash_coll |= (int) hashcode; count++; UpdateVersion(); isWriterInProgress = false; Thread.EndCriticalRegion(); return; } // The current bucket is in use // OR // it is available, but has had the collision bit set and we have already found an available bucket if (((buckets[bucketNumber].hash_coll & 0x7FFFFFFF) == hashcode) && KeyEquals (buckets[bucketNumber].key, key)) { if (add) { throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", buckets[bucketNumber].key, key)); } Thread.BeginCriticalRegion(); isWriterInProgress = true; buckets[bucketNumber].val = nvalue; UpdateVersion(); isWriterInProgress = false; Thread.EndCriticalRegion(); return; } // The current bucket is full, and we have therefore collided. We need to set the collision bit // UNLESS // we have remembered an available slot previously. if (emptySlotNumber == -1) {// We don't need to set the collision bit here since we already have an empty slot if( buckets[bucketNumber].hash_coll >= 0 ) { buckets[bucketNumber].hash_coll |= unchecked((int)0x80000000); occupancy++; } } bucketNumber = (int) (((long)bucketNumber + incr)% (uint)buckets.Length); } while (++ntry < buckets.Length); // This code is here if and only if there were no buckets without a collision bit set in the entire table if (emptySlotNumber != -1) { // We pretty much have to insert in this order. Don't set hash // code until the value & key are set appropriately. Thread.BeginCriticalRegion(); isWriterInProgress = true; buckets[emptySlotNumber].val = nvalue; buckets[emptySlotNumber].key = key; buckets[emptySlotNumber].hash_coll |= (int) hashcode; count++; UpdateVersion(); isWriterInProgress = false; Thread.EndCriticalRegion(); return; } // If you see this assertt, make sure load factor & count are reasonable. // Then verify that our double hash function (h2, described at top of file) // meets the requirements described above. You should never see this assertt. BCLDebug.Assert(false, "hash table insert failed! Load factor too high, or our double hashing function is incorrect."); throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_HashInsertFailed")); } private void putEntry (bucket[] newBuckets, Object key, Object nvalue, int hashcode) { BCLDebug.Assert(hashcode >= 0, "hashcode >= 0"); // make sure collision bit (sign bit) wasn't set. uint seed = (uint) hashcode; uint incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)newBuckets.Length - 1))); int bucketNumber = (int) (seed % (uint)newBuckets.Length); do { if ((newBuckets[bucketNumber].key == null) || (newBuckets[bucketNumber].key == buckets)) { newBuckets[bucketNumber].val = nvalue; newBuckets[bucketNumber].key = key; newBuckets[bucketNumber].hash_coll |= hashcode; return; } if( newBuckets[bucketNumber].hash_coll >= 0 ) { newBuckets[bucketNumber].hash_coll |= unchecked((int)0x80000000); occupancy++; } bucketNumber = (int) (((long)bucketNumber + incr)% (uint)newBuckets.Length); } while (true); } // Removes an entry from this hashtable. If an entry with the specified // key exists in the hashtable, it is removed. An ArgumentException is // thrown if the key is null. // [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] public virtual void Remove(Object key) { if (key == null) { throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key")); } uint seed; uint incr; // Assuming only one concurrent writer, write directly into buckets. uint hashcode = InitHash(key, buckets.Length, out seed, out incr); int ntry = 0; bucket b; int bn = (int) (seed % (uint)buckets.Length); // bucketNumber do { b = buckets[bn]; if (((b.hash_coll & 0x7FFFFFFF) == hashcode) && KeyEquals (b.key, key)) { Thread.BeginCriticalRegion(); isWriterInProgress = true; // Clear hash_coll field, then key, then value buckets[bn].hash_coll &= unchecked((int)0x80000000); if (buckets[bn].hash_coll != 0) { buckets[bn].key = buckets; } else { buckets[bn].key = null; } buckets[bn].val = null; // Free object references sooner & simplify ContainsValue. count--; UpdateVersion(); isWriterInProgress = false; Thread.EndCriticalRegion(); return; } bn = (int) (((long)bn + incr)% (uint)buckets.Length); } while (b.hash_coll < 0 && ++ntry < buckets.Length); //throw new ArgumentException(Environment.GetResourceString("Arg_RemoveArgNotFound")); } // Returns the object to synchronize on for this hash table. public virtual Object SyncRoot { get { if( _syncRoot == null) { System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null); } return _syncRoot; } } // Returns the number of associations in this hashtable. // public virtual int Count { get { return count; } } // Returns a thread-safe wrapper for a Hashtable. // [HostProtection(Synchronization=true)] public static Hashtable Synchronized(Hashtable table) { if (table==null) throw new ArgumentNullException("table"); return new SyncHashtable(table); } // // The ISerializable Implementation // public virtual void GetObjectData(SerializationInfo info, StreamingContext context) { if (info==null) { throw new ArgumentNullException("info"); } info.AddValue(LoadFactorName, loadFactor); info.AddValue(VersionName, version); // // We need to maintain serialization compatibility with Everett and RTM. // If the comparer is null or a compatible comparer, serialize Hashtable // in a format that can be deserialized on Everett and RTM. // #pragma warning disable 618 if( _keycomparer == null) { info.AddValue(ComparerName, null,typeof(IComparer)); info.AddValue(HashCodeProviderName, null, typeof(IHashCodeProvider)); } else if(_keycomparer is CompatibleComparer) { CompatibleComparer c = _keycomparer as CompatibleComparer; info.AddValue(ComparerName, c.Comparer, typeof(IComparer)); info.AddValue(HashCodeProviderName, c.HashCodeProvider, typeof(IHashCodeProvider)); } else{ info.AddValue(KeyComparerName, _keycomparer, typeof(IEqualityComparer)); } #pragma warning restore 618 info.AddValue(HashSizeName, buckets.Length); //This is the length of the bucket array. Object [] serKeys = new Object[count]; Object [] serValues = new Object[count]; CopyKeys(serKeys, 0); CopyValues(serValues,0); info.AddValue(KeysName, serKeys, typeof(Object[])); info.AddValue(ValuesName, serValues, typeof(Object[])); } // // DeserializationEvent Listener // public virtual void OnDeserialization(Object sender) { if (buckets!=null) { return; //Somebody had a dependency on this hashtable and fixed us up before the ObjectManager got to it. } if (m_siInfo==null) { throw new SerializationException(Environment.GetResourceString("Serialization_InvalidOnDeser")); } int hashsize = 0; IComparer c = null; #pragma warning disable 618 IHashCodeProvider hcp = null; #pragma warning restore 618 Object [] serKeys = null; Object [] serValues = null; SerializationInfoEnumerator enumerator = m_siInfo.GetEnumerator(); while( enumerator.MoveNext()) { switch( enumerator.Name) { case LoadFactorName: loadFactor = m_siInfo.GetSingle(LoadFactorName); break; case HashSizeName: hashsize = m_siInfo.GetInt32(HashSizeName); break; case KeyComparerName: _keycomparer = (IEqualityComparer)m_siInfo.GetValue(KeyComparerName, typeof(IEqualityComparer)); break; case ComparerName: c = (IComparer)m_siInfo.GetValue(ComparerName, typeof(IComparer)); break; case HashCodeProviderName: #pragma warning disable 618 hcp = (IHashCodeProvider)m_siInfo.GetValue(HashCodeProviderName, typeof(IHashCodeProvider)); #pragma warning restore 618 break; case KeysName: serKeys = (Object[])m_siInfo.GetValue(KeysName, typeof(Object[])); break; case ValuesName: serValues = (Object[])m_siInfo.GetValue(ValuesName, typeof(Object[])); break; } } loadsize = (int)(loadFactor*hashsize); // V1 object doesn't has _keycomparer field. if ( (_keycomparer == null) && ( (c != null) || (hcp != null) ) ){ _keycomparer = new CompatibleComparer(c,hcp); } buckets = new bucket[hashsize]; if (serKeys==null) { throw new SerializationException(Environment.GetResourceString("Serialization_MissingKeys")); } if (serValues==null) { throw new SerializationException(Environment.GetResourceString("Serialization_MissingValues")); } if (serKeys.Length!=serValues.Length) { throw new SerializationException(Environment.GetResourceString("Serialization_KeyValueDifferentSizes")); } for (int i=0; i0) { bucket--; Object keyv = hashtable.buckets[bucket].key; if ((keyv!= null) && (keyv != hashtable.buckets)) { currentKey = keyv; currentValue = hashtable.buckets[bucket].val; current = true; return true; } } current = false; return false; } public virtual DictionaryEntry Entry { get { if (current == false) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumOpCantHappen)); return new DictionaryEntry(currentKey, currentValue); } } public virtual Object Current { get { if (current == false) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumOpCantHappen)); if (getObjectRetType==Keys) return currentKey; else if (getObjectRetType==Values) return currentValue; else return new DictionaryEntry(currentKey, currentValue); } } public virtual Object Value { get { if (current == false) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumOpCantHappen)); return currentValue; } } public virtual void Reset() { if (version != hashtable.version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); current = false; bucket = hashtable.buckets.Length; currentKey = null; currentValue = null; } } // internal debug view class for hashtable internal class HashtableDebugView { private Hashtable hashtable; public HashtableDebugView( Hashtable hashtable) { if( hashtable == null) { throw new ArgumentNullException( "hashtable"); } this.hashtable = hashtable; } [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] public KeyValuePairs[] Items { get { return hashtable.ToKeyValuePairsArray(); } } } } internal static class HashHelpers { // Table of prime numbers to use as hash table sizes. // The entry used for capacity is the smallest prime number in this aaray // that is larger than twice the previous capacity. internal static readonly int[] primes = { 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369}; [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)] internal static bool IsPrime(int candidate) { if ((candidate & 1) != 0) { int limit = (int)Math.Sqrt (candidate); for (int divisor = 3; divisor <= limit; divisor+=2) { if ((candidate % divisor) == 0) return false; } return true; } return (candidate == 2); } [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)] internal static int GetPrime(int min) { if (min < 0) throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow")); for (int i = 0; i < primes.Length; i++) { int prime = primes[i]; if (prime >= min) return prime; } //outside of our predefined table. //compute the hard way. for (int i = (min | 1); i < Int32.MaxValue;i+=2) { if (IsPrime(i)) return i; } return min; } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- TemplateComponentConnector.cs
- SQLString.cs
- AuthenticationException.cs
- listitem.cs
- OleDbConnectionPoolGroupProviderInfo.cs
- WebPartMenu.cs
- RtType.cs
- TransportListener.cs
- SqlUtils.cs
- ContextDataSourceContextData.cs
- OleDbDataAdapter.cs
- InternalCache.cs
- ScriptResourceDefinition.cs
- AggregateException.cs
- DeviceSpecific.cs
- XpsResourcePolicy.cs
- EntityContainerAssociationSet.cs
- AttributeData.cs
- Material.cs
- LogicalTreeHelper.cs
- TextComposition.cs
- ProfileProvider.cs
- SelectionListComponentEditor.cs
- PopupEventArgs.cs
- PageStatePersister.cs
- TypeDescriptionProviderAttribute.cs
- IImplicitResourceProvider.cs
- SQLString.cs
- TreeViewItem.cs
- InvalidFilterCriteriaException.cs
- Point3DCollection.cs
- XsltContext.cs
- WebPartConnectionsConnectVerb.cs
- Adorner.cs
- ControlUtil.cs
- SqlDataSourceCache.cs
- unsafenativemethodstextservices.cs
- FederatedMessageSecurityOverHttpElement.cs
- ByteRangeDownloader.cs
- Nodes.cs
- EdmRelationshipRoleAttribute.cs
- safesecurityhelperavalon.cs
- Rijndael.cs
- LocalizationComments.cs
- FlowDocumentScrollViewer.cs
- GridLength.cs
- SafePointer.cs
- SubqueryRules.cs
- CompilationSection.cs
- ReferencedType.cs
- WebFormsRootDesigner.cs
- FixedSOMGroup.cs
- _FixedSizeReader.cs
- FontCollection.cs
- WebConfigurationHost.cs
- SelectionEditingBehavior.cs
- WrapPanel.cs
- DataBinder.cs
- DeviceFilterEditorDialog.cs
- MapPathBasedVirtualPathProvider.cs
- AggregationMinMaxHelpers.cs
- DocumentReference.cs
- WebPartUserCapability.cs
- SqlRemoveConstantOrderBy.cs
- QueryableDataSource.cs
- CodeMethodReturnStatement.cs
- HtmlEncodedRawTextWriter.cs
- CodeTryCatchFinallyStatement.cs
- XmlSchemaAttributeGroup.cs
- PersonalizationDictionary.cs
- AppDomainFactory.cs
- HttpCapabilitiesBase.cs
- WrappedKeySecurityToken.cs
- MeshGeometry3D.cs
- BindingEditor.xaml.cs
- StatusBarDrawItemEvent.cs
- ResourceKey.cs
- ControlAdapter.cs
- BitmapEffectGroup.cs
- URL.cs
- SchemaNotation.cs
- HierarchicalDataBoundControlAdapter.cs
- StringUtil.cs
- WindowManager.cs
- SizeAnimationUsingKeyFrames.cs
- ProtectedConfiguration.cs
- GradientPanel.cs
- FragmentNavigationEventArgs.cs
- ResourceReferenceExpression.cs
- DynamicDataManager.cs
- BypassElement.cs
- ChannelSinkStacks.cs
- XmlWrappingReader.cs
- DetailsViewUpdateEventArgs.cs
- GridViewDeleteEventArgs.cs
- DataGridViewColumnCollectionDialog.cs
- Base64Stream.cs
- OdbcConnectionHandle.cs
- SamlConditions.cs
- ToolStripRendererSwitcher.cs