3 releases

0.0.4 Nov 4, 2022
0.0.3 Nov 3, 2022
0.0.2 Dec 13, 2021
0.0.1 Dec 13, 2021

#1570 in Data structures

MIT license

49KB
1K SLoC

fr-trie

CI CodeCov

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

License

Licensed under MIT license

Dependencies

~0.5–1MB
~25K SLoC