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

quiche/
ranges.rs
