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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
extern crate alloc;
use alloc::collections::BTreeSet;
/// One station's received dots, compactly: the gap-free prefix `1..=floor` plus
/// the exceptions received above it.
///
/// Private to the dot-set module tree. The codec reads the compact form
/// directly to emit maximal runs, and rebuilds it from a decoded frame.
#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
pub(super) struct StationDots {
/// The greatest `n` such that every dot `1..=n` has been received.
pub(super) floor: u64,
/// Dots received out of order, all `> floor + 1` (a dot at `floor + 1` is
/// absorbed into the floor immediately, so the form is canonical).
pub(super) above: BTreeSet<u64>,
}
impl StationDots {
/// Whether `dot` has been received: inside the prefix or among the
/// exceptions.
pub(super) fn contains(&self, dot: u64) -> bool {
dot <= self.floor || self.above.contains(&dot)
}
/// Whether this station's dots contain every dot the `other` station holds,
/// computed on the floors and exception runs without enumerating a dot.
///
/// `other`'s dots are its prefix `1..=other.floor` and its parked
/// exceptions. The prefix is covered iff either `other.floor <= self.floor`
/// (self's own prefix already spans it) or every dot of the tail
/// `self.floor+1 ..= other.floor` sits in self's exceptions, which is a
/// range *count* against `above` rather than a per-dot probe. Each of
/// `other`'s exceptions must then lie at or below self's floor or among
/// self's exceptions.
pub(super) fn covers(&self, other: &Self) -> bool {
// The prefix tail self must fill from its exceptions to cover other's
// deeper floor. When other's floor is the shallower one the tail is
// empty and the prefix is covered outright.
if other.floor > self.floor {
let tail_len = other.floor - self.floor;
// Every dot in `(self.floor, other.floor]` must be a self exception;
// count them by range instead of enumerating the span. `above` holds
// only dots `> floor`, so the lower bound is `self.floor + 1`.
let filled = self
.above
.range(self.floor.saturating_add(1)..=other.floor)
.count();
if u64::try_from(filled).unwrap_or(u64::MAX) != tail_len {
return false;
}
}
// Other's exceptions all lie strictly above other's floor, hence strictly
// above the shared prefix; each must be held by self directly.
other.above.iter().all(|&dot| self.contains(dot))
}
/// The greatest received dot: the last exception, or the floor when none.
pub(super) fn high_water(&self) -> u64 {
self.above.last().copied().unwrap_or(self.floor)
}
/// Folds any newly contiguous exceptions into the floor, restoring the
/// canonical (maximally absorbed) form.
pub(super) fn absorb(&mut self) {
while self.floor < u64::MAX && self.above.remove(&(self.floor + 1)) {
self.floor += 1;
}
}
/// Removes one dot, returning whether it was held. The *store-role* write
/// (the survivor law shrinks a presence store); the receipt-role have-set
/// stays grow-only, which is why this is not public.
///
/// Removing an exception is an `O(log)` set removal. Removing a dot at or
/// below the floor retracts the floor to `dot - 1` and parks the rest of
/// the old prefix (`dot + 1 ..= floor`) as exceptions: `O(floor - dot)`
/// once, the compact form's honest price for a mid-prefix removal (the
/// pure survivor rebuild pays the same shape on *every* fold instead).
/// Canonical form is preserved: every parked dot is `> floor + 1` after
/// the retraction, and absorption cannot apply (the removed dot's slot is
/// the gap).
pub(super) fn remove(&mut self, dot: u64) -> bool {
if dot > self.floor {
return self.above.remove(&dot);
}
if dot == 0 || self.floor == 0 {
return false;
}
// Guarded so the parked range never computes `u64::MAX + 1`: at
// `dot == floor` the range is empty, and at the ceiling the
// unguarded `dot + 1` would overflow (wrap to an unbounded extend
// in release). The `absorb` guard's mirror.
if dot < self.floor {
self.above.extend((dot + 1)..=self.floor);
}
self.floor = dot - 1;
true
}
/// The union of two stations' dots: the larger prefix plus every exception
/// it does not already cover, re-absorbed.
pub(super) fn merge(&self, other: &Self) -> Self {
let floor = self.floor.max(other.floor);
let above = self
.above
.iter()
.chain(other.above.iter())
.copied()
.filter(|&dot| dot > floor)
.collect();
let mut merged = Self { floor, above };
merged.absorb();
merged
}
/// The intersection of two stations' dots: dots held by both, re-absorbed.
///
/// The shared floor is the meet of the two floors (every dot at or below it
/// is on both sides). A dot strictly above it survives iff both stations
/// hold it, which splits into two disjoint, individually sorted sources:
/// the exceptions both sides park (a linear merge of the two sorted `above`
/// sets), and the *cross* dots one side parks inside the other's deeper
/// prefix (`floor < dot <= peer.floor`, a prefix range of that side's
/// `above`). A cross dot lies at or below the peer's floor while a
/// both-parked dot lies strictly above it, so the two sources never overlap
/// and their concatenation is duplicate-free. This replaces the per-element
/// `contains` probe (a `BTreeSet` lookup each) of the earlier two filtered
/// scans with a single linear intersection plus a range slice. Split out of
/// [`DotSet::intersect`](crate::metis::DotSet::intersect) so the causal
/// kernel can reuse the meet on a single station without materializing a
/// whole `DotSet`.
pub(super) fn intersect(&self, other: &Self) -> Self {
let floor = self.floor.min(other.floor);
// The in-order-receipt common case: neither side parks an exception, so
// the meet is the bare floor with nothing above and no absorb pass. This
// skips the intersection-and-range iterator setup, which is pure overhead
// when both `above` sets are empty (the deep-floor hot path).
if self.above.is_empty() && other.above.is_empty() {
return Self {
floor,
above: BTreeSet::new(),
};
}
// At most one side sits below the other's floor, so at most one carries
// *cross* dots: exceptions it parks inside the peer's deeper prefix
// (`floor < dot <= peer.floor`). Only the side whose floor equals the
// meet can have them, and only when the peer's floor is strictly deeper;
// otherwise the range is empty. `range` panics on an inverted bound, so
// the guard is load-bearing, not decorative.
let both = self.above.intersection(&other.above).copied();
// The shallower side (if any) contributes its exceptions that sit inside
// the deeper side's prefix, `floor + 1 ..= deeper_floor`; equal floors
// contribute none. Naming the shallow side keeps the one `range` call.
let cross = match self.floor.cmp(&other.floor) {
core::cmp::Ordering::Less => Some((&self.above, other.floor)),
core::cmp::Ordering::Greater => Some((&other.above, self.floor)),
core::cmp::Ordering::Equal => None,
}
.map(|(shallow, deeper_floor)| shallow.range(floor.saturating_add(1)..=deeper_floor));
let above = both.chain(cross.into_iter().flatten().copied()).collect();
let mut common = Self { floor, above };
common.absorb();
common
}
}