fqdn_trie/lib.rs
1//! This crate provides two data structures based on FQDN tries in order
2//! to provide very fast lookup in the FQDN hierarchy.
3//!
4//! The trie implementation is optimized to FQDN context and follows these rules:
5//! * the search algorithm finds the longuest domain suffix
6//! * the algorithm is case-insensitive
7//! * the internal structure exploits the range of allowed characters in FQDN
8
9mod trie;
10mod set;
11mod map;
12
13use fqdn::{FQDN,Fqdn};
14pub use set::FqdnTrieSet;
15pub use map::FqdnTrieMap;
16
17/// Associate a FQDN to a structure.
18trait HasFqdn {
19 /// Get the FQDN which is associated to this trait.
20 fn fqdn(&self) -> &Fqdn;
21}
22
23// size of the alphabet
24pub(crate) const ALPHABET_SIZE: usize = 40; // we should also count the '_' and '#'
25
26// in order to decrease the necessary memory, this table reduces the search space only
27// to allowed chars in FQDN, i.e. a-z, A-Z, 0-9, -, _ and #.
28// all the others are treated equally (i.e. as a dot)
29// this is case insensitive (lower and upper case give the same index)
30
31pub(crate) const ALPHABET: [u8;256] = [
32 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 16
33 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 32
34 0, 0, 0,39, 0, 0, 0, 0, 0, 0, 0, 0, 0,37, 0, 0, // 48 (# et -)
35 27,28,29,30,31,32,33,34, 35,36, 0, 0, 0, 0, 0, 0, // 64 (0-9)
36 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, // 80 (A-O)
37 16,17,18,19,20,21,22,23, 24,25,26, 0, 0, 0, 0,38, // 96 (P-Z et _)
38 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, // 112 (a-o)
39 16,17,18,19,20,21,22,23, 24,25,26, 0, 0, 0, 0, 0, // 128 (p-z)
40 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
41 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
42 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
43 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
44 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
45 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
46 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
47 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
48];