Code:
/ 4.0 / 4.0 / 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. 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
- RevocationPoint.cs
- MbpInfo.cs
- _NegoStream.cs
- SafeCancelMibChangeNotify.cs
- SessionPageStatePersister.cs
- ColorTransform.cs
- ReversePositionQuery.cs
- PropertyMap.cs
- VBCodeProvider.cs
- SurrogateSelector.cs
- MembershipSection.cs
- StorageSetMapping.cs
- QueryInterceptorAttribute.cs
- ProcessHostServerConfig.cs
- ButtonPopupAdapter.cs
- ProcessModule.cs
- StringUtil.cs
- SqlCharStream.cs
- XmlAutoDetectWriter.cs
- RuntimeVariableList.cs
- DispatcherHookEventArgs.cs
- NavigationProgressEventArgs.cs
- DataGridViewUtilities.cs
- Focus.cs
- ColorEditor.cs
- ReceiveDesigner.xaml.cs
- CodeDOMUtility.cs
- GZipUtils.cs
- GenericFlowSwitchHelper.cs
- AbandonedMutexException.cs
- UserValidatedEventArgs.cs
- RotateTransform.cs
- AdornedElementPlaceholder.cs
- Highlights.cs
- HScrollProperties.cs
- Type.cs
- SystemResourceKey.cs
- OleDbSchemaGuid.cs
- RoleManagerEventArgs.cs
- PeerTransportSecurityElement.cs
- XmlSchemaAttribute.cs
- Certificate.cs
- BaseTemplateCodeDomTreeGenerator.cs
- SqlDataRecord.cs
- DelegateSerializationHolder.cs
- DataGridViewCellCollection.cs
- PackageRelationshipSelector.cs
- FileSecurity.cs
- ProjectionQueryOptionExpression.cs
- PreProcessInputEventArgs.cs
- embossbitmapeffect.cs
- SerialStream.cs
- RegexGroupCollection.cs
- DeleteBookmarkScope.cs
- SizeChangedInfo.cs
- ListViewSelectEventArgs.cs
- AudioException.cs
- brushes.cs
- HttpContextServiceHost.cs
- OleDbRowUpdatingEvent.cs
- SubtreeProcessor.cs
- RuntimeResourceSet.cs
- PenContexts.cs
- Icon.cs
- DragCompletedEventArgs.cs
- TypeConverter.cs
- ConnectionPoolManager.cs
- webproxy.cs
- SqlParameterizer.cs
- Utils.cs
- WebServiceFault.cs
- NameTable.cs
- SmiRequestExecutor.cs
- AxDesigner.cs
- TextShapeableCharacters.cs
- EventSetterHandlerConverter.cs
- ListViewCancelEventArgs.cs
- PathStreamGeometryContext.cs
- BlockUIContainer.cs
- CacheMemory.cs
- FrameSecurityDescriptor.cs
- ServerProtocol.cs
- UserNameServiceElement.cs
- XmlSchemaCollection.cs
- FtpRequestCacheValidator.cs
- TreeNodeCollection.cs
- Privilege.cs
- OLEDB_Enum.cs
- CalendarDateRange.cs
- HttpCapabilitiesSectionHandler.cs
- DataTableExtensions.cs
- DataMisalignedException.cs
- ClientTargetSection.cs
- SqlReferenceCollection.cs
- Int16Animation.cs
- SamlAdvice.cs
- ZoomingMessageFilter.cs
- XmlSortKeyAccumulator.cs
- Odbc32.cs
- ChildrenQuery.cs