1pub const NO_PATTERN: u16 = u16::MAX;
4pub const NO_NODE: u16 = u16::MAX;
5
6#[derive(Debug, Clone)]
7pub struct TrieNode {
8 pub pattern_idx: u16,
9 pub children: [u16; 128],
10}
11
12impl Default for TrieNode {
13 fn default() -> Self {
14 Self {
15 pattern_idx: NO_PATTERN,
16 children: [NO_NODE; 128],
17 }
18 }
19}
20
21#[derive(Debug, Clone)]
22pub struct PatternTrie {
23 pub nodes: Vec<TrieNode>,
24 pub max_depth: usize,
25}
26
27impl Default for PatternTrie {
28 fn default() -> Self {
29 Self::new()
30 }
31}
32
33impl PatternTrie {
34 pub fn new() -> Self {
35 let mut trie = Self {
36 nodes: Vec::with_capacity(384),
37 max_depth: 0,
38 };
39 trie.nodes.push(TrieNode::default());
41 trie
42 }
43
44 pub fn insert(&mut self, pattern_bytes: &[u8], pattern_idx: u16) {
46 let mut current_idx: usize = 0;
47 let mut depth = 0;
48
49 for &b in pattern_bytes {
50 let ascii_idx = (b & 0x7F) as usize;
51 let next_idx = self.nodes[current_idx].children[ascii_idx];
52
53 if next_idx == NO_NODE {
54 let new_idx = self.nodes.len() as u16;
55 self.nodes.push(TrieNode::default());
56 self.nodes[current_idx].children[ascii_idx] = new_idx;
57 current_idx = new_idx as usize;
58 } else {
59 current_idx = next_idx as usize;
60 }
61 depth += 1;
62 }
63
64 self.nodes[current_idx].pattern_idx = pattern_idx;
65 if depth > self.max_depth {
66 self.max_depth = depth;
67 }
68 }
69
70 #[inline(always)]
73 pub fn longest_match(&self, input: &[u8], start: usize) -> Option<(u16, usize)> {
74 let len = input.len();
75 if start >= len {
76 return None;
77 }
78
79 let mut current_node = 0usize;
80 let mut best_match: Option<(u16, usize)> = None;
81 let limit = (start + self.max_depth).min(len);
82
83 let mut offset = start;
84 while offset < limit {
85 let b = input[offset];
86 if b >= 128 {
87 break;
88 }
89 let next_node = self.nodes[current_node].children[b as usize];
90 if next_node == NO_NODE {
91 break;
92 }
93 current_node = next_node as usize;
94 let pat_idx = self.nodes[current_node].pattern_idx;
95 if pat_idx != NO_PATTERN {
96 best_match = Some((pat_idx, offset - start + 1));
97 }
98 offset += 1;
99 }
100
101 best_match
102 }
103}