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!

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

Usage

This library is available on crates.io and can be used by adding the following to your project's [Cargo.toml]:

toml [dependencies] byte_set = "0.1.3"

To import the [byte_set!] macro, add this to your crate root (main.rs or lib.rs):

rust use byte_set::byte_set;

If you're not using Rust 2018 edition, it must be imported differently:

```rust

[macro_use]

extern crate byte_set; ```

Examples

`ByteSet` Type

First, let's import [ByteSet]:

rust use byte_set::ByteSet;

Here's how you create an empty set:

rust let bytes = ByteSet::new();

You can create a set filled with all bytes (0 through 255) just as easily:

rust 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:

rust let mut bytes = ByteSet::new(); bytes.insert(255);

Use [inserting] as an immutable alternative, by passing the calling [ByteSet] by value:

rust let bytes = ByteSet::new().inserting(255);

Use [insert_all] to include all bytes of another [ByteSet], by mutating the [ByteSet] in-place:

```rust let mut alphabet = ByteSet::ASCIIUPPERCASE; alphabet.insertall(ByteSet::ASCII_LOWERCASE);

asserteq!(alphabet, ByteSet::ASCIIALPHABETIC); ```

Use [inserting_all] as an immutable alternative, by passing the calling [ByteSet] by value:

```rust let alphabet = ByteSet::ASCIIUPPERCASE.insertingall(ByteSet::ASCII_LOWERCASE);

asserteq!(alphabet, ByteSet::ASCIIALPHABETIC); ```

Extend

Rather than call [insert] in a loop, [extend] simplifies inserting from an iterator:

rust 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:

rust let mut bytes = ByteSet::full(); bytes.remove(255);

Use [removing] as an immutable alternative, by passing the calling [ByteSet] by value:

rust let bytes = ByteSet::full().removing(255);

Use [remove_all] to exclude all bytes of another [ByteSet], by mutating the [ByteSet] in-place:

```rust let mut alphabet = ByteSet::ASCIIALPHANUMERIC; alphabet.removeall(ByteSet::ASCII_DIGIT);

asserteq!(alphabet, ByteSet::ASCIIALPHABETIC); ```

Use [removing_all] as an immutable alternative, by passing the calling [ByteSet] by value:

```rust let alphabet = ByteSet::ASCIIALPHANUMERIC.removingall(ByteSet::ASCII_DIGIT);

asserteq!(alphabet, ByteSet::ASCIIALPHABETIC); ```

Iterate

Iterating can be done with just a for loop, and goes in order from least to greatest:

rust 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:

rust 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:

rust fn has_null(bytes: &ByteSet) -> bool { bytes.contains(0) }

Use [contains_any] to check for any matches in another [ByteSet]:

rust 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:

```rust 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:

```rust fn test(a: &ByteSet, b: &ByteSet) { assert!(a.isstrictsubset(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:

rust 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:

rust let bytes = byte_set![1, 2, 3, b'x', b'y', b'z'];

It even works at compile-time in a const expression:

```rust 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]:

rust let bytes = byte_set![0, 1, 4, 5, 244];

The in-memory representation of bytes would look like:

text 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:

sh 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:

sh cargo bench ByteSet

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

Benchmark a specific [ByteSet] operation by running:

sh 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:

toml [dependencies.byte_set] version = "0.1.3" features = ["rand"]

This makes the following possible:

```rust let bytes = rand::random::();

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

toml [dependencies.byte_set] version = "0.1.3" features = ["serde"]

This makes the following possible:

```rust 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.

ByteSet

Table of Contents

Usage

[macro_use]

Examples

ByteSet Type

Insert

Extend

Remove

Iterate

Contains

Subset

Min and Max

byte_set! Macro

Implementation

Benchmarks

Ecosystem Integrations

rand

serde

[derive(Serialize, Deserialize)]

License

`ByteSet` Type

`byte_set!` Macro

`rand`

`serde`