source: trunk/libtransmission/bitfield.c @ 12248

Last change on this file since 12248 was 12248, checked in by jordan, 11 years ago

(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

  • Property svn:keywords set to Date Rev Author Id
File size: 7.9 KB
Line 
1/*
2 * This file Copyright (C) Mnemosyne LLC
3 *
4 * This file is licensed by the GPL version 2. Works owned by the
5 * Transmission project are granted a special exemption to clause 2(b)
6 * so that the bulk of its code can remain under the MIT license.
7 * This exemption does not extend to derived works not owned by
8 * the Transmission project.
9 *
10 * $Id: bitfield.c 12248 2011-03-28 16:31:05Z jordan $
11 */
12
13#include <assert.h>
14#include <string.h> /* memset */
15
16#include "transmission.h"
17#include "bitfield.h"
18#include "utils.h" /* tr_new0() */
19
20const tr_bitfield TR_BITFIELD_INIT = { NULL, 0, 0, 0, false, false };
21
22/****
23*****
24****/
25
26static const int8_t trueBitCount[256] =
27{
28    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
29    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
30    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
31    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
32    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
33    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
34    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
35    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
36    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
37    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
38    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
39    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
40    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
41    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
42    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
43    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
44};
45
46static size_t
47countRange( const tr_bitfield * b, size_t begin, size_t end )
48{
49    size_t ret = 0;
50    const int first_byte = begin >> 3u;
51    const int last_byte = ( end - 1 ) >> 3u;
52
53    assert( b->bits != NULL );
54
55    if( first_byte == last_byte )
56    {
57        int i;
58        uint8_t val = b->bits[first_byte];
59
60        i = begin - (first_byte * 8);
61        val <<= i;
62        val >>= i;
63        i = (last_byte+1)*8 - end;
64        val >>= i;
65        val <<= i;
66
67        ret += trueBitCount[val];
68    }
69    else
70    {
71        int i;
72        uint8_t val;
73
74        /* first byte */
75        i = begin - (first_byte * 8);
76        val = b->bits[first_byte];
77        val <<= i;
78        val >>= i;
79        ret += trueBitCount[val];
80
81        /* middle bytes */
82        for( i=first_byte+1; i<last_byte; ++i )
83            ret += trueBitCount[b->bits[i]];
84
85        /* last byte */
86        i = (last_byte+1)*8 - end;
87        val = b->bits[last_byte];
88        val >>= i;
89        val <<= i;
90        ret += trueBitCount[val];
91    }
92
93    assert( ret <= ( begin - end ) );
94    return ret;
95}
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 TracBrowser for help on using the repository browser.