index_set/
shared_bitset.rs

1use crate::*;
2
3/// A trait for updating values in a shared bit-set.
4pub trait SharedBitSet<T> {
5    /// Clears the set
6    ///
7    /// # Example
8    ///
9    /// ```rust
10    /// use index_set::{SharedBitSet, BitSet};
11    /// use std::sync::atomic::AtomicU32;
12    ///
13    /// let mut bitset: [AtomicU32; 4] = Default::default();
14    /// bitset.insert(0);
15    /// assert!(!BitSet::is_empty(&bitset[..]));
16    ///
17    /// bitset.clear();
18    /// assert!(BitSet::is_empty(&bitset[..]));
19    /// ```
20    fn clear(&self);
21
22    /// Inserts the index into the set
23    /// Returns `true` if the index was not already set
24    ///
25    /// # Example
26    ///
27    /// ```rust
28    /// use index_set::{SharedBitSet, BitSet};
29    /// use std::sync::atomic::AtomicU32;
30    ///
31    /// let mut bitset: [AtomicU32; 4] = Default::default();
32    /// bitset.insert(0);
33    /// assert_eq!(bitset.has(0), true);
34    /// ```
35    fn insert(&self, index: T) -> Option<bool>;
36
37    /// Removes the index from the set
38    /// Returns `true` if the index was set.
39    ///
40    /// # Example
41    ///
42    /// ```rust
43    /// use index_set::{SharedBitSet, BitSet};
44    /// use std::sync::atomic::AtomicU32;
45    ///
46    /// let mut bitset: [AtomicU32; 4] = Default::default();
47    /// bitset.insert(42);
48    /// assert_eq!(bitset.has(42), true);
49    ///
50    /// bitset.remove(42);
51    /// assert_eq!(bitset.has(42), false);
52    /// ```
53    fn remove(&self, index: T) -> Option<bool>;
54}
55
56impl<Set, T> SharedBitSet<T> for &Set
57where
58    Set: SharedBitSet<T> + ?Sized,
59{
60    #[inline]
61    fn clear(&self) {
62        SharedBitSet::clear(*self);
63    }
64
65    #[inline]
66    fn insert(&self, index: T) -> Option<bool> {
67        SharedBitSet::insert(*self, index)
68    }
69
70    #[inline]
71    fn remove(&self, index: T) -> Option<bool> {
72        SharedBitSet::remove(*self, index)
73    }
74}
75
76macro_rules! impl_shared_bit_set {
77    [$($ty:tt for $target: ty)*] => {$(
78        impl SharedBitSet<$ty> for [$target] {
79            fn clear(&self) {
80                for slot in self.iter() {
81                    slot.store(0, Ordering::Release);
82                }
83            }
84
85            #[inline]
86            fn insert(&self, index: $ty) -> Option<bool> {
87                let slot_idx = usize::try_from(index / $ty::BITS as $ty).ok()?;
88                let mask = 1 << (index % $ty::BITS as $ty);
89
90                let slot = self
91                    .get(slot_idx)?
92                    .fetch_or(mask, Ordering::Release);
93
94                Some(slot & mask != 0)
95            }
96
97            #[inline]
98            fn remove(&self, index: $ty) -> Option<bool> {
99                let slot_idx = usize::try_from(index / $ty::BITS as $ty).ok()?;
100                let mask = 1 << (index % $ty::BITS as $ty);
101
102                let slot = self
103                    .get(slot_idx)?
104                    .fetch_and(!mask, Ordering::Release);
105
106                Some(slot & mask != 0)
107            }
108        }
109    )*};
110}
111
112impl_shared_bit_set! {
113    u32 for AtomicU32
114    u64 for AtomicU64
115    usize for AtomicUsize
116}
index_set/shared_bitset.rs

index_set/
shared_bitset.rs
