source: trunk/libtransmission/completion.c @ 7631

Last change on this file since 7631 was 7631, checked in by charles, 13 years ago

(trunk libT) much faster implementation of tr_cpBlockBitfieldSet()

  • Property svn:keywords set to Date Rev Author Id
File size: 11.0 KB
Line 
1/******************************************************************************
2 * $Id: completion.c 7631 2009-01-07 02:22:11Z charles $
3 *
4 * Copyright (c) 2005-2008 Transmission authors and contributors
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 * DEALINGS IN THE SOFTWARE.
23 *****************************************************************************/
24
25#include <assert.h>
26#include <string.h>
27
28#include "transmission.h"
29#include "completion.h"
30#include "torrent.h"
31#include "utils.h"
32
33static void
34tr_cpReset( tr_completion * cp )
35{
36    tr_bitfieldClear( &cp->pieceBitfield );
37    tr_bitfieldClear( &cp->blockBitfield );
38    memset( cp->completeBlocks, 0, sizeof( uint16_t ) * cp->tor->info.pieceCount );
39    cp->sizeNow = 0;
40    cp->sizeWhenDoneIsDirty = 1;
41    cp->haveValidIsDirty = 1;
42}
43
44tr_completion *
45tr_cpConstruct( tr_completion * cp, tr_torrent * tor )
46{
47    cp->tor = tor;
48    cp->completeBlocks  = tr_new( uint16_t, tor->info.pieceCount );
49    tr_bitfieldConstruct( &cp->blockBitfield, tor->blockCount );
50    tr_bitfieldConstruct( &cp->pieceBitfield, tor->info.pieceCount );
51    tr_cpReset( cp );
52    return cp;
53}
54
55tr_completion*
56tr_cpDestruct( tr_completion * cp )
57{
58    tr_free( cp->completeBlocks );
59    tr_bitfieldDestruct( &cp->pieceBitfield );
60    tr_bitfieldDestruct( &cp->blockBitfield );
61    return cp;
62}
63
64void
65tr_cpInvalidateDND( tr_completion * cp )
66{
67    cp->sizeWhenDoneIsDirty = 1;
68}
69
70uint64_t
71tr_cpSizeWhenDone( const tr_completion * ccp )
72{
73    if( ccp->sizeWhenDoneIsDirty )
74    {
75        tr_completion *    cp = (tr_completion *) ccp; /* mutable */
76        const tr_torrent * tor = cp->tor;
77        const tr_info *    info = &tor->info;
78        tr_piece_index_t   i;
79        uint64_t           size = 0;
80
81        for( i = 0; i < info->pieceCount; ++i )
82        {
83            if( !info->pieces[i].dnd )
84            {
85                /* we want the piece... */
86                size += tr_torPieceCountBytes( tor, i );
87            }
88            else if( tr_cpPieceIsComplete( cp, i ) )
89            {
90                /* we have the piece... */
91                size += tr_torPieceCountBytes( tor, i );
92            }
93            else if( cp->completeBlocks[i] )
94            {
95                /* we have part of the piece... */
96                const tr_block_index_t b = tr_torPieceFirstBlock( tor, i );
97                const tr_block_index_t e = b + tr_torPieceCountBlocks( tor,
98                                                                       i );
99                tr_block_index_t       j;
100                for( j = b; j < e; ++j )
101                    if( tr_cpBlockIsComplete( cp, j ) )
102                        size += tr_torBlockCountBytes( tor, j );
103            }
104        }
105
106        cp->sizeWhenDoneLazy = size;
107        cp->sizeWhenDoneIsDirty = 0;
108    }
109
110    assert( ccp->sizeWhenDoneLazy <= ccp->tor->info.totalSize );
111    assert( ccp->sizeWhenDoneLazy >= ccp->sizeNow );
112    return ccp->sizeWhenDoneLazy;
113}
114
115void
116tr_cpPieceAdd( tr_completion *  cp,
117               tr_piece_index_t piece )
118{
119    const tr_torrent *     tor = cp->tor;
120    const tr_block_index_t start = tr_torPieceFirstBlock( tor, piece );
121    const tr_block_index_t end = start + tr_torPieceCountBlocks( tor, piece );
122    tr_block_index_t       i;
123
124    for( i = start; i < end; ++i )
125        tr_cpBlockAdd( cp, i );
126}
127
128void
129tr_cpPieceRem( tr_completion *  cp,
130               tr_piece_index_t piece )
131{
132    const tr_torrent *     tor = cp->tor;
133    const tr_block_index_t start = tr_torPieceFirstBlock( tor, piece );
134    const tr_block_index_t end = start + tr_torPieceCountBlocks( tor, piece );
135    tr_block_index_t       block;
136
137    assert( cp );
138    assert( piece < tor->info.pieceCount );
139    assert( start < tor->blockCount );
140    assert( start <= end );
141    assert( end <= tor->blockCount );
142
143    for( block = start; block < end; ++block )
144        if( tr_cpBlockIsComplete( cp, block ) )
145            cp->sizeNow -= tr_torBlockCountBytes( tor, block );
146
147    cp->sizeWhenDoneIsDirty = 1;
148    cp->haveValidIsDirty = 1;
149    cp->completeBlocks[piece] = 0;
150    tr_bitfieldRemRange ( &cp->blockBitfield, start, end );
151    tr_bitfieldRem( &cp->pieceBitfield, piece );
152}
153
154void
155tr_cpBlockAdd( tr_completion * cp, tr_block_index_t block )
156{
157    const tr_torrent * tor = cp->tor;
158
159    if( !tr_cpBlockIsComplete( cp, block ) )
160    {
161        const tr_piece_index_t piece = tr_torBlockPiece( tor, block );
162        const int              blockSize = tr_torBlockCountBytes( tor,
163                                                                  block );
164
165        ++cp->completeBlocks[piece];
166
167        if( tr_cpPieceIsComplete( cp, piece ) )
168            tr_bitfieldAdd( &cp->pieceBitfield, piece );
169
170        tr_bitfieldAdd( &cp->blockBitfield, block );
171
172        cp->sizeNow += blockSize;
173
174        cp->haveValidIsDirty = 1;
175        cp->sizeWhenDoneIsDirty = 1;
176    }
177}
178
179tr_bool
180tr_cpBlockBitfieldSet( tr_completion * cp, tr_bitfield * blockBitfield )
181{
182    int success = FALSE;
183
184    assert( cp );
185    assert( blockBitfield );
186
187    if(( success = blockBitfield->byteCount == cp->blockBitfield.byteCount ))
188    {
189        tr_block_index_t b = 0;
190        tr_piece_index_t p = 0;
191        uint32_t pieceBlock = 0;
192        uint32_t completeBlocksInPiece = 0;
193        tr_block_index_t completeBlocksInTorrent = 0;
194        uint32_t blocksInCurrentPiece = tr_torPieceCountBlocks( cp->tor, p );
195
196        assert( blockBitfield->byteCount == cp->blockBitfield.byteCount );
197
198        tr_cpReset( cp );
199
200        cp->sizeWhenDoneIsDirty = TRUE;
201        cp->haveValidIsDirty = TRUE;
202        memcpy( cp->blockBitfield.bits, blockBitfield->bits, blockBitfield->byteCount );
203
204        while( b < cp->tor->blockCount )
205        {
206            if( tr_bitfieldHasFast( blockBitfield, b ) )
207                ++completeBlocksInPiece;
208
209            ++b;
210            ++pieceBlock;
211
212            if( pieceBlock == blocksInCurrentPiece )
213            {
214                cp->completeBlocks[p] = completeBlocksInPiece;
215
216                completeBlocksInTorrent += completeBlocksInPiece;
217
218                if( completeBlocksInPiece == blocksInCurrentPiece )
219                    tr_bitfieldAdd( &cp->pieceBitfield, p );
220
221                ++p;
222                completeBlocksInPiece = 0;
223                pieceBlock = 0;
224                blocksInCurrentPiece = tr_torPieceCountBlocks( cp->tor, p );
225            }
226        }
227
228        /* update sizeNow */
229        cp->sizeNow = completeBlocksInTorrent;
230        cp->sizeNow *= tr_torBlockCountBytes( cp->tor, 0 );
231        if( tr_bitfieldHasFast( &cp->blockBitfield, cp->tor->blockCount-1 ) ) {
232            cp->sizeNow -= tr_torBlockCountBytes( cp->tor, 0 );
233            cp->sizeNow += tr_torBlockCountBytes( cp->tor, cp->tor->blockCount-1 );
234        }
235
236#if 1
237#warning these checks are to see if the implementation is good, since getting this function wrong could make Transmission think their downloaded data has disappeared.  But they are also expensive, so this block should be turned off after the nightly build users had a chance to smoke out any errors.
238        /**
239        ***  correctness checks
240        **/
241        for( b=0; b<cp->tor->blockCount; ++b )
242            assert( tr_bitfieldHasFast( blockBitfield, b ) == tr_bitfieldHasFast( &cp->blockBitfield, b ) );
243
244        assert( cp->sizeNow <= cp->tor->info.totalSize );
245        for( p=0; p<cp->tor->info.pieceCount; ++p ) {
246            const uint32_t blocksInCurrentPiece = tr_torPieceCountBlocks( cp->tor, p );
247            const tr_block_index_t start = tr_torPieceFirstBlock( cp->tor, p );
248            const tr_block_index_t end = start + tr_torPieceCountBlocks( cp->tor, p );
249            uint32_t completeBlocksInPiece = 0;
250
251            assert( tr_bitfieldHasFast( &cp->pieceBitfield, p ) == ( blocksInCurrentPiece == cp->completeBlocks[p] ) );
252
253            for( b=start; b<end; ++b )
254                if( tr_bitfieldHasFast( &cp->blockBitfield, b ) )
255                    ++completeBlocksInPiece;
256            assert( completeBlocksInPiece == cp->completeBlocks[p] );
257        }
258#endif
259    }
260
261    return success;
262}
263
264/***
265****
266***/
267
268tr_completeness
269tr_cpGetStatus( const tr_completion * cp )
270{
271    if( cp->sizeNow == cp->tor->info.totalSize ) return TR_SEED;
272    if( cp->sizeNow == tr_cpSizeWhenDone( cp ) ) return TR_PARTIAL_SEED;
273    return TR_LEECH;
274}
275
276static uint64_t
277calculateHaveValid( const tr_completion * ccp )
278{
279    uint64_t                  b = 0;
280    tr_piece_index_t          i;
281    const tr_torrent        * tor            = ccp->tor;
282    const uint64_t            pieceSize      = tor->info.pieceSize;
283    const uint64_t            lastPieceSize  = tor->lastPieceSize;
284    const tr_piece_index_t    lastPiece      = tor->info.pieceCount - 1;
285
286    for( i=0; i!=lastPiece; ++i )
287        if( tr_cpPieceIsComplete( ccp, i ) )
288            b += pieceSize;
289
290    if( tr_cpPieceIsComplete( ccp, lastPiece ) )
291        b += lastPieceSize;
292
293    return b;
294}
295
296uint64_t
297tr_cpHaveValid( const tr_completion * ccp )
298{
299    if( ccp->haveValidIsDirty )
300    {
301        tr_completion * cp = (tr_completion *) ccp; /* mutable */
302        cp->haveValidLazy = calculateHaveValid( ccp );
303        cp->haveValidIsDirty = 0;
304    }
305
306    return ccp->haveValidLazy;
307}
308
309void
310tr_cpGetAmountDone( const tr_completion * cp,
311                    float *               tab,
312                    int                   tabCount )
313{
314    int                i;
315    const tr_torrent * tor = cp->tor;
316    const float        interval = tor->info.pieceCount / (float)tabCount;
317    const int          isSeed = tr_cpGetStatus( cp ) == TR_SEED;
318
319    for( i = 0; i < tabCount; ++i )
320    {
321        const tr_piece_index_t piece = i * interval;
322
323        if( tor == NULL )
324            tab[i] = 0.0f;
325        else if( isSeed || tr_cpPieceIsComplete( cp, piece ) )
326            tab[i] = 1.0f;
327        else
328            tab[i] = (float)cp->completeBlocks[piece] /
329                     tr_torPieceCountBlocks( tor, piece );
330    }
331}
332
333int
334tr_cpMissingBlocksInPiece( const tr_completion * cp, tr_piece_index_t piece )
335{
336    return tr_torPieceCountBlocks( cp->tor, piece ) - cp->completeBlocks[piece];
337}
338
339
340tr_bool
341tr_cpPieceIsComplete( const tr_completion * cp, tr_piece_index_t piece )
342{
343    return cp->completeBlocks[piece] == tr_torPieceCountBlocks( cp->tor, piece );
344}
Note: See TracBrowser for help on using the repository browser.