index-set 0.2.0

bitset implementation with support for atomic operations
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use crate::*;

/// A trait for updating values in a shared bit-set.
pub trait SharedBitSet<T> {
    /// Clears the set
    ///
    /// # Example
    ///
    /// ```rust
    /// use index_set::{SharedBitSet, BitSet};
    /// use std::sync::atomic::AtomicU32;
    ///
    /// let mut bitset: [AtomicU32; 4] = Default::default();
    /// bitset.insert(0);
    /// assert!(!BitSet::is_empty(&bitset[..]));
    ///
    /// bitset.clear();
    /// assert!(BitSet::is_empty(&bitset[..]));
    /// ```
    fn clear(&self);

    /// Inserts the index into the set
    /// Returns `true` if the index was not already set
    ///
    /// # Example
    ///
    /// ```rust
    /// use index_set::{SharedBitSet, BitSet};
    /// use std::sync::atomic::AtomicU32;
    ///
    /// let mut bitset: [AtomicU32; 4] = Default::default();
    /// bitset.insert(0);
    /// assert_eq!(bitset.has(0), true);
    /// ```
    fn insert(&self, index: T) -> Option<bool>;

    /// Removes the index from the set
    /// Returns `true` if the index was set.
    ///
    /// # Example
    ///
    /// ```rust
    /// use index_set::{SharedBitSet, BitSet};
    /// use std::sync::atomic::AtomicU32;
    ///
    /// let mut bitset: [AtomicU32; 4] = Default::default();
    /// bitset.insert(42);
    /// assert_eq!(bitset.has(42), true);
    ///
    /// bitset.remove(42);
    /// assert_eq!(bitset.has(42), false);
    /// ```
    fn remove(&self, index: T) -> Option<bool>;
}

impl<Set, T> SharedBitSet<T> for &Set
where
    Set: SharedBitSet<T> + ?Sized,
{
    #[inline]
    fn clear(&self) {
        SharedBitSet::clear(*self);
    }

    #[inline]
    fn insert(&self, index: T) -> Option<bool> {
        SharedBitSet::insert(*self, index)
    }

    #[inline]
    fn remove(&self, index: T) -> Option<bool> {
        SharedBitSet::remove(*self, index)
    }
}

macro_rules! impl_shared_bit_set {
    [$($ty:tt for $target: ty)*] => {$(
        impl SharedBitSet<$ty> for [$target] {
            fn clear(&self) {
                for slot in self.iter() {
                    slot.store(0, Ordering::Release);
                }
            }

            #[inline]
            fn insert(&self, index: $ty) -> Option<bool> {
                let slot_idx = usize::try_from(index / $ty::BITS as $ty).ok()?;
                let mask = 1 << (index % $ty::BITS as $ty);

                let slot = self
                    .get(slot_idx)?
                    .fetch_or(mask, Ordering::Release);

                Some(slot & mask != 0)
            }

            #[inline]
            fn remove(&self, index: $ty) -> Option<bool> {
                let slot_idx = usize::try_from(index / $ty::BITS as $ty).ok()?;
                let mask = 1 << (index % $ty::BITS as $ty);

                let slot = self
                    .get(slot_idx)?
                    .fetch_and(!mask, Ordering::Release);

                Some(slot & mask != 0)
            }
        }
    )*};
}

impl_shared_bit_set! {
    u32 for AtomicU32
    u64 for AtomicU64
    usize for AtomicUsize
}