blob: 4966a99d2c96c1683ebc12324c566bb0e0c58b9a [file] [log] [blame]
// 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.
//go:build go1.21
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 subsquent 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)
}
// 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}
}