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
- DataGridViewAccessibleObject.cs
- TextFormatter.cs
- StandardCommands.cs
- CommonObjectSecurity.cs
- XmlNamespaceManager.cs
- CollectionsUtil.cs
- SourceInterpreter.cs
- ContextItem.cs
- WebZone.cs
- ViewPort3D.cs
- PointCollection.cs
- RelationshipEndCollection.cs
- IApplicationTrustManager.cs
- ToolboxBitmapAttribute.cs
- WhitespaceRuleLookup.cs
- WorkflowDispatchContext.cs
- AuthenticationManager.cs
- BufferAllocator.cs
- ToolStripGripRenderEventArgs.cs
- PrintDialog.cs
- ObjectContext.cs
- PeerApplication.cs
- ServiceDocument.cs
- PersonalizationProviderHelper.cs
- RotateTransform.cs
- DashStyle.cs
- WindowsGraphics2.cs
- ListControl.cs
- MyContact.cs
- DataRowView.cs
- WebReference.cs
- ContextInformation.cs
- WS2007HttpBindingCollectionElement.cs
- util.cs
- XhtmlBasicImageAdapter.cs
- SchemaMerger.cs
- XpsFontSubsetter.cs
- CoreSwitches.cs
- FilterableAttribute.cs
- SystemIPv6InterfaceProperties.cs
- BinaryNegotiation.cs
- PrimarySelectionGlyph.cs
- BindingMemberInfo.cs
- RegexRunnerFactory.cs
- CompositeScriptReference.cs
- ConnectorEditor.cs
- Cursor.cs
- DelegateHelpers.cs
- PackWebRequest.cs
- Block.cs
- AttachmentService.cs
- IIS7UserPrincipal.cs
- TableItemStyle.cs
- Avt.cs
- ResourceSetExpression.cs
- PipeSecurity.cs
- JpegBitmapDecoder.cs
- AutoResizedEvent.cs
- XmlEncodedRawTextWriter.cs
- BatchParser.cs
- Rotation3D.cs
- CharacterBufferReference.cs
- CodeConditionStatement.cs
- JsonWriterDelegator.cs
- DesignerCategoryAttribute.cs
- InputBinder.cs
- CompilerResults.cs
- ButtonPopupAdapter.cs
- QuotedPrintableStream.cs
- CompositeControl.cs
- PropertyInformationCollection.cs
- CellConstantDomain.cs
- SqlCommandBuilder.cs
- SingleTagSectionHandler.cs
- Int32Rect.cs
- SqlFunctions.cs
- CustomSignedXml.cs
- LocationReferenceValue.cs
- XmlQualifiedNameTest.cs
- SvcMapFileLoader.cs
- QuinticEase.cs
- MessagePartProtectionMode.cs
- SqlGatherConsumedAliases.cs
- SystemSounds.cs
- SendKeys.cs
- HtmlFormAdapter.cs
- RequestResizeEvent.cs
- TypeResolvingOptions.cs
- PointCollection.cs
- ExclusiveHandleList.cs
- WebPartExportVerb.cs
- NotSupportedException.cs
- RotateTransform.cs
- WebEncodingValidatorAttribute.cs
- WorkflowRuntimeServiceElement.cs
- remotingproxy.cs
- SizeAnimation.cs
- SwitchExpression.cs
- UIElement.cs
- LogFlushAsyncResult.cs