| 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 indices 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 |
} |