ckb_tx_pool/block_assembler/
candidate_uncles.rs

1use ckb_types::core::{BlockNumber, EpochExt, UncleBlockView};
2use std::collections::{BTreeMap, HashSet, btree_map::Entry};
3
4use ckb_snapshot::Snapshot;
5use ckb_store::ChainStore;
6
7#[cfg(not(test))]
8const MAX_CANDIDATE_UNCLES: usize = 128;
9#[cfg(test)]
10pub(crate) const MAX_CANDIDATE_UNCLES: usize = 4;
11
12#[cfg(not(test))]
13const MAX_PER_HEIGHT: usize = 10;
14#[cfg(test)]
15pub(crate) const MAX_PER_HEIGHT: usize = 2;
16
17/// Candidate uncles container
18pub struct CandidateUncles {
19    pub(crate) map: BTreeMap<BlockNumber, HashSet<UncleBlockView>>,
20    count: usize,
21}
22
23impl CandidateUncles {
24    /// Construct new candidate uncles container
25    pub fn new() -> CandidateUncles {
26        CandidateUncles {
27            map: BTreeMap::new(),
28            count: 0,
29        }
30    }
31
32    /// insert new candidate uncles
33    /// If the map did not have this value present, true is returned.
34    /// If the map did have this value present, false is returned.
35    pub fn insert(&mut self, uncle: UncleBlockView) -> bool {
36        let number: BlockNumber = uncle.header().number();
37        if self.count >= MAX_CANDIDATE_UNCLES {
38            let first_key = *self.map.keys().next().expect("length checked");
39            if number > first_key {
40                if let Some(set) = self.map.remove(&first_key) {
41                    self.count -= set.len();
42                }
43            } else {
44                return false;
45            }
46        }
47
48        let set = self.map.entry(number).or_default();
49        if set.len() < MAX_PER_HEIGHT {
50            let ret = set.insert(uncle);
51            if ret {
52                self.count += 1;
53            }
54            ret
55        } else {
56            false
57        }
58    }
59
60    /// Returns the number of elements in the container.
61    pub fn len(&self) -> usize {
62        self.count
63    }
64
65    /// Returns true if the container contains no elements.
66    pub fn is_empty(&self) -> bool {
67        self.len() == 0
68    }
69
70    #[cfg(test)]
71    /// Removing all values.
72    pub fn clear(&mut self) {
73        self.map.clear();
74        self.count = 0;
75    }
76
77    /// Returns true if the container contains a value.
78    pub fn contains(&self, uncle: &UncleBlockView) -> bool {
79        let number: BlockNumber = uncle.header().number();
80        self.map
81            .get(&number)
82            .map(|set| set.contains(uncle))
83            .unwrap_or(false)
84    }
85
86    /// Gets an iterator over the values of the map, in order by block_number.
87    pub fn values(&self) -> impl Iterator<Item = &UncleBlockView> {
88        self.map.values().flat_map(HashSet::iter)
89    }
90
91    /// Removes uncles from the container by specified uncle's number
92    pub fn remove_by_number(&mut self, uncle: &UncleBlockView) -> bool {
93        let number: BlockNumber = uncle.header().number();
94
95        if let Entry::Occupied(mut entry) = self.map.entry(number) {
96            let set = entry.get_mut();
97            if set.remove(uncle) {
98                self.count -= 1;
99                if set.is_empty() {
100                    entry.remove();
101                }
102                return true;
103            }
104        }
105        false
106    }
107
108    /// Get uncles from snapshot and current states.
109    // A block B1 is considered to be the uncle of another block B2 if all of the following conditions are met:
110    // (1) they are in the same epoch, sharing the same difficulty;
111    // (2) height(B2) > height(B1);
112    // (3) B1's parent is either B2's ancestor or embedded in B2 or its ancestors as an uncle;
113    // and (4) B2 is the first block in its chain to refer to B1.
114    pub fn prepare_uncles(
115        &mut self,
116        snapshot: &Snapshot,
117        current_epoch_ext: &EpochExt,
118    ) -> Vec<UncleBlockView> {
119        let candidate_number = snapshot.tip_number() + 1;
120        let epoch_number = current_epoch_ext.number();
121        let max_uncles_num = snapshot.consensus().max_uncles_num();
122        let mut uncles: Vec<UncleBlockView> = Vec::with_capacity(max_uncles_num);
123        let mut removed = Vec::new();
124
125        for uncle in self.values() {
126            if uncles.len() == max_uncles_num {
127                break;
128            }
129            let parent_hash = uncle.header().parent_hash();
130            // we should keep candidate util next epoch
131            if uncle.compact_target() != current_epoch_ext.compact_target()
132                || uncle.epoch().number() != epoch_number
133            {
134                removed.push(uncle.clone());
135            } else if !snapshot.is_main_chain(&uncle.hash())
136                && !snapshot.is_uncle(&uncle.hash())
137                && uncle.number() < candidate_number
138                && (uncles.iter().any(|u| u.hash() == parent_hash)
139                    || snapshot.is_main_chain(&parent_hash)
140                    || snapshot.is_uncle(&parent_hash))
141            {
142                uncles.push(uncle.clone());
143            }
144        }
145
146        for r in removed {
147            self.remove_by_number(&r);
148        }
149        uncles
150    }
151}
152
153impl Default for CandidateUncles {
154    fn default() -> Self {
155        Self::new()
156    }
157}
ckb_tx_pool/block_assembler/candidate_uncles.rs

ckb_tx_pool/block_assembler/
candidate_uncles.rs
