naga/proc/overloads/
one_bits_iter.rs

1//! An iterator over bitmasks.
2
3/// An iterator that produces the set bits in the given `u64`.
4///
5/// `OneBitsIter(n)` is an [`Iterator`] that produces each of the set bits in
6/// `n`, as a bitmask, in order of increasing value. In other words, it produces
7/// the unique sequence of distinct powers of two that adds up to `n`.
8///
9/// For example, iterating over `OneBitsIter(21)` produces the values `1`, `4`,
10/// and `16`, in that order, because `21` is `0xb10101`.
11///
12/// When `n` is the bits of a bitmask, this iterates over the set bits in the
13/// bitmask, in order of increasing bit value. `bitflags` does define an `iter`
14/// method, but it's not well-specified or well-implemented.
15///
16/// The values produced are masks, not bit numbers. Use `u64::trailing_zeros` if
17/// you need bit numbers.
18pub struct OneBitsIter(u64);
19
20impl OneBitsIter {
21    pub const fn new(bits: u64) -> Self {
22        Self(bits)
23    }
24}
25
26impl Iterator for OneBitsIter {
27    type Item = u64;
28
29    fn next(&mut self) -> Option<Self::Item> {
30        if self.0 == 0 {
31            return None;
32        }
33
34        // Subtracting one from a value in binary clears the lowest `1` bit
35        // (call it `B`), and sets all the bits below that.
36        let mask = self.0 - 1;
37
38        // Complementing that means that we've instead *set* `B`, *cleared*
39        // everything below it, and *complemented* everything above it.
40        //
41        // Masking with the original value clears everything above and below
42        // `B`, leaving only `B` set. This is the value we produce.
43        let item = self.0 & !mask;
44
45        // Now that we've produced this bit, remove it from `self.0`.
46        self.0 &= mask;
47
48        Some(item)
49    }
50}
51
52#[test]
53fn empty() {
54    assert_eq!(OneBitsIter(0).next(), None);
55}
56
57#[test]
58fn all() {
59    let mut obi = OneBitsIter(!0);
60    for bit in 0..64 {
61        assert_eq!(obi.next(), Some(1 << bit));
62    }
63    assert_eq!(obi.next(), None);
64}
65
66#[test]
67fn first() {
68    let mut obi = OneBitsIter(1);
69    assert_eq!(obi.next(), Some(1));
70    assert_eq!(obi.next(), None);
71}
72
73#[test]
74fn last() {
75    let mut obi = OneBitsIter(1 << 63);
76    assert_eq!(obi.next(), Some(1 << 63));
77    assert_eq!(obi.next(), None);
78}
79
80#[test]
81fn in_order() {
82    let mut obi = OneBitsIter(0b11011000001);
83    assert_eq!(obi.next(), Some(1));
84    assert_eq!(obi.next(), Some(64));
85    assert_eq!(obi.next(), Some(128));
86    assert_eq!(obi.next(), Some(512));
87    assert_eq!(obi.next(), Some(1024));
88    assert_eq!(obi.next(), None);
89}