Crate spillsort 

Sort more records than fit in memory: sorted runs spill to disk and merge as they are read.

A record is a key and a value, both bytes. Records sort by key, compared as bytes, and records with equal keys come out in the order they were pushed. A Sorter holds at most Config::max_bytes of records in memory. Once half of that is full, a background thread sorts it, on a pool of Config::threads threads if there are more than one, and writes it, compressed with LZ4, to a temporary file, a run, while the other half fills. Sorter::finish merges the runs with the records still held and returns them in order.

The key module builds keys from numbers, text, bytes, and tuples of them, and their bytes compare as those values do in Python. A key built from several fields sorts field by field.

use spillsort::{Config, Sorter, key};

let mut sorter = Sorter::new(Config::default().max_bytes(1 << 20))?;
for (refname, start) in [("chr2", 5), ("chr1", 70), ("chr1", 8)] {
    let mut sort_key = Vec::new();
    key::push_str(&mut sort_key, refname);
    key::push_int(&mut sort_key, start);
    sorter.push(&sort_key, format!("{refname}:{start}").as_bytes())?;
}

let mut merged = sorter.finish()?;
let mut values = Vec::new();
while let Some((_, value)) = merged.next_record()? {
    values.push(String::from_utf8_lossy(value).into_owned());
}
assert_eq!(values, ["chr1:8", "chr1:70", "chr2:5"]);

Modules

key

Keys whose bytes compare as the values they encode compare in Python.

Structs

Config

How much a Sorter holds in memory, where it spills, and how many runs it merges at once.

Merged

The records of a Sorter, merged in order from its runs and the records it still held.

Sorter

Sorts records pushed in any order, then Sorter::finish returns them merged in order.

Enums

Error

An error from sorting or merging.

Constants

DEFAULT_MAX_BYTES

The default for Config::max_bytes: 256 MiB.

DEFAULT_MAX_OPEN

The default for Config::max_open.

DEFAULT_THREADS

The default for Config::threads.

MIN_MAX_BYTES

The least Config::max_bytes may be.

MIN_MAX_OPEN

The least Config::max_open may be.

Type Aliases

Result

A result whose error is an Error.