index_set/
bitset.rs

1use crate::*;
2
3/// A trait for reading values from a bit set.
4pub trait BitSet<T> {
5    /// Returns the number of bits that can be stored in the set.
6    ///
7    /// # Example
8    ///
9    /// ```rust
10    /// use index_set::BitSet;
11    ///
12    /// let bitset: &[u32] = &[0; 4];
13    /// assert_eq!(bitset.capacity(), 128);
14    /// ```
15    fn capacity(&self) -> T;
16
17    /// Returns `true` if the set contains the given value.
18    ///
19    /// # Example
20    ///
21    /// ```rust
22    /// use index_set::{BitSet, BitSetMut};
23    ///
24    /// let mut bitset: [u32; 4] = [0; 4];
25    /// bitset.insert(0);
26    /// assert!(bitset.has(0));
27    /// ```
28    fn has(&self, _: T) -> bool;
29
30    /// Returns `true` if the set is empty.
31    ///
32    /// # Example
33    ///
34    /// ```rust
35    /// use index_set::{BitSet, BitSetMut};
36    ///
37    /// let mut bitset: [u32; 4] = [0; 4];
38    /// assert!(BitSet::is_empty(&bitset[..]));
39    ///
40    /// bitset.insert(0);
41    /// assert!(!BitSet::is_empty(&bitset[..]));
42    /// ```
43    fn is_empty(&self) -> bool;
44
45    /// Returns the number of values in the set.
46    ///
47    /// # Example
48    ///
49    /// ```rust
50    /// use index_set::{BitSet, BitSetMut};
51    ///
52    /// let mut bitset: [u32; 4] = [0; 4];
53    ///
54    /// bitset.insert(0);
55    /// assert_eq!(bitset.size(), 1);
56    /// ```
57    fn size(&self) -> T;
58}
59
60macro_rules! impl_deref {
61    ($($target: ty),*) => {$(
62        impl<Set, T> BitSet<T> for $target
63        where
64            Set: BitSet<T> + ?Sized,
65        {
66            #[inline]
67            fn capacity(&self) -> T {
68                BitSet::capacity(&**self)
69            }
70
71            #[inline]
72            fn has(&self, index: T) -> bool {
73                BitSet::has(&**self, index)
74            }
75
76            #[inline]
77            fn is_empty(&self) -> bool {
78                BitSet::is_empty(&**self)
79            }
80
81            #[inline]
82            fn size(&self) -> T {
83                BitSet::size(&**self)
84            }
85        }
86    )*}
87}
88
89impl_deref! {
90    &Set, Box<Set>
91}
92
93macro_rules! impl_bit_set {
94    [$($ty:tt),*] => {$(
95        impl BitSet<$ty> for [$ty] {
96            #[inline]
97            fn capacity(&self) -> $ty {
98                self.len() as $ty * $ty::BITS as $ty
99            }
100
101            #[inline]
102            fn has(&self, index: $ty) -> bool {
103                 let slot_idx = match usize::try_from(index / $ty::BITS as $ty) {
104                    Ok(slot_idx) => slot_idx,
105                    Err(_) => return false,
106                };
107                let mask = 1 << (index % $ty::BITS as $ty);
108                self.get(slot_idx).is_some_and(|slot| slot & mask != 0)
109            }
110
111            #[inline]
112            fn is_empty(&self) -> bool {
113                self.iter().all(|&slot| slot == 0)
114            }
115
116            #[inline]
117            fn size(&self) -> $ty {
118                self.iter().map(|slot| slot.count_ones() as $ty).sum()
119            }
120        }
121    )*};
122}
123
124macro_rules! impl_atomic_bit_set {
125    [$($ty:tt for $target: ty)*] => {$(
126        impl BitSet<$ty> for [$target] {
127            fn capacity(&self) -> $ty {
128                self.len() as $ty * $ty::BITS as $ty
129            }
130
131            #[inline]
132            fn has(&self, index: $ty) -> bool {
133                let slot_idx = match usize::try_from(index / $ty::BITS as $ty) {
134                    Ok(slot_idx) => slot_idx,
135                    Err(_) => return false,
136                };
137                let mask = 1 << (index % $ty::BITS as $ty);
138                self.get(slot_idx)
139                    .is_some_and(|slot| slot.load(Ordering::Acquire) & mask != 0)
140            }
141
142            fn is_empty(&self) -> bool {
143                self.iter().all(|slot| slot.load(Ordering::Acquire) == 0)
144            }
145
146            fn size(&self) -> $ty {
147                self.iter()
148                    .map(|slot| slot.load(Ordering::Acquire).count_ones() as $ty)
149                    .sum()
150            }
151        }
152    )*};
153}
154
155impl_bit_set! {
156    u16, u32, u64, usize, u128
157}
158
159impl_atomic_bit_set! {
160    u32 for AtomicU32
161    u64 for AtomicU64
162    usize for AtomicUsize
163}
index_set/bitset.rs

index_set/
bitset.rs
