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}