Ignore:
Timestamp:
Mar 28, 2011, 4:31:05 PM (11 years ago)
Author:
jordan
Message:

(trunk libT) break the mac build and introduce new crashes.

This is partially to address #4145 "Downloads stuck at 100%" by refactoring the bitset, bitfield, and tr_completion; however, the ripple effect is larger than usual so things may get worse in the short term before getting better.

livings124: to fix the mac build, remove bitset.[ch] from xcode

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/bitfield.c

    r12096 r12248  
    1616#include "transmission.h"
    1717#include "bitfield.h"
    18 #include "bitset.h"
    1918#include "utils.h" /* tr_new0() */
    2019
    21 const tr_bitfield TR_BITFIELD_INIT = { NULL, 0, 0 };
    22 
    23 tr_bitfield*
    24 tr_bitfieldConstruct( tr_bitfield * b, size_t bitCount )
    25 {
    26     b->bitCount = bitCount;
    27     b->byteCount = ( bitCount + 7u ) / 8u;
    28     b->bits = tr_new0( uint8_t, b->byteCount );
    29     return b;
    30 }
    31 
    32 tr_bitfield*
    33 tr_bitfieldDestruct( tr_bitfield * b )
    34 {
    35     if( b )
    36         tr_free( b->bits );
    37     return b;
    38 }
    39 
    40 tr_bitfield*
    41 tr_bitfieldNew( size_t bitCount )
    42 {
    43     return tr_bitfieldConstruct( tr_new( tr_bitfield, 1 ), bitCount );
    44 }
    45 
    46 void
    47 tr_bitfieldFree( tr_bitfield * b )
    48 {
    49     tr_free( tr_bitfieldDestruct( b ) );
    50 }
    51 
    52 void
    53 tr_bitfieldClear( tr_bitfield * bitfield )
    54 {
    55     memset( bitfield->bits, 0, bitfield->byteCount );
    56 }
    57 
    58 int
    59 tr_bitfieldAdd( tr_bitfield * bitfield,
    60                 size_t        nth )
    61 {
    62     assert( bitfield );
    63     assert( bitfield->bits );
    64 
    65     if( nth >= bitfield->bitCount )
    66         return -1;
    67 
    68     bitfield->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
    69     return 0;
    70 }
    71 
    72 /* Sets bit range [begin, end) to 1 */
    73 int
    74 tr_bitfieldAddRange( tr_bitfield * b,
    75                      size_t        begin,
    76                      size_t        end )
    77 {
    78     size_t        sb, eb;
    79     unsigned char sm, em;
    80 
    81     end--;
    82 
    83     if( ( end >= b->bitCount ) || ( begin > end ) )
    84         return -1;
    85 
    86     sb = begin >> 3;
    87     sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
    88     eb = end >> 3;
    89     em = 0xff << ( 7 - ( end & 7 ) );
    90 
    91     if( sb == eb )
    92     {
    93         b->bits[sb] |= ( sm & em );
    94     }
    95     else
    96     {
    97         b->bits[sb] |= sm;
    98         b->bits[eb] |= em;
    99         if( ++sb < eb )
    100             memset ( b->bits + sb, 0xff, eb - sb );
    101     }
    102 
    103     return 0;
    104 }
    105 
    106 int
    107 tr_bitfieldRem( tr_bitfield * bitfield,
    108                 size_t        nth )
    109 {
    110     assert( bitfield );
    111     assert( bitfield->bits );
    112 
    113     if( nth >= bitfield->bitCount )
    114         return -1;
    115 
    116     bitfield->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
    117     return 0;
    118 }
    119 
    120 /* Clears bit range [begin, end) to 0 */
    121 int
    122 tr_bitfieldRemRange( tr_bitfield * b,
    123                      size_t        begin,
    124                      size_t        end )
    125 {
    126     size_t        sb, eb;
    127     unsigned char sm, em;
    128 
    129     end--;
    130 
    131     if( ( end >= b->bitCount ) || ( begin > end ) )
    132         return -1;
    133 
    134     sb = begin >> 3;
    135     sm = 0xff << ( 8 - ( begin & 7 ) );
    136     eb = end >> 3;
    137     em = ~( 0xff << ( 7 - ( end & 7 ) ) );
    138 
    139     if( sb == eb )
    140     {
    141         b->bits[sb] &= ( sm | em );
    142     }
    143     else
    144     {
    145         b->bits[sb] &= sm;
    146         b->bits[eb] &= em;
    147         if( ++sb < eb )
    148             memset ( b->bits + sb, 0, eb - sb );
    149     }
    150 
    151     return 0;
    152 }
    153 
    154 tr_bitfield*
    155 tr_bitfieldOr( tr_bitfield * a, const tr_bitfield * b )
    156 {
    157     uint8_t * ait = a->bits;
    158     const uint8_t * aend = ait + a->byteCount;
    159     const uint8_t * bit = b->bits;
    160     const uint8_t * bend = bit + b->byteCount;
    161 
    162     while( ait!=aend && bit!=bend )
    163         *ait++ |= *bit++;
    164 
    165     return a;
    166 }
    167 
    168 static const int trueBitCount[256] =
     20const tr_bitfield TR_BITFIELD_INIT = { NULL, 0, 0, 0, false, false };
     21
     22/****
     23*****
     24****/
     25
     26static const int8_t trueBitCount[256] =
    16927{
    17028    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
     
    18644};
    18745
    188 size_t
    189 tr_bitfieldCountTrueBits( const tr_bitfield* b )
    190 {
    191     size_t           ret = 0;
    192     const uint8_t *  it, *end;
    193 
    194     if( !b )
    195         return 0;
    196 
    197     for( it = b->bits, end = it + b->byteCount; it != end; ++it )
    198         ret += trueBitCount[*it];
    199 
    200     return ret;
    201 }
    202 
    203 size_t
    204 tr_bitfieldCountRange( const tr_bitfield * b, size_t begin, size_t end )
     46static size_t
     47countRange( const tr_bitfield * b, size_t begin, size_t end )
    20548{
    20649    size_t ret = 0;
     
    20851    const int last_byte = ( end - 1 ) >> 3u;
    20952
    210     assert( begin < end );
     53    assert( b->bits != NULL );
    21154
    21255    if( first_byte == last_byte )
     
    25194    return ret;
    25295}
     96
     97size_t
     98tr_bitfieldCountRange( const tr_bitfield * b, size_t begin, size_t end )
     99{
     100    assert( begin < end );
     101
     102    if( tr_bitfieldHasAll( b ) )
     103        return end - begin;
     104
     105    if( tr_bitfieldHasNone( b ) )
     106        return 0;
     107
     108    return countRange( b, begin, end );
     109}
     110
     111/***
     112****
     113***/
     114
     115static bool
     116tr_bitfieldIsValid( const tr_bitfield * b )
     117{
     118    return ( b != NULL )
     119        && ( b->bits || ( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b )))
     120        && ( b->byte_count <= b->bit_count )
     121        && ( b->true_count <= b->bit_count )
     122        && ( !b->bits || ( b->true_count == countRange( b, 0, b->bit_count )));
     123}
     124
     125void*
     126tr_bitfieldGetRaw( const tr_bitfield * b, size_t * byte_count )
     127{
     128    uint8_t * bits;
     129
     130    if( b->bits )
     131    {
     132        bits = tr_memdup( b->bits, b->byte_count );
     133    }
     134    else
     135    {
     136        assert( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) );
     137
     138        bits = tr_new0( uint8_t, b->byte_count );
     139
     140        if( tr_bitfieldHasAll( b ) )
     141        {
     142            uint8_t val = 0xFF;
     143            const int n = b->byte_count - 1;
     144            memset( bits, val, n );
     145            bits[n] = val << (b->byte_count*8 - b->bit_count);
     146        }
     147    }
     148
     149    *byte_count = b->byte_count;
     150    return bits;
     151}
     152
     153static void
     154tr_bitfieldEnsureBitsAlloced( tr_bitfield * b )
     155{
     156    if( b->bits == NULL )
     157        b->bits = tr_bitfieldGetRaw( b, &b->byte_count );
     158
     159    assert( tr_bitfieldIsValid( b ) );
     160}
     161
     162static void
     163tr_bitfieldSetTrueCount( tr_bitfield * b, size_t n )
     164{
     165    b->true_count = n;
     166
     167    if( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) )
     168    {
     169        tr_free( b->bits );
     170        b->bits = NULL;
     171    }
     172
     173    assert( tr_bitfieldIsValid(  b ) );
     174}
     175
     176static void
     177tr_bitfieldRebuildTrueCount( tr_bitfield * b )
     178{
     179    tr_bitfieldSetTrueCount( b, countRange( b, 0, b->bit_count ) );
     180}
     181
     182static void
     183tr_bitfieldIncTrueCount( tr_bitfield * b, int i )
     184{
     185    tr_bitfieldSetTrueCount( b, b->true_count + i );
     186}
     187
     188/****
     189*****
     190****/
     191
     192void
     193tr_bitfieldConstruct( tr_bitfield * b, size_t bit_count )
     194{
     195    b->bit_count = bit_count;
     196    b->byte_count = ( bit_count + 7u ) / 8u;
     197    b->true_count = 0;
     198    b->bits = NULL;
     199    b->have_all_hint = false;
     200    b->have_none_hint = false;
     201
     202    assert( tr_bitfieldIsValid( b ) );
     203}
     204
     205void
     206tr_bitfieldDestruct( tr_bitfield * b )
     207{
     208    tr_bitfieldSetHasNone( b );
     209}
     210
     211static void
     212tr_bitfieldClear( tr_bitfield * b )
     213{
     214    tr_free( b->bits );
     215    b->bits = NULL;
     216    b->true_count = 0;
     217
     218    assert( tr_bitfieldIsValid( b ) );
     219}
     220
     221void
     222tr_bitfieldSetHasNone( tr_bitfield * b )
     223{
     224    tr_bitfieldClear( b );
     225    b->have_all_hint = false;
     226    b->have_none_hint = true;
     227}
     228
     229void
     230tr_bitfieldSetHasAll( tr_bitfield * b )
     231{
     232    tr_bitfieldClear( b );
     233    b->true_count = b->bit_count;
     234    b->have_all_hint = true;
     235    b->have_none_hint = false;
     236}
     237
     238bool
     239tr_bitfieldSetFromBitfield( tr_bitfield * b, const tr_bitfield * src )
     240{
     241    bool success = true;
     242
     243    if( tr_bitfieldHasAll( src ) )
     244        tr_bitfieldSetHasAll( b );
     245    else if( tr_bitfieldHasNone( src ) )
     246        tr_bitfieldSetHasNone( b );
     247    else
     248        success = tr_bitfieldSetRaw( b, src->bits, src->byte_count );
     249
     250    return success;
     251}
     252
     253bool
     254tr_bitfieldSetRaw( tr_bitfield * b, const void * bits, size_t byte_count )
     255{
     256    const bool success = b->byte_count == byte_count;
     257
     258    if( success )
     259    {
     260        tr_bitfieldSetHasNone( b );
     261        b->bits = tr_memdup( bits, byte_count );
     262        tr_bitfieldRebuildTrueCount( b );
     263    }
     264
     265    return success;
     266}
     267
     268void
     269tr_bitfieldAdd( tr_bitfield * b, size_t nth )
     270{
     271    assert( nth < b->bit_count );
     272
     273    if( !tr_bitfieldHas( b, nth ) )
     274    {
     275        tr_bitfieldEnsureBitsAlloced( b );
     276        b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
     277        tr_bitfieldIncTrueCount( b, 1 );
     278    }
     279}
     280
     281/* Sets bit range [begin, end) to 1 */
     282void
     283tr_bitfieldAddRange( tr_bitfield * b, size_t begin, size_t end )
     284{
     285    size_t sb, eb;
     286    unsigned char sm, em;
     287    const size_t diff = (end-begin) - tr_bitfieldCountRange( b, begin, end );
     288
     289    if( diff == 0 )
     290        return;
     291
     292    end--;
     293    if( ( end >= b->bit_count ) || ( begin > end ) )
     294        return;
     295
     296    sb = begin >> 3;
     297    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
     298    eb = end >> 3;
     299    em = 0xff << ( 7 - ( end & 7 ) );
     300
     301    tr_bitfieldEnsureBitsAlloced( b );
     302    if( sb == eb )
     303    {
     304        b->bits[sb] |= ( sm & em );
     305    }
     306    else
     307    {
     308        b->bits[sb] |= sm;
     309        b->bits[eb] |= em;
     310        if( ++sb < eb )
     311            memset ( b->bits + sb, 0xff, eb - sb );
     312    }
     313
     314    tr_bitfieldIncTrueCount( b, diff );
     315}
     316
     317void
     318tr_bitfieldRem( tr_bitfield * b, size_t nth )
     319{
     320    assert( tr_bitfieldIsValid( b ) );
     321
     322    if( !tr_bitfieldHas( b, nth ) )
     323    {
     324        tr_bitfieldEnsureBitsAlloced( b );
     325        b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
     326        tr_bitfieldIncTrueCount( b, -1 );
     327    }
     328}
     329
     330/* Clears bit range [begin, end) to 0 */
     331void
     332tr_bitfieldRemRange( tr_bitfield * b, size_t begin, size_t end )
     333{
     334    size_t sb, eb;
     335    unsigned char sm, em;
     336    const size_t diff = tr_bitfieldCountRange( b, begin, end );
     337
     338    if( !diff )
     339        return;
     340
     341    end--;
     342
     343    if( ( end >= b->bit_count ) || ( begin > end ) )
     344        return;
     345
     346    sb = begin >> 3;
     347    sm = 0xff << ( 8 - ( begin & 7 ) );
     348    eb = end >> 3;
     349    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
     350
     351    tr_bitfieldEnsureBitsAlloced( b );
     352    if( sb == eb )
     353    {
     354        b->bits[sb] &= ( sm | em );
     355    }
     356    else
     357    {
     358        b->bits[sb] &= sm;
     359        b->bits[eb] &= em;
     360        if( ++sb < eb )
     361            memset ( b->bits + sb, 0, eb - sb );
     362    }
     363
     364    tr_bitfieldIncTrueCount( b, -diff );
     365}
Note: See TracChangeset for help on using the changeset viewer.