Changeset 5644


Ignore:
Timestamp:
Apr 18, 2008, 8:56:20 PM (14 years ago)
Author:
charles
Message:

use a binary search to slightly speed up finding the right location in a torrent when reading/writing a piece.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/inout.c

    r5329 r5644  
    9494                  uint64_t         * fileOffset )
    9595{
    96     const tr_info * info = &tor->info;
    97 
    98     tr_file_index_t i;
    99     uint64_t piecePos = ((uint64_t)pieceIndex * info->pieceSize) + pieceOffset;
    100 
    101     if( pieceIndex >= info->pieceCount )
    102         return TR_ERROR_ASSERT;
    103     if( pieceOffset >= tr_torPieceCountBytes( tor, pieceIndex ) )
    104         return TR_ERROR_ASSERT;
    105     if( piecePos >= info->totalSize )
    106         return TR_ERROR_ASSERT;
    107 
    108     for( i=0; info->files[i].length<=piecePos; ++i )
    109         piecePos -= info->files[i].length;
    110 
    111     *fileIndex = i;
    112     *fileOffset = piecePos;
    113 
    114     assert( *fileIndex < info->fileCount );
    115     assert( *fileOffset < info->files[i].length );
     96    size_t len;
     97    tr_file_index_t first, last;
     98    const tr_info * inf = &tor->info;
     99    uint64_t offset = tr_pieceOffset( tor, pieceIndex, pieceOffset, 0 );
     100
     101    assert( pieceIndex < inf->pieceCount );
     102    assert( pieceOffset < tr_torPieceCountBytes( tor, pieceIndex ) );
     103    assert( offset < inf->totalSize );
     104   
     105    /* use a lower-bound bsearch to find the file that matches */
     106    first = 0;
     107    last = inf->fileCount;
     108    len = last - first;
     109    while( len > 0 ) {
     110        size_t half = len / 2;
     111        size_t middle = first + half;
     112        if( inf->files[middle].offset + inf->files[middle].length < offset ) {
     113            first = middle;
     114            ++first;
     115            len = len - half - 1;
     116        }
     117        else len = half;
     118    }
     119   
     120    *fileIndex = first;
     121    *fileOffset = offset - inf->files[first].offset;
     122
     123    assert( inf->files[first].offset <= offset );
     124    assert( offset < inf->files[first].offset + inf->files[first].length );
     125    assert( *fileIndex < inf->fileCount );
     126    assert( *fileOffset < inf->files[first].length );
    116127    return 0;
    117128}
     
    163174    const tr_info * info = &tor->info;
    164175
    165     if( pieceIndex >= tor->info.pieceCount )
    166         err = TR_ERROR_ASSERT;
    167     else if( buflen > ( size_t ) tr_torPieceCountBytes( tor, pieceIndex ) )
    168         err = TR_ERROR_ASSERT;
     176    assert( pieceIndex < tor->info.pieceCount );
     177    assert( pieceOffset + buflen <= tr_torPieceCountBytes( tor, pieceIndex ) );
    169178
    170179    if( !err )
     
    254263
    255264    tr_lockUnlock( lock );
    256     return 0;
     265    return err;
    257266}
    258267
Note: See TracChangeset for help on using the changeset viewer.