1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
use crate::keys::*;
use crate::TrieNode;
use crate::{SubTrie, SubTrieMut, SubTrieResult};
use std::borrow::Borrow;
use nibble_vec::Nibblet;
impl<'a, K, V> SubTrie<'a, K, V>
where
K: TrieKey,
{
pub fn get<Q: ?Sized>(&self, key: &Q) -> SubTrieResult<&V>
where
K: Borrow<Q>,
Q: TrieKey,
{
subtrie_get(&self.prefix, self.node, key)
}
}
fn subtrie_get<'a, K, Q: ?Sized, V>(
prefix: &Nibblet,
node: &'a TrieNode<K, V>,
key: &Q,
) -> SubTrieResult<&'a V>
where
K: TrieKey,
K: Borrow<Q>,
Q: TrieKey,
{
let key_enc = key.encode();
match match_keys(0, prefix, &key_enc) {
KeyMatch::Full => Ok(node.value()),
KeyMatch::FirstPrefix => Ok(node
.get(&stripped(key_enc, prefix))
.and_then(TrieNode::value)),
_ => Err(()),
}
}
impl<'a, K, V> SubTrieMut<'a, K, V>
where
K: TrieKey,
{
pub fn value_mut(&mut self) -> Option<&mut V> {
self.node.value_mut()
}
pub fn get<Q: ?Sized>(&self, key: &Q) -> SubTrieResult<&V>
where
K: Borrow<Q>,
Q: TrieKey,
{
subtrie_get(&self.prefix, &*self.node, key)
}
pub fn insert(&mut self, key: K, value: V) -> SubTrieResult<V> {
let key_enc = key.encode();
let previous = match match_keys(0, &self.prefix, &key_enc) {
KeyMatch::Full => self.node.replace_value(key, value),
KeyMatch::FirstPrefix => self
.node
.insert(key, value, stripped(key_enc, &self.prefix)),
_ => {
return Err(());
}
};
if previous.is_none() {
*self.length += 1;
}
Ok(previous)
}
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> SubTrieResult<V>
where
K: Borrow<Q>,
Q: TrieKey,
{
let key_enc = key.encode();
let removed = match match_keys(0, &self.prefix, &key_enc) {
KeyMatch::Full => self.node.take_value(key),
KeyMatch::FirstPrefix => self.node.remove(key),
_ => {
return Err(());
}
};
if removed.is_some() {
*self.length -= 1;
}
Ok(removed)
}
}
fn stripped(mut key: Nibblet, prefix: &Nibblet) -> Nibblet {
key.split(prefix.len())
}