HashRepartitionStream.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / Core / System / Linq / Parallel / Partitioning / HashRepartitionStream.cs / 1305376 / HashRepartitionStream.cs

                            // ==++== 
//
//   Copyright (c) Microsoft Corporation.  All rights reserved.
//
// ==--== 
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
// 
// HashPartitionedStream.cs 
//
// [....] 
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

using System.Collections.Generic; 
using System.Diagnostics.Contracts;
using System.Threading; 
 
namespace System.Linq.Parallel
{ 
    /// 
    /// A repartitioning stream must take input data that has already been partitioned and
    /// redistribute its contents based on a new partitioning algorithm. This is accomplished
    /// by making each partition p responsible for redistributing its input data to the 
    /// correct destination partition. Some input elements may remain in p, but many will now
    /// belong to a different partition and will need to move. This requires a great deal of 
    /// synchronization, but allows threads to repartition data incrementally and in parallel. 
    /// Each partition will "pull" data on-demand instead of partitions "pushing" data, which
    /// allows us to reduce some amount of synchronization overhead. 
    ///
    /// We currently only offer one form of reparitioning via hashing.  This used to be an
    /// abstract base class, but we have eliminated that to get rid of some virtual calls on
    /// hot code paths.  Uses a key selection algorithm with mod'ding to determine destination. 
    ///
    /// @ 
 

 



 
    internal abstract class HashRepartitionStream : PartitionedStream, TOrderKey>
    { 
        private readonly IEqualityComparer m_keyComparer; // The optional key comparison routine. 
        private readonly IEqualityComparer m_elementComparer; // The optional element comparison routine.
        private readonly int m_distributionMod; // The distribution value we'll use to scramble input. 

        //----------------------------------------------------------------------------------------
        // Creates a new partition exchange operator.
        // 

        internal HashRepartitionStream( 
            int partitionsCount, IComparer orderKeyComparer, IEqualityComparer hashKeyComparer, 
            IEqualityComparer elementComparer)
            : base(partitionsCount, orderKeyComparer, OrdinalIndexState.Shuffled) 
        {
            // elementComparer is used by operators that use elements themselves as the hash keys.
            // When elements are used as keys, THashKey should be NoKeyMemoizationRequired.
            m_keyComparer = hashKeyComparer; 
            m_elementComparer = elementComparer;
 
            Contract.Assert(m_keyComparer == null || m_elementComparer == null); 
            Contract.Assert(m_elementComparer == null || typeof(THashKey) == typeof(NoKeyMemoizationRequired));
 
            // We use the following constant when distributing hash-codes into partition streams.
            // It's an (arbitrary) prime number to account for poor hashing functions, e.g. those
            // that all the primitive types use (e.g. Int32 returns itself). The goal is to add some
            // degree of randomization to avoid predictable distributions for certain data sequences, 
            // for the same reason prime numbers are frequently used in hashtable implementations.
            // For instance, if all hash-codes end up as even, we would starve half of the partitions 
            // by just using the raw hash-code. This isn't perfect, of course, since a stream 
            // of integers with the same value end up in the same partition, but helps.
            const int DEFAULT_HASH_MOD_DISTRIBUTION = 503; 

            // We need to guarantee our distribution mod is greater than the number of partitions.
            m_distributionMod = DEFAULT_HASH_MOD_DISTRIBUTION;
            while (m_distributionMod < partitionsCount) 
            {
                // We use checked arithmetic here.  We'll only overflow for huge numbers of partitions 
                // (quite unlikely), so the remote possibility of an exception is fine. 
                checked
                { 
                    m_distributionMod *= 2;
                }
            }
        } 

        //--------------------------------------------------------------------------------------- 
        // Manufactures a hash code for a given value or key. 
        //
 
        // The hash-code used for null elements.
        private const int NULL_ELEMENT_HASH_CODE = 0;

        internal int GetHashCode(TInputOutput element) 
        {
            return 
                (0x7fffffff & 
                    (m_elementComparer == null ?
                        (element == null ? NULL_ELEMENT_HASH_CODE : element.GetHashCode()) : 
                        m_elementComparer.GetHashCode(element)))
                        % m_distributionMod;
        }
 
        internal int GetHashCode(THashKey key)
        { 
            return 
                (0x7fffffff &
                    (m_keyComparer == null ? 
                        (key == null ? NULL_ELEMENT_HASH_CODE : key.GetHashCode()) :
                        m_keyComparer.GetHashCode(key))) % m_distributionMod;
        }
    } 

} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK