rangeset.go

Documentation: golang.org/x/net/internal/quic

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  //go:build go1.21
     6  
     7  package quic
     8  
     9  // A rangeset is a set of int64s, stored as an ordered list of non-overlapping,
    10  // non-empty ranges.
    11  //
    12  // Rangesets are efficient for small numbers of ranges,
    13  // which is expected to be the common case.
    14  type rangeset[T ~int64] []i64range[T]
    15  
    16  type i64range[T ~int64] struct {
    17  	start, end T // [start, end)
    18  }
    19  
    20  // size returns the size of the range.
    21  func (r i64range[T]) size() T {
    22  	return r.end - r.start
    23  }
    24  
    25  // contains reports whether v is in the range.
    26  func (r i64range[T]) contains(v T) bool {
    27  	return r.start <= v && v < r.end
    28  }
    29  
    30  // add adds [start, end) to the set, combining it with existing ranges if necessary.
    31  func (s *rangeset[T]) add(start, end T) {
    32  	if start == end {
    33  		return
    34  	}
    35  	for i := range *s {
    36  		r := &(*s)[i]
    37  		if r.start > end {
    38  			// The new range comes before range i.
    39  			s.insertrange(i, start, end)
    40  			return
    41  		}
    42  		if start > r.end {
    43  			// The new range comes after range i.
    44  			continue
    45  		}
    46  		// The new range is adjacent to or overlapping range i.
    47  		if start < r.start {
    48  			r.start = start
    49  		}
    50  		if end <= r.end {
    51  			return
    52  		}
    53  		// Possibly coalesce subsquent ranges into range i.
    54  		r.end = end
    55  		j := i + 1
    56  		for ; j < len(*s) && r.end >= (*s)[j].start; j++ {
    57  			if e := (*s)[j].end; e > r.end {
    58  				// Range j ends after the new range.
    59  				r.end = e
    60  			}
    61  		}
    62  		s.removeranges(i+1, j)
    63  		return
    64  	}
    65  	*s = append(*s, i64range[T]{start, end})
    66  }
    67  
    68  // sub removes [start, end) from the set.
    69  func (s *rangeset[T]) sub(start, end T) {
    70  	removefrom, removeto := -1, -1
    71  	for i := range *s {
    72  		r := &(*s)[i]
    73  		if end < r.start {
    74  			break
    75  		}
    76  		if r.end < start {
    77  			continue
    78  		}
    79  		switch {
    80  		case start <= r.start && end >= r.end:
    81  			// Remove the entire range.
    82  			if removefrom == -1 {
    83  				removefrom = i
    84  			}
    85  			removeto = i + 1
    86  		case start <= r.start:
    87  			// Remove a prefix.
    88  			r.start = end
    89  		case end >= r.end:
    90  			// Remove a suffix.
    91  			r.end = start
    92  		default:
    93  			// Remove the middle, leaving two new ranges.
    94  			rend := r.end
    95  			r.end = start
    96  			s.insertrange(i+1, end, rend)
    97  			return
    98  		}
    99  	}
   100  	if removefrom != -1 {
   101  		s.removeranges(removefrom, removeto)
   102  	}
   103  }
   104  
   105  // contains reports whether s contains v.
   106  func (s rangeset[T]) contains(v T) bool {
   107  	for _, r := range s {
   108  		if v >= r.end {
   109  			continue
   110  		}
   111  		if r.start <= v {
   112  			return true
   113  		}
   114  		return false
   115  	}
   116  	return false
   117  }
   118  
   119  // rangeContaining returns the range containing v, or the range [0,0) if v is not in s.
   120  func (s rangeset[T]) rangeContaining(v T) i64range[T] {
   121  	for _, r := range s {
   122  		if v >= r.end {
   123  			continue
   124  		}
   125  		if r.start <= v {
   126  			return r
   127  		}
   128  		break
   129  	}
   130  	return i64range[T]{0, 0}
   131  }
   132  
   133  // min returns the minimum value in the set, or 0 if empty.
   134  func (s rangeset[T]) min() T {
   135  	if len(s) == 0 {
   136  		return 0
   137  	}
   138  	return s[0].start
   139  }
   140  
   141  // max returns the maximum value in the set, or 0 if empty.
   142  func (s rangeset[T]) max() T {
   143  	if len(s) == 0 {
   144  		return 0
   145  	}
   146  	return s[len(s)-1].end - 1
   147  }
   148  
   149  // end returns the end of the last range in the set, or 0 if empty.
   150  func (s rangeset[T]) end() T {
   151  	if len(s) == 0 {
   152  		return 0
   153  	}
   154  	return s[len(s)-1].end
   155  }
   156  
   157  // numRanges returns the number of ranges in the rangeset.
   158  func (s rangeset[T]) numRanges() int {
   159  	return len(s)
   160  }
   161  
   162  // isrange reports if the rangeset covers exactly the range [start, end).
   163  func (s rangeset[T]) isrange(start, end T) bool {
   164  	switch len(s) {
   165  	case 0:
   166  		return start == 0 && end == 0
   167  	case 1:
   168  		return s[0].start == start && s[0].end == end
   169  	}
   170  	return false
   171  }
   172  
   173  // removeranges removes ranges [i,j).
   174  func (s *rangeset[T]) removeranges(i, j int) {
   175  	if i == j {
   176  		return
   177  	}
   178  	copy((*s)[i:], (*s)[j:])
   179  	*s = (*s)[:len(*s)-(j-i)]
   180  }
   181  
   182  // insert adds a new range at index i.
   183  func (s *rangeset[T]) insertrange(i int, start, end T) {
   184  	*s = append(*s, i64range[T]{})
   185  	copy((*s)[i+1:], (*s)[i:])
   186  	(*s)[i] = i64range[T]{start, end}
   187  }
   188
View as plain text