Code:
/ 4.0 / 4.0 / untmp / 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.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- CollectionAdapters.cs
- SamlDoNotCacheCondition.cs
- WebResourceAttribute.cs
- StorageTypeMapping.cs
- SystemKeyConverter.cs
- AffineTransform3D.cs
- Compiler.cs
- Message.cs
- WindowsSidIdentity.cs
- AsyncStreamReader.cs
- ParserExtension.cs
- Section.cs
- FilterEventArgs.cs
- HttpConfigurationContext.cs
- WindowsNonControl.cs
- DesignerValidatorAdapter.cs
- HttpResponseInternalBase.cs
- SpecialFolderEnumConverter.cs
- ResolveCriteria11.cs
- CodeTypeDeclarationCollection.cs
- UniqueTransportManagerRegistration.cs
- SizeAnimation.cs
- CharKeyFrameCollection.cs
- AutomationPropertyChangedEventArgs.cs
- TraceSection.cs
- BypassElement.cs
- XmlNodeChangedEventArgs.cs
- CheckBox.cs
- ItemsControl.cs
- EventArgs.cs
- ButtonBase.cs
- StagingAreaInputItem.cs
- WrappingXamlSchemaContext.cs
- DesignerVerb.cs
- RetrieveVirtualItemEventArgs.cs
- CollectionCodeDomSerializer.cs
- TrustManagerPromptUI.cs
- CounterCreationDataCollection.cs
- _ListenerResponseStream.cs
- TreeViewItemAutomationPeer.cs
- NamespaceList.cs
- TimeSpanOrInfiniteConverter.cs
- AutomationElementCollection.cs
- EnumerationRangeValidationUtil.cs
- GroupByQueryOperator.cs
- MembershipPasswordException.cs
- ClonableStack.cs
- BamlResourceContent.cs
- PermissionListSet.cs
- HwndSubclass.cs
- IsolatedStorageFilePermission.cs
- EditorZoneBase.cs
- AsyncStreamReader.cs
- DataBinder.cs
- DataViewManagerListItemTypeDescriptor.cs
- DateTimeConverter2.cs
- Stylesheet.cs
- RenameRuleObjectDialog.cs
- SqlDataSource.cs
- EncryptedPackageFilter.cs
- httpapplicationstate.cs
- SafeHandles.cs
- Queue.cs
- EntitySetBaseCollection.cs
- QuotedStringWriteStateInfo.cs
- X509Certificate2.cs
- TagMapCollection.cs
- NopReturnReader.cs
- EntityClassGenerator.cs
- Polyline.cs
- exports.cs
- HasRunnableWorkflowEvent.cs
- odbcmetadatacollectionnames.cs
- EditBehavior.cs
- WebConfigurationHostFileChange.cs
- ConfigurationManagerInternalFactory.cs
- BypassElementCollection.cs
- controlskin.cs
- CodeAccessPermission.cs
- PreviewPageInfo.cs
- XsltSettings.cs
- DBSchemaTable.cs
- Avt.cs
- TimelineGroup.cs
- XmlLanguage.cs
- DependencyProperty.cs
- DocumentSequenceHighlightLayer.cs
- RectAnimationUsingKeyFrames.cs
- VirtualDirectoryMappingCollection.cs
- NewExpression.cs
- InheritanceContextHelper.cs
- ItemMap.cs
- Hex.cs
- InteropEnvironment.cs
- WebBrowserNavigatedEventHandler.cs
- DataGridViewLinkColumn.cs
- controlskin.cs
- CollectionViewProxy.cs
- PropertyEntry.cs
- RawStylusInputCustomDataList.cs