Changeset 9920
 Timestamp:
 Jan 12, 2010, 8:17:22 PM (12 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/libtransmission/peermgr.c
r9890 r9920 157 157 { 158 158 tr_piece_index_t index; 159 tr_piece_index_t salt;159 int16_t salt; 160 160 int16_t requestCount; 161 161 }; … … 181 181 182 182 struct weighted_piece * pieces; 183 int piecesSort;184 183 int pieceCount; 185 186 tr_bool isInEndgame;187 184 } 188 185 Torrent; … … 806 803  mode==PIECES_SORTED_BY_WEIGHT ); 807 804 808 if( t>piecesSort != mode ) 809 { 810 t>piecesSort = mode; 811 812 switch( mode ) { 813 case PIECES_SORTED_BY_WEIGHT: compar = comparePieceByWeight; break; 814 case PIECES_SORTED_BY_INDEX: compar = comparePieceByIndex; break; 815 default: assert( 0 && "unhandled" ); break; 816 } 817 818 weightTorrent = t>tor; 819 qsort( t>pieces, t>pieceCount, 820 sizeof( struct weighted_piece ), compar ); 821 } 822 823 /* Also, as long as we've got the pieces sorted by weight, 824 * let's also update t.isInEndgame */ 825 if( t>piecesSort == PIECES_SORTED_BY_WEIGHT ) 826 { 827 tr_bool endgame = TRUE; 828 829 if( ( t>pieces != NULL ) && ( t>pieceCount > 0 ) ) 830 { 831 const tr_completion * cp = &t>tor>completion; 832 const struct weighted_piece * p = t>pieces; 833 const int pending = p>requestCount; 834 const int missing = tr_cpMissingBlocksInPiece( cp, p>index ); 835 endgame = pending >= missing; 836 } 837 838 t>isInEndgame = endgame; 839 /*if( t>isInEndgame ) fprintf( stderr, "ENDGAME reached\n" );*/ 840 } 805 switch( mode ) { 806 case PIECES_SORTED_BY_WEIGHT: compar = comparePieceByWeight; break; 807 case PIECES_SORTED_BY_INDEX: compar = comparePieceByIndex; break; 808 default: assert( 0 && "unhandled" ); break; 809 } 810 811 weightTorrent = t>tor; 812 qsort( t>pieces, t>pieceCount, 813 sizeof( struct weighted_piece ), compar ); 814 } 815 816 static tr_bool 817 isInEndgame( Torrent * t ) 818 { 819 tr_bool endgame = TRUE; 820 821 if( ( t>pieces != NULL ) && ( t>pieceCount > 0 ) ) 822 { 823 const tr_completion * cp = &t>tor>completion; 824 const struct weighted_piece * p = t>pieces; 825 const int pending = p>requestCount; 826 const int missing = tr_cpMissingBlocksInPiece( cp, p>index ); 827 endgame = pending >= missing; 828 } 829 830 /*if( endgame ) fprintf( stderr, "ENDGAME reached\n" );*/ 831 return endgame; 841 832 } 842 833 … … 844 835 pieceListLookup( Torrent * t, tr_piece_index_t index ) 845 836 { 846 struct weighted_piece key; 847 key.index = index; 848 849 pieceListSort( t, PIECES_SORTED_BY_INDEX ); 850 851 return bsearch( &key, t>pieces, t>pieceCount, 852 sizeof( struct weighted_piece ), 853 comparePieceByIndex ); 837 const struct weighted_piece * limit = t>pieces; 838 struct weighted_piece * piece = t>pieces + t>pieceCount  1; 839 840 if ( t>pieceCount == 0 ) return NULL; 841 842 /* reverse linear search */ 843 for( ;; ) 844 { 845 if( piece < limit ) return NULL; 846 if( index == piece>index ) return piece; else piece; 847 } 854 848 } 855 849 … … 907 901 t>pieces = pieces; 908 902 t>pieceCount = pieceCount; 909 t>piecesSort = PIECES_SORTED_BY_INDEX; 903 904 pieceListSort( t, PIECES_SORTED_BY_WEIGHT ); 910 905 911 906 /* cleanup */ … … 938 933 pieceListRemoveRequest( Torrent * t, tr_block_index_t block ) 939 934 { 940 struct weighted_piece * p;941 935 const tr_piece_index_t index = tr_torBlockPiece( t>tor, block ); 942 943 if(( p = pieceListLookup( t, index ))) 944 if( p>requestCount > 0 ) 945 p>requestCount; 946 947 /* note: this invalidates the weighted.piece.weight field, 948 * but that's OK since the call to pieceListLookup ensured 949 * that we were sorted by index anyway.. next time we resort 950 * by weight, pieceListSort() will update the weights */ 936 const struct weighted_piece * p = pieceListLookup( t, index ); 937 938 if( p != NULL ) 939 { 940 const int pos = p  t>pieces; 941 struct weighted_piece piece = t>pieces[pos]; 942 int newpos; 943 tr_bool exact; 944 945 /* remove request */ 946 if( piece.requestCount > 0 ) 947 piece.requestCount; 948 949 /* List is nearly sorted (by weight) : insert piece into the right place. */ 950 951 weightTorrent = t>tor; 952 newpos = tr_lowerBound( &piece, t>pieces, t>pieceCount, 953 sizeof( struct weighted_piece ), 954 comparePieceByWeight, &exact ); 955 956 if( newpos == pos  newpos == pos + 1 ) 957 { 958 /* it's VERY likely that piece keeps its position */ 959 t>pieces[pos].requestCount = piece.requestCount; 960 } 961 else 962 { 963 /* piece is removed temporally to make insertion easier */ 964 memmove( &t>pieces[pos], 965 &t>pieces[pos + 1], 966 sizeof( struct weighted_piece ) * ( t>pieceCount  pos ) ); 967 968 if( newpos > pos ) newpos; 969 970 memmove( &t>pieces[newpos + 1], 971 &t>pieces[newpos], 972 sizeof( struct weighted_piece ) * ( t>pieceCount++  newpos ) ); 973 974 t>pieces[newpos] = piece; 975 } 976 } 951 977 } 952 978 … … 973 999 int got; 974 1000 Torrent * t; 1001 tr_bool endgame; 975 1002 struct weighted_piece * pieces; 976 1003 const tr_bitset * have = &peer>have; … … 987 1014 if( t>pieces == NULL ) 988 1015 pieceListRebuild( t ); 989 pieceListSort( t, PIECES_SORTED_BY_WEIGHT ); 1016 1017 endgame = isInEndgame( t ); 990 1018 991 1019 pieces = t>pieces; … … 994 1022 struct weighted_piece * p = pieces + i; 995 1023 const int missing = tr_cpMissingBlocksInPiece( &tor>completion, p>index ); 996 const int maxDuplicatesPerBlock = t>isInEndgame ? 3 : 1;1024 const int maxDuplicatesPerBlock = endgame ? 3 : 1; 997 1025 998 1026 if( p>requestCount > ( missing * maxDuplicatesPerBlock ) ) … … 1030 1058 1031 1059 /* In most cases we've just changed the weights of a small number of pieces. 1032 * So rather than qsort()ing the entire array, it's faster to sort only the 1033 * changed ones, then do a standard mergetwosortedarrays pass on the 1034 * changed and unchanged pieces. */ 1060 * So rather than qsort()ing the entire array, it's faster to apply an 1061 * adaptive insertion sort algorithm. */ 1035 1062 if( got > 0 ) 1036 1063 { 1037 struct weighted_piece * p; 1038 struct weighted_piece * pieces; 1039 struct weighted_piece * a = t>pieces; 1040 struct weighted_piece * a_end = t>pieces + i; 1041 struct weighted_piece * b = a_end; 1042 struct weighted_piece * b_end = t>pieces + t>pieceCount; 1043 1044 /* resort the pieces that we changed */ 1064 /* not enough requests  last piece modified */ 1065 if ( i == t>pieceCount ) i; 1066 1045 1067 weightTorrent = t>tor; 1046 qsort( a, a_enda, sizeof( struct weighted_piece ), comparePieceByWeight ); 1047 1048 /* allocate a new array */ 1049 p = pieces = tr_new( struct weighted_piece, t>pieceCount ); 1050 1051 /* merge the two sorted arrays into this new array */ 1052 weightTorrent = t>tor; 1053 while( a!=a_end && b!=b_end ) 1054 *p++ = comparePieceByWeight( a, b ) < 0 ? *a++ : *b++; 1055 while( a!=a_end ) *p++ = *a++; 1056 while( b!=b_end ) *p++ = *b++; 1057 1058 #if 0 1059 /* make sure we did it right */ 1060 assert( p  pieces == t>pieceCount ); 1061 for( it=pieces; it+1<p; ++it ) 1062 assert( it>weight <= it[1].weight ); 1063 #endif 1064 1065 /* update */ 1066 tr_free( t>pieces ); 1067 t>pieces = pieces; 1068 while( i >= 0 ) 1069 { 1070 tr_bool exact; 1071 1072 /* relative position! */ 1073 const int newpos = tr_lowerBound( &t>pieces[i], &t>pieces[i + 1], 1074 t>pieceCount  (i + 1), 1075 sizeof( struct weighted_piece ), 1076 comparePieceByWeight, &exact ); 1077 if( newpos > 0 ) 1078 { 1079 const struct weighted_piece piece = t>pieces[i]; 1080 memmove( &t>pieces[i], 1081 &t>pieces[i + 1], 1082 sizeof( struct weighted_piece ) * ( newpos ) ); 1083 t>pieces[i + newpos] = piece; 1084 } 1085 } 1068 1086 } 1069 1087 … … 1368 1386 1369 1387 requestListRemove( t, block, peer ); 1370 pieceListRemoveRequest( t, block );1371 1388 1372 1389 if( tr_cpBlockIsComplete( &tor>completion, block ) ) … … 1374 1391 tordbg( t, "we have this block already..." ); 1375 1392 clientGotUnwantedBlock( tor, block ); 1393 pieceListRemoveRequest( t, block ); 1376 1394 } 1377 1395 else 1378 1396 { 1379 1397 tr_cpBlockAdd( &tor>completion, block ); 1398 pieceListRemoveRequest( t, block ); 1380 1399 tr_torrentSetDirty( tor ); 1381 1400
Note: See TracChangeset
for help on using the changeset viewer.