Expand description
Efficient sets of bytes for Rust, brought to you by @NikolaiVazquez!
The star of the show is ByteSet: an allocation-free sorted set. It is a
much faster alternative to HashSet<u8>, BTreeSet<u8>, and other
types for a variety of scenarios. See “Implementation”
for a peek under the hood.
If you found this library useful, please consider sponsoring me on GitHub!
§Table of Contents
§Usage
This library is available on crates.io and can be used by adding
the following to your project’s Cargo.toml:
[dependencies]
byte_set = "0.1.3"To import the byte_set! macro, add this to your crate root (main.rs or
lib.rs):
use byte_set::byte_set;If you’re not using Rust 2018 edition, it must be imported differently:
#[macro_use]
extern crate byte_set;§Examples
§ByteSet Type
First, let’s import ByteSet:
use byte_set::ByteSet;Here’s how you create an empty set:
let bytes = ByteSet::new();You can create a set filled with all bytes (0 through 255) just as easily:
let bytes = ByteSet::full();Ok, let’s see what we can do with this. Note that this isn’t the only
available functionality. See ByteSet for a complete list.
§Insert
Use insert to include a single byte, by mutating the ByteSet
in-place:
let mut bytes = ByteSet::new();
bytes.insert(255);Use inserting as an immutable alternative, by passing the calling
ByteSet by value:
let bytes = ByteSet::new().inserting(255);Use insert_all to include all bytes of another ByteSet, by mutating
the ByteSet in-place:
let mut alphabet = ByteSet::ASCII_UPPERCASE;
alphabet.insert_all(ByteSet::ASCII_LOWERCASE);
assert_eq!(alphabet, ByteSet::ASCII_ALPHABETIC);Use inserting_all as an immutable alternative, by passing the calling
ByteSet by value:
let alphabet = ByteSet::ASCII_UPPERCASE.inserting_all(ByteSet::ASCII_LOWERCASE);
assert_eq!(alphabet, ByteSet::ASCII_ALPHABETIC);§Extend
Rather than call insert in a loop, extend simplifies inserting from
an iterator:
fn take_string(bytes: &mut ByteSet, s: &str) {
bytes.extend(s.as_bytes());
}Because this iterates over the entire input, it is much more efficient to
use insert_all instead of extend when inserting another ByteSet.
§Remove
Use remove to exclude a single byte by mutating the set in-place:
let mut bytes = ByteSet::full();
bytes.remove(255);Use removing as an immutable alternative, by passing the calling
ByteSet by value:
let bytes = ByteSet::full().removing(255);Use remove_all to exclude all bytes of another ByteSet, by mutating
the ByteSet in-place:
let mut alphabet = ByteSet::ASCII_ALPHANUMERIC;
alphabet.remove_all(ByteSet::ASCII_DIGIT);
assert_eq!(alphabet, ByteSet::ASCII_ALPHABETIC);Use removing_all as an immutable alternative, by passing the calling
ByteSet by value:
let alphabet = ByteSet::ASCII_ALPHANUMERIC.removing_all(ByteSet::ASCII_DIGIT);
assert_eq!(alphabet, ByteSet::ASCII_ALPHABETIC);§Iterate
Iterating can be done with just a for loop, and goes in order from least
to greatest:
fn small_to_big(bytes: ByteSet) {
for byte in bytes {
do_work(byte);
}
}Iterating in reverse is slightly more verbose, and goes in order from greatest to least:
fn big_to_small(bytes: ByteSet) {
for byte in bytes.into_iter().rev() {
do_work(byte);
}
}§Contains
It wouldn’t really be a set if you couldn’t check if it has specific items.
Use contains to check a single byte:
fn has_null(bytes: &ByteSet) -> bool {
bytes.contains(0)
}Use contains_any to check for any matches in another ByteSet:
fn intersects(a: &ByteSet, b: &ByteSet) -> bool {
a.contains_any(b)
}§Subset
Use is_subset to check that all of the bytes in a ByteSet are
contained in another:
fn test(a: &ByteSet, b: &ByteSet) {
assert!(a.is_subset(b));
// Always passes because every set is a subset of itself.
assert!(a.is_subset(a));
}Use is_strict_subset to check is_subset and that the sets are not
the same:
fn test(a: &ByteSet, b: &ByteSet) {
assert!(a.is_strict_subset(b));
// `a` is equal to itself.
assert!(!a.is_strict_subset(a));
}For the sake of completion, there is also is_superset and
is_strict_superset, which call these functions with a and b
switched.
§Min and Max
Use first to get the smallest byte and last to get the biggest byte:
fn sanity_check(bytes: &ByteSet) {
if let (Some(first), Some(last)) = (bytes.first(), bytes.last()) {
assert!(first <= last);
} else {
// `bytes` is empty.
}
}These are the first and last bytes returned when iterating.
§byte_set! Macro
byte_set! enables you to create a ByteSet with the same syntax as
vec! or array expressions:
let bytes = byte_set![1, 2, 3, b'x', b'y', b'z'];It even works at compile-time in a const expression:
const WHOA: ByteSet = byte_set![b'w', b'h', b'o', b'a'];
static ABC: ByteSet = byte_set![b'a', b'c', b'c'];§Implementation
ByteSet is implemented as a 256-bit mask where each bit corresponds to a
byte value. The first (least significant) bit in the mask represents the
first byte (0) in the set. Likewise, the last last (most significant) bit
represents the last byte (255).
Given the following ByteSet:
let bytes = byte_set![0, 1, 4, 5, 244];The in-memory representation of bytes would look like:
Byte: 0 1 2 3 4 5 6 7 ... 253 244 255
Value: 1 1 0 0 1 1 0 0 ... 0 1 0This bit mask is composed of either [u64; 4] or [u32; 8] depending on
the target CPU (see #3). Because this comes out to only 32 bytes,
ByteSet implements Copy.
§Benchmarks
I will upload benchmarks run from my machine soon.
In the meantime, you can benchmark this library by running:
cargo benchBy default, this will benchmark ByteSet along with various other types
to compare performance. Note that this will take a long time (about 1
hour and 30 minutes).
Benchmark only ByteSet by running:
cargo bench ByteSetThis takes about 15 minutes, so maybe grab a coffee in the meantime.
Benchmark a specific ByteSet operation by running:
cargo bench $operation/ByteSetSee /benches/benchmarks for strings that can be used for $operation.
Note that cargo bench takes a regular expression, so Contains (Random)
will not work because the parentheses are treated as a capture group. To
match parentheses, escape them: Contains \(Random\).
§Ecosystem Integrations
This library has extended functionality for some popular crates.
§rand
Use the rand (or rand_core) feature in your Cargo.toml to enable
random ByteSet generation:
[dependencies.byte_set]
version = "0.1.3"
features = ["rand"]This makes the following possible:
let bytes = rand::random::<ByteSet>();
// Same as above.
let bytes = ByteSet::rand(rand::thread_rng());
// Handle failure instead of panicking.
match ByteSet::try_rand(rand::rngs::OsRng) {
Ok(bytes) => // ...
Err(error) => // ...
}§serde
Use the serde feature in your Cargo.toml to enable Serialize and
Deserialize for ByteSet:
[dependencies.byte_set]
version = "0.1.3"
features = ["serde"]This makes the following possible:
use serde::{Serialize, Deserialize};
#[derive(Serialize, Deserialize)]
struct MyValue {
bytes: ByteSet
}ByteSet can be serialized into a u8 sequence, and deserialized from
&[u8] or a u8 sequence.
Read more about using serde at serde.rs.
§License
This project is released under either:
at your choosing.