source: trunk/libtransmission/bitset.c @ 12019

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

(trunk libT) if we're a partial seed and the peer has everything we have, disconnect.

  • Property svn:keywords set to Date Rev Author Id
File size: 5.9 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: bitset.c 12019 2011-02-24 01:50:35Z jordan $
11 */
12
13#include "transmission.h"
14#include "bencode.h"
15#include "bitset.h"
16#include "utils.h"
17
18const tr_bitset TR_BITSET_INIT = { FALSE, FALSE, { NULL, 0, 0 } };
19
20void
21tr_bitsetConstruct( tr_bitset * b, size_t bitCount )
22{
23    *b = TR_BITSET_INIT;
24    b->bitfield.bitCount = bitCount;
25}
26
27void
28tr_bitsetDestruct( tr_bitset * b )
29{
30    tr_free( b->bitfield.bits );
31    *b = TR_BITSET_INIT;
32}
33
34static void
35tr_bitsetClear( tr_bitset * b )
36{
37    tr_free( b->bitfield.bits );
38    b->bitfield.bits = NULL;
39    b->haveAll = FALSE;
40    b->haveNone = FALSE;
41}
42
43void
44tr_bitsetSetHaveAll( tr_bitset * b )
45{
46    tr_bitsetClear( b );
47    b->haveAll = TRUE;
48}
49
50void
51tr_bitsetSetHaveNone( tr_bitset * b )
52{
53    tr_bitsetClear( b );
54    b->haveNone = TRUE;
55}
56
57void
58tr_bitsetSetBitfield( tr_bitset * b, const tr_bitfield * bitfield )
59{
60    const size_t n = tr_bitfieldCountTrueBits( bitfield );
61
62    if( n == 0 )
63    {
64        tr_bitsetSetHaveNone( b );
65    }
66    else if( n == bitfield->bitCount )
67    {
68        tr_bitsetSetHaveAll( b );
69    }
70    else
71    {
72        tr_bitsetDestruct( b );
73        b->bitfield.bits = tr_memdup( bitfield->bits, bitfield->byteCount );
74        b->bitfield.bitCount = bitfield->bitCount;
75        b->bitfield.byteCount = bitfield->byteCount;
76    }
77}
78
79/***
80****
81***/
82
83void
84tr_bitsetAdd( tr_bitset * b, size_t i )
85{
86    tr_bitfield * bf = &b->bitfield;
87
88    if( b->haveAll )
89        return;
90
91    b->haveNone = FALSE;
92
93    /* do we need to resize the bitfield to accomodate this bit? */
94    if( !bf->bits || ( bf->bitCount < i+1 ) )
95    {
96        const size_t oldByteCount = bf->byteCount;
97        if( bf->bitCount < i + 1 )
98            bf->bitCount = i + 1;
99        bf->byteCount = ( bf->bitCount + 7u ) / 8u;
100        bf->bits = tr_renew( uint8_t, bf->bits, bf->byteCount );
101        if( bf->byteCount > oldByteCount )
102            memset( bf->bits + oldByteCount, 0, bf->byteCount - oldByteCount );
103    }
104
105    tr_bitfieldAdd( bf, i );
106}
107
108void
109tr_bitsetRem( tr_bitset * b, size_t i )
110{
111    if( b->haveNone )
112        return;
113
114    b->haveAll = FALSE;
115
116    if( !b->bitfield.bits )
117    {
118        tr_bitfieldConstruct( &b->bitfield, b->bitfield.bitCount );
119        tr_bitfieldAddRange( &b->bitfield, 0, b->bitfield.bitCount );
120    }
121
122    tr_bitfieldRem( &b->bitfield, i );
123}
124
125void
126tr_bitsetRemRange( tr_bitset * b, size_t begin, size_t end )
127{
128    if( b->haveNone )
129        return;
130
131    b->haveAll = FALSE; 
132    if( !b->bitfield.bits )
133    {
134        tr_bitfieldConstruct( &b->bitfield, b->bitfield.bitCount );
135        tr_bitfieldAddRange( &b->bitfield, 0, b->bitfield.bitCount );
136    }
137
138    tr_bitfieldRemRange( &b->bitfield, begin, end );
139}
140
141/***
142****
143***/
144
145tr_bool
146tr_bitsetHas( const tr_bitset * b, const size_t nth )
147{
148    if( b->haveAll ) return TRUE;
149    if( b->haveNone ) return FALSE;
150    if( nth >= b->bitfield.bitCount ) return FALSE;
151    return tr_bitfieldHas( &b->bitfield, nth );
152}
153
154size_t
155tr_bitsetCountRange( const tr_bitset * b, const size_t begin, const size_t end )
156{
157    if( b->haveAll ) return end - begin;
158    if( b->haveNone ) return 0;
159    return tr_bitfieldCountRange( &b->bitfield, begin, end );
160}
161
162/* return true if "b" is equal to, or a superset of, "set" */
163tr_bool
164tr_bitsetHasSet( const tr_bitset * b, const tr_bitset * set )
165{
166    const uint8_t * bit = b->bitfield.bits;
167    const uint8_t * bend = bit + b->bitfield.byteCount;
168    const uint8_t * sit = set->bitfield.bits;
169    const uint8_t * send = sit + set->bitfield.byteCount;
170   
171    if( b->haveAll || set->haveAll )
172        return b->haveAll;
173
174    if( b->haveNone || set->haveNone )
175        return set->haveNone;
176
177    for( ; bit!=bend && sit!=send; ++bit, ++sit )
178        if( ( *bit & *sit ) != *sit )
179            return FALSE;
180
181    return TRUE;
182}
183
184double
185tr_bitsetPercent( const tr_bitset * b )
186{
187    if( b->haveAll ) return 1.0;
188    if( b->haveNone ) return 0.0;
189    if( b->bitfield.bitCount == 0 ) return 0.0;
190    return tr_bitfieldCountTrueBits( &b->bitfield ) / (double)b->bitfield.bitCount;
191}
192
193void
194tr_bitsetOr( tr_bitfield * a, const tr_bitset * b )
195{
196    if( b->haveAll )
197        tr_bitfieldAddRange( a, 0, a->bitCount );
198    else if( !b->haveNone )
199        tr_bitfieldOr( a, &b->bitfield );
200}
201
202/***
203****
204***/
205
206tr_bool
207tr_bitsetFromBenc( tr_bitset * bitset, tr_benc * benc )
208{
209    size_t buflen;
210    const uint8_t * buf;
211    tr_bool handled = FALSE;
212
213    if( tr_bencGetRaw( benc, &buf, &buflen ) )
214    {
215        if( ( buflen == 3 ) && !memcmp( buf, "all", 3 ) )
216        {
217            tr_bitsetSetHaveAll( bitset );
218            handled = TRUE;
219        }
220        else if( ( buflen == 4 ) && !memcmp( buf, "none", 4 ) )
221        {
222            tr_bitsetSetHaveNone( bitset );
223            handled = TRUE;
224        }
225        else
226        {
227            bitset->haveAll = FALSE;
228            bitset->haveNone = FALSE;
229            tr_free( bitset->bitfield.bits );
230            bitset->bitfield.bits = tr_memdup( buf, buflen );
231            bitset->bitfield.byteCount = buflen;
232            bitset->bitfield.bitCount = buflen * 8;
233            handled = TRUE;
234        }
235    }
236
237    return handled;
238}
239
240void
241tr_bitsetToBenc( const tr_bitset * bitset, tr_benc * benc )
242{
243    if( bitset->haveAll )
244    {
245        tr_bencInitStr( benc, "all", 3 );
246    }
247    else if( bitset->haveNone )
248    {
249        tr_bencInitStr( benc, "none", 4 );
250    }
251    else
252    {
253        const tr_bitfield * bf = &bitset->bitfield;
254        const size_t n = tr_bitfieldCountTrueBits( bf );
255
256        if( n == bf->bitCount )
257        {
258            tr_bencInitStr( benc, "all", 3 );
259        }
260        else if( n == 0 )
261        {
262            tr_bencInitStr( benc, "none", 4 );
263        }
264        else
265        {
266            tr_bencInitRaw( benc, bf->bits, bf->byteCount );
267        }
268    }
269}
Note: See TracBrowser for help on using the repository browser.