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