quiche/
ranges.rs

1// Copyright (C) 2018-2019, Cloudflare, Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright notice,
9//       this list of conditions and the following disclaimer.
10//
11//     * Redistributions in binary form must reproduce the above copyright
12//       notice, this list of conditions and the following disclaimer in the
13//       documentation and/or other materials provided with the distribution.
14//
15// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27use std::iter::FromIterator;
28use std::ops::Range;
29
30use std::collections::BTreeMap;
31use std::collections::Bound;
32
33use either::Either;
34use smallvec::SmallVec;
35
36const MAX_INLINE_CAPACITY: usize = 4;
37const MIN_TO_INLINE: usize = 2;
38
39/// A sorted collection of non overlapping [`u64`] ranges
40#[derive(Clone, PartialEq, Eq, PartialOrd)]
41pub enum RangeSet {
42    Inline(InlineRangeSet),
43    BTree(BTreeRangeSet),
44}
45
46/// A [`RangeSet`] variant backed by a [`SmallVec`] that is capable of storing
47/// [`MAX_INLINE_CAPACITY`] of ranges without allocation
48#[derive(Clone, PartialEq, Eq, PartialOrd)]
49pub struct InlineRangeSet {
50    inner: SmallVec<[(u64, u64); MAX_INLINE_CAPACITY]>,
51    capacity: usize,
52}
53
54/// A [`RangeSet`] variant backed by a [`BTreeMap`] that is capable of storing
55/// an arbitrary number of ranges
56#[derive(Clone, PartialEq, Eq, PartialOrd)]
57pub struct BTreeRangeSet {
58    inner: BTreeMap<u64, u64>,
59    capacity: usize,
60}
61
62impl RangeSet {
63    /// Create a new [`RangeSet`].
64    ///
65    /// When the length of a [`RangeSet`] overflows `capacity` it will remove
66    /// the smallest range.
67    pub fn new(capacity: usize) -> Self {
68        RangeSet::Inline(InlineRangeSet {
69            inner: Default::default(),
70            capacity,
71        })
72    }
73
74    /// The number of nonoverlapping ranges stored in this [`RangeSet`].
75    pub fn len(&self) -> usize {
76        match self {
77            RangeSet::Inline(set) => set.inner.len(),
78            RangeSet::BTree(set) => set.inner.len(),
79        }
80    }
81
82    /// Converts the inner representation from a BTree to Inline and vice versa
83    /// when the proper conditions are met. Keeps the stored data intact.
84    #[inline(always)]
85    fn fixup(&mut self) {
86        match self {
87            RangeSet::Inline(set) if set.inner.len() == MAX_INLINE_CAPACITY => {
88                let old_inner = std::mem::take(&mut set.inner);
89                *self = RangeSet::BTree(BTreeRangeSet {
90                    inner: old_inner.into_inner().expect("At capacity").into(),
91                    capacity: set.capacity,
92                });
93            },
94
95            RangeSet::BTree(set) if set.inner.len() <= MIN_TO_INLINE => {
96                let old_inner = std::mem::take(&mut set.inner);
97                *self = RangeSet::Inline(InlineRangeSet {
98                    inner: SmallVec::from_iter(old_inner),
99                    capacity: set.capacity,
100                })
101            },
102
103            _ => {},
104        }
105    }
106
107    /// Insert a new [`Range`] into the collection.
108    ///
109    /// If the [`Range`] overlaps with any existing range, it may be merged with
110    /// one or more other [`Range`]s. If following the insertion the number of
111    /// stored ranges overflows capacity, the smalles range will be removed.
112    #[inline]
113    pub fn insert(&mut self, item: Range<u64>) {
114        match self {
115            RangeSet::Inline(set) => set.insert(item),
116            RangeSet::BTree(set) => set.insert(item),
117        }
118
119        self.fixup();
120    }
121
122    /// Iterate over the stored ranges in incremental order.
123    pub fn iter(
124        &self,
125    ) -> impl DoubleEndedIterator<Item = Range<u64>> + ExactSizeIterator + '_
126    {
127        match self {
128            RangeSet::BTree(set) =>
129                Either::Left(set.inner.iter().map(|(k, v)| *k..*v)),
130
131            RangeSet::Inline(set) =>
132                Either::Right(set.inner.iter().map(|(s, e)| *s..*e)),
133        }
134    }
135
136    /// Iterate over every single [`u64`] value covered by the ranges in this
137    /// [`RangeSet`] in incremental order.
138    pub fn flatten(&self) -> impl DoubleEndedIterator<Item = u64> + '_ {
139        match self {
140            RangeSet::BTree(set) =>
141                Either::Left(set.inner.iter().flat_map(|(k, v)| *k..*v)),
142
143            RangeSet::Inline(set) =>
144                Either::Right(set.inner.iter().flat_map(|(s, e)| *s..*e)),
145        }
146    }
147
148    /// The smallest value covered by ranges in this collection.
149    pub fn first(&self) -> Option<u64> {
150        match self {
151            RangeSet::Inline(set) => set.inner.first().map(|(s, _)| *s),
152
153            RangeSet::BTree(set) => set.inner.first_key_value().map(|(k, _)| *k),
154        }
155    }
156
157    /// The largest value covered by ranges in this collection.
158    pub fn last(&self) -> Option<u64> {
159        match self {
160            RangeSet::Inline(set) => set.inner.last().map(|(_, e)| *e - 1),
161
162            RangeSet::BTree(set) =>
163                set.inner.last_key_value().map(|(_, v)| *v - 1),
164        }
165    }
166
167    #[inline]
168    pub fn remove_until(&mut self, largest: u64) {
169        match self {
170            RangeSet::Inline(set) => set.remove_until(largest),
171            RangeSet::BTree(set) => set.remove_until(largest),
172        }
173
174        self.fixup();
175    }
176
177    pub fn push_item(&mut self, item: u64) {
178        self.insert(item..item + 1)
179    }
180}
181
182impl InlineRangeSet {
183    fn insert(&mut self, item: Range<u64>) {
184        let start = item.start;
185        let mut end = item.end;
186        let mut pos = 0;
187
188        loop {
189            match self.inner.get_mut(pos) {
190                Some((s, e)) => {
191                    if start > *e {
192                        // Skip while start is greater than end
193                        pos += 1;
194                        continue;
195                    }
196
197                    if end < *s {
198                        // Inserted range is entirely before this range. Insert
199                        // and return.
200                        if self.inner.len() == self.capacity {
201                            self.inner.remove(0);
202                            pos -= 1;
203                        }
204
205                        self.inner.insert(pos, (start, end));
206                        return;
207                    }
208
209                    // At this point we know (start <= *e)
210                    if start < *s {
211                        // We know we are completely past the previous range, so
212                        // we can simply adjust the lower bound
213                        *s = start;
214                    }
215
216                    if end > *e {
217                        // We adjusted the upper bound of an existing range, we
218                        // must now check it does not overlap with the next range
219                        *e = end;
220                        break;
221                    } else {
222                        return;
223                    }
224                },
225
226                None => {
227                    if self.inner.len() == self.capacity {
228                        self.inner.remove(0);
229                    }
230
231                    self.inner.push((start, end));
232                    return;
233                },
234            }
235        }
236
237        // Merge any newly overlapping ranges
238        while let Some((s, e)) = self.inner.get(pos + 1).copied() {
239            if end < s {
240                // We are done, since the next range is completely disjoint
241                break;
242            }
243
244            let new_e = e.max(end);
245            self.inner[pos].1 = new_e;
246            end = new_e;
247            self.inner.remove(pos + 1);
248        }
249    }
250
251    fn remove_until(&mut self, largest: u64) {
252        while let Some((s, e)) = self.inner.first_mut() {
253            if largest >= *e {
254                self.inner.remove(0);
255                continue;
256            }
257
258            *s = (largest + 1).max(*s);
259            if *s == *e {
260                self.inner.remove(0);
261            }
262
263            break;
264        }
265    }
266}
267
268impl BTreeRangeSet {
269    // TODO: use RangeInclusive
270    fn insert(&mut self, item: Range<u64>) {
271        let mut start = item.start;
272        let mut end = item.end;
273
274        // Check if preceding existing range overlaps with the new one.
275        if let Some(r) = self.prev_to(start) {
276            // New range overlaps with existing range in the set, merge them.
277            if range_overlaps(&r, &item) {
278                self.inner.remove(&r.start);
279
280                start = std::cmp::min(start, r.start);
281                end = std::cmp::max(end, r.end);
282            }
283        }
284
285        // Check if following existing ranges overlap with the new one.
286        while let Some(r) = self.next_to(start) {
287            // Existing range is fully contained in the new range, remove it.
288            if item.contains(&r.start) && item.contains(&r.end) {
289                self.inner.remove(&r.start);
290                continue;
291            }
292
293            // New range doesn't overlap anymore, we are done.
294            if !range_overlaps(&r, &item) {
295                break;
296            }
297
298            // New range overlaps with existing range in the set, merge them.
299            self.inner.remove(&r.start);
300
301            start = std::cmp::min(start, r.start);
302            end = std::cmp::max(end, r.end);
303        }
304
305        if self.inner.len() >= self.capacity {
306            self.inner.pop_first();
307        }
308
309        self.inner.insert(start, end);
310    }
311
312    fn remove_until(&mut self, largest: u64) {
313        let ranges: Vec<Range<u64>> = self
314            .inner
315            .range((Bound::Unbounded, Bound::Included(&largest)))
316            .map(|(&s, &e)| (s..e))
317            .collect();
318
319        for r in ranges {
320            self.inner.remove(&r.start);
321
322            if r.end > largest + 1 {
323                let start = largest + 1;
324                self.insert(start..r.end);
325            }
326        }
327    }
328
329    fn prev_to(&self, item: u64) -> Option<Range<u64>> {
330        self.inner
331            .range((Bound::Unbounded, Bound::Included(item)))
332            .map(|(&s, &e)| (s..e))
333            .next_back()
334    }
335
336    fn next_to(&self, item: u64) -> Option<Range<u64>> {
337        self.inner
338            .range((Bound::Included(item), Bound::Unbounded))
339            .map(|(&s, &e)| (s..e))
340            .next()
341    }
342}
343
344impl Default for RangeSet {
345    fn default() -> Self {
346        RangeSet::Inline(InlineRangeSet {
347            inner: Default::default(),
348            capacity: usize::MAX,
349        })
350    }
351}
352
353// This implements comparison between `BTreeRangeSet` and standard `Range`. The
354// idea is that a `RangeSet` with no gaps (i.e. that only contains a single
355// range) is basically equvalent to a normal `Range` so they should be
356// comparable.
357impl PartialEq<Range<u64>> for RangeSet {
358    fn eq(&self, other: &Range<u64>) -> bool {
359        // If there is more than one range it means that the range set is not
360        // contiguous, so can't be equal to a single range.
361        if self.len() != 1 {
362            return false;
363        }
364
365        // Get the first and only range in the set.
366        let range = self.iter().next().unwrap();
367        range == *other
368    }
369}
370
371impl std::fmt::Debug for RangeSet {
372    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
373        let ranges: Vec<Range<u64>> = self
374            .iter()
375            .map(|mut r| {
376                r.end -= 1;
377                r
378            })
379            .collect();
380
381        write!(f, "{ranges:?}")
382    }
383}
384
385fn range_overlaps(r: &Range<u64>, other: &Range<u64>) -> bool {
386    other.start >= r.start && other.start <= r.end ||
387        other.end >= r.start && other.end <= r.end
388}
389
390#[cfg(test)]
391mod tests {
392    use super::*;
393
394    #[test]
395    fn insert_non_overlapping() {
396        let mut r = RangeSet::default();
397        assert_eq!(r.len(), 0);
398        let empty: &[u64] = &[];
399        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &empty);
400
401        r.insert(4..7);
402        assert_eq!(r.len(), 1);
403        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6]);
404
405        r.insert(9..12);
406        assert_eq!(r.len(), 2);
407        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
408    }
409
410    #[test]
411    fn insert_contained() {
412        let mut r = RangeSet::default();
413
414        r.insert(4..7);
415        r.insert(9..12);
416        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
417
418        r.insert(4..7);
419        assert_eq!(r.len(), 2);
420        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
421
422        r.insert(4..6);
423        assert_eq!(r.len(), 2);
424        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
425
426        r.insert(5..6);
427        assert_eq!(r.len(), 2);
428        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
429
430        r.insert(10..11);
431        assert_eq!(r.len(), 2);
432        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
433
434        r.insert(9..11);
435        assert_eq!(r.len(), 2);
436        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
437    }
438
439    #[test]
440    fn insert_overlapping() {
441        let mut r = RangeSet::default();
442
443        r.insert(3..6);
444        r.insert(9..12);
445        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[3, 4, 5, 9, 10, 11]);
446
447        r.insert(5..7);
448        assert_eq!(r.len(), 2);
449        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[3, 4, 5, 6, 9, 10, 11]);
450
451        r.insert(10..15);
452        assert_eq!(r.len(), 2);
453        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
454            3, 4, 5, 6, 9, 10, 11, 12, 13, 14
455        ]);
456
457        r.insert(2..5);
458        assert_eq!(r.len(), 2);
459        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
460            2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14
461        ]);
462
463        r.insert(8..10);
464        assert_eq!(r.len(), 2);
465        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
466            2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14
467        ]);
468
469        r.insert(6..10);
470        assert_eq!(r.len(), 1);
471        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
472            2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
473        ]);
474    }
475
476    #[test]
477    fn insert_overlapping_multi() {
478        let mut r = RangeSet::default();
479
480        r.insert(3..6);
481        r.insert(16..20);
482        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
483            3, 4, 5, 16, 17, 18, 19
484        ]);
485
486        r.insert(10..11);
487        assert_eq!(r.len(), 3);
488        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
489            3, 4, 5, 10, 16, 17, 18, 19
490        ]);
491
492        assert!(matches!(r, RangeSet::Inline(_)));
493
494        r.insert(13..14);
495        assert_eq!(r.len(), 4);
496        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
497            3, 4, 5, 10, 13, 16, 17, 18, 19
498        ]);
499
500        // Make sure it converted to a btree at capacity
501        assert!(matches!(r, RangeSet::BTree(_)));
502
503        r.insert(4..17);
504        assert_eq!(r.len(), 1);
505        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
506            3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
507        ]);
508
509        // Make sure it converted back to inline
510        assert!(matches!(r, RangeSet::Inline(_)));
511    }
512
513    #[test]
514    fn prev_to() {
515        let mut r = BTreeRangeSet {
516            inner: Default::default(),
517            capacity: usize::MAX,
518        };
519
520        r.insert(4..7);
521        r.insert(9..12);
522
523        assert_eq!(r.prev_to(2), None);
524        assert_eq!(r.prev_to(4), Some(4..7));
525        assert_eq!(r.prev_to(15), Some(9..12));
526        assert_eq!(r.prev_to(5), Some(4..7));
527        assert_eq!(r.prev_to(8), Some(4..7));
528    }
529
530    #[test]
531    fn next_to() {
532        let mut r = BTreeRangeSet {
533            inner: Default::default(),
534            capacity: usize::MAX,
535        };
536
537        r.insert(4..7);
538        r.insert(9..12);
539
540        assert_eq!(r.next_to(2), Some(4..7));
541        assert_eq!(r.next_to(12), None);
542        assert_eq!(r.next_to(15), None);
543        assert_eq!(r.next_to(5), Some(9..12));
544        assert_eq!(r.next_to(8), Some(9..12));
545    }
546
547    #[test]
548    fn push_item() {
549        let mut r = RangeSet::default();
550
551        r.insert(4..7);
552        r.insert(9..12);
553        assert_eq!(r.len(), 2);
554        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
555
556        r.push_item(15);
557        assert_eq!(r.len(), 3);
558        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
559            4, 5, 6, 9, 10, 11, 15
560        ]);
561
562        r.push_item(15);
563        assert_eq!(r.len(), 3);
564        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
565            4, 5, 6, 9, 10, 11, 15
566        ]);
567
568        r.push_item(1);
569        assert_eq!(r.len(), 4);
570        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
571            1, 4, 5, 6, 9, 10, 11, 15
572        ]);
573
574        r.push_item(12);
575        r.push_item(13);
576        r.push_item(14);
577
578        assert_eq!(r.len(), 3);
579        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
580            1, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15
581        ]);
582
583        r.push_item(2);
584        r.push_item(3);
585        assert_eq!(r.len(), 2);
586        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
587            1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15
588        ]);
589
590        r.push_item(8);
591        r.push_item(7);
592        assert_eq!(r.len(), 1);
593        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
594            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
595        ]);
596    }
597
598    #[test]
599    fn flatten_rev() {
600        let mut r = RangeSet::default();
601        assert_eq!(r.len(), 0);
602
603        let empty: &[u64] = &[];
604        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &empty);
605
606        r.insert(4..7);
607        assert_eq!(r.len(), 1);
608        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6]);
609        assert_eq!(&r.flatten().rev().collect::<Vec<u64>>(), &[6, 5, 4]);
610
611        r.insert(9..12);
612        assert_eq!(r.len(), 2);
613        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[4, 5, 6, 9, 10, 11]);
614        assert_eq!(&r.flatten().rev().collect::<Vec<u64>>(), &[
615            11, 10, 9, 6, 5, 4
616        ]);
617    }
618
619    #[test]
620    fn flatten_one() {
621        let mut r = RangeSet::default();
622        assert_eq!(r.len(), 0);
623
624        let empty: &[u64] = &[];
625        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &empty);
626
627        r.insert(0..1);
628        assert_eq!(r.len(), 1);
629        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[0]);
630        assert_eq!(&r.flatten().rev().collect::<Vec<u64>>(), &[0]);
631    }
632
633    #[test]
634    fn remove_largest() {
635        let mut r = RangeSet::default();
636
637        r.insert(3..6);
638        r.insert(9..11);
639        r.insert(13..14);
640        r.insert(16..20);
641        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
642            3, 4, 5, 9, 10, 13, 16, 17, 18, 19
643        ]);
644
645        r.remove_until(2);
646        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
647            3, 4, 5, 9, 10, 13, 16, 17, 18, 19
648        ]);
649
650        r.remove_until(4);
651        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
652            5, 9, 10, 13, 16, 17, 18, 19
653        ]);
654
655        r.remove_until(6);
656        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[
657            9, 10, 13, 16, 17, 18, 19
658        ]);
659
660        r.remove_until(10);
661        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[13, 16, 17, 18, 19]);
662
663        r.remove_until(17);
664        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[18, 19]);
665
666        r.remove_until(18);
667        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &[19]);
668
669        r.remove_until(20);
670
671        let empty: &[u64] = &[];
672        assert_eq!(&r.flatten().collect::<Vec<u64>>(), &empty);
673    }
674
675    #[test]
676    fn eq_range() {
677        let mut r = RangeSet::default();
678        assert_ne!(r, 0..0);
679
680        let expected = 3..20;
681
682        r.insert(3..6);
683        assert_ne!(r, expected);
684
685        r.insert(16..20);
686        assert_ne!(r, expected);
687
688        r.insert(10..11);
689        assert_ne!(r, expected);
690
691        r.insert(13..14);
692        assert_ne!(r, expected);
693
694        r.insert(4..17);
695
696        assert_eq!(r, expected);
697    }
698
699    #[test]
700    fn first_last() {
701        let mut r = RangeSet::default();
702        assert_eq!(r.first(), None);
703        assert_eq!(r.last(), None);
704
705        r.insert(10..11);
706        assert_eq!(r.first(), Some(10));
707        assert_eq!(r.last(), Some(10));
708
709        r.insert(13..14);
710        assert_eq!(r.first(), Some(10));
711        assert_eq!(r.last(), Some(13));
712
713        r.insert(3..6);
714        assert_eq!(r.first(), Some(3));
715        assert_eq!(r.last(), Some(13));
716
717        r.insert(16..20);
718        assert_eq!(r.first(), Some(3));
719        assert_eq!(r.last(), Some(19));
720
721        r.insert(4..17);
722        assert_eq!(r.first(), Some(3));
723        assert_eq!(r.last(), Some(19));
724    }
725
726    #[test]
727    fn capacity() {
728        let mut r = RangeSet::new(3);
729        assert_eq!(r.first(), None);
730        assert_eq!(r.last(), None);
731
732        r.insert(10..11);
733        assert_eq!(r.first(), Some(10));
734        assert_eq!(r.last(), Some(10));
735
736        r.insert(13..14);
737        assert_eq!(r.first(), Some(10));
738        assert_eq!(r.last(), Some(13));
739
740        r.insert(3..6);
741        assert_eq!(r.first(), Some(3));
742        assert_eq!(r.last(), Some(13));
743
744        r.insert(16..20);
745        assert_eq!(r.first(), Some(10));
746        assert_eq!(r.last(), Some(19));
747
748        r.insert(4..17);
749        assert_eq!(r.first(), Some(4));
750        assert_eq!(r.last(), Some(19));
751    }
752}
quiche/ranges.rs

quiche/
ranges.rs
