bitset_core/
lib.rs

1/*!
2BitSet
3======
4
5[![MIT License](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
6[![crates.io](https://img.shields.io/crates/v/bitset-core.svg)](https://crates.io/crates/bitset-core)
7[![docs.rs](https://docs.rs/bitset-core/badge.svg)](https://docs.rs/bitset-core)
8
9Straightforward, no-std compatible, simd optimized, BitSet API.
10
11Examples
12--------
13
14This crate provides its functionality through the `BitSet` trait.
15
16```rust
17use bitset_core::BitSet;
18```
19
20The containers for the bitset provided by this crate are unsigned integers, slices of unsigned integers and simd-like types, and `Vec<_>`, `Box<[_]>` if the `std` feature is enabled (enabled by default).
21
22```rust
23use bitset_core::BitSet;
24
25let mut bits = [0u32; 4];
26assert_eq!(bits.bit_len(), 4 * 32);
27
28bits.bit_init(true); // Set all bits to true
29assert!(bits.bit_all()); // All bits are set
30
31bits.bit_reset(13); // Reset the 13th bit
32assert!(bits.bit_any()); // At least some bits are set
33
34bits.bit_flip(42); // Flip the 42nd bit twice (no change)
35bits.bit_flip(42);
36
37bits.bit_cond(1, false); // Set the bit to runtime value
38
39assert_eq!(bits.bit_test(42), true);
40assert_eq!(bits.bit_test(13), false);
41assert_eq!(bits.bit_test(1), false);
42
43assert_eq!(bits.bit_count(), 4 * 32 - 2);
44```
45
46Simd optimization is provided by using underlying primitives such as `[u32; 4]` which match the hardware's 128-bit simd registers. The compiler is heavily encouraged to vectorize these primitives.
47
48```rust
49use bitset_core::BitSet;
50
51let mut a = [[0x21212121u32; 4]; 16];
52let b = [[0x55555555u32; 4]; 16];
53
54a.bit_or(&b);
55a.bit_and(&b);
56a.bit_xor(&b);
57a.bit_not();
58
59assert_eq!(a, [[0xffffffffu32; 4]; 16]);
60```
61
62For non fixed-size containers using the `std` feature `BitSet` is also implemented for `Vec<T>` and `Box<[T]>` (where `[T]`: `BitSet`).
63
64Future work includes making everything const fn to enable all of this at compiletime, blocked on support for traits in const fn.
65
66License
67-------
68
69Licensed under [MIT License](https://opensource.org/licenses/MIT), see [license.txt](license.txt).
70
71### Contribution
72
73Unless you explicitly state otherwise, any contribution intentionally submitted
74for inclusion in the work by you, shall be licensed as above, without any additional terms or conditions.
75*/
76
77#![no_std]
78
79#[cfg(any(test, feature = "std"))]
80#[macro_use]
81extern crate std;
82
83/// The BitSet API.
84pub trait BitSet {
85	/// Returns total number of bits.
86	fn bit_len(&self) -> usize;
87
88	/// Initializes all bits.
89	fn bit_init(&mut self, value: bool) -> &mut Self;
90	/// Format the bits.
91	#[inline]
92	fn bit_fmt(&self) -> &BitFmt<Self> {
93		unsafe { &*(self as *const _ as *const _) }
94	}
95
96	/// Returns if the given bit is set.
97	fn bit_test(&self, bit: usize) -> bool;
98	/// Sets the given bit.
99	fn bit_set(&mut self, bit: usize) -> &mut Self;
100	/// Resets the given bit.
101	fn bit_reset(&mut self, bit: usize) -> &mut Self;
102	/// Flips the given bit.
103	fn bit_flip(&mut self, bit: usize) -> &mut Self;
104	/// Conditionally sets or resets the given bit.
105	fn bit_cond(&mut self, bit: usize, value: bool) -> &mut Self;
106
107	/// Returns if all bits are set.
108	fn bit_all(&self) -> bool;
109	/// Returns if any bits are set.
110	fn bit_any(&self) -> bool;
111	/// Returns if none of the bits are set.
112	#[inline]
113	fn bit_none(&self) -> bool {
114		!self.bit_any()
115	}
116
117	/// Returns if the two bitsets are equal.
118	fn bit_eq(&self, rhs: &Self) -> bool;
119	/// Returns if the two bitsets have no bits in common.
120	fn bit_disjoint(&self, rhs: &Self) -> bool;
121	/// Returns if self is a subset of rhs.
122	fn bit_subset(&self, rhs: &Self) -> bool;
123	/// Returns if self is a superset of rhs.
124	#[inline]
125	fn bit_superset(&self, rhs: &Self) -> bool {
126		rhs.bit_subset(self)
127	}
128
129	/// Bitwise OR.
130	fn bit_or(&mut self, rhs: &Self) -> &mut Self;
131	/// Bitwise AND.
132	fn bit_and(&mut self, rhs: &Self) -> &mut Self;
133	/// Bitwise AND after NOT of rhs.
134	fn bit_andnot(&mut self, rhs: &Self) -> &mut Self;
135	/// Bitwise XOR.
136	fn bit_xor(&mut self, rhs: &Self) -> &mut Self;
137	/// Bitwise NOT.
138	fn bit_not(&mut self) -> &mut Self;
139	/// Bitwise combine with MASK.
140	fn bit_mask(&mut self, rhs: &Self, mask: &Self) -> &mut Self;
141
142	/// Counts the number of set bits.
143	fn bit_count(&self) -> usize;
144}
145
146/// Shorthand for setting bits on the bitset container.
147///
148/// Returns the value of the initial argument after setting the bits.
149///
150/// ```
151/// use bitset_core::{bitset, BitSet};
152/// let bits = bitset!([0u8; 4]; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31);
153/// assert_eq!(bits.bit_count(), 11);
154/// ```
155#[macro_export]
156macro_rules! bitset {
157	($init:expr; $($bit:expr),* $(,)?) => {{
158		use $crate::BitSet;
159		#[allow(unused_mut)]
160		match $init {
161			mut this => {
162				$(this.bit_set($bit as usize);)*
163				this
164			},
165		}
166	}};
167}
168
169/// Shorthand for combining bitsets with bit_or.
170///
171/// Returns the value of the initial argument after combining the bits.
172///
173/// ```
174/// use bitset_core::{bitor, BitSet};
175/// let bits = bitor!([0u8; 4]; [0x01; 4], [0x10; 4]);
176/// assert_eq!(bits, [0x11; 4]);
177/// ```
178#[macro_export]
179macro_rules! bitor {
180	($init:expr; $($bits:expr),* $(,)?) => {{
181		use $crate::BitSet;
182		#[allow(unused_mut)]
183		match $init {
184			mut this => {
185				$(this.bit_or(&$bits);)*
186				this
187			},
188		}
189	}};
190}
191
192/// Implements the `BitSet` trait members for your type through `DerefMut`.
193///
194/// Unfortunately due to the trait orphan rules it is not possible to automatically provide an implementation for all types implementing DerefMut.
195#[macro_export]
196macro_rules! impl_bitset {
197	() => {
198		#[inline]
199		fn bit_len(&self) -> usize {
200			use ::core::ops;
201			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_len(<Self as ops::Deref>::deref(self))
202		}
203
204		#[inline]
205		fn bit_init(&mut self, value: bool) -> &mut Self {
206			use ::core::ops;
207			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_init(<Self as ops::DerefMut>::deref_mut(self), value);
208			self
209		}
210
211		#[inline]
212		fn bit_test(&self, bit: usize) -> bool {
213			use ::core::ops;
214			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_test(<Self as ops::Deref>::deref(self), bit)
215		}
216		#[inline]
217		fn bit_set(&mut self, bit: usize) -> &mut Self {
218			use ::core::ops;
219			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_set(<Self as ops::DerefMut>::deref_mut(self), bit);
220			self
221		}
222		#[inline]
223		fn bit_reset(&mut self, bit: usize) -> &mut Self {
224			use ::core::ops;
225			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_reset(<Self as ops::DerefMut>::deref_mut(self), bit);
226			self
227		}
228		#[inline]
229		fn bit_flip(&mut self, bit: usize) -> &mut Self {
230			use ::core::ops;
231			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_flip(<Self as ops::DerefMut>::deref_mut(self), bit);
232			self
233		}
234		#[inline]
235		fn bit_cond(&mut self, bit: usize, value: bool) -> &mut Self {
236			use ::core::ops;
237			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_cond(<Self as ops::DerefMut>::deref_mut(self), bit, value);
238			self
239		}
240
241		#[inline]
242		fn bit_all(&self) -> bool {
243			use ::core::ops;
244			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_all(<Self as ops::Deref>::deref(self))
245		}
246		#[inline]
247		fn bit_any(&self) -> bool {
248			use ::core::ops;
249			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_any(<Self as ops::Deref>::deref(self))
250		}
251		#[inline]
252		fn bit_none(&self) -> bool {
253			use ::core::ops;
254			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_none(<Self as ops::Deref>::deref(self))
255		}
256
257		#[inline]
258		fn bit_eq(&self, rhs: &Self) -> bool {
259			use ::core::ops;
260			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_eq(<Self as ops::Deref>::deref(self), <Self as ops::Deref>::deref(rhs))
261		}
262		#[inline]
263		fn bit_disjoint(&self, rhs: &Self) -> bool {
264			use ::core::ops;
265			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_disjoint(<Self as ops::Deref>::deref(self), <Self as ops::Deref>::deref(rhs))
266		}
267		#[inline]
268		fn bit_subset(&self, rhs: &Self) -> bool {
269			use ::core::ops;
270			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_subset(<Self as ops::Deref>::deref(self), <Self as ops::Deref>::deref(rhs))
271		}
272		#[inline]
273		fn bit_superset(&self, rhs: &Self) -> bool {
274			use ::core::ops;
275			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_superset(<Self as ops::Deref>::deref(self), <Self as ops::Deref>::deref(rhs))
276		}
277
278		#[inline]
279		fn bit_or(&mut self, rhs: &Self) -> &mut Self {
280			use ::core::ops;
281			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_or(<Self as ops::DerefMut>::deref_mut(self), <Self as ops::Deref>::deref(rhs));
282			self
283		}
284		#[inline]
285		fn bit_and(&mut self, rhs: &Self) -> &mut Self {
286			use ::core::ops;
287			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_and(<Self as ops::DerefMut>::deref_mut(self), <Self as ops::Deref>::deref(rhs));
288			self
289		}
290		#[inline]
291		fn bit_andnot(&mut self, rhs: &Self) -> &mut Self {
292			use ::core::ops;
293			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_andnot(<Self as ops::DerefMut>::deref_mut(self), <Self as ops::Deref>::deref(rhs));
294			self
295		}
296		#[inline]
297		fn bit_xor(&mut self, rhs: &Self) -> &mut Self {
298			use ::core::ops;
299			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_xor(<Self as ops::DerefMut>::deref_mut(self), <Self as ops::Deref>::deref(rhs));
300			self
301		}
302		#[inline]
303		fn bit_not(&mut self) -> &mut Self {
304			use ::core::ops;
305			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_not(<Self as ops::DerefMut>::deref_mut(self));
306			self
307		}
308		#[inline]
309		fn bit_mask(&mut self, rhs: &Self, mask: &Self) -> &mut Self {
310			use ::core::ops;
311			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_mask(<Self as ops::DerefMut>::deref_mut(self), <Self as ops::Deref>::deref(rhs), <Self as ops::Deref>::deref(mask));
312			self
313		}
314
315		#[inline]
316		fn bit_count(&self) -> usize {
317			use ::core::ops;
318			<<Self as ops::Deref>::Target as $crate::BitSet>::bit_count(<Self as ops::Deref>::deref(self))
319		}
320	};
321}
322
323mod uint;
324mod slice;
325mod simd;
326
327#[cfg(feature = "std")]
328mod stdty;
329
330mod fmt;
331pub use self::fmt::BitFmt;
332
333//----------------------------------------------------------------
334
335#[cfg(test)]
336fn unary_tests<T: ?Sized + BitSet>(bits: &mut T) {
337	// reset all bits
338	bits.bit_init(false);
339	assert_eq!(bits.bit_any(), false);
340	assert_eq!(bits.bit_all(), false);
341	// set even bits
342	for i in 0..bits.bit_len() {
343		bits.bit_set(i & !1);
344	}
345	assert_eq!(bits.bit_any(), true);
346	assert_eq!(bits.bit_all(), false);
347	for i in 0..bits.bit_len() {
348		assert_eq!(bits.bit_test(i), i & 1 == 0);
349	}
350	// invert all bits and flip back
351	bits.bit_not();
352	for i in 0..bits.bit_len() {
353		bits.bit_flip(i);
354		assert_eq!(bits.bit_test(i), i & 1 == 0);
355	}
356
357	// set all bits
358	bits.bit_init(true);
359	assert_eq!(bits.bit_any(), true);
360	assert_eq!(bits.bit_all(), true);
361	// clear even bits
362	for i in 0..bits.bit_len() {
363		bits.bit_reset(i & !1);
364	}
365	assert_eq!(bits.bit_any(), true);
366	assert_eq!(bits.bit_all(), false);
367	for i in 0..bits.bit_len() {
368		assert_eq!(bits.bit_test(i), i & 1 != 0);
369	}
370	// invert all bits and flip back
371	bits.bit_not();
372	for i in 0..bits.bit_len() {
373		bits.bit_flip(i);
374		assert_eq!(bits.bit_test(i), i & 1 != 0);
375	}
376
377	assert!(!bits.bit_disjoint(bits));
378	assert!(bits.bit_subset(bits));
379	assert!(bits.bit_superset(bits));
380}
bitset_core/lib.rs

bitset_core/
lib.rs
