ByteSet

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

1. Usage
2. Examples
   1. ByteSet Type
      1. Insert
      2. Extend
      3. Remove
      4. Iterate
      5. Contains
      6. Subset
      7. Min and Max
   2. byte_set! Macro
3. Implementation
4. Benchmarks
5. Ecosystem Integrations
   1. rand
   2. serde
6. License

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   0

This 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 bench

By 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 ByteSet

This takes about 15 minutes, so maybe grab a coffee in the meantime.

Benchmark a specific ByteSet operation by running:

cargo bench $operation/ByteSet

See /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:

• MIT License

• Apache License (Version 2.0)

at your choosing.