Struct hibitset::BitSet

source ·
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§

source§

impl BitSet

source

pub fn new() -> BitSet

Creates an empty BitSet.

source

pub fn with_capacity(max: u32) -> BitSet

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

source

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

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

source

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.

source

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

Returns true if id is in the set.

source

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

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

source

pub fn clear(&mut self)

Completely wipes out the bit set.

source

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

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

pub const LAYER1_GRANULARITY: usize = 64usize

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

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

pub const LAYER2_GRANULARITY: usize = 4_096usize

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

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§

source§

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

§

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

The resulting type after applying the & operator.
source§

fn bitand(self, rhs: T) -> Self::Output

Performs the & operation. Read more
source§

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

§

type Output = BitSetAnd<BitSet, T>

The resulting type after applying the & operator.
source§

fn bitand(self, rhs: T) -> Self::Output

Performs the & operation. Read more
source§

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

source§

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

Performs the &= operation. Read more
source§

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

§

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

The resulting type after applying the | operator.
source§

fn bitor(self, rhs: T) -> Self::Output

Performs the | operation. Read more
source§

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

§

type Output = BitSetOr<BitSet, T>

The resulting type after applying the | operator.
source§

fn bitor(self, rhs: T) -> Self::Output

Performs the | operation. Read more
source§

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

source§

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

Performs the |= operation. Read more
source§

impl BitSetLike for BitSet

source§

fn layer3(&self) -> usize

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

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

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

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

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

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

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

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

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

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

Gets the usize corresponding to layer and index. Read more
source§

fn is_empty(&self) -> bool

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

fn iter(self) -> BitIter<Self>
where Self: Sized,

Create an iterator that will scan over the keyspace
source§

fn par_iter(self) -> BitParIter<Self>
where Self: Sized,

Create a parallel iterator that will scan over the keyspace
source§

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

§

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

The resulting type after applying the ^ operator.
source§

fn bitxor(self, rhs: T) -> Self::Output

Performs the ^ operation. Read more
source§

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

§

type Output = BitSetXor<BitSet, T>

The resulting type after applying the ^ operator.
source§

fn bitxor(self, rhs: T) -> Self::Output

Performs the ^ operation. Read more
source§

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

source§

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

Performs the ^= operation. Read more
source§

impl Clone for BitSet

source§

fn clone(&self) -> BitSet

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl Debug for BitSet

source§

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

Formats the value using the given formatter. Read more
source§

impl Default for BitSet

source§

fn default() -> BitSet

Returns the “default value” for a type. Read more
source§

impl DrainableBitSet for BitSet

source§

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

Removes bit from the bit set. Read more
source§

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

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

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

source§

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

Extends a collection with the contents of an iterator. Read more
source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
source§

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. Read more
source§

impl Extend<u32> for BitSet

source§

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

Extends a collection with the contents of an iterator. Read more
source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
source§

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. Read more
source§

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

source§

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

Creates a value from an iterator. Read more
source§

impl FromIterator<u32> for BitSet

source§

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

Creates a value from an iterator. Read more
source§

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?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
source§

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?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
source§

impl<'a> Not for &'a BitSet

§

type Output = BitSetNot<&'a BitSet>

The resulting type after applying the ! operator.
source§

fn not(self) -> Self::Output

Performs the unary ! operation. Read more
source§

impl Not for BitSet

§

type Output = BitSetNot<BitSet>

The resulting type after applying the ! operator.
source§

fn not(self) -> Self::Output

Performs the unary ! operation. Read more
source§

impl PartialEq for BitSet

source§

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

Tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

impl Eq for BitSet

Auto Trait Implementations§

§

impl Freeze for BitSet

§

impl RefUnwindSafe for BitSet

§

impl Send for BitSet

§

impl Sync for BitSet

§

impl Unpin for BitSet

§

impl UnwindSafe for BitSet

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

default unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> Pointable for T

source§

const ALIGN: usize = _

The alignment of pointer.
§

type Init = T

The type for initializers.
source§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
source§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
source§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
source§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.