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

quorum_set/quorum/
quorum_set_impl.rs
