avian3d/data_structures/
bit_vec.rs

1//! A minimalistic dynamically sized compact bit vector with a fixed block size of 64 bits.
2//!
3//! Only a very limited set of operations are supported.
4
5use core::ops::BitOrAssign;
6use core::slice;
7
8/// A dynamically sized compact bit vector with a fixed block size of 64 bits.
9#[derive(Clone, Debug, Default)]
10#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
11pub struct BitVec {
12    blocks: Vec<u64>,
13    block_capacity: usize,
14    block_count: usize,
15}
16
17#[inline]
18fn bits_to_blocks(bits: usize) -> usize {
19    bits.div_ceil(u64::BITS as usize)
20}
21
22impl BitVec {
23    /// Creates a new [`BitVec`] with the specified bit capacity.
24    #[inline]
25    pub fn new(bit_capacity: usize) -> Self {
26        let block_capacity = bits_to_blocks(bit_capacity);
27
28        Self {
29            blocks: vec![0; block_capacity * size_of::<u64>()],
30            block_capacity,
31            block_count: 0,
32        }
33    }
34
35    /// Sets the bit count of the [`BitVec`] and clears all bits.
36    ///
37    /// If the new bit count exceeds the current block capacity, the block capacity is increased.
38    #[inline]
39    pub fn set_bit_count_and_clear(&mut self, bit_count: usize) {
40        let block_count = bits_to_blocks(bit_count);
41
42        if self.block_capacity < block_count {
43            let new_bit_capacity = bit_count + (bit_count >> 1);
44            *self = Self::new(new_bit_capacity);
45        }
46
47        self.block_count = block_count;
48        self.blocks.iter_mut().for_each(|b| *b = 0);
49    }
50
51    /// Sets the bit count of the [`BitVec`] and sets all bits.
52    ///
53    /// # Panics
54    ///
55    /// Panics if the new bit count exceeds the current block capacity with `debug_assertions` enabled.
56    #[inline]
57    pub fn set(&mut self, index: usize) {
58        let block_index = index / 64;
59        debug_assert!(block_index < self.block_count);
60        let bit_index = index % 64;
61        let mask = 1 << bit_index;
62        self.blocks[block_index] |= mask;
63    }
64
65    /// Unsets the bit at the specified index.
66    #[inline]
67    pub fn unset(&mut self, index: usize) {
68        let block_index = index / 64;
69        if block_index >= self.block_count {
70            return;
71        }
72        let bit_index = index % 64;
73        let mask = 1 << bit_index;
74        self.blocks[block_index] &= !mask;
75    }
76
77    /// Gets the bit at the specified index.
78    ///
79    /// Returns `false` if the index is out of bounds or the bit is unset.
80    #[inline]
81    pub fn get(&self, index: usize) -> bool {
82        let block_index = index / 64;
83        if block_index >= self.block_count {
84            return false;
85        }
86        let bit_index = index % 64;
87        let mask = 1 << bit_index;
88        (self.blocks[block_index] & mask) != 0
89    }
90
91    /// Returns the block capacity of the [`BitVec`].
92    #[inline]
93    pub fn block_capacity(&self) -> usize {
94        self.block_capacity
95    }
96
97    /// Returns the block count of the [`BitVec`].
98    #[inline]
99    pub fn block_count(&self) -> usize {
100        self.block_count
101    }
102
103    /// Clears all bits in the [`BitVec`].
104    #[inline]
105    pub fn clear(&mut self) {
106        self.blocks.iter_mut().for_each(|b| *b = 0);
107    }
108
109    /// Returns an iterator over the blocks of the [`BitVec`].
110    #[inline]
111    pub fn blocks(&self) -> Blocks {
112        Blocks {
113            iter: self.blocks.iter(),
114        }
115    }
116
117    /// Performs an in-place bitwise OR operation with another [`BitVec`].
118    #[inline]
119    pub fn or(&mut self, other: &Self) {
120        debug_assert!(
121            self.block_count == other.block_count,
122            "block counts do not match for `BitVec::or` ({} != {})",
123            self.block_count,
124            other.block_count
125        );
126
127        for i in 0..self.block_count {
128            self.blocks[i] |= other.blocks[i];
129        }
130    }
131}
132
133impl BitOrAssign<&BitVec> for BitVec {
134    #[inline]
135    fn bitor_assign(&mut self, rhs: &BitVec) {
136        self.or(rhs);
137    }
138}
139
140/// An iterator over the blocks of a [`BitVec`].
141#[derive(Clone)]
142pub struct Blocks<'a> {
143    iter: slice::Iter<'a, u64>,
144}
145
146impl Iterator for Blocks<'_> {
147    type Item = u64;
148
149    #[inline]
150    fn next(&mut self) -> Option<u64> {
151        self.iter.next().cloned()
152    }
153
154    #[inline]
155    fn size_hint(&self) -> (usize, Option<usize>) {
156        self.iter.size_hint()
157    }
158}
159
160impl DoubleEndedIterator for Blocks<'_> {
161    #[inline]
162    fn next_back(&mut self) -> Option<u64> {
163        self.iter.next_back().cloned()
164    }
165}
166
167impl ExactSizeIterator for Blocks<'_> {}
avian3d/data_structures/bit_vec.rs

avian3d/data_structures/
bit_vec.rs
