Changeset 13123
 Timestamp:
 Dec 31, 2011, 9:28:53 PM (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/libtransmission/peermgr.c
r12954 r13123 3833 3833 } 3834 3834 3835 /* sort an array of peer candidates */ 3835 #ifndef NDEBUG 3836 3836 static int 3837 comparePeerCandidates( const void * va, const void * vb ) 3838 { 3839 const struct peer_candidate * a = va; 3840 const struct peer_candidate * b = vb; 3841 3842 if( a>score < b>score ) return 1; 3843 if( a>score > b>score ) return 1; 3844 3845 return 0; 3846 } 3837 checkPartition( const struct peer_candidate * candidates, int left, int right, uint64_t pivotScore, int storeIndex ) 3838 { 3839 int i; 3840 3841 assert( storeIndex >= left ); 3842 assert( storeIndex <= right ); 3843 assert( candidates[storeIndex].score == pivotScore ); 3844 3845 for( i=left; i<storeIndex; ++i ) 3846 assert( candidates[i].score < pivotScore ); 3847 for( i=storeIndex+1; i<=right; ++i ) 3848 assert( candidates[i].score >= pivotScore ); 3849 3850 return true; 3851 } 3852 #endif 3853 3854 /* Helper to selectBestCandidates(). 3855 * Adapted from http://en.wikipedia.org/wiki/Selection_algorithm */ 3856 static int 3857 partitionPeerCandidates( struct peer_candidate * candidates, int left, int right, int pivotIndex ) 3858 { 3859 int i; 3860 int storeIndex; 3861 struct peer_candidate tmp; 3862 const struct peer_candidate pivotValue = candidates[pivotIndex]; 3863 3864 /* move pivot to end */ 3865 tmp = candidates[right]; 3866 candidates[right] = pivotValue; 3867 candidates[pivotIndex] = tmp; 3868 3869 storeIndex = left; 3870 for( i=left; i<=right; ++i ) 3871 { 3872 if( candidates[i].score < pivotValue.score ) 3873 { 3874 tmp = candidates[storeIndex]; 3875 candidates[storeIndex] = candidates[i]; 3876 candidates[i] = tmp; 3877 storeIndex++; 3878 } 3879 } 3880 3881 /* move pivot to its final place */ 3882 tmp = candidates[right]; 3883 candidates[right] = candidates[storeIndex]; 3884 candidates[storeIndex] = tmp; 3885 3886 /* sanity check */ 3887 assert( checkPartition( candidates, left, right, pivotValue.score, storeIndex ) ); 3888 3889 return storeIndex; 3890 } 3891 3892 /* Adapted from http://en.wikipedia.org/wiki/Selection_algorithm */ 3893 static void 3894 selectPeerCandidates( struct peer_candidate * candidates, int left, int right, int k ) 3895 { 3896 if( right > left ) 3897 { 3898 const int pivotIndex = left + (rightleft)/2; 3899 3900 int pivotNewIndex = partitionPeerCandidates( candidates, left, right, pivotIndex ); 3901 3902 if( pivotNewIndex > left + k ) /* new condition */ 3903 selectPeerCandidates( candidates, left, pivotNewIndex1, k ); 3904 else if( pivotNewIndex < left + k ) 3905 selectPeerCandidates( candidates, pivotNewIndex+1, right, k+leftpivotNewIndex1 ); 3906 } 3907 } 3908 3909 #ifndef NDEBUG 3910 static bool 3911 checkBestScoresComeFirst( const struct peer_candidate * candidates, int n, int k ) 3912 { 3913 int i; 3914 uint64_t worstFirstScore = 0; 3915 const int x = MIN( n, k )  1; 3916 3917 for( i=0; i<x; i++ ) 3918 if( worstFirstScore < candidates[i].score ) 3919 worstFirstScore = candidates[i].score; 3920 3921 for( i=0; i<x; i++ ) 3922 assert( candidates[i].score <= worstFirstScore ); 3923 3924 for( i=x+1; i<n; i++ ) 3925 assert( candidates[i].score >= worstFirstScore ); 3926 3927 return true; 3928 } 3929 #endif /* NDEBUG */ 3847 3930 3848 3931 /** @return an array of all the atoms we might want to connect to */ 3849 3932 static struct peer_candidate* 3850 getPeerCandidates( tr_session * session, int * candidateCount )3933 getPeerCandidates( tr_session * session, int * candidateCount, int max ) 3851 3934 { 3852 3935 int atomCount; … … 3913 3996 3914 3997 *candidateCount = walk  candidates; 3915 if( *candidateCount > 1 ) 3916 qsort( candidates, *candidateCount, sizeof( struct peer_candidate ), comparePeerCandidates ); 3998 if( walk != candidates ) 3999 selectPeerCandidates( candidates, 0, (walkcandidates)1, max ); 4000 4001 assert( checkBestScoresComeFirst( candidates, *candidateCount, max ) ); 4002 3917 4003 return candidates; 3918 4004 } … … 3991 4077 struct peer_candidate * candidates; 3992 4078 3993 candidates = getPeerCandidates( mgr>session, &n );4079 candidates = getPeerCandidates( mgr>session, &n, max ); 3994 4080 3995 4081 for( i=0; i<n && i<max; ++i )
Note: See TracChangeset
for help on using the changeset viewer.