diff options
Diffstat (limited to 'src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs')
| -rw-r--r-- | src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs | 1463 |
1 files changed, 1463 insertions, 0 deletions
diff --git a/src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs b/src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs new file mode 100644 index 000000000..5b576973a --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs @@ -0,0 +1,1463 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System; +using System.Collections; +using System.Diagnostics; +using System.Runtime.CompilerServices; +using System.Runtime.Serialization; + +namespace System.Collections.Generic +{ + /// <summary> + /// Used internally to control behavior of insertion into a <see cref="Dictionary{TKey, TValue}"/>. + /// </summary> + internal enum InsertionBehavior : byte + { + /// <summary> + /// The default insertion behavior. + /// </summary> + None = 0, + + /// <summary> + /// Specifies that an existing entry with the same key should be overwritten if encountered. + /// </summary> + OverwriteExisting = 1, + + /// <summary> + /// Specifies that if an existing entry with the same key is encountered, an exception should be thrown. + /// </summary> + ThrowOnExisting = 2 + } + + [DebuggerTypeProxy(typeof(IDictionaryDebugView<,>))] + [DebuggerDisplay("Count = {Count}")] + [Serializable] + [System.Runtime.CompilerServices.TypeForwardedFrom("mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")] + public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback + { + private struct Entry + { + public int hashCode; // Lower 31 bits of hash code, -1 if unused + public int next; // Index of next entry, -1 if last + public TKey key; // Key of entry + public TValue value; // Value of entry + } + + private int[] buckets; + private Entry[] entries; + private int count; + private int version; + private int freeList; + private int freeCount; + private IEqualityComparer<TKey> comparer; + private KeyCollection keys; + private ValueCollection values; + private object _syncRoot; + + // constants for serialization + private const string VersionName = "Version"; // Do not rename (binary serialization) + private const string HashSizeName = "HashSize"; // Do not rename (binary serialization). Must save buckets.Length + private const string KeyValuePairsName = "KeyValuePairs"; // Do not rename (binary serialization) + private const string ComparerName = "Comparer"; // Do not rename (binary serialization) + + public Dictionary() : this(0, null) { } + + public Dictionary(int capacity) : this(capacity, null) { } + + public Dictionary(IEqualityComparer<TKey> comparer) : this(0, comparer) { } + + public Dictionary(int capacity, IEqualityComparer<TKey> comparer) + { + if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity); + if (capacity > 0) Initialize(capacity); + this.comparer = comparer ?? EqualityComparer<TKey>.Default; + + if (this.comparer == EqualityComparer<string>.Default) + { + this.comparer = (IEqualityComparer<TKey>)NonRandomizedStringEqualityComparer.Default; + } + } + + public Dictionary(IDictionary<TKey, TValue> dictionary) : this(dictionary, null) { } + + public Dictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) : + this(dictionary != null ? dictionary.Count : 0, comparer) + { + if (dictionary == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); + } + + // It is likely that the passed-in dictionary is Dictionary<TKey,TValue>. When this is the case, + // avoid the enumerator allocation and overhead by looping through the entries array directly. + // We only do this when dictionary is Dictionary<TKey,TValue> and not a subclass, to maintain + // back-compat with subclasses that may have overridden the enumerator behavior. + if (dictionary.GetType() == typeof(Dictionary<TKey, TValue>)) + { + Dictionary<TKey, TValue> d = (Dictionary<TKey, TValue>)dictionary; + int count = d.count; + Entry[] entries = d.entries; + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) + { + Add(entries[i].key, entries[i].value); + } + } + return; + } + + foreach (KeyValuePair<TKey, TValue> pair in dictionary) + { + Add(pair.Key, pair.Value); + } + } + + public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection) : this(collection, null) { } + + public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer) : + this((collection as ICollection<KeyValuePair<TKey, TValue>>)?.Count ?? 0, comparer) + { + if (collection == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); + } + + foreach (KeyValuePair<TKey, TValue> pair in collection) + { + Add(pair.Key, pair.Value); + } + } + + protected Dictionary(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. + HashHelpers.SerializationInfoTable.Add(this, info); + } + + public IEqualityComparer<TKey> Comparer + { + get + { + return comparer; + } + } + + public int Count + { + get { return count - freeCount; } + } + + public KeyCollection Keys + { + get + { + if (keys == null) keys = new KeyCollection(this); + return keys; + } + } + + ICollection<TKey> IDictionary<TKey, TValue>.Keys + { + get + { + if (keys == null) keys = new KeyCollection(this); + return keys; + } + } + + IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys + { + get + { + if (keys == null) keys = new KeyCollection(this); + return keys; + } + } + + public ValueCollection Values + { + get + { + if (values == null) values = new ValueCollection(this); + return values; + } + } + + ICollection<TValue> IDictionary<TKey, TValue>.Values + { + get + { + if (values == null) values = new ValueCollection(this); + return values; + } + } + + IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values + { + get + { + if (values == null) values = new ValueCollection(this); + return values; + } + } + + public TValue this[TKey key] + { + get + { + int i = FindEntry(key); + if (i >= 0) return entries[i].value; + ThrowHelper.ThrowKeyNotFoundException(); + return default(TValue); + } + set + { + bool modified = TryInsert(key, value, InsertionBehavior.OverwriteExisting); + Debug.Assert(modified); + } + } + + public void Add(TKey key, TValue value) + { + bool modified = TryInsert(key, value, InsertionBehavior.ThrowOnExisting); + Debug.Assert(modified); // If there was an existing key and the Add failed, an exception will already have been thrown. + } + + void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair) + { + Add(keyValuePair.Key, keyValuePair.Value); + } + + bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair) + { + int i = FindEntry(keyValuePair.Key); + if (i >= 0 && EqualityComparer<TValue>.Default.Equals(entries[i].value, keyValuePair.Value)) + { + return true; + } + return false; + } + + bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair) + { + int i = FindEntry(keyValuePair.Key); + if (i >= 0 && EqualityComparer<TValue>.Default.Equals(entries[i].value, keyValuePair.Value)) + { + Remove(keyValuePair.Key); + return true; + } + return false; + } + + public void Clear() + { + if (count > 0) + { + for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; + Array.Clear(entries, 0, count); + freeList = -1; + count = 0; + freeCount = 0; + version++; + } + } + + public bool ContainsKey(TKey key) + { + return FindEntry(key) >= 0; + } + + public bool ContainsValue(TValue value) + { + if (value == null) + { + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0 && entries[i].value == null) return true; + } + } + else + { + EqualityComparer<TValue> c = EqualityComparer<TValue>.Default; + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true; + } + } + return false; + } + + private void CopyTo(KeyValuePair<TKey, TValue>[] array, int index) + { + if (array == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (index < 0 || index > array.Length) + { + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); + } + + if (array.Length - index < Count) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + int count = this.count; + Entry[] entries = this.entries; + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) + { + array[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value); + } + } + } + + public Enumerator GetEnumerator() + { + return new Enumerator(this, Enumerator.KeyValuePair); + } + + IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() + { + return new Enumerator(this, Enumerator.KeyValuePair); + } + + public virtual void GetObjectData(SerializationInfo info, StreamingContext context) + { + if (info == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info); + } + + info.AddValue(VersionName, version); + info.AddValue(ComparerName, comparer, typeof(IEqualityComparer<TKey>)); + info.AddValue(HashSizeName, buckets == null ? 0 : buckets.Length); // This is the length of the bucket array + + if (buckets != null) + { + var array = new KeyValuePair<TKey, TValue>[Count]; + CopyTo(array, 0); + info.AddValue(KeyValuePairsName, array, typeof(KeyValuePair<TKey, TValue>[])); + } + } + + private int FindEntry(TKey key) + { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + + if (buckets != null) + { + int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; + for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) + { + if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i; + } + } + return -1; + } + + private void Initialize(int capacity) + { + int size = HashHelpers.GetPrime(capacity); + buckets = new int[size]; + for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; + entries = new Entry[size]; + freeList = -1; + } + + private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior) + { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + + if (buckets == null) Initialize(0); + int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; + int targetBucket = hashCode % buckets.Length; + int collisionCount = 0; + + for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) + { + if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) + { + if (behavior == InsertionBehavior.OverwriteExisting) + { + entries[i].value = value; + version++; + return true; + } + + if (behavior == InsertionBehavior.ThrowOnExisting) + { + ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key); + } + + return false; + } + collisionCount++; + } + + int index; + if (freeCount > 0) + { + index = freeList; + freeList = entries[index].next; + freeCount--; + } + else + { + if (count == entries.Length) + { + Resize(); + targetBucket = hashCode % buckets.Length; + } + index = count; + count++; + } + + entries[index].hashCode = hashCode; + entries[index].next = buckets[targetBucket]; + entries[index].key = key; + entries[index].value = value; + buckets[targetBucket] = index; + version++; + + // If we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing + // i.e. EqualityComparer<string>.Default. + + if (collisionCount > HashHelpers.HashCollisionThreshold && comparer is NonRandomizedStringEqualityComparer) + { + comparer = (IEqualityComparer<TKey>)EqualityComparer<string>.Default; + Resize(entries.Length, true); + } + + return true; + } + + public virtual void OnDeserialization(object sender) + { + SerializationInfo siInfo; + HashHelpers.SerializationInfoTable.TryGetValue(this, out siInfo); + + if (siInfo == null) + { + // We can return immediately if this function is called twice. + // Note we remove the serialization info from the table at the end of this method. + return; + } + + int realVersion = siInfo.GetInt32(VersionName); + int hashsize = siInfo.GetInt32(HashSizeName); + comparer = (IEqualityComparer<TKey>)siInfo.GetValue(ComparerName, typeof(IEqualityComparer<TKey>)); + + if (hashsize != 0) + { + buckets = new int[hashsize]; + for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; + entries = new Entry[hashsize]; + freeList = -1; + + KeyValuePair<TKey, TValue>[] array = (KeyValuePair<TKey, TValue>[]) + siInfo.GetValue(KeyValuePairsName, typeof(KeyValuePair<TKey, TValue>[])); + + if (array == null) + { + ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingKeys); + } + + for (int i = 0; i < array.Length; i++) + { + if (array[i].Key == null) + { + ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_NullKey); + } + Add(array[i].Key, array[i].Value); + } + } + else + { + buckets = null; + } + + version = realVersion; + HashHelpers.SerializationInfoTable.Remove(this); + } + + private void Resize() + { + Resize(HashHelpers.ExpandPrime(count), false); + } + + private void Resize(int newSize, bool forceNewHashCodes) + { + Debug.Assert(newSize >= entries.Length); + int[] newBuckets = new int[newSize]; + for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1; + Entry[] newEntries = new Entry[newSize]; + Array.Copy(entries, 0, newEntries, 0, count); + + if (forceNewHashCodes) + { + for (int i = 0; i < count; i++) + { + if (newEntries[i].hashCode != -1) + { + newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF); + } + } + } + + for (int i = 0; i < count; i++) + { + if (newEntries[i].hashCode >= 0) + { + int bucket = newEntries[i].hashCode % newSize; + newEntries[i].next = newBuckets[bucket]; + newBuckets[bucket] = i; + } + } + + buckets = newBuckets; + entries = newEntries; + } + + // The overload Remove(TKey key, out TValue value) is a copy of this method with one additional + // statement to copy the value for entry being removed into the output parameter. + // Code has been intentionally duplicated for performance reasons. + public bool Remove(TKey key) + { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + + if (buckets != null) + { + int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; + int bucket = hashCode % buckets.Length; + int last = -1; + int i = buckets[bucket]; + while (i >= 0) + { + ref Entry entry = ref entries[i]; + + if (entry.hashCode == hashCode && comparer.Equals(entry.key, key)) + { + if (last < 0) + { + buckets[bucket] = entry.next; + } + else + { + entries[last].next = entry.next; + } + entry.hashCode = -1; + entry.next = freeList; + + if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>()) + { + entry.key = default(TKey); + } + if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>()) + { + entry.value = default(TValue); + } + freeList = i; + freeCount++; + version++; + return true; + } + + last = i; + i = entry.next; + } + } + return false; + } + + // This overload is a copy of the overload Remove(TKey key) with one additional + // statement to copy the value for entry being removed into the output parameter. + // Code has been intentionally duplicated for performance reasons. + public bool Remove(TKey key, out TValue value) + { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + + if (buckets != null) + { + int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; + int bucket = hashCode % buckets.Length; + int last = -1; + int i = buckets[bucket]; + while (i >= 0) + { + ref Entry entry = ref entries[i]; + + if (entry.hashCode == hashCode && comparer.Equals(entry.key, key)) + { + if (last < 0) + { + buckets[bucket] = entry.next; + } + else + { + entries[last].next = entry.next; + } + + value = entry.value; + + entry.hashCode = -1; + entry.next = freeList; + + if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>()) + { + entry.key = default(TKey); + } + if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>()) + { + entry.value = default(TValue); + } + freeList = i; + freeCount++; + version++; + return true; + } + + last = i; + i = entry.next; + } + } + value = default(TValue); + return false; + } + + public bool TryGetValue(TKey key, out TValue value) + { + int i = FindEntry(key); + if (i >= 0) + { + value = entries[i].value; + return true; + } + value = default(TValue); + return false; + } + + public bool TryAdd(TKey key, TValue value) => TryInsert(key, value, InsertionBehavior.None); + + bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly + { + get { return false; } + } + + void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int index) + { + CopyTo(array, index); + } + + void ICollection.CopyTo(Array array, int index) + { + if (array == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (array.Rank != 1) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); + } + + if (array.GetLowerBound(0) != 0) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); + } + + if (index < 0 || index > array.Length) + { + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); + } + + if (array.Length - index < Count) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + KeyValuePair<TKey, TValue>[] pairs = array as KeyValuePair<TKey, TValue>[]; + if (pairs != null) + { + CopyTo(pairs, index); + } + else if (array is DictionaryEntry[]) + { + DictionaryEntry[] dictEntryArray = array as DictionaryEntry[]; + Entry[] entries = this.entries; + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) + { + dictEntryArray[index++] = new DictionaryEntry(entries[i].key, entries[i].value); + } + } + } + else + { + object[] objects = array as object[]; + if (objects == null) + { + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); + } + + try + { + int count = this.count; + Entry[] entries = this.entries; + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) + { + objects[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value); + } + } + } + catch (ArrayTypeMismatchException) + { + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); + } + } + } + + IEnumerator IEnumerable.GetEnumerator() + { + return new Enumerator(this, Enumerator.KeyValuePair); + } + + bool ICollection.IsSynchronized + { + get { return false; } + } + + object ICollection.SyncRoot + { + get + { + if (_syncRoot == null) + { + System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); + } + return _syncRoot; + } + } + + bool IDictionary.IsFixedSize + { + get { return false; } + } + + bool IDictionary.IsReadOnly + { + get { return false; } + } + + ICollection IDictionary.Keys + { + get { return (ICollection)Keys; } + } + + ICollection IDictionary.Values + { + get { return (ICollection)Values; } + } + + object IDictionary.this[object key] + { + get + { + if (IsCompatibleKey(key)) + { + int i = FindEntry((TKey)key); + if (i >= 0) + { + return entries[i].value; + } + } + return null; + } + set + { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value); + + try + { + TKey tempKey = (TKey)key; + try + { + this[tempKey] = (TValue)value; + } + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); + } + } + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); + } + } + } + + private static bool IsCompatibleKey(object key) + { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + return (key is TKey); + } + + void IDictionary.Add(object key, object value) + { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value); + + try + { + TKey tempKey = (TKey)key; + + try + { + Add(tempKey, (TValue)value); + } + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); + } + } + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); + } + } + + bool IDictionary.Contains(object key) + { + if (IsCompatibleKey(key)) + { + return ContainsKey((TKey)key); + } + + return false; + } + + IDictionaryEnumerator IDictionary.GetEnumerator() + { + return new Enumerator(this, Enumerator.DictEntry); + } + + void IDictionary.Remove(object key) + { + if (IsCompatibleKey(key)) + { + Remove((TKey)key); + } + } + + public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>, + IDictionaryEnumerator + { + private Dictionary<TKey, TValue> dictionary; + private int version; + private int index; + private KeyValuePair<TKey, TValue> current; + private int getEnumeratorRetType; // What should Enumerator.Current return? + + internal const int DictEntry = 1; + internal const int KeyValuePair = 2; + + internal Enumerator(Dictionary<TKey, TValue> dictionary, int getEnumeratorRetType) + { + this.dictionary = dictionary; + version = dictionary.version; + index = 0; + this.getEnumeratorRetType = getEnumeratorRetType; + current = new KeyValuePair<TKey, TValue>(); + } + + public bool MoveNext() + { + if (version != dictionary.version) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); + } + + // Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends. + // dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue + while ((uint)index < (uint)dictionary.count) + { + ref Entry entry = ref dictionary.entries[index++]; + + if (entry.hashCode >= 0) + { + current = new KeyValuePair<TKey, TValue>(entry.key, entry.value); + return true; + } + } + + index = dictionary.count + 1; + current = new KeyValuePair<TKey, TValue>(); + return false; + } + + public KeyValuePair<TKey, TValue> Current + { + get { return current; } + } + + public void Dispose() + { + } + + object IEnumerator.Current + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + if (getEnumeratorRetType == DictEntry) + { + return new System.Collections.DictionaryEntry(current.Key, current.Value); + } + else + { + return new KeyValuePair<TKey, TValue>(current.Key, current.Value); + } + } + } + + void IEnumerator.Reset() + { + if (version != dictionary.version) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); + } + + index = 0; + current = new KeyValuePair<TKey, TValue>(); + } + + DictionaryEntry IDictionaryEnumerator.Entry + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + return new DictionaryEntry(current.Key, current.Value); + } + } + + object IDictionaryEnumerator.Key + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + return current.Key; + } + } + + object IDictionaryEnumerator.Value + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + return current.Value; + } + } + } + + [DebuggerTypeProxy(typeof(DictionaryKeyCollectionDebugView<,>))] + [DebuggerDisplay("Count = {Count}")] + public sealed class KeyCollection : ICollection<TKey>, ICollection, IReadOnlyCollection<TKey> + { + private Dictionary<TKey, TValue> dictionary; + + public KeyCollection(Dictionary<TKey, TValue> dictionary) + { + if (dictionary == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); + } + this.dictionary = dictionary; + } + + public Enumerator GetEnumerator() + { + return new Enumerator(dictionary); + } + + public void CopyTo(TKey[] array, int index) + { + if (array == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (index < 0 || index > array.Length) + { + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); + } + + if (array.Length - index < dictionary.Count) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + int count = dictionary.count; + Entry[] entries = dictionary.entries; + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) array[index++] = entries[i].key; + } + } + + public int Count + { + get { return dictionary.Count; } + } + + bool ICollection<TKey>.IsReadOnly + { + get { return true; } + } + + void ICollection<TKey>.Add(TKey item) + { + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); + } + + void ICollection<TKey>.Clear() + { + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); + } + + bool ICollection<TKey>.Contains(TKey item) + { + return dictionary.ContainsKey(item); + } + + bool ICollection<TKey>.Remove(TKey item) + { + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); + return false; + } + + IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator() + { + return new Enumerator(dictionary); + } + + IEnumerator IEnumerable.GetEnumerator() + { + return new Enumerator(dictionary); + } + + void ICollection.CopyTo(Array array, int index) + { + if (array == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (array.Rank != 1) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); + } + + if (array.GetLowerBound(0) != 0) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); + } + + if (index < 0 || index > array.Length) + { + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); + } + + if (array.Length - index < dictionary.Count) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + TKey[] keys = array as TKey[]; + if (keys != null) + { + CopyTo(keys, index); + } + else + { + object[] objects = array as object[]; + if (objects == null) + { + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); + } + + int count = dictionary.count; + Entry[] entries = dictionary.entries; + try + { + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) objects[index++] = entries[i].key; + } + } + catch (ArrayTypeMismatchException) + { + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); + } + } + } + + bool ICollection.IsSynchronized + { + get { return false; } + } + + object ICollection.SyncRoot + { + get { return ((ICollection)dictionary).SyncRoot; } + } + + public struct Enumerator : IEnumerator<TKey>, System.Collections.IEnumerator + { + private Dictionary<TKey, TValue> dictionary; + private int index; + private int version; + private TKey currentKey; + + internal Enumerator(Dictionary<TKey, TValue> dictionary) + { + this.dictionary = dictionary; + version = dictionary.version; + index = 0; + currentKey = default(TKey); + } + + public void Dispose() + { + } + + public bool MoveNext() + { + if (version != dictionary.version) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); + } + + while ((uint)index < (uint)dictionary.count) + { + ref Entry entry = ref dictionary.entries[index++]; + + if (entry.hashCode >= 0) + { + currentKey = entry.key; + return true; + } + } + + index = dictionary.count + 1; + currentKey = default(TKey); + return false; + } + + public TKey Current + { + get + { + return currentKey; + } + } + + object System.Collections.IEnumerator.Current + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + return currentKey; + } + } + + void System.Collections.IEnumerator.Reset() + { + if (version != dictionary.version) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); + } + + index = 0; + currentKey = default(TKey); + } + } + } + + [DebuggerTypeProxy(typeof(DictionaryValueCollectionDebugView<,>))] + [DebuggerDisplay("Count = {Count}")] + public sealed class ValueCollection : ICollection<TValue>, ICollection, IReadOnlyCollection<TValue> + { + private Dictionary<TKey, TValue> dictionary; + + public ValueCollection(Dictionary<TKey, TValue> dictionary) + { + if (dictionary == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); + } + this.dictionary = dictionary; + } + + public Enumerator GetEnumerator() + { + return new Enumerator(dictionary); + } + + public void CopyTo(TValue[] array, int index) + { + if (array == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (index < 0 || index > array.Length) + { + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); + } + + if (array.Length - index < dictionary.Count) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + int count = dictionary.count; + Entry[] entries = dictionary.entries; + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) array[index++] = entries[i].value; + } + } + + public int Count + { + get { return dictionary.Count; } + } + + bool ICollection<TValue>.IsReadOnly + { + get { return true; } + } + + void ICollection<TValue>.Add(TValue item) + { + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); + } + + bool ICollection<TValue>.Remove(TValue item) + { + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); + return false; + } + + void ICollection<TValue>.Clear() + { + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); + } + + bool ICollection<TValue>.Contains(TValue item) + { + return dictionary.ContainsValue(item); + } + + IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator() + { + return new Enumerator(dictionary); + } + + IEnumerator IEnumerable.GetEnumerator() + { + return new Enumerator(dictionary); + } + + void ICollection.CopyTo(Array array, int index) + { + if (array == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (array.Rank != 1) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); + } + + if (array.GetLowerBound(0) != 0) + { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); + } + + if (index < 0 || index > array.Length) + { + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); + } + + if (array.Length - index < dictionary.Count) + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + + TValue[] values = array as TValue[]; + if (values != null) + { + CopyTo(values, index); + } + else + { + object[] objects = array as object[]; + if (objects == null) + { + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); + } + + int count = dictionary.count; + Entry[] entries = dictionary.entries; + try + { + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) objects[index++] = entries[i].value; + } + } + catch (ArrayTypeMismatchException) + { + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); + } + } + } + + bool ICollection.IsSynchronized + { + get { return false; } + } + + object ICollection.SyncRoot + { + get { return ((ICollection)dictionary).SyncRoot; } + } + + public struct Enumerator : IEnumerator<TValue>, System.Collections.IEnumerator + { + private Dictionary<TKey, TValue> dictionary; + private int index; + private int version; + private TValue currentValue; + + internal Enumerator(Dictionary<TKey, TValue> dictionary) + { + this.dictionary = dictionary; + version = dictionary.version; + index = 0; + currentValue = default(TValue); + } + + public void Dispose() + { + } + + public bool MoveNext() + { + if (version != dictionary.version) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); + } + + while ((uint)index < (uint)dictionary.count) + { + ref Entry entry = ref dictionary.entries[index++]; + + if (entry.hashCode >= 0) + { + currentValue = entry.value; + return true; + } + } + index = dictionary.count + 1; + currentValue = default(TValue); + return false; + } + + public TValue Current + { + get + { + return currentValue; + } + } + + object System.Collections.IEnumerator.Current + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + return currentValue; + } + } + + void System.Collections.IEnumerator.Reset() + { + if (version != dictionary.version) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); + } + index = 0; + currentValue = default(TValue); + } + } + } + } +} |