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 to 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
:
[]
= "0.1"
To import the byte_set!
macro, add this to your crate root (main.rs
or
lib.rs
):
use byte_set;
If you're not using Rust 2018 edition, it must be imported differently:
extern crate byte_set;
Examples
ByteSet
Type
First, let's import ByteSet
:
use ByteSet;
Here's how you create an empty set:
let bytes = new;
You can create a set filled with all bytes (0 through 255) just as easily:
let bytes = 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 = new;
bytes.insert;
Use inserting
as an immutable alternative, by passing the calling
ByteSet
by value:
let bytes = new.inserting;
Use insert_all
to include all bytes of another ByteSet
, by mutating the
ByteSet
in-place:
let mut alphabet = ASCII_UPPERCASE;
alphabet.insert_all;
assert_eq!;
Use inserting_all
as an immutable alternative, by passing the calling
ByteSet
by value:
let alphabet = ASCII_UPPERCASE.inserting_all;
assert_eq!;
Extend
Rather than call insert
in a loop, extend
simplifies inserting from an
iterator:
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 = full;
bytes.remove;
Use removing
as an immutable alternative, by passing the calling ByteSet
by value:
let bytes = full.removing;
Use remove_all
to exclude all bytes of another ByteSet
, by mutating the
ByteSet
in-place:
let mut alphabet = ASCII_ALPHANUMERIC;
alphabet.remove_all;
assert_eq!;
Use removing_all
as an immutable alternative, by passing the calling
ByteSet
by value:
let alphabet = ASCII_ALPHANUMERIC.removing_all;
assert_eq!;
Iterate
Iterating can be done with just a for
loop, and goes in order from least to
greatest:
Iterating in reverse is slightly more verbose, and goes in order from greatest to least:
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:
Use contains_any
to check for any matches in another ByteSet
:
Subset
Use is_subset
to check that all of the bytes in a ByteSet
are contained
in another:
Use is_strict_subset
to check is_subset
and that the sets are not the
same:
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:
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!;
It even works at compile-time in a const
expression:
const WHOA: ByteSet = byte_set!;
static ABC: ByteSet = byte_set!;
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!;
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:
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:
This takes about 15 minutes, so maybe grab a coffee in the meantime.
Benchmark a specific ByteSet
operation by running:
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\)
.
License
This project is released under either:
at your choosing.