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

use keys::*;
use std::borrow::Borrow;
use trie_node::TrieNode;
use {NibbleVec, SubTrie, SubTrieMut, SubTrieResult};

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: &NibbleVec,
    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: NibbleVec, prefix: &NibbleVec) -> NibbleVec {
    key.split(prefix.len())
}