From e212eeceb751f47897bf7e8801b4b4bf54f0e119 Mon Sep 17 00:00:00 2001 From: Charles Kerr Date: Sat, 7 Jun 2008 14:41:31 +0000 Subject: [PATCH] add first draft of tr_bitfieldFindTrue() courtesy of erdgeist --- libtransmission/completion.c | 14 ++++++++--- libtransmission/completion.h | 5 +++- libtransmission/fastresume.c | 1 + libtransmission/resume.c | 1 + libtransmission/utils-test.c | 22 ++++++++++++++++++ libtransmission/utils.c | 45 ++++++++++++++++++++++++++++++++++++ libtransmission/utils.h | 8 +++++++ 7 files changed, 92 insertions(+), 4 deletions(-) diff --git a/libtransmission/completion.c b/libtransmission/completion.c index 440e01a55..f6e8ae7bb 100644 --- a/libtransmission/completion.c +++ b/libtransmission/completion.c @@ -179,6 +179,14 @@ tr_cpPieceRem( tr_completion * cp, tr_piece_index_t piece ) tr_bitfieldRem( cp->pieceBitfield, piece ); } +int +tr_cpBlockFindComplete( const tr_completion * cp, + size_t startPos, + size_t * foundPos ) +{ + return tr_bitfieldFindTrue( cp->blockBitfield, startPos, foundPos ); +} + int tr_cpBlockIsComplete( const tr_completion * cp, tr_block_index_t block ) { @@ -232,9 +240,9 @@ tr_cpBlockBitfieldSet( tr_completion * cp, tr_bitfield * bitfield ) return TR_ERROR_ASSERT; tr_cpReset( cp ); - for( i=0; i < cp->tor->blockCount; ++i ) - if( tr_bitfieldHas( bitfield, i ) ) - tr_cpBlockAdd( cp, i ); + i = 0; + while( tr_bitfieldFindTrue( bitfield, i, &i ) ) + tr_cpBlockAdd( cp, i++ ); return 0; } diff --git a/libtransmission/completion.h b/libtransmission/completion.h index 6f0135279..615624409 100644 --- a/libtransmission/completion.h +++ b/libtransmission/completion.h @@ -53,9 +53,12 @@ void tr_cpPieceRem( tr_completion *, tr_piece_index_t piece ); /* Blocks */ int tr_cpBlockIsComplete( const tr_completion *, tr_block_index_t block ); +int tr_cpBlockFindComplete( const tr_completion * cp, + size_t startPos, size_t* foundPos ); void tr_cpBlockAdd( tr_completion *, tr_block_index_t block ); tr_errno tr_cpBlockBitfieldSet( tr_completion *, struct tr_bitfield * ); -int tr_cpMissingBlocksInPiece( const tr_completion * cp, tr_piece_index_t piece ); +int tr_cpMissingBlocksInPiece( const tr_completion * cp, + tr_piece_index_t piece ); const struct tr_bitfield * tr_cpPieceBitfield( const tr_completion* ); diff --git a/libtransmission/fastresume.c b/libtransmission/fastresume.c index 5163f79f4..c70f58ada 100644 --- a/libtransmission/fastresume.c +++ b/libtransmission/fastresume.c @@ -430,6 +430,7 @@ parseProgress( tr_torrent * tor, /* get the completion bitfield */ memset( &bitfield, 0, sizeof bitfield ); bitfield.byteCount = FR_BLOCK_BITFIELD_LEN( tor ); + bitfield.bitCount = bitfield.byteCount * 8; bitfield.bits = (uint8_t*) walk; if( !tr_cpBlockBitfieldSet( tor->completion, &bitfield ) ) ret = TR_FR_PROGRESS; diff --git a/libtransmission/resume.c b/libtransmission/resume.c index ecc072a53..db98b95ee 100644 --- a/libtransmission/resume.c +++ b/libtransmission/resume.c @@ -320,6 +320,7 @@ loadProgress( tr_benc * dict, tr_torrent * tor ) { tr_bitfield tmp; tmp.byteCount = b->val.s.i; + tmp.bitCount = tmp.byteCount * 8; tmp.bits = (uint8_t*) b->val.s.s; if( tr_cpBlockBitfieldSet( tor->completion, &tmp ) ) { tr_torrentUncheck( tor ); diff --git a/libtransmission/utils-test.c b/libtransmission/utils-test.c index d061aedcd..6c36bb726 100644 --- a/libtransmission/utils-test.c +++ b/libtransmission/utils-test.c @@ -33,6 +33,7 @@ test_bitfields( void ) { int i; int bitcount = 5000000; + size_t pos; tr_bitfield * field = tr_bitfieldNew( bitcount ); /* make every seventh one true */ @@ -44,6 +45,27 @@ test_bitfields( void ) for( i=0; i>= 4; + if ( val & 0xCU ) pos |= 2, val >>= 2; + if ( val & 0x2 ) pos |= 1; + return 7 - pos; +} + +int +tr_bitfieldFindTrue( const tr_bitfield * bitfield, + size_t startBit, + size_t * setmePos ) +{ + if( bitfield && bitfield->bits && startBit < bitfield->bitCount ) + { + const uint8_t * b = bitfield->bits + startBit/8; + const uint8_t * end = bitfield->bits + bitfield->byteCount; + + /* If first byte already contains a set bit after startBit*/ + if( *b & ( 0xff >> (startBit&7) ) ) { + *setmePos = 8 * ( b - bitfield->bits ); + *setmePos += find_top_bit( *b & ( 0xff >> (startBit&7) ) ); + return 1; + } + + /* Test bitfield for first non zero byte */ + ++b; + while( (b < end) && !*b ) + ++b; + + /* If we hit the end of our bitfield, no set bit was found */ + if( b == end ) + return 0; + + /* New bitposition is byteoff*8 */ + *setmePos = 8 * ( b - bitfield->bits ) + find_top_bit( *b ); + + return 1; + } + + return 0; +} + int tr_bitfieldAdd( tr_bitfield * bitfield, size_t nth ) { diff --git a/libtransmission/utils.h b/libtransmission/utils.h index c48c4a1bf..e9d1d992d 100644 --- a/libtransmission/utils.h +++ b/libtransmission/utils.h @@ -263,6 +263,14 @@ size_t tr_bitfieldCountTrueBits( const tr_bitfield* ); tr_bitfield* tr_bitfieldOr( tr_bitfield*, const tr_bitfield* ); +/** @brief finds the first true bit in the bitfield, starting at `startPos' + @param setmePos the position of the true bit, if found, is set here. + @return nonzero if a true bit was found */ +int tr_bitfieldFindTrue( const tr_bitfield * bitfield, + size_t startPos, + size_t * setmePos ); + + /** A stripped-down version of bitfieldHas to be used for speed when you're looping quickly. This version has none of tr_bitfieldHas()'s safety checks, so you -- 2.40.0