Struct specs::BitSet

pub struct BitSet { /* fields omitted */ }

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

impl BitSet

pub fn new() -> BitSet

Creates an empty BitSet.

pub fn with_capacity(max: u32) -> BitSet

Creates an empty BitSet, preallocated for up to max indices.

pub fn add(&mut self, id: u32) -> bool

Adds id to the BitSet. Returns true if the value was already in the set.

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.

pub fn contains(&self, id: u32) -> bool

Returns true if id is in the set.

pub fn contains_set(&self, other: &BitSet) -> bool

Returns true if all ids in other are contained in this set

pub fn clear(&mut self)

Completely wipes out the bit set.

pub const BITS_PER_USIZE: usize

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);

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 1s 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);

pub const LAYER1_GRANULARITY: usize

How many Indexes are described by as single layer 1 bit, intended for use with BitSet::layer1_as_slice().

BitSets are defined in terms of usizes summarizing usizes, 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);

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 Indexes 0-63 are set, bit 1 will be set if any Indexes 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 1s 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);

pub const LAYER2_GRANULARITY: usize

How many Indexes are described by as single layer 2 bit, intended for use with BitSet::layer2_as_slice().

BitSets are defined in terms of usizes summarizing usizes, 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);

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 Indexes 0-4095 are set, bit 1 will be set if any Indexes 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 1s 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

impl<'a, T> BitAnd<T> for &'a BitSet where
    T: BitSetLike, 

type Output = BitSetAnd<&'a BitSet, T>

The resulting type after applying the & operator.

pub fn bitand(self, rhs: T) -> <&'a BitSet as BitAnd<T>>::Output

Performs the & operation.

impl<T> BitAnd<T> for BitSet where
    T: BitSetLike, 

type Output = BitSetAnd<BitSet, T>

The resulting type after applying the & operator.

pub fn bitand(self, rhs: T) -> <BitSet as BitAnd<T>>::Output

Performs the & operation.

impl<'a, B> BitAndAssign<&'a B> for BitSet where
    B: BitSetLike, 

pub fn bitand_assign(&mut self, lhs: &B)

Performs the &= operation.

impl<T> BitOr<T> for BitSet where
    T: BitSetLike, 

type Output = BitSetOr<BitSet, T>

The resulting type after applying the | operator.

pub fn bitor(self, rhs: T) -> <BitSet as BitOr<T>>::Output

Performs the | operation.

impl<'a, T> BitOr<T> for &'a BitSet where
    T: BitSetLike, 

type Output = BitSetOr<&'a BitSet, T>

The resulting type after applying the | operator.

pub fn bitor(self, rhs: T) -> <&'a BitSet as BitOr<T>>::Output

Performs the | operation.

impl<'a, B> BitOrAssign<&'a B> for BitSet where
    B: BitSetLike, 

pub fn bitor_assign(&mut self, lhs: &B)

Performs the |= operation.

impl BitSetLike for BitSet

pub fn layer3(&self) -> usize

Return a usize where each bit represents if any word in layer2 has been set.

pub fn layer2(&self, i: usize) -> usize

Return the usize from the array of usizes that indicates if any bit has been set in layer1

pub fn layer1(&self, i: usize) -> usize

Return the usize from the array of usizes that indicates if any bit has been set in layer0

pub fn layer0(&self, i: usize) -> usize

Return a usize that maps to the direct 1:1 association with each index of the set

pub fn contains(&self, i: u32) -> bool

Allows checking if set bit is contained in the bit set.

fn get_from_layer(&self, layer: usize, idx: usize) -> usize

Gets the usize corresponding to layer and index.

fn is_empty(&self) -> bool

Returns true if this BitSetLike contains nothing, and false otherwise.

fn iter(self) -> BitIter<Self>

Create an iterator that will scan over the keyspace

fn par_iter(self) -> BitParIter<Self>

Create a parallel iterator that will scan over the keyspace

impl<'a, T> BitXor<T> for &'a BitSet where
    T: BitSetLike, 

type Output = BitSetXor<&'a BitSet, T>

The resulting type after applying the ^ operator.

pub fn bitxor(self, rhs: T) -> <&'a BitSet as BitXor<T>>::Output

Performs the ^ operation.

impl<T> BitXor<T> for BitSet where
    T: BitSetLike, 

type Output = BitSetXor<BitSet, T>

The resulting type after applying the ^ operator.

pub fn bitxor(self, rhs: T) -> <BitSet as BitXor<T>>::Output

Performs the ^ operation.

impl<'a, B> BitXorAssign<&'a B> for BitSet where
    B: BitSetLike, 

pub fn bitxor_assign(&mut self, lhs: &B)

Performs the ^= operation.

impl Clone for BitSet

pub fn clone(&self) -> BitSet

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BitSet

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl Default for BitSet

pub fn default() -> BitSet

Returns the “default value” for a type.

impl DrainableBitSet for BitSet

pub fn remove(&mut self, i: u32) -> bool

Removes bit from the bit set.

fn drain(&'a mut self) -> DrainBitIter<'a, Self>

Create a draining iterator that will scan over the keyspace and clears it while doing so.

impl<'a> Extend<&'a u32> for BitSet

pub fn extend<T>(&mut self, iter: T) where
    T: IntoIterator<Item = &'a u32>, 

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl Extend<u32> for BitSet

pub fn extend<T>(&mut self, iter: T) where
    T: IntoIterator<Item = u32>, 

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a> FromIterator<&'a u32> for BitSet

pub fn from_iter<T>(iter: T) -> BitSet where
    T: IntoIterator<Item = &'a u32>, 

Creates a value from an iterator.

impl FromIterator<u32> for BitSet

pub fn from_iter<T>(iter: T) -> BitSet where
    T: IntoIterator<Item = u32>, 

Creates a value from an iterator.

impl IntoIterator for BitSet

type Item = <BitIter<BitSet> as Iterator>::Item

The type of the elements being iterated over.

type IntoIter = BitIter<BitSet>

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> <BitSet as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<'a> IntoIterator for &'a BitSet

type Item = <BitIter<&'a BitSet> as Iterator>::Item

The type of the elements being iterated over.

type IntoIter = BitIter<&'a BitSet>

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> <&'a BitSet as IntoIterator>::IntoIter

Creates an iterator from a value.

impl Join for BitSet

type Type = Index

Type of joined components.

type Value = ()

Type of joined storages.

type Mask = BitSet

Type of joined bit mask.

unsafe fn open(self) -> (Self::Mask, Self::Value)

Open this join by returning the mask and the storages.

unsafe fn get(_: &mut Self::Value, id: Index) -> Self::Type

Get a joined component value by a given index.

fn join(self) -> JoinIter<Self> where
    Self: Sized, 

Create a joined iterator over the contents.

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.

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.

impl<'a> Join for &'a BitSet

type Type = Index

Type of joined components.

type Value = ()

Type of joined storages.

type Mask = &'a BitSet

Type of joined bit mask.

unsafe fn open(self) -> (Self::Mask, Self::Value)

Open this join by returning the mask and the storages.

unsafe fn get(_: &mut Self::Value, id: Index) -> Self::Type

Get a joined component value by a given index.

fn join(self) -> JoinIter<Self> where
    Self: Sized, 

Create a joined iterator over the contents.

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.

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.

impl<'a> Not for &'a BitSet

type Output = BitSetNot<&'a BitSet>

The resulting type after applying the ! operator.

pub fn not(self) -> <&'a BitSet as Not>::Output

Performs the unary ! operation.

impl Not for BitSet

type Output = BitSetNot<BitSet>

The resulting type after applying the ! operator.

pub fn not(self) -> <BitSet as Not>::Output

Performs the unary ! operation.

impl ParJoin for BitSet

fn par_join(self) -> JoinParIter<Self> where
    Self: Sized, 

Create a joined parallel iterator over the contents.

impl<'a> ParJoin for &'a BitSet

fn par_join(self) -> JoinParIter<Self> where
    Self: Sized, 

Create a joined parallel iterator over the contents.

impl PartialEq<BitSet> for BitSet

pub fn eq(&self, rhv: &BitSet) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl Eq for BitSet