Ignore:
Timestamp:
Mar 30, 2011, 4:14:57 AM (11 years ago)
Author:
jordan
Message:

(trunk libT) handle situations where we don't know the bitfield's upper bound in advance. This comes up sometimes with magnet links.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/bitfield.c

    r12255 r12262  
    1212
    1313#include <assert.h>
     14#include <stdlib.h> /* realloc() */
    1415#include <string.h> /* memset */
    1516
     
    4546
    4647static size_t
     48countArray( const tr_bitfield * b )
     49{
     50    size_t i;
     51    size_t ret = 0;
     52
     53    for( i=0; i<b->alloc_count; ++i )
     54        ret += trueBitCount[b->bits[i]];
     55
     56    return ret;
     57}
     58
     59size_t
     60tr_bitfieldCountTrueBits( const tr_bitfield * b )
     61{
     62    assert( b->true_count == ( b->bit_count ? tr_bitfieldCountRange( b, 0, b->bit_count ) : countArray ( b ) ) );
     63    return b->true_count;
     64}
     65
     66static size_t
    4767countRange( const tr_bitfield * b, size_t begin, size_t end )
    4868{
    4969    size_t ret = 0;
    50     const int first_byte = begin >> 3u;
    51     const int last_byte = ( end - 1 ) >> 3u;
     70    const size_t first_byte = begin >> 3u;
     71    const size_t last_byte = ( end - 1 ) >> 3u;
    5272
    5373    if( !b->bit_count )
     74        return 0;
     75    if( first_byte >= b->alloc_count )
    5476        return 0;
    5577
     
    7395    else
    7496    {
    75         int i;
     97        size_t i;
    7698        uint8_t val;
    7799
     
    84106
    85107        /* middle bytes */
    86         for( i=first_byte+1; i<last_byte; ++i )
    87             ret += trueBitCount[b->bits[i]];
     108        for( i=first_byte+1; i<b->alloc_count && i<last_byte; ++i )
     109            if( trueBitCount[b->bits[i]] )
     110                ret += trueBitCount[b->bits[i]];
    88111
    89112        /* last byte */
    90         i = (last_byte+1)*8 - end;
    91         val = b->bits[last_byte];
    92         val >>= i;
    93         val <<= i;
    94         ret += trueBitCount[val];
     113        if( last_byte < b->alloc_count ) {
     114            i = (last_byte+1)*8 - end;
     115            val = b->bits[last_byte];
     116            val >>= i;
     117            val <<= i;
     118            ret += trueBitCount[val];
     119        }
    95120    }
    96121
     
    118143tr_bitfieldIsValid( const tr_bitfield * b )
    119144{
    120     return ( b != NULL )
    121         && ( b->byte_count <= b->bit_count )
    122         && ( b->true_count <= b->bit_count )
    123         && ( !b->bits || ( b->true_count == countRange( b, 0, b->bit_count )));
     145    assert( b != NULL );
     146    assert( ( b->alloc_count == 0 ) == ( b->bits == 0 ) );
     147    assert( !b->bits || ( b->true_count == countArray ( b ) ) );
     148    return true;
     149}
     150
     151static size_t
     152get_bytes_needed( size_t bit_count )
     153{
     154    return ( bit_count + 7u ) / 8u;
     155}
     156
     157static void
     158set_all_true( uint8_t * array, size_t bit_count )
     159{
     160    const uint8_t val = 0xFF;
     161    const size_t n = get_bytes_needed( bit_count );
     162    memset( array, val, n-1 );
     163    array[n-1] = val << (n*8 - bit_count);
    124164}
    125165
     
    127167tr_bitfieldGetRaw( const tr_bitfield * b, size_t * byte_count )
    128168{
    129     uint8_t * bits;
    130 
    131     if( b->bits )
    132     {
    133         bits = tr_memdup( b->bits, b->byte_count );
    134     }
     169    const size_t n = get_bytes_needed( b->bit_count );
     170    uint8_t * bits = tr_new0( uint8_t, n );
     171
     172    assert( b->bit_count > 0 );
     173    assert( n >= b->alloc_count );
     174
     175    if( b->alloc_count )
     176        memcpy( bits, b->bits, b->alloc_count );
     177    else if( tr_bitfieldHasAll( b ) )
     178        set_all_true( bits, b->bit_count );
     179
     180    *byte_count = n;
     181    return bits;
     182}
     183
     184static void
     185tr_bitfieldEnsureBitsAlloced( tr_bitfield * b, size_t nth )
     186{
     187    size_t bytes_needed;
     188    const bool has_all = tr_bitfieldHasAll( b );
     189
     190    assert( tr_bitfieldIsValid( b ) );
     191
     192    if( has_all )
     193        bytes_needed = get_bytes_needed( MAX( nth, b->true_count ) + 1 );
    135194    else
    136     {
    137         assert( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) );
    138 
    139         bits = tr_new0( uint8_t, b->byte_count );
    140 
    141         if( tr_bitfieldHasAll( b ) )
    142         {
    143             uint8_t val = 0xFF;
    144             const int n = b->byte_count - 1;
    145             memset( bits, val, n );
    146             bits[n] = val << (b->byte_count*8 - b->bit_count);
    147         }
    148     }
    149 
    150     *byte_count = b->byte_count;
    151     return bits;
    152 }
    153 
    154 static void
    155 tr_bitfieldEnsureBitsAlloced( tr_bitfield * b )
    156 {
    157     if( b->bits == NULL )
    158         b->bits = tr_bitfieldGetRaw( b, &b->byte_count );
    159 
    160     assert( tr_bitfieldIsValid( b ) );
     195        bytes_needed = get_bytes_needed( nth + 1 );
     196
     197    if( b->alloc_count < bytes_needed )
     198    {
     199        const size_t old_count = countArray( b );
     200        b->bits = tr_renew( uint8_t, b->bits, bytes_needed );
     201        memset( b->bits + b->alloc_count, 0, bytes_needed - b->alloc_count );
     202        b->alloc_count = bytes_needed;
     203        assert( old_count == countArray( b ) );
     204
     205        if( has_all )
     206            set_all_true( b->bits, b->true_count );
     207    }
     208
     209    assert( tr_bitfieldIsValid( b ) );
     210}
     211
     212static void
     213tr_bitfieldFreeArray( tr_bitfield * b )
     214{
     215    tr_free( b->bits );
     216    b->bits = NULL;
     217    b->alloc_count = 0;
    161218}
    162219
     
    167224
    168225    if( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) )
    169     {
    170         tr_free( b->bits );
    171         b->bits = NULL;
    172     }
     226        tr_bitfieldFreeArray( b );
    173227
    174228    assert( tr_bitfieldIsValid(  b ) );
     
    178232tr_bitfieldRebuildTrueCount( tr_bitfield * b )
    179233{
    180     tr_bitfieldSetTrueCount( b, countRange( b, 0, b->bit_count ) );
     234    tr_bitfieldSetTrueCount( b, countArray( b ) );
    181235}
    182236
     
    195249{
    196250    b->bit_count = bit_count;
    197     b->byte_count = ( bit_count + 7u ) / 8u;
    198251    b->true_count = 0;
    199252    b->bits = NULL;
     253    b->alloc_count = 0;
    200254    b->have_all_hint = false;
    201255    b->have_none_hint = false;
     
    204258}
    205259
    206 static void
    207 tr_bitfieldClear( tr_bitfield * b )
    208 {
    209     tr_free( b->bits );
    210     b->bits = NULL;
     260void
     261tr_bitfieldSetHasNone( tr_bitfield * b )
     262{
     263    tr_bitfieldFreeArray( b );
    211264    b->true_count = 0;
    212 
    213     assert( tr_bitfieldIsValid( b ) );
    214 }
    215 
    216 void
    217 tr_bitfieldSetHasNone( tr_bitfield * b )
    218 {
    219     tr_bitfieldClear( b );
    220265    b->have_all_hint = false;
    221266    b->have_none_hint = true;
     267
     268    assert( tr_bitfieldIsValid( b ) );
    222269}
    223270
     
    225272tr_bitfieldSetHasAll( tr_bitfield * b )
    226273{
    227     tr_bitfieldClear( b );
     274    tr_bitfieldFreeArray( b );
    228275    b->true_count = b->bit_count;
    229276    b->have_all_hint = true;
    230277    b->have_none_hint = false;
    231 }
    232 
    233 bool
     278
     279    assert( tr_bitfieldIsValid( b ) );
     280}
     281
     282void
    234283tr_bitfieldSetFromBitfield( tr_bitfield * b, const tr_bitfield * src )
    235284{
    236     bool success = true;
    237 
    238285    if( tr_bitfieldHasAll( src ) )
    239286        tr_bitfieldSetHasAll( b );
     
    241288        tr_bitfieldSetHasNone( b );
    242289    else
    243         success = tr_bitfieldSetRaw( b, src->bits, src->byte_count );
    244 
    245     return success;
    246 }
    247 
    248 bool
     290        tr_bitfieldSetRaw( b, src->bits, src->alloc_count );
     291}
     292
     293void
    249294tr_bitfieldSetRaw( tr_bitfield * b, const void * bits, size_t byte_count )
    250295{
    251     const bool success = b->byte_count == byte_count;
    252 
    253     if( success )
    254     {
    255         tr_bitfieldSetHasNone( b );
    256         b->bits = tr_memdup( bits, byte_count );
    257         tr_bitfieldRebuildTrueCount( b );
    258     }
    259 
    260     return success;
     296    tr_bitfieldFreeArray( b );
     297    b->true_count = 0;
     298    b->bits = tr_memdup( bits, byte_count );
     299    b->alloc_count = byte_count;
     300    tr_bitfieldRebuildTrueCount( b );
    261301}
    262302
     
    264304tr_bitfieldAdd( tr_bitfield * b, size_t nth )
    265305{
    266     assert( nth < b->bit_count );
     306    assert( tr_bitfieldIsValid(  b ) );
    267307
    268308    if( !tr_bitfieldHas( b, nth ) )
    269309    {
    270         tr_bitfieldEnsureBitsAlloced( b );
     310        tr_bitfieldEnsureBitsAlloced( b, nth );
    271311        b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
    272312        tr_bitfieldIncTrueCount( b, 1 );
    273313    }
     314    assert( tr_bitfieldIsValid(  b ) );
    274315}
    275316
     
    294335    em = 0xff << ( 7 - ( end & 7 ) );
    295336
    296     tr_bitfieldEnsureBitsAlloced( b );
     337    tr_bitfieldEnsureBitsAlloced( b, end );
    297338    if( sb == eb )
    298339    {
     
    317358    if( !tr_bitfieldHas( b, nth ) )
    318359    {
    319         tr_bitfieldEnsureBitsAlloced( b );
     360        tr_bitfieldEnsureBitsAlloced( b, nth );
    320361        b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
    321362        tr_bitfieldIncTrueCount( b, -1 );
     
    344385    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
    345386
    346     tr_bitfieldEnsureBitsAlloced( b );
     387    tr_bitfieldEnsureBitsAlloced( b, end );
    347388    if( sb == eb )
    348389    {
Note: See TracChangeset for help on using the changeset viewer.