/rust/registry/src/index.crates.io-1949cf8c6b5b557f/radix_trie-0.2.1/src/trie.rs

Source
use crate::traversal::DescendantResult::*;
use crate::TrieNode;
use crate::{SubTrie, SubTrieMut, Trie, TrieCommon, TrieKey};
use std::borrow::Borrow;

use nibble_vec::Nibblet;

impl<K, V> Trie<K, V>
where
    K: TrieKey,
{
    /// Create an empty Trie.
    #[inline]
    pub fn new() -> Trie<K, V> {
        Trie {
            length: 0,
            node: TrieNode::new(),
        }
    }

    /// Fetch a reference to the given key's corresponding value, if any.
    ///
    /// 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.
    #[inline]
    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        let key_fragments = key.encode();
        self.node
            .get(&key_fragments)
            .and_then(|t| t.value_checked(key))
    }

    /// Fetch a mutable reference to the given key's corresponding value, if any.
    ///
    /// 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.
    #[inline]
    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        let key_fragments = key.encode();
        self.node
            .get_mut(&key_fragments)
            .and_then(|t| t.value_checked_mut(key))
    }

    /// Insert the given key-value pair, returning any previous value associated with the key.
    #[inline]
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        let key_fragments = key.encode();
        let result = self.node.insert(key, value, key_fragments);
        if result.is_none() {
            self.length += 1;
        }
        result
    }

    /// Remove the value associated with the given 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.
    #[inline]
    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        let removed = self.node.remove(key);
        if removed.is_some() {
            self.length -= 1;
        }
        removed
    }

    /// Get a mutable reference to the value stored at this node, if any.
    pub fn value_mut(&mut self) -> Option<&mut V> {
        self.node.value_mut()
    }

    /// Fetch a reference to the subtrie for a given 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.
    #[inline]
    pub fn subtrie<'a, Q: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        let key_fragments = key.encode();
        self.node
            .get(&key_fragments)
            .map(|node| node.as_subtrie(key_fragments))
    }

    /// Fetch a mutable reference to the subtrie for a given 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.
    #[inline]
    pub fn subtrie_mut<'a, Q: ?Sized>(&'a mut self, key: &Q) -> Option<SubTrieMut<'a, K, V>>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        let key_fragments = key.encode();
        let length_ref = &mut self.length;
        self.node
            .get_mut(&key_fragments)
            .map(move |node| node.as_subtrie_mut(key_fragments, length_ref))
    }

    /// Fetch a reference to the closest ancestor node of the given key.
    ///
    /// If `key` is encoded as byte-vector `b`, return the node `n` in the tree
    /// such that `n`'s key's byte-vector is the longest possible prefix of `b`, and `n`
    /// has a value.
    ///
    /// Invariant: `result.is_some() => result.key_value.is_some()`.
    ///
    /// 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.
    #[inline]
    pub fn get_ancestor<'a, Q: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        let mut key_fragments = key.encode();
        self.node
            .get_ancestor(&key_fragments)
            .map(|(node, node_key_len)| {
                key_fragments.split(node_key_len);
                node.as_subtrie(key_fragments)
            })
    }

    /// Fetch the closest ancestor *value* for a given key.
    ///
    /// See `get_ancestor` for precise semantics, this is just a shortcut.
    ///
    /// 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.
    #[inline]
    pub fn get_ancestor_value<Q: ?Sized>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        self.get_ancestor(key).and_then(|t| t.node.value())
    }

    /// 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
    #[inline]
    pub fn get_raw_ancestor<'a, Q: ?Sized>(&'a self, key: &Q) -> SubTrie<'a, K, V>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        let mut nv = key.encode();
        let (ancestor_node, depth) = self.node.get_raw_ancestor(&nv);
        nv.split(depth);
        ancestor_node.as_subtrie(nv)
    }

    /// Fetch the closest descendant for a given key.
    ///
    /// If the key is in the trie, this is the same as `subtrie`.
    ///
    /// 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
    #[inline]
    pub fn get_raw_descendant<'a, Q: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
    where
        K: Borrow<Q>,
        Q: TrieKey,
    {
        let mut nv = key.encode();
        self.node.get_raw_descendant(&nv).map(|desc| {
            let (node, prefix) = match desc {
                NoModification(node) => (node, nv),
                ExtendKey(node, depth, extension) => {
                    nv.split(depth);
                    (node, nv.join(extension))
                }
            };
            node.as_subtrie(prefix)
        })
    }

    /// Take a function `f` and apply it to the value stored at `key`.
    ///
    /// If no value is stored at `key`, store `default`.
    #[inline]
    pub fn map_with_default<F>(&mut self, key: K, f: F, default: V)
    where
        F: Fn(&mut V),
    {
        {
            if let Some(v) = self.get_mut(&key) {
                f(v);
                return;
            }
        }
        self.insert(key, default);
    }

    /// Check that the Trie invariants are satisfied - you shouldn't ever have to call this!
    /// Quite slow!
    #[doc(hidden)]
    pub fn check_integrity(&self) -> bool {
        let (ok, length) = self.node.check_integrity_recursive(&Nibblet::new());
        ok && length == self.length
    }
}

impl<K, V> PartialEq for Trie<K, V>
where
    K: TrieKey,
    V: PartialEq,
{
    #[inline]
    fn eq(&self, other: &Trie<K, V>) -> bool {
        if self.len() != other.len() {
            return false;
        }

        self.iter()
            .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
    }
}

impl<K: TrieKey, V> Default for Trie<K, V> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

Coverage Report

Created: 2025-10-10 07:11

Line	Count	Source
1		use crate::traversal::DescendantResult::*;
2		use crate::TrieNode;
3		use crate::{SubTrie, SubTrieMut, Trie, TrieCommon, TrieKey};
4		use std::borrow::Borrow;
5
6		use nibble_vec::Nibblet;
7
8		impl<K, V> Trie<K, V>
9		where
10		K: TrieKey,
11		{
12		/// Create an empty Trie.
13		#[inline]
14	0	pub fn new() -> Trie<K, V> {
15	0	Trie {
16	0	length: 0,
17	0	node: TrieNode::new(),
18	0	}
19	0	} Unexecuted instantiation: <radix_trie::Trie<alloc::vec::Vec<u8>, bool>>::new Unexecuted instantiation: <radix_trie::Trie<_, _>>::new
20
21		/// Fetch a reference to the given key's corresponding value, if any.
22		///
23		/// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
24		/// form must match those for the key type.
25		#[inline]
26	0	pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
27	0	where
28	0	K: Borrow<Q>,
29	0	Q: TrieKey,
30		{
31	0	let key_fragments = key.encode();
32	0	self.node
33	0	.get(&key_fragments)
34	0	.and_then(\|t\| t.value_checked(key)) Unexecuted instantiation: <radix_trie::Trie<alloc::vec::Vec<u8>, bool>>::get::<alloc::vec::Vec<u8>>::{closure#0} Unexecuted instantiation: <radix_trie::Trie<_, _>>::get::<_>::{closure#0}
35	0	} Unexecuted instantiation: <radix_trie::Trie<alloc::vec::Vec<u8>, bool>>::get::<alloc::vec::Vec<u8>> Unexecuted instantiation: <radix_trie::Trie<_, _>>::get::<_>
36
37		/// Fetch a mutable reference to the given key's corresponding value, if any.
38		///
39		/// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
40		/// form must match those for the key type.
41		#[inline]
42	0	pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
43	0	where
44	0	K: Borrow<Q>,
45	0	Q: TrieKey,
46		{
47	0	let key_fragments = key.encode();
48	0	self.node
49	0	.get_mut(&key_fragments)
50	0	.and_then(\|t\| t.value_checked_mut(key))
51	0	}
52
53		/// Insert the given key-value pair, returning any previous value associated with the key.
54		#[inline]
55	0	pub fn insert(&mut self, key: K, value: V) -> Option<V> {
56	0	let key_fragments = key.encode();
57	0	let result = self.node.insert(key, value, key_fragments);
58	0	if result.is_none() {
59	0	self.length += 1;
60	0	}
61	0	result
62	0	} Unexecuted instantiation: <radix_trie::Trie<alloc::vec::Vec<u8>, bool>>::insert Unexecuted instantiation: <radix_trie::Trie<_, _>>::insert
63
64		/// Remove the value associated with the given key.
65		///
66		/// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
67		/// form must match those for the key type.
68		#[inline]
69	0	pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
70	0	where
71	0	K: Borrow<Q>,
72	0	Q: TrieKey,
73		{
74	0	let removed = self.node.remove(key);
75	0	if removed.is_some() {
76	0	self.length -= 1;
77	0	}
78	0	removed
79	0	}
80
81		/// Get a mutable reference to the value stored at this node, if any.
82	0	pub fn value_mut(&mut self) -> Option<&mut V> {
83	0	self.node.value_mut()
84	0	}
85
86		/// Fetch a reference to the subtrie for a given 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		#[inline]
91	0	pub fn subtrie<'a, Q: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
92	0	where
93	0	K: Borrow<Q>,
94	0	Q: TrieKey,
95		{
96	0	let key_fragments = key.encode();
97	0	self.node
98	0	.get(&key_fragments)
99	0	.map(\|node\| node.as_subtrie(key_fragments))
100	0	}
101
102		/// Fetch a mutable reference to the subtrie for a given key.
103		///
104		/// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
105		/// form must match those for the key type.
106		#[inline]
107	0	pub fn subtrie_mut<'a, Q: ?Sized>(&'a mut self, key: &Q) -> Option<SubTrieMut<'a, K, V>>
108	0	where
109	0	K: Borrow<Q>,
110	0	Q: TrieKey,
111		{
112	0	let key_fragments = key.encode();
113	0	let length_ref = &mut self.length;
114	0	self.node
115	0	.get_mut(&key_fragments)
116	0	.map(move \|node\| node.as_subtrie_mut(key_fragments, length_ref))
117	0	}
118
119		/// Fetch a reference to the closest ancestor node of the given key.
120		///
121		/// If `key` is encoded as byte-vector `b`, return the node `n` in the tree
122		/// such that `n`'s key's byte-vector is the longest possible prefix of `b`, and `n`
123		/// has a value.
124		///
125		/// Invariant: `result.is_some() => result.key_value.is_some()`.
126		///
127		/// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
128		/// form must match those for the key type.
129		#[inline]
130	0	pub fn get_ancestor<'a, Q: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
131	0	where
132	0	K: Borrow<Q>,
133	0	Q: TrieKey,
134		{
135	0	let mut key_fragments = key.encode();
136	0	self.node
137	0	.get_ancestor(&key_fragments)
138	0	.map(\|(node, node_key_len)\| {
139	0	key_fragments.split(node_key_len);
140	0	node.as_subtrie(key_fragments)
141	0	})
142	0	}
143
144		/// Fetch the closest ancestor value for a given key.
145		///
146		/// See `get_ancestor` for precise semantics, this is just a shortcut.
147		///
148		/// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
149		/// form must match those for the key type.
150		#[inline]
151	0	pub fn get_ancestor_value<Q: ?Sized>(&self, key: &Q) -> Option<&V>
152	0	where
153	0	K: Borrow<Q>,
154	0	Q: TrieKey,
155		{
156	0	self.get_ancestor(key).and_then(\|t\| t.node.value())
157	0	}
158
159		/// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
160		/// form must match those for the key type
161		#[inline]
162	0	pub fn get_raw_ancestor<'a, Q: ?Sized>(&'a self, key: &Q) -> SubTrie<'a, K, V>
163	0	where
164	0	K: Borrow<Q>,
165	0	Q: TrieKey,
166		{
167	0	let mut nv = key.encode();
168	0	let (ancestor_node, depth) = self.node.get_raw_ancestor(&nv);
169	0	nv.split(depth);
170	0	ancestor_node.as_subtrie(nv)
171	0	}
172
173		/// Fetch the closest descendant for a given key.
174		///
175		/// If the key is in the trie, this is the same as `subtrie`.
176		///
177		/// The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed
178		/// form must match those for the key type
179		#[inline]
180	0	pub fn get_raw_descendant<'a, Q: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
181	0	where
182	0	K: Borrow<Q>,
183	0	Q: TrieKey,
184		{
185	0	let mut nv = key.encode();
186	0	self.node.get_raw_descendant(&nv).map(\|desc\| {
187	0	let (node, prefix) = match desc {
188	0	NoModification(node) => (node, nv),
189	0	ExtendKey(node, depth, extension) => {
190	0	nv.split(depth);
191	0	(node, nv.join(extension))
192		}
193		};
194	0	node.as_subtrie(prefix)
195	0	})
196	0	}
197
198		/// Take a function `f` and apply it to the value stored at `key`.
199		///
200		/// If no value is stored at `key`, store `default`.
201		#[inline]
202	0	pub fn map_with_default<F>(&mut self, key: K, f: F, default: V)
203	0	where
204	0	F: Fn(&mut V),
205		{
206		{
207	0	if let Some(v) = self.get_mut(&key) {
208	0	f(v);
209	0	return;
210	0	}
211		}
212	0	self.insert(key, default);
213	0	}
214
215		/// Check that the Trie invariants are satisfied - you shouldn't ever have to call this!
216		/// Quite slow!
217		#[doc(hidden)]
218	0	pub fn check_integrity(&self) -> bool {
219	0	let (ok, length) = self.node.check_integrity_recursive(&Nibblet::new());
220	0	ok && length == self.length
221	0	}
222		}
223
224		impl<K, V> PartialEq for Trie<K, V>
225		where
226		K: TrieKey,
227		V: PartialEq,
228		{
229		#[inline]
230	0	fn eq(&self, other: &Trie<K, V>) -> bool {
231	0	if self.len() != other.len() {
232	0	return false;
233	0	}
234
235	0	self.iter()
236	0	.all(\|(key, value)\| other.get(key).map_or(false, \|v\| value == v))
237	0	}
238		}
239
240		impl<K: TrieKey, V> Default for Trie<K, V> {
241		#[inline]
242	0	fn default() -> Self {
243	0	Self::new()
244	0	} Unexecuted instantiation: <radix_trie::Trie<alloc::vec::Vec<u8>, bool> as core::default::Default>::default Unexecuted instantiation: <radix_trie::Trie<_, _> as core::default::Default>::default
245		}