spillsort/
lib.rs

1//! Sort more records than fit in memory: sorted runs spill to disk and merge as they are read.
2//!
3//! A record is a key and a value, both bytes. Records sort by key, compared as bytes, and records
4//! with equal keys come out in the order they were pushed. A [`Sorter`] holds at most
5//! [`Config::max_bytes`] of records in memory. Once half of that is full, a background thread
6//! sorts it, on a pool of [`Config::threads`] threads if there are more than one, and writes it,
7//! compressed with LZ4, to a temporary file, a run, while the other half fills.
8//! [`Sorter::finish`] merges the runs with the records still held and returns them in order.
9//!
10//! The [`key`] module builds keys from numbers, text, bytes, and tuples of them, and their bytes
11//! compare as those values do in Python. A key built from several fields sorts field by field.
12//!
13//! ```
14//! use spillsort::{Config, Sorter, key};
15//!
16//! let mut sorter = Sorter::new(Config::default().max_bytes(1 << 20))?;
17//! for (refname, start) in [("chr2", 5), ("chr1", 70), ("chr1", 8)] {
18//!     let mut sort_key = Vec::new();
19//!     key::push_str(&mut sort_key, refname);
20//!     key::push_int(&mut sort_key, start);
21//!     sorter.push(&sort_key, format!("{refname}:{start}").as_bytes())?;
22//! }
23//!
24//! let mut merged = sorter.finish()?;
25//! let mut values = Vec::new();
26//! while let Some((_, value)) = merged.next_record()? {
27//!     values.push(String::from_utf8_lossy(value).into_owned());
28//! }
29//! assert_eq!(values, ["chr1:8", "chr1:70", "chr2:5"]);
30//! # Ok::<(), spillsort::Error>(())
31//! ```
32
33mod channel;
34pub mod key;
35mod merge;
36mod run;
37mod sorter;
38
39#[cfg(feature = "python")]
40mod python;
41
42use std::fmt;
43use std::io;
44
45pub use merge::Merged;
46pub use sorter::{
47    Config, DEFAULT_MAX_BYTES, DEFAULT_MAX_OPEN, DEFAULT_THREADS, MIN_MAX_BYTES, MIN_MAX_OPEN,
48    Sorter,
49};
50
51#[cfg(doctest)]
52#[doc = include_str!("../README.md")]
53struct ReadmeDoctests;
54
55/// An error from sorting or merging.
56#[derive(Debug)]
57#[non_exhaustive]
58pub enum Error {
59    /// Writing or reading a run failed.
60    Io(io::Error),
61    /// A setting or a record is invalid, such as a key of 4 GiB or more.
62    Invalid(String),
63    /// An earlier error lost records, so the sorter or merge cannot go on.
64    Failed,
65}
66
67impl From<io::Error> for Error {
68    fn from(error: io::Error) -> Self {
69        Error::Io(error)
70    }
71}
72
73impl fmt::Display for Error {
74    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
75        match self {
76            Error::Io(error) => error.fmt(f),
77            Error::Invalid(message) => f.write_str(message),
78            Error::Failed => f.write_str("an earlier error lost records, so sorting cannot go on"),
79        }
80    }
81}
82
83impl std::error::Error for Error {
84    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
85        match self {
86            Error::Io(error) => Some(error),
87            Error::Invalid(_) | Error::Failed => None,
88        }
89    }
90}
91
92/// A result whose error is an [`Error`].
93pub type Result<T> = std::result::Result<T, Error>;
spillsort/lib.rs

spillsort/
lib.rs
