source: trunk/libtransmission/bitfield.c @ 12326

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

(trunk libT) remove an assertion from bitfield that doesn't always need to be true

  • 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 12326 2011-04-06 04:55:57Z 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
174    if( b->alloc_count )
175        memcpy( bits, b->bits, b->alloc_count );
176    else if( tr_bitfieldHasAll( b ) )
177        set_all_true( bits, b->bit_count );
178
179    *byte_count = n;
180    return bits;
181}
182
183static void
184tr_bitfieldEnsureBitsAlloced( tr_bitfield * b, size_t nth )
185{
186    size_t bytes_needed;
187    const bool has_all = tr_bitfieldHasAll( b );
188
189    assert( tr_bitfieldIsValid( b ) );
190
191    if( has_all )
192        bytes_needed = get_bytes_needed( MAX( nth, b->true_count ) + 1 );
193    else
194        bytes_needed = get_bytes_needed( nth + 1 );
195
196    if( b->alloc_count < bytes_needed )
197    {
198        const size_t old_count = countArray( b );
199        b->bits = tr_renew( uint8_t, b->bits, bytes_needed );
200        memset( b->bits + b->alloc_count, 0, bytes_needed - b->alloc_count );
201        b->alloc_count = bytes_needed;
202        assert( old_count == countArray( b ) );
203
204        if( has_all )
205            set_all_true( b->bits, b->true_count );
206    }
207
208    assert( tr_bitfieldIsValid( b ) );
209}
210
211static void
212tr_bitfieldFreeArray( tr_bitfield * b )
213{
214    tr_free( b->bits );
215    b->bits = NULL;
216    b->alloc_count = 0;
217}
218
219static void
220tr_bitfieldSetTrueCount( tr_bitfield * b, size_t n )
221{
222    b->true_count = n;
223
224    if( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) )
225        tr_bitfieldFreeArray( b );
226
227    assert( tr_bitfieldIsValid(  b ) );
228}
229
230static void
231tr_bitfieldRebuildTrueCount( tr_bitfield * b )
232{
233    tr_bitfieldSetTrueCount( b, countArray( b ) );
234}
235
236static void
237tr_bitfieldIncTrueCount( tr_bitfield * b, int i )
238{
239    tr_bitfieldSetTrueCount( b, b->true_count + i );
240}
241
242/****
243*****
244****/
245
246void
247tr_bitfieldConstruct( tr_bitfield * b, size_t bit_count )
248{
249    b->bit_count = bit_count;
250    b->true_count = 0;
251    b->bits = NULL;
252    b->alloc_count = 0;
253    b->have_all_hint = false;
254    b->have_none_hint = false;
255
256    assert( tr_bitfieldIsValid( b ) );
257}
258
259void
260tr_bitfieldSetHasNone( tr_bitfield * b )
261{
262    tr_bitfieldFreeArray( b );
263    b->true_count = 0;
264    b->have_all_hint = false;
265    b->have_none_hint = true;
266
267    assert( tr_bitfieldIsValid( b ) );
268}
269
270void
271tr_bitfieldSetHasAll( tr_bitfield * b )
272{
273    tr_bitfieldFreeArray( b );
274    b->true_count = b->bit_count;
275    b->have_all_hint = true;
276    b->have_none_hint = false;
277
278    assert( tr_bitfieldIsValid( b ) );
279}
280
281void
282tr_bitfieldSetFromBitfield( tr_bitfield * b, const tr_bitfield * src )
283{
284    if( tr_bitfieldHasAll( src ) )
285        tr_bitfieldSetHasAll( b );
286    else if( tr_bitfieldHasNone( src ) )
287        tr_bitfieldSetHasNone( b );
288    else
289        tr_bitfieldSetRaw( b, src->bits, src->alloc_count );
290}
291
292void
293tr_bitfieldSetRaw( tr_bitfield * b, const void * bits, size_t byte_count )
294{
295    tr_bitfieldFreeArray( b );
296    b->true_count = 0;
297    b->bits = tr_memdup( bits, byte_count );
298    b->alloc_count = byte_count;
299    tr_bitfieldRebuildTrueCount( b );
300}
301
302void
303tr_bitfieldAdd( tr_bitfield * b, size_t nth )
304{
305    if( !tr_bitfieldHas( b, nth ) )
306    {
307        tr_bitfieldEnsureBitsAlloced( b, nth );
308        b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
309        tr_bitfieldIncTrueCount( b, 1 );
310    }
311}
312
313/* Sets bit range [begin, end) to 1 */
314void
315tr_bitfieldAddRange( tr_bitfield * b, size_t begin, size_t end )
316{
317    size_t sb, eb;
318    unsigned char sm, em;
319    const size_t diff = (end-begin) - tr_bitfieldCountRange( b, begin, end );
320
321    if( diff == 0 )
322        return;
323
324    end--;
325    if( ( end >= b->bit_count ) || ( begin > end ) )
326        return;
327
328    sb = begin >> 3;
329    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
330    eb = end >> 3;
331    em = 0xff << ( 7 - ( end & 7 ) );
332
333    tr_bitfieldEnsureBitsAlloced( b, end );
334    if( sb == eb )
335    {
336        b->bits[sb] |= ( sm & em );
337    }
338    else
339    {
340        b->bits[sb] |= sm;
341        b->bits[eb] |= em;
342        if( ++sb < eb )
343            memset ( b->bits + sb, 0xff, eb - sb );
344    }
345
346    tr_bitfieldIncTrueCount( b, diff );
347}
348
349void
350tr_bitfieldRem( tr_bitfield * b, size_t nth )
351{
352    assert( tr_bitfieldIsValid( b ) );
353
354    if( !tr_bitfieldHas( b, nth ) )
355    {
356        tr_bitfieldEnsureBitsAlloced( b, nth );
357        b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
358        tr_bitfieldIncTrueCount( b, -1 );
359    }
360}
361
362/* Clears bit range [begin, end) to 0 */
363void
364tr_bitfieldRemRange( tr_bitfield * b, size_t begin, size_t end )
365{
366    size_t sb, eb;
367    unsigned char sm, em;
368    const size_t diff = tr_bitfieldCountRange( b, begin, end );
369
370    if( !diff )
371        return;
372
373    end--;
374
375    if( ( end >= b->bit_count ) || ( begin > end ) )
376        return;
377
378    sb = begin >> 3;
379    sm = 0xff << ( 8 - ( begin & 7 ) );
380    eb = end >> 3;
381    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
382
383    tr_bitfieldEnsureBitsAlloced( b, end );
384    if( sb == eb )
385    {
386        b->bits[sb] &= ( sm | em );
387    }
388    else
389    {
390        b->bits[sb] &= sm;
391        b->bits[eb] &= em;
392        if( ++sb < eb )
393            memset ( b->bits + sb, 0, eb - sb );
394    }
395
396    tr_bitfieldIncTrueCount( b, -diff );
397}
Note: See TracBrowser for help on using the repository browser.