1 files changed, 193 insertions, 0 deletions
diff --git a/src/vendor/golang.org/x/net/quic/rangeset.go b/src/vendor/golang.org/x/net/quic/rangeset.go
new file mode 100644
index 0000000000..3d6f5f9799
--- /dev/null
+++ b/src/vendor/golang.org/x/net/quic/rangeset.go
@@ -0,0 +1,193 @@
+// Copyright 2023 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package quic
+
+// A rangeset is a set of int64s, stored as an ordered list of non-overlapping,
+// non-empty ranges.
+//
+// Rangesets are efficient for small numbers of ranges,
+// which is expected to be the common case.
+type rangeset[T ~int64] []i64range[T]
+
+type i64range[T ~int64] struct {
+	start, end T // [start, end)
+}
+
+// size returns the size of the range.
+func (r i64range[T]) size() T {
+	return r.end - r.start
+}
+
+// contains reports whether v is in the range.
+func (r i64range[T]) contains(v T) bool {
+	return r.start <= v && v < r.end
+}
+
+// add adds [start, end) to the set, combining it with existing ranges if necessary.
+func (s *rangeset[T]) add(start, end T) {
+	if start == end {
+		return
+	}
+	for i := range *s {
+		r := &(*s)[i]
+		if r.start > end {
+			// The new range comes before range i.
+			s.insertrange(i, start, end)
+			return
+		}
+		if start > r.end {
+			// The new range comes after range i.
+			continue
+		}
+		// The new range is adjacent to or overlapping range i.
+		if start < r.start {
+			r.start = start
+		}
+		if end <= r.end {
+			return
+		}
+		// Possibly coalesce subsequent ranges into range i.
+		r.end = end
+		j := i + 1
+		for ; j < len(*s) && r.end >= (*s)[j].start; j++ {
+			if e := (*s)[j].end; e > r.end {
+				// Range j ends after the new range.
+				r.end = e
+			}
+		}
+		s.removeranges(i+1, j)
+		return
+	}
+	*s = append(*s, i64range[T]{start, end})
+}
+
+// sub removes [start, end) from the set.
+func (s *rangeset[T]) sub(start, end T) {
+	removefrom, removeto := -1, -1
+	for i := range *s {
+		r := &(*s)[i]
+		if end < r.start {
+			break
+		}
+		if r.end < start {
+			continue
+		}
+		switch {
+		case start <= r.start && end >= r.end:
+			// Remove the entire range.
+			if removefrom == -1 {
+				removefrom = i
+			}
+			removeto = i + 1
+		case start <= r.start:
+			// Remove a prefix.
+			r.start = end
+		case end >= r.end:
+			// Remove a suffix.
+			r.end = start
+		default:
+			// Remove the middle, leaving two new ranges.
+			rend := r.end
+			r.end = start
+			s.insertrange(i+1, end, rend)
+			return
+		}
+	}
+	if removefrom != -1 {
+		s.removeranges(removefrom, removeto)
+	}
+}
+
+// contains reports whether s contains v.
+func (s rangeset[T]) contains(v T) bool {
+	for _, r := range s {
+		if v >= r.end {
+			continue
+		}
+		if r.start <= v {
+			return true
+		}
+		return false
+	}
+	return false
+}
+
+// rangeContaining returns the range containing v, or the range [0,0) if v is not in s.
+func (s rangeset[T]) rangeContaining(v T) i64range[T] {
+	for _, r := range s {
+		if v >= r.end {
+			continue
+		}
+		if r.start <= v {
+			return r
+		}
+		break
+	}
+	return i64range[T]{0, 0}
+}
+
+// min returns the minimum value in the set, or 0 if empty.
+func (s rangeset[T]) min() T {
+	if len(s) == 0 {
+		return 0
+	}
+	return s[0].start
+}
+
+// max returns the maximum value in the set, or 0 if empty.
+func (s rangeset[T]) max() T {
+	if len(s) == 0 {
+		return 0
+	}
+	return s[len(s)-1].end - 1
+}
+
+// end returns the end of the last range in the set, or 0 if empty.
+func (s rangeset[T]) end() T {
+	if len(s) == 0 {
+		return 0
+	}
+	return s[len(s)-1].end
+}
+
+// numRanges returns the number of ranges in the rangeset.
+func (s rangeset[T]) numRanges() int {
+	return len(s)
+}
+
+// size returns the size of all ranges in the rangeset.
+func (s rangeset[T]) size() (total T) {
+	for _, r := range s {
+		total += r.size()
+	}
+	return total
+}
+
+// isrange reports if the rangeset covers exactly the range [start, end).
+func (s rangeset[T]) isrange(start, end T) bool {
+	switch len(s) {
+	case 0:
+		return start == 0 && end == 0
+	case 1:
+		return s[0].start == start && s[0].end == end
+	}
+	return false
+}
+
+// removeranges removes ranges [i,j).
+func (s *rangeset[T]) removeranges(i, j int) {
+	if i == j {
+		return
+	}
+	copy((*s)[i:], (*s)[j:])
+	*s = (*s)[:len(*s)-(j-i)]
+}
+
+// insert adds a new range at index i.
+func (s *rangeset[T]) insertrange(i int, start, end T) {
+	*s = append(*s, i64range[T]{})
+	copy((*s)[i+1:], (*s)[i:])
+	(*s)[i] = i64range[T]{start, end}
+}