quorum_set/quorum/
quorum_set_impl.rs

1use std::collections::BTreeSet;
2
3use crate::Node;
4use crate::QuorumTree;
5use crate::quorum::quorum_set::QuorumSet;
6
7/// Majority quorum implementation for a flat voter set.
8///
9/// A candidate set is accepted when it contains more than half of the IDs in
10/// this `BTreeSet`.
11impl<ID> QuorumSet for BTreeSet<ID>
12where ID: PartialOrd + Ord + Clone + 'static
13{
14    type Id = ID;
15    type Iter = std::collections::btree_set::IntoIter<ID>;
16
17    fn is_quorum<'a, I: Iterator<Item = &'a ID> + Clone>(&self, ids: I) -> bool {
18        let mut count = 0;
19        let limit = self.len();
20        for id in self {
21            if ids.clone().any(|candidate| candidate == id) {
22                count += 2;
23                if count > limit {
24                    return true;
25                }
26            }
27        }
28        false
29    }
30
31    fn ids(&self) -> Self::Iter {
32        self.clone().into_iter()
33    }
34}
35
36/// Joint quorum implementation for multiple flat voter sets.
37///
38/// A candidate set is accepted only when it is a majority quorum in every
39/// member config. `ids()` returns the deduplicated union of all config IDs.
40impl<NID> QuorumSet for Vec<BTreeSet<NID>>
41where NID: PartialOrd + Ord + Clone + 'static
42{
43    type Id = NID;
44    type Iter = std::collections::btree_set::IntoIter<NID>;
45
46    fn is_quorum<'a, I: Iterator<Item = &'a NID> + Clone>(&self, ids: I) -> bool {
47        for config in self {
48            if !config.is_quorum(ids.clone()) {
49                return false;
50            }
51        }
52        true
53    }
54
55    fn ids(&self) -> Self::Iter {
56        let mut ids = BTreeSet::new();
57        for config in self {
58            ids.extend(config.iter().cloned());
59        }
60        ids.into_iter()
61    }
62}
63
64/// Hierarchical quorum implementation for [`QuorumTree`].
65///
66/// Evaluation follows the tree structure. `ids()` returns all leaf IDs once,
67/// even when the same node appears in more than one subtree.
68impl<ID> QuorumSet for QuorumTree<ID>
69where ID: Ord + Clone + 'static
70{
71    type Id = ID;
72    type Iter = std::collections::btree_set::IntoIter<ID>;
73
74    fn is_quorum<'a, I: Iterator<Item = &'a ID> + Clone>(&self, ids: I) -> bool {
75        self.spec.is_quorum(ids)
76    }
77
78    fn ids(&self) -> Self::Iter {
79        let mut ids = BTreeSet::new();
80        collect_tree_ids(self, &mut ids);
81        ids.into_iter()
82    }
83}
84
85fn collect_tree_ids<ID>(tree: &QuorumTree<ID>, ids: &mut BTreeSet<ID>)
86where ID: Ord + Clone {
87    for node in tree.children() {
88        match node {
89            Node::Id(id) => {
90                ids.insert(id.clone());
91            }
92            Node::Subtree(subtree) => {
93                collect_tree_ids(subtree, ids);
94            }
95        }
96    }
97}
quorum_set/quorum/quorum_set_impl.rs

quorum_set/quorum/
quorum_set_impl.rs
