source: trunk/libtransmission/bitfield.c @ 11280

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

(trunk) fix svn properties on several files. Thanks ot Elbandi for suggesting this

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