Code:
/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / wpf / src / Shared / MS / Utility / ItemMap.cs / 1 / ItemMap.cs
using System; using System.Collections; using System.Diagnostics; namespace MS.Utility { // // ItemStructMap// // Disable warnings about fields never being assigned to // This struct is designed to function with its fields starting at // their default values and without the need of surfacing a constructor // other than the deafult #pragma warning disable 649 internal struct ItemStructMap { public int EnsureEntry(int key) { int index = Search(key); if (index < 0) { // Not found, add Entry // Create initial capacity, if necessary if (Entries == null) { Entries = new Entry[SearchTypeThreshold]; } // Convert not-found index to insertion point index = ~index; Entry[] destEntries = Entries; // Increase capacity, if necessary if ((Count + 1) > Entries.Length) { destEntries = new Entry[Entries.Length * 2]; // Initialize start of new array Array.Copy(Entries, 0, destEntries, 0, index); } // Shift entries to make room for new key at provided insertion point Array.Copy(Entries, index, destEntries, index + 1, Count - index); // Ensure Source and Destination arrays are the same Entries = destEntries; // Clear new entry Entries[index] = EmptyEntry; // Set Entries[index].Key = key; Count++; } return index; } public int Search(int key) { int keyPv = Int32.MaxValue; int iPv = 0; // Use fastest search based on size if (Count > SearchTypeThreshold) { // Binary Search int iLo = 0; int iHi = Count - 1; while (iLo <= iHi) { iPv = (iHi + iLo) / 2; keyPv = Entries[iPv].Key; if (key == keyPv) { return iPv; } if (key < keyPv) { iHi = iPv - 1; } else { iLo = iPv + 1; } } } else { // Linear search for (int i = 0; i < Count; i++) { iPv = i; keyPv = Entries[iPv].Key; if (key == keyPv) { return iPv; } if (key < keyPv) { break; } } } // iPv and keyPv will match and have the last pivot check // Return a negative value whose bitwise compliment // is this index of the first Entry that is greater // than the key passed in (sorted insertion point) if (key > keyPv) { iPv++; } return ~iPv; } private const int SearchTypeThreshold = 4; public Entry[] Entries; public int Count; public struct Entry { public int Key; public T Value; } private static Entry EmptyEntry; } #pragma warning restore 649 } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved. using System; using System.Collections; using System.Diagnostics; namespace MS.Utility { // // ItemStructMap // // Disable warnings about fields never being assigned to // This struct is designed to function with its fields starting at // their default values and without the need of surfacing a constructor // other than the deafult #pragma warning disable 649 internal struct ItemStructMap { public int EnsureEntry(int key) { int index = Search(key); if (index < 0) { // Not found, add Entry // Create initial capacity, if necessary if (Entries == null) { Entries = new Entry[SearchTypeThreshold]; } // Convert not-found index to insertion point index = ~index; Entry[] destEntries = Entries; // Increase capacity, if necessary if ((Count + 1) > Entries.Length) { destEntries = new Entry[Entries.Length * 2]; // Initialize start of new array Array.Copy(Entries, 0, destEntries, 0, index); } // Shift entries to make room for new key at provided insertion point Array.Copy(Entries, index, destEntries, index + 1, Count - index); // Ensure Source and Destination arrays are the same Entries = destEntries; // Clear new entry Entries[index] = EmptyEntry; // Set Entries[index].Key = key; Count++; } return index; } public int Search(int key) { int keyPv = Int32.MaxValue; int iPv = 0; // Use fastest search based on size if (Count > SearchTypeThreshold) { // Binary Search int iLo = 0; int iHi = Count - 1; while (iLo <= iHi) { iPv = (iHi + iLo) / 2; keyPv = Entries[iPv].Key; if (key == keyPv) { return iPv; } if (key < keyPv) { iHi = iPv - 1; } else { iLo = iPv + 1; } } } else { // Linear search for (int i = 0; i < Count; i++) { iPv = i; keyPv = Entries[iPv].Key; if (key == keyPv) { return iPv; } if (key < keyPv) { break; } } } // iPv and keyPv will match and have the last pivot check // Return a negative value whose bitwise compliment // is this index of the first Entry that is greater // than the key passed in (sorted insertion point) if (key > keyPv) { iPv++; } return ~iPv; } private const int SearchTypeThreshold = 4; public Entry[] Entries; public int Count; public struct Entry { public int Key; public T Value; } private static Entry EmptyEntry; } #pragma warning restore 649 } // 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
- DbMetaDataColumnNames.cs
- TemplateBuilder.cs
- SplashScreenNativeMethods.cs
- XmlSchema.cs
- SchemaTableOptionalColumn.cs
- ConfigurationValidatorAttribute.cs
- ImpersonateTokenRef.cs
- WSDualHttpBindingCollectionElement.cs
- WorkflowDebuggerSteppingAttribute.cs
- BooleanKeyFrameCollection.cs
- CellTreeSimplifier.cs
- SerializationStore.cs
- SmiMetaData.cs
- WebPartEventArgs.cs
- PageRanges.cs
- Rotation3D.cs
- TCPClient.cs
- TableLayoutSettingsTypeConverter.cs
- SemanticResultKey.cs
- _NtlmClient.cs
- Directory.cs
- CLSCompliantAttribute.cs
- DataGridViewAdvancedBorderStyle.cs
- VerticalAlignConverter.cs
- DbMetaDataCollectionNames.cs
- DeviceSpecificChoiceCollection.cs
- AuthenticationSection.cs
- JoinGraph.cs
- _FixedSizeReader.cs
- OracleBFile.cs
- DiagnosticTraceSource.cs
- ArgumentNullException.cs
- MergeExecutor.cs
- InvariantComparer.cs
- DataKeyPropertyAttribute.cs
- PeerCustomResolverElement.cs
- SortableBindingList.cs
- ArrayTypeMismatchException.cs
- SQLConvert.cs
- Stroke2.cs
- SchemaInfo.cs
- Deserializer.cs
- SiteMapNodeItem.cs
- QuaternionAnimationBase.cs
- Reference.cs
- TextRunProperties.cs
- InvalidEnumArgumentException.cs
- TdsParserHelperClasses.cs
- StorageInfo.cs
- PointAnimationUsingPath.cs
- MemberAccessException.cs
- ExtendedPropertyCollection.cs
- AppliedDeviceFiltersDialog.cs
- SafeReversePInvokeHandle.cs
- ResourcePermissionBase.cs
- FaultContractAttribute.cs
- DataGridItemCollection.cs
- TransactedBatchContext.cs
- WsatAdminException.cs
- TreeViewCancelEvent.cs
- DoubleLink.cs
- ExceptionHandlerDesigner.cs
- GeometryDrawing.cs
- CompressStream.cs
- CategoryValueConverter.cs
- ClaimSet.cs
- ObjectQueryProvider.cs
- ReadContentAsBinaryHelper.cs
- UnlockCardRequest.cs
- TabletCollection.cs
- ConfigurationValidatorBase.cs
- RewritingValidator.cs
- UniqueID.cs
- TablePatternIdentifiers.cs
- ToolBarOverflowPanel.cs
- DynamicPhysicalDiscoSearcher.cs
- TripleDES.cs
- DeferredReference.cs
- Table.cs
- DbgUtil.cs
- Vector3DAnimationBase.cs
- UnsafeNativeMethods.cs
- DirectoryNotFoundException.cs
- MutexSecurity.cs
- AnimationClock.cs
- SoapObjectReader.cs
- PrintDocument.cs
- DBDataPermissionAttribute.cs
- AttributeCollection.cs
- OSFeature.cs
- Native.cs
- PipeSecurity.cs
- Label.cs
- FactoryGenerator.cs
- ParameterEditorUserControl.cs
- Highlights.cs
- XmlSerializationGeneratedCode.cs
- InputProcessorProfilesLoader.cs
- InvalidWMPVersionException.cs
- SendSecurityHeaderElementContainer.cs