Changeset 6072


Ignore:
Timestamp:
Jun 7, 2008, 2:41:31 PM (13 years ago)
Author:
charles
Message:

add first draft of tr_bitfieldFindTrue() courtesy of erdgeist

Location:
trunk/libtransmission
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/completion.c

    r6071 r6072  
    181181
    182182int
     183tr_cpBlockFindComplete( const tr_completion * cp,
     184                        size_t                startPos,
     185                        size_t              * foundPos )
     186{
     187    return tr_bitfieldFindTrue( cp->blockBitfield, startPos, foundPos );
     188}
     189
     190int
    183191tr_cpBlockIsComplete( const tr_completion * cp, tr_block_index_t block )
    184192{
     
    233241
    234242    tr_cpReset( cp );
    235     for( i=0; i < cp->tor->blockCount; ++i )
    236         if( tr_bitfieldHas( bitfield, i ) )
    237             tr_cpBlockAdd( cp, i );
     243    i = 0;
     244    while( tr_bitfieldFindTrue( bitfield, i, &i ) )
     245        tr_cpBlockAdd( cp, i++ );
    238246
    239247    return 0;
  • trunk/libtransmission/completion.h

    r5682 r6072  
    5454/* Blocks */
    5555int              tr_cpBlockIsComplete( const tr_completion *, tr_block_index_t block );
     56int              tr_cpBlockFindComplete( const tr_completion * cp,
     57                                         size_t startPos, size_t* foundPos );
    5658void             tr_cpBlockAdd( tr_completion *, tr_block_index_t block );
    5759tr_errno         tr_cpBlockBitfieldSet( tr_completion *, struct tr_bitfield * );
    58 int              tr_cpMissingBlocksInPiece( const tr_completion * cp, tr_piece_index_t piece );
     60int              tr_cpMissingBlocksInPiece( const tr_completion * cp,
     61                                            tr_piece_index_t piece );
    5962
    6063
  • trunk/libtransmission/fastresume.c

    r6071 r6072  
    431431        memset( &bitfield, 0, sizeof bitfield );
    432432        bitfield.byteCount = FR_BLOCK_BITFIELD_LEN( tor );
     433        bitfield.bitCount = bitfield.byteCount * 8;
    433434        bitfield.bits = (uint8_t*) walk;
    434435        if( !tr_cpBlockBitfieldSet( tor->completion, &bitfield ) )
  • trunk/libtransmission/resume.c

    r6071 r6072  
    321321            tr_bitfield tmp;
    322322            tmp.byteCount = b->val.s.i;
     323            tmp.bitCount = tmp.byteCount * 8;
    323324            tmp.bits = (uint8_t*) b->val.s.s;
    324325            if( tr_cpBlockBitfieldSet( tor->completion, &tmp ) ) {
  • trunk/libtransmission/utils-test.c

    r6004 r6072  
    3434    int i;
    3535    int bitcount = 5000000;
     36    size_t pos;
    3637    tr_bitfield * field = tr_bitfieldNew( bitcount );
    3738
     
    4445    for( i=0; i<bitcount; ++i )
    4546        check( tr_bitfieldHas( field, i ) == (!(i%7)) );
     47
     48    /* testing the "find next" function */
     49    check( tr_bitfieldFindTrue( field, 0, &pos ) );
     50    check( pos == 0 );
     51    check( tr_bitfieldFindTrue( field, 1, &pos ) );
     52    check( pos == 7 );
     53    check( tr_bitfieldFindTrue( field, 2, &pos ) );
     54    check( pos == 7 );
     55    check( tr_bitfieldFindTrue( field, 7, &pos ) );
     56    check( pos == 7 );
     57    check( tr_bitfieldFindTrue( field, 8, &pos ) );
     58    check( pos == 14 );
     59    check( tr_bitfieldFindTrue( field, 13, &pos ) );
     60    check( pos == 14 );
     61    check( tr_bitfieldFindTrue( field, 14, &pos ) );
     62    check( pos == 14 );
     63    check( tr_bitfieldFindTrue( field, 15, &pos ) );
     64    check( pos == 21 );
     65    check( tr_bitfieldFindTrue( field, 16, &pos ) );
     66    check( pos == 21 );
     67
    4668
    4769    tr_bitfieldFree( field );
  • trunk/libtransmission/utils.c

    r6071 r6072  
    733733}
    734734
     735static int
     736find_top_bit( uint8_t val )
     737{
     738    int pos = 0;
     739    if ( val & 0xF0U ) pos |= 4, val >>= 4;
     740    if ( val & 0xCU )  pos |= 2, val >>= 2;
     741    if ( val & 0x2 )   pos |= 1;
     742    return 7 - pos;
     743}
     744
     745int
     746tr_bitfieldFindTrue( const tr_bitfield  * bitfield,
     747                     size_t               startBit,
     748                     size_t             * setmePos )
     749{
     750    if( bitfield && bitfield->bits && startBit < bitfield->bitCount )
     751    {
     752        const uint8_t * b   = bitfield->bits + startBit/8;
     753        const uint8_t * end = bitfield->bits + bitfield->byteCount;
     754
     755        /* If first byte already contains a set bit after startBit*/
     756        if( *b & ( 0xff >> (startBit&7) ) ) {
     757            *setmePos  = 8 * ( b - bitfield->bits );
     758            *setmePos += find_top_bit( *b & ( 0xff >> (startBit&7) ) );
     759            return 1;
     760        }
     761
     762        /* Test bitfield for first non zero byte */
     763        ++b;
     764        while( (b < end) && !*b )
     765            ++b;
     766
     767        /* If we hit the end of our bitfield, no set bit was found */
     768        if( b == end )
     769            return 0;
     770
     771        /* New bitposition is byteoff*8 */
     772        *setmePos = 8 * ( b - bitfield->bits ) + find_top_bit( *b );
     773
     774        return 1;
     775    }
     776
     777    return 0;
     778}
     779
    735780int
    736781tr_bitfieldAdd( tr_bitfield  * bitfield, size_t nth )
  • trunk/libtransmission/utils.h

    r6071 r6072  
    264264tr_bitfield* tr_bitfieldOr( tr_bitfield*, const tr_bitfield* );
    265265
     266/** @brief finds the first true bit in the bitfield, starting at `startPos'
     267    @param setmePos the position of the true bit, if found, is set here.
     268    @return nonzero if a true bit was found */
     269int tr_bitfieldFindTrue( const tr_bitfield  * bitfield,
     270                         size_t               startPos,
     271                         size_t             * setmePos );
     272
     273
    266274/** A stripped-down version of bitfieldHas to be used
    267275    for speed when you're looping quickly.  This version
Note: See TracChangeset for help on using the changeset viewer.