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,
{
    /// Look up the value for the given key, which should be an extension of this subtrie's key.
    ///
    /// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
    /// form *must* match those for the key type
    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,
{
    /// Mutable reference to the node's value.
    pub fn value_mut(&mut self) -> Option<&mut V> {
        self.node.value_mut()
    }

    /// Look up the value for the given key, which should be an extension of this subtrie's key.
    ///
    /// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
    /// form *must* match those for the key type
    pub fn get<Q: ?Sized>(&self, key: &Q) -> SubTrieResult<&V>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        subtrie_get(&self.prefix, &*self.node, key)
    }

    /// Insert a value in this subtrie. The key should be an extension of this subtrie's 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)
    }

    /// Remove a value from this subtrie. The key should be an extension of this subtrie's key.
    ///
    /// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
    /// form *must* match those for the key type
    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())
}