Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / wpf / src / Shared / MS / Utility / ItemMap.cs / 1305600 / 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
- Vector3D.cs
- XmlAutoDetectWriter.cs
- ExtenderControl.cs
- ShaderEffect.cs
- LoginUtil.cs
- recordstatefactory.cs
- GZipStream.cs
- ArrayList.cs
- SetterBase.cs
- MenuBase.cs
- PreProcessInputEventArgs.cs
- adornercollection.cs
- BamlBinaryWriter.cs
- CodeAttachEventStatement.cs
- DataGridViewCellConverter.cs
- CodeObject.cs
- EffectiveValueEntry.cs
- Rule.cs
- ChangeToolStripParentVerb.cs
- Cell.cs
- SchemaTypeEmitter.cs
- StickyNoteContentControl.cs
- ActivityCodeDomSerializationManager.cs
- ImmutableClientRuntime.cs
- OuterGlowBitmapEffect.cs
- Rotation3DAnimationUsingKeyFrames.cs
- RegexTree.cs
- DataTableReaderListener.cs
- PolyBezierSegment.cs
- RealizationDrawingContextWalker.cs
- ISFClipboardData.cs
- MemberCollection.cs
- SoapMessage.cs
- ByteFacetDescriptionElement.cs
- RijndaelManagedTransform.cs
- WebBrowser.cs
- StatementContext.cs
- DiscoveryDocumentSearchPattern.cs
- DashStyles.cs
- RectangleGeometry.cs
- QuestionEventArgs.cs
- BypassElementCollection.cs
- KeyValueSerializer.cs
- LinkClickEvent.cs
- EncryptedData.cs
- RemotingAttributes.cs
- ProcessHostConfigUtils.cs
- FixUpCollection.cs
- WebPartDisplayModeCancelEventArgs.cs
- PipelineModuleStepContainer.cs
- ISessionStateStore.cs
- DataGridViewColumnEventArgs.cs
- COM2TypeInfoProcessor.cs
- MetadataWorkspace.cs
- StringInfo.cs
- PersonalizationAdministration.cs
- SafeEventLogReadHandle.cs
- HierarchicalDataBoundControl.cs
- FreezableCollection.cs
- ColorMap.cs
- WmpBitmapEncoder.cs
- PropertyEmitter.cs
- CodeEventReferenceExpression.cs
- ListViewDataItem.cs
- NumberAction.cs
- SQLDoubleStorage.cs
- HitTestDrawingContextWalker.cs
- IISUnsafeMethods.cs
- ControlCollection.cs
- QilLiteral.cs
- BufferedWebEventProvider.cs
- Utilities.cs
- SecUtil.cs
- EdmMember.cs
- CapacityStreamGeometryContext.cs
- InputProcessorProfiles.cs
- FontStyles.cs
- StorageEndPropertyMapping.cs
- SqlDataSourceSelectingEventArgs.cs
- cookiecollection.cs
- SafeFileMappingHandle.cs
- ClientType.cs
- OLEDB_Util.cs
- ResourcesChangeInfo.cs
- RunInstallerAttribute.cs
- ForeignConstraint.cs
- CapiHashAlgorithm.cs
- RegexCompilationInfo.cs
- remotingproxy.cs
- EncoderNLS.cs
- HtmlInputImage.cs
- WebPartEditorCancelVerb.cs
- DiscoveryDocumentLinksPattern.cs
- ParallelTimeline.cs
- DataGridViewCellConverter.cs
- SqlTypesSchemaImporter.cs
- LateBoundBitmapDecoder.cs
- Brush.cs
- HostingEnvironmentException.cs
- CodeExpressionCollection.cs