Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / Core / System / Linq / Parallel / QueryOperators / Binary / ExceptQueryOperator.cs / 1305376 / ExceptQueryOperator.cs
// ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ // // ExceptQueryOperator.cs // //[....] // // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- using System.Collections.Generic; using System.Diagnostics.Contracts; using System.Threading; namespace System.Linq.Parallel { ////// Operator that yields the elements from the first data source that aren't in the second. /// This is known as the set relative complement, i.e. left - right. /// ///internal sealed class ExceptQueryOperator : BinaryQueryOperator { private readonly IEqualityComparer m_comparer; // An equality comparer. //---------------------------------------------------------------------------------------- // Constructs a new set except operator. // internal ExceptQueryOperator(ParallelQuery left, ParallelQuery right, IEqualityComparer comparer) :base(left, right) { Contract.Assert(left != null && right != null, "child data sources cannot be null"); m_comparer = comparer; m_outputOrdered = LeftChild.OutputOrdered; SetOrdinalIndex(OrdinalIndexState.Shuffled); } internal override QueryResults Open( QuerySettings settings, bool preferStriping) { // We just open our child operators, left and then right. Do not propagate the preferStriping value, but // instead explicitly set it to false. Regardless of whether the parent prefers striping or range // partitioning, the output will be hash-partititioned. QueryResults leftChildResults = LeftChild.Open(settings, false); QueryResults rightChildResults = RightChild.Open(settings, false); return new BinaryQueryOperatorResults(leftChildResults, rightChildResults, this, settings, false); } public override void WrapPartitionedStream ( PartitionedStream leftStream, PartitionedStream rightStream, IPartitionedStreamRecipient outputRecipient, bool preferStriping, QuerySettings settings) { Contract.Assert(leftStream.PartitionCount == rightStream.PartitionCount); if (OutputOrdered) { WrapPartitionedStreamHelper ( ExchangeUtilities.HashRepartitionOrdered ( leftStream, null, null, m_comparer, settings.CancellationState.MergedCancellationToken), rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken); } else { WrapPartitionedStreamHelper ( ExchangeUtilities.HashRepartition ( leftStream, null, null, m_comparer, settings.CancellationState.MergedCancellationToken), rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken); } } //--------------------------------------------------------------------------------------- // This is a helper method. WrapPartitionedStream decides what type TLeftKey is going // to be, and then call this method with that key as a generic parameter. // private void WrapPartitionedStreamHelper ( PartitionedStream , TLeftKey> leftHashStream, PartitionedStream rightPartitionedStream, IPartitionedStreamRecipient outputRecipient, CancellationToken cancellationToken) { int partitionCount = leftHashStream.PartitionCount; PartitionedStream , int> rightHashStream = ExchangeUtilities.HashRepartition ( rightPartitionedStream, null, null, m_comparer, cancellationToken); PartitionedStream outputStream = new PartitionedStream (partitionCount, leftHashStream.KeyComparer, OrdinalIndexState.Shuffled); for (int i = 0; i < partitionCount; i++) { if (OutputOrdered) { outputStream[i] = new OrderedExceptQueryOperatorEnumerator ( leftHashStream[i], rightHashStream[i], m_comparer, leftHashStream.KeyComparer, cancellationToken); } else { outputStream[i] = (QueryOperatorEnumerator )(object) new ExceptQueryOperatorEnumerator (leftHashStream[i], rightHashStream[i], m_comparer, cancellationToken); } } outputRecipient.Receive(outputStream); } //--------------------------------------------------------------------------------------- // Returns an enumerable that represents the query executing sequentially. // internal override IEnumerable AsSequentialQuery(CancellationToken token) { IEnumerable wrappedLeftChild = CancellableEnumerable.Wrap(LeftChild.AsSequentialQuery(token), token); IEnumerable wrappedRightChild = CancellableEnumerable.Wrap(RightChild.AsSequentialQuery(token), token); return wrappedLeftChild.Except(wrappedRightChild, m_comparer); } //--------------------------------------------------------------------------------------- // Whether this operator performs a premature merge. // internal override bool LimitsParallelism { get { return false; } } //---------------------------------------------------------------------------------------- // This enumerator calculates the distinct set incrementally. It does this by maintaining // a history -- in the form of a set -- of all data already seen. It then only returns // elements that have not yet been seen. // class ExceptQueryOperatorEnumerator : QueryOperatorEnumerator { private QueryOperatorEnumerator , TLeftKey> m_leftSource; // Left data source. private QueryOperatorEnumerator , int> m_rightSource; // Right data source. private IEqualityComparer m_comparer; // A comparer used for equality checks/hash-coding. private Set m_hashLookup; // The hash lookup, used to produce the distinct set. private CancellationToken m_cancellationToken; private Shared m_outputLoopCount; //--------------------------------------------------------------------------------------- // Instantiates a new except query operator enumerator. // internal ExceptQueryOperatorEnumerator( QueryOperatorEnumerator , TLeftKey> leftSource, QueryOperatorEnumerator , int> rightSource, IEqualityComparer comparer, CancellationToken cancellationToken) { Contract.Assert(leftSource != null); Contract.Assert(rightSource != null); m_leftSource = leftSource; m_rightSource = rightSource; m_comparer = comparer; m_cancellationToken = cancellationToken; } //---------------------------------------------------------------------------------------- // Walks the two data sources, left and then right, to produce the distinct set // internal override bool MoveNext(ref TInputOutput currentElement, ref int currentKey) { Contract.Assert(m_leftSource != null); Contract.Assert(m_rightSource != null); // Build the set out of the left data source, if we haven't already. if (m_hashLookup == null) { m_outputLoopCount = new Shared (0); // @ m_hashLookup = new Set (m_comparer); Pair rightElement = default(Pair ); int rightKeyUnused = default(int); int i = 0; while (m_rightSource.MoveNext(ref rightElement, ref rightKeyUnused)) { if ((i++ & CancellationState.POLL_INTERVAL) == 0) CancellationState.ThrowIfCanceled(m_cancellationToken); m_hashLookup.Add(rightElement.First); } } // Now iterate over the right data source, looking for matches. Pair leftElement = default(Pair ); TLeftKey leftKeyUnused = default(TLeftKey); while (m_leftSource.MoveNext(ref leftElement, ref leftKeyUnused)) { if ((m_outputLoopCount.Value++ & CancellationState.POLL_INTERVAL) == 0) CancellationState.ThrowIfCanceled(m_cancellationToken); if (m_hashLookup.Add(leftElement.First)) { // This element has never been seen. Return it. currentElement = leftElement.First; #if DEBUG currentKey = unchecked((int)0xdeadbeef); #endif return true; } } return false; } protected override void Dispose(bool disposing) { Contract.Assert(m_leftSource != null && m_rightSource != null); m_leftSource.Dispose(); m_rightSource.Dispose(); } } class OrderedExceptQueryOperatorEnumerator : QueryOperatorEnumerator { private QueryOperatorEnumerator , TLeftKey> m_leftSource; // Left data source. private QueryOperatorEnumerator , int> m_rightSource; // Right data source. private IEqualityComparer m_comparer; // A comparer used for equality checks/hash-coding. private IComparer m_leftKeyComparer; // A comparer for order keys. private IEnumerator , Pair >> m_outputEnumerator; // The enumerator output elements + order keys. private CancellationToken m_cancellationToken; //---------------------------------------------------------------------------------------- // Instantiates a new except query operator enumerator. // internal OrderedExceptQueryOperatorEnumerator( QueryOperatorEnumerator , TLeftKey> leftSource, QueryOperatorEnumerator , int> rightSource, IEqualityComparer comparer, IComparer leftKeyComparer, CancellationToken cancellationToken) { Contract.Assert(leftSource != null); Contract.Assert(rightSource != null); m_leftSource = leftSource; m_rightSource = rightSource; m_comparer = comparer; m_leftKeyComparer = leftKeyComparer; m_cancellationToken = cancellationToken; } //--------------------------------------------------------------------------------------- // Walks the two data sources, left and then right, to produce the distinct set // internal override bool MoveNext(ref TInputOutput currentElement, ref TLeftKey currentKey) { Contract.Assert(m_leftSource != null); Contract.Assert(m_rightSource != null); // Build the set out of the left data source, if we haven't already. if (m_outputEnumerator == null) { // @ Set rightLookup = new Set (m_comparer); Pair rightElement = default(Pair ); int rightKeyUnused = default(int); int i=0; while (m_rightSource.MoveNext(ref rightElement, ref rightKeyUnused)) { if ((i++ & CancellationState.POLL_INTERVAL) == 0) CancellationState.ThrowIfCanceled(m_cancellationToken); rightLookup.Add(rightElement.First); } var leftLookup = new Dictionary , Pair >( new WrapperEqualityComparer (m_comparer)); Pair leftElement = default(Pair ); TLeftKey leftKey = default(TLeftKey); while (m_leftSource.MoveNext(ref leftElement, ref leftKey)) { if ((i++ & CancellationState.POLL_INTERVAL) == 0) CancellationState.ThrowIfCanceled(m_cancellationToken); if (rightLookup.Contains(leftElement.First)) { continue; } Pair oldEntry; Wrapper wrappedLeftElement = new Wrapper (leftElement.First); if (!leftLookup.TryGetValue(wrappedLeftElement, out oldEntry) || m_leftKeyComparer.Compare(leftKey, oldEntry.Second) < 0) { // For each "elem" value, we store the smallest key, and the element value that had that key. // Note that even though two element values are "equal" according to the EqualityComparer, // we still cannot choose arbitrarily which of the two to yield. leftLookup[wrappedLeftElement] = new Pair (leftElement.First, leftKey); } } m_outputEnumerator = leftLookup.GetEnumerator(); } if (m_outputEnumerator.MoveNext()) { Pair currentPair = m_outputEnumerator.Current.Value; currentElement = currentPair.First; currentKey = currentPair.Second; return true; } return false; } protected override void Dispose(bool disposing) { Contract.Assert(m_leftSource != null && m_rightSource != null); m_leftSource.Dispose(); m_rightSource.Dispose(); } } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ // // ExceptQueryOperator.cs // // [....] // // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- using System.Collections.Generic; using System.Diagnostics.Contracts; using System.Threading; namespace System.Linq.Parallel { ////// Operator that yields the elements from the first data source that aren't in the second. /// This is known as the set relative complement, i.e. left - right. /// ///internal sealed class ExceptQueryOperator : BinaryQueryOperator { private readonly IEqualityComparer m_comparer; // An equality comparer. //---------------------------------------------------------------------------------------- // Constructs a new set except operator. // internal ExceptQueryOperator(ParallelQuery left, ParallelQuery right, IEqualityComparer comparer) :base(left, right) { Contract.Assert(left != null && right != null, "child data sources cannot be null"); m_comparer = comparer; m_outputOrdered = LeftChild.OutputOrdered; SetOrdinalIndex(OrdinalIndexState.Shuffled); } internal override QueryResults Open( QuerySettings settings, bool preferStriping) { // We just open our child operators, left and then right. Do not propagate the preferStriping value, but // instead explicitly set it to false. Regardless of whether the parent prefers striping or range // partitioning, the output will be hash-partititioned. QueryResults leftChildResults = LeftChild.Open(settings, false); QueryResults rightChildResults = RightChild.Open(settings, false); return new BinaryQueryOperatorResults(leftChildResults, rightChildResults, this, settings, false); } public override void WrapPartitionedStream ( PartitionedStream leftStream, PartitionedStream rightStream, IPartitionedStreamRecipient outputRecipient, bool preferStriping, QuerySettings settings) { Contract.Assert(leftStream.PartitionCount == rightStream.PartitionCount); if (OutputOrdered) { WrapPartitionedStreamHelper ( ExchangeUtilities.HashRepartitionOrdered ( leftStream, null, null, m_comparer, settings.CancellationState.MergedCancellationToken), rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken); } else { WrapPartitionedStreamHelper ( ExchangeUtilities.HashRepartition ( leftStream, null, null, m_comparer, settings.CancellationState.MergedCancellationToken), rightStream, outputRecipient, settings.CancellationState.MergedCancellationToken); } } //--------------------------------------------------------------------------------------- // This is a helper method. WrapPartitionedStream decides what type TLeftKey is going // to be, and then call this method with that key as a generic parameter. // private void WrapPartitionedStreamHelper ( PartitionedStream , TLeftKey> leftHashStream, PartitionedStream rightPartitionedStream, IPartitionedStreamRecipient outputRecipient, CancellationToken cancellationToken) { int partitionCount = leftHashStream.PartitionCount; PartitionedStream , int> rightHashStream = ExchangeUtilities.HashRepartition ( rightPartitionedStream, null, null, m_comparer, cancellationToken); PartitionedStream outputStream = new PartitionedStream (partitionCount, leftHashStream.KeyComparer, OrdinalIndexState.Shuffled); for (int i = 0; i < partitionCount; i++) { if (OutputOrdered) { outputStream[i] = new OrderedExceptQueryOperatorEnumerator ( leftHashStream[i], rightHashStream[i], m_comparer, leftHashStream.KeyComparer, cancellationToken); } else { outputStream[i] = (QueryOperatorEnumerator )(object) new ExceptQueryOperatorEnumerator (leftHashStream[i], rightHashStream[i], m_comparer, cancellationToken); } } outputRecipient.Receive(outputStream); } //--------------------------------------------------------------------------------------- // Returns an enumerable that represents the query executing sequentially. // internal override IEnumerable AsSequentialQuery(CancellationToken token) { IEnumerable wrappedLeftChild = CancellableEnumerable.Wrap(LeftChild.AsSequentialQuery(token), token); IEnumerable wrappedRightChild = CancellableEnumerable.Wrap(RightChild.AsSequentialQuery(token), token); return wrappedLeftChild.Except(wrappedRightChild, m_comparer); } //--------------------------------------------------------------------------------------- // Whether this operator performs a premature merge. // internal override bool LimitsParallelism { get { return false; } } //---------------------------------------------------------------------------------------- // This enumerator calculates the distinct set incrementally. It does this by maintaining // a history -- in the form of a set -- of all data already seen. It then only returns // elements that have not yet been seen. // class ExceptQueryOperatorEnumerator : QueryOperatorEnumerator { private QueryOperatorEnumerator , TLeftKey> m_leftSource; // Left data source. private QueryOperatorEnumerator , int> m_rightSource; // Right data source. private IEqualityComparer m_comparer; // A comparer used for equality checks/hash-coding. private Set m_hashLookup; // The hash lookup, used to produce the distinct set. private CancellationToken m_cancellationToken; private Shared m_outputLoopCount; //--------------------------------------------------------------------------------------- // Instantiates a new except query operator enumerator. // internal ExceptQueryOperatorEnumerator( QueryOperatorEnumerator , TLeftKey> leftSource, QueryOperatorEnumerator , int> rightSource, IEqualityComparer comparer, CancellationToken cancellationToken) { Contract.Assert(leftSource != null); Contract.Assert(rightSource != null); m_leftSource = leftSource; m_rightSource = rightSource; m_comparer = comparer; m_cancellationToken = cancellationToken; } //---------------------------------------------------------------------------------------- // Walks the two data sources, left and then right, to produce the distinct set // internal override bool MoveNext(ref TInputOutput currentElement, ref int currentKey) { Contract.Assert(m_leftSource != null); Contract.Assert(m_rightSource != null); // Build the set out of the left data source, if we haven't already. if (m_hashLookup == null) { m_outputLoopCount = new Shared (0); // @ m_hashLookup = new Set (m_comparer); Pair rightElement = default(Pair ); int rightKeyUnused = default(int); int i = 0; while (m_rightSource.MoveNext(ref rightElement, ref rightKeyUnused)) { if ((i++ & CancellationState.POLL_INTERVAL) == 0) CancellationState.ThrowIfCanceled(m_cancellationToken); m_hashLookup.Add(rightElement.First); } } // Now iterate over the right data source, looking for matches. Pair leftElement = default(Pair ); TLeftKey leftKeyUnused = default(TLeftKey); while (m_leftSource.MoveNext(ref leftElement, ref leftKeyUnused)) { if ((m_outputLoopCount.Value++ & CancellationState.POLL_INTERVAL) == 0) CancellationState.ThrowIfCanceled(m_cancellationToken); if (m_hashLookup.Add(leftElement.First)) { // This element has never been seen. Return it. currentElement = leftElement.First; #if DEBUG currentKey = unchecked((int)0xdeadbeef); #endif return true; } } return false; } protected override void Dispose(bool disposing) { Contract.Assert(m_leftSource != null && m_rightSource != null); m_leftSource.Dispose(); m_rightSource.Dispose(); } } class OrderedExceptQueryOperatorEnumerator : QueryOperatorEnumerator { private QueryOperatorEnumerator , TLeftKey> m_leftSource; // Left data source. private QueryOperatorEnumerator , int> m_rightSource; // Right data source. private IEqualityComparer m_comparer; // A comparer used for equality checks/hash-coding. private IComparer m_leftKeyComparer; // A comparer for order keys. private IEnumerator , Pair >> m_outputEnumerator; // The enumerator output elements + order keys. private CancellationToken m_cancellationToken; //---------------------------------------------------------------------------------------- // Instantiates a new except query operator enumerator. // internal OrderedExceptQueryOperatorEnumerator( QueryOperatorEnumerator , TLeftKey> leftSource, QueryOperatorEnumerator , int> rightSource, IEqualityComparer comparer, IComparer leftKeyComparer, CancellationToken cancellationToken) { Contract.Assert(leftSource != null); Contract.Assert(rightSource != null); m_leftSource = leftSource; m_rightSource = rightSource; m_comparer = comparer; m_leftKeyComparer = leftKeyComparer; m_cancellationToken = cancellationToken; } //--------------------------------------------------------------------------------------- // Walks the two data sources, left and then right, to produce the distinct set // internal override bool MoveNext(ref TInputOutput currentElement, ref TLeftKey currentKey) { Contract.Assert(m_leftSource != null); Contract.Assert(m_rightSource != null); // Build the set out of the left data source, if we haven't already. if (m_outputEnumerator == null) { // @ Set rightLookup = new Set (m_comparer); Pair rightElement = default(Pair ); int rightKeyUnused = default(int); int i=0; while (m_rightSource.MoveNext(ref rightElement, ref rightKeyUnused)) { if ((i++ & CancellationState.POLL_INTERVAL) == 0) CancellationState.ThrowIfCanceled(m_cancellationToken); rightLookup.Add(rightElement.First); } var leftLookup = new Dictionary , Pair >( new WrapperEqualityComparer (m_comparer)); Pair leftElement = default(Pair ); TLeftKey leftKey = default(TLeftKey); while (m_leftSource.MoveNext(ref leftElement, ref leftKey)) { if ((i++ & CancellationState.POLL_INTERVAL) == 0) CancellationState.ThrowIfCanceled(m_cancellationToken); if (rightLookup.Contains(leftElement.First)) { continue; } Pair oldEntry; Wrapper wrappedLeftElement = new Wrapper (leftElement.First); if (!leftLookup.TryGetValue(wrappedLeftElement, out oldEntry) || m_leftKeyComparer.Compare(leftKey, oldEntry.Second) < 0) { // For each "elem" value, we store the smallest key, and the element value that had that key. // Note that even though two element values are "equal" according to the EqualityComparer, // we still cannot choose arbitrarily which of the two to yield. leftLookup[wrappedLeftElement] = new Pair (leftElement.First, leftKey); } } m_outputEnumerator = leftLookup.GetEnumerator(); } if (m_outputEnumerator.MoveNext()) { Pair currentPair = m_outputEnumerator.Current.Value; currentElement = currentPair.First; currentKey = currentPair.Second; return true; } return false; } protected override void Dispose(bool disposing) { Contract.Assert(m_leftSource != null && m_rightSource != null); m_leftSource.Dispose(); m_rightSource.Dispose(); } } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu

This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- AttributeQuery.cs
- ProtocolsConfigurationHandler.cs
- SimpleBitVector32.cs
- LicenseProviderAttribute.cs
- OleAutBinder.cs
- TreeNodeStyle.cs
- PathFigureCollection.cs
- StringArrayConverter.cs
- SelfIssuedAuthRSACryptoProvider.cs
- IncrementalHitTester.cs
- SafeLibraryHandle.cs
- TreeNodeStyleCollection.cs
- BitmapEffectInputData.cs
- XmlILModule.cs
- AuthenticationModuleElementCollection.cs
- ConfigXmlSignificantWhitespace.cs
- AppDomain.cs
- SQLByte.cs
- DecimalAnimationBase.cs
- DateTimeHelper.cs
- HatchBrush.cs
- ActivityMetadata.cs
- ValidationSummary.cs
- StrokeNode.cs
- ObjectDataSourceMethodEventArgs.cs
- Menu.cs
- Parameter.cs
- TextWriter.cs
- SortKey.cs
- OperationFormatUse.cs
- WebPartRestoreVerb.cs
- UserControl.cs
- XmlSchemaSimpleTypeUnion.cs
- IListConverters.cs
- ContextMenuStrip.cs
- TiffBitmapDecoder.cs
- CompilationPass2TaskInternal.cs
- MiniModule.cs
- ExtenderProviderService.cs
- XmlSchemaCompilationSettings.cs
- EditorAttribute.cs
- Accessible.cs
- ColumnResizeUndoUnit.cs
- _Events.cs
- EdmFunction.cs
- RelativeSource.cs
- UnregisterInfo.cs
- XmlDictionaryReaderQuotas.cs
- PriorityQueue.cs
- VisemeEventArgs.cs
- ProcessHost.cs
- ProcessModule.cs
- SQLDecimalStorage.cs
- CngKeyCreationParameters.cs
- RegisteredExpandoAttribute.cs
- CodeIterationStatement.cs
- DataException.cs
- UInt16.cs
- ConnectionStringsExpressionBuilder.cs
- SchemaCollectionPreprocessor.cs
- Barrier.cs
- storepermission.cs
- VariableAction.cs
- QilBinary.cs
- ThreadExceptionDialog.cs
- X509Certificate2.cs
- ZipIOZip64EndOfCentralDirectoryLocatorBlock.cs
- DataGridAutomationPeer.cs
- LambdaCompiler.Expressions.cs
- ExpandSegmentCollection.cs
- Point3DCollectionValueSerializer.cs
- FormatException.cs
- Sentence.cs
- ScalarType.cs
- CompositeCollectionView.cs
- StreamUpgradeProvider.cs
- DecimalKeyFrameCollection.cs
- HtmlElementEventArgs.cs
- RepeatInfo.cs
- Int16Converter.cs
- SharedPerformanceCounter.cs
- CssClassPropertyAttribute.cs
- UrlUtility.cs
- FunctionDefinition.cs
- EntityDataSourceStatementEditor.cs
- BinaryUtilClasses.cs
- XmlHierarchyData.cs
- AdapterUtil.cs
- KeyConstraint.cs
- AttributeExtensions.cs
- DocumentProperties.cs
- StorageComplexPropertyMapping.cs
- AuthStoreRoleProvider.cs
- BitmapPalettes.cs
- Stylesheet.cs
- SQLInt16Storage.cs
- CopyNamespacesAction.cs
- PKCS1MaskGenerationMethod.cs
- TabItem.cs
- XmlMemberMapping.cs