crdt_sample/
dotcontext.rs

1use std::cmp::max;
2use std::collections::{HashMap, HashSet};
3use std::hash::Hash;
4use std::fmt::Debug;
5use std::mem::size_of;
6
7/// Tries to optimize mapping.
8/// Source: https://github.com/CBaquero/delta-enabled-crdts/blob/master/delta-crdts.cc
9#[derive(Debug, PartialEq, Eq, Clone)]
10pub struct DotContext<K: PartialEq + Eq + Hash + Clone + Debug> {
11    pub cc: HashMap<K, i64>,   // Compact Causal Context
12    pub dc: HashSet<(K, i64)>, // Dot Cloud
13}
14
15impl<K: PartialEq + Eq + Hash + Clone + Debug> DotContext<K> {
16    pub fn new() -> Self {
17        Self {
18            cc: HashMap::new(),
19            dc: HashSet::new(),
20        }
21    }
22
23    pub fn get_bytes_size(&self) -> usize {
24        let mut total_size = 0; 
25        for (_, _) in self.cc.iter() {
26            total_size += size_of::<K>(); 
27            total_size += size_of::<i64>(); 
28        }
29
30        for _ in self.dc.iter(){
31            total_size += size_of::<K>(); 
32            total_size += size_of::<i64>(); 
33        }
34        total_size
35    }
36
37    /// Verifies if the received argument was already seen.
38    pub fn dotin(&self, d: &(K, i64)) -> bool {
39        if let Some(&v) = self.cc.get(&d.0) {
40            if d.1 <= v {
41                return true;
42            }
43        } else if let Some(_) = self.dc.get(d) {
44            return true;
45        }
46        return false;
47    }
48
49    /// Creates a new dot considering that the dots are already compact.
50    pub fn makedot(&mut self, id: &K) -> (K, i64) {
51        match self.cc.get_mut(id) {
52            // No entry, then create one.
53            None => {self.cc.insert(id.clone(), 1);},
54            // There is an entry, then update it.
55            Some(v) => {*v += 1;}
56        }
57        return (id.clone(), self.cc.get(id).unwrap().clone());
58    }
59
60    /// Adds a dot to the struct.
61    pub fn insert_dot(&mut self, dot: &(K, i64), compact: Option<bool>) {
62        self.dc.insert(dot.clone());
63        match compact {
64            Some(true) => self.compact(),
65            Some(false) => return,
66            None => self.compact(),
67        }
68    }
69
70    pub fn join(&mut self, other: &Self) {
71        for (other_k, &other_val) in other.cc.iter() {
72            
73            match self.cc.get_mut(&other_k) {
74                // No previous record, then insert. 
75                None => {
76                    self.cc.insert(other_k.clone(), other_val);
77                }, 
78                // Get maximum between both.
79                Some(self_val) => {
80                    *self_val = max(*self_val, other_val);
81                }
82            }
83        }
84
85        self.union_dc(&other.dc);
86        self.compact();
87    }
88
89    /// Performs the union between the self.dc and the one received. 
90    fn union_dc(&mut self, dc: &HashSet<(K, i64)>) {
91        for (id, val) in dc.iter() {
92            self.dc.insert((id.clone(), val.clone()));
93        }
94    }
95
96    pub fn compact(&mut self) {
97        let mut repeat: bool;
98        loop {
99            repeat = false;
100            self.dc = self
101                .dc
102                .drain()
103                .filter(|(id, dc_count)| {
104                    match self.cc.get_mut(id) {
105                        // No CC entry.
106                        None => {
107                            // If starts, with 1 (not decoupled), can compact.
108                            if *dc_count == 1 { 
109                                self.cc.insert(id.clone(), *dc_count);
110                                repeat = true;
111                                return false; // Do not re-add it to dc.
112                            }
113                        }
114                        // There is already a CC entry.
115                        Some(cc_count) => {
116                            // Contiguos, compact.
117                            if *cc_count == *dc_count - 1 {
118                                *cc_count += 1;
119                                repeat = true;
120                                return false; // Do not re-add it to dc.
121                            }
122                            // Has dc_count is already considered in cc.
123                            else if *cc_count >= *dc_count {
124                                return false; // Do not re-add it to dc.
125                                              // No extra compact opportunities. Flag untoched.
126                            }
127                        }
128                    }
129                    return true; // cc_count <= dc_count.
130                })
131                .collect();
132
133            if !repeat {
134                break;
135            }
136        }
137    }
138
139}
crdt_sample/dotcontext.rs

crdt_sample/
dotcontext.rs
