bones_ecs/
bitset.rs

1//! Bitset implementation.
2//!
3//! Bitsets are powered by the [`bitset_core`] crate.
4//!
5//! A Bones bitset is a vector of 32-byte sectors. The size of a bitset can be controlled by the
6//! `keysize*` features (note that they are all mutually exclusive with each other). The `keysize`
7//! is exponentially correlated to the number of bits, or entities, that the set can track; where
8//! the number of bits equals two raised to the power of `keysize`. Below are the available
9//! `keysize`s and the size of their resulting bitsets.
10//!
11//! | Keysize | Bit Count  | Sectors    | Memory |
12//! | ------- | ---------- | ---------- | ------ |
13//! |      32 |  4 billion | 16 million | 512 MB |
14//! |      24 | 16 million |      65536 |   2 MB |
15//! |      20 |  1 million |       4096 | 128 KB |
16//! |      16 |      65536 |        256 |   8 KB |
17//! |      12 |       4096 |         16 | 512  B |
18//! |      10 |       1024 |          4 | 128  B |
19//!
20//! Keysize (`K`) refers to the name of the feature. A keysize of 16 refers to the `keysize16`
21//! feature.
22//!
23//! Bit Count is the total number of bits in the bitset (`2^K`). Due to the nature of binary
24//! numbers this means that a value with more than `K` bits should not be used to index into the
25//! bitset since e.g. `u16::MAX` is the index of the last bit in a `keysize16` bitset.
26//!
27//! Sectors is the number of sub-arrays within the bitset `Vec`. Sectors are 256 bits as they are
28//! comprised of 8 `u32`s. Note that SIMD instructions process 256 bits/entities at a time.
29//!
30//! Memory is the total amount of memory that the bitset will occupy.
31//!
32//! [`bitset_core`]: https://docs.rs/bitset_core
33
34use crate::prelude::*;
35
36#[cfg(all(
37    feature = "keysize10",
38    not(feature = "keysize12"),
39    not(feature = "keysize16"),
40    not(feature = "keysize20"),
41    not(feature = "keysize24"),
42    not(feature = "keysize32")
43))]
44#[allow(missing_docs)]
45pub const BITSET_EXP: u32 = 10;
46
47#[cfg(all(
48    feature = "keysize12",
49    not(feature = "keysize10"),
50    not(feature = "keysize16"),
51    not(feature = "keysize20"),
52    not(feature = "keysize24"),
53    not(feature = "keysize32")
54))]
55#[allow(missing_docs)]
56pub const BITSET_EXP: u32 = 12;
57
58// 16 is the default, if no `keysize*` features are enabled then use this one.
59#[cfg(any(
60    feature = "keysize16",
61    all(
62        not(feature = "keysize10"),
63        not(feature = "keysize12"),
64        not(feature = "keysize20"),
65        not(feature = "keysize24"),
66        not(feature = "keysize32")
67    )
68))]
69#[allow(missing_docs)]
70pub const BITSET_EXP: u32 = 16;
71
72#[cfg(all(
73    feature = "keysize20",
74    not(feature = "keysize10"),
75    not(feature = "keysize12"),
76    not(feature = "keysize16"),
77    not(feature = "keysize24"),
78    not(feature = "keysize32")
79))]
80#[allow(missing_docs)]
81pub const BITSET_EXP: u32 = 20;
82
83#[cfg(all(
84    feature = "keysize24",
85    not(feature = "keysize10"),
86    not(feature = "keysize12"),
87    not(feature = "keysize16"),
88    not(feature = "keysize20"),
89    not(feature = "keysize32")
90))]
91#[allow(missing_docs)]
92pub const BITSET_EXP: u32 = 24;
93
94#[cfg(all(
95    feature = "keysize32",
96    not(feature = "keysize10"),
97    not(feature = "keysize12"),
98    not(feature = "keysize16"),
99    not(feature = "keysize20"),
100    not(feature = "keysize24")
101))]
102#[allow(missing_docs)]
103pub const BITSET_EXP: u32 = 32;
104
105pub use bitset_core::*;
106
107/// The number of bits in a bitset.
108pub(crate) const BITSET_SIZE: usize = 2usize.saturating_pow(BITSET_EXP);
109
110/// The number of bits in a bitset "sector" (one of the sub-arrays).
111///
112/// A sector is an array of 8 `u32` values, so there are `8 * 32` bits in a sector.
113///
114/// This value is constant, as a sector is appropriately sized to fit into a vector register for
115/// SIMD instructions.
116const BITSET_SECTOR_SIZE: usize = 32 * 8;
117
118const BITSET_SECTOR_COUNT: usize = BITSET_SIZE / BITSET_SECTOR_SIZE;
119
120/// The type of bitsets used to track entities in component storages.
121/// Mostly used to create caches.
122#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
123#[derive(Deref, DerefMut, Clone, Debug)]
124pub struct BitSetVec(pub Vec<[u32; 8]>);
125
126impl Default for BitSetVec {
127    fn default() -> Self {
128        create_bitset()
129    }
130}
131
132impl BitSetVec {
133    /// Check whether or not the bitset contains the given entity.
134    #[inline]
135    pub fn contains(&self, entity: Entity) -> bool {
136        self.bit_test(entity.index() as usize)
137    }
138
139    /// Set an entity on the the bitset.
140    #[inline]
141    pub fn set(&mut self, entity: Entity) {
142        self.bit_set(entity.index() as usize);
143    }
144}
145
146/// Creates a bitset big enough to contain the index of each entity.
147/// Mostly used to create caches.
148pub fn create_bitset() -> BitSetVec {
149    BitSetVec(vec![[0u32; 8]; BITSET_SECTOR_COUNT])
150}
bones_ecs/bitset.rs

bones_ecs/
bitset.rs
