1use smallvec::SmallVec;
  2use std::cmp::{self, Ordering};
  3use std::ops::{Add, AddAssign};
  4
  5pub type ReplicaId = u16;
  6pub type Seq = u32;
  7
  8#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq, Ord, PartialOrd)]
  9pub struct Local {
 10    pub replica_id: ReplicaId,
 11    pub value: Seq,
 12}
 13
 14#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
 15pub struct Lamport {
 16    pub value: Seq,
 17    pub replica_id: ReplicaId,
 18}
 19
 20impl Local {
 21    pub fn new(replica_id: ReplicaId) -> Self {
 22        Self {
 23            replica_id,
 24            value: 1,
 25        }
 26    }
 27
 28    pub fn tick(&mut self) -> Self {
 29        let timestamp = *self;
 30        self.value += 1;
 31        timestamp
 32    }
 33
 34    pub fn observe(&mut self, timestamp: Self) {
 35        if timestamp.replica_id == self.replica_id {
 36            self.value = cmp::max(self.value, timestamp.value + 1);
 37        }
 38    }
 39}
 40
 41impl<'a> Add<&'a Self> for Local {
 42    type Output = Local;
 43
 44    fn add(self, other: &'a Self) -> Self::Output {
 45        cmp::max(&self, other).clone()
 46    }
 47}
 48
 49impl<'a> AddAssign<&'a Local> for Local {
 50    fn add_assign(&mut self, other: &Self) {
 51        if *self < *other {
 52            *self = other.clone();
 53        }
 54    }
 55}
 56
 57#[derive(Clone, Debug, Default, Hash, Eq, PartialEq)]
 58pub struct Global(SmallVec<[Local; 3]>);
 59
 60impl Global {
 61    pub fn new() -> Self {
 62        Self::default()
 63    }
 64
 65    pub fn get(&self, replica_id: ReplicaId) -> Seq {
 66        self.0
 67            .iter()
 68            .find(|t| t.replica_id == replica_id)
 69            .map_or(0, |t| t.value)
 70    }
 71
 72    pub fn observe(&mut self, timestamp: Local) {
 73        if let Some(entry) = self
 74            .0
 75            .iter_mut()
 76            .find(|t| t.replica_id == timestamp.replica_id)
 77        {
 78            entry.value = cmp::max(entry.value, timestamp.value);
 79        } else {
 80            self.0.push(timestamp);
 81        }
 82    }
 83
 84    pub fn join(&mut self, other: &Self) {
 85        for timestamp in other.0.iter() {
 86            self.observe(*timestamp);
 87        }
 88    }
 89
 90    pub fn meet(&mut self, other: &Self) {
 91        for timestamp in other.0.iter() {
 92            if let Some(entry) = self
 93                .0
 94                .iter_mut()
 95                .find(|t| t.replica_id == timestamp.replica_id)
 96            {
 97                entry.value = cmp::min(entry.value, timestamp.value);
 98            } else {
 99                self.0.push(*timestamp);
100            }
101        }
102    }
103
104    pub fn observed(&self, timestamp: Local) -> bool {
105        self.get(timestamp.replica_id) >= timestamp.value
106    }
107
108    pub fn changed_since(&self, other: &Self) -> bool {
109        self.0.iter().any(|t| t.value > other.get(t.replica_id))
110    }
111}
112
113impl PartialOrd for Global {
114    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
115        let mut global_ordering = Ordering::Equal;
116
117        for timestamp in self.0.iter().chain(other.0.iter()) {
118            let ordering = self
119                .get(timestamp.replica_id)
120                .cmp(&other.get(timestamp.replica_id));
121            if ordering != Ordering::Equal {
122                if global_ordering == Ordering::Equal {
123                    global_ordering = ordering;
124                } else if ordering != global_ordering {
125                    return None;
126                }
127            }
128        }
129
130        Some(global_ordering)
131    }
132}
133
134impl Lamport {
135    pub fn new(replica_id: ReplicaId) -> Self {
136        Self {
137            value: 1,
138            replica_id,
139        }
140    }
141
142    pub fn tick(&mut self) -> Self {
143        let timestamp = *self;
144        self.value += 1;
145        timestamp
146    }
147
148    pub fn observe(&mut self, timestamp: Self) {
149        self.value = cmp::max(self.value, timestamp.value) + 1;
150    }
151}