source: trunk/libtransmission/bitfield.c @ 11599

Last change on this file since 11599 was 11599, checked in by charles, 11 years ago

(trunk) Join the 21st century and use only 1 space at the end sentences. This commit is nearly as important as the semi-annual ones that remove trailing spaces from the ends of lines of code... :)

  • Property svn:keywords set to Date Rev Author Id
File size: 5.4 KB
Line 
1/*
2 * This file Copyright (C) 2009-2010 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 11599 2010-12-27 19:18:17Z charles $
11 */
12
13#include <assert.h>
14#include <string.h> /* memset */
15
16#include "transmission.h"
17#include "bitfield.h"
18#include "bitset.h"
19
20tr_bitfield*
21tr_bitfieldConstruct( tr_bitfield * b, size_t bitCount )
22{
23    b->bitCount = bitCount;
24    b->byteCount = ( bitCount + 7u ) / 8u;
25    b->bits = tr_new0( uint8_t, b->byteCount );
26    return b;
27}
28
29tr_bitfield*
30tr_bitfieldDestruct( tr_bitfield * b )
31{
32    if( b )
33        tr_free( b->bits );
34    return b;
35}
36
37tr_bitfield*
38tr_bitfieldDup( const tr_bitfield * in )
39{
40    tr_bitfield * ret = tr_new0( tr_bitfield, 1 );
41
42    ret->bitCount = in->bitCount;
43    ret->byteCount = in->byteCount;
44    ret->bits = tr_memdup( in->bits, in->byteCount );
45    return ret;
46}
47
48void
49tr_bitfieldClear( tr_bitfield * bitfield )
50{
51    memset( bitfield->bits, 0, bitfield->byteCount );
52}
53
54int
55tr_bitfieldIsEmpty( const tr_bitfield * bitfield )
56{
57    size_t i;
58
59    for( i = 0; i < bitfield->byteCount; ++i )
60        if( bitfield->bits[i] )
61            return 0;
62
63    return 1;
64}
65
66int
67tr_bitfieldAdd( tr_bitfield * bitfield,
68                size_t        nth )
69{
70    assert( bitfield );
71    assert( bitfield->bits );
72
73    if( nth >= bitfield->bitCount )
74        return -1;
75
76    bitfield->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
77    return 0;
78}
79
80/* Sets bit range [begin, end) to 1 */
81int
82tr_bitfieldAddRange( tr_bitfield * b,
83                     size_t        begin,
84                     size_t        end )
85{
86    size_t        sb, eb;
87    unsigned char sm, em;
88
89    end--;
90
91    if( ( end >= b->bitCount ) || ( begin > end ) )
92        return -1;
93
94    sb = begin >> 3;
95    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
96    eb = end >> 3;
97    em = 0xff << ( 7 - ( end & 7 ) );
98
99    if( sb == eb )
100    {
101        b->bits[sb] |= ( sm & em );
102    }
103    else
104    {
105        b->bits[sb] |= sm;
106        b->bits[eb] |= em;
107        if( ++sb < eb )
108            memset ( b->bits + sb, 0xff, eb - sb );
109    }
110
111    return 0;
112}
113
114int
115tr_bitfieldRem( tr_bitfield * bitfield,
116                size_t        nth )
117{
118    assert( bitfield );
119    assert( bitfield->bits );
120
121    if( nth >= bitfield->bitCount )
122        return -1;
123
124    bitfield->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
125    return 0;
126}
127
128/* Clears bit range [begin, end) to 0 */
129int
130tr_bitfieldRemRange( tr_bitfield * b,
131                     size_t        begin,
132                     size_t        end )
133{
134    size_t        sb, eb;
135    unsigned char sm, em;
136
137    end--;
138
139    if( ( end >= b->bitCount ) || ( begin > end ) )
140        return -1;
141
142    sb = begin >> 3;
143    sm = 0xff << ( 8 - ( begin & 7 ) );
144    eb = end >> 3;
145    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
146
147    if( sb == eb )
148    {
149        b->bits[sb] &= ( sm | em );
150    }
151    else
152    {
153        b->bits[sb] &= sm;
154        b->bits[eb] &= em;
155        if( ++sb < eb )
156            memset ( b->bits + sb, 0, eb - sb );
157    }
158
159    return 0;
160}
161
162tr_bitfield*
163tr_bitfieldOr( tr_bitfield * a, const tr_bitfield * b )
164{
165    uint8_t * ait = a->bits;
166    const uint8_t * aend = ait + a->byteCount;
167    const uint8_t * bit = b->bits;
168    const uint8_t * bend = bit + b->byteCount;
169
170    while( ait!=aend && bit!=bend )
171        *ait++ |= *bit++;
172
173    return a;
174}
175
176/* set 'a' to all the flags that were in 'a' but not 'b' */
177void
178tr_bitfieldDifference( tr_bitfield * a, const tr_bitfield * b )
179{
180    uint8_t * ait = a->bits;
181    const uint8_t * aend = ait + a->byteCount;
182    const uint8_t * bit = b->bits;
183    const uint8_t * bend = bit + b->byteCount;
184
185    while( ait!=aend && bit!=bend )
186        *ait++ &= ~( *bit++ );
187}
188
189size_t
190tr_bitfieldCountTrueBits( const tr_bitfield* b )
191{
192    size_t           ret = 0;
193    const uint8_t *  it, *end;
194    static const int trueBitCount[256] = {
195        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
196        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
197        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
198        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
199        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
200        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
201        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
202        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
203    };
204
205    if( !b )
206        return 0;
207
208    for( it = b->bits, end = it + b->byteCount; it != end; ++it )
209        ret += trueBitCount[*it];
210
211    return ret;
212}
213
214/***
215****
216***/
217
218void
219tr_bitsetReserve( tr_bitset * b, size_t size )
220{
221    if( b->bitfield.bitCount < size )
222    {
223        tr_bitfield * tmp = tr_bitfieldDup( &b->bitfield );
224
225        tr_bitfieldDestruct( &b->bitfield );
226        tr_bitfieldConstruct( &b->bitfield, size );
227
228        if( ( tmp->bits != NULL ) && ( tmp->byteCount > 0 ) )
229            memcpy( b->bitfield.bits, tmp->bits, tmp->byteCount );
230
231        tr_bitfieldFree( tmp );
232    }
233}
Note: See TracBrowser for help on using the repository browser.