mycelial_crdt/
vclock.rs

1//! VClock and helpers around vclock to simplify some tasks
2//!
3//! # Example
4//!
5//! ```rust
6//! use mycelial_crdt::vclock::{VClock, VClockDiff};
7//!
8//! let mut vclock_0 = VClock::new();
9//! let mut vclock_1 = VClock::new();
10//!
11//! assert_eq!(vclock_0.get_clock(0), 0);
12//! vclock_0.inc(0);
13//! vclock_0.inc(0);
14//! assert_eq!(vclock_0.get_clock(0), 2);
15//!
16//! assert_eq!(vclock_1.get_clock(1), 0);
17//! vclock_1.inc(1);
18//! assert_eq!(vclock_1.get_clock(1), 1);
19//!
20//! // Difference between vclock_0 and vclock_1
21//! let vclock_diff: VClockDiff = (&vclock_0, &vclock_1).into();
22//! assert_eq!(
23//!     vclock_diff.into_iter().map(|(&p, &(s, e))| (p, (s, e))).collect::<Vec<_>>(),
24//!     vec![(0, (0, 2))]
25//! );
26//!
27//! // Difference between vclock_1 and vclock_0
28//! let vclock_diff: VClockDiff = (&vclock_1, &vclock_0).into();
29//! assert_eq!(
30//!     vclock_diff.into_iter().map(|(&p, &(s, e))| (p, (s, e))).collect::<Vec<_>>(),
31//!     vec![(1, (0, 1))]
32//! );
33//! ```
34
35use serde::{Deserialize, Serialize};
36use std::collections::HashMap;
37use std::convert::From;
38
39/// VClock represented as a hashmap where key is a process id and value is current clock value
40#[derive(Debug, PartialEq, Eq, Clone, Serialize, Deserialize)]
41pub struct VClock(HashMap<u64, u64>);
42
43impl VClock {
44    /// Initialize new VClock
45    pub fn new() -> Self {
46        Self(HashMap::new())
47    }
48
49    /// Increment given process clock by 1
50    pub fn inc(&mut self, process: u64) -> u64 {
51        let value = match self.0.get(&process) {
52            Some(&value) => value,
53            None => 0,
54        } + 1;
55        self.0.insert(process, value);
56        value
57    }
58
59    /// Get current clock value for a given process
60    pub fn get_clock(&self, process: u64) -> u64 {
61        self.0.get(&process).map_or(0, |&x| x)
62    }
63
64    /// Peek next process clock value
65    pub fn next_value(&self, process: u64) -> u64 {
66        self.get_clock(process) + 1
67    }
68}
69
70impl Default for VClock {
71    fn default() -> Self {
72        Self::new()
73    }
74}
75
76impl<'a> IntoIterator for &'a VClock {
77    type Item = (&'a u64, &'a u64);
78    type IntoIter = std::collections::hash_map::Iter<'a, u64, u64>;
79
80    fn into_iter(self) -> Self::IntoIter {
81        self.0.iter()
82    }
83}
84
85/// VClockDiff represents difference ranges between 2 vclocks
86#[derive(Debug, PartialEq, Eq)]
87pub struct VClockDiff(HashMap<u64, (u64, u64)>);
88
89impl VClockDiff {
90    /// Initialize empty vclock diff
91    pub fn new() -> Self {
92        Self(HashMap::new())
93    }
94
95    /// Get difference range for a given process
96    pub fn get_range(&self, process: u64) -> Option<(u64, u64)> {
97        self.0.get(&process).copied()
98    }
99
100    /// Insert new range for a given process
101    ///
102    /// Not really used, simplifies tests
103    pub fn insert(&mut self, process: u64, diff: (u64, u64)) {
104        self.0.insert(process, diff);
105    }
106}
107
108impl Default for VClockDiff {
109    fn default() -> Self {
110        Self::new()
111    }
112}
113
114impl<'a> IntoIterator for &'a VClockDiff {
115    type Item = (&'a u64, &'a (u64, u64));
116    type IntoIter = std::collections::hash_map::Iter<'a, u64, (u64, u64)>;
117
118    fn into_iter(self) -> Self::IntoIter {
119        self.0.iter()
120    }
121}
122
123impl From<(&VClock, &VClock)> for VClockDiff {
124    fn from((vclock_left, vclock_right): (&VClock, &VClock)) -> Self {
125        let mut vdiff = VClockDiff::new();
126        for (&process, &clock_left) in vclock_left {
127            let clock_right = vclock_right.get_clock(process);
128            if clock_left > clock_right {
129                vdiff.insert(process, (clock_right, clock_left));
130            };
131        }
132        vdiff
133    }
134}
mycelial_crdt/vclock.rs

mycelial_crdt/
vclock.rs
