pub struct BitSet { /* private fields */ }
Expand description
A BitSet
is a simple set designed to track which indices are placed
into it.
Note, a BitSet
is limited by design to only usize**4
indices.
Adding beyond this limit will cause the BitSet
to panic.
Implementations
sourceimpl BitSet
impl BitSet
sourcepub fn with_capacity(max: u32) -> BitSet
pub fn with_capacity(max: u32) -> BitSet
Creates an empty BitSet
, preallocated for up to max
indices.
sourcepub fn add(&mut self, id: u32) -> bool
pub fn add(&mut self, id: u32) -> bool
Adds id
to the BitSet
. Returns true
if the value was
already in the set.
sourcepub fn remove(&mut self, id: u32) -> bool
pub fn remove(&mut self, id: u32) -> bool
Removes id
from the set, returns true
if the value
was removed, and false
if the value was not set
to begin with.
sourcepub fn contains_set(&self, other: &BitSet) -> bool
pub fn contains_set(&self, other: &BitSet) -> bool
Returns true
if all ids in other
are contained in this set
sourcepub const BITS_PER_USIZE: usize = 64usize
pub const BITS_PER_USIZE: usize = 64usize
How many bits are in a usize
.
This value can be trivially determined. It is provided here as a constant for clarity.
Example
use hibitset::BitSet;
assert_eq!(BitSet::BITS_PER_USIZE, std::mem::size_of::<usize>()*8);
sourcepub fn layer0_as_slice(&self) -> &[usize]
pub fn layer0_as_slice(&self) -> &[usize]
Returns the bottom layer of the bitset as a slice. Each bit in this slice refers to a single
Index
.
The slice’s length will be at least the length needed to reflect all the 1
s in the bitset,
but is not otherwise guaranteed. Consider it to be an implementation detail.
Example
use hibitset::BitSet;
let index: u32 = 12345;
let mut bitset = BitSet::new();
bitset.add(index);
// layer 0 is 1:1 with Indexes, so we expect that bit in the slice to be set
let slice = bitset.layer0_as_slice();
let bit_index = index as usize;
// map that bit index to a usize in the slice and a bit within that usize
let slice_index = bit_index / BitSet::BITS_PER_USIZE;
let bit_at_index = bit_index % BitSet::BITS_PER_USIZE;
assert_eq!(slice[slice_index], 1 << bit_at_index);
sourcepub const LAYER1_GRANULARITY: usize = 64usize
pub const LAYER1_GRANULARITY: usize = 64usize
How many Index
es are described by as single layer 1 bit, intended for use with
BitSet::layer1_as_slice()
.
BitSet
s are defined in terms of usize
s summarizing usize
s, so this value can be
trivially determined. It is provided here as a constant for clarity.
Example
use hibitset::BitSet;
assert_eq!(BitSet::LAYER1_GRANULARITY, BitSet::BITS_PER_USIZE);
sourcepub fn layer1_as_slice(&self) -> &[usize]
pub fn layer1_as_slice(&self) -> &[usize]
Returns the second layer of the bitset as a slice. Each bit in this slice summarizes a
corresponding usize
from layer0
. (If usize
is 64 bits, bit 0 will be set if any
Index
es 0-63 are set, bit 1 will be set if any Index
es 64-127 are set, etc.)
BitSet::LAYER1_GRANULARITY
reflects how many indexes are summarized per layer 1 bit.
The slice’s length is not guaranteed, except that it will be at least the length needed to
reflect all the 1
s in the bitset.
Example
use hibitset::BitSet;
let index: u32 = 12345;
let mut bitset = BitSet::new();
bitset.add(index);
// layer 1 summarizes multiple indexes per bit, so divide appropriately
let slice = bitset.layer1_as_slice();
let bit_index = index as usize / BitSet::LAYER1_GRANULARITY;
// map that bit index to a usize in the slice and a bit within that usize
let slice_index = bit_index / BitSet::BITS_PER_USIZE;
let bit_at_index = bit_index % BitSet::BITS_PER_USIZE;
assert_eq!(slice[slice_index], 1 << bit_at_index);
sourcepub const LAYER2_GRANULARITY: usize = 4_096usize
pub const LAYER2_GRANULARITY: usize = 4_096usize
How many Index
es are described by as single layer 2 bit, intended for use with
BitSet::layer2_as_slice()
.
BitSet
s are defined in terms of usize
s summarizing usize
s, so this value can be
trivially determined. It is provided here as a constant for clarity.
Example
use hibitset::BitSet;
assert_eq!(BitSet::LAYER2_GRANULARITY, BitSet::LAYER1_GRANULARITY * BitSet::BITS_PER_USIZE);
sourcepub fn layer2_as_slice(&self) -> &[usize]
pub fn layer2_as_slice(&self) -> &[usize]
Returns the third layer of the bitset as a slice. Each bit in this slice summarizes a
corresponding usize
from layer1
. If usize
is 64 bits, bit 0 will be set if any
Index
es 0-4095 are set, bit 1 will be set if any Index
es 4096-8191 are set, etc.
The slice’s length is not guaranteed, except that it will be at least the length needed to
reflect all the 1
s in the bitset.
Example
use hibitset::BitSet;
let index: u32 = 12345;
let mut bitset = BitSet::new();
bitset.add(index);
// layer 2 summarizes multiple indexes per bit, so divide appropriately
let slice = bitset.layer2_as_slice();
let bit_index = index as usize / BitSet::LAYER2_GRANULARITY;
// map that bit index to a usize in the slice and a bit within that usize
let slice_index = bit_index / BitSet::BITS_PER_USIZE;
let bit_at_index = bit_index % BitSet::BITS_PER_USIZE;
assert_eq!(slice[slice_index], 1 << bit_at_index);
Trait Implementations
sourceimpl<'a, T> BitAnd<T> for &'a BitSet where
T: BitSetLike,
impl<'a, T> BitAnd<T> for &'a BitSet where
T: BitSetLike,
sourceimpl<T> BitAnd<T> for BitSet where
T: BitSetLike,
impl<T> BitAnd<T> for BitSet where
T: BitSetLike,
sourceimpl<'a, B> BitAndAssign<&'a B> for BitSet where
B: BitSetLike,
impl<'a, B> BitAndAssign<&'a B> for BitSet where
B: BitSetLike,
sourcefn bitand_assign(&mut self, lhs: &B)
fn bitand_assign(&mut self, lhs: &B)
Performs the &=
operation. Read more
sourceimpl<'a, T> BitOr<T> for &'a BitSet where
T: BitSetLike,
impl<'a, T> BitOr<T> for &'a BitSet where
T: BitSetLike,
sourceimpl<T> BitOr<T> for BitSet where
T: BitSetLike,
impl<T> BitOr<T> for BitSet where
T: BitSetLike,
sourceimpl<'a, B> BitOrAssign<&'a B> for BitSet where
B: BitSetLike,
impl<'a, B> BitOrAssign<&'a B> for BitSet where
B: BitSetLike,
sourcefn bitor_assign(&mut self, lhs: &B)
fn bitor_assign(&mut self, lhs: &B)
Performs the |=
operation. Read more
sourceimpl BitSetLike for BitSet
impl BitSetLike for BitSet
sourcefn layer3(&self) -> usize
fn layer3(&self) -> usize
Return a usize
where each bit represents if any word in layer2
has been set. Read more
sourcefn layer2(&self, i: usize) -> usize
fn layer2(&self, i: usize) -> usize
Return the usize
from the array of usizes that indicates if any
bit has been set in layer1 Read more
sourcefn layer1(&self, i: usize) -> usize
fn layer1(&self, i: usize) -> usize
Return the usize
from the array of usizes that indicates if any
bit has been set in layer0 Read more
sourcefn layer0(&self, i: usize) -> usize
fn layer0(&self, i: usize) -> usize
Return a usize
that maps to the direct 1:1 association with
each index of the set Read more
sourcefn get_from_layer(&self, layer: usize, idx: usize) -> usize
fn get_from_layer(&self, layer: usize, idx: usize) -> usize
Gets the usize
corresponding to layer and index. Read more
sourcefn is_empty(&self) -> bool
fn is_empty(&self) -> bool
Returns true if this BitSetLike
contains nothing, and false otherwise.
sourcefn par_iter(self) -> BitParIter<Self>
fn par_iter(self) -> BitParIter<Self>
Create a parallel iterator that will scan over the keyspace
sourceimpl<'a, T> BitXor<T> for &'a BitSet where
T: BitSetLike,
impl<'a, T> BitXor<T> for &'a BitSet where
T: BitSetLike,
sourceimpl<T> BitXor<T> for BitSet where
T: BitSetLike,
impl<T> BitXor<T> for BitSet where
T: BitSetLike,
sourceimpl<'a, B> BitXorAssign<&'a B> for BitSet where
B: BitSetLike,
impl<'a, B> BitXorAssign<&'a B> for BitSet where
B: BitSetLike,
sourcefn bitxor_assign(&mut self, lhs: &B)
fn bitxor_assign(&mut self, lhs: &B)
Performs the ^=
operation. Read more
sourceimpl DrainableBitSet for BitSet
impl DrainableBitSet for BitSet
sourceimpl<'a> Extend<&'a u32> for BitSet
impl<'a> Extend<&'a u32> for BitSet
sourcefn extend<T>(&mut self, iter: T) where
T: IntoIterator<Item = &'a u32>,
fn extend<T>(&mut self, iter: T) where
T: IntoIterator<Item = &'a u32>,
Extends a collection with the contents of an iterator. Read more
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Extends a collection with exactly one element.
sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
sourceimpl Extend<u32> for BitSet
impl Extend<u32> for BitSet
sourcefn extend<T>(&mut self, iter: T) where
T: IntoIterator<Item = u32>,
fn extend<T>(&mut self, iter: T) where
T: IntoIterator<Item = u32>,
Extends a collection with the contents of an iterator. Read more
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Extends a collection with exactly one element.
sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
sourceimpl<'a> FromIterator<&'a u32> for BitSet
impl<'a> FromIterator<&'a u32> for BitSet
sourceimpl FromIterator<u32> for BitSet
impl FromIterator<u32> for BitSet
sourceimpl<'a> IntoIterator for &'a BitSet
impl<'a> IntoIterator for &'a BitSet
sourceimpl IntoIterator for BitSet
impl IntoIterator for BitSet
sourceimpl<'a> Join for &'a BitSet
impl<'a> Join for &'a BitSet
sourceunsafe fn open(self) -> (Self::Mask, Self::Value)
unsafe fn open(self) -> (Self::Mask, Self::Value)
Open this join by returning the mask and the storages. Read more
sourceunsafe fn get(_: &mut Self::Value, id: Index) -> Self::Type
unsafe fn get(_: &mut Self::Value, id: Index) -> Self::Type
Get a joined component value by a given index. Read more
sourcefn join(self) -> JoinIter<Self>ⓘNotable traits for JoinIter<J>impl<J: Join> Iterator for JoinIter<J> type Item = J::Type;
where
Self: Sized,
fn join(self) -> JoinIter<Self>ⓘNotable traits for JoinIter<J>impl<J: Join> Iterator for JoinIter<J> type Item = J::Type;
where
Self: Sized,
Create a joined iterator over the contents.
sourcefn maybe(self) -> MaybeJoin<Self> where
Self: Sized,
fn maybe(self) -> MaybeJoin<Self> where
Self: Sized,
Returns a Join
-able structure that yields all indices, returning
None
for all missing elements and Some(T)
for found elements. Read more
sourcefn is_unconstrained() -> bool
fn is_unconstrained() -> bool
If this Join
typically returns all indices in the mask, then iterating
over only it or combined with other joins that are also dangerous
will cause the JoinIter
/ParJoin
to go through all indices which
is usually not what is wanted and will kill performance. Read more
sourceimpl Join for BitSet
impl Join for BitSet
sourceunsafe fn open(self) -> (Self::Mask, Self::Value)
unsafe fn open(self) -> (Self::Mask, Self::Value)
Open this join by returning the mask and the storages. Read more
sourceunsafe fn get(_: &mut Self::Value, id: Index) -> Self::Type
unsafe fn get(_: &mut Self::Value, id: Index) -> Self::Type
Get a joined component value by a given index. Read more
sourcefn join(self) -> JoinIter<Self>ⓘNotable traits for JoinIter<J>impl<J: Join> Iterator for JoinIter<J> type Item = J::Type;
where
Self: Sized,
fn join(self) -> JoinIter<Self>ⓘNotable traits for JoinIter<J>impl<J: Join> Iterator for JoinIter<J> type Item = J::Type;
where
Self: Sized,
Create a joined iterator over the contents.
sourcefn maybe(self) -> MaybeJoin<Self> where
Self: Sized,
fn maybe(self) -> MaybeJoin<Self> where
Self: Sized,
Returns a Join
-able structure that yields all indices, returning
None
for all missing elements and Some(T)
for found elements. Read more
sourcefn is_unconstrained() -> bool
fn is_unconstrained() -> bool
If this Join
typically returns all indices in the mask, then iterating
over only it or combined with other joins that are also dangerous
will cause the JoinIter
/ParJoin
to go through all indices which
is usually not what is wanted and will kill performance. Read more
sourceimpl<'a> ParJoin for &'a BitSet
impl<'a> ParJoin for &'a BitSet
sourcefn par_join(self) -> JoinParIter<Self> where
Self: Sized,
fn par_join(self) -> JoinParIter<Self> where
Self: Sized,
Create a joined parallel iterator over the contents.
sourceimpl ParJoin for BitSet
impl ParJoin for BitSet
sourcefn par_join(self) -> JoinParIter<Self> where
Self: Sized,
fn par_join(self) -> JoinParIter<Self> where
Self: Sized,
Create a joined parallel iterator over the contents.
impl Eq for BitSet
Auto Trait Implementations
impl RefUnwindSafe for BitSet
impl Send for BitSet
impl Sync for BitSet
impl Unpin for BitSet
impl UnwindSafe for BitSet
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
sourceimpl<T> Pointable for T
impl<T> Pointable for T
sourceimpl<T> TryDefault for T where
T: Default,
impl<T> TryDefault for T where
T: Default,
sourcefn try_default() -> Result<T, String>
fn try_default() -> Result<T, String>
Tries to create the default.
sourcefn unwrap_default() -> Self
fn unwrap_default() -> Self
Calls try_default
and panics on an error case.