vectorclock/
clock.rs

1use std::hash::Hash;
2use std::collections::HashMap;
3use std::collections::hash_map::Entry;
4
5#[derive(Debug, PartialEq, Eq, Copy, Clone)]
6pub enum TemporalRelation {
7    Equal,
8    Caused,
9    EffectOf,
10    Concurrent,
11}
12
13#[derive(PartialEq, Eq, Debug)]
14pub struct VectorClock<HostType: Hash + Eq> {
15    entries: HashMap<HostType, u64>,
16}
17
18impl<HostType: Clone + Hash + Eq> VectorClock<HostType> {
19    pub fn new() -> VectorClock<HostType> {
20        VectorClock {
21            entries: HashMap::new(),
22        }
23    }
24
25    pub fn incremented(&self, host: HostType) -> Self {
26        let mut entries = self.entries.clone();
27
28        match entries.entry(host) {
29            Entry::Vacant(e) => { e.insert(1); },
30            Entry::Occupied(mut e) => {
31                let v = *e.get();
32                e.insert(v + 1);
33            },
34        };
35
36        VectorClock {
37            entries: entries,
38        }
39    }
40
41    pub fn temporal_relation(&self, other: &Self) -> TemporalRelation {
42        if self == other {
43            TemporalRelation::Equal
44        }
45        else if self.superseded_by(other) {
46            TemporalRelation::Caused
47        }
48        else if other.superseded_by(self) {
49            TemporalRelation::EffectOf
50        }
51        else {
52            TemporalRelation::Concurrent
53        }
54    }
55
56    fn superseded_by(&self, other: &Self) -> bool {
57        let mut has_smaller = false;
58
59        for (host, &self_n) in self.entries.iter() {
60            let other_n = *other.entries.get(host).unwrap_or(&0);
61
62            if self_n > other_n {
63                return false;
64            }
65
66            has_smaller = has_smaller || (self_n < other_n);
67        }
68
69        for (host, &other_n) in other.entries.iter() {
70            let self_n = *self.entries.get(host).unwrap_or(&0);
71
72            if self_n > other_n {
73                return false;
74            }
75
76            has_smaller = has_smaller || (self_n < other_n);
77        }
78
79        has_smaller
80    }
81
82    pub fn merge_with(&self, other: &Self) -> Self {
83        let mut entries = self.entries.clone();
84
85        for (host, &other_n) in other.entries.iter() {
86            match entries.entry(host.clone()) {
87                Entry::Vacant(e) => { e.insert(other_n); },
88                Entry::Occupied(mut e) => {
89                    let self_n = *e.get();
90
91                    if other_n > self_n {
92                        e.insert(other_n);
93                    }
94                }
95            }
96        }
97
98        VectorClock {
99            entries: entries,
100        }
101    }
102}
103
104#[cfg(test)]
105mod test {
106    use super::{VectorClock, TemporalRelation};
107
108    type StrVectorClock = VectorClock<&'static str>;
109
110    #[test]
111    fn test_empty_ordering() {
112        let c1 = StrVectorClock::new();
113        let c2 = StrVectorClock::new();
114
115        assert_eq!(c1, c2);
116
117        assert!(c1.temporal_relation(&c2) == TemporalRelation::Equal);
118        assert!(c2.temporal_relation(&c1) == TemporalRelation::Equal);
119    }
120
121    #[test]
122    fn test_incremented_ordering() {
123        let c1 = StrVectorClock::new();
124        let c2 = c1.incremented("A");
125
126        assert!(!(c1 == c2));
127
128        assert!(c1.temporal_relation(&c2) == TemporalRelation::Caused);
129        assert!(c2.temporal_relation(&c1) == TemporalRelation::EffectOf);
130    }
131
132    #[test]
133    fn test_diverged() {
134        let base = StrVectorClock::new();
135        let c1 = base.incremented("A");
136        let c2 = base.incremented("B");
137
138        assert!(!(c1 == c2));
139
140        assert!(c1.temporal_relation(&c2) == TemporalRelation::Concurrent);
141        assert!(c2.temporal_relation(&c1) == TemporalRelation::Concurrent);
142    }
143
144    #[test]
145    fn test_merged() {
146        let base = StrVectorClock::new();
147        let c1 = base.incremented("A");
148        let c2 = base.incremented("B");
149
150        let m = c1.merge_with(&c2);
151
152        assert!(m.temporal_relation(&c1) == TemporalRelation::EffectOf);
153        assert!(c1.temporal_relation(&m) == TemporalRelation::Caused);
154
155        assert!(m.temporal_relation(&c2) == TemporalRelation::EffectOf);
156        assert!(c2.temporal_relation(&m) == TemporalRelation::Caused);
157    }
158}
vectorclock/clock.rs

vectorclock/
clock.rs
