Struct rustc_index::bit_set::ChunkedBitSet
source · pub struct ChunkedBitSet<T> {
domain_size: usize,
chunks: Box<[Chunk]>,
marker: PhantomData<T>,
}
Expand description
A fixed-size bitset type with a partially dense, partially sparse representation. The bitset is broken into chunks, and chunks that are all zeros or all ones are represented and handled very efficiently.
This type is especially efficient for sets that typically have a large
domain_size
with significant stretches of all zeros or all ones, and also
some stretches with lots of 0s and 1s mixed in a way that causes trouble
for IntervalSet
.
T
is an index type, typically a newtyped usize
wrapper, but it can also
just be usize
.
All operations that involve an element will panic if the element is equal to or greater than the domain size. All operations that involve two bitsets will panic if the bitsets have differing domain sizes.
Fields§
§domain_size: usize
§chunks: Box<[Chunk]>
The chunks. Each one contains exactly CHUNK_BITS values, except the last one which contains 1..=CHUNK_BITS values.
marker: PhantomData<T>
Implementations§
source§impl<T> ChunkedBitSet<T>
impl<T> ChunkedBitSet<T>
pub fn domain_size(&self) -> usize
source§impl<T: Idx> ChunkedBitSet<T>
impl<T: Idx> ChunkedBitSet<T>
sourcefn new(domain_size: usize, is_empty: bool) -> Self
fn new(domain_size: usize, is_empty: bool) -> Self
Creates a new bitset with a given domain_size
and chunk kind.
sourcepub fn new_empty(domain_size: usize) -> Self
pub fn new_empty(domain_size: usize) -> Self
Creates a new, empty bitset with a given domain_size
.
sourcepub fn new_filled(domain_size: usize) -> Self
pub fn new_filled(domain_size: usize) -> Self
Creates a new, filled bitset with a given domain_size
.
pub fn iter(&self) -> ChunkedBitIter<'_, T> ⓘ
sourcepub fn insert_all(&mut self)
pub fn insert_all(&mut self)
Sets all bits to true.
sourcepub fn union<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
pub fn union<Rhs>(&mut self, other: &Rhs) -> boolwhere Self: BitRelations<Rhs>,
Sets self = self | other
and returns true
if self
changed
(i.e., if new bits were added).
sourcepub fn subtract<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
pub fn subtract<Rhs>(&mut self, other: &Rhs) -> boolwhere Self: BitRelations<Rhs>,
Sets self = self - other
and returns true
if self
changed.
(i.e., if any bits were removed).
sourcepub fn intersect<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
pub fn intersect<Rhs>(&mut self, other: &Rhs) -> boolwhere Self: BitRelations<Rhs>,
Sets self = self & other
and return true
if self
changed.
(i.e., if any bits were removed).
Trait Implementations§
source§impl<T: Idx> BitRelations<ChunkedBitSet<T>> for BitSet<T>
impl<T: Idx> BitRelations<ChunkedBitSet<T>> for BitSet<T>
fn union(&mut self, other: &ChunkedBitSet<T>) -> bool
fn subtract(&mut self, _other: &ChunkedBitSet<T>) -> bool
fn intersect(&mut self, other: &ChunkedBitSet<T>) -> bool
source§impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T>
impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T>
fn union(&mut self, other: &ChunkedBitSet<T>) -> bool
fn subtract(&mut self, _other: &ChunkedBitSet<T>) -> bool
fn intersect(&mut self, _other: &ChunkedBitSet<T>) -> bool
source§impl<T: Idx> BitRelations<HybridBitSet<T>> for ChunkedBitSet<T>
impl<T: Idx> BitRelations<HybridBitSet<T>> for ChunkedBitSet<T>
fn union(&mut self, other: &HybridBitSet<T>) -> bool
fn subtract(&mut self, other: &HybridBitSet<T>) -> bool
fn intersect(&mut self, _other: &HybridBitSet<T>) -> bool
source§impl<T> Clone for ChunkedBitSet<T>
impl<T> Clone for ChunkedBitSet<T>
source§fn clone_from(&mut self, from: &Self)
fn clone_from(&mut self, from: &Self)
WARNING: this implementation of clone_from will panic if the two
bitsets have different domain sizes. This constraint is not inherent to
clone_from
, but it works with the existing call sites and allows a
faster implementation, which is important because this function is hot.
source§impl<T: Debug> Debug for ChunkedBitSet<T>
impl<T: Debug> Debug for ChunkedBitSet<T>
source§impl<T: PartialEq> PartialEq<ChunkedBitSet<T>> for ChunkedBitSet<T>
impl<T: PartialEq> PartialEq<ChunkedBitSet<T>> for ChunkedBitSet<T>
source§fn eq(&self, other: &ChunkedBitSet<T>) -> bool
fn eq(&self, other: &ChunkedBitSet<T>) -> bool
self
and other
values to be equal, and is used
by ==
.impl<T: Eq> Eq for ChunkedBitSet<T>
impl<T> StructuralEq for ChunkedBitSet<T>
impl<T> StructuralPartialEq for ChunkedBitSet<T>
Auto Trait Implementations§
impl<T> RefUnwindSafe for ChunkedBitSet<T>where T: RefUnwindSafe,
impl<T> !Send for ChunkedBitSet<T>
impl<T> !Sync for ChunkedBitSet<T>
impl<T> Unpin for ChunkedBitSet<T>where T: Unpin,
impl<T> UnwindSafe for ChunkedBitSet<T>where T: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Layout§
Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...)
attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.
Size: 24 bytes