source: trunk/libtransmission/bitfield.c @ 12310

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

(trunk libT) #4165 "crash on startup introduced in r12262" -- experimental commit

  • Property svn:keywords set to Date Rev Author Id
File size: 8.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 12310 2011-04-05 00:29:42Z jordan $
11 */
12
13#include <assert.h>
14#include <stdlib.h> /* realloc() */
15#include <string.h> /* memset */
16
17#include "transmission.h"
18#include "bitfield.h"
19#include "utils.h" /* tr_new0() */
20
21const tr_bitfield TR_BITFIELD_INIT = { NULL, 0, 0, 0, false, false };
22
23/****
24*****
25****/
26
27static const int8_t trueBitCount[256] =
28{
29    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
30    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
31    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
32    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
33    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
34    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
35    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
36    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
37    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
38    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
39    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
40    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
41    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
42    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
43    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
44    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
45};
46
47static 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
59static size_t
60countRange( const tr_bitfield * b, size_t begin, size_t end )
61{
62    size_t ret = 0;
63    const size_t first_byte = begin >> 3u;
64    const size_t last_byte = ( end - 1 ) >> 3u;
65
66    if( !b->bit_count )
67        return 0;
68    if( first_byte >= b->alloc_count )
69        return 0;
70
71    assert( begin < end );
72    assert( b->bits != NULL );
73
74    if( first_byte == last_byte )
75    {
76        int i;
77        uint8_t val = b->bits[first_byte];
78
79        i = begin - (first_byte * 8);
80        val <<= i;
81        val >>= i;
82        i = (last_byte+1)*8 - end;
83        val >>= i;
84        val <<= i;
85
86        ret += trueBitCount[val];
87    }
88    else
89    {
90        size_t i;
91        uint8_t val;
92
93        /* first byte */
94        i = begin - (first_byte * 8);
95        val = b->bits[first_byte];
96        val <<= i;
97        val >>= i;
98        ret += trueBitCount[val];
99
100        /* middle bytes */
101        for( i=first_byte+1; i<b->alloc_count && i<last_byte; ++i )
102            if( trueBitCount[b->bits[i]] )
103                ret += trueBitCount[b->bits[i]];
104
105        /* last byte */
106        if( last_byte < b->alloc_count ) {
107            i = (last_byte+1)*8 - end;
108            val = b->bits[last_byte];
109            val >>= i;
110            val <<= i;
111            ret += trueBitCount[val];
112        }
113    }
114
115    assert( ret <= ( begin - end ) );
116    return ret;
117}
118
119size_t
120tr_bitfieldCountRange( const tr_bitfield * b, size_t begin, size_t end )
121{
122    if( tr_bitfieldHasAll( b ) )
123        return end - begin;
124
125    if( tr_bitfieldHasNone( b ) )
126        return 0;
127
128    return countRange( b, begin, end );
129}
130
131/***
132****
133***/
134
135static bool
136tr_bitfieldIsValid( const tr_bitfield * b )
137{
138    assert( b != NULL );
139    assert( ( b->alloc_count == 0 ) == ( b->bits == 0 ) );
140    assert( !b->bits || ( b->true_count == countArray ( b ) ) );
141    return true;
142}
143
144size_t
145tr_bitfieldCountTrueBits( const tr_bitfield * b )
146{
147    tr_bitfieldIsValid( b );
148    return b->true_count;
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);
164}
165
166void*
167tr_bitfieldGetRaw( const tr_bitfield * b, size_t * byte_count )
168{
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 );
194    else
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;
218}
219
220static void
221tr_bitfieldSetTrueCount( tr_bitfield * b, size_t n )
222{
223    b->true_count = n;
224
225    if( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) )
226        tr_bitfieldFreeArray( b );
227
228    assert( tr_bitfieldIsValid(  b ) );
229}
230
231static void
232tr_bitfieldRebuildTrueCount( tr_bitfield * b )
233{
234    tr_bitfieldSetTrueCount( b, countArray( b ) );
235}
236
237static void
238tr_bitfieldIncTrueCount( tr_bitfield * b, int i )
239{
240    tr_bitfieldSetTrueCount( b, b->true_count + i );
241}
242
243/****
244*****
245****/
246
247void
248tr_bitfieldConstruct( tr_bitfield * b, size_t bit_count )
249{
250    b->bit_count = bit_count;
251    b->true_count = 0;
252    b->bits = NULL;
253    b->alloc_count = 0;
254    b->have_all_hint = false;
255    b->have_none_hint = false;
256
257    assert( tr_bitfieldIsValid( b ) );
258}
259
260void
261tr_bitfieldSetHasNone( tr_bitfield * b )
262{
263    tr_bitfieldFreeArray( b );
264    b->true_count = 0;
265    b->have_all_hint = false;
266    b->have_none_hint = true;
267
268    assert( tr_bitfieldIsValid( b ) );
269}
270
271void
272tr_bitfieldSetHasAll( tr_bitfield * b )
273{
274    tr_bitfieldFreeArray( b );
275    b->true_count = b->bit_count;
276    b->have_all_hint = true;
277    b->have_none_hint = false;
278
279    assert( tr_bitfieldIsValid( b ) );
280}
281
282void
283tr_bitfieldSetFromBitfield( tr_bitfield * b, const tr_bitfield * src )
284{
285    if( tr_bitfieldHasAll( src ) )
286        tr_bitfieldSetHasAll( b );
287    else if( tr_bitfieldHasNone( src ) )
288        tr_bitfieldSetHasNone( b );
289    else
290        tr_bitfieldSetRaw( b, src->bits, src->alloc_count );
291}
292
293void
294tr_bitfieldSetRaw( tr_bitfield * b, const void * bits, size_t byte_count )
295{
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 );
301}
302
303void
304tr_bitfieldAdd( tr_bitfield * b, size_t nth )
305{
306    if( !tr_bitfieldHas( b, nth ) )
307    {
308        tr_bitfieldEnsureBitsAlloced( b, nth );
309        b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
310        tr_bitfieldIncTrueCount( b, 1 );
311    }
312}
313
314/* Sets bit range [begin, end) to 1 */
315void
316tr_bitfieldAddRange( tr_bitfield * b, size_t begin, size_t end )
317{
318    size_t sb, eb;
319    unsigned char sm, em;
320    const size_t diff = (end-begin) - tr_bitfieldCountRange( b, begin, end );
321
322    if( diff == 0 )
323        return;
324
325    end--;
326    if( ( end >= b->bit_count ) || ( begin > end ) )
327        return;
328
329    sb = begin >> 3;
330    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
331    eb = end >> 3;
332    em = 0xff << ( 7 - ( end & 7 ) );
333
334    tr_bitfieldEnsureBitsAlloced( b, end );
335    if( sb == eb )
336    {
337        b->bits[sb] |= ( sm & em );
338    }
339    else
340    {
341        b->bits[sb] |= sm;
342        b->bits[eb] |= em;
343        if( ++sb < eb )
344            memset ( b->bits + sb, 0xff, eb - sb );
345    }
346
347    tr_bitfieldIncTrueCount( b, diff );
348}
349
350void
351tr_bitfieldRem( tr_bitfield * b, size_t nth )
352{
353    assert( tr_bitfieldIsValid( b ) );
354
355    if( !tr_bitfieldHas( b, nth ) )
356    {
357        tr_bitfieldEnsureBitsAlloced( b, nth );
358        b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
359        tr_bitfieldIncTrueCount( b, -1 );
360    }
361}
362
363/* Clears bit range [begin, end) to 0 */
364void
365tr_bitfieldRemRange( tr_bitfield * b, size_t begin, size_t end )
366{
367    size_t sb, eb;
368    unsigned char sm, em;
369    const size_t diff = tr_bitfieldCountRange( b, begin, end );
370
371    if( !diff )
372        return;
373
374    end--;
375
376    if( ( end >= b->bit_count ) || ( begin > end ) )
377        return;
378
379    sb = begin >> 3;
380    sm = 0xff << ( 8 - ( begin & 7 ) );
381    eb = end >> 3;
382    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
383
384    tr_bitfieldEnsureBitsAlloced( b, end );
385    if( sb == eb )
386    {
387        b->bits[sb] &= ( sm | em );
388    }
389    else
390    {
391        b->bits[sb] &= sm;
392        b->bits[eb] &= em;
393        if( ++sb < eb )
394            memset ( b->bits + sb, 0, eb - sb );
395    }
396
397    tr_bitfieldIncTrueCount( b, -diff );
398}
Note: See TracBrowser for help on using the repository browser.