s2n_quic_core/interval_set/
interval.rs

1// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
2// SPDX-License-Identifier: Apache-2.0
3
4use super::IntervalSetError;
5use core::{
6    cmp::Ordering,
7    fmt,
8    ops::{Bound, Range, RangeBounds, RangeInclusive},
9};
10
11#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
12pub struct Interval<T> {
13    pub(super) start: T,
14    pub(super) end: T,
15}
16
17impl<T: IntervalBound> Interval<T> {
18    pub fn from_range_bounds<B: RangeBounds<T>>(bounds: B) -> Result<Self, IntervalSetError> {
19        let start = match bounds.start_bound() {
20            Bound::Included(start) => *start,
21            Bound::Excluded(start) => start.step_down().ok_or(IntervalSetError::InvalidInterval)?,
22            _ => return Err(IntervalSetError::InvalidInterval),
23        };
24
25        let end = match bounds.end_bound() {
26            Bound::Included(end) => *end,
27            Bound::Excluded(end) => end.step_down().ok_or(IntervalSetError::InvalidInterval)?,
28            _ => return Err(IntervalSetError::InvalidInterval),
29        };
30
31        let interval = Self { start, end };
32
33        if interval.is_valid() {
34            Ok(interval)
35        } else {
36            Err(IntervalSetError::InvalidInterval)
37        }
38    }
39
40    #[inline]
41    pub fn start_inclusive(&self) -> T {
42        self.start
43    }
44
45    #[inline]
46    pub fn start_exclusive(&self) -> T {
47        self.start.step_down_saturating()
48    }
49
50    #[inline]
51    pub fn end_inclusive(&self) -> T {
52        self.end
53    }
54
55    #[inline]
56    pub fn end_exclusive(&self) -> T {
57        self.end.step_up_saturating()
58    }
59
60    #[inline]
61    pub fn len(&self) -> usize {
62        // Interval always has at least 1
63        let interval_base_len = 1;
64        interval_base_len + self.start.steps_between(&self.end)
65    }
66
67    #[inline]
68    pub fn set_len(&mut self, len: usize) {
69        debug_assert_ne!(len, 0, "Intervals cannot be 0 length");
70        self.end = self.start.steps_between_len(len);
71    }
72
73    #[inline]
74    pub fn is_empty(&self) -> bool {
75        // Interval always has at least 1
76        false
77    }
78
79    #[inline]
80    pub fn is_valid(&self) -> bool {
81        self.end >= self.start
82    }
83
84    #[inline]
85    pub(crate) fn should_coalesce(&self, other: &Self) -> bool {
86        self.start <= other.end_exclusive()
87    }
88}
89
90impl<T: IntervalBound> IntoIterator for &Interval<T> {
91    type IntoIter = Interval<T>;
92    type Item = T;
93
94    #[inline]
95    fn into_iter(self) -> Self::IntoIter {
96        *self
97    }
98}
99
100impl<T> RangeBounds<T> for Interval<T> {
101    #[inline]
102    fn start_bound(&self) -> Bound<&T> {
103        Bound::Included(&self.start)
104    }
105
106    #[inline]
107    fn end_bound(&self) -> Bound<&T> {
108        Bound::Included(&self.end)
109    }
110}
111
112impl<T> RangeBounds<T> for &Interval<T> {
113    #[inline]
114    fn start_bound(&self) -> Bound<&T> {
115        Bound::Included(&self.start)
116    }
117
118    #[inline]
119    fn end_bound(&self) -> Bound<&T> {
120        Bound::Included(&self.end)
121    }
122}
123
124impl<T: Ord> PartialEq<T> for Interval<T> {
125    #[inline]
126    fn eq(&self, value: &T) -> bool {
127        self.partial_cmp(value) == Some(Ordering::Equal)
128    }
129}
130
131impl<T: Ord> PartialOrd<T> for Interval<T> {
132    #[inline]
133    fn partial_cmp(&self, value: &T) -> Option<Ordering> {
134        use Ordering::*;
135        Some(match (self.start.cmp(value), self.end.cmp(value)) {
136            (Equal, _) => Equal,
137            (_, Equal) => Equal,
138            (Greater, Less) => Equal,
139            (Less, Greater) => Equal,
140            (Less, Less) => Less,
141            (Greater, Greater) => Greater,
142        })
143    }
144}
145
146impl<T: IntervalBound> From<&Interval<T>> for Interval<T> {
147    #[inline]
148    fn from(interval: &Interval<T>) -> Self {
149        *interval
150    }
151}
152
153macro_rules! range_impls {
154    ($range_ty:ident, $into:expr, $from:expr) => {
155        impl<T: IntervalBound> From<Interval<T>> for $range_ty<T> {
156            #[inline]
157            fn from(range: Interval<T>) -> Self {
158                #[allow(clippy::redundant_closure_call)]
159                ($into)(range)
160            }
161        }
162
163        impl<T: IntervalBound> From<&Interval<T>> for $range_ty<T> {
164            #[inline]
165            fn from(range: &Interval<T>) -> Self {
166                #[allow(clippy::redundant_closure_call)]
167                ($into)(*range)
168            }
169        }
170
171        impl<T: IntervalBound> From<$range_ty<T>> for Interval<T> {
172            #[inline]
173            fn from(range: $range_ty<T>) -> Self {
174                #[allow(clippy::redundant_closure_call)]
175                ($from)(range)
176            }
177        }
178
179        impl<'a, T: IntervalBound> From<&'a $range_ty<T>> for Interval<T> {
180            #[inline]
181            fn from(range: &'a $range_ty<T>) -> Self {
182                #[allow(clippy::redundant_closure_call)]
183                ($from)(range.clone())
184            }
185        }
186
187        impl<T: IntervalBound> PartialEq<$range_ty<T>> for Interval<T> {
188            #[inline]
189            fn eq(&self, other: &$range_ty<T>) -> bool {
190                self.partial_cmp(other) == Some(Ordering::Equal)
191            }
192        }
193
194        impl<T: IntervalBound> PartialEq<$range_ty<T>> for &Interval<T> {
195            #[inline]
196            fn eq(&self, other: &$range_ty<T>) -> bool {
197                self.partial_cmp(other) == Some(Ordering::Equal)
198            }
199        }
200
201        impl<T: IntervalBound> PartialOrd<$range_ty<T>> for Interval<T> {
202            #[inline]
203            fn partial_cmp(&self, other: &$range_ty<T>) -> Option<Ordering> {
204                let other: Self = other.into();
205                self.partial_cmp(&other)
206            }
207        }
208
209        impl<T: IntervalBound> PartialOrd<$range_ty<T>> for &Interval<T> {
210            #[inline]
211            fn partial_cmp(&self, other: &$range_ty<T>) -> Option<Ordering> {
212                let other: Interval<_> = other.into();
213                (*self).partial_cmp(&other)
214            }
215        }
216    };
217}
218
219range_impls!(
220    Range,
221    |interval: Interval<_>| interval.start..interval.end_exclusive(),
222    |range: Range<_>| Self {
223        start: range.start,
224        end: range.end.step_down_saturating(),
225    }
226);
227
228range_impls!(
229    RangeInclusive,
230    |interval: Interval<_>| interval.start..=interval.end,
231    |range: RangeInclusive<_>| {
232        let (start, end) = range.into_inner();
233        Self { start, end }
234    }
235);
236
237impl<T: IntervalBound> Iterator for Interval<T> {
238    type Item = T;
239
240    #[inline]
241    fn next(&mut self) -> Option<T> {
242        let current = self.start;
243        if current > self.end {
244            return None;
245        }
246        if let Some(next) = current.step_up() {
247            self.start = next;
248        } else {
249            self.end = current.step_down()?;
250        }
251        Some(current)
252    }
253}
254
255impl<T: IntervalBound> DoubleEndedIterator for Interval<T> {
256    #[inline]
257    fn next_back(&mut self) -> Option<T> {
258        let current = self.end;
259        if current < self.start {
260            return None;
261        }
262        if let Some(next) = current.step_down() {
263            self.end = next;
264        } else {
265            self.start = current.step_up()?;
266        }
267        Some(current)
268    }
269}
270
271impl<T: fmt::Debug> fmt::Debug for Interval<T> {
272    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
273        ((&self.start)..=(&self.end)).fmt(f)
274    }
275}
276
277pub trait IntervalBound: Copy + Ord + Sized {
278    fn step_up(self) -> Option<Self>;
279    fn step_down(self) -> Option<Self>;
280    fn steps_between(&self, upper: &Self) -> usize;
281    fn steps_between_len(&self, len: usize) -> Self;
282
283    fn step_up_saturating(self) -> Self {
284        self.step_up().unwrap_or(self)
285    }
286
287    fn step_down_saturating(self) -> Self {
288        self.step_down().unwrap_or(self)
289    }
290}
291
292macro_rules! integer_bounds {
293    ($type:ident) => {
294        impl IntervalBound for $type {
295            #[inline]
296            fn step_up(self) -> Option<Self> {
297                self.checked_add(1)
298            }
299
300            #[inline]
301            fn step_down(self) -> Option<Self> {
302                self.checked_sub(1)
303            }
304
305            #[inline]
306            fn steps_between(&self, upper: &Self) -> usize {
307                use core::convert::TryInto;
308                (upper - self).try_into().unwrap_or(usize::MAX)
309            }
310
311            #[inline]
312            fn steps_between_len(&self, len: usize) -> Self {
313                use core::convert::TryInto;
314                let len: Self = (len - 1).try_into().unwrap();
315                *self + len
316            }
317        }
318    };
319}
320
321integer_bounds!(u8);
322integer_bounds!(i8);
323integer_bounds!(u16);
324integer_bounds!(i16);
325integer_bounds!(u32);
326integer_bounds!(i32);
327integer_bounds!(u64);
328integer_bounds!(i64);
329integer_bounds!(u128);
330integer_bounds!(i128);
331integer_bounds!(usize);
332integer_bounds!(isize);
333
334use crate::{packet::number::PacketNumber, varint::VarInt};
335
336impl IntervalBound for VarInt {
337    #[inline]
338    fn step_up(self) -> Option<Self> {
339        self.checked_add(Self::from_u8(1))
340    }
341
342    #[inline]
343    fn step_down(self) -> Option<Self> {
344        self.checked_sub(Self::from_u8(1))
345    }
346
347    #[inline]
348    fn steps_between(&self, upper: &Self) -> usize {
349        <u64 as IntervalBound>::steps_between(self, upper)
350    }
351
352    #[inline]
353    fn steps_between_len(&self, len: usize) -> Self {
354        *self + (len - 1)
355    }
356}
357
358impl IntervalBound for PacketNumber {
359    #[inline]
360    fn step_up(self) -> Option<Self> {
361        self.next()
362    }
363
364    #[inline]
365    fn step_down(self) -> Option<Self> {
366        let space = self.space();
367        let value = PacketNumber::as_varint(self);
368        Some(space.new_packet_number(value.step_down()?))
369    }
370
371    #[inline]
372    fn steps_between(&self, upper: &Self) -> usize {
373        let lower = PacketNumber::as_varint(*self);
374        let upper = PacketNumber::as_varint(*upper);
375        lower.steps_between(&upper)
376    }
377
378    #[inline]
379    fn steps_between_len(&self, len: usize) -> Self {
380        let start = PacketNumber::as_varint(*self);
381        let end = start.steps_between_len(len);
382        self.space().new_packet_number(end)
383    }
384}
s2n_quic_core/interval_set/interval.rs

s2n_quic_core/interval_set/
interval.rs
