solana_ledger/
ancestor_iterator.rs

1use {crate::blockstore::*, solana_clock::Slot, solana_hash::Hash};
2
3pub struct AncestorIterator<'a> {
4    current: Option<Slot>,
5    blockstore: &'a Blockstore,
6}
7
8impl<'a> AncestorIterator<'a> {
9    pub fn new(start_slot: Slot, blockstore: &'a Blockstore) -> Self {
10        let current = blockstore.meta(start_slot).unwrap().and_then(|slot_meta| {
11            if start_slot != 0 {
12                slot_meta.parent_slot
13            } else {
14                None
15            }
16        });
17        Self {
18            current,
19            blockstore,
20        }
21    }
22
23    pub fn new_inclusive(start_slot: Slot, blockstore: &'a Blockstore) -> Self {
24        Self {
25            current: blockstore.meta(start_slot).unwrap().map(|_| start_slot),
26            blockstore,
27        }
28    }
29}
30impl Iterator for AncestorIterator<'_> {
31    type Item = Slot;
32
33    fn next(&mut self) -> Option<Self::Item> {
34        let current = self.current;
35        current.inspect(|&slot| {
36            if slot != 0 {
37                self.current = self
38                    .blockstore
39                    .meta(slot)
40                    .unwrap()
41                    .and_then(|slot_meta| slot_meta.parent_slot);
42            } else {
43                self.current = None;
44            }
45        })
46    }
47}
48
49pub struct AncestorIteratorWithHash<'a> {
50    ancestor_iterator: AncestorIterator<'a>,
51}
52impl<'a> From<AncestorIterator<'a>> for AncestorIteratorWithHash<'a> {
53    fn from(ancestor_iterator: AncestorIterator<'a>) -> Self {
54        Self { ancestor_iterator }
55    }
56}
57impl Iterator for AncestorIteratorWithHash<'_> {
58    type Item = (Slot, Hash);
59    fn next(&mut self) -> Option<Self::Item> {
60        self.ancestor_iterator
61            .next()
62            .and_then(|next_ancestor_slot| {
63                self.ancestor_iterator
64                    .blockstore
65                    .get_bank_hash(next_ancestor_slot)
66                    .map(|next_ancestor_hash| (next_ancestor_slot, next_ancestor_hash))
67            })
68    }
69}
70
71#[cfg(test)]
72mod tests {
73    use {
74        super::*,
75        solana_hash::Hash,
76        std::{collections::HashMap, path::Path},
77        trees::tr,
78    };
79
80    fn setup_forks(ledger_path: &Path) -> Blockstore {
81        let blockstore = Blockstore::open(ledger_path).unwrap();
82        /*
83            Build fork structure:
84
85                slot 0
86                    |
87                slot 1
88                /    \
89            slot 2    |
90                |       |
91            slot 3    |
92                        |
93                        |
94                    slot 4
95        */
96        let tree = tr(0) / (tr(1) / (tr(2) / (tr(3))) / (tr(4)));
97        blockstore.add_tree(tree, true, true, 2, Hash::default());
98        blockstore
99    }
100
101    #[test]
102    fn test_ancestor_iterator() {
103        let ledger_path = get_tmp_ledger_path_auto_delete!();
104        let blockstore = setup_forks(ledger_path.path());
105
106        // Test correctness
107        assert!(AncestorIterator::new(0, &blockstore).next().is_none());
108        assert_eq!(
109            AncestorIterator::new(4, &blockstore).collect::<Vec<Slot>>(),
110            vec![1, 0]
111        );
112        assert_eq!(
113            AncestorIterator::new(3, &blockstore).collect::<Vec<Slot>>(),
114            vec![2, 1, 0]
115        );
116    }
117
118    #[test]
119    fn test_ancestor_iterator_inclusive() {
120        let ledger_path = get_tmp_ledger_path_auto_delete!();
121        let blockstore = Blockstore::open(ledger_path.path()).unwrap();
122
123        let (shreds, _) = make_slot_entries(0, 0, 42);
124        blockstore.insert_shreds(shreds, None, false).unwrap();
125        let (shreds, _) = make_slot_entries(1, 0, 42);
126        blockstore.insert_shreds(shreds, None, false).unwrap();
127        let (shreds, _) = make_slot_entries(2, 1, 42);
128        blockstore.insert_shreds(shreds, None, false).unwrap();
129
130        assert_eq!(
131            AncestorIterator::new(2, &blockstore).collect::<Vec<Slot>>(),
132            vec![1, 0]
133        );
134        // existing start_slot
135        assert_eq!(
136            AncestorIterator::new_inclusive(2, &blockstore).collect::<Vec<Slot>>(),
137            vec![2, 1, 0]
138        );
139
140        // non-existing start_slot
141        assert_eq!(
142            AncestorIterator::new_inclusive(3, &blockstore).collect::<Vec<Slot>>(),
143            vec![] as Vec<Slot>
144        );
145    }
146
147    #[test]
148    fn test_ancestor_iterator_with_hash() {
149        let ledger_path = get_tmp_ledger_path_auto_delete!();
150        let blockstore = setup_forks(ledger_path.path());
151
152        // Insert frozen hashes
153        let mut slot_to_bank_hash = HashMap::new();
154        for slot in 0..=4 {
155            let bank_hash = Hash::new_unique();
156            slot_to_bank_hash.insert(slot, bank_hash);
157            blockstore.insert_bank_hash(slot, bank_hash, false);
158        }
159
160        // Test correctness
161        assert!(
162            AncestorIteratorWithHash::from(AncestorIterator::new(0, &blockstore))
163                .next()
164                .is_none()
165        );
166        assert_eq!(
167            AncestorIteratorWithHash::from(AncestorIterator::new(4, &blockstore))
168                .collect::<Vec<(Slot, Hash)>>(),
169            vec![(1, slot_to_bank_hash[&1]), (0, slot_to_bank_hash[&0])]
170        );
171        assert_eq!(
172            AncestorIteratorWithHash::from(AncestorIterator::new(3, &blockstore))
173                .collect::<Vec<(Slot, Hash)>>(),
174            vec![
175                (2, slot_to_bank_hash[&2]),
176                (1, slot_to_bank_hash[&1]),
177                (0, slot_to_bank_hash[&0])
178            ]
179        );
180    }
181}
solana_ledger/ancestor_iterator.rs

solana_ledger/
ancestor_iterator.rs
