bs

Crates.iobs
lib.rsbs
version0.3.0
sourcesrc
created_at2022-06-23 04:00:18.128625
updated_at2024-06-09 01:28:32.235274
descriptionSimple bitset with small-set (single-word) optimization.
homepage
repositoryhttp://github.com/graydon/bs
max_upload_size
id611640
size18,298
Graydon Hoare (graydon)

documentation

README

bs

This crate provides a bitset abstraction that has a non-allocating fast-and-small case for bitsets containing only bits in the range 0..=63, which it stores in a single u64. For many programs, bitsets are nearly all empty or contain mostly low-numbered bits, but periodically contain higher bits so need to transparently overflow. This is for such programs.

I'm sorry for making another bitset crate. Remarkably, despite dozens of bitset crates, I couldn't find one that does this in the simple/fast/obvious way (using plain 1-word ops) and overflows to large bitsets when necessary. There are many fixed-size-only crates, and many variable-size-only crates, and two crates (smallbitvec and id-set) that almost do what I want but make inexplicably poor size or representation choices for the fast-and-small case, making it not-fast or not-small anyways. This crate does the simple / small / fast / obvious thing you'd expect: an enum with a small u64 case and a big vector-backed case.

It delegates to bit_set for its vector-backed case, which is perfectly fine. Like bit_set is does not expose (nor track) a number of "total bits" in the bitset, only the number of set (1-valued) bits. This is usually what you want -- transparently expanding storage to accommodate the set bits and implicitly treating the bitset as containing infinite zeroes past the last set-bit -- but if you want to track a max limit of the zeroes, you can add that yourself by embedding it in a tuple with an extra word.

Note that this also means there is no "invert" or "not" operation, since it would produce an infinite set of set-bits. But you usually only want an invert operation in order to perform a "difference" operation, which is provided. And if you really want an inverse-given-some-bounds operation, if you track a max limit of the zeroes, you can initialize a bitset full of set-bits at that limit and take the difference from it.

License: MIT OR Apache-2.0

Commit count: 0

cargo fmt