boarddown_core/crdt/
vector.rs

1use serde::{Deserialize, Serialize};
2use std::collections::HashMap;
3
4#[derive(Debug, Clone)]
5pub struct VectorClock {
6    clock: HashMap<u64, u64>,
7}
8
9impl VectorClock {
10    pub fn new() -> Self {
11        Self {
12            clock: HashMap::new(),
13        }
14    }
15
16    pub fn get(&self, client_id: u64) -> u64 {
17        self.clock.get(&client_id).copied().unwrap_or(0)
18    }
19
20    pub fn increment(&mut self, client_id: u64) -> u64 {
21        let next = self.get(client_id) + 1;
22        self.clock.insert(client_id, next);
23        next
24    }
25
26    pub fn merge(&self, other: &Self) -> Self {
27        let mut result = self.clone();
28        for (client_id, seq) in &other.clock {
29            let current = result.get(*client_id);
30            if seq > &current {
31                result.clock.insert(*client_id, *seq);
32            }
33        }
34        result
35    }
36
37    pub fn happens_before(&self, other: &Self) -> bool {
38        let all_keys: std::collections::HashSet<_> = self.clock.keys().chain(other.clock.keys()).collect();
39        
40        let mut has_strictly_less = false;
41        
42        for key in all_keys {
43            let self_val = self.get(*key);
44            let other_val = other.get(*key);
45            
46            if self_val > other_val {
47                return false;
48            }
49            if self_val < other_val {
50                has_strictly_less = true;
51            }
52        }
53        
54        has_strictly_less
55    }
56
57    pub fn is_concurrent(&self, other: &Self) -> bool {
58        !self.happens_before(other) && !other.happens_before(self)
59    }
60}
61
62impl Default for VectorClock {
63    fn default() -> Self {
64        Self::new()
65    }
66}
67
68impl Serialize for VectorClock {
69    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
70    where
71        S: serde::Serializer,
72    {
73        self.clock.serialize(serializer)
74    }
75}
76
77impl<'de> Deserialize<'de> for VectorClock {
78    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
79    where
80        D: serde::Deserializer<'de>,
81    {
82        let clock: HashMap<u64, u64> = HashMap::deserialize(deserializer)?;
83        Ok(Self { clock })
84    }
85}
boarddown_core/crdt/vector.rs

boarddown_core/crdt/
vector.rs
