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; i 0) {
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
- SmiGettersStream.cs
- BaseResourcesBuildProvider.cs
- Lasso.cs
- LogSwitch.cs
- RootProfilePropertySettingsCollection.cs
- XamlPointCollectionSerializer.cs
- DecimalAnimation.cs
- MessageSecurityOverTcp.cs
- BuildDependencySet.cs
- PropertyInfoSet.cs
- ProcessHostServerConfig.cs
- LinkButton.cs
- Assert.cs
- PieceNameHelper.cs
- CompiledXpathExpr.cs
- XXXOnTypeBuilderInstantiation.cs
- TypeNameConverter.cs
- DesignerLinkAdapter.cs
- ThrowHelper.cs
- TreeNodeStyleCollectionEditor.cs
- RevocationPoint.cs
- HtmlLiteralTextAdapter.cs
- SafePointer.cs
- EdmProperty.cs
- invalidudtexception.cs
- SelectionEditor.cs
- BaseInfoTable.cs
- BoundPropertyEntry.cs
- DataStreamFromComStream.cs
- ErrorStyle.cs
- Evaluator.cs
- ProfileSection.cs
- DesignSurface.cs
- NumericUpDownAcceleration.cs
- PublishLicense.cs
- ConnectionStringsExpressionBuilder.cs
- FontStretches.cs
- SqlBuilder.cs
- ELinqQueryState.cs
- EntityDataSourceEntityTypeFilterConverter.cs
- NamespaceMapping.cs
- MessageFormatterConverter.cs
- ObjectItemCollection.cs
- JournalEntryStack.cs
- XmlException.cs
- HwndSource.cs
- SQLDoubleStorage.cs
- CatalogPart.cs
- FieldToken.cs
- BindingGroup.cs
- SeekStoryboard.cs
- XmlSchemaNotation.cs
- CompatibleComparer.cs
- PasswordDeriveBytes.cs
- WebServiceEnumData.cs
- GridViewColumnHeaderAutomationPeer.cs
- Int32RectConverter.cs
- ProgressBarBrushConverter.cs
- XmlSchemaChoice.cs
- TableCell.cs
- ConfigurationStrings.cs
- PrefixQName.cs
- XmlBinaryReaderSession.cs
- DataContractSerializerOperationFormatter.cs
- CodeMemberMethod.cs
- VisualTreeHelper.cs
- HierarchicalDataSourceControl.cs
- ScriptRef.cs
- DetailsViewInsertEventArgs.cs
- BooleanConverter.cs
- SqlStatistics.cs
- ConsumerConnectionPointCollection.cs
- VirtualDirectoryMapping.cs
- ContainerCodeDomSerializer.cs
- DispatcherOperation.cs
- InboundActivityHelper.cs
- ContentOperations.cs
- EncryptedKeyHashIdentifierClause.cs
- RegexCode.cs
- SaveFileDialog.cs
- OracleParameterCollection.cs
- RoamingStoreFileUtility.cs
- Ref.cs
- XmlQualifiedNameTest.cs
- SegmentInfo.cs
- ISO2022Encoding.cs
- UnionExpr.cs
- DefaultTextStoreTextComposition.cs
- DesignTimeType.cs
- ValidationService.cs
- ClientSponsor.cs
- FileDialog_Vista_Interop.cs
- CircleHotSpot.cs
- SQLDoubleStorage.cs
- MulticastDelegate.cs
- Symbol.cs
- CodeTypeMemberCollection.cs
- CompilationSection.cs
- Vector3dCollection.cs
- RectangleConverter.cs