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

quorum_set/quorum/
quorum_set_impl.rs
