atomr_cluster/
vector_clock.rs

1//! Vector clock.
2
3use std::cmp::Ordering;
4use std::collections::BTreeMap;
5
6use serde::{Deserialize, Serialize};
7
8#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Default)]
9pub struct VectorClock {
10    pub versions: BTreeMap<String, u64>,
11}
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14#[non_exhaustive]
15pub enum VectorRelation {
16    Before,
17    After,
18    Same,
19    Concurrent,
20}
21
22impl VectorClock {
23    pub fn new() -> Self {
24        Self::default()
25    }
26
27    pub fn tick(&mut self, node: &str) {
28        *self.versions.entry(node.to_string()).or_insert(0) += 1;
29    }
30
31    pub fn merge(&self, other: &Self) -> Self {
32        let mut out = self.clone();
33        for (k, v) in &other.versions {
34            let entry = out.versions.entry(k.clone()).or_insert(0);
35            if *v > *entry {
36                *entry = *v;
37            }
38        }
39        out
40    }
41
42    pub fn compare(&self, other: &Self) -> VectorRelation {
43        let keys: std::collections::BTreeSet<_> = self.versions.keys().chain(other.versions.keys()).collect();
44        let mut a_le = true;
45        let mut b_le = true;
46        for k in keys {
47            let a = self.versions.get(k.as_str()).copied().unwrap_or(0);
48            let b = other.versions.get(k.as_str()).copied().unwrap_or(0);
49            match a.cmp(&b) {
50                Ordering::Less => {} // a still ≤
51                Ordering::Greater => a_le = false,
52                Ordering::Equal => {}
53            }
54            match a.cmp(&b) {
55                Ordering::Greater => {} // b still ≤
56                Ordering::Less => b_le = false,
57                Ordering::Equal => {}
58            }
59        }
60        match (a_le, b_le) {
61            (true, true) => VectorRelation::Same,
62            (true, false) => VectorRelation::Before,
63            (false, true) => VectorRelation::After,
64            (false, false) => VectorRelation::Concurrent,
65        }
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn tick_and_compare() {
75        let mut a = VectorClock::new();
76        let mut b = VectorClock::new();
77        a.tick("A");
78        b.tick("A");
79        assert_eq!(a.compare(&b), VectorRelation::Same);
80        a.tick("A");
81        assert_eq!(b.compare(&a), VectorRelation::Before);
82        b.tick("B");
83        assert_eq!(a.compare(&b), VectorRelation::Concurrent);
84    }
85
86    #[test]
87    fn merge_is_pointwise_max() {
88        let mut a = VectorClock::new();
89        let mut b = VectorClock::new();
90        a.tick("A");
91        a.tick("A");
92        b.tick("A");
93        b.tick("B");
94        let m = a.merge(&b);
95        assert_eq!(m.versions["A"], 2);
96        assert_eq!(m.versions["B"], 1);
97    }
98}
atomr_cluster/vector_clock.rs

atomr_cluster/
vector_clock.rs
