/__w/smoldot/smoldot/repo/lib/src/chain/fork_tree.rs
Line | Count | Source (jump to first uncovered line) |
1 | | // Smoldot |
2 | | // Copyright (C) 2019-2022 Parity Technologies (UK) Ltd. |
3 | | // SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0 |
4 | | |
5 | | // This program is free software: you can redistribute it and/or modify |
6 | | // it under the terms of the GNU General Public License as published by |
7 | | // the Free Software Foundation, either version 3 of the License, or |
8 | | // (at your option) any later version. |
9 | | |
10 | | // This program is distributed in the hope that it will be useful, |
11 | | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | | // GNU General Public License for more details. |
14 | | |
15 | | // You should have received a copy of the GNU General Public License |
16 | | // along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | | |
18 | | //! Data structure containing trees of nodes. |
19 | | //! |
20 | | //! The [`ForkTree`] data structure can be used in situations where there exists a finalized |
21 | | //! block, plus a tree of non-finalized blocks that all descend from that finalized block. |
22 | | //! |
23 | | //! The [`ForkTree`] only contains the non-finalized blocks. The finalized block, virtual root |
24 | | //! of the tree, is only implicitly there. |
25 | | //! |
26 | | //! # Example |
27 | | //! |
28 | | //! ``` |
29 | | //! use smoldot::chain::fork_tree::ForkTree; |
30 | | //! |
31 | | //! let mut tree = ForkTree::new(); |
32 | | //! |
33 | | //! // Add a first node with no parent. In other words, its parent is the finalized block that is |
34 | | //! // virtually there but not managed by the `ForkTree`. |
35 | | //! // Note that the user data (`"foo"` here) can be of any type. It can be used to store |
36 | | //! // additional information on each node. |
37 | | //! let node0 = tree.insert(None, "foo"); |
38 | | //! // Add a second node, child of the first one. |
39 | | //! let node1 = tree.insert(Some(node0), "bar"); |
40 | | //! // Add a third node, child of the second one. |
41 | | //! let node2 = tree.insert(Some(node1), "baz"); |
42 | | //! |
43 | | //! // Removes `node1` and all the nodes that aren't its descendants. |
44 | | //! // This is typically called when `node1` gets finalized. |
45 | | //! // This function returns an iterator containing the blocks that have been removed. |
46 | | //! tree.prune_ancestors(node1); |
47 | | //! |
48 | | //! // Only `node2` remains. |
49 | | //! assert!(tree.get(node0).is_none()); |
50 | | //! assert!(tree.get(node1).is_none()); |
51 | | //! assert!(tree.get(node2).is_some()); |
52 | | //! ``` |
53 | | |
54 | | use core::{fmt, iter}; |
55 | | |
56 | | /// Tree of nodes. Each node contains a value of type `T`. |
57 | | pub struct ForkTree<T> { |
58 | | /// Container storing the nodes. |
59 | | nodes: slab::Slab<Node<T>>, |
60 | | /// Index of the node in the tree without any parent nor previous sibling. |
61 | | first_root: Option<usize>, |
62 | | } |
63 | | |
64 | | struct Node<T> { |
65 | | /// Index within [`ForkTree::nodes`] of the parent of that node. `None` if the node is a root. |
66 | | parent: Option<usize>, |
67 | | /// Index within [`ForkTree::nodes`] of the first child of that node. `None` if no children. |
68 | | first_child: Option<usize>, |
69 | | /// Index within [`ForkTree::nodes`] of the next sibling of that node. `None` if that node is |
70 | | /// the last child of its parent. |
71 | | next_sibling: Option<usize>, |
72 | | /// Index within [`ForkTree::nodes`] of the previous sibling of that node. `None` if the node |
73 | | /// is the first child of its parent. |
74 | | previous_sibling: Option<usize>, |
75 | | /// Always `false`, except temporarily set to `true` during the pruning process on nodes that |
76 | | /// are ancestors of the pruning target. |
77 | | is_prune_target_ancestor: bool, |
78 | | /// Data decided by the external API user. |
79 | | data: T, |
80 | | } |
81 | | |
82 | | impl<T> ForkTree<T> { |
83 | | /// Initializes a new `ForkTree`. |
84 | 3 | pub fn new() -> Self { |
85 | 3 | ForkTree { |
86 | 3 | nodes: slab::Slab::new(), |
87 | 3 | first_root: None, |
88 | 3 | } |
89 | 3 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreelE3newB6_ Line | Count | Source | 84 | 1 | pub fn new() -> Self { | 85 | 1 | ForkTree { | 86 | 1 | nodes: slab::Slab::new(), | 87 | 1 | first_root: None, | 88 | 1 | } | 89 | 1 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeuE3newB6_ Line | Count | Source | 84 | 2 | pub fn new() -> Self { | 85 | 2 | ForkTree { | 86 | 2 | nodes: slab::Slab::new(), | 87 | 2 | first_root: None, | 88 | 2 | } | 89 | 2 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE3newB6_ |
90 | | |
91 | | /// Initializes a new `ForkTree` with a certain pre-allocated capacity. |
92 | 29 | pub fn with_capacity(cap: usize) -> Self { |
93 | 29 | ForkTree { |
94 | 29 | nodes: slab::Slab::with_capacity(cap), |
95 | 29 | first_root: None, |
96 | 29 | } |
97 | 29 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE13with_capacityB6_ Line | Count | Source | 92 | 6 | pub fn with_capacity(cap: usize) -> Self { | 93 | 6 | ForkTree { | 94 | 6 | nodes: slab::Slab::with_capacity(cap), | 95 | 6 | first_root: None, | 96 | 6 | } | 97 | 6 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockuEE13with_capacityB6_ Line | Count | Source | 92 | 2 | pub fn with_capacity(cap: usize) -> Self { | 93 | 2 | ForkTree { | 94 | 2 | nodes: slab::Slab::with_capacity(cap), | 95 | 2 | first_root: None, | 96 | 2 | } | 97 | 2 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE13with_capacityCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE13with_capacityCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE13with_capacityCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE13with_capacityCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE13with_capacityCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE13with_capacityB6_ _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE13with_capacityCsiLzmwikkc22_14json_rpc_basic Line | Count | Source | 92 | 2 | pub fn with_capacity(cap: usize) -> Self { | 93 | 2 | ForkTree { | 94 | 2 | nodes: slab::Slab::with_capacity(cap), | 95 | 2 | first_root: None, | 96 | 2 | } | 97 | 2 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E13with_capacityCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE13with_capacityCscDgN54JpMGG_6author _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE13with_capacityCsibGXYHQB8Ea_25json_rpc_general_requests Line | Count | Source | 92 | 19 | pub fn with_capacity(cap: usize) -> Self { | 93 | 19 | ForkTree { | 94 | 19 | nodes: slab::Slab::with_capacity(cap), | 95 | 19 | first_root: None, | 96 | 19 | } | 97 | 19 | } |
|
98 | | |
99 | | /// Reserves additional capacity for at least `additional` new blocks without allocating. |
100 | 0 | pub fn reserve(&mut self, additional: usize) { |
101 | 0 | self.nodes.reserve(additional); |
102 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE7reserveB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE7reserveB6_ |
103 | | |
104 | | /// Removes all elements in the tree, leaving it empty. |
105 | 0 | pub fn clear(&mut self) { |
106 | 0 | self.nodes.clear(); |
107 | 0 | self.first_root = None; |
108 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE5clearB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE5clearB6_ |
109 | | |
110 | | /// Shrink the capacity of the tree as much as possible. |
111 | 0 | pub fn shrink_to_fit(&mut self) { |
112 | 0 | self.nodes.shrink_to_fit(); |
113 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE13shrink_to_fitB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE13shrink_to_fitB6_ |
114 | | |
115 | | /// Returns true if there isn't any element in the tree. |
116 | 0 | pub fn is_empty(&self) -> bool { |
117 | 0 | self.nodes.is_empty() |
118 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE8is_emptyB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE8is_emptyB6_ |
119 | | |
120 | | /// Returns the number of elements in the tree. |
121 | 0 | pub fn len(&self) -> usize { |
122 | 0 | self.nodes.len() |
123 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE3lenB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE3lenCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE3lenCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE3lenCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE3lenB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3lenCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3lenCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3lenCsibGXYHQB8Ea_25json_rpc_general_requests |
124 | | |
125 | | /// Returns an iterator to all the node values without any specific order. |
126 | 5 | pub fn iter_unordered(&self) -> impl Iterator<Item = (NodeIndex, &T)> { |
127 | 5 | self.nodes.iter().map(|n| (NodeIndex(n.0), &n.1.data)2 ) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE14iter_unordered0B8_ Line | Count | Source | 127 | 2 | self.nodes.iter().map(|n| (NodeIndex(n.0), &n.1.data)) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE14iter_unordered0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE14iter_unordered0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE14iter_unordered0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEEE14iter_unordered0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEE14iter_unordered0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE14iter_unordered0B8_ |
128 | 5 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE14iter_unorderedB6_ Line | Count | Source | 126 | 5 | pub fn iter_unordered(&self) -> impl Iterator<Item = (NodeIndex, &T)> { | 127 | 5 | self.nodes.iter().map(|n| (NodeIndex(n.0), &n.1.data)) | 128 | 5 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE14iter_unorderedCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE14iter_unorderedCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE14iter_unorderedCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE14iter_unorderedCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE14iter_unorderedCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE14iter_unorderedB6_ |
129 | | |
130 | | /// Returns an iterator to all the node values. The returned items are guaranteed to be in an |
131 | | /// order in which the parents are found before their children. |
132 | 5 | pub fn iter_ancestry_order(&'_ self) -> impl Iterator<Item = (NodeIndex, &'_ T)> + '_ { |
133 | 9 | iter::successors(self.first_root.map(NodeIndex), move |n| { |
134 | 9 | self.ancestry_order_next(*n) |
135 | 9 | }) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE19iter_ancestry_order0B8_ Line | Count | Source | 133 | 6 | iter::successors(self.first_root.map(NodeIndex), move |n| { | 134 | 6 | self.ancestry_order_next(*n) | 135 | 6 | }) |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreelE19iter_ancestry_order0B8_ Line | Count | Source | 133 | 3 | iter::successors(self.first_root.map(NodeIndex), move |n| { | 134 | 3 | self.ancestry_order_next(*n) | 135 | 3 | }) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEE19iter_ancestry_order0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEEE19iter_ancestry_order0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE19iter_ancestry_order0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE19iter_ancestry_order0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE19iter_ancestry_order0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE19iter_ancestry_order0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_order0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeAhj20_E19iter_ancestry_order0CsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_order0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_order0CsibGXYHQB8Ea_25json_rpc_general_requests |
136 | 9 | .map(move |idx| (idx, &self.nodes[idx.0].data)) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE19iter_ancestry_orders_0B8_ Line | Count | Source | 136 | 6 | .map(move |idx| (idx, &self.nodes[idx.0].data)) |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreelE19iter_ancestry_orders_0B8_ Line | Count | Source | 136 | 3 | .map(move |idx| (idx, &self.nodes[idx.0].data)) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE19iter_ancestry_orders_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEEE19iter_ancestry_orders_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE19iter_ancestry_orders_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE19iter_ancestry_orders_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEE19iter_ancestry_orders_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE19iter_ancestry_orders_0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_orders_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeAhj20_E19iter_ancestry_orders_0CsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_orders_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_orders_0CsibGXYHQB8Ea_25json_rpc_general_requests |
137 | 5 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE19iter_ancestry_orderB6_ Line | Count | Source | 132 | 4 | pub fn iter_ancestry_order(&'_ self) -> impl Iterator<Item = (NodeIndex, &'_ T)> + '_ { | 133 | 4 | iter::successors(self.first_root.map(NodeIndex), move |n| { | 134 | | self.ancestry_order_next(*n) | 135 | 4 | }) | 136 | 4 | .map(move |idx| (idx, &self.nodes[idx.0].data)) | 137 | 4 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreelE19iter_ancestry_orderB6_ Line | Count | Source | 132 | 1 | pub fn iter_ancestry_order(&'_ self) -> impl Iterator<Item = (NodeIndex, &'_ T)> + '_ { | 133 | 1 | iter::successors(self.first_root.map(NodeIndex), move |n| { | 134 | | self.ancestry_order_next(*n) | 135 | 1 | }) | 136 | 1 | .map(move |idx| (idx, &self.nodes[idx.0].data)) | 137 | 1 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE19iter_ancestry_orderCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE19iter_ancestry_orderCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE19iter_ancestry_orderCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE19iter_ancestry_orderCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE19iter_ancestry_orderCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE19iter_ancestry_orderB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_orderCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E19iter_ancestry_orderCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_orderCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19iter_ancestry_orderCsibGXYHQB8Ea_25json_rpc_general_requests |
138 | | |
139 | 9 | fn ancestry_order_next(&self, node_index: NodeIndex) -> Option<NodeIndex> { |
140 | 9 | debug_assert!(!self.nodes[node_index.0].is_prune_target_ancestor); |
141 | | |
142 | 9 | if let Some(idx4 ) = self.nodes[node_index.0].first_child { |
143 | 4 | debug_assert_eq!(self.nodes[idx].parent, Some(node_index.0)); |
144 | 4 | return Some(NodeIndex(idx)); |
145 | 5 | } |
146 | | |
147 | 5 | if let Some(idx1 ) = self.nodes[node_index.0].next_sibling { |
148 | 1 | debug_assert_eq!(self.nodes[idx].previous_sibling, Some(node_index.0)); |
149 | 1 | debug_assert_eq!(self.nodes[idx].parent, self.nodes[node_index.0].parent); |
150 | 1 | return Some(NodeIndex(idx)); |
151 | 4 | } |
152 | 4 | |
153 | 4 | let mut return_value = self.nodes[node_index.0].parent; |
154 | 8 | while let Some(idx4 ) = return_value { |
155 | 4 | if let Some(next_sibling0 ) = self.nodes[idx].next_sibling { |
156 | 0 | debug_assert_eq!(self.nodes[next_sibling].previous_sibling, Some(idx)); |
157 | 0 | debug_assert_eq!(self.nodes[next_sibling].parent, self.nodes[idx].parent); |
158 | 0 | return Some(NodeIndex(next_sibling)); |
159 | 4 | } |
160 | 4 | return_value = self.nodes[idx].parent; |
161 | | } |
162 | 4 | return_value.map(NodeIndex) |
163 | 9 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE19ancestry_order_nextB6_ Line | Count | Source | 139 | 6 | fn ancestry_order_next(&self, node_index: NodeIndex) -> Option<NodeIndex> { | 140 | 6 | debug_assert!(!self.nodes[node_index.0].is_prune_target_ancestor); | 141 | | | 142 | 6 | if let Some(idx3 ) = self.nodes[node_index.0].first_child { | 143 | 3 | debug_assert_eq!(self.nodes[idx].parent, Some(node_index.0)); | 144 | 3 | return Some(NodeIndex(idx)); | 145 | 3 | } | 146 | | | 147 | 3 | if let Some(idx0 ) = self.nodes[node_index.0].next_sibling { | 148 | 0 | debug_assert_eq!(self.nodes[idx].previous_sibling, Some(node_index.0)); | 149 | 0 | debug_assert_eq!(self.nodes[idx].parent, self.nodes[node_index.0].parent); | 150 | 0 | return Some(NodeIndex(idx)); | 151 | 3 | } | 152 | 3 | | 153 | 3 | let mut return_value = self.nodes[node_index.0].parent; | 154 | 6 | while let Some(idx3 ) = return_value { | 155 | 3 | if let Some(next_sibling0 ) = self.nodes[idx].next_sibling { | 156 | 0 | debug_assert_eq!(self.nodes[next_sibling].previous_sibling, Some(idx)); | 157 | 0 | debug_assert_eq!(self.nodes[next_sibling].parent, self.nodes[idx].parent); | 158 | 0 | return Some(NodeIndex(next_sibling)); | 159 | 3 | } | 160 | 3 | return_value = self.nodes[idx].parent; | 161 | | } | 162 | 3 | return_value.map(NodeIndex) | 163 | 6 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreelE19ancestry_order_nextB6_ Line | Count | Source | 139 | 3 | fn ancestry_order_next(&self, node_index: NodeIndex) -> Option<NodeIndex> { | 140 | 3 | debug_assert!(!self.nodes[node_index.0].is_prune_target_ancestor); | 141 | | | 142 | 3 | if let Some(idx1 ) = self.nodes[node_index.0].first_child { | 143 | 1 | debug_assert_eq!(self.nodes[idx].parent, Some(node_index.0)); | 144 | 1 | return Some(NodeIndex(idx)); | 145 | 2 | } | 146 | | | 147 | 2 | if let Some(idx1 ) = self.nodes[node_index.0].next_sibling { | 148 | 1 | debug_assert_eq!(self.nodes[idx].previous_sibling, Some(node_index.0)); | 149 | 1 | debug_assert_eq!(self.nodes[idx].parent, self.nodes[node_index.0].parent); | 150 | 1 | return Some(NodeIndex(idx)); | 151 | 1 | } | 152 | 1 | | 153 | 1 | let mut return_value = self.nodes[node_index.0].parent; | 154 | 2 | while let Some(idx1 ) = return_value { | 155 | 1 | if let Some(next_sibling0 ) = self.nodes[idx].next_sibling { | 156 | 0 | debug_assert_eq!(self.nodes[next_sibling].previous_sibling, Some(idx)); | 157 | 0 | debug_assert_eq!(self.nodes[next_sibling].parent, self.nodes[idx].parent); | 158 | 0 | return Some(NodeIndex(next_sibling)); | 159 | 1 | } | 160 | 1 | return_value = self.nodes[idx].parent; | 161 | | } | 162 | 1 | return_value.map(NodeIndex) | 163 | 3 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE19ancestry_order_nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE19ancestry_order_nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE19ancestry_order_nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE19ancestry_order_nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE19ancestry_order_nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE19ancestry_order_nextB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19ancestry_order_nextCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E19ancestry_order_nextCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19ancestry_order_nextCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE19ancestry_order_nextCsibGXYHQB8Ea_25json_rpc_general_requests |
164 | | |
165 | | /// Returns `true` if the given [`NodeIndex`] is valid. |
166 | 0 | pub fn contains(&self, index: NodeIndex) -> bool { |
167 | 0 | self.nodes.contains(index.0) |
168 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE8containsB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE8containsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE8containsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE8containsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE8containsB6_ |
169 | | |
170 | | /// Returns the value of the node with the given index. |
171 | 75 | pub fn get(&self, index: NodeIndex) -> Option<&T> { |
172 | 75 | self.nodes.get(index.0).map(|n| &n.data70 ) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockuEE3get0B8_ Line | Count | Source | 172 | 6 | self.nodes.get(index.0).map(|n| &n.data) |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE3get0B8_ Line | Count | Source | 172 | 61 | self.nodes.get(index.0).map(|n| &n.data) |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreelE3get0B8_ Line | Count | Source | 172 | 3 | self.nodes.get(index.0).map(|n| &n.data) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE3get0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEEE3get0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEE3get0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE3get0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE3get0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE3get0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3get0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeAhj20_E3get0CsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3get0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3get0CsibGXYHQB8Ea_25json_rpc_general_requests |
173 | 75 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockuEE3getB6_ Line | Count | Source | 171 | 6 | pub fn get(&self, index: NodeIndex) -> Option<&T> { | 172 | 6 | self.nodes.get(index.0).map(|n| &n.data) | 173 | 6 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE3getB6_ Line | Count | Source | 171 | 62 | pub fn get(&self, index: NodeIndex) -> Option<&T> { | 172 | 62 | self.nodes.get(index.0).map(|n| &n.data) | 173 | 62 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreelE3getB6_ Line | Count | Source | 171 | 7 | pub fn get(&self, index: NodeIndex) -> Option<&T> { | 172 | 7 | self.nodes.get(index.0).map(|n| &n.data) | 173 | 7 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE3getCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE3getCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE3getCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE3getCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE3getCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE3getB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3getCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E3getCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3getCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE3getCsibGXYHQB8Ea_25json_rpc_general_requests |
174 | | |
175 | | /// Returns the value of the node with the given index. |
176 | 8 | pub fn get_mut(&mut self, index: NodeIndex) -> Option<&mut T> { |
177 | 8 | self.nodes.get_mut(index.0).map(|n| &mut n.data) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE7get_mut0B8_ Line | Count | Source | 177 | 8 | self.nodes.get_mut(index.0).map(|n| &mut n.data) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE7get_mut0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEEE7get_mut0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEE7get_mut0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE7get_mut0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE7get_mut0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE7get_mut0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE7get_mut0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE7get_mut0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE7get_mut0CsibGXYHQB8Ea_25json_rpc_general_requests |
178 | 8 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE7get_mutB6_ Line | Count | Source | 176 | 8 | pub fn get_mut(&mut self, index: NodeIndex) -> Option<&mut T> { | 177 | 8 | self.nodes.get_mut(index.0).map(|n| &mut n.data) | 178 | 8 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE7get_mutCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE7get_mutCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE7get_mutCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE7get_mutCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE7get_mutCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE7get_mutB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE7get_mutCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE7get_mutCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE7get_mutCsibGXYHQB8Ea_25json_rpc_general_requests |
179 | | |
180 | | /// Modifies all the block user datas and returns a new map. |
181 | | /// |
182 | | /// The returned tree keeps the same [`NodeIndex`]es as `self`. |
183 | 0 | pub fn map<U>(self, mut map: impl FnMut(T) -> U) -> ForkTree<U> { |
184 | 0 | ForkTree { |
185 | 0 | nodes: self |
186 | 0 | .nodes |
187 | 0 | .into_iter() |
188 | 0 | .map(|(index, node)| { |
189 | 0 | let node = Node { |
190 | 0 | parent: node.parent, |
191 | 0 | first_child: node.first_child, |
192 | 0 | next_sibling: node.next_sibling, |
193 | 0 | previous_sibling: node.previous_sibling, |
194 | 0 | is_prune_target_ancestor: node.is_prune_target_ancestor, |
195 | 0 | data: map(node.data), |
196 | 0 | }; |
197 | 0 |
|
198 | 0 | (index, node) |
199 | 0 | }) Unexecuted instantiation: _RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreepE3mapppE0B9_ Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_8ForkTreeINtNtB7_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1u_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB23_7RuntimeEEEE3mapIB11_B1q_B21_B3i_ENCINvMB13_INtB13_9AsyncTreeB1q_B21_B2V_E22map_async_op_user_dataB3i_NCNCINvB23_14run_backgroundNtNtCsDDUKWWCHAU_18smoldot_light_wasm8platform11PlatformRefE0si_0E0E0B65_ Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_8ForkTreepE3mapppE0B9_ |
200 | 0 | .collect(), |
201 | 0 | first_root: self.first_root, |
202 | 0 | } |
203 | 0 | } Unexecuted instantiation: _RINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB3_8ForkTreepE3mapppEB7_ Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB3_8ForkTreeINtNtB5_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1s_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB21_7RuntimeEEEE3mapIBZ_B1o_B1Z_B3g_ENCINvMB11_INtB11_9AsyncTreeB1o_B1Z_B2T_E22map_async_op_user_dataB3g_NCNCINvB21_14run_backgroundNtNtCsDDUKWWCHAU_18smoldot_light_wasm8platform11PlatformRefE0si_0E0EB62_ Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB3_8ForkTreepE3mapppEB7_ |
204 | | |
205 | | /// Returns the ancestors of the given node. The iterator is empty if the node doesn't have |
206 | | /// any parent. |
207 | | /// |
208 | | /// # Panic |
209 | | /// |
210 | | /// Panics if the [`NodeIndex`] is invalid. |
211 | | /// |
212 | 0 | pub fn ancestors(&'_ self, node: NodeIndex) -> impl Iterator<Item = NodeIndex> + '_ { |
213 | 0 | iter::successors(Some(node), move |n| self.nodes[n.0].parent.map(NodeIndex)).skip(1) Unexecuted instantiation: _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreepE9ancestors0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE9ancestors0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE9ancestors0B8_ |
214 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE9ancestorsB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE9ancestorsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE9ancestorsB6_ |
215 | | |
216 | | /// Returns the parent of the given node. Returns `None` if the node doesn't have any parent. |
217 | | /// |
218 | | /// # Panic |
219 | | /// |
220 | | /// Panics if the [`NodeIndex`] is invalid. |
221 | | /// |
222 | 0 | pub fn parent(&self, node: NodeIndex) -> Option<NodeIndex> { |
223 | 0 | self.nodes[node.0].parent.map(NodeIndex) |
224 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE6parentB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE6parentCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE6parentCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE6parentCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE6parentB6_ |
225 | | |
226 | | /// Returns the list of children that have the given node as parent. |
227 | | /// |
228 | | /// # Panic |
229 | | /// |
230 | | /// Panics if the [`NodeIndex`] is invalid. |
231 | | /// |
232 | 0 | pub fn children(&'_ self, node: Option<NodeIndex>) -> impl Iterator<Item = NodeIndex> + '_ { |
233 | 0 | let first = match node { |
234 | 0 | Some(n) => self.nodes[n.0].first_child, |
235 | 0 | None => self.first_root, |
236 | | }; |
237 | | |
238 | 0 | iter::successors(first, move |n| self.nodes[*n].next_sibling).map(NodeIndex) Unexecuted instantiation: _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreepE8children0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE8children0B8_ |
239 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreepE8childrenB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE8childrenB6_ |
240 | | |
241 | | /// Removes from the tree: |
242 | | /// |
243 | | /// - The node passed as parameter. |
244 | | /// - The ancestors of the node passed as parameter. |
245 | | /// - Any node not a descendant of the node passed as parameter. |
246 | | /// |
247 | | /// Returns an iterator containing the removed elements. |
248 | | /// All elements are removed from the tree even if the returned iterator is dropped eagerly. |
249 | | /// |
250 | | /// Elements are returned in an unspecified order. However, each element yielded is guaranteed |
251 | | /// to be yielded *before* its parent gets yielded. |
252 | | /// This can be more or less called "reverse hierarchical order". |
253 | | /// |
254 | | /// In other words, doing `prune_ancestors(...).filter(|n| n.is_prune_target_ancestor)` is |
255 | | /// guaranteed to return the elements in the same order as [`ForkTree::node_to_root_path`] |
256 | | /// does. |
257 | | /// |
258 | | /// # Panic |
259 | | /// |
260 | | /// Panics if the [`NodeIndex`] is invalid. |
261 | | /// |
262 | 2 | pub fn prune_ancestors(&mut self, node_index: NodeIndex) -> PruneAncestorsIter<T> { |
263 | 2 | self.prune_ancestors_inner(node_index, false) |
264 | 2 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE15prune_ancestorsB6_ Line | Count | Source | 262 | 1 | pub fn prune_ancestors(&mut self, node_index: NodeIndex) -> PruneAncestorsIter<T> { | 263 | 1 | self.prune_ancestors_inner(node_index, false) | 264 | 1 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreelE15prune_ancestorsB6_ Line | Count | Source | 262 | 1 | pub fn prune_ancestors(&mut self, node_index: NodeIndex) -> PruneAncestorsIter<T> { | 263 | 1 | self.prune_ancestors_inner(node_index, false) | 264 | 1 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE15prune_ancestorsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE15prune_ancestorsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE15prune_ancestorsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE15prune_ancestorsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE15prune_ancestorsCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE15prune_ancestorsB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE15prune_ancestorsCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E15prune_ancestorsCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE15prune_ancestorsCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE15prune_ancestorsCsibGXYHQB8Ea_25json_rpc_general_requests |
265 | | |
266 | | /// Removes from the tree any node that isn't either an ancestor or a descendant of the target |
267 | | /// node. |
268 | | /// |
269 | | /// This function is similar to [`ForkTree::prune_ancestors`], except that all nodes returned |
270 | | /// by the iterator are guaranteed to have [`PrunedNode::is_prune_target_ancestor`] equal |
271 | | /// to `false`. |
272 | | /// |
273 | | /// # Panic |
274 | | /// |
275 | | /// Panics if the [`NodeIndex`] is invalid. |
276 | | /// |
277 | 3 | pub fn prune_uncles(&mut self, node_index: NodeIndex) -> PruneAncestorsIter<T> { |
278 | 3 | self.prune_ancestors_inner(node_index, true) |
279 | 3 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE12prune_unclesB6_ Line | Count | Source | 277 | 3 | pub fn prune_uncles(&mut self, node_index: NodeIndex) -> PruneAncestorsIter<T> { | 278 | 3 | self.prune_ancestors_inner(node_index, true) | 279 | 3 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE12prune_unclesCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE12prune_unclesB6_ |
280 | | |
281 | 5 | fn prune_ancestors_inner( |
282 | 5 | &mut self, |
283 | 5 | node_index: NodeIndex, |
284 | 5 | uncles_only: bool, |
285 | 5 | ) -> PruneAncestorsIter<T> { |
286 | 5 | let iter = self.first_root.unwrap(); |
287 | 5 | |
288 | 5 | // `first_root` is updated ahead of the removal of the nodes. The update strategy is as |
289 | 5 | // follows: |
290 | 5 | // - If `uncles_only`, then it becomes the oldest ancestor of the target node. This is |
291 | 5 | // done in the loop below at the same time as marking node as `is_prune_target_ancestor`. |
292 | 5 | // - If `!uncles_only`, then it becomes the first child of the target node. |
293 | 5 | |
294 | 5 | // Set `is_prune_target_ancestor` to true for `node_index` and all its ancestors. |
295 | 5 | { |
296 | 5 | let mut node = node_index.0; |
297 | 9 | loop { |
298 | 9 | debug_assert!(!self.nodes[node].is_prune_target_ancestor); |
299 | 9 | self.nodes[node].is_prune_target_ancestor = true; |
300 | 9 | |
301 | 9 | if uncles_only { |
302 | 6 | self.first_root = Some(node); |
303 | 6 | }3 |
304 | | |
305 | 9 | node = match self.nodes[node].parent { |
306 | 4 | Some(n) => n, |
307 | 5 | None => break, |
308 | 5 | } |
309 | 5 | } |
310 | 5 | } |
311 | 5 | |
312 | 5 | if !uncles_only { |
313 | 2 | self.first_root = self.nodes[node_index.0].first_child; |
314 | 3 | } |
315 | | |
316 | 5 | PruneAncestorsIter { |
317 | 5 | finished: false, |
318 | 5 | tree: self, |
319 | 5 | uncles_only, |
320 | 5 | new_final: node_index, |
321 | 5 | iter, |
322 | 5 | traversing_up: false, |
323 | 5 | } |
324 | 5 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE21prune_ancestors_innerB6_ Line | Count | Source | 281 | 4 | fn prune_ancestors_inner( | 282 | 4 | &mut self, | 283 | 4 | node_index: NodeIndex, | 284 | 4 | uncles_only: bool, | 285 | 4 | ) -> PruneAncestorsIter<T> { | 286 | 4 | let iter = self.first_root.unwrap(); | 287 | 4 | | 288 | 4 | // `first_root` is updated ahead of the removal of the nodes. The update strategy is as | 289 | 4 | // follows: | 290 | 4 | // - If `uncles_only`, then it becomes the oldest ancestor of the target node. This is | 291 | 4 | // done in the loop below at the same time as marking node as `is_prune_target_ancestor`. | 292 | 4 | // - If `!uncles_only`, then it becomes the first child of the target node. | 293 | 4 | | 294 | 4 | // Set `is_prune_target_ancestor` to true for `node_index` and all its ancestors. | 295 | 4 | { | 296 | 4 | let mut node = node_index.0; | 297 | 7 | loop { | 298 | 7 | debug_assert!(!self.nodes[node].is_prune_target_ancestor); | 299 | 7 | self.nodes[node].is_prune_target_ancestor = true; | 300 | 7 | | 301 | 7 | if uncles_only { | 302 | 6 | self.first_root = Some(node); | 303 | 6 | }1 | 304 | | | 305 | 7 | node = match self.nodes[node].parent { | 306 | 3 | Some(n) => n, | 307 | 4 | None => break, | 308 | 4 | } | 309 | 4 | } | 310 | 4 | } | 311 | 4 | | 312 | 4 | if !uncles_only { | 313 | 1 | self.first_root = self.nodes[node_index.0].first_child; | 314 | 3 | } | 315 | | | 316 | 4 | PruneAncestorsIter { | 317 | 4 | finished: false, | 318 | 4 | tree: self, | 319 | 4 | uncles_only, | 320 | 4 | new_final: node_index, | 321 | 4 | iter, | 322 | 4 | traversing_up: false, | 323 | 4 | } | 324 | 4 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreelE21prune_ancestors_innerB6_ Line | Count | Source | 281 | 1 | fn prune_ancestors_inner( | 282 | 1 | &mut self, | 283 | 1 | node_index: NodeIndex, | 284 | 1 | uncles_only: bool, | 285 | 1 | ) -> PruneAncestorsIter<T> { | 286 | 1 | let iter = self.first_root.unwrap(); | 287 | 1 | | 288 | 1 | // `first_root` is updated ahead of the removal of the nodes. The update strategy is as | 289 | 1 | // follows: | 290 | 1 | // - If `uncles_only`, then it becomes the oldest ancestor of the target node. This is | 291 | 1 | // done in the loop below at the same time as marking node as `is_prune_target_ancestor`. | 292 | 1 | // - If `!uncles_only`, then it becomes the first child of the target node. | 293 | 1 | | 294 | 1 | // Set `is_prune_target_ancestor` to true for `node_index` and all its ancestors. | 295 | 1 | { | 296 | 1 | let mut node = node_index.0; | 297 | 2 | loop { | 298 | 2 | debug_assert!(!self.nodes[node].is_prune_target_ancestor); | 299 | 2 | self.nodes[node].is_prune_target_ancestor = true; | 300 | 2 | | 301 | 2 | if uncles_only { | 302 | 0 | self.first_root = Some(node); | 303 | 2 | } | 304 | | | 305 | 2 | node = match self.nodes[node].parent { | 306 | 1 | Some(n) => n, | 307 | 1 | None => break, | 308 | 1 | } | 309 | 1 | } | 310 | 1 | } | 311 | 1 | | 312 | 1 | if !uncles_only { | 313 | 1 | self.first_root = self.nodes[node_index.0].first_child; | 314 | 1 | }0 | 315 | | | 316 | 1 | PruneAncestorsIter { | 317 | 1 | finished: false, | 318 | 1 | tree: self, | 319 | 1 | uncles_only, | 320 | 1 | new_final: node_index, | 321 | 1 | iter, | 322 | 1 | traversing_up: false, | 323 | 1 | } | 324 | 1 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE21prune_ancestors_innerCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE21prune_ancestors_innerCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE21prune_ancestors_innerCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE21prune_ancestors_innerCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE21prune_ancestors_innerCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE21prune_ancestors_innerB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE21prune_ancestors_innerCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E21prune_ancestors_innerCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE21prune_ancestors_innerCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE21prune_ancestors_innerCsibGXYHQB8Ea_25json_rpc_general_requests |
325 | | |
326 | | /// Returns the common ancestor between `node1` and `node2`, if any is known. |
327 | | /// |
328 | | /// # Panic |
329 | | /// |
330 | | /// Panics if one of the [`NodeIndex`]s is invalid. |
331 | | /// |
332 | 14 | pub fn common_ancestor(&self, node1: NodeIndex, node2: NodeIndex) -> Option<NodeIndex> { |
333 | 14 | let dist_to_root1 = self.node_to_root_path(node1).count(); |
334 | 14 | let dist_to_root2 = self.node_to_root_path(node2).count(); |
335 | 14 | |
336 | 14 | let mut iter1 = self |
337 | 14 | .node_to_root_path(node1) |
338 | 14 | .skip(dist_to_root1.saturating_sub(dist_to_root2)); |
339 | 14 | let mut iter2 = self |
340 | 14 | .node_to_root_path(node2) |
341 | 14 | .skip(dist_to_root2.saturating_sub(dist_to_root1)); |
342 | | |
343 | | loop { |
344 | 20 | match (iter1.next(), iter2.next()) { |
345 | 16 | (Some(a), Some(b10 )) if a == b => return Some(a)10 , |
346 | 6 | (Some(_), Some(_)) => continue, |
347 | 4 | (None, None) => return None, |
348 | 0 | _ => unreachable!(), |
349 | | } |
350 | | } |
351 | 14 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE15common_ancestorB6_ Line | Count | Source | 332 | 10 | pub fn common_ancestor(&self, node1: NodeIndex, node2: NodeIndex) -> Option<NodeIndex> { | 333 | 10 | let dist_to_root1 = self.node_to_root_path(node1).count(); | 334 | 10 | let dist_to_root2 = self.node_to_root_path(node2).count(); | 335 | 10 | | 336 | 10 | let mut iter1 = self | 337 | 10 | .node_to_root_path(node1) | 338 | 10 | .skip(dist_to_root1.saturating_sub(dist_to_root2)); | 339 | 10 | let mut iter2 = self | 340 | 10 | .node_to_root_path(node2) | 341 | 10 | .skip(dist_to_root2.saturating_sub(dist_to_root1)); | 342 | | | 343 | | loop { | 344 | 12 | match (iter1.next(), iter2.next()) { | 345 | 10 | (Some(a), Some(b8 )) if a == b => return Some(a)8 , | 346 | 2 | (Some(_), Some(_)) => continue, | 347 | 2 | (None, None) => return None, | 348 | 0 | _ => unreachable!(), | 349 | | } | 350 | | } | 351 | 10 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeuE15common_ancestorB6_ Line | Count | Source | 332 | 4 | pub fn common_ancestor(&self, node1: NodeIndex, node2: NodeIndex) -> Option<NodeIndex> { | 333 | 4 | let dist_to_root1 = self.node_to_root_path(node1).count(); | 334 | 4 | let dist_to_root2 = self.node_to_root_path(node2).count(); | 335 | 4 | | 336 | 4 | let mut iter1 = self | 337 | 4 | .node_to_root_path(node1) | 338 | 4 | .skip(dist_to_root1.saturating_sub(dist_to_root2)); | 339 | 4 | let mut iter2 = self | 340 | 4 | .node_to_root_path(node2) | 341 | 4 | .skip(dist_to_root2.saturating_sub(dist_to_root1)); | 342 | | | 343 | | loop { | 344 | 8 | match (iter1.next(), iter2.next()) { | 345 | 6 | (Some(a), Some(b2 )) if a == b => return Some(a)2 , | 346 | 4 | (Some(_), Some(_)) => continue, | 347 | 2 | (None, None) => return None, | 348 | 0 | _ => unreachable!(), | 349 | | } | 350 | | } | 351 | 4 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE15common_ancestorCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE15common_ancestorB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E15common_ancestorCsiUjFBJteJ7x_17smoldot_full_node |
352 | | |
353 | | /// Returns true if `maybe_ancestor` is an ancestor of `maybe_descendant`. Also returns `true` |
354 | | /// if the two [`NodeIndex`] are equal. |
355 | | /// |
356 | | /// # Panic |
357 | | /// |
358 | | /// Panics if one of the [`NodeIndex`]s is invalid. |
359 | | /// |
360 | 6 | pub fn is_ancestor(&self, maybe_ancestor: NodeIndex, maybe_descendant: NodeIndex) -> bool { |
361 | 6 | // Do this check separately, otherwise the code below would successfully return `true` |
362 | 6 | // if `maybe_ancestor` and `descendant` are invalid but equal. |
363 | 6 | assert!(self.nodes.contains(maybe_descendant.0)); |
364 | | |
365 | 6 | let mut iter = maybe_descendant.0; |
366 | | loop { |
367 | 6 | if iter == maybe_ancestor.0 { |
368 | 6 | return true; |
369 | 0 | } |
370 | 0 |
|
371 | 0 | iter = match self.nodes[iter].parent { |
372 | 0 | Some(p) => p, |
373 | 0 | None => return false, |
374 | | }; |
375 | | } |
376 | 6 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE11is_ancestorB6_ Line | Count | Source | 360 | 6 | pub fn is_ancestor(&self, maybe_ancestor: NodeIndex, maybe_descendant: NodeIndex) -> bool { | 361 | 6 | // Do this check separately, otherwise the code below would successfully return `true` | 362 | 6 | // if `maybe_ancestor` and `descendant` are invalid but equal. | 363 | 6 | assert!(self.nodes.contains(maybe_descendant.0)); | 364 | | | 365 | 6 | let mut iter = maybe_descendant.0; | 366 | | loop { | 367 | 6 | if iter == maybe_ancestor.0 { | 368 | 6 | return true; | 369 | 0 | } | 370 | 0 |
| 371 | 0 | iter = match self.nodes[iter].parent { | 372 | 0 | Some(p) => p, | 373 | 0 | None => return false, | 374 | | }; | 375 | | } | 376 | 6 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE11is_ancestorCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE11is_ancestorCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE11is_ancestorCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE11is_ancestorCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE11is_ancestorCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE11is_ancestorB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE11is_ancestorCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE11is_ancestorCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE11is_ancestorCsibGXYHQB8Ea_25json_rpc_general_requests |
377 | | |
378 | | /// Returns two iterators: the first iterator enumerates the nodes from `node1` to the common |
379 | | /// ancestor of `node1` and `node2`. The second iterator enumerates the nodes from that common |
380 | | /// ancestor to `node2`. The common ancestor isn't included in either iterator. If `node1` and |
381 | | /// `node2` are equal then both iterators are empty, otherwise `node1` is always included in |
382 | | /// the first iterator and `node2` always included in the second iterator. |
383 | | /// |
384 | | /// # Panic |
385 | | /// |
386 | | /// Panics if one of the [`NodeIndex`]s is invalid. |
387 | | /// |
388 | 12 | pub fn ascend_and_descend( |
389 | 12 | &'_ self, |
390 | 12 | node1: NodeIndex, |
391 | 12 | node2: NodeIndex, |
392 | 12 | ) -> ( |
393 | 12 | impl Iterator<Item = NodeIndex> + Clone + '_, |
394 | 12 | impl Iterator<Item = NodeIndex> + Clone + '_, |
395 | 12 | ) { |
396 | 12 | let common_ancestor = self.common_ancestor(node1, node2); |
397 | 12 | |
398 | 12 | let iter1 = self |
399 | 12 | .node_to_root_path(node1) |
400 | 13 | .take_while(move |v| Some(*v) != common_ancestor)12 ; _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeuE18ascend_and_descend0B8_ Line | Count | Source | 400 | 3 | .take_while(move |v| Some(*v) != common_ancestor); |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE18ascend_and_descend0B8_ Line | Count | Source | 400 | 10 | .take_while(move |v| Some(*v) != common_ancestor); |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE18ascend_and_descend0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE18ascend_and_descend0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeAhj20_E18ascend_and_descend0CsiUjFBJteJ7x_17smoldot_full_node |
401 | | |
402 | 12 | let iter2 = if let Some(common_ancestor9 ) = common_ancestor { |
403 | 9 | either::Left( |
404 | 9 | self.root_to_node_path(node2) |
405 | 16 | .skip_while(move |v| *v != common_ancestor) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeuE18ascend_and_descends_0B8_ Line | Count | Source | 405 | 1 | .skip_while(move |v| *v != common_ancestor) |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE18ascend_and_descends_0B8_ Line | Count | Source | 405 | 15 | .skip_while(move |v| *v != common_ancestor) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE18ascend_and_descends_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE18ascend_and_descends_0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeAhj20_E18ascend_and_descends_0CsiUjFBJteJ7x_17smoldot_full_node |
406 | 9 | .skip(1), |
407 | 9 | ) |
408 | | } else { |
409 | 3 | either::Right(self.root_to_node_path(node2)) |
410 | | }; |
411 | | |
412 | 12 | (iter1, iter2) |
413 | 12 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE18ascend_and_descendB6_ Line | Count | Source | 388 | 10 | pub fn ascend_and_descend( | 389 | 10 | &'_ self, | 390 | 10 | node1: NodeIndex, | 391 | 10 | node2: NodeIndex, | 392 | 10 | ) -> ( | 393 | 10 | impl Iterator<Item = NodeIndex> + Clone + '_, | 394 | 10 | impl Iterator<Item = NodeIndex> + Clone + '_, | 395 | 10 | ) { | 396 | 10 | let common_ancestor = self.common_ancestor(node1, node2); | 397 | 10 | | 398 | 10 | let iter1 = self | 399 | 10 | .node_to_root_path(node1) | 400 | 10 | .take_while(move |v| Some(*v) != common_ancestor); | 401 | | | 402 | 10 | let iter2 = if let Some(common_ancestor8 ) = common_ancestor { | 403 | 8 | either::Left( | 404 | 8 | self.root_to_node_path(node2) | 405 | 8 | .skip_while(move |v| *v != common_ancestor) | 406 | 8 | .skip(1), | 407 | 8 | ) | 408 | | } else { | 409 | 2 | either::Right(self.root_to_node_path(node2)) | 410 | | }; | 411 | | | 412 | 10 | (iter1, iter2) | 413 | 10 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeuE18ascend_and_descendB6_ Line | Count | Source | 388 | 2 | pub fn ascend_and_descend( | 389 | 2 | &'_ self, | 390 | 2 | node1: NodeIndex, | 391 | 2 | node2: NodeIndex, | 392 | 2 | ) -> ( | 393 | 2 | impl Iterator<Item = NodeIndex> + Clone + '_, | 394 | 2 | impl Iterator<Item = NodeIndex> + Clone + '_, | 395 | 2 | ) { | 396 | 2 | let common_ancestor = self.common_ancestor(node1, node2); | 397 | 2 | | 398 | 2 | let iter1 = self | 399 | 2 | .node_to_root_path(node1) | 400 | 2 | .take_while(move |v| Some(*v) != common_ancestor); | 401 | | | 402 | 2 | let iter2 = if let Some(common_ancestor1 ) = common_ancestor { | 403 | 1 | either::Left( | 404 | 1 | self.root_to_node_path(node2) | 405 | 1 | .skip_while(move |v| *v != common_ancestor) | 406 | 1 | .skip(1), | 407 | 1 | ) | 408 | | } else { | 409 | 1 | either::Right(self.root_to_node_path(node2)) | 410 | | }; | 411 | | | 412 | 2 | (iter1, iter2) | 413 | 2 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE18ascend_and_descendCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE18ascend_and_descendB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E18ascend_and_descendCsiUjFBJteJ7x_17smoldot_full_node |
414 | | |
415 | | /// Enumerates all the nodes, starting from the given node, to the root. Each element |
416 | | /// returned by the iterator is a parent of the previous one. The iterator does include the |
417 | | /// node itself. |
418 | | /// |
419 | | /// # Panic |
420 | | /// |
421 | | /// Panics if the [`NodeIndex`] is invalid. |
422 | | /// |
423 | 141 | pub fn node_to_root_path( |
424 | 141 | &'_ self, |
425 | 141 | node_index: NodeIndex, |
426 | 141 | ) -> impl Iterator<Item = NodeIndex> + Clone + '_ { |
427 | 244 | iter::successors(Some(node_index), move |n| { |
428 | 244 | self.nodes[n.0].parent.map(NodeIndex) |
429 | 244 | }) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreelE17node_to_root_path0B8_ Line | Count | Source | 427 | 16 | iter::successors(Some(node_index), move |n| { | 428 | 16 | self.nodes[n.0].parent.map(NodeIndex) | 429 | 16 | }) |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeuE17node_to_root_path0B8_ Line | Count | Source | 427 | 34 | iter::successors(Some(node_index), move |n| { | 428 | 34 | self.nodes[n.0].parent.map(NodeIndex) | 429 | 34 | }) |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE17node_to_root_path0B8_ Line | Count | Source | 427 | 194 | iter::successors(Some(node_index), move |n| { | 428 | 194 | self.nodes[n.0].parent.map(NodeIndex) | 429 | 194 | }) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE17node_to_root_path0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE17node_to_root_path0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEEE17node_to_root_path0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEE17node_to_root_path0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE17node_to_root_path0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeAhj20_E17node_to_root_path0CsiUjFBJteJ7x_17smoldot_full_node |
430 | 141 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeuE17node_to_root_pathB6_ Line | Count | Source | 423 | 23 | pub fn node_to_root_path( | 424 | 23 | &'_ self, | 425 | 23 | node_index: NodeIndex, | 426 | 23 | ) -> impl Iterator<Item = NodeIndex> + Clone + '_ { | 427 | 23 | iter::successors(Some(node_index), move |n| { | 428 | | self.nodes[n.0].parent.map(NodeIndex) | 429 | 23 | }) | 430 | 23 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE17node_to_root_pathB6_ Line | Count | Source | 423 | 112 | pub fn node_to_root_path( | 424 | 112 | &'_ self, | 425 | 112 | node_index: NodeIndex, | 426 | 112 | ) -> impl Iterator<Item = NodeIndex> + Clone + '_ { | 427 | 112 | iter::successors(Some(node_index), move |n| { | 428 | | self.nodes[n.0].parent.map(NodeIndex) | 429 | 112 | }) | 430 | 112 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreelE17node_to_root_pathB6_ Line | Count | Source | 423 | 6 | pub fn node_to_root_path( | 424 | 6 | &'_ self, | 425 | 6 | node_index: NodeIndex, | 426 | 6 | ) -> impl Iterator<Item = NodeIndex> + Clone + '_ { | 427 | 6 | iter::successors(Some(node_index), move |n| { | 428 | | self.nodes[n.0].parent.map(NodeIndex) | 429 | 6 | }) | 430 | 6 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE17node_to_root_pathCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE17node_to_root_pathCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE17node_to_root_pathCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE17node_to_root_pathCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE17node_to_root_pathB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E17node_to_root_pathCsiUjFBJteJ7x_17smoldot_full_node |
431 | | |
432 | | /// Same as [`ForkTree::node_to_root_path`], but gives the path in the reverse order. |
433 | | /// |
434 | | /// # Panic |
435 | | /// |
436 | | /// Panics if the [`NodeIndex`] is invalid. |
437 | | /// |
438 | 24 | pub fn root_to_node_path( |
439 | 24 | &'_ self, |
440 | 24 | node_index: NodeIndex, |
441 | 24 | ) -> impl Iterator<Item = NodeIndex> + Clone + '_ { |
442 | 24 | debug_assert!(self.nodes.get(usize::MAX).is_none()); |
443 | | |
444 | | // First element is an invalid key, each successor is the last element of |
445 | | // `node_to_root_path(node_index)` that isn't equal to `current`. |
446 | | // Since the first element is invalid, we skip it. |
447 | 67 | iter::successors(Some(NodeIndex(usize::MAX)), 24 move |¤t| { |
448 | 67 | self.node_to_root_path(node_index) |
449 | 121 | .take_while(move |n| *n != current) _RNCNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB6_8ForkTreeuE17root_to_node_path00Ba_ Line | Count | Source | 449 | 7 | .take_while(move |n| *n != current) |
_RNCNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB6_8ForkTreeINtNtNtBa_12transactions10light_pool5BlockuEE17root_to_node_path00Ba_ Line | Count | Source | 449 | 114 | .take_while(move |n| *n != current) |
Unexecuted instantiation: _RNCNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB6_8ForkTreeINtNtNtBa_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE17root_to_node_path00CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB6_8ForkTreeINtNtB8_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1v_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE17root_to_node_path00CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB6_8ForkTreeINtNtB8_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1v_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB24_7RuntimeEEEE17root_to_node_path00CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB6_8ForkTreeINtNtB8_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB24_7RuntimeEEE17root_to_node_path00CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB6_8ForkTreepE17root_to_node_path00Ba_ Unexecuted instantiation: _RNCNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB6_8ForkTreeAhj20_E17root_to_node_path00CsiUjFBJteJ7x_17smoldot_full_node |
450 | 67 | .last() |
451 | 67 | }) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeuE17root_to_node_path0B8_ Line | Count | Source | 447 | 5 | iter::successors(Some(NodeIndex(usize::MAX)), move |¤t| { | 448 | 5 | self.node_to_root_path(node_index) | 449 | 5 | .take_while(move |n| *n != current) | 450 | 5 | .last() | 451 | 5 | }) |
_RNCNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockuEE17root_to_node_path0B8_ Line | Count | Source | 447 | 62 | iter::successors(Some(NodeIndex(usize::MAX)), move |¤t| { | 448 | 62 | self.node_to_root_path(node_index) | 449 | 62 | .take_while(move |n| *n != current) | 450 | 62 | .last() | 451 | 62 | }) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtNtB8_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE17root_to_node_path0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE17root_to_node_path0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1t_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEEE17root_to_node_path0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeINtNtB6_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB22_7RuntimeEEE17root_to_node_path0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreepE17root_to_node_path0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB4_8ForkTreeAhj20_E17root_to_node_path0CsiUjFBJteJ7x_17smoldot_full_node |
452 | 24 | .skip(1) |
453 | 24 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE17root_to_node_pathB6_ Line | Count | Source | 438 | 22 | pub fn root_to_node_path( | 439 | 22 | &'_ self, | 440 | 22 | node_index: NodeIndex, | 441 | 22 | ) -> impl Iterator<Item = NodeIndex> + Clone + '_ { | 442 | 22 | debug_assert!(self.nodes.get(usize::MAX).is_none()); | 443 | | | 444 | | // First element is an invalid key, each successor is the last element of | 445 | | // `node_to_root_path(node_index)` that isn't equal to `current`. | 446 | | // Since the first element is invalid, we skip it. | 447 | 22 | iter::successors(Some(NodeIndex(usize::MAX)), move |¤t| { | 448 | | self.node_to_root_path(node_index) | 449 | | .take_while(move |n| *n != current) | 450 | | .last() | 451 | 22 | }) | 452 | 22 | .skip(1) | 453 | 22 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeuE17root_to_node_pathB6_ Line | Count | Source | 438 | 2 | pub fn root_to_node_path( | 439 | 2 | &'_ self, | 440 | 2 | node_index: NodeIndex, | 441 | 2 | ) -> impl Iterator<Item = NodeIndex> + Clone + '_ { | 442 | 2 | debug_assert!(self.nodes.get(usize::MAX).is_none()); | 443 | | | 444 | | // First element is an invalid key, each successor is the last element of | 445 | | // `node_to_root_path(node_index)` that isn't equal to `current`. | 446 | | // Since the first element is invalid, we skip it. | 447 | 2 | iter::successors(Some(NodeIndex(usize::MAX)), move |¤t| { | 448 | | self.node_to_root_path(node_index) | 449 | | .take_while(move |n| *n != current) | 450 | | .last() | 451 | 2 | }) | 452 | 2 | .skip(1) | 453 | 2 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE17root_to_node_pathCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE17root_to_node_pathCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE17root_to_node_pathCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE17root_to_node_pathCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE17root_to_node_pathB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E17root_to_node_pathCsiUjFBJteJ7x_17smoldot_full_node |
454 | | |
455 | | /// Finds the first node in the tree that matches the given condition. |
456 | 6 | pub fn find(&self, mut cond: impl FnMut(&T) -> bool) -> Option<NodeIndex> { |
457 | 6 | self.nodes |
458 | 6 | .iter() |
459 | 21 | .filter(|(_, n)| cond(&n.data)) _RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basic0E0B9_ Line | Count | Source | 459 | 1 | .filter(|(_, n)| cond(&n.data)) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics0_0E0B9_ Line | Count | Source | 459 | 3 | .filter(|(_, n)| cond(&n.data)) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics1_0E0B9_ Line | Count | Source | 459 | 4 | .filter(|(_, n)| cond(&n.data)) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics2_0E0B9_ Line | Count | Source | 459 | 5 | .filter(|(_, n)| cond(&n.data)) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics3_0E0B9_ Line | Count | Source | 459 | 6 | .filter(|(_, n)| cond(&n.data)) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics_0E0B9_ Line | Count | Source | 459 | 2 | .filter(|(_, n)| cond(&n.data)) |
Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_8ForkTreepE4findpE0B9_ |
460 | 6 | .map(|(i, _)| i) _RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basic0Es_0B9_ Line | Count | Source | 460 | 1 | .map(|(i, _)| i) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics0_0Es_0B9_ Line | Count | Source | 460 | 1 | .map(|(i, _)| i) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics1_0Es_0B9_ Line | Count | Source | 460 | 1 | .map(|(i, _)| i) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics2_0Es_0B9_ Line | Count | Source | 460 | 1 | .map(|(i, _)| i) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics3_0Es_0B9_ Line | Count | Source | 460 | 1 | .map(|(i, _)| i) |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_8ForkTreelE4findNCNvNtB5_5testss_5basics_0Es_0B9_ Line | Count | Source | 460 | 1 | .map(|(i, _)| i) |
Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_8ForkTreepE4findpEs_0B9_ |
461 | 6 | .next() |
462 | 6 | .map(NodeIndex) |
463 | 6 | } _RINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB3_8ForkTreelE4findNCNvNtB3_5testss_5basic0EB7_ Line | Count | Source | 456 | 1 | pub fn find(&self, mut cond: impl FnMut(&T) -> bool) -> Option<NodeIndex> { | 457 | 1 | self.nodes | 458 | 1 | .iter() | 459 | 1 | .filter(|(_, n)| cond(&n.data)) | 460 | 1 | .map(|(i, _)| i) | 461 | 1 | .next() | 462 | 1 | .map(NodeIndex) | 463 | 1 | } |
_RINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB3_8ForkTreelE4findNCNvNtB3_5testss_5basics0_0EB7_ Line | Count | Source | 456 | 1 | pub fn find(&self, mut cond: impl FnMut(&T) -> bool) -> Option<NodeIndex> { | 457 | 1 | self.nodes | 458 | 1 | .iter() | 459 | 1 | .filter(|(_, n)| cond(&n.data)) | 460 | 1 | .map(|(i, _)| i) | 461 | 1 | .next() | 462 | 1 | .map(NodeIndex) | 463 | 1 | } |
_RINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB3_8ForkTreelE4findNCNvNtB3_5testss_5basics1_0EB7_ Line | Count | Source | 456 | 1 | pub fn find(&self, mut cond: impl FnMut(&T) -> bool) -> Option<NodeIndex> { | 457 | 1 | self.nodes | 458 | 1 | .iter() | 459 | 1 | .filter(|(_, n)| cond(&n.data)) | 460 | 1 | .map(|(i, _)| i) | 461 | 1 | .next() | 462 | 1 | .map(NodeIndex) | 463 | 1 | } |
_RINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB3_8ForkTreelE4findNCNvNtB3_5testss_5basics2_0EB7_ Line | Count | Source | 456 | 1 | pub fn find(&self, mut cond: impl FnMut(&T) -> bool) -> Option<NodeIndex> { | 457 | 1 | self.nodes | 458 | 1 | .iter() | 459 | 1 | .filter(|(_, n)| cond(&n.data)) | 460 | 1 | .map(|(i, _)| i) | 461 | 1 | .next() | 462 | 1 | .map(NodeIndex) | 463 | 1 | } |
_RINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB3_8ForkTreelE4findNCNvNtB3_5testss_5basics3_0EB7_ Line | Count | Source | 456 | 1 | pub fn find(&self, mut cond: impl FnMut(&T) -> bool) -> Option<NodeIndex> { | 457 | 1 | self.nodes | 458 | 1 | .iter() | 459 | 1 | .filter(|(_, n)| cond(&n.data)) | 460 | 1 | .map(|(i, _)| i) | 461 | 1 | .next() | 462 | 1 | .map(NodeIndex) | 463 | 1 | } |
_RINvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB3_8ForkTreelE4findNCNvNtB3_5testss_5basics_0EB7_ Line | Count | Source | 456 | 1 | pub fn find(&self, mut cond: impl FnMut(&T) -> bool) -> Option<NodeIndex> { | 457 | 1 | self.nodes | 458 | 1 | .iter() | 459 | 1 | .filter(|(_, n)| cond(&n.data)) | 460 | 1 | .map(|(i, _)| i) | 461 | 1 | .next() | 462 | 1 | .map(NodeIndex) | 463 | 1 | } |
Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB3_8ForkTreepE4findpEB7_ |
464 | | |
465 | | /// Inserts a new node in the tree. |
466 | | /// |
467 | | /// # Panic |
468 | | /// |
469 | | /// Panics if `parent` isn't a valid node index. |
470 | | /// |
471 | 30 | pub fn insert(&mut self, parent: Option<NodeIndex>, child: T) -> NodeIndex { |
472 | 30 | if let Some(parent17 ) = parent { |
473 | 17 | let next_sibling = self.nodes.get_mut(parent.0).unwrap().first_child; |
474 | 17 | |
475 | 17 | let new_node_index = self.nodes.insert(Node { |
476 | 17 | parent: Some(parent.0), |
477 | 17 | first_child: None, |
478 | 17 | next_sibling, |
479 | 17 | previous_sibling: None, |
480 | 17 | is_prune_target_ancestor: false, |
481 | 17 | data: child, |
482 | 17 | }); |
483 | 17 | |
484 | 17 | self.nodes.get_mut(parent.0).unwrap().first_child = Some(new_node_index); |
485 | | |
486 | 17 | if let Some(next_sibling3 ) = next_sibling { |
487 | 3 | self.nodes.get_mut(next_sibling).unwrap().previous_sibling = Some(new_node_index); |
488 | 14 | } |
489 | | |
490 | 17 | NodeIndex(new_node_index) |
491 | | } else { |
492 | 13 | let new_node_index = self.nodes.insert(Node { |
493 | 13 | parent: None, |
494 | 13 | first_child: None, |
495 | 13 | next_sibling: self.first_root, |
496 | 13 | previous_sibling: None, |
497 | 13 | is_prune_target_ancestor: false, |
498 | 13 | data: child, |
499 | 13 | }); |
500 | | |
501 | 13 | if let Some(first_root2 ) = self.first_root { |
502 | 2 | self.nodes.get_mut(first_root).unwrap().previous_sibling = Some(new_node_index); |
503 | 11 | } |
504 | | |
505 | 13 | self.first_root = Some(new_node_index); |
506 | 13 | |
507 | 13 | NodeIndex(new_node_index) |
508 | | } |
509 | 30 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockuEE6insertB6_ Line | Count | Source | 471 | 4 | pub fn insert(&mut self, parent: Option<NodeIndex>, child: T) -> NodeIndex { | 472 | 4 | if let Some(parent2 ) = parent { | 473 | 2 | let next_sibling = self.nodes.get_mut(parent.0).unwrap().first_child; | 474 | 2 | | 475 | 2 | let new_node_index = self.nodes.insert(Node { | 476 | 2 | parent: Some(parent.0), | 477 | 2 | first_child: None, | 478 | 2 | next_sibling, | 479 | 2 | previous_sibling: None, | 480 | 2 | is_prune_target_ancestor: false, | 481 | 2 | data: child, | 482 | 2 | }); | 483 | 2 | | 484 | 2 | self.nodes.get_mut(parent.0).unwrap().first_child = Some(new_node_index); | 485 | | | 486 | 2 | if let Some(next_sibling0 ) = next_sibling { | 487 | 0 | self.nodes.get_mut(next_sibling).unwrap().previous_sibling = Some(new_node_index); | 488 | 2 | } | 489 | | | 490 | 2 | NodeIndex(new_node_index) | 491 | | } else { | 492 | 2 | let new_node_index = self.nodes.insert(Node { | 493 | 2 | parent: None, | 494 | 2 | first_child: None, | 495 | 2 | next_sibling: self.first_root, | 496 | 2 | previous_sibling: None, | 497 | 2 | is_prune_target_ancestor: false, | 498 | 2 | data: child, | 499 | 2 | }); | 500 | | | 501 | 2 | if let Some(first_root0 ) = self.first_root { | 502 | 0 | self.nodes.get_mut(first_root).unwrap().previous_sibling = Some(new_node_index); | 503 | 2 | } | 504 | | | 505 | 2 | self.first_root = Some(new_node_index); | 506 | 2 | | 507 | 2 | NodeIndex(new_node_index) | 508 | | } | 509 | 4 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockuEE6insertB6_ Line | Count | Source | 471 | 15 | pub fn insert(&mut self, parent: Option<NodeIndex>, child: T) -> NodeIndex { | 472 | 15 | if let Some(parent8 ) = parent { | 473 | 8 | let next_sibling = self.nodes.get_mut(parent.0).unwrap().first_child; | 474 | 8 | | 475 | 8 | let new_node_index = self.nodes.insert(Node { | 476 | 8 | parent: Some(parent.0), | 477 | 8 | first_child: None, | 478 | 8 | next_sibling, | 479 | 8 | previous_sibling: None, | 480 | 8 | is_prune_target_ancestor: false, | 481 | 8 | data: child, | 482 | 8 | }); | 483 | 8 | | 484 | 8 | self.nodes.get_mut(parent.0).unwrap().first_child = Some(new_node_index); | 485 | | | 486 | 8 | if let Some(next_sibling0 ) = next_sibling { | 487 | 0 | self.nodes.get_mut(next_sibling).unwrap().previous_sibling = Some(new_node_index); | 488 | 8 | } | 489 | | | 490 | 8 | NodeIndex(new_node_index) | 491 | | } else { | 492 | 7 | let new_node_index = self.nodes.insert(Node { | 493 | 7 | parent: None, | 494 | 7 | first_child: None, | 495 | 7 | next_sibling: self.first_root, | 496 | 7 | previous_sibling: None, | 497 | 7 | is_prune_target_ancestor: false, | 498 | 7 | data: child, | 499 | 7 | }); | 500 | | | 501 | 7 | if let Some(first_root1 ) = self.first_root { | 502 | 1 | self.nodes.get_mut(first_root).unwrap().previous_sibling = Some(new_node_index); | 503 | 6 | } | 504 | | | 505 | 7 | self.first_root = Some(new_node_index); | 506 | 7 | | 507 | 7 | NodeIndex(new_node_index) | 508 | | } | 509 | 15 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreelE6insertB6_ Line | Count | Source | 471 | 6 | pub fn insert(&mut self, parent: Option<NodeIndex>, child: T) -> NodeIndex { | 472 | 6 | if let Some(parent5 ) = parent { | 473 | 5 | let next_sibling = self.nodes.get_mut(parent.0).unwrap().first_child; | 474 | 5 | | 475 | 5 | let new_node_index = self.nodes.insert(Node { | 476 | 5 | parent: Some(parent.0), | 477 | 5 | first_child: None, | 478 | 5 | next_sibling, | 479 | 5 | previous_sibling: None, | 480 | 5 | is_prune_target_ancestor: false, | 481 | 5 | data: child, | 482 | 5 | }); | 483 | 5 | | 484 | 5 | self.nodes.get_mut(parent.0).unwrap().first_child = Some(new_node_index); | 485 | | | 486 | 5 | if let Some(next_sibling2 ) = next_sibling { | 487 | 2 | self.nodes.get_mut(next_sibling).unwrap().previous_sibling = Some(new_node_index); | 488 | 3 | } | 489 | | | 490 | 5 | NodeIndex(new_node_index) | 491 | | } else { | 492 | 1 | let new_node_index = self.nodes.insert(Node { | 493 | 1 | parent: None, | 494 | 1 | first_child: None, | 495 | 1 | next_sibling: self.first_root, | 496 | 1 | previous_sibling: None, | 497 | 1 | is_prune_target_ancestor: false, | 498 | 1 | data: child, | 499 | 1 | }); | 500 | | | 501 | 1 | if let Some(first_root0 ) = self.first_root { | 502 | 0 | self.nodes.get_mut(first_root).unwrap().previous_sibling = Some(new_node_index); | 503 | 1 | } | 504 | | | 505 | 1 | self.first_root = Some(new_node_index); | 506 | 1 | | 507 | 1 | NodeIndex(new_node_index) | 508 | | } | 509 | 6 | } |
_RNvMNtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB2_8ForkTreeuE6insertB6_ Line | Count | Source | 471 | 5 | pub fn insert(&mut self, parent: Option<NodeIndex>, child: T) -> NodeIndex { | 472 | 5 | if let Some(parent2 ) = parent { | 473 | 2 | let next_sibling = self.nodes.get_mut(parent.0).unwrap().first_child; | 474 | 2 | | 475 | 2 | let new_node_index = self.nodes.insert(Node { | 476 | 2 | parent: Some(parent.0), | 477 | 2 | first_child: None, | 478 | 2 | next_sibling, | 479 | 2 | previous_sibling: None, | 480 | 2 | is_prune_target_ancestor: false, | 481 | 2 | data: child, | 482 | 2 | }); | 483 | 2 | | 484 | 2 | self.nodes.get_mut(parent.0).unwrap().first_child = Some(new_node_index); | 485 | | | 486 | 2 | if let Some(next_sibling1 ) = next_sibling { | 487 | 1 | self.nodes.get_mut(next_sibling).unwrap().previous_sibling = Some(new_node_index); | 488 | 1 | } | 489 | | | 490 | 2 | NodeIndex(new_node_index) | 491 | | } else { | 492 | 3 | let new_node_index = self.nodes.insert(Node { | 493 | 3 | parent: None, | 494 | 3 | first_child: None, | 495 | 3 | next_sibling: self.first_root, | 496 | 3 | previous_sibling: None, | 497 | 3 | is_prune_target_ancestor: false, | 498 | 3 | data: child, | 499 | 3 | }); | 500 | | | 501 | 3 | if let Some(first_root1 ) = self.first_root { | 502 | 1 | self.nodes.get_mut(first_root).unwrap().previous_sibling = Some(new_node_index); | 503 | 2 | } | 504 | | | 505 | 3 | self.first_root = Some(new_node_index); | 506 | 3 | | 507 | 3 | NodeIndex(new_node_index) | 508 | | } | 509 | 5 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEE6insertCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1r_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEEE6insertCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB20_7RuntimeEEE6insertCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEE6insertCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtNtB6_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEE6insertCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreepE6insertB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE6insertCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeAhj20_E6insertCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE6insertCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB2_8ForkTreeINtNtB4_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEE6insertCsibGXYHQB8Ea_25json_rpc_general_requests |
510 | | } |
511 | | |
512 | | impl<T> Default for ForkTree<T> { |
513 | 0 | fn default() -> Self { |
514 | 0 | Self::new() |
515 | 0 | } Unexecuted instantiation: _RNvXININtNtCsN16ciHI6Qf_7smoldot5chain9fork_trees_0pEINtB5_8ForkTreepENtNtCsaYZPK01V26L_4core7default7Default7defaultB9_ Unexecuted instantiation: _RNvXININtNtCseuYC0Zibziv_7smoldot5chain9fork_trees_0pEINtB5_8ForkTreepENtNtCsaYZPK01V26L_4core7default7Default7defaultB9_ |
516 | | } |
517 | | |
518 | | impl<T> fmt::Debug for ForkTree<T> |
519 | | where |
520 | | T: fmt::Debug, |
521 | | { |
522 | 0 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
523 | 0 | f.debug_list() |
524 | 0 | .entries(self.nodes.iter().map(|(_, v)| &v.data)) Unexecuted instantiation: _RNCNvXININtNtCsN16ciHI6Qf_7smoldot5chain9fork_trees0_0pEINtB7_8ForkTreepENtNtCsaYZPK01V26L_4core3fmt5Debug3fmt0Bb_ Unexecuted instantiation: _RNCNvXININtNtCseuYC0Zibziv_7smoldot5chain9fork_trees0_0pEINtB7_8ForkTreepENtNtCsaYZPK01V26L_4core3fmt5Debug3fmt0Bb_ |
525 | 0 | .finish() |
526 | 0 | } Unexecuted instantiation: _RNvXININtNtCsN16ciHI6Qf_7smoldot5chain9fork_trees0_0pEINtB5_8ForkTreepENtNtCsaYZPK01V26L_4core3fmt5Debug3fmtB9_ Unexecuted instantiation: _RNvXININtNtCseuYC0Zibziv_7smoldot5chain9fork_trees0_0pEINtB5_8ForkTreepENtNtCsaYZPK01V26L_4core3fmt5Debug3fmtB9_ |
527 | | } |
528 | | |
529 | | /// Iterator of elements removed when pruning ancestors. |
530 | | pub struct PruneAncestorsIter<'a, T> { |
531 | | /// True if iterator is completed. If true, none of the values of the other fields are relevant |
532 | | /// anymore. |
533 | | finished: bool, |
534 | | |
535 | | // Parent object. |
536 | | // Note that `first_root` has already been updated to be the new final, and therefore |
537 | | // shouldn't be relied upon. |
538 | | tree: &'a mut ForkTree<T>, |
539 | | |
540 | | /// Current node being iterated. |
541 | | /// Order of iteration is: go down the hierarchy as deep as possible by following the first |
542 | | /// child. If there is no first child, instead go to the next sibling. If there is no next |
543 | | /// sibling, go to the parent. |
544 | | iter: usize, |
545 | | |
546 | | /// True if the previous iteration was from a node lower in the hierarchy. |
547 | | traversing_up: bool, |
548 | | |
549 | | /// Target of the pruning. Value which `prune_ancestors` has been called with. |
550 | | new_final: NodeIndex, |
551 | | |
552 | | /// If `true`, `new_final` and its ancestors aren't removed. |
553 | | uncles_only: bool, |
554 | | } |
555 | | |
556 | | impl<'a, T> Iterator for PruneAncestorsIter<'a, T> { |
557 | | type Item = PrunedNode<T>; |
558 | | |
559 | 14 | fn next(&mut self) -> Option<Self::Item> { |
560 | 26 | loop { |
561 | 26 | if self.finished { |
562 | 10 | break None; |
563 | 16 | } |
564 | 16 | |
565 | 16 | let iter_node = &mut self.tree.nodes[self.iter]; |
566 | 16 | |
567 | 16 | // If current node is a direct child of `new_final`, then don't remove it. |
568 | 16 | // Instead, just update its parent to be `None` and continue iterating. |
569 | 16 | if iter_node.parent == Some(self.new_final.0) { |
570 | 1 | debug_assert!(!self.traversing_up); |
571 | 1 | if !self.uncles_only { |
572 | 1 | iter_node.parent = None; |
573 | 1 | }0 |
574 | 1 | self.iter = if let Some(next_sibling0 ) = iter_node.next_sibling { |
575 | 0 | next_sibling |
576 | | } else { |
577 | 1 | self.traversing_up = true; |
578 | 1 | self.new_final.0 |
579 | | }; |
580 | 1 | continue; |
581 | 15 | } |
582 | 15 | |
583 | 15 | // If `traversing_up` is false`, try to go down the hierarchy as deeply as possible. |
584 | 15 | if !self.traversing_up { |
585 | 10 | if let Some(first_child5 ) = iter_node.first_child { |
586 | 5 | self.iter = first_child; |
587 | 5 | continue; |
588 | 5 | } |
589 | 5 | } |
590 | | |
591 | | // Keep a copy of `self.iter` because we update it now. |
592 | 10 | let maybe_removed_node_index = NodeIndex(self.iter); |
593 | | |
594 | | // Jump either to its next sibling, or, if it was the last sibling, back to its |
595 | | // parent. |
596 | 10 | if let Some(next_sibling1 ) = iter_node.next_sibling { |
597 | 1 | self.traversing_up = false; |
598 | 1 | self.iter = next_sibling; |
599 | 9 | } else if let Some(parent4 ) = iter_node.parent { |
600 | 4 | self.traversing_up = true; |
601 | 4 | self.iter = parent; |
602 | 5 | } else { |
603 | 5 | self.finished = true; |
604 | 5 | }; |
605 | | |
606 | | // Should the node be removed? |
607 | 10 | if self.uncles_only && iter_node.is_prune_target_ancestor6 { |
608 | | // Reset `is_prune_target_ancestor` for next time we do some pruning. |
609 | 6 | iter_node.is_prune_target_ancestor = false; |
610 | 6 | |
611 | 6 | // Update the inter-node relationships. |
612 | 6 | iter_node.next_sibling = None; |
613 | 6 | if iter_node.previous_sibling.take().is_some() { |
614 | | // Notice the `take()` here ^ |
615 | 0 | if let Some(parent) = iter_node.parent { |
616 | 0 | debug_assert!(self.tree.nodes[parent].first_child.is_some()); |
617 | 0 | self.tree.nodes[parent].first_child = Some(maybe_removed_node_index.0); |
618 | 0 | } |
619 | 6 | } |
620 | | |
621 | 6 | continue; |
622 | 4 | } |
623 | 4 | |
624 | 4 | // Actually remove the node. |
625 | 4 | debug_assert!(self |
626 | 4 | .tree |
627 | 4 | .first_root |
628 | 4 | .map_or(true, |n| n != maybe_removed_node_index.03 )); Unexecuted instantiation: _RNCNvXs1_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtNtBb_12transactions10light_pool5BlockuEENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4next0Bb_ _RNCNvXs1_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterlENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4next0Bb_ Line | Count | Source | 628 | 3 | .map_or(true, |n| n != maybe_removed_node_index.0)); |
Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1H_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEENtNtNtNtB1H_4iter6traits8iterator8Iterator4next0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1H_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB2g_7RuntimeEEEENtNtNtNtB1H_4iter6traits8iterator8Iterator4next0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB2g_7RuntimeEEENtNtNtNtB1H_4iter6traits8iterator8Iterator4next0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEENtNtNtNtB1J_4iter6traits8iterator8Iterator4next0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtNtBb_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4next0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXININtNtCseuYC0Zibziv_7smoldot5chain9fork_trees1_0pEINtB7_18PruneAncestorsIterpENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4next0Bb_ Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtNtB1J_4iter6traits8iterator8Iterator4next0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterAhj20_ENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4next0CsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtNtB1J_4iter6traits8iterator8Iterator4next0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtNtB1J_4iter6traits8iterator8Iterator4next0CsibGXYHQB8Ea_25json_rpc_general_requests |
629 | 4 | let iter_node = self.tree.nodes.remove(maybe_removed_node_index.0); |
630 | 4 | |
631 | 4 | break Some(PrunedNode { |
632 | 4 | index: maybe_removed_node_index, |
633 | 4 | is_prune_target_ancestor: iter_node.is_prune_target_ancestor, |
634 | 4 | user_data: iter_node.data, |
635 | 4 | }); |
636 | | } |
637 | 14 | } _RNvXs1_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtNtB9_12transactions10light_pool5BlockuEENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4nextB9_ Line | Count | Source | 559 | 9 | fn next(&mut self) -> Option<Self::Item> { | 560 | 18 | loop { | 561 | 18 | if self.finished { | 562 | 8 | break None; | 563 | 10 | } | 564 | 10 | | 565 | 10 | let iter_node = &mut self.tree.nodes[self.iter]; | 566 | 10 | | 567 | 10 | // If current node is a direct child of `new_final`, then don't remove it. | 568 | 10 | // Instead, just update its parent to be `None` and continue iterating. | 569 | 10 | if iter_node.parent == Some(self.new_final.0) { | 570 | 0 | debug_assert!(!self.traversing_up); | 571 | 0 | if !self.uncles_only { | 572 | 0 | iter_node.parent = None; | 573 | 0 | } | 574 | 0 | self.iter = if let Some(next_sibling) = iter_node.next_sibling { | 575 | 0 | next_sibling | 576 | | } else { | 577 | 0 | self.traversing_up = true; | 578 | 0 | self.new_final.0 | 579 | | }; | 580 | 0 | continue; | 581 | 10 | } | 582 | 10 | | 583 | 10 | // If `traversing_up` is false`, try to go down the hierarchy as deeply as possible. | 584 | 10 | if !self.traversing_up { | 585 | 7 | if let Some(first_child3 ) = iter_node.first_child { | 586 | 3 | self.iter = first_child; | 587 | 3 | continue; | 588 | 4 | } | 589 | 3 | } | 590 | | | 591 | | // Keep a copy of `self.iter` because we update it now. | 592 | 7 | let maybe_removed_node_index = NodeIndex(self.iter); | 593 | | | 594 | | // Jump either to its next sibling, or, if it was the last sibling, back to its | 595 | | // parent. | 596 | 7 | if let Some(next_sibling0 ) = iter_node.next_sibling { | 597 | 0 | self.traversing_up = false; | 598 | 0 | self.iter = next_sibling; | 599 | 7 | } else if let Some(parent3 ) = iter_node.parent { | 600 | 3 | self.traversing_up = true; | 601 | 3 | self.iter = parent; | 602 | 4 | } else { | 603 | 4 | self.finished = true; | 604 | 4 | }; | 605 | | | 606 | | // Should the node be removed? | 607 | 7 | if self.uncles_only && iter_node.is_prune_target_ancestor6 { | 608 | | // Reset `is_prune_target_ancestor` for next time we do some pruning. | 609 | 6 | iter_node.is_prune_target_ancestor = false; | 610 | 6 | | 611 | 6 | // Update the inter-node relationships. | 612 | 6 | iter_node.next_sibling = None; | 613 | 6 | if iter_node.previous_sibling.take().is_some() { | 614 | | // Notice the `take()` here ^ | 615 | 0 | if let Some(parent) = iter_node.parent { | 616 | 0 | debug_assert!(self.tree.nodes[parent].first_child.is_some()); | 617 | 0 | self.tree.nodes[parent].first_child = Some(maybe_removed_node_index.0); | 618 | 0 | } | 619 | 6 | } | 620 | | | 621 | 6 | continue; | 622 | 1 | } | 623 | 1 | | 624 | 1 | // Actually remove the node. | 625 | 1 | debug_assert!(self | 626 | 1 | .tree | 627 | 1 | .first_root | 628 | 1 | .map_or(true, |n| n != maybe_removed_node_index.0)); | 629 | 1 | let iter_node = self.tree.nodes.remove(maybe_removed_node_index.0); | 630 | 1 | | 631 | 1 | break Some(PrunedNode { | 632 | 1 | index: maybe_removed_node_index, | 633 | 1 | is_prune_target_ancestor: iter_node.is_prune_target_ancestor, | 634 | 1 | user_data: iter_node.data, | 635 | 1 | }); | 636 | | } | 637 | 9 | } |
_RNvXs1_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterlENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4nextB9_ Line | Count | Source | 559 | 5 | fn next(&mut self) -> Option<Self::Item> { | 560 | 8 | loop { | 561 | 8 | if self.finished { | 562 | 2 | break None; | 563 | 6 | } | 564 | 6 | | 565 | 6 | let iter_node = &mut self.tree.nodes[self.iter]; | 566 | 6 | | 567 | 6 | // If current node is a direct child of `new_final`, then don't remove it. | 568 | 6 | // Instead, just update its parent to be `None` and continue iterating. | 569 | 6 | if iter_node.parent == Some(self.new_final.0) { | 570 | 1 | debug_assert!(!self.traversing_up); | 571 | 1 | if !self.uncles_only { | 572 | 1 | iter_node.parent = None; | 573 | 1 | }0 | 574 | 1 | self.iter = if let Some(next_sibling0 ) = iter_node.next_sibling { | 575 | 0 | next_sibling | 576 | | } else { | 577 | 1 | self.traversing_up = true; | 578 | 1 | self.new_final.0 | 579 | | }; | 580 | 1 | continue; | 581 | 5 | } | 582 | 5 | | 583 | 5 | // If `traversing_up` is false`, try to go down the hierarchy as deeply as possible. | 584 | 5 | if !self.traversing_up { | 585 | 3 | if let Some(first_child2 ) = iter_node.first_child { | 586 | 2 | self.iter = first_child; | 587 | 2 | continue; | 588 | 1 | } | 589 | 2 | } | 590 | | | 591 | | // Keep a copy of `self.iter` because we update it now. | 592 | 3 | let maybe_removed_node_index = NodeIndex(self.iter); | 593 | | | 594 | | // Jump either to its next sibling, or, if it was the last sibling, back to its | 595 | | // parent. | 596 | 3 | if let Some(next_sibling1 ) = iter_node.next_sibling { | 597 | 1 | self.traversing_up = false; | 598 | 1 | self.iter = next_sibling; | 599 | 2 | } else if let Some(parent1 ) = iter_node.parent { | 600 | 1 | self.traversing_up = true; | 601 | 1 | self.iter = parent; | 602 | 1 | } else { | 603 | 1 | self.finished = true; | 604 | 1 | }; | 605 | | | 606 | | // Should the node be removed? | 607 | 3 | if self.uncles_only && iter_node.is_prune_target_ancestor0 { | 608 | | // Reset `is_prune_target_ancestor` for next time we do some pruning. | 609 | 0 | iter_node.is_prune_target_ancestor = false; | 610 | 0 |
| 611 | 0 | // Update the inter-node relationships. | 612 | 0 | iter_node.next_sibling = None; | 613 | 0 | if iter_node.previous_sibling.take().is_some() { | 614 | | // Notice the `take()` here ^ | 615 | 0 | if let Some(parent) = iter_node.parent { | 616 | 0 | debug_assert!(self.tree.nodes[parent].first_child.is_some()); | 617 | 0 | self.tree.nodes[parent].first_child = Some(maybe_removed_node_index.0); | 618 | 0 | } | 619 | 0 | } | 620 | | | 621 | 0 | continue; | 622 | 3 | } | 623 | 3 | | 624 | 3 | // Actually remove the node. | 625 | 3 | debug_assert!(self | 626 | 3 | .tree | 627 | 3 | .first_root | 628 | 3 | .map_or(true, |n| n != maybe_removed_node_index.0)); | 629 | 3 | let iter_node = self.tree.nodes.remove(maybe_removed_node_index.0); | 630 | 3 | | 631 | 3 | break Some(PrunedNode { | 632 | 3 | index: maybe_removed_node_index, | 633 | 3 | is_prune_target_ancestor: iter_node.is_prune_target_ancestor, | 634 | 3 | user_data: iter_node.data, | 635 | 3 | }); | 636 | | } | 637 | 5 | } |
Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1F_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEENtNtNtNtB1F_4iter6traits8iterator8Iterator4nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1F_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB2e_7RuntimeEEEENtNtNtNtB1F_4iter6traits8iterator8Iterator4nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB2e_7RuntimeEEENtNtNtNtB1F_4iter6traits8iterator8Iterator4nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEENtNtNtNtB1H_4iter6traits8iterator8Iterator4nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtNtB9_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4nextCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXININtNtCseuYC0Zibziv_7smoldot5chain9fork_trees1_0pEINtB5_18PruneAncestorsIterpENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4nextB9_ Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtNtB1H_4iter6traits8iterator8Iterator4nextCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterAhj20_ENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator4nextCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtNtB1H_4iter6traits8iterator8Iterator4nextCscDgN54JpMGG_6author Unexecuted instantiation: _RNvXs1_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtNtB1H_4iter6traits8iterator8Iterator4nextCsibGXYHQB8Ea_25json_rpc_general_requests |
638 | | |
639 | 1 | fn size_hint(&self) -> (usize, Option<usize>) { |
640 | 1 | (0, Some(self.tree.nodes.len())) |
641 | 1 | } _RNvXs1_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterlENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator9size_hintB9_ Line | Count | Source | 639 | 1 | fn size_hint(&self) -> (usize, Option<usize>) { | 640 | 1 | (0, Some(self.tree.nodes.len())) | 641 | 1 | } |
Unexecuted instantiation: _RNvXININtNtCseuYC0Zibziv_7smoldot5chain9fork_trees1_0pEINtB5_18PruneAncestorsIterpENtNtNtNtCsaYZPK01V26L_4core4iter6traits8iterator8Iterator9size_hintB9_ |
642 | | } |
643 | | |
644 | | impl<'a, T> Drop for PruneAncestorsIter<'a, T> { |
645 | 5 | fn drop(&mut self) { |
646 | | // Make sure that all elements are removed. |
647 | 5 | loop { |
648 | 5 | if self.next().is_none() { |
649 | 5 | break; |
650 | 0 | } |
651 | | } |
652 | | |
653 | 5 | if self.uncles_only { |
654 | 3 | debug_assert!(self.tree.first_root.is_some()); |
655 | 2 | } |
656 | | |
657 | 5 | debug_assert!(self |
658 | 5 | .tree |
659 | 5 | .first_root |
660 | 5 | .map_or(true, |fr| self.tree.nodes.contains(fr)4 )); _RNCNvXs2_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtNtBb_12transactions10light_pool5BlockuEENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4drop0Bb_ Line | Count | Source | 660 | 3 | .map_or(true, |fr| self.tree.nodes.contains(fr))); |
_RNCNvXs2_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterlENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4drop0Bb_ Line | Count | Source | 660 | 1 | .map_or(true, |fr| self.tree.nodes.contains(fr))); |
Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1H_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEENtNtNtB1H_3ops4drop4Drop4drop0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1H_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB2g_7RuntimeEEEENtNtNtB1H_3ops4drop4Drop4drop0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB2g_7RuntimeEEENtNtNtB1H_3ops4drop4Drop4drop0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEENtNtNtB1J_3ops4drop4Drop4drop0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtNtBb_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4drop0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvXININtNtCseuYC0Zibziv_7smoldot5chain9fork_trees2_0pEINtB7_18PruneAncestorsIterpENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4drop0Bb_ Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtB1J_3ops4drop4Drop4drop0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterAhj20_ENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4drop0CsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtB1J_3ops4drop4Drop4drop0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB7_18PruneAncestorsIterINtNtB9_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtB1J_3ops4drop4Drop4drop0CsibGXYHQB8Ea_25json_rpc_general_requests |
661 | | |
662 | 5 | debug_assert_eq!(self.uncles_only, self.tree.get(self.new_final).is_some()); |
663 | | |
664 | | // Do a full pass on the tree. This triggers a lot of debug assertions. |
665 | | #[cfg(debug_assertions)] |
666 | 9 | for _ in self.tree.iter_ancestry_order()5 {} |
667 | 5 | } _RNvXs2_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtNtB9_12transactions10light_pool5BlockuEENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4dropB9_ Line | Count | Source | 645 | 4 | fn drop(&mut self) { | 646 | | // Make sure that all elements are removed. | 647 | 4 | loop { | 648 | 4 | if self.next().is_none() { | 649 | 4 | break; | 650 | 0 | } | 651 | | } | 652 | | | 653 | 4 | if self.uncles_only { | 654 | 3 | debug_assert!(self.tree.first_root.is_some()); | 655 | 1 | } | 656 | | | 657 | 4 | debug_assert!(self | 658 | 4 | .tree | 659 | 4 | .first_root | 660 | 4 | .map_or(true, |fr| self.tree.nodes.contains(fr))); | 661 | | | 662 | 4 | debug_assert_eq!(self.uncles_only, self.tree.get(self.new_final).is_some()); | 663 | | | 664 | | // Do a full pass on the tree. This triggers a lot of debug assertions. | 665 | | #[cfg(debug_assertions)] | 666 | 6 | for _ in self.tree.iter_ancestry_order()4 {} | 667 | 4 | } |
_RNvXs2_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterlENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4dropB9_ Line | Count | Source | 645 | 1 | fn drop(&mut self) { | 646 | | // Make sure that all elements are removed. | 647 | 1 | loop { | 648 | 1 | if self.next().is_none() { | 649 | 1 | break; | 650 | 0 | } | 651 | | } | 652 | | | 653 | 1 | if self.uncles_only { | 654 | 0 | debug_assert!(self.tree.first_root.is_some()); | 655 | 1 | } | 656 | | | 657 | 1 | debug_assert!(self | 658 | 1 | .tree | 659 | 1 | .first_root | 660 | 1 | .map_or(true, |fr| self.tree.nodes.contains(fr))); | 661 | | | 662 | 1 | debug_assert_eq!(self.uncles_only, self.tree.get(self.new_final).is_some()); | 663 | | | 664 | | // Do a full pass on the tree. This triggers a lot of debug assertions. | 665 | | #[cfg(debug_assertions)] | 666 | 3 | for _ in self.tree.iter_ancestry_order()1 {} | 667 | 1 | } |
Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationAhj20_INtNtB1F_6option6OptionINtNtCsdZExvAaxgia_5alloc3vec3VechEEEENtNtNtB1F_3ops4drop4Drop4dropCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtB1F_6option6OptionINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB2e_7RuntimeEEEENtNtNtB1F_3ops4drop4Drop4dropCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_10async_tree5BlockNtNtCsaYZPK01V26L_4core4time8DurationNtNtCsih6EgvAwZF2_13smoldot_light15runtime_service5BlockINtNtCsdZExvAaxgia_5alloc4sync3ArcNtB2e_7RuntimeEEENtNtNtB1F_3ops4drop4Drop4dropCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionuEEENtNtNtB1H_3ops4drop4Drop4dropCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtNtB9_12transactions10light_pool5BlockNtNtCsih6EgvAwZF2_13smoldot_light20transactions_service5BlockEENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4dropCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvXININtNtCseuYC0Zibziv_7smoldot5chain9fork_trees2_0pEINtB5_18PruneAncestorsIterpENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4dropB9_ Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtB1H_3ops4drop4Drop4dropCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterAhj20_ENtNtNtCsaYZPK01V26L_4core3ops4drop4Drop4dropCsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtB1H_3ops4drop4Drop4dropCscDgN54JpMGG_6author Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeINtB5_18PruneAncestorsIterINtNtB7_11blocks_tree5BlockINtNtCsaYZPK01V26L_4core6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEEENtNtNtB1H_3ops4drop4Drop4dropCsibGXYHQB8Ea_25json_rpc_general_requests |
668 | | } |
669 | | |
670 | | /// Node removed by [`ForkTree::prune_ancestors`]. |
671 | | pub struct PrunedNode<T> { |
672 | | /// Former index of the node. This index is no longer valid. |
673 | | pub index: NodeIndex, |
674 | | /// True if this node is an ancestor of the target of the pruning. |
675 | | pub is_prune_target_ancestor: bool, |
676 | | /// Value that was passed to [`ForkTree::insert`]. |
677 | | pub user_data: T, |
678 | | } |
679 | | |
680 | | /// Index of a node within a [`ForkTree`]. Never invalidated unless the node is removed. |
681 | | #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)] |
682 | | pub struct NodeIndex(usize); |
683 | | |
684 | | impl NodeIndex { |
685 | | /// Value that compares inferior or equal to any possible [`NodeIndex`̀]. |
686 | | pub const MIN: Self = NodeIndex(usize::MIN); |
687 | | /// Returns the value that compares superior or equal to any possible [`NodeIndex`̀]. |
688 | | pub const MAX: Self = NodeIndex(usize::MAX); |
689 | | |
690 | | /// Adds `1` to `self`. Returns `None` if this causes an overflow. |
691 | 0 | pub fn inc(self) -> Option<Self> { |
692 | 0 | self.0.checked_add(1).map(NodeIndex) |
693 | 0 | } Unexecuted instantiation: _RNvMs3_NtNtCsN16ciHI6Qf_7smoldot5chain9fork_treeNtB5_9NodeIndex3inc Unexecuted instantiation: _RNvMs3_NtNtCseuYC0Zibziv_7smoldot5chain9fork_treeNtB5_9NodeIndex3inc |
694 | | } |
695 | | |
696 | | #[cfg(test)] |
697 | | mod tests { |
698 | | use super::ForkTree; |
699 | | |
700 | | #[test] |
701 | 1 | fn basic() { |
702 | 1 | let mut tree = ForkTree::new(); |
703 | 1 | |
704 | 1 | let node0 = tree.insert(None, 0); |
705 | 1 | let node1 = tree.insert(Some(node0), 1); |
706 | 1 | let node2 = tree.insert(Some(node1), 2); |
707 | 1 | let node3 = tree.insert(Some(node2), 3); |
708 | 1 | let node4 = tree.insert(Some(node2), 4); |
709 | 1 | let node5 = tree.insert(Some(node0), 5); |
710 | 1 | |
711 | 1 | assert_eq!(tree.find(|v| *v == 0), Some(node0)); |
712 | 2 | assert_eq!(tree.find(1 |v| *v == 1), Some(node1))1 ; |
713 | 3 | assert_eq!(tree.find(1 |v| *v == 2), Some(node2))1 ; |
714 | 4 | assert_eq!(tree.find(1 |v| *v == 3), Some(node3))1 ; |
715 | 5 | assert_eq!(tree.find(1 |v| *v == 4), Some(node4))1 ; |
716 | 6 | assert_eq!(tree.find(1 |v| *v == 5), Some(node5))1 ; |
717 | | |
718 | 1 | assert_eq!( |
719 | 1 | tree.node_to_root_path(node3).collect::<Vec<_>>(), |
720 | 1 | &[node3, node2, node1, node0] |
721 | 1 | ); |
722 | 1 | assert_eq!( |
723 | 1 | tree.node_to_root_path(node4).collect::<Vec<_>>(), |
724 | 1 | &[node4, node2, node1, node0] |
725 | 1 | ); |
726 | 1 | assert_eq!( |
727 | 1 | tree.node_to_root_path(node1).collect::<Vec<_>>(), |
728 | 1 | &[node1, node0] |
729 | 1 | ); |
730 | 1 | assert_eq!( |
731 | 1 | tree.node_to_root_path(node5).collect::<Vec<_>>(), |
732 | 1 | &[node5, node0] |
733 | 1 | ); |
734 | | |
735 | 1 | let iter = tree.prune_ancestors(node1); |
736 | 1 | assert_eq!( |
737 | 3 | iter.filter(|n| n.is_prune_target_ancestor) |
738 | 2 | .map(|n| n.index) |
739 | 1 | .collect::<Vec<_>>(), |
740 | 1 | vec![node1, node0] |
741 | 1 | ); |
742 | | |
743 | 1 | assert!(tree.get(node0).is_none()); |
744 | 1 | assert!(tree.get(node1).is_none()); |
745 | 1 | assert_eq!(tree.get(node2), Some(&2)); |
746 | 1 | assert_eq!(tree.get(node3), Some(&3)); |
747 | 1 | assert_eq!(tree.get(node4), Some(&4)); |
748 | 1 | assert!(tree.get(node5).is_none()); |
749 | | |
750 | 1 | assert_eq!( |
751 | 1 | tree.node_to_root_path(node3).collect::<Vec<_>>(), |
752 | 1 | &[node3, node2] |
753 | 1 | ); |
754 | 1 | assert_eq!( |
755 | 1 | tree.node_to_root_path(node4).collect::<Vec<_>>(), |
756 | 1 | &[node4, node2] |
757 | 1 | ); |
758 | 1 | } |
759 | | |
760 | | #[test] |
761 | 1 | fn ascend_descend_when_common_ancestor_is_not_root() { |
762 | 1 | let mut tree = ForkTree::new(); |
763 | 1 | |
764 | 1 | let node0 = tree.insert(None, ()); |
765 | 1 | let node1 = tree.insert(Some(node0), ()); |
766 | 1 | let node2 = tree.insert(Some(node0), ()); |
767 | 1 | |
768 | 1 | let (ascend, descend) = tree.ascend_and_descend(node1, node2); |
769 | 1 | assert_eq!(ascend.collect::<Vec<_>>(), vec![node1]); |
770 | 1 | assert_eq!(descend.collect::<Vec<_>>(), vec![node2]); |
771 | | |
772 | 1 | assert_eq!(tree.common_ancestor(node1, node2), Some(node0)); |
773 | 1 | } |
774 | | |
775 | | #[test] |
776 | 1 | fn ascend_descend_when_common_ancestor_is_root() { |
777 | 1 | let mut tree = ForkTree::new(); |
778 | 1 | |
779 | 1 | let node0 = tree.insert(None, ()); |
780 | 1 | let node1 = tree.insert(None, ()); |
781 | 1 | |
782 | 1 | let (ascend, descend) = tree.ascend_and_descend(node0, node1); |
783 | 1 | assert_eq!(ascend.collect::<Vec<_>>(), vec![node0]); |
784 | 1 | assert_eq!(descend.collect::<Vec<_>>(), vec![node1]); |
785 | | |
786 | 1 | assert_eq!(tree.common_ancestor(node0, node1), None); |
787 | 1 | } |
788 | | |
789 | | // TODO: add more testing for the order of elements returned by `prune_ancestors` |
790 | | } |