cranelift_bitset/
scalar.rs

1//! Scalar bitsets.
2
3use core::mem::size_of;
4use core::ops::{Add, BitAnd, BitOr, Not, Shl, Shr, Sub};
5
6/// A small bitset built on top of a single primitive integer type.
7///
8/// # Example
9///
10/// ```
11/// use cranelift_bitset::ScalarBitSet;
12///
13/// // Create a new bitset backed with a `u32`.
14/// let mut bitset = ScalarBitSet::<u32>::new();
15///
16/// // Bitsets are initially empty.
17/// assert!(bitset.is_empty());
18/// assert_eq!(bitset.len(), 0);
19///
20/// // Insert into the bitset.
21/// bitset.insert(4);
22/// bitset.insert(5);
23/// bitset.insert(6);
24///
25/// // Now the bitset is not empty.
26/// assert_eq!(bitset.len(), 3);
27/// assert!(!bitset.is_empty());
28/// assert!(bitset.contains(4));
29/// assert!(bitset.contains(5));
30/// assert!(bitset.contains(6));
31///
32/// // Remove an element from the bitset.
33/// let was_present = bitset.remove(6);
34/// assert!(was_present);
35/// assert!(!bitset.contains(6));
36/// assert_eq!(bitset.len(), 2);
37///
38/// // Can iterate over the elements in the set.
39/// let elems: Vec<_> = bitset.iter().collect();
40/// assert_eq!(elems, [4, 5]);
41/// ```
42#[derive(Clone, Copy, PartialEq, Eq)]
43#[cfg_attr(
44    feature = "enable-serde",
45    derive(serde_derive::Serialize, serde_derive::Deserialize)
46)]
47pub struct ScalarBitSet<T>(pub T);
48
49impl<T> core::fmt::Debug for ScalarBitSet<T>
50where
51    T: ScalarBitSetStorage,
52{
53    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
54        let mut s = f.debug_struct(core::any::type_name::<Self>());
55        for i in 0..Self::capacity() {
56            use alloc::string::ToString;
57            let i = u8::try_from(i).unwrap();
58            s.field(&i.to_string(), &self.contains(i));
59        }
60        s.finish()
61    }
62}
63
64impl<T> Default for ScalarBitSet<T>
65where
66    T: ScalarBitSetStorage,
67{
68    #[inline]
69    fn default() -> Self {
70        Self::new()
71    }
72}
73
74impl<T> ScalarBitSet<T>
75where
76    T: ScalarBitSetStorage,
77{
78    /// Create a new, empty bitset.
79    ///
80    /// # Example
81    ///
82    /// ```
83    /// use cranelift_bitset::ScalarBitSet;
84    ///
85    /// let bitset = ScalarBitSet::<u64>::new();
86    ///
87    /// assert!(bitset.is_empty());
88    /// ```
89    #[inline]
90    pub fn new() -> Self {
91        Self(T::from(0))
92    }
93
94    /// Construct a bitset with the half-open range `[lo, hi)` inserted.
95    ///
96    /// # Example
97    ///
98    /// ```
99    /// use cranelift_bitset::ScalarBitSet;
100    ///
101    /// let bitset = ScalarBitSet::<u64>::from_range(3, 6);
102    ///
103    /// assert_eq!(bitset.len(), 3);
104    ///
105    /// assert!(bitset.contains(3));
106    /// assert!(bitset.contains(4));
107    /// assert!(bitset.contains(5));
108    /// ```
109    ///
110    /// # Panics
111    ///
112    /// Panics if `lo > hi` or if `hi > Self::capacity()`.
113    ///
114    /// ```should_panic
115    /// use cranelift_bitset::ScalarBitSet;
116    ///
117    /// // The lower bound may not be larger than the upper bound.
118    /// let bitset = ScalarBitSet::<u64>::from_range(6, 3);
119    /// ```
120    ///
121    /// ```should_panic
122    /// use cranelift_bitset::ScalarBitSet;
123    ///
124    /// // The bounds must fit within the backing scalar type.
125    /// let bitset = ScalarBitSet::<u64>::from_range(3, 69);
126    /// ```
127    #[inline]
128    pub fn from_range(lo: u8, hi: u8) -> Self {
129        assert!(lo <= hi);
130        assert!(hi <= Self::capacity());
131
132        let one = T::from(1);
133
134        // We can't just do (one << hi) - one here as the shift may overflow
135        let hi_rng = if hi >= 1 {
136            (one << (hi - 1)) + ((one << (hi - 1)) - one)
137        } else {
138            T::from(0)
139        };
140
141        let lo_rng = (one << lo) - one;
142
143        Self(hi_rng - lo_rng)
144    }
145
146    /// The maximum number of bits that can be stored in this bitset.
147    ///
148    /// If you need more bits than this, use a
149    /// [`CompoundBitSet`][crate::CompoundBitSet] instead of a `ScalarBitSet`.
150    ///
151    /// # Example
152    ///
153    /// ```
154    /// use cranelift_bitset::ScalarBitSet;
155    ///
156    /// assert_eq!(ScalarBitSet::<u8>::capacity(), 8);
157    /// assert_eq!(ScalarBitSet::<u64>::capacity(), 64);
158    /// ```
159    #[inline]
160    pub fn capacity() -> u8 {
161        u8::try_from(size_of::<T>()).unwrap() * 8
162    }
163
164    /// Get the number of elements in this set.
165    ///
166    /// # Example
167    ///
168    /// ```
169    /// use cranelift_bitset::ScalarBitSet;
170    ///
171    /// let mut bitset = ScalarBitSet::<u64>::new();
172    ///
173    /// assert_eq!(bitset.len(), 0);
174    ///
175    /// bitset.insert(24);
176    /// bitset.insert(13);
177    /// bitset.insert(36);
178    ///
179    /// assert_eq!(bitset.len(), 3);
180    /// ```
181    #[inline]
182    pub fn len(&self) -> u8 {
183        self.0.count_ones()
184    }
185
186    /// Is this bitset empty?
187    ///
188    /// # Example
189    ///
190    /// ```
191    /// use cranelift_bitset::ScalarBitSet;
192    ///
193    /// let mut bitset = ScalarBitSet::<u16>::new();
194    ///
195    /// assert!(bitset.is_empty());
196    ///
197    /// bitset.insert(10);
198    ///
199    /// assert!(!bitset.is_empty());
200    /// ```
201    #[inline]
202    pub fn is_empty(&self) -> bool {
203        self.0 == T::from(0)
204    }
205
206    /// Check whether this bitset contains `i`.
207    ///
208    /// # Example
209    ///
210    /// ```
211    /// use cranelift_bitset::ScalarBitSet;
212    ///
213    /// let mut bitset = ScalarBitSet::<u8>::new();
214    ///
215    /// assert!(!bitset.contains(7));
216    ///
217    /// bitset.insert(7);
218    ///
219    /// assert!(bitset.contains(7));
220    /// ```
221    ///
222    /// # Panics
223    ///
224    /// Panics if `i` is greater than or equal to [`Self::capacity()`][Self::capacity].
225    ///
226    /// ```should_panic
227    /// use cranelift_bitset::ScalarBitSet;
228    ///
229    /// let mut bitset = ScalarBitSet::<u8>::new();
230    ///
231    /// // A `ScalarBitSet<u8>` can only hold the elements `0..=7`, so `8` is
232    /// // out of bounds and will trigger a panic.
233    /// bitset.contains(8);
234    /// ```
235    #[inline]
236    pub fn contains(&self, i: u8) -> bool {
237        assert!(i < Self::capacity());
238        self.0 & (T::from(1) << i) != T::from(0)
239    }
240
241    /// Insert `i` into this bitset.
242    ///
243    /// Returns whether the value was newly inserted. That is:
244    ///
245    /// * If the set did not previously contain `i` then `true` is returned.
246    ///
247    /// * If the set already contained `i` then `false` is returned.
248    ///
249    /// # Example
250    ///
251    /// ```
252    /// use cranelift_bitset::ScalarBitSet;
253    ///
254    /// let mut bitset = ScalarBitSet::<u8>::new();
255    ///
256    /// // When an element is inserted that was not already present in the set,
257    /// // then `true` is returned.
258    /// let is_new = bitset.insert(7);
259    /// assert!(is_new);
260    ///
261    /// // The element is now present in the set.
262    /// assert!(bitset.contains(7));
263    ///
264    /// // And when the element is already in the set, `false` is returned from
265    /// // `insert`.
266    /// let is_new = bitset.insert(7);
267    /// assert!(!is_new);
268    /// ```
269    ///
270    /// # Panics
271    ///
272    /// Panics if `i` is greater than or equal to [`Self::capacity()`][Self::capacity].
273    ///
274    /// ```should_panic
275    /// use cranelift_bitset::ScalarBitSet;
276    ///
277    /// let mut bitset = ScalarBitSet::<u32>::new();
278    ///
279    /// // A `ScalarBitSet<u32>` can only hold the elements `0..=31`, so `42` is
280    /// // out of bounds and will trigger a panic.
281    /// bitset.insert(42);
282    /// ```
283    #[inline]
284    pub fn insert(&mut self, i: u8) -> bool {
285        let is_new = !self.contains(i);
286        self.0 = self.0 | (T::from(1) << i);
287        is_new
288    }
289
290    /// Remove `i` from this bitset.
291    ///
292    /// Returns whether `i` was previously in this set or not.
293    ///
294    /// # Example
295    ///
296    /// ```
297    /// use cranelift_bitset::ScalarBitSet;
298    ///
299    /// let mut bitset = ScalarBitSet::<u128>::new();
300    ///
301    /// // Removing an element that was not present in the set returns `false`.
302    /// let was_present = bitset.remove(100);
303    /// assert!(!was_present);
304    ///
305    /// // And when the element was in the set, `true` is returned.
306    /// bitset.insert(100);
307    /// let was_present = bitset.remove(100);
308    /// assert!(was_present);
309    /// ```
310    ///
311    /// # Panics
312    ///
313    /// Panics if `i` is greater than or equal to [`Self::capacity()`][Self::capacity].
314    ///
315    /// ```should_panic
316    /// use cranelift_bitset::ScalarBitSet;
317    ///
318    /// let mut bitset = ScalarBitSet::<u16>::new();
319    ///
320    /// // A `ScalarBitSet<u16>` can only hold the elements `0..=15`, so `20` is
321    /// // out of bounds and will trigger a panic.
322    /// bitset.remove(20);
323    /// ```
324    #[inline]
325    pub fn remove(&mut self, i: u8) -> bool {
326        let was_present = self.contains(i);
327        self.0 = self.0 & !(T::from(1) << i);
328        was_present
329    }
330
331    /// Remove all entries from this bitset.
332    ///
333    /// # Example
334    ///
335    /// ```
336    /// use cranelift_bitset::ScalarBitSet;
337    ///
338    /// let mut bitset = ScalarBitSet::<u32>::new();
339    ///
340    /// bitset.insert(10);
341    /// bitset.insert(20);
342    /// bitset.insert(30);
343    ///
344    /// bitset.clear();
345    ///
346    /// assert!(bitset.is_empty());
347    /// ```
348    #[inline]
349    pub fn clear(&mut self) {
350        self.0 = T::from(0);
351    }
352
353    /// Remove and return the largest value in the bitset.
354    ///
355    /// # Example
356    ///
357    /// ```
358    /// use cranelift_bitset::ScalarBitSet;
359    ///
360    /// let mut bitset = ScalarBitSet::<u64>::new();
361    ///
362    /// bitset.insert(0);
363    /// bitset.insert(24);
364    /// bitset.insert(13);
365    /// bitset.insert(36);
366    ///
367    /// assert_eq!(bitset.pop(), Some(36));
368    /// assert_eq!(bitset.pop(), Some(24));
369    /// assert_eq!(bitset.pop(), Some(13));
370    /// assert_eq!(bitset.pop(), Some(0));
371    /// assert_eq!(bitset.pop(), None);
372    /// ```
373    #[inline]
374    pub fn pop(&mut self) -> Option<u8> {
375        let max = self.max()?;
376        self.remove(max);
377        Some(max)
378    }
379
380    /// Return the smallest number contained in this bitset or `None` if this
381    /// bitset is empty.
382    ///
383    /// # Example
384    ///
385    /// ```
386    /// use cranelift_bitset::ScalarBitSet;
387    ///
388    /// let mut bitset = ScalarBitSet::<u64>::new();
389    ///
390    /// // When the bitset is empty, `min` returns `None`.
391    /// assert_eq!(bitset.min(), None);
392    ///
393    /// bitset.insert(28);
394    /// bitset.insert(1);
395    /// bitset.insert(63);
396    ///
397    /// // When the bitset is not empty, it returns the smallest element.
398    /// assert_eq!(bitset.min(), Some(1));
399    /// ```
400    #[inline]
401    pub fn min(&self) -> Option<u8> {
402        if self.0 == T::from(0) {
403            None
404        } else {
405            Some(self.0.trailing_zeros())
406        }
407    }
408
409    /// Return the largest number contained in the bitset or None if this bitset
410    /// is empty
411    ///
412    /// # Example
413    ///
414    /// ```
415    /// use cranelift_bitset::ScalarBitSet;
416    ///
417    /// let mut bitset = ScalarBitSet::<u64>::new();
418    ///
419    /// // When the bitset is empty, `max` returns `None`.
420    /// assert_eq!(bitset.max(), None);
421    ///
422    /// bitset.insert(0);
423    /// bitset.insert(36);
424    /// bitset.insert(49);
425    ///
426    /// // When the bitset is not empty, it returns the smallest element.
427    /// assert_eq!(bitset.max(), Some(49));
428    /// ```
429    #[inline]
430    pub fn max(&self) -> Option<u8> {
431        if self.0 == T::from(0) {
432            None
433        } else {
434            let leading_zeroes = self.0.leading_zeros();
435            Some(Self::capacity() - leading_zeroes - 1)
436        }
437    }
438
439    /// Iterate over the items in this set.
440    ///
441    /// Items are always yielded in sorted order.
442    ///
443    /// # Example
444    ///
445    /// ```
446    /// use cranelift_bitset::ScalarBitSet;
447    ///
448    /// let mut bitset = ScalarBitSet::<u64>::new();
449    ///
450    /// bitset.insert(19);
451    /// bitset.insert(3);
452    /// bitset.insert(63);
453    /// bitset.insert(0);
454    ///
455    /// assert_eq!(
456    ///     bitset.iter().collect::<Vec<_>>(),
457    ///     [0, 3, 19, 63],
458    /// );
459    /// ```
460    #[inline]
461    pub fn iter(&self) -> Iter<T> {
462        Iter {
463            value: self.0,
464            index: 0,
465        }
466    }
467}
468
469impl<T> IntoIterator for ScalarBitSet<T>
470where
471    T: ScalarBitSetStorage,
472{
473    type Item = u8;
474
475    type IntoIter = Iter<T>;
476
477    #[inline]
478    fn into_iter(self) -> Self::IntoIter {
479        self.iter()
480    }
481}
482
483impl<'a, T> IntoIterator for &'a ScalarBitSet<T>
484where
485    T: ScalarBitSetStorage,
486{
487    type Item = u8;
488
489    type IntoIter = Iter<T>;
490
491    #[inline]
492    fn into_iter(self) -> Self::IntoIter {
493        self.iter()
494    }
495}
496
497/// A trait implemented by all integers that can be used as the backing storage
498/// for a [`ScalarBitSet`].
499///
500/// You shouldn't have to implement this yourself, it is already implemented for
501/// `u{8,16,32,64,128}` and if you need more bits than that, then use
502/// [`CompoundBitSet`][crate::CompoundBitSet] instead.
503pub trait ScalarBitSetStorage:
504    Default
505    + From<u8>
506    + Shl<u8, Output = Self>
507    + Shr<u8, Output = Self>
508    + BitAnd<Output = Self>
509    + BitOr<Output = Self>
510    + Not<Output = Self>
511    + Sub<Output = Self>
512    + Add<Output = Self>
513    + PartialEq
514    + Copy
515{
516    /// Count the number of leading zeros.
517    fn leading_zeros(self) -> u8;
518
519    /// Count the number of trailing zeros.
520    fn trailing_zeros(self) -> u8;
521
522    /// Count the number of bits set in this integer.
523    fn count_ones(self) -> u8;
524}
525
526macro_rules! impl_storage {
527    ( $int:ty ) => {
528        impl ScalarBitSetStorage for $int {
529            fn leading_zeros(self) -> u8 {
530                u8::try_from(self.leading_zeros()).unwrap()
531            }
532
533            fn trailing_zeros(self) -> u8 {
534                u8::try_from(self.trailing_zeros()).unwrap()
535            }
536
537            fn count_ones(self) -> u8 {
538                u8::try_from(self.count_ones()).unwrap()
539            }
540        }
541    };
542}
543
544impl_storage!(u8);
545impl_storage!(u16);
546impl_storage!(u32);
547impl_storage!(u64);
548impl_storage!(u128);
549impl_storage!(usize);
550
551/// An iterator over the elements in a [`ScalarBitSet`].
552pub struct Iter<T> {
553    value: T,
554    index: u8,
555}
556
557impl<T> Iterator for Iter<T>
558where
559    T: ScalarBitSetStorage,
560{
561    type Item = u8;
562
563    #[inline]
564    fn next(&mut self) -> Option<u8> {
565        if self.value == T::from(0) {
566            None
567        } else {
568            let trailing_zeros = self.value.trailing_zeros();
569            let elem = self.index + trailing_zeros;
570            self.index += trailing_zeros + 1;
571            self.value = self.value >> (trailing_zeros + 1);
572            Some(elem)
573        }
574    }
575}
cranelift_bitset/scalar.rs

cranelift_bitset/
scalar.rs
