source: trunk/libtransmission/bitfield.c @ 12251

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

(trunk libT) more completion and bitfield cleanup: (1) fix regression in tr_cpSizeWhenDone() reported by Waldorf, (2) make simple one-liner functions inlined

  • Property svn:keywords set to Date Rev Author Id
File size: 7.8 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 12251 2011-03-29 01:17:18Z 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
205static void
206tr_bitfieldClear( tr_bitfield * b )
207{
208    tr_free( b->bits );
209    b->bits = NULL;
210    b->true_count = 0;
211
212    assert( tr_bitfieldIsValid( b ) );
213}
214
215void
216tr_bitfieldSetHasNone( tr_bitfield * b )
217{
218    tr_bitfieldClear( b );
219    b->have_all_hint = false;
220    b->have_none_hint = true;
221}
222
223void
224tr_bitfieldSetHasAll( tr_bitfield * b )
225{
226    tr_bitfieldClear( b );
227    b->true_count = b->bit_count;
228    b->have_all_hint = true;
229    b->have_none_hint = false;
230}
231
232bool
233tr_bitfieldSetFromBitfield( tr_bitfield * b, const tr_bitfield * src )
234{
235    bool success = true;
236
237    if( tr_bitfieldHasAll( src ) )
238        tr_bitfieldSetHasAll( b );
239    else if( tr_bitfieldHasNone( src ) )
240        tr_bitfieldSetHasNone( b );
241    else
242        success = tr_bitfieldSetRaw( b, src->bits, src->byte_count );
243
244    return success;
245}
246
247bool
248tr_bitfieldSetRaw( tr_bitfield * b, const void * bits, size_t byte_count )
249{
250    const bool success = b->byte_count == byte_count;
251
252    if( success )
253    {
254        tr_bitfieldSetHasNone( b );
255        b->bits = tr_memdup( bits, byte_count );
256        tr_bitfieldRebuildTrueCount( b );
257    }
258
259    return success;
260}
261
262void
263tr_bitfieldAdd( tr_bitfield * b, size_t nth )
264{
265    assert( nth < b->bit_count );
266
267    if( !tr_bitfieldHas( b, nth ) )
268    {
269        tr_bitfieldEnsureBitsAlloced( b );
270        b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
271        tr_bitfieldIncTrueCount( b, 1 );
272    }
273}
274
275/* Sets bit range [begin, end) to 1 */
276void
277tr_bitfieldAddRange( tr_bitfield * b, size_t begin, size_t end )
278{
279    size_t sb, eb;
280    unsigned char sm, em;
281    const size_t diff = (end-begin) - tr_bitfieldCountRange( b, begin, end );
282
283    if( diff == 0 )
284        return;
285
286    end--;
287    if( ( end >= b->bit_count ) || ( begin > end ) )
288        return;
289
290    sb = begin >> 3;
291    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
292    eb = end >> 3;
293    em = 0xff << ( 7 - ( end & 7 ) );
294
295    tr_bitfieldEnsureBitsAlloced( b );
296    if( sb == eb )
297    {
298        b->bits[sb] |= ( sm & em );
299    }
300    else
301    {
302        b->bits[sb] |= sm;
303        b->bits[eb] |= em;
304        if( ++sb < eb )
305            memset ( b->bits + sb, 0xff, eb - sb );
306    }
307
308    tr_bitfieldIncTrueCount( b, diff );
309}
310
311void
312tr_bitfieldRem( tr_bitfield * b, size_t nth )
313{
314    assert( tr_bitfieldIsValid( b ) );
315
316    if( !tr_bitfieldHas( b, nth ) )
317    {
318        tr_bitfieldEnsureBitsAlloced( b );
319        b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
320        tr_bitfieldIncTrueCount( b, -1 );
321    }
322}
323
324/* Clears bit range [begin, end) to 0 */
325void
326tr_bitfieldRemRange( tr_bitfield * b, size_t begin, size_t end )
327{
328    size_t sb, eb;
329    unsigned char sm, em;
330    const size_t diff = tr_bitfieldCountRange( b, begin, end );
331
332    if( !diff )
333        return;
334
335    end--;
336
337    if( ( end >= b->bit_count ) || ( begin > end ) )
338        return;
339
340    sb = begin >> 3;
341    sm = 0xff << ( 8 - ( begin & 7 ) );
342    eb = end >> 3;
343    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
344
345    tr_bitfieldEnsureBitsAlloced( b );
346    if( sb == eb )
347    {
348        b->bits[sb] &= ( sm | em );
349    }
350    else
351    {
352        b->bits[sb] &= sm;
353        b->bits[eb] &= em;
354        if( ++sb < eb )
355            memset ( b->bits + sb, 0, eb - sb );
356    }
357
358    tr_bitfieldIncTrueCount( b, -diff );
359}
Note: See TracBrowser for help on using the repository browser.