/rust/registry/src/index.crates.io-6f17d22bba15001f/hashbrown-0.12.3/src/raw/bitmask.rs

Source (jump to first uncovered line)
use super::imp::{BitMaskWord, BITMASK_MASK, BITMASK_STRIDE};
#[cfg(feature = "nightly")]
use core::intrinsics;

/// A bit mask which contains the result of a `Match` operation on a `Group` and
/// allows iterating through them.
///
/// The bit mask is arranged so that low-order bits represent lower memory
/// addresses for group match results.
///
/// For implementation reasons, the bits in the set may be sparsely packed, so
/// that there is only one bit-per-byte used (the high bit, 7). If this is the
/// case, `BITMASK_STRIDE` will be 8 to indicate a divide-by-8 should be
/// performed on counts/indices to normalize this difference. `BITMASK_MASK` is
/// similarly a mask of all the actually-used bits.
#[derive(Copy, Clone)]
pub struct BitMask(pub BitMaskWord);

#[allow(clippy::use_self)]
impl BitMask {
    /// Returns a new `BitMask` with all bits inverted.
    #[inline]
    #[must_use]
    pub fn invert(self) -> Self {
        BitMask(self.0 ^ BITMASK_MASK)
    }

    /// Flip the bit in the mask for the entry at the given index.
    ///
    /// Returns the bit's previous state.
    #[inline]
    #[allow(clippy::cast_ptr_alignment)]
    #[cfg(feature = "raw")]
    pub unsafe fn flip(&mut self, index: usize) -> bool {
        // NOTE: The + BITMASK_STRIDE - 1 is to set the high bit.
        let mask = 1 << (index * BITMASK_STRIDE + BITMASK_STRIDE - 1);
        self.0 ^= mask;
        // The bit was set if the bit is now 0.
        self.0 & mask == 0
    }

    /// Returns a new `BitMask` with the lowest bit removed.
    #[inline]
    #[must_use]
    pub fn remove_lowest_bit(self) -> Self {
        BitMask(self.0 & (self.0 - 1))
    }
    /// Returns whether the `BitMask` has at least one set bit.
    #[inline]
    pub fn any_bit_set(self) -> bool {
        self.0 != 0
    }

    /// Returns the first set bit in the `BitMask`, if there is one.
    #[inline]
    pub fn lowest_set_bit(self) -> Option<usize> {
        if self.0 == 0 {
            None
        } else {
            Some(unsafe { self.lowest_set_bit_nonzero() })
        }
    }

    /// Returns the first set bit in the `BitMask`, if there is one. The
    /// bitmask must not be empty.
    #[inline]
    #[cfg(feature = "nightly")]
    pub unsafe fn lowest_set_bit_nonzero(self) -> usize {
        intrinsics::cttz_nonzero(self.0) as usize / BITMASK_STRIDE
    }
    #[inline]
    #[cfg(not(feature = "nightly"))]
    pub unsafe fn lowest_set_bit_nonzero(self) -> usize {
        self.trailing_zeros()
    }

    /// Returns the number of trailing zeroes in the `BitMask`.
    #[inline]
    pub fn trailing_zeros(self) -> usize {
        // ARM doesn't have a trailing_zeroes instruction, and instead uses
        // reverse_bits (RBIT) + leading_zeroes (CLZ). However older ARM
        // versions (pre-ARMv7) don't have RBIT and need to emulate it
        // instead. Since we only have 1 bit set in each byte on ARM, we can
        // use swap_bytes (REV) + leading_zeroes instead.
        if cfg!(target_arch = "arm") && BITMASK_STRIDE % 8 == 0 {
            self.0.swap_bytes().leading_zeros() as usize / BITMASK_STRIDE
        } else {
            self.0.trailing_zeros() as usize / BITMASK_STRIDE
        }
    }

    /// Returns the number of leading zeroes in the `BitMask`.
    #[inline]
    pub fn leading_zeros(self) -> usize {
        self.0.leading_zeros() as usize / BITMASK_STRIDE
    }
}

impl IntoIterator for BitMask {
    type Item = usize;
    type IntoIter = BitMaskIter;

    #[inline]
    fn into_iter(self) -> BitMaskIter {
        BitMaskIter(self)
    }
}

/// Iterator over the contents of a `BitMask`, returning the indices of set
/// bits.
pub struct BitMaskIter(BitMask);

impl Iterator for BitMaskIter {
    type Item = usize;

    #[inline]
    fn next(&mut self) -> Option<usize> {
        let bit = self.0.lowest_set_bit()?;
        self.0 = self.0.remove_lowest_bit();
        Some(bit)
    }
}

Line	Count	Source (jump to first uncovered line)
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	0	pub fn invert(self) -> Self {
25	0	BitMask(self.0 ^ BITMASK_MASK)
26	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::invert Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::invert
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	0	pub unsafe fn flip(&mut self, index: usize) -> bool {
35	0	// NOTE: The + BITMASK_STRIDE - 1 is to set the high bit.
36	0	let mask = 1 << (index * BITMASK_STRIDE + BITMASK_STRIDE - 1);
37	0	self.0 ^= mask;
38	0	// The bit was set if the bit is now 0.
39	0	self.0 & mask == 0
40	0	}
41
42		/// Returns a new `BitMask` with the lowest bit removed.
43		#[inline]
44		#[must_use]
45	0	pub fn remove_lowest_bit(self) -> Self {
46	0	BitMask(self.0 & (self.0 - 1))
47	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::remove_lowest_bit Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::remove_lowest_bit Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::remove_lowest_bit
48		/// Returns whether the `BitMask` has at least one set bit.
49		#[inline]
50	0	pub fn any_bit_set(self) -> bool {
51	0	self.0 != 0
52	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::any_bit_set Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::any_bit_set
53
54		/// Returns the first set bit in the `BitMask`, if there is one.
55		#[inline]
56	0	pub fn lowest_set_bit(self) -> Option<usize> {
57	0	if self.0 == 0 {
58	0	None
59		} else {
60	0	Some(unsafe { self.lowest_set_bit_nonzero() })
61		}
62	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::lowest_set_bit Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::lowest_set_bit Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::lowest_set_bit
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	0	pub unsafe fn lowest_set_bit_nonzero(self) -> usize {
74	0	self.trailing_zeros()
75	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::lowest_set_bit_nonzero Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::lowest_set_bit_nonzero Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::lowest_set_bit_nonzero
76
77		/// Returns the number of trailing zeroes in the `BitMask`.
78		#[inline]
79	0	pub fn trailing_zeros(self) -> usize {
80	0	// ARM doesn't have a trailing_zeroes instruction, and instead uses
81	0	// reverse_bits (RBIT) + leading_zeroes (CLZ). However older ARM
82	0	// versions (pre-ARMv7) don't have RBIT and need to emulate it
83	0	// instead. Since we only have 1 bit set in each byte on ARM, we can
84	0	// use swap_bytes (REV) + leading_zeroes instead.
85	0	if cfg!(target_arch = "arm") && BITMASK_STRIDE % 8 == 0 {
86	0	self.0.swap_bytes().leading_zeros() as usize / BITMASK_STRIDE
87		} else {
88	0	self.0.trailing_zeros() as usize / BITMASK_STRIDE
89		}
90	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::trailing_zeros Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::trailing_zeros Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::trailing_zeros
91
92		/// Returns the number of leading zeroes in the `BitMask`.
93		#[inline]
94	0	pub fn leading_zeros(self) -> usize {
95	0	self.0.leading_zeros() as usize / BITMASK_STRIDE
96	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::leading_zeros Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask>::leading_zeros
97		}
98
99		impl IntoIterator for BitMask {
100		type Item = usize;
101		type IntoIter = BitMaskIter;
102
103		#[inline]
104	0	fn into_iter(self) -> BitMaskIter {
105	0	BitMaskIter(self)
106	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMask as core::iter::traits::collect::IntoIterator>::into_iter
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	0	fn next(&mut self) -> Option<usize> {
118	0	let bit = self.0.lowest_set_bit()?;
119	0	self.0 = self.0.remove_lowest_bit();
120	0	Some(bit)
121	0	} Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMaskIter as core::iter::traits::iterator::Iterator>::next Unexecuted instantiation: <hashbrown::raw::inner::bitmask::BitMaskIter as core::iter::traits::iterator::Iterator>::next
122		}

Coverage Report

Created: 2024-12-17 06:15