Crate rbitset

A #[no_std] compatible crate providing a fixed-size BitSet implementation that stores booleans efficiently in an array of integers.

Overview

The primary type of this crate is BitSet. A BitSet value is a fixed-size collection of bits, each representing a boolean value. It provides methods for setting, clearing, and testing individual bits, as well as performing set operations like union, intersection, and difference.

The BitSet type is repr(transparent), meaning the representation of the struct is guaranteed to be the same as the inner array, making it usable where the struct representation is important, such as C FFI, optimization and more.

The remainder of this documentation is organized as follows:

• Features gives a very brief summary of the features rbitset does and does not support.
• Usage shows how to add rbitset to your Rust project.
• Examples shows a small cookbook of programs for common tasks.
• Crate features documents the Cargo features that can be enabled or disabled for this crate.

Features

Here is a non-exhaustive list of the things that rbitset supports:

• no_std support: Can be used in environments without the standard library.
• Fixed-size: The size of the bitset is determined at compile time.
• Efficient bit manipulation: Provides methods for setting, clearing, and testing bits.
• Set operations: Supports union, intersection, difference, and symmetric difference as iterators.
• Serde support: Can be serialized and deserialized using the serde crate (with the serde feature enabled).

Usage

The rbitset project is on crates.io and can be used by adding rbitset to your dependencies in your project’s Cargo.toml. Or more simply, just run cargo add rbitset.

cargo add rbitset

or

[dependencies]
rbitset = "0.3.6"

Examples

Bit sets are extremely cheap. You can store any number from 0 to 255 in an array of 4x 64-bit numbers. The lookup should in theory be O(1). Example usage of this is strspn. Here it is in rust, using this library:

use rbitset::BitSet256;

/// The C standard library function strspn, reimplemented in rust. It works by
/// placing all allowed values in a bit set, and returning on the first
/// character not on the list. A BitSet256 uses no heap allocations and only 4
/// 64-bit integers in stack memory.
fn strspn(s: &[u8], accept: &[u8]) -> usize {
    let mut allow = BitSet256::new();

    for &c in accept {
        allow.insert(c as usize);
    }

    for (i, &c) in s.iter().enumerate() {
        if !allow.contains(c as usize) {
            return i;
        }
    }
    s.len()
}

Crate Features

Ecosystem features

• serde — When enabled, rbitset will depend on the serde crate and the BitSet type will implement the Serialize and Deserialize traits.

Modules

changelog

A documentation module for this crate changelog.

Structs

BitSet

This type represents a fixed-size bit set.

Difference

A lazy iterator producing elements in the difference of BitSets.

Drain

A draining iterator over the items of a BitSet.

Intersection

A lazy iterator producing elements in the intersection of BitSets.

IntoIter

An owning iterator over the items of a BitSet.

Iter

An iterator over the items of a BitSet.

SymmetricDifference

A lazy iterator producing elements in the symmetric difference of BitSets.

Union

A lazy iterator producing elements in the union of BitSets.

Enums

BitSetError

Possible errors on the BitSet operations.

Type Aliases

BitSet8

A bit set able to hold up to 8 elements.

BitSet16

A bit set able to hold up to 16 elements.

BitSet32

A bit set able to hold up to 32 elements.

BitSet64

A bit set able to hold up to 64 elements.

BitSet128

A bit set able to hold up to 128 elements.

BitSet256

A bit set able to hold up to 256 elements.

BitSet512

A bit set able to hold up to 512 elements.

BitSet1024

A bit set able to hold up to 1024 elements.