An updatable finite state set for Rust. fst::Set is compact and fast to query but immutable once built; IncrementalFstSet puts a sorted in-memory mutation buffer in front of one, so inserts and removes are cheap and reads still see the current state. The buffer is folded back into a fresh FST when it grows past a configured threshold. Persistence stays yours to drive: the crate opens no files, and every mutation reports whether the FST or only the buffer changed, so the expensive write can be skipped. Full walkthrough in the usage guide, signatures in the API reference.
use fst_incremental::{FstChangeType, IncrementalFstSet};
let set = IncrementalFstSet::new(None).unwrap();
set.insert(b"apple".to_vec()).unwrap();
set.insert(b"apricot".to_vec()).unwrap();
assert!(set.contains(b"apple").unwrap());
set.remove(b"apple").unwrap();
assert!(!set.contains(b"apple").unwrap());
assert_eq!(set.force_rebuild().unwrap().change_type, FstChangeType::FstRebuilt);[dependencies]
fst_incremental = "1"The fst crate is re-exported as fst_incremental::fst, so you do not need your own dependency on it to name an Automaton or bring Streamer into scope.
| Feature | Default | Effect |
|---|---|---|
serde |
yes | Derives Serialize/Deserialize on SerializableFstBuffers and CompactArenaSet, so the mutation buffer can be persisted in a format of your choosing. |
| You want to | Use |
|---|---|
| Build a set in memory | IncrementalFstSet::new |
| Load one from FST bytes you already hold | IncrementalFstSet::from_data |
| Load a large one without reading it in | IncrementalFstSet::from_persisted_mmap |
| Add or remove a single key | insert, remove |
| Load many keys at once | bulk_insert, then finish_bulk_operations_and_rebuild_if_needed |
| Test membership | contains |
| Walk every key in order | stream |
| Run an automaton (prefix, fuzzy, regex) over the set | search |
| Decide what needs writing to disk | the FstChangeType on every mutation result |
| Save the set | persisted_fst_as_bytes plus buffers_snapshot |
| Control when rebuilds happen | FstConfigOptions |
| See what rebuilds are costing | get_metrics |
Stable. The public API is frozen for the 1.x line.
Measured figures for every operation, and a comparison against the pre-rewrite implementation, are in docs/benches.
Minimum supported Rust version is 1.85, required by edition 2024. An MSRV increase is a minor version bump.
Licensed under the Mozilla Public License 2.0. See LICENSE.