Instantly share code, notes, and snippets.

Embed
What would you like to do?
Radix Trie Traversal Function
fn uber<K, V, Key, Value, Output,
RootFn, NoChildFn, FullMatchFn, PartialMatchFn, FirstPrefixFn>
(
trie: &mut Trie<K, V>,
key: Key,
value: Value,
mut key_fragments: NibbleVec,
root_fn: RootFn,
no_child_fn: NoChildFn,
full_match_fn: FullMatchFn,
partial_match_fn: PartialMatchFn,
first_prefix_fn: FirstPrefixFn,
action_fn: fn(&mut Trie<K, V>, Output, usize) -> Output
) -> Output
where
RootFn: Fn(&mut Trie<K, V>, Key, Value) -> Output,
NoChildFn: Fn(&mut Trie<K, V>, Key, Value, NibbleVec, usize) -> Output,
FullMatchFn: Fn(&mut Trie<K, V>, Key, Value, NibbleVec) -> Output,
PartialMatchFn: Fn(&mut Trie<K, V>, Key, Value, NibbleVec, usize) -> Output,
FirstPrefixFn: Fn(&mut Trie<K, V>, Key, Value, NibbleVec) -> Output
{
use keys::{KeyMatch, match_keys};
if key_fragments.len() == 0 {
return root_fn(trie, key, value);
}
let bucket = key_fragments.get(0) as usize;
let intermediate = match trie.children[bucket] {
None => return no_child_fn(trie, key, value, key_fragments, bucket),
Some(ref mut child) => {
match match_keys(&key_fragments, &child.key) {
KeyMatch::Full => full_match_fn(child, key, value, key_fragments),
KeyMatch::Partial(idx) => partial_match_fn(child, key, value, key_fragments, idx),
KeyMatch::FirstPrefix => first_prefix_fn(child, key, value, key_fragments),
// Split the key and recurse.
KeyMatch::SecondPrefix => {
let new_key = key_fragments.split(child.key.len());
uber(child, key, value, new_key, root_fn,
no_child_fn, full_match_fn, partial_match_fn, first_prefix_fn, action_fn)
}
}
}
};
action_fn(trie, intermediate, bucket)
}
fn no_op<K, V>(trie: &mut Trie<K, V>, key: K, value: V) -> Option<V> where K: TrieKey {
let encoding = NibbleVec::from_byte_vec(key.encode());
fn action_fn<K, V>(_: &mut Trie<K, V>, x: Option<V>, _: usize) -> Option<V> { x }
uber(
trie, key, value, encoding,
|_, _, _| None,
|_, _, _, _, _| None,
|_, _, _, _| None,
|_, _, _, _, _| None,
|_, _, _, _| None,
action_fn
)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment