3 releases
0.0.4 | Nov 4, 2022 |
---|---|
0.0.3 | Nov 3, 2022 |
0.0.2 | Dec 13, 2021 |
0.0.1 |
|
#1570 in Data structures
49KB
1K
SLoC
fr-trie
This is a generic fuzzy and compact Trie implementation focused on:
- Small memory footprint.
- Efficient caching.
Trie is keyed by lists of type K
, which can be anything satisfying the KeyPrefix
and Clone
traits.
This structure is thought to be used in some particular scenarios where:
- The keys prefixes are string based and highly repeating.
- The volume of keys to store is not very big.
- A fuzzy and customizable key matching strategy is needed.
For more information, see the API documentation.
Usage
Add fr-trie
to your Cargo.toml
.
[dependencies]
fr-trie = "*"
Examples
Glob matching with multiple results
use fr_trie::glob::acl::{Acl, AclTrie, Permissions};
use fr_trie::glob::GlobMatcher;
fn demo() {
let mut trie = AclTrie::new();
trie.insert(Acl::new("/path/*"), Permissions::READ);
trie.insert(Acl::new("/path/to/resource"), Permissions::WRITE);
// Multiget example 1
let result = trie.get_merge::<GlobMatcher>(&Acl::new("/path/to/anything"));
if let Some(value) = result {
if value == Permissions::READ {
println!("Expecting /path/* wilcard key is accessed");
}
}
// Multiget example 2
let result = trie.get_merge::<GlobMatcher>(&Acl::new("/path/to/resource"));
if let Some(value) = result {
if value == (Permissions::READ | Permissions::WRITE) {
println!("Expecting both /path/* wilcard key and /path/to/resource is accessed");
}
}
// Dump trie structure
trie.foreach(|tup| {
let indent= String::from_utf8(vec![b' '; tup.0 *3]).unwrap();
println!("{} {} = {:?}", indent, tup.1, tup.2);
});
}
Caveats
- Still not fully-productive
Similar work
- Radix Trie – Fast generic radix trie implemented in Rust
- Sequence Trie – Ergonomic trie data structure
License
Licensed under MIT license
Dependencies
~0.5–1MB
~25K SLoC