bitflagset/
atomic_boxed.rs

1use alloc::boxed::Box;
2use alloc::vec::Vec;
3use core::marker::PhantomData;
4use core::ops::Deref;
5use core::sync::atomic::Ordering;
6use num_traits::{PrimInt, Zero};
7use radium::Radium;
8
9use super::atomic_slice::AtomicBitSlice;
10use super::boxed::BoxedBitSet;
11
12/// Heap-allocated atomic bitset with dynamically sized storage.
13///
14/// `AtomicBoxedBitSet<A, V>` is the atomic counterpart of
15/// [`BoxedBitSet`](super::BoxedBitSet). It owns a `Box<[A]>` of atomic words
16/// and delegates common operations to [`AtomicBitSlice<A, V>`] via `Deref`.
17///
18/// # Atomicity guarantees
19///
20/// Each individual method (`insert`, `remove`, `contains`, ...) performs atomic
21/// operations **per word**. The bitset as a whole is **not** a single atomic
22/// unit — concurrent modifications to bits in different words are independent
23/// atomic operations with no cross-word transactional guarantee. See
24/// [`AtomicBitSlice`] for details.
25pub struct AtomicBoxedBitSet<A, V>(Box<[A]>, PhantomData<V>);
26
27impl<A: Radium, V> Deref for AtomicBoxedBitSet<A, V>
28where
29    A::Item: PrimInt,
30{
31    type Target = AtomicBitSlice<A, V>;
32
33    #[inline]
34    fn deref(&self) -> &Self::Target {
35        AtomicBitSlice::from_slice_ref(&self.0)
36    }
37}
38
39impl<A: Radium, V> AtomicBoxedBitSet<A, V>
40where
41    A::Item: PrimInt,
42{
43    pub fn from_boxed_slice(store: Box<[A]>) -> Self {
44        Self(store, PhantomData)
45    }
46}
47
48impl<A: Radium + Default, V> AtomicBoxedBitSet<A, V>
49where
50    A::Item: PrimInt,
51{
52    pub fn with_capacity(bits: usize) -> Self {
53        let bits_per = core::mem::size_of::<A>() * 8;
54        let store_size = bits.div_ceil(bits_per);
55        let mut store = Vec::new();
56        store.resize_with(store_size, A::default);
57        Self(store.into_boxed_slice(), PhantomData)
58    }
59}
60
61impl<A: Radium, V> AtomicBoxedBitSet<A, V>
62where
63    A::Item: PrimInt,
64{
65    /// Atomically drain all bits, returning a non-atomic [`BoxedBitSet`]
66    /// containing the drained values. The source is left empty.
67    ///
68    /// Each word is swapped independently — this is NOT an atomic snapshot
69    /// of the entire bitset.
70    pub fn drain(&self) -> BoxedBitSet<A::Item, V>
71    where
72        A::Item: Default,
73    {
74        let mut drained = BoxedBitSet::<A::Item, V>::with_capacity(self.capacity());
75        for (source, target) in self.0.iter().zip(drained.as_raw_mut_slice().iter_mut()) {
76            *target = source.swap(A::Item::zero(), Ordering::AcqRel);
77        }
78        drained
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85    use alloc::vec;
86    use alloc::vec::Vec;
87    use core::sync::atomic::AtomicU64;
88    use proptest::prelude::*;
89
90    #[test]
91    fn test_boxed_basic() {
92        let bs = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
93        assert!(bs.is_empty());
94        assert_eq!(bs.len(), 0);
95        assert_eq!(bs.capacity(), 256);
96
97        assert!(bs.insert(0));
98        assert!(!bs.insert(0));
99        assert!(bs.insert(63));
100        assert!(bs.insert(64));
101        assert!(bs.insert(200));
102
103        assert!(!bs.is_empty());
104        assert_eq!(bs.len(), 4);
105
106        assert!(bs.contains(&0));
107        assert!(bs.contains(&63));
108        assert!(bs.contains(&64));
109        assert!(bs.contains(&200));
110        assert!(!bs.contains(&1));
111
112        assert!(bs.remove(63));
113        assert!(!bs.remove(63));
114        assert_eq!(bs.len(), 3);
115
116        bs.clear();
117        assert!(bs.is_empty());
118        assert_eq!(bs.len(), 0);
119    }
120
121    #[test]
122    fn test_boxed_boundary() {
123        // 256 bits
124        let bs = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
125        bs.insert(0);
126        bs.insert(255);
127        assert_eq!(bs.len(), 2);
128        assert!(bs.contains(&0));
129        assert!(bs.contains(&255));
130
131        let items: Vec<usize> = bs.iter().collect();
132        assert_eq!(items, vec![0, 255]);
133
134        bs.remove(255);
135        assert!(!bs.contains(&255));
136
137        // 65536 bits
138        let bs = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(65536);
139        bs.insert(0);
140        bs.insert(65535);
141        bs.insert(32768);
142        assert_eq!(bs.len(), 3);
143
144        let items: Vec<usize> = bs.iter().collect();
145        assert_eq!(items, vec![0, 32768, 65535]);
146
147        bs.remove(65535);
148        assert!(!bs.contains(&65535));
149        assert_eq!(bs.len(), 2);
150    }
151
152    #[test]
153    fn test_boxed_drain() {
154        let bs = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
155        bs.insert(3);
156        bs.insert(100);
157        bs.insert(200);
158
159        let drained = bs.drain();
160        assert!(bs.is_empty());
161
162        let items: Vec<usize> = drained.iter().collect();
163        assert_eq!(items, vec![3, 100, 200]);
164    }
165
166    #[test]
167    fn test_boxed_set_relations() {
168        let a = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
169        a.insert(1);
170        a.insert(65);
171
172        let b = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
173        b.insert(1);
174        b.insert(65);
175        b.insert(200);
176
177        let c = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
178        c.insert(2);
179        c.insert(66);
180
181        assert!(a.is_subset(&b));
182        assert!(!b.is_subset(&a));
183        assert!(b.is_superset(&a));
184        assert!(!a.is_superset(&b));
185        assert!(a.is_disjoint(&c));
186        assert!(!a.is_disjoint(&b));
187    }
188
189    #[test]
190    fn test_mismatched_capacity_subset() {
191        // small ⊂ large: small has bits only in shared range
192        let small = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(64);
193        small.insert(1);
194        let large = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
195        large.insert(1);
196        large.insert(200);
197        assert!(small.is_subset(&large));
198        assert!(!large.is_subset(&small)); // large has bit 200 beyond small's range
199
200        // small with bits set is NOT subset of empty large
201        let s2 = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(128);
202        s2.insert(100);
203        let l2 = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(64);
204        assert!(!s2.is_subset(&l2)); // bit 100 is beyond l2's range
205
206        // empty is always subset
207        let empty = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(64);
208        assert!(empty.is_subset(&large));
209        assert!(empty.is_subset(&small));
210    }
211
212    #[test]
213    fn test_mismatched_capacity_disjoint() {
214        let a = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(64);
215        a.insert(1);
216        let b = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
217        b.insert(200); // beyond a's range, no overlap
218        assert!(a.is_disjoint(&b));
219
220        b.insert(1); // now overlaps
221        assert!(!a.is_disjoint(&b));
222    }
223
224    #[test]
225    fn test_boxed_toggle() {
226        let bs = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(256);
227        bs.insert(10);
228        bs.toggle(10);
229        assert!(!bs.contains(&10));
230        bs.toggle(10);
231        assert!(bs.contains(&10));
232        bs.toggle(200);
233        assert!(bs.contains(&200));
234    }
235
236    proptest! {
237        #[test]
238        fn parity_atomic_boxed_65536(ops in prop::collection::vec((any::<bool>(), 0..65536usize), 0..200)) {
239            let atomic = AtomicBoxedBitSet::<AtomicU64, usize>::with_capacity(65536);
240            let mut plain = BoxedBitSet::<u64, usize>::with_capacity(65536);
241
242            for &(insert, idx) in &ops {
243                if insert {
244                    atomic.insert(idx);
245                    plain.insert(idx);
246                } else {
247                    atomic.remove(idx);
248                    plain.remove(idx);
249                }
250            }
251
252            prop_assert_eq!(atomic.len(), plain.len(), "len mismatch");
253            prop_assert_eq!(atomic.is_empty(), plain.is_empty(), "is_empty mismatch");
254
255            let atomic_bits: Vec<usize> = atomic.iter().collect();
256            let plain_bits: Vec<usize> = plain.iter().collect();
257            prop_assert_eq!(atomic_bits, plain_bits, "iter mismatch");
258        }
259    }
260}
bitflagset/atomic_boxed.rs

bitflagset/
atomic_boxed.rs
