source: trunk/libtransmission/bitfield.c @ 12262

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

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

  • Property svn:keywords set to Date Rev Author Id
File size: 9.1 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 12262 2011-03-30 04:14: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
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
67countRange( const tr_bitfield * b, size_t begin, size_t end )
68{
69    size_t ret = 0;
70    const size_t first_byte = begin >> 3u;
71    const size_t last_byte = ( end - 1 ) >> 3u;
72
73    if( !b->bit_count )
74        return 0;
75    if( first_byte >= b->alloc_count )
76        return 0;
77
78    assert( begin < end );
79    assert( b->bits != NULL );
80
81    if( first_byte == last_byte )
82    {
83        int i;
84        uint8_t val = b->bits[first_byte];
85
86        i = begin - (first_byte * 8);
87        val <<= i;
88        val >>= i;
89        i = (last_byte+1)*8 - end;
90        val >>= i;
91        val <<= i;
92
93        ret += trueBitCount[val];
94    }
95    else
96    {
97        size_t i;
98        uint8_t val;
99
100        /* first byte */
101        i = begin - (first_byte * 8);
102        val = b->bits[first_byte];
103        val <<= i;
104        val >>= i;
105        ret += trueBitCount[val];
106
107        /* middle bytes */
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]];
111
112        /* last byte */
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        }
120    }
121
122    assert( ret <= ( begin - end ) );
123    return ret;
124}
125
126size_t
127tr_bitfieldCountRange( const tr_bitfield * b, size_t begin, size_t end )
128{
129    if( tr_bitfieldHasAll( b ) )
130        return end - begin;
131
132    if( tr_bitfieldHasNone( b ) )
133        return 0;
134
135    return countRange( b, begin, end );
136}
137
138/***
139****
140***/
141
142static bool
143tr_bitfieldIsValid( const tr_bitfield * b )
144{
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);
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    assert( tr_bitfieldIsValid(  b ) );
307
308    if( !tr_bitfieldHas( b, nth ) )
309    {
310        tr_bitfieldEnsureBitsAlloced( b, nth );
311        b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
312        tr_bitfieldIncTrueCount( b, 1 );
313    }
314    assert( tr_bitfieldIsValid(  b ) );
315}
316
317/* Sets bit range [begin, end) to 1 */
318void
319tr_bitfieldAddRange( tr_bitfield * b, size_t begin, size_t end )
320{
321    size_t sb, eb;
322    unsigned char sm, em;
323    const size_t diff = (end-begin) - tr_bitfieldCountRange( b, begin, end );
324
325    if( diff == 0 )
326        return;
327
328    end--;
329    if( ( end >= b->bit_count ) || ( begin > end ) )
330        return;
331
332    sb = begin >> 3;
333    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
334    eb = end >> 3;
335    em = 0xff << ( 7 - ( end & 7 ) );
336
337    tr_bitfieldEnsureBitsAlloced( b, end );
338    if( sb == eb )
339    {
340        b->bits[sb] |= ( sm & em );
341    }
342    else
343    {
344        b->bits[sb] |= sm;
345        b->bits[eb] |= em;
346        if( ++sb < eb )
347            memset ( b->bits + sb, 0xff, eb - sb );
348    }
349
350    tr_bitfieldIncTrueCount( b, diff );
351}
352
353void
354tr_bitfieldRem( tr_bitfield * b, size_t nth )
355{
356    assert( tr_bitfieldIsValid( b ) );
357
358    if( !tr_bitfieldHas( b, nth ) )
359    {
360        tr_bitfieldEnsureBitsAlloced( b, nth );
361        b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
362        tr_bitfieldIncTrueCount( b, -1 );
363    }
364}
365
366/* Clears bit range [begin, end) to 0 */
367void
368tr_bitfieldRemRange( tr_bitfield * b, size_t begin, size_t end )
369{
370    size_t sb, eb;
371    unsigned char sm, em;
372    const size_t diff = tr_bitfieldCountRange( b, begin, end );
373
374    if( !diff )
375        return;
376
377    end--;
378
379    if( ( end >= b->bit_count ) || ( begin > end ) )
380        return;
381
382    sb = begin >> 3;
383    sm = 0xff << ( 8 - ( begin & 7 ) );
384    eb = end >> 3;
385    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
386
387    tr_bitfieldEnsureBitsAlloced( b, end );
388    if( sb == eb )
389    {
390        b->bits[sb] &= ( sm | em );
391    }
392    else
393    {
394        b->bits[sb] &= sm;
395        b->bits[eb] &= em;
396        if( ++sb < eb )
397            memset ( b->bits + sb, 0, eb - sb );
398    }
399
400    tr_bitfieldIncTrueCount( b, -diff );
401}
Note: See TracBrowser for help on using the repository browser.