solana_core/consensus/
tree_diff.rs

1use std::{collections::HashSet, hash::Hash};
2
3pub trait TreeDiff<'a> {
4    type TreeKey: 'a + Hash + PartialEq + Eq + Copy;
5    type ChildIter: Iterator<Item = &'a Self::TreeKey>;
6
7    fn children(&self, key: &Self::TreeKey) -> Option<Self::ChildIter>;
8
9    fn contains_slot(&self, slot: &Self::TreeKey) -> bool;
10
11    // Find all nodes reachable from `root1`, excluding subtree at `root2`
12    fn subtree_diff(&self, root1: Self::TreeKey, root2: Self::TreeKey) -> HashSet<Self::TreeKey> {
13        if !self.contains_slot(&root1) {
14            return HashSet::new();
15        }
16        let mut pending_keys = vec![root1];
17        let mut reachable_set = HashSet::new();
18        while let Some(current_key) = pending_keys.pop() {
19            if current_key == root2 {
20                continue;
21            }
22            for child in self
23                .children(&current_key)
24                .expect("slot was discovered earlier, must exist")
25            {
26                pending_keys.push(*child);
27            }
28            reachable_set.insert(current_key);
29        }
30
31        reachable_set
32    }
33}