rangeset.go

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