cranelift_codegen/
bitset.rs

1//! Small Bitset
2//!
3//! This module defines a struct `BitSet<T>` encapsulating a bitset built over the type T.
4//! T is intended to be a primitive unsigned type. Currently it can be any type between u8 and u32
5//!
6//! If you would like to add support for larger bitsets in the future, you need to change the trait
7//! bound `Into<u32>` and the `u32` in the implementation of `max_bits()`.
8
9use core::convert::{From, Into};
10use core::mem::size_of;
11use core::ops::{Add, BitOr, Shl, Sub};
12
13/// A small bitset built on a single primitive integer type
14#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
15#[cfg_attr(feature = "enable-serde", derive(serde::Serialize, serde::Deserialize))]
16pub struct BitSet<T>(pub T);
17
18impl<T> BitSet<T>
19where
20    T: Into<u32>
21        + From<u8>
22        + BitOr<T, Output = T>
23        + Shl<u8, Output = T>
24        + Sub<T, Output = T>
25        + Add<T, Output = T>
26        + PartialEq
27        + Copy,
28{
29    /// Maximum number of bits supported by this BitSet instance
30    pub fn bits() -> usize {
31        size_of::<T>() * 8
32    }
33
34    /// Maximum number of bits supported by any bitset instance atm.
35    pub fn max_bits() -> usize {
36        size_of::<u32>() * 8
37    }
38
39    /// Check if this BitSet contains the number num
40    pub fn contains(&self, num: u32) -> bool {
41        debug_assert!((num as usize) < Self::bits());
42        debug_assert!((num as usize) < Self::max_bits());
43        self.0.into() & (1 << num) != 0
44    }
45
46    /// Return the smallest number contained in the bitset or None if empty
47    pub fn min(&self) -> Option<u8> {
48        if self.0.into() == 0 {
49            None
50        } else {
51            Some(self.0.into().trailing_zeros() as u8)
52        }
53    }
54
55    /// Return the largest number contained in the bitset or None if empty
56    pub fn max(&self) -> Option<u8> {
57        if self.0.into() == 0 {
58            None
59        } else {
60            let leading_zeroes = self.0.into().leading_zeros() as usize;
61            Some((Self::max_bits() - leading_zeroes - 1) as u8)
62        }
63    }
64
65    /// Construct a BitSet with the half-open range [lo,hi) filled in
66    pub fn from_range(lo: u8, hi: u8) -> Self {
67        debug_assert!(lo <= hi);
68        debug_assert!((hi as usize) <= Self::bits());
69        let one: T = T::from(1);
70        // I can't just do (one << hi) - one here as the shift may overflow
71        let hi_rng = if hi >= 1 {
72            (one << (hi - 1)) + ((one << (hi - 1)) - one)
73        } else {
74            T::from(0)
75        };
76
77        let lo_rng = (one << lo) - one;
78
79        Self(hi_rng - lo_rng)
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    #[test]
88    fn contains() {
89        let s = BitSet::<u8>(255);
90        for i in 0..7 {
91            assert!(s.contains(i));
92        }
93
94        let s1 = BitSet::<u8>(0);
95        for i in 0..7 {
96            assert!(!s1.contains(i));
97        }
98
99        let s2 = BitSet::<u8>(127);
100        for i in 0..6 {
101            assert!(s2.contains(i));
102        }
103        assert!(!s2.contains(7));
104
105        let s3 = BitSet::<u8>(2 | 4 | 64);
106        assert!(!s3.contains(0) && !s3.contains(3) && !s3.contains(4));
107        assert!(!s3.contains(5) && !s3.contains(7));
108        assert!(s3.contains(1) && s3.contains(2) && s3.contains(6));
109
110        let s4 = BitSet::<u16>(4 | 8 | 256 | 1024);
111        assert!(
112            !s4.contains(0)
113                && !s4.contains(1)
114                && !s4.contains(4)
115                && !s4.contains(5)
116                && !s4.contains(6)
117                && !s4.contains(7)
118                && !s4.contains(9)
119                && !s4.contains(11)
120        );
121        assert!(s4.contains(2) && s4.contains(3) && s4.contains(8) && s4.contains(10));
122    }
123
124    #[test]
125    fn minmax() {
126        let s = BitSet::<u8>(255);
127        assert_eq!(s.min(), Some(0));
128        assert_eq!(s.max(), Some(7));
129        assert!(s.min() == Some(0) && s.max() == Some(7));
130        let s1 = BitSet::<u8>(0);
131        assert!(s1.min() == None && s1.max() == None);
132        let s2 = BitSet::<u8>(127);
133        assert!(s2.min() == Some(0) && s2.max() == Some(6));
134        let s3 = BitSet::<u8>(2 | 4 | 64);
135        assert!(s3.min() == Some(1) && s3.max() == Some(6));
136        let s4 = BitSet::<u16>(4 | 8 | 256 | 1024);
137        assert!(s4.min() == Some(2) && s4.max() == Some(10));
138    }
139
140    #[test]
141    fn from_range() {
142        let s = BitSet::<u8>::from_range(5, 5);
143        assert!(s.0 == 0);
144
145        let s = BitSet::<u8>::from_range(0, 8);
146        assert!(s.0 == 255);
147
148        let s = BitSet::<u16>::from_range(0, 8);
149        assert!(s.0 == 255u16);
150
151        let s = BitSet::<u16>::from_range(0, 16);
152        assert!(s.0 == 65535u16);
153
154        let s = BitSet::<u8>::from_range(5, 6);
155        assert!(s.0 == 32u8);
156
157        let s = BitSet::<u8>::from_range(3, 7);
158        assert!(s.0 == 8 | 16 | 32 | 64);
159
160        let s = BitSet::<u16>::from_range(5, 11);
161        assert!(s.0 == 32 | 64 | 128 | 256 | 512 | 1024);
162    }
163}
cranelift_codegen/bitset.rs

cranelift_codegen/
bitset.rs
