reth_trie_common/
utils.rs

1use alloc::vec::Vec;
2
3/// Helper function to extend a sorted vector with another sorted vector.
4/// Values from `other` take precedence for duplicate keys.
5///
6/// This function efficiently merges two sorted vectors by:
7/// 1. Iterating through the target vector with mutable references
8/// 2. Using a peekable iterator for the other vector
9/// 3. For each target item, processing other items that come before or equal to it
10/// 4. Collecting items from other that need to be inserted
11/// 5. Appending and re-sorting only if new items were added
12pub(crate) fn extend_sorted_vec<K, V>(target: &mut Vec<(K, V)>, other: &[(K, V)])
13where
14    K: Clone + Ord,
15    V: Clone,
16{
17    if other.is_empty() {
18        return;
19    }
20
21    let mut other_iter = other.iter().peekable();
22    let mut to_insert = Vec::new();
23
24    // Iterate through target and update/collect items from other
25    for target_item in target.iter_mut() {
26        while let Some(other_item) = other_iter.peek() {
27            use core::cmp::Ordering;
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}
reth_trie_common/utils.rs

reth_trie_common/
utils.rs
