bit-set 0.11.0

A set of bits
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

use crate::local_prelude::*;

#[allow(type_alias_bounds)]
type MatchWords<'a, B: BitBlock> =
    Chain<Enumerate<Blocks<'a, B>>, Skip<Take<Enumerate<Repeat<B>>>>>;

/// Computes how many blocks are needed to store that many bits
pub(crate) fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
    // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
    // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
    // one too many. So we need to check if that's the case. We can do that by computing if
    // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
    // superior modulo operator on a power of two to this.
    //
    // Note that we can technically avoid this branch with the expression
    // `(nbits + BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
    if bits % B::bits() == 0 {
        bits / B::bits()
    } else {
        bits / B::bits() + 1
    }
}

#[allow(clippy::iter_skip_zero)]
// Take two BitVec's, and return iterators of their words, where the shorter one
// has been padded with 0's
pub(crate) fn match_words<'a, 'b, B: BitBlock>(
    a: &'a BitVec<B>,
    b: &'b BitVec<B>,
) -> (MatchWords<'a, B>, MatchWords<'b, B>) {
    let a_len = a.storage().len();
    let b_len = b.storage().len();

    // have to uselessly pretend to pad the longer one for type matching
    if a_len < b_len {
        (
            a.blocks()
                .enumerate()
                .chain(iter::repeat(B::zero()).enumerate().take(b_len).skip(a_len)),
            b.blocks()
                .enumerate()
                .chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)),
        )
    } else {
        (
            a.blocks()
                .enumerate()
                .chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)),
            b.blocks()
                .enumerate()
                .chain(iter::repeat(B::zero()).enumerate().take(a_len).skip(b_len)),
        )
    }
}