pub struct TrieNode<V> { /* private fields */ }Expand description
Implementation of a trie tree structure. In Sozu this is used to store and lookup domains recursively. Each node represents a “level domain”. A leaf node (leftmost label) can be a wildcard, a regex pattern or a plain string. Leaves also store a value associated with the complete domain. For Sozu it is a list of (PathRule, MethodRule, ClusterId). See the Router strucure.
Implementations§
Source§impl<V: Debug + Clone> TrieNode<V>
impl<V: Debug + Clone> TrieNode<V>
pub fn new(key: Key, value: V) -> TrieNode<V>
pub fn wildcard(key: Key, value: V) -> TrieNode<V>
pub fn root() -> TrieNode<V>
pub fn is_empty(&self) -> bool
pub fn insert(&mut self, key: Key, value: V) -> InsertResult
pub fn insert_recursive( &mut self, partial_key: &[u8], key: &Key, value: V, ) -> InsertResult
pub fn remove(&mut self, key: &Key) -> RemoveResult
pub fn remove_recursive(&mut self, partial_key: &[u8]) -> RemoveResult
Sourcepub fn lookup_with_path<'a, 'b>(
&'b self,
partial_key: &'a [u8],
accept_wildcard: bool,
trace: TrieMatches<'a, 'b>,
accept: &mut dyn FnMut(&KeyValue<Key, V>) -> bool,
) -> Option<(&'b KeyValue<Key, V>, TrieMatches<'a, 'b>)>
pub fn lookup_with_path<'a, 'b>( &'b self, partial_key: &'a [u8], accept_wildcard: bool, trace: TrieMatches<'a, 'b>, accept: &mut dyn FnMut(&KeyValue<Key, V>) -> bool, ) -> Option<(&'b KeyValue<Key, V>, TrieMatches<'a, 'b>)>
Look up partial_key and additionally collect the non-literal segments
that matched along the way (TrieMatches).
Equivalent to lookup for callers that don’t need the captures, but
frontends with $HOST[n] rewrite templates need the matched segments
to fill the placeholders. The accumulator is passed in by value so
callers can pre-size it (Vec::with_capacity) and we own the path
returned alongside the value. It carries the segments of the
candidate that ANSWERED: the walk rewinds the ones it tried and
abandoned.
accept filters candidates — see TrieNode::lookup_recursive
for the precedence order it is applied in. Pass
&mut |_: &KeyValue<Key, V>| true to take the first leaf found.
Sourcepub fn lookup(
&self,
partial_key: &[u8],
accept_wildcard: bool,
) -> Option<&KeyValue<Key, V>>
pub fn lookup( &self, partial_key: &[u8], accept_wildcard: bool, ) -> Option<&KeyValue<Key, V>>
Request-addressed lookup: which entry serves partial_key.
Same walk and same precedence as TrieNode::lookup_with_path —
stated once, in TrieNode::lookup_recursive — without recording
the segments it matched. This is the resolver SNI goes through
(lib/src/tls.rs, lib/src/protocol/tcp_preread/), so certificate
selection follows the same order as HTTP routing.
pub fn lookup_mut( &mut self, partial_key: &[u8], accept_wildcard: bool, ) -> Option<&mut KeyValue<Key, V>>
pub fn print(&self)
pub fn print_recursive(&self, partial_key: &[u8], indent: u8)
Sourcepub fn for_each_value_mut<F: FnMut(&mut V)>(&mut self, f: &mut F)
pub fn for_each_value_mut<F: FnMut(&mut V)>(&mut self, f: &mut F)
Visit every stored value in the trie (the literal key_value and
the leftmost wildcard slot of every node, plus all
regex-subtree leaves) and invoke f on each. Used by the router
to walk all routes for cross-cutting refreshes (e.g. listener-
default HSTS reflow) without rebuilding the trie.
pub fn domain_insert(&mut self, key: Key, value: V) -> InsertResult
pub fn domain_remove(&mut self, key: &Key) -> RemoveResult
pub fn domain_lookup( &self, key: &[u8], accept_wildcard: bool, ) -> Option<&KeyValue<Key, V>>
Sourcepub fn domain_lookup_mut(
&mut self,
key: &[u8],
accept_wildcard: bool,
) -> Option<&mut KeyValue<Key, V>>
pub fn domain_lookup_mut( &mut self, key: &[u8], accept_wildcard: bool, ) -> Option<&mut KeyValue<Key, V>>
Key-addressed mutable accessor: the node the configured hostname
key OWNS, never the node that would serve a request for it.
With accept_wildcard: false a literal key may not resolve into a
non-literal entry — neither the * slot nor a matching regex
segment — which is what keeps add_tree_rule and insert_sni_route
from pushing a rule onto an entry that serves a whole family of
hosts (sozu#1351). Use TrieNode::domain_lookup to ask which
entry serves a host.