source: trunk/libtransmission/bitfield.c @ 12006

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

(trunk libT) remove unused functions: tr_bitsetDifference() tr_bitfieldDifference()

  • Property svn:keywords set to Date Rev Author Id
File size: 4.6 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 12006 2011-02-21 15:36:07Z jordan $
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
176size_t
177tr_bitfieldCountTrueBits( const tr_bitfield* b )
178{
179    size_t           ret = 0;
180    const uint8_t *  it, *end;
181    static const int trueBitCount[256] = {
182        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,
183        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,
184        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,
185        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,
186        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,
187        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,
188        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,
189        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
190    };
191
192    if( !b )
193        return 0;
194
195    for( it = b->bits, end = it + b->byteCount; it != end; ++it )
196        ret += trueBitCount[*it];
197
198    return ret;
199}
Note: See TracBrowser for help on using the repository browser.