Coverage Report

Created: 2026-06-30 07:02

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/rust/registry/src/index.crates.io-1949cf8c6b5b557f/radix_trie-0.3.0/src/subtrie.rs
Line
Count
Source
1
use crate::TrieNode;
2
use crate::keys::*;
3
use crate::{SubTrie, SubTrieMut, SubTrieResult};
4
use std::borrow::Borrow;
5
6
use nibble_vec::Nibblet;
7
8
impl<'a, K, V> SubTrie<'a, K, V>
9
where
10
    K: TrieKey,
11
{
12
    /// Look up the value for the given key, which should be an extension of this subtrie's key.
13
    ///
14
    /// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
15
    /// form *must* match those for the key type
16
0
    pub fn get<Q: ?Sized>(&self, key: &Q) -> SubTrieResult<&V>
17
0
    where
18
0
        K: Borrow<Q>,
19
0
        Q: TrieKey,
20
    {
21
0
        subtrie_get(&self.prefix, self.node, key)
22
0
    }
23
}
24
25
0
fn subtrie_get<'a, K, Q: ?Sized, V>(
26
0
    prefix: &Nibblet,
27
0
    node: &'a TrieNode<K, V>,
28
0
    key: &Q,
29
0
) -> SubTrieResult<&'a V>
30
0
where
31
0
    K: TrieKey,
32
0
    K: Borrow<Q>,
33
0
    Q: TrieKey,
34
{
35
0
    let key_enc = key.encode();
36
0
    match match_keys(0, prefix, &key_enc) {
37
0
        KeyMatch::Full => Ok(node.value()),
38
0
        KeyMatch::FirstPrefix => Ok(node
39
0
            .get(&stripped(key_enc, prefix))
40
0
            .and_then(TrieNode::value)),
41
0
        _ => Err(()),
42
    }
43
0
}
44
45
impl<'a, K, V> SubTrieMut<'a, K, V>
46
where
47
    K: TrieKey,
48
{
49
    /// Mutable reference to the node's value.
50
0
    pub fn value_mut(&mut self) -> Option<&mut V> {
51
0
        self.node.value_mut()
52
0
    }
53
54
    /// Look up the value for the given key, which should be an extension of this subtrie's key.
55
    ///
56
    /// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
57
    /// form *must* match those for the key type
58
0
    pub fn get<Q: ?Sized>(&self, key: &Q) -> SubTrieResult<&V>
59
0
    where
60
0
        K: Borrow<Q>,
61
0
        Q: TrieKey,
62
    {
63
0
        subtrie_get(&self.prefix, &*self.node, key)
64
0
    }
65
66
    /// Insert a value in this subtrie. The key should be an extension of this subtrie's key.
67
0
    pub fn insert(&mut self, key: K, value: V) -> SubTrieResult<V> {
68
0
        let key_enc = key.encode();
69
0
        let previous = match match_keys(0, &self.prefix, &key_enc) {
70
0
            KeyMatch::Full => self.node.replace_value(key, value),
71
0
            KeyMatch::FirstPrefix => self
72
0
                .node
73
0
                .insert(key, value, stripped(key_enc, &self.prefix)),
74
            _ => {
75
0
                return Err(());
76
            }
77
        };
78
79
0
        if previous.is_none() {
80
0
            *self.length += 1;
81
0
        }
82
83
0
        Ok(previous)
84
0
    }
85
86
    /// Remove a value from this subtrie. The key should be an extension of this subtrie's key.
87
    ///
88
    /// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
89
    /// form *must* match those for the key type
90
0
    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> SubTrieResult<V>
91
0
    where
92
0
        K: Borrow<Q>,
93
0
        Q: TrieKey,
94
    {
95
0
        let key_enc = key.encode();
96
0
        let removed = match match_keys(0, &self.prefix, &key_enc) {
97
0
            KeyMatch::Full => self.node.take_value(key),
98
0
            KeyMatch::FirstPrefix => self.node.remove(key),
99
            _ => {
100
0
                return Err(());
101
            }
102
        };
103
104
0
        if removed.is_some() {
105
0
            *self.length -= 1;
106
0
        }
107
108
0
        Ok(removed)
109
0
    }
110
}
111
112
0
fn stripped(mut key: Nibblet, prefix: &Nibblet) -> Nibblet {
113
0
    key.split(prefix.len())
114
0
}