reth_trie_common/
utils.rs

1use alloc::vec::Vec;
2use core::cmp::Ordering;
3
4/// Helper function to extend a sorted vector with another sorted vector.
5/// Values from `other` take precedence for duplicate keys.
6///
7/// This function efficiently merges two sorted vectors by:
8/// 1. Iterating through the target vector with mutable references
9/// 2. Using a peekable iterator for the other vector
10/// 3. For each target item, processing other items that come before or equal to it
11/// 4. Collecting items from other that need to be inserted
12/// 5. Appending and re-sorting only if new items were added
13pub(crate) fn extend_sorted_vec<K, V>(target: &mut Vec<(K, V)>, other: &[(K, V)])
14where
15    K: Clone + Ord,
16    V: Clone,
17{
18    if other.is_empty() {
19        return;
20    }
21
22    let mut other_iter = other.iter().peekable();
23    let mut to_insert = Vec::new();
24
25    // Iterate through target and update/collect items from other
26    for target_item in target.iter_mut() {
27        while let Some(other_item) = other_iter.peek() {
28            match other_item.0.cmp(&target_item.0) {
29                Ordering::Less => {
30                    // Other item comes before current target item, collect it
31                    to_insert.push(other_iter.next().unwrap().clone());
32                }
33                Ordering::Equal => {
34                    // Same key, update target with other's value
35                    target_item.1 = other_iter.next().unwrap().1.clone();
36                    break;
37                }
38                Ordering::Greater => {
39                    // Other item comes after current target item, keep target unchanged
40                    break;
41                }
42            }
43        }
44    }
45
46    // Append collected new items, as well as any remaining from `other` which are necessarily also
47    // new, and sort if needed
48    if !to_insert.is_empty() || other_iter.peek().is_some() {
49        target.extend(to_insert);
50        target.extend(other_iter.cloned());
51        target.sort_unstable_by(|a, b| a.0.cmp(&b.0));
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_extend_sorted_vec() {
61        let mut target = vec![(1, "a"), (3, "c")];
62        let other = vec![(2, "b"), (3, "c_new")];
63        extend_sorted_vec(&mut target, &other);
64        assert_eq!(target, vec![(1, "a"), (2, "b"), (3, "c_new")]);
65    }
66}
reth_trie_common/utils.rs

reth_trie_common/
utils.rs
