]>
Commit | Line | Data |
---|---|---|
6a06907d XL |
1 | use super::imp::{BitMaskWord, BITMASK_MASK, BITMASK_STRIDE}; |
2 | #[cfg(feature = "nightly")] | |
3 | use core::intrinsics; | |
4 | ||
5 | /// A bit mask which contains the result of a `Match` operation on a `Group` and | |
6 | /// allows iterating through them. | |
7 | /// | |
8 | /// The bit mask is arranged so that low-order bits represent lower memory | |
9 | /// addresses for group match results. | |
10 | /// | |
11 | /// For implementation reasons, the bits in the set may be sparsely packed, so | |
12 | /// that there is only one bit-per-byte used (the high bit, 7). If this is the | |
13 | /// case, `BITMASK_STRIDE` will be 8 to indicate a divide-by-8 should be | |
14 | /// performed on counts/indices to normalize this difference. `BITMASK_MASK` is | |
15 | /// similarly a mask of all the actually-used bits. | |
16 | #[derive(Copy, Clone)] | |
17 | pub struct BitMask(pub BitMaskWord); | |
18 | ||
19 | #[allow(clippy::use_self)] | |
20 | impl BitMask { | |
21 | /// Returns a new `BitMask` with all bits inverted. | |
22 | #[inline] | |
23 | #[must_use] | |
24 | pub fn invert(self) -> Self { | |
25 | BitMask(self.0 ^ BITMASK_MASK) | |
26 | } | |
27 | ||
28 | /// Flip the bit in the mask for the entry at the given index. | |
29 | /// | |
30 | /// Returns the bit's previous state. | |
31 | #[inline] | |
32 | #[allow(clippy::cast_ptr_alignment)] | |
33 | #[cfg(feature = "raw")] | |
34 | pub unsafe fn flip(&mut self, index: usize) -> bool { | |
35 | // NOTE: The + BITMASK_STRIDE - 1 is to set the high bit. | |
36 | let mask = 1 << (index * BITMASK_STRIDE + BITMASK_STRIDE - 1); | |
37 | self.0 ^= mask; | |
38 | // The bit was set if the bit is now 0. | |
39 | self.0 & mask == 0 | |
40 | } | |
41 | ||
42 | /// Returns a new `BitMask` with the lowest bit removed. | |
43 | #[inline] | |
44 | #[must_use] | |
45 | pub fn remove_lowest_bit(self) -> Self { | |
46 | BitMask(self.0 & (self.0 - 1)) | |
47 | } | |
48 | /// Returns whether the `BitMask` has at least one set bit. | |
49 | #[inline] | |
50 | pub fn any_bit_set(self) -> bool { | |
51 | self.0 != 0 | |
52 | } | |
53 | ||
54 | /// Returns the first set bit in the `BitMask`, if there is one. | |
55 | #[inline] | |
56 | pub fn lowest_set_bit(self) -> Option<usize> { | |
57 | if self.0 == 0 { | |
58 | None | |
59 | } else { | |
60 | Some(unsafe { self.lowest_set_bit_nonzero() }) | |
61 | } | |
62 | } | |
63 | ||
64 | /// Returns the first set bit in the `BitMask`, if there is one. The | |
65 | /// bitmask must not be empty. | |
66 | #[inline] | |
67 | #[cfg(feature = "nightly")] | |
68 | pub unsafe fn lowest_set_bit_nonzero(self) -> usize { | |
69 | intrinsics::cttz_nonzero(self.0) as usize / BITMASK_STRIDE | |
70 | } | |
71 | #[inline] | |
72 | #[cfg(not(feature = "nightly"))] | |
73 | pub unsafe fn lowest_set_bit_nonzero(self) -> usize { | |
74 | self.trailing_zeros() | |
75 | } | |
76 | ||
77 | /// Returns the number of trailing zeroes in the `BitMask`. | |
78 | #[inline] | |
79 | pub fn trailing_zeros(self) -> usize { | |
80 | // ARM doesn't have a trailing_zeroes instruction, and instead uses | |
81 | // reverse_bits (RBIT) + leading_zeroes (CLZ). However older ARM | |
82 | // versions (pre-ARMv7) don't have RBIT and need to emulate it | |
83 | // instead. Since we only have 1 bit set in each byte on ARM, we can | |
84 | // use swap_bytes (REV) + leading_zeroes instead. | |
85 | if cfg!(target_arch = "arm") && BITMASK_STRIDE % 8 == 0 { | |
86 | self.0.swap_bytes().leading_zeros() as usize / BITMASK_STRIDE | |
87 | } else { | |
88 | self.0.trailing_zeros() as usize / BITMASK_STRIDE | |
89 | } | |
90 | } | |
91 | ||
92 | /// Returns the number of leading zeroes in the `BitMask`. | |
93 | #[inline] | |
94 | pub fn leading_zeros(self) -> usize { | |
95 | self.0.leading_zeros() as usize / BITMASK_STRIDE | |
96 | } | |
97 | } | |
98 | ||
99 | impl IntoIterator for BitMask { | |
100 | type Item = usize; | |
101 | type IntoIter = BitMaskIter; | |
102 | ||
103 | #[inline] | |
104 | fn into_iter(self) -> BitMaskIter { | |
105 | BitMaskIter(self) | |
106 | } | |
107 | } | |
108 | ||
109 | /// Iterator over the contents of a `BitMask`, returning the indicies of set | |
110 | /// bits. | |
111 | pub struct BitMaskIter(BitMask); | |
112 | ||
113 | impl Iterator for BitMaskIter { | |
114 | type Item = usize; | |
115 | ||
116 | #[inline] | |
117 | fn next(&mut self) -> Option<usize> { | |
118 | let bit = self.0.lowest_set_bit()?; | |
119 | self.0 = self.0.remove_lowest_bit(); | |
120 | Some(bit) | |
121 | } | |
122 | } |