Code:
/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / clr / src / BCL / System / Collections / Generic / Dictionary.cs / 1305376 / Dictionary.cs
// ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== /*============================================================ ** ** Class: Dictionary ** **[....] ** ** Purpose: Generic hash table implementation ** ** #DictionaryVersusHashtableThreadSafety ** Hashtable has multiple reader/single writer (MR/SW) thread safety built into ** certain methods and properties, whereas Dictionary doesn't. If you're ** converting framework code that formerly used Hashtable to Dictionary, it's ** important to consider whether callers may have taken a dependence on MR/SW ** thread safety. If a reader writer lock is available, then that may be used ** with a Dictionary to get the same thread safety guarantee. ** ** Reader writer locks don't exist in silverlight, so we do the following as a ** result of removing non-generic collections from silverlight: ** 1. If the Hashtable was fully synchronized, then we replace it with a ** Dictionary with full locks around reads/writes (same thread safety ** guarantee). ** 2. Otherwise, the Hashtable has the default MR/SW thread safety behavior, ** so we do one of the following on a case-by-case basis: ** a. If the ---- can be addressed by rearranging the code and using a temp ** variable (for example, it's only populated immediately after created) ** then we address the ---- this way and use Dictionary. ** b. If there's concern about degrading performance with the increased ** locking, we ifdef with FEATURE_NONGENERIC_COLLECTIONS so we can at ** least use Hashtable in the desktop build, but Dictionary with full ** locks in silverlight builds. Note that this is heavier locking than ** MR/SW, but this is the only option without rewriting (or adding back) ** the reader writer lock. ** c. If there's no performance concern (e.g. debug-only code) we ** consistently replace Hashtable with Dictionary plus full locks to ** reduce complexity. ** d. Most of serialization is dead code in silverlight. Instead of updating ** those Hashtable occurences in serialization, we carved out references ** to serialization such that this code doesn't need to build in ** silverlight. ===========================================================*/ namespace System.Collections.Generic { using System; using System.Collections; using System.Diagnostics; using System.Diagnostics.Contracts; using System.Runtime.Serialization; using System.Security.Permissions; [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))] [DebuggerDisplay("Count = {Count}")] [Serializable] [System.Runtime.InteropServices.ComVisible(false)] public class Dictionary: IDictionary , IDictionary, 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 comparer; private KeyCollection keys; private ValueCollection values; private Object _syncRoot; private SerializationInfo m_siInfo; //A temporary variable which we need during deserialization. // constants for serialization private const String VersionName = "Version"; private const String HashSizeName = "HashSize"; // Must save buckets.Length private const String KeyValuePairsName = "KeyValuePairs"; private const String ComparerName = "Comparer"; public Dictionary(): this(0, null) {} public Dictionary(int capacity): this(capacity, null) {} public Dictionary(IEqualityComparer comparer): this(0, comparer) {} public Dictionary(int capacity, IEqualityComparer comparer) { if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity); if (capacity > 0) Initialize(capacity); this.comparer = comparer ?? EqualityComparer .Default; } public Dictionary(IDictionary dictionary): this(dictionary, null) {} public Dictionary(IDictionary dictionary, IEqualityComparer comparer): this(dictionary != null? dictionary.Count: 0, comparer) { if( dictionary == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); } foreach (KeyValuePair pair in dictionary) { 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. m_siInfo = info; } public IEqualityComparer Comparer { get { return comparer; } } public int Count { get { return count - freeCount; } } public KeyCollection Keys { get { Contract.Ensures(Contract.Result () != null); if (keys == null) keys = new KeyCollection(this); return keys; } } ICollection IDictionary .Keys { get { if (keys == null) keys = new KeyCollection(this); return keys; } } public ValueCollection Values { get { Contract.Ensures(Contract.Result () != null); if (values == null) values = new ValueCollection(this); return values; } } ICollection IDictionary .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 { Insert(key, value, false); } } public void Add(TKey key, TValue value) { Insert(key, value, true); } void ICollection >.Add(KeyValuePair keyValuePair) { Add(keyValuePair.Key, keyValuePair.Value); } bool ICollection >.Contains(KeyValuePair keyValuePair) { int i = FindEntry(keyValuePair.Key); if( i >= 0 && EqualityComparer .Default.Equals(entries[i].value, keyValuePair.Value)) { return true; } return false; } bool ICollection >.Remove(KeyValuePair keyValuePair) { int i = FindEntry(keyValuePair.Key); if( i >= 0 && EqualityComparer .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 c = EqualityComparer .Default; for (int i = 0; i < count; i++) { if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true; } } return false; } // This security annotation is present only because of tool issues. Annotations should be kept in the // baseline xml files. Basically, don't copy this style of security annotation! [System.Security.SecuritySafeCritical] private void CopyTo(KeyValuePair [] array, int index) { if (array == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } if (index < 0 || index > array.Length ) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); } 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 (entries[i].key, entries[i].value); } } } public Enumerator GetEnumerator() { return new Enumerator(this, Enumerator.KeyValuePair); } IEnumerator > IEnumerable >.GetEnumerator() { return new Enumerator(this, Enumerator.KeyValuePair); } [System.Security.SecurityCritical] // auto-generated_required 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 )); info.AddValue(HashSizeName, buckets == null ? 0 : buckets.Length); //This is the length of the bucket array. if( buckets != null) { KeyValuePair [] array = new KeyValuePair [Count]; CopyTo(array, 0); info.AddValue(KeyValuePairsName, array, typeof(KeyValuePair [])); } } 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 void Insert(TKey key, TValue value, bool add) { if( key == null ) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } if (buckets == null) Initialize(0); int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; int targetBucket = hashCode % buckets.Length; for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) { if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { if (add) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); } entries[i].value = value; version++; return; } } 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++; } public virtual void OnDeserialization(Object sender) { if (m_siInfo==null) { // It might be necessary to call OnDeserialization from a container if the container object also implements // OnDeserialization. However, remoting will call OnDeserialization again. // We can return immediately if this function is called twice. // Note we set m_siInfo to null at the end of this method. return; } int realVersion = m_siInfo.GetInt32(VersionName); int hashsize = m_siInfo.GetInt32(HashSizeName); comparer = (IEqualityComparer )m_siInfo.GetValue(ComparerName, typeof(IEqualityComparer )); 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 [] array = (KeyValuePair []) m_siInfo.GetValue(KeyValuePairsName, typeof(KeyValuePair [])); if (array==null) { ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingKeys); } for (int i=0; i = 0; last = i, i = entries[i].next) { if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { if (last < 0) { buckets[bucket] = entries[i].next; } else { entries[last].next = entries[i].next; } entries[i].hashCode = -1; entries[i].next = freeList; entries[i].key = default(TKey); entries[i].value = default(TValue); freeList = i; freeCount++; version++; return true; } } } 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; } // This is a convenience method for the internal callers that were converted from using Hashtable. // Many were combining key doesn't exist and key exists but null value (for non-value types) checks. // This allows them to continue getting that behavior with minimal code delta. This is basically // TryGetValue without the out param internal TValue GetValueOrDefault(TKey key) { int i = FindEntry(key); if (i >= 0) { return entries[i].value; } return default(TValue); } bool ICollection >.IsReadOnly { get { return false; } } void ICollection >.CopyTo(KeyValuePair [] 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.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); } if (array.Length - index < Count) { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); } KeyValuePair [] pairs = array as KeyValuePair []; 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(ExceptionResource.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 (entries[i].key, entries[i].value); } } } catch(ArrayTypeMismatchException) { ThrowHelper.ThrowArgumentException(ExceptionResource.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
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- CommandHelpers.cs
- WmfPlaceableFileHeader.cs
- ValidatorUtils.cs
- RowUpdatedEventArgs.cs
- TextRenderer.cs
- TemplatedAdorner.cs
- SqlGatherConsumedAliases.cs
- embossbitmapeffect.cs
- HttpTransportSecurityElement.cs
- ApplicationDirectoryMembershipCondition.cs
- PointConverter.cs
- ValidateNames.cs
- WorkflowExecutor.cs
- ServiceElementCollection.cs
- ToolStripPanelRow.cs
- TextParaClient.cs
- TimeZone.cs
- ContentElement.cs
- TextDecorationLocationValidation.cs
- DetailsViewInsertEventArgs.cs
- HtmlInputText.cs
- DataGridViewRowsAddedEventArgs.cs
- EventPropertyMap.cs
- LayoutSettings.cs
- SafeRightsManagementHandle.cs
- StylusPlugin.cs
- CommandCollectionEditor.cs
- DataServiceQueryException.cs
- MimeTypePropertyAttribute.cs
- SvcMapFileSerializer.cs
- GridView.cs
- DataFieldConverter.cs
- HostedTransportConfigurationBase.cs
- PkcsUtils.cs
- SequentialOutput.cs
- QuaternionValueSerializer.cs
- SqlCacheDependency.cs
- PeerInvitationResponse.cs
- XmlElementList.cs
- AccessibleObject.cs
- PackageRelationship.cs
- ResourceDescriptionAttribute.cs
- QueryStringConverter.cs
- TableAutomationPeer.cs
- VariableQuery.cs
- Dictionary.cs
- ReachObjectContext.cs
- BroadcastEventHelper.cs
- AuthenticodeSignatureInformation.cs
- ParenthesizePropertyNameAttribute.cs
- X509Utils.cs
- SqlDependencyUtils.cs
- SerializationBinder.cs
- ColorConverter.cs
- ResourcesBuildProvider.cs
- ListSourceHelper.cs
- CompositionCommandSet.cs
- WindowsGraphics.cs
- FlowDocumentPaginator.cs
- PropertyCollection.cs
- PropertyMappingExceptionEventArgs.cs
- BinaryKeyIdentifierClause.cs
- ModifierKeysValueSerializer.cs
- TextPointer.cs
- DataRowView.cs
- ExpressionBindings.cs
- NamespaceImport.cs
- CustomError.cs
- CodeArrayIndexerExpression.cs
- StrokeIntersection.cs
- _WinHttpWebProxyDataBuilder.cs
- CroppedBitmap.cs
- DataFormats.cs
- ConnectionsZoneDesigner.cs
- SecurityTokenAuthenticator.cs
- CompilationUnit.cs
- DataGridParentRows.cs
- WebBrowserPermission.cs
- Assembly.cs
- URLEditor.cs
- XmlDataSourceNodeDescriptor.cs
- GroupStyle.cs
- dataprotectionpermission.cs
- EntityCommandCompilationException.cs
- QueryPageSettingsEventArgs.cs
- Pair.cs
- Helpers.cs
- FontWeight.cs
- DefaultHttpHandler.cs
- SAPIEngineTypes.cs
- ClientSettingsStore.cs
- Visual3D.cs
- ElementProxy.cs
- WSTrust.cs
- ModelFactory.cs
- ScriptResourceAttribute.cs
- CatalogZone.cs
- AsyncSerializedWorker.cs
- DesignSurfaceServiceContainer.cs
- XsltSettings.cs