box3d_rust/
bitset.rs

1// Port of box3d-cpp-reference/src/bitset.h and src/bitset.c (plus b3CountSetBits
2// from table.c). A bit set provides fast operations on large arrays of bits.
3//
4// The C struct owns a raw `uint64_t*` with separate `blockCapacity` and
5// `blockCount`. The Rust port stores the blocks in a `Vec<u64>` whose length is
6// always the capacity, and keeps `block_count` as the logical size. That
7// preserves the C distinction exactly: reads and clears past `block_count` are
8// no-ops even when the capacity is larger, and the growth policy matches.
9//
10// SPDX-FileCopyrightText: 2025 Erin Catto
11// SPDX-License-Identifier: MIT
12
13use crate::core::pop_count64;
14
15/// Bit set providing fast operations on large arrays of bits.
16#[derive(Debug, Clone, Default)]
17pub struct BitSet {
18    /// Backing storage. `blocks.len()` is the block capacity.
19    pub(crate) blocks: Vec<u64>,
20    /// Logical number of active blocks (`blockCount` in C).
21    pub(crate) block_count: u32,
22}
23
24impl BitSet {
25    /// (b3CreateBitSet)
26    pub fn new(bit_capacity: u32) -> BitSet {
27        let block_capacity = bit_capacity.div_ceil(u64::BITS);
28        BitSet {
29            blocks: vec![0; block_capacity as usize],
30            block_count: 0,
31        }
32    }
33
34    /// Release the storage. (b3DestroyBitSet)
35    ///
36    /// Rust would drop the storage automatically; this mirrors the C function so
37    /// ported call sites read the same.
38    pub fn destroy(&mut self) {
39        self.blocks = Vec::new();
40        self.block_count = 0;
41    }
42
43    /// The allocated block capacity (`blockCapacity` in C).
44    fn block_capacity(&self) -> u32 {
45        self.blocks.len() as u32
46    }
47
48    /// (b3SetBitCountAndClear)
49    pub fn set_bit_count_and_clear(&mut self, bit_count: u32) {
50        let block_count = bit_count.div_ceil(u64::BITS);
51        if self.block_capacity() < block_count {
52            self.destroy();
53            let new_bit_capacity = bit_count + (bit_count >> 1);
54            *self = BitSet::new(new_bit_capacity);
55        }
56
57        self.block_count = block_count;
58        for block in &mut self.blocks[..block_count as usize] {
59            *block = 0;
60        }
61    }
62
63    /// (b3GrowBitSet)
64    pub fn grow(&mut self, block_count: u32) {
65        debug_assert!(block_count > self.block_count);
66        if block_count > self.block_capacity() {
67            // C: new capacity = blockCount + blockCount / 2, freshly zeroed, with
68            // the old capacity's blocks copied in. Vec::resize preserves existing
69            // elements [0, old_len) and zero-fills the new tail, which matches
70            // because old_len == old capacity.
71            let new_capacity = block_count + block_count / 2;
72            self.blocks.resize(new_capacity as usize, 0);
73        }
74
75        self.block_count = block_count;
76    }
77
78    /// In-place union: `self |= other`. (b3InPlaceUnion)
79    pub fn in_place_union(&mut self, other: &BitSet) {
80        debug_assert!(self.block_count == other.block_count);
81        let block_count = self.block_count as usize;
82        for i in 0..block_count {
83            self.blocks[i] |= other.blocks[i];
84        }
85    }
86
87    /// Count the number of set bits. (b3CountSetBits, from table.c)
88    pub fn count_set_bits(&self) -> i32 {
89        let mut pop_count = 0;
90        for i in 0..self.block_count as usize {
91            pop_count += pop_count64(self.blocks[i]);
92        }
93        pop_count
94    }
95
96    /// Set a bit that must lie within the current block count. (b3SetBit)
97    pub fn set_bit(&mut self, bit_index: u32) {
98        let block_index = bit_index / 64;
99        debug_assert!(block_index < self.block_count);
100        self.blocks[block_index as usize] |= 1u64 << (bit_index % 64);
101    }
102
103    /// Set a bit, growing the set if needed. (b3SetBitGrow)
104    pub fn set_bit_grow(&mut self, bit_index: u32) {
105        let block_index = bit_index / 64;
106        if block_index >= self.block_count {
107            self.grow(block_index + 1);
108        }
109        self.blocks[block_index as usize] |= 1u64 << (bit_index % 64);
110    }
111
112    /// Clear a bit. Out-of-range indices are ignored. (b3ClearBit)
113    pub fn clear_bit(&mut self, bit_index: u32) {
114        let block_index = bit_index / 64;
115        if block_index >= self.block_count {
116            return;
117        }
118        self.blocks[block_index as usize] &= !(1u64 << (bit_index % 64));
119    }
120
121    /// Get a bit. Out-of-range indices read as false. (b3GetBit)
122    pub fn get_bit(&self, bit_index: u32) -> bool {
123        let block_index = bit_index / 64;
124        if block_index >= self.block_count {
125            return false;
126        }
127        (self.blocks[block_index as usize] & (1u64 << (bit_index % 64))) != 0
128    }
129
130    /// Byte size of the allocated storage. (b3GetBitSetBytes)
131    pub fn bytes(&self) -> i32 {
132        self.block_capacity() as i32 * core::mem::size_of::<u64>() as i32
133    }
134
135    /// Number of active 64-bit blocks (`blockCount` in C). Used together with
136    /// [`BitSet::block`] to port the C word/CTZ set-bit iteration loops.
137    pub fn block_count(&self) -> u32 {
138        self.block_count
139    }
140
141    /// The k-th active 64-bit block (`bits[k]` in C).
142    pub fn block(&self, block_index: u32) -> u64 {
143        debug_assert!(block_index < self.block_count);
144        self.blocks[block_index as usize]
145    }
146}
box3d_rust/bitset.rs

box3d_rust/
bitset.rs
