1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
pub use crate::clock::Slot;
use bv::BitVec;
#[repr(C)]
#[derive(Serialize, Deserialize, PartialEq, Debug)]
pub struct SlotHistory {
pub bits: BitVec<u64>,
pub next_slot: Slot,
}
impl Default for SlotHistory {
fn default() -> Self {
let mut bits = BitVec::new_fill(false, MAX_ENTRIES);
bits.set(0, true);
Self { bits, next_slot: 1 }
}
}
pub const MAX_ENTRIES: u64 = 1024 * 1024;
#[derive(PartialEq, Debug)]
pub enum Check {
Future,
TooOld,
Found,
NotFound,
}
impl SlotHistory {
pub fn add(&mut self, slot: Slot) {
for skipped in self.next_slot..slot {
self.bits.set(skipped % MAX_ENTRIES, false);
}
self.bits.set(slot % MAX_ENTRIES, true);
self.next_slot = slot + 1;
}
pub fn check(&self, slot: Slot) -> Check {
if slot >= self.next_slot {
Check::Future
} else if self.next_slot - slot > MAX_ENTRIES {
Check::TooOld
} else if self.bits.get(slot % MAX_ENTRIES) {
Check::Found
} else {
Check::NotFound
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
let mut slot_history = SlotHistory::default();
slot_history.add(2);
assert_eq!(slot_history.check(0), Check::Found);
assert_eq!(slot_history.check(1), Check::NotFound);
for i in 3..MAX_ENTRIES {
assert_eq!(slot_history.check(i), Check::Future);
}
slot_history.add(MAX_ENTRIES);
assert_eq!(slot_history.check(0), Check::TooOld);
assert_eq!(slot_history.check(1), Check::NotFound);
assert_eq!(slot_history.check(2), Check::Found);
}
}