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
- DbConnectionHelper.cs
- TransactionState.cs
- DurableInstanceProvider.cs
- updateconfighost.cs
- TrackingParameters.cs
- RoleGroupCollection.cs
- PenContexts.cs
- RowUpdatedEventArgs.cs
- EndpointConfigContainer.cs
- RadialGradientBrush.cs
- DeploymentSection.cs
- InkCanvasAutomationPeer.cs
- SecureEnvironment.cs
- CodePageEncoding.cs
- FormsIdentity.cs
- ConnectionInterfaceCollection.cs
- QilGenerator.cs
- ConsumerConnectionPointCollection.cs
- HwndProxyElementProvider.cs
- MetadataProperty.cs
- XMLSyntaxException.cs
- DetailsViewAutoFormat.cs
- OrderByLifter.cs
- EpmHelper.cs
- RadioButton.cs
- _LazyAsyncResult.cs
- CorrelationToken.cs
- Application.cs
- DataServiceEntityAttribute.cs
- NetPipeSection.cs
- ErrorHandlingAcceptor.cs
- SHA512.cs
- ClientApiGenerator.cs
- XmlSortKeyAccumulator.cs
- ReferenceConverter.cs
- Barrier.cs
- ConfigurationPermission.cs
- HtmlEmptyTagControlBuilder.cs
- XamlVector3DCollectionSerializer.cs
- DrawingBrush.cs
- IntSecurity.cs
- GridViewRowEventArgs.cs
- MsmqReceiveParameters.cs
- DataGridTextColumn.cs
- WebPartsPersonalizationAuthorization.cs
- MatrixCamera.cs
- PageSetupDialog.cs
- AutoResizedEvent.cs
- ListViewCommandEventArgs.cs
- LogLogRecordHeader.cs
- TraceListeners.cs
- SoapReflectionImporter.cs
- Int32Converter.cs
- NavigationProperty.cs
- MessageBox.cs
- xmlfixedPageInfo.cs
- VirtualStackFrame.cs
- BaseServiceProvider.cs
- LinkButton.cs
- SQLDateTime.cs
- SqlResolver.cs
- OdbcUtils.cs
- CollectionViewGroup.cs
- MetadataExchangeClient.cs
- FormView.cs
- CustomAssemblyResolver.cs
- ImageSourceConverter.cs
- PageRequestManager.cs
- SiteMap.cs
- XmlQualifiedName.cs
- UrlEncodedParameterWriter.cs
- ImageAutomationPeer.cs
- XAMLParseException.cs
- LinearGradientBrush.cs
- StructuredProperty.cs
- XmlTypeAttribute.cs
- CompModSwitches.cs
- TabRenderer.cs
- HitTestParameters3D.cs
- UnauthorizedAccessException.cs
- HtmlInputCheckBox.cs
- OledbConnectionStringbuilder.cs
- BmpBitmapEncoder.cs
- SchemaElementLookUpTable.cs
- FileSystemInfo.cs
- RoutingBehavior.cs
- FixedDocument.cs
- PolicyFactory.cs
- TypeDescriptor.cs
- RepeatButton.cs
- Helper.cs
- XmlWrappingWriter.cs
- DocumentViewerHelper.cs
- PhoneCallDesigner.cs
- DummyDataSource.cs
- ErrorFormatterPage.cs
- PathStreamGeometryContext.cs
- SqlDataSourceCache.cs
- XamlHttpHandlerFactory.cs
- XhtmlCssHandler.cs