Skip to content

Commit 5282a4d

Browse files
james7132james7132
committed
Get Masks working with blocks instead of usize
1 parent 7e0d844 commit 5282a4d

File tree

6 files changed

+55
-18
lines changed

6 files changed

+55
-18
lines changed

‎src/block/avx2.rs‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
#![allow(clippy::undocumented_unsafe_blocks)]
2+
13
#[cfg(target_arch = "x86")]
24
use core::arch::x86::*;
35
#[cfg(target_arch = "x86_64")]
@@ -20,12 +22,12 @@ impl Block {
2022
pub const BITS: usize = core::mem::size_of::<Self>() * 8;
2123

2224
#[inline]
23-
fn into_usize_array(self) -> [usize; Self::USIZE_COUNT] {
25+
pub fn into_usize_array(self) -> [usize; Self::USIZE_COUNT] {
2426
unsafe { core::mem::transmute(self.0) }
2527
}
2628

2729
#[inline]
28-
const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
30+
pub const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
2931
Self(unsafe { core::mem::transmute(array) })
3032
}
3133

‎src/block/default.rs‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,16 @@ impl Block {
1111
pub const ALL: Self = Block(!0);
1212
pub const BITS: usize = core::mem::size_of::<Self>() * 8;
1313

14+
#[inline]
15+
pub fn into_usize_array(self) -> [usize; Self::USIZE_COUNT] {
16+
[self]
17+
}
18+
19+
#[inline]
20+
pub const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
21+
array.0
22+
}
23+
1424
#[inline]
1525
pub const fn is_empty(self) -> bool {
1626
self.0 == Self::NONE.0

‎src/block/mod.rs‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,32 @@ mod wasm32;
3737
#[cfg(target_arch = "wasm32")]
3838
pub use self::wasm32::*;
3939

40+
impl Block {
41+
#[inline]
42+
pub fn upper_mask(bits: usize) -> Self {
43+
let mut array = [0_usize; Self::USIZE_COUNT];
44+
let (idx, rem) = crate::div_rem(bits, crate::BITS);
45+
array[idx] = usize::max_value() << rem;
46+
for value in array.iter_mut().skip(idx + 1) {
47+
*value = usize::MAX;
48+
}
49+
Self::from_usize_array(array)
50+
}
51+
52+
#[inline]
53+
pub fn lower_mask(bits: usize) -> Self {
54+
!Self::upper_mask(bits)
55+
}
56+
57+
#[inline]
58+
pub fn count_ones(self) -> u32 {
59+
self.into_usize_array()
60+
.into_iter()
61+
.map(usize::count_ones)
62+
.sum()
63+
}
64+
}
65+
4066
impl Eq for Block {}
4167

4268
impl PartialOrd for Block {

‎src/block/sse2.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ impl Block {
2222
}
2323

2424
#[inline]
25-
const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
25+
pub const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
2626
Self(unsafe { core::mem::transmute(array) })
2727
}
2828

‎src/block/wasm32.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,12 +17,12 @@ impl Block {
1717
pub const BITS: usize = core::mem::size_of::<Self>() * 8;
1818

1919
#[inline]
20-
fn into_usize_array(self) -> [usize; Self::USIZE_COUNT] {
20+
pub fn into_usize_array(self) -> [usize; Self::USIZE_COUNT] {
2121
unsafe { core::mem::transmute(self.0) }
2222
}
2323

2424
#[inline]
25-
const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
25+
pub const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
2626
Self(unsafe { core::mem::transmute(array) })
2727
}
2828

‎src/lib.rs‎

Lines changed: 12 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -437,7 +437,7 @@ impl FixedBitSet {
437437
Masks::new(range, self.length)
438438
.map(|(block, mask)| {
439439
// SAFETY: Masks cannot return a block index that is out of range.
440-
let value = unsafe { *self.get_unchecked(block) };
440+
let value = unsafe { *self.data.get_unchecked(block) };
441441
(value & mask).count_ones() as usize
442442
})
443443
.sum()
@@ -452,7 +452,7 @@ impl FixedBitSet {
452452
pub fn set_range<T: IndexRange>(&mut self, range: T, enabled: bool) {
453453
for (block, mask) in Masks::new(range, self.length) {
454454
// SAFETY: Masks cannot return a block index that is out of range.
455-
let block = unsafe { self.get_unchecked_mut(block) };
455+
let block = unsafe { self.data.get_unchecked_mut(block) };
456456
if enabled {
457457
*block |= mask;
458458
} else {
@@ -480,7 +480,7 @@ impl FixedBitSet {
480480
pub fn toggle_range<T: IndexRange>(&mut self, range: T) {
481481
for (block, mask) in Masks::new(range, self.length) {
482482
// SAFETY: Masks cannot return a block index that is out of range.
483-
let block = unsafe { self.get_unchecked_mut(block) };
483+
let block = unsafe { self.data.get_unchecked_mut(block) };
484484
*block ^= mask;
485485
}
486486
}
@@ -870,9 +870,9 @@ impl<'a> FusedIterator for Union<'a> {}
870870

871871
struct Masks {
872872
first_block: usize,
873-
first_mask: usize,
873+
first_mask: Block,
874874
last_block: usize,
875-
last_mask: usize,
875+
last_mask: Block,
876876
}
877877

878878
impl Masks {
@@ -888,33 +888,32 @@ impl Masks {
888888
length
889889
);
890890

891-
let (first_block, first_rem) = div_rem(start, BITS);
892-
let (last_block, last_rem) = div_rem(end, BITS);
891+
let (first_block, first_rem) = div_rem(start, Block::BITS);
892+
let (last_block, last_rem) = div_rem(end, Block::BITS);
893893

894894
Masks {
895895
first_block,
896-
first_mask: usize::max_value() << first_rem,
896+
first_mask: Block::upper_mask(first_rem),
897897
last_block,
898-
last_mask: (usize::max_value() >> 1) >> (BITS - last_rem - 1),
899-
// this is equivalent to `MAX >> (BITS - x)` with correct semantics when x == 0.
898+
last_mask: Block::lower_mask(last_rem),
900899
}
901900
}
902901
}
903902

904903
impl Iterator for Masks {
905-
type Item = (usize, usize);
904+
type Item = (usize, Block);
906905
#[inline]
907906
fn next(&mut self) -> Option<Self::Item> {
908907
match self.first_block.cmp(&self.last_block) {
909908
Ordering::Less => {
910909
let res = (self.first_block, self.first_mask);
911910
self.first_block += 1;
912-
self.first_mask = !0;
911+
self.first_mask = Block::ALL;
913912
Some(res)
914913
}
915914
Ordering::Equal => {
916915
let mask = self.first_mask & self.last_mask;
917-
let res = if mask == 0 {
916+
let res = if mask.is_empty() {
918917
None
919918
} else {
920919
Some((self.first_block, mask))

0 commit comments

Comments
 (0)