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
- SemanticKeyElement.cs
- CompareInfo.cs
- OdbcDataAdapter.cs
- AssemblyLoader.cs
- ConstraintEnumerator.cs
- FileInfo.cs
- XPathBinder.cs
- DbConnectionPoolGroup.cs
- XPathPatternBuilder.cs
- DataGridViewHitTestInfo.cs
- FlowchartDesigner.xaml.cs
- StringUtil.cs
- MailMessageEventArgs.cs
- Regex.cs
- StatusBarPanelClickEvent.cs
- contentDescriptor.cs
- CompositeCollection.cs
- CodeParameterDeclarationExpression.cs
- ComplexTypeEmitter.cs
- CodeSubDirectory.cs
- SecurityNegotiationException.cs
- StateMachineWorkflowInstance.cs
- ViewBox.cs
- DataGridViewColumnDividerDoubleClickEventArgs.cs
- XmlCharCheckingReader.cs
- XmlChildEnumerator.cs
- MediaCommands.cs
- FamilyMapCollection.cs
- ReadOnlyMetadataCollection.cs
- SHA512.cs
- LocalClientSecuritySettingsElement.cs
- Array.cs
- ListItem.cs
- XdrBuilder.cs
- WhiteSpaceTrimStringConverter.cs
- RawKeyboardInputReport.cs
- CompiledELinqQueryState.cs
- CodeConstructor.cs
- MSG.cs
- SetterBase.cs
- DataRelationCollection.cs
- StatusBar.cs
- EditingScopeUndoUnit.cs
- SizeValueSerializer.cs
- SoapObjectInfo.cs
- CreatingCookieEventArgs.cs
- FamilyTypeface.cs
- SchemaSetCompiler.cs
- controlskin.cs
- DbExpressionVisitor_TResultType.cs
- MappingItemCollection.cs
- ChtmlLinkAdapter.cs
- ResourceDescriptionAttribute.cs
- DataGridViewLayoutData.cs
- WsdlExporter.cs
- ResourcePermissionBase.cs
- AuthenticodeSignatureInformation.cs
- QueueAccessMode.cs
- SrgsToken.cs
- MetadataCacheItem.cs
- SqlAggregateChecker.cs
- FontCacheUtil.cs
- ConsoleKeyInfo.cs
- HtmlPhoneCallAdapter.cs
- DataSourceComponent.cs
- Block.cs
- SQLMoney.cs
- ProfileModule.cs
- BufferBuilder.cs
- HtmlTableCell.cs
- SqlInfoMessageEvent.cs
- SignedXml.cs
- XsltException.cs
- WebInvokeAttribute.cs
- OverflowException.cs
- InstanceDataCollection.cs
- RequestTimeoutManager.cs
- ContractValidationHelper.cs
- Matrix.cs
- OdbcEnvironment.cs
- RemoveStoryboard.cs
- Parser.cs
- Timeline.cs
- TextOnlyOutput.cs
- CompilerErrorCollection.cs
- ReadOnlyPropertyMetadata.cs
- CodeSnippetCompileUnit.cs
- ZipIOExtraFieldPaddingElement.cs
- UriSectionReader.cs
- Set.cs
- ArrayList.cs
- followingquery.cs
- AsyncOperationManager.cs
- StylusOverProperty.cs
- SystemIPv6InterfaceProperties.cs
- OpCodes.cs
- WorkflowMessageEventHandler.cs
- BulletChrome.cs
- FaultHandlingFilter.cs
- EdgeModeValidation.cs