source: trunk/libtransmission/bitfield.h @ 12262

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

(trunk libT) handle situations where we don't know the bitfield's upper bound in advance. This comes up sometimes with magnet links.

  • Property svn:keywords set to Date Rev Author Id
File size: 3.1 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.h 12262 2011-03-30 04:14:57Z jordan $
11 */
12
13#ifndef __TRANSMISSION__
14 #error only libtransmission should #include this header.
15#endif
16
17#ifndef TR_BITFIELD_H
18#define TR_BITFIELD_H 1
19
20#include <assert.h>
21#include "transmission.h"
22
23/** @brief Implementation of the BitTorrent spec's Bitfield array of bits */
24typedef struct tr_bitfield
25{
26    uint8_t *  bits;
27    size_t     alloc_count;
28
29    size_t     bit_count;
30
31    size_t     true_count;
32
33    /* Special cases for when full or empty but we don't know the bitCount.
34       This occurs when a magnet link's peers send have all / have none */
35    bool       have_all_hint;
36    bool       have_none_hint;
37}
38tr_bitfield;
39
40/***
41****
42***/
43
44void   tr_bitfieldSetHasAll( tr_bitfield* );
45
46void   tr_bitfieldSetHasNone( tr_bitfield* );
47
48void   tr_bitfieldAdd( tr_bitfield*, size_t bit );
49
50void   tr_bitfieldRem( tr_bitfield*, size_t bit );
51
52void   tr_bitfieldAddRange( tr_bitfield*, size_t begin, size_t end );
53
54void   tr_bitfieldRemRange( tr_bitfield*, size_t begin, size_t end );
55
56/***
57****  life cycle
58***/
59
60extern const tr_bitfield TR_BITFIELD_INIT;
61
62void   tr_bitfieldConstruct( tr_bitfield*, size_t bit_count );
63
64static inline void
65tr_bitfieldDestruct( tr_bitfield * b )
66{
67    tr_bitfieldSetHasNone( b );
68}
69
70/***
71****
72***/
73
74void   tr_bitfieldSetFromBitfield( tr_bitfield*, const tr_bitfield* );
75
76void   tr_bitfieldSetRaw( tr_bitfield*, const void * bits, size_t byte_count );
77
78void*  tr_bitfieldGetRaw( const tr_bitfield * b, size_t * byte_count );
79
80/***
81****
82***/
83
84size_t  tr_bitfieldCountRange( const tr_bitfield*, size_t begin, size_t end );
85
86size_t  tr_bitfieldCountTrueBits( const tr_bitfield * b );
87
88static inline bool
89tr_bitfieldHasAll( const tr_bitfield * b )
90{
91    return b->bit_count ? ( b->true_count == b->bit_count ) : b->have_all_hint;
92}
93
94static inline bool
95tr_bitfieldHasNone( const tr_bitfield * b )
96{
97    return b->bit_count ? ( b->true_count == 0 ) : b->have_none_hint;
98}
99
100/** A stripped-down version of bitfieldHas to be used
101    for speed when you're looping quickly. This version
102    has none of tr_bitfieldHas()'s safety checks, so you
103    need to call tr_bitfieldTestFast() first before you
104    start looping. */
105static inline bool
106tr_bitfieldHasFast( const tr_bitfield * b, const size_t n )
107{
108    if( tr_bitfieldHasAll( b ) ) return true;
109    if( tr_bitfieldHasNone( b ) ) return false;
110    return ( b->bits[n>>3u] << ( n & 7u ) & 0x80 ) != 0;
111}
112
113/** @param high the highest nth bit you're going to access */
114static inline bool
115tr_bitfieldTestFast( const tr_bitfield * b, const size_t high )
116{
117    return ( b != NULL )
118        && ( high < b->bit_count );
119}
120
121static inline bool
122tr_bitfieldHas( const tr_bitfield * b, size_t n )
123{
124    if( tr_bitfieldHasAll( b ) ) return true;
125    if( tr_bitfieldHasNone( b ) ) return false;
126    if( n>>3u >= b->alloc_count ) return false;
127    return ( b->bits[n>>3u] << ( n & 7u ) & 0x80 ) != 0;
128}
129
130#endif
Note: See TracBrowser for help on using the repository browser.