Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / 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
- Exceptions.cs
- PeerToPeerException.cs
- TextTreeInsertElementUndoUnit.cs
- DetailsViewRowCollection.cs
- BrowserCapabilitiesFactoryBase.cs
- ResumeStoryboard.cs
- ReachUIElementCollectionSerializerAsync.cs
- JsonQueryStringConverter.cs
- HtmlTableRow.cs
- SmtpNetworkElement.cs
- MasterPage.cs
- ChannelManager.cs
- ScrollChrome.cs
- HttpWriter.cs
- ChannelManager.cs
- ResourceDescriptionAttribute.cs
- BrowserCapabilitiesFactory.cs
- ScrollChrome.cs
- GPPOINT.cs
- InkPresenterAutomationPeer.cs
- TextSimpleMarkerProperties.cs
- KeyNotFoundException.cs
- Mappings.cs
- NavigationPropertyEmitter.cs
- BookmarkNameHelper.cs
- ConfigurationValidatorBase.cs
- ParamArrayAttribute.cs
- DriveInfo.cs
- SoapAttributeAttribute.cs
- ThemeDictionaryExtension.cs
- Rect.cs
- VirtualizingStackPanel.cs
- XmlDeclaration.cs
- TemplateControlCodeDomTreeGenerator.cs
- DesignTable.cs
- ValidatedControlConverter.cs
- IndexedEnumerable.cs
- PropertyManager.cs
- ItemCollection.cs
- SharingService.cs
- MetadataProperty.cs
- DataGrid.cs
- Policy.cs
- XmlnsPrefixAttribute.cs
- BamlResourceSerializer.cs
- PerformanceCounterPermission.cs
- XsltException.cs
- RootBrowserWindowAutomationPeer.cs
- List.cs
- BitmapEffectCollection.cs
- HandlerMappingMemo.cs
- DataBindingCollectionConverter.cs
- DefaultBinder.cs
- SigningCredentials.cs
- DesignTimeParseData.cs
- ProcessThreadDesigner.cs
- TextBounds.cs
- XsltOutput.cs
- OutputScopeManager.cs
- OSEnvironmentHelper.cs
- SqlDataSourceStatusEventArgs.cs
- FontStretch.cs
- NTAccount.cs
- WCFServiceClientProxyGenerator.cs
- TimeSpanMinutesOrInfiniteConverter.cs
- BufferedGraphics.cs
- Empty.cs
- IdentityNotMappedException.cs
- IfAction.cs
- HostProtectionException.cs
- SQLInt64Storage.cs
- ToolStripGrip.cs
- XPathNavigatorKeyComparer.cs
- VBIdentifierDesigner.xaml.cs
- SqlDependencyUtils.cs
- DbTypeMap.cs
- RoamingStoreFile.cs
- HttpDictionary.cs
- CatalogZoneBase.cs
- CustomAssemblyResolver.cs
- InputLanguageCollection.cs
- Panel.cs
- IndicShape.cs
- XmlReaderSettings.cs
- SimpleNameService.cs
- WindowsFormsHelpers.cs
- InteropAutomationProvider.cs
- DirectoryNotFoundException.cs
- OutputCacheSettings.cs
- WebMessageEncodingBindingElement.cs
- OracleNumber.cs
- FileChangesMonitor.cs
- CounterSampleCalculator.cs
- JsonSerializer.cs
- RecordManager.cs
- ValidatorCompatibilityHelper.cs
- SystemIcmpV6Statistics.cs
- Substitution.cs
- GraphicsPathIterator.cs
- mda.cs