hashtable.cs

来自「没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没」· CS 代码 · 共 1,511 行 · 第 1/3 页

				while(origSize > 0)
				{
					--origSize;
					if(orig[origSize].key != null && orig[origSize].key != removed)
					{
						AddDirect(orig[origSize].key, orig[origSize].value);
					}
				}

				// Add the new entry to the hash table.
				AddDirect(key, value);

				// Update the generation count.
				++generation;
			}

	// Implement the ICloneable interface.
	public virtual Object Clone()
			{
				Hashtable hashtab = (Hashtable)(MemberwiseClone());
				if(capacity > 0)
				{
					hashtab.table = new HashBucket [capacity];
					Array.Copy(table, hashtab.table, capacity);
				}
				return hashtab;
			}

	// Implement the ICollection interface.
	public virtual void CopyTo(Array array, int index)
			{
				if(array == null)
				{
					throw new ArgumentNullException("array");
				}
				else if(array.Rank != 1)
				{
					throw new ArgumentException(_("Arg_RankMustBe1"));
				}
				else if(index < array.GetLowerBound(0))
				{
					throw new ArgumentOutOfRangeException
						("index", _("Arg_InvalidArrayIndex"));
				}
				else if(index > (array.GetLength(0) - num))
				{
					throw new ArgumentException(_("Arg_InvalidArrayRange"));
				}
				else
				{
					int posn;
					for(posn = 0; posn < table.Length; ++posn)
					{
						if(table[posn].key != null && table[posn].key != removed)
						{
							array.SetValue
								(new DictionaryEntry(table[posn].key,
													 table[posn].value),
								 index++);
						}
					}
				}
			}
	public virtual int Count
			{
				get
				{
					return num;
				}
			}
	public virtual bool IsSynchronized
			{
				get
				{
					return false;
				}
			}
	public virtual Object SyncRoot
			{
				get
				{
					return this;
				}
			}

	// Implement the IDictionary interface.
	public virtual void Add(Object key, Object value)
			{
				// Find an empty slot to add the entry, or expand
				// the table if there are no free slots.
				int hash = GetHash(key);
				if(capacity == 0)
				{
					ExpandAndAdd(key, value);
					return;
				}
				hash = (int)(((uint)hash) % ((uint)capacity));
				int count = capacity;
				while(count > 0)
				{
					if(table[hash].key == null || table[hash].key == removed)
					{
						// We've found an empty slot.  Check the capacity.
						if(num >= capacityLimit)
						{
							// We must increase the capacity before adding.
							ExpandAndAdd(key, value);
						}
						else
						{
							// Add the entry to the empty slot.
							table[hash].key = key;
							table[hash].value = value;
							++num;
							++generation;
						}
						return;
					}
					else if(KeyEquals(table[hash].key, key))
					{
						// There is already an entry with the key.
						throw new ArgumentException
							(_("Arg_ExistingEntry"));
					}
					hash = (hash + 1) % capacity;
					--count;
				}
				ExpandAndAdd(key, value);
			}
	public virtual void Clear()
			{
				if(table != null)
				{
					Array.Clear(table, 0, capacity);
				}
				num = 0;
			}
	public virtual bool Contains(Object key)
			{
				return ContainsKey(key);
			}
	public virtual IDictionaryEnumerator GetEnumerator()
			{
				return new HashtableEnum(this);
			}
	public virtual void Remove(Object key)
			{
				int hash = GetHash(key);
				if(capacity == 0)
				{
					return;
				}
				hash = (int)(((uint)hash) % ((uint)capacity));
				int count = capacity;
				while(count > 0)
				{
					if(table[hash].key == null)
					{
						break;
					}
					else if(KeyEquals(table[hash].key, key))
					{
						table[hash].key = removed;
						table[hash].value = null;
						--num;
						++generation;
						break;
					}
					hash = (hash + 1) % capacity;
					--count;
				}
			}
	public virtual bool IsFixedSize
			{
				get
				{
					return false;
				}
			}
	public virtual bool IsReadOnly
			{
				get
				{
					return false;
				}
			}
	[IndexerName("Item")]
	public virtual Object this[Object key]
			{
				get
				{
					// Find an existing entry with the specified key.
					int hash = GetHash(key);
					if(capacity == 0)
					{
						return null;
					}
					hash = (int)(((uint)hash) % ((uint)capacity));
					int count = capacity;
					while(count > 0)
					{
						if(table[hash].key == null)
						{
							break;
						}
						else if(KeyEquals(table[hash].key, key))
						{
							return table[hash].value;
						}
						hash = (hash + 1) % capacity;
						--count;
					}
					return null;
				}
				set
				{
					// Find an existing entry and replace it, or
					// add a new entry to the table if not found.
					int hash = GetHash(key);
					if(capacity == 0)
					{
						ExpandAndAdd(key, value);
						return;
					}
					hash = (int)(((uint)hash) % ((uint)capacity));
					int count = capacity;
					int removed_hash = -1;
					while(count > 0)
					{
						if(table[hash].key == removed && removed_hash == -1)
							removed_hash = hash;
						else if(table[hash].key == null)
							break;
						else if(KeyEquals(table[hash].key, key))
						{
							// There is already an entry with the key,
							// so replace its value.
							table[hash].value = value;
							++generation;
							return;
						}
						hash = (hash + 1) % capacity;
						--count;
					}
					// The key wan't in the table.  Add it.
					//
					// This code assums the invariant:
					//     capacity >= capacityLimit
					// always holds true.
					if(num >= capacityLimit)
					{
						// We must increase the capacity before adding.
						ExpandAndAdd(key, value);
					}
					else
					{
						// Add the entry to the empty slot.
						if (removed_hash != -1)
							hash = removed_hash;
						table[hash].key = key;
						table[hash].value = value;
						++num;
						++generation;
					}
				}
			}
	public virtual ICollection Keys
			{
				get
				{
					return new HashtableKeyValueCollection(this, true);
				}
			}
	public virtual ICollection Values
			{
				get
				{
					return new HashtableKeyValueCollection(this, false);
				}
			}

	// Implement the IEnumerable interface.
	IEnumerator IEnumerable.GetEnumerator()
			{
				return new HashtableEnum(this);
			}

	// Determine if this hash table contains a specific key.
	public virtual bool ContainsKey(Object key)
			{
				int hash = GetHash(key);
				if(capacity == 0)
				{
					return false;
				}
				hash = (int)(((uint)hash) % ((uint)capacity));
				int count = capacity;
				while(count > 0)
				{
					if(table[hash].key == null)
					{
						break;
					}
					else if(KeyEquals(table[hash].key, key))
					{
						return true;
					}
					hash = (hash + 1) % capacity;
					--count;
				}
				return false;
			}

	// Determine if this hash table contains a specific value.
	public virtual bool ContainsValue(Object value)
			{
				int posn;
				for(posn = capacity - 1; posn >= 0; --posn)
				{
					if(table[posn].key != null && table[posn].key != removed &&
					   table[posn].value == value)
					{
						return true;
					}
				}
				return false;
			}

	// Get the hash value for a key.
	protected virtual int GetHash(Object key)
			{
				if(key == null)
				{
					throw new ArgumentNullException("key");
				}
			#if ECMA_COMPAT
				if(hcp__ != null)
				{
					return hcp__.GetHashCode(key);
				}
			#else
				IHashCodeProvider provider = hcp;
				if(provider != null)
				{
					return provider.GetHashCode(key);
				}
			#endif
				else
				{
					return key.GetHashCode();
				}
			}

#if CONFIG_SERIALIZATION

	// Get the serialization data for this object.
	public virtual void GetObjectData(SerializationInfo info,
									  StreamingContext context)
			{
				if(info == null)
				{
					throw new ArgumentNullException("info");
				}
				info.AddValue("LoadFactor", loadFactor);
				info.AddValue("Version", generation);
				info.AddValue("Comparer", comparer, typeof(IComparer));
				info.AddValue("HashCodeProvider", hcp,
							  typeof(IHashCodeProvider));
				info.AddValue("HashSize", (table == null ? 0 : table.Length));

				Object[] keyTemp = new Object [num];
				Keys.CopyTo(keyTemp, 0);
				info.AddValue("Keys", keyTemp, typeof(Object[]));

				Object[] valTemp = new Object [num];
				Values.CopyTo(valTemp, 0);
				info.AddValue("Values", valTemp, typeof(Object[]));
			}

	// Process a deserialization callback.
	public virtual void OnDeserialization(Object sender)
			{
				// If the table is non-null, then we've been re-entered.
				if(table != null)
				{
					return;
				}

				// Bail out if there is no de-serialization information.
				if(info == null)
				{
					throw new ArgumentNullException("info");
				}

				// De-serialize the main parameter values.
				try
				{
					loadFactor = info.GetSingle("LoadFactor");
					if(loadFactor < 0.1f)
					{
						loadFactor = 0.1f;
					}
					else if(loadFactor > 1.0f)
					{
						loadFactor = 1.0f;
					}
				}
				catch(NotImplementedException)
				{
					// Floating point not supported by the runtime engine.
				}
				generation = info.GetInt32("Version");
				comparer = (IComparer)(info.GetValue
						("Comparer", typeof(IComparer)));
				hcp = (IHashCodeProvider)(info.GetValue
						("HashCodeProvider", typeof(IHashCodeProvider)));
				int hashSize = info.GetInt32("HashSize");
				if(hashSize > 0)
				{
					capacity = hashSize;
					try
					{
						capacityLimit = (int)(hashSize * loadFactor);
					}
					catch(NotImplementedException)
					{
						// Floating point not supported by the runtime engine.
						capacityLimit = capacity;
					}
					table = new HashBucket [hashSize];
				}

				// Get the key and value arrays from the serialization data.
				Object[] keys = (Object[])(info.GetValue
						("Keys", typeof(Object[])));
				Object[] values = (Object[])(info.GetValue
						("Values", typeof(Object[])));
				if(keys == null || values == null)
				{
					throw new SerializationException
						(_("Serialize_StateMissing"));
				}
				if(keys.Length != values.Length)
				{
					throw new SerializationException
						(_("Serialize_KeyValueMismatch"));
				}

				// Add the (key, value) pairs to the hash table.
				int posn;
				for(posn = 0; posn < keys.Length; ++posn)
				{
					Add(keys[posn], values[posn]);
				}

				// De-serialization is finished.
				info = null;
			}

#endif // CONFIG_SERIALIZATION

	// Determine if an item is equal to a key value.
	protected virtual bool KeyEquals(Object item, Object key)
			{
				if(item == null)
				{
					throw new ArgumentNullException("item");
				}
				if(key == null)
				{
					throw new ArgumentNullException("key");
				}
			#if ECMA_COMPAT
				if(comparer__ != null)
				{
					return (comparer__.Compare(item, key) == 0);
				}
			#else
				IComparer cmp = comparer;
				if(cmp != null)
				{
					return (cmp.Compare(item, key) == 0);
				}
			#endif
				else
				{
					return item.Equals(key);
				}
			}

	// Wrap a Hashtable object to make it synchronized.
	public static Hashtable Synchronized(Hashtable table)
			{
				if(table == null)
				{
					throw new ArgumentNullException("table");
				}
				else if(table.IsSynchronized)
				{
					return table;
				}
				else
				{
					return new SynchronizedHashtable(table);