quic: parameterize rangeset
Make the rangeset type parameterized, so it can be used for
either packet number or byte ranges without type conversions.
For golang/go#58547
Change-Id: I764913a33ba58222dcfd36f94de01c2249d73551
Reviewed-on: https://go-review.googlesource.com/c/net/+/499284
Run-TryBot: Damien Neil <dneil@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Jonathan Amsterdam <jba@google.com>
diff --git a/internal/quic/frame_debug.go b/internal/quic/frame_debug.go
index 34a0039..93ddf55 100644
--- a/internal/quic/frame_debug.go
+++ b/internal/quic/frame_debug.go
@@ -116,15 +116,15 @@
// debugFrameAck is an ACK frame.
type debugFrameAck struct {
ackDelay time.Duration
- ranges []i64range
+ ranges []i64range[packetNumber]
}
func parseDebugFrameAck(b []byte) (f debugFrameAck, n int) {
f.ranges = nil
_, f.ackDelay, n = consumeAckFrame(b, ackDelayExponent, func(start, end packetNumber) {
- f.ranges = append(f.ranges, i64range{
- start: int64(start),
- end: int64(end),
+ f.ranges = append(f.ranges, i64range[packetNumber]{
+ start: start,
+ end: end,
})
})
// Ranges are parsed smallest to highest; reverse ranges slice to order them high to low.
@@ -144,7 +144,7 @@
}
func (f debugFrameAck) write(w *packetWriter) bool {
- return w.appendAckFrame(rangeset(f.ranges), ackDelayExponent, f.ackDelay)
+ return w.appendAckFrame(rangeset[packetNumber](f.ranges), ackDelayExponent, f.ackDelay)
}
// debugFrameResetStream is a RESET_STREAM frame.
diff --git a/internal/quic/packet_codec_test.go b/internal/quic/packet_codec_test.go
index 2a2043b..efd519b 100644
--- a/internal/quic/packet_codec_test.go
+++ b/internal/quic/packet_codec_test.go
@@ -222,7 +222,7 @@
s: "ACK Delay=80µs [0,16) [17,32) [48,64)",
f: debugFrameAck{
ackDelay: (10 << ackDelayExponent) * time.Microsecond,
- ranges: []i64range{
+ ranges: []i64range[packetNumber]{
{0x00, 0x10},
{0x11, 0x20},
{0x30, 0x40},
@@ -595,7 +595,7 @@
desc: "ACK frame with ECN counts",
want: debugFrameAck{
ackDelay: (10 << ackDelayExponent) * time.Microsecond,
- ranges: []i64range{
+ ranges: []i64range[packetNumber]{
{0, 1},
},
},
diff --git a/internal/quic/packet_writer.go b/internal/quic/packet_writer.go
index 494105e..bfe9af7 100644
--- a/internal/quic/packet_writer.go
+++ b/internal/quic/packet_writer.go
@@ -257,7 +257,7 @@
// to the peer potentially failing to receive an acknowledgement
// for an older packet during a period of high packet loss or
// reordering. This may result in unnecessary retransmissions.
-func (w *packetWriter) appendAckFrame(seen rangeset, ackDelayExponent uint8, delay time.Duration) (added bool) {
+func (w *packetWriter) appendAckFrame(seen rangeset[packetNumber], ackDelayExponent uint8, delay time.Duration) (added bool) {
if len(seen) == 0 {
return false
}
diff --git a/internal/quic/rangeset.go b/internal/quic/rangeset.go
index ea331ab..5339c5a 100644
--- a/internal/quic/rangeset.go
+++ b/internal/quic/rangeset.go
@@ -11,27 +11,24 @@
//
// Rangesets are efficient for small numbers of ranges,
// which is expected to be the common case.
-//
-// Once we're willing to drop support for pre-generics versions of Go, this can
-// be made into a parameterized type to permit use with packetNumber without casts.
-type rangeset []i64range
+type rangeset[T ~int64] []i64range[T]
-type i64range struct {
- start, end int64 // [start, end)
+type i64range[T ~int64] struct {
+ start, end T // [start, end)
}
// size returns the size of the range.
-func (r i64range) size() int64 {
+func (r i64range[T]) size() T {
return r.end - r.start
}
// contains reports whether v is in the range.
-func (r i64range) contains(v int64) bool {
+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) add(start, end int64) {
+func (s *rangeset[T]) add(start, end T) {
if start == end {
return
}
@@ -65,11 +62,11 @@
s.removeranges(i+1, j)
return
}
- *s = append(*s, i64range{start, end})
+ *s = append(*s, i64range[T]{start, end})
}
// sub removes [start, end) from the set.
-func (s *rangeset) sub(start, end int64) {
+func (s *rangeset[T]) sub(start, end T) {
removefrom, removeto := -1, -1
for i := range *s {
r := &(*s)[i]
@@ -106,7 +103,7 @@
}
// contains reports whether s contains v.
-func (s rangeset) contains(v int64) bool {
+func (s rangeset[T]) contains(v T) bool {
for _, r := range s {
if v >= r.end {
continue
@@ -120,7 +117,7 @@
}
// rangeContaining returns the range containing v, or the range [0,0) if v is not in s.
-func (s rangeset) rangeContaining(v int64) i64range {
+func (s rangeset[T]) rangeContaining(v T) i64range[T] {
for _, r := range s {
if v >= r.end {
continue
@@ -130,11 +127,11 @@
}
break
}
- return i64range{0, 0}
+ return i64range[T]{0, 0}
}
// min returns the minimum value in the set, or 0 if empty.
-func (s rangeset) min() int64 {
+func (s rangeset[T]) min() T {
if len(s) == 0 {
return 0
}
@@ -142,7 +139,7 @@
}
// max returns the maximum value in the set, or 0 if empty.
-func (s rangeset) max() int64 {
+func (s rangeset[T]) max() T {
if len(s) == 0 {
return 0
}
@@ -150,7 +147,7 @@
}
// end returns the end of the last range in the set, or 0 if empty.
-func (s rangeset) end() int64 {
+func (s rangeset[T]) end() T {
if len(s) == 0 {
return 0
}
@@ -158,7 +155,7 @@
}
// isrange reports if the rangeset covers exactly the range [start, end).
-func (s rangeset) isrange(start, end int64) bool {
+func (s rangeset[T]) isrange(start, end T) bool {
switch len(s) {
case 0:
return start == 0 && end == 0
@@ -169,7 +166,7 @@
}
// removeranges removes ranges [i,j).
-func (s *rangeset) removeranges(i, j int) {
+func (s *rangeset[T]) removeranges(i, j int) {
if i == j {
return
}
@@ -178,8 +175,8 @@
}
// insert adds a new range at index i.
-func (s *rangeset) insertrange(i int, start, end int64) {
- *s = append(*s, i64range{})
+func (s *rangeset[T]) insertrange(i int, start, end T) {
+ *s = append(*s, i64range[T]{})
copy((*s)[i+1:], (*s)[i:])
- (*s)[i] = i64range{start, end}
+ (*s)[i] = i64range[T]{start, end}
}
diff --git a/internal/quic/rangeset_test.go b/internal/quic/rangeset_test.go
index 082f920..3080469 100644
--- a/internal/quic/rangeset_test.go
+++ b/internal/quic/rangeset_test.go
@@ -13,13 +13,13 @@
func TestRangeSize(t *testing.T) {
for _, test := range []struct {
- r i64range
+ r i64range[int64]
want int64
}{{
- r: i64range{0, 100},
+ r: i64range[int64]{0, 100},
want: 100,
}, {
- r: i64range{10, 20},
+ r: i64range[int64]{10, 20},
want: 10,
}} {
if got := test.r.size(); got != test.want {
@@ -29,7 +29,7 @@
}
func TestRangeContains(t *testing.T) {
- r := i64range{5, 10}
+ r := i64range[int64]{5, 10}
for _, i := range []int64{0, 4, 10, 15} {
if r.contains(i) {
t.Errorf("%v.contains(%v) = true, want false", r, i)
@@ -45,69 +45,69 @@
func TestRangesetAdd(t *testing.T) {
for _, test := range []struct {
desc string
- set rangeset
- add i64range
- want rangeset
+ set rangeset[int64]
+ add i64range[int64]
+ want rangeset[int64]
}{{
desc: "add to empty set",
- set: rangeset{},
- add: i64range{0, 100},
- want: rangeset{{0, 100}},
+ set: rangeset[int64]{},
+ add: i64range[int64]{0, 100},
+ want: rangeset[int64]{{0, 100}},
}, {
desc: "add empty range",
- set: rangeset{},
- add: i64range{100, 100},
- want: rangeset{},
+ set: rangeset[int64]{},
+ add: i64range[int64]{100, 100},
+ want: rangeset[int64]{},
}, {
desc: "append nonadjacent range",
- set: rangeset{{100, 200}},
- add: i64range{300, 400},
- want: rangeset{{100, 200}, {300, 400}},
+ set: rangeset[int64]{{100, 200}},
+ add: i64range[int64]{300, 400},
+ want: rangeset[int64]{{100, 200}, {300, 400}},
}, {
desc: "prepend nonadjacent range",
- set: rangeset{{100, 200}},
- add: i64range{0, 50},
- want: rangeset{{0, 50}, {100, 200}},
+ set: rangeset[int64]{{100, 200}},
+ add: i64range[int64]{0, 50},
+ want: rangeset[int64]{{0, 50}, {100, 200}},
}, {
desc: "insert nonadjacent range",
- set: rangeset{{100, 200}, {500, 600}},
- add: i64range{300, 400},
- want: rangeset{{100, 200}, {300, 400}, {500, 600}},
+ set: rangeset[int64]{{100, 200}, {500, 600}},
+ add: i64range[int64]{300, 400},
+ want: rangeset[int64]{{100, 200}, {300, 400}, {500, 600}},
}, {
desc: "prepend adjacent range",
- set: rangeset{{100, 200}},
- add: i64range{50, 100},
- want: rangeset{{50, 200}},
+ set: rangeset[int64]{{100, 200}},
+ add: i64range[int64]{50, 100},
+ want: rangeset[int64]{{50, 200}},
}, {
desc: "append adjacent range",
- set: rangeset{{100, 200}},
- add: i64range{200, 250},
- want: rangeset{{100, 250}},
+ set: rangeset[int64]{{100, 200}},
+ add: i64range[int64]{200, 250},
+ want: rangeset[int64]{{100, 250}},
}, {
desc: "prepend overlapping range",
- set: rangeset{{100, 200}},
- add: i64range{50, 150},
- want: rangeset{{50, 200}},
+ set: rangeset[int64]{{100, 200}},
+ add: i64range[int64]{50, 150},
+ want: rangeset[int64]{{50, 200}},
}, {
desc: "append overlapping range",
- set: rangeset{{100, 200}},
- add: i64range{150, 250},
- want: rangeset{{100, 250}},
+ set: rangeset[int64]{{100, 200}},
+ add: i64range[int64]{150, 250},
+ want: rangeset[int64]{{100, 250}},
}, {
desc: "replace range",
- set: rangeset{{100, 200}},
- add: i64range{50, 250},
- want: rangeset{{50, 250}},
+ set: rangeset[int64]{{100, 200}},
+ add: i64range[int64]{50, 250},
+ want: rangeset[int64]{{50, 250}},
}, {
desc: "prepend and combine",
- set: rangeset{{100, 200}, {300, 400}, {500, 600}},
- add: i64range{50, 300},
- want: rangeset{{50, 400}, {500, 600}},
+ set: rangeset[int64]{{100, 200}, {300, 400}, {500, 600}},
+ add: i64range[int64]{50, 300},
+ want: rangeset[int64]{{50, 400}, {500, 600}},
}, {
desc: "combine several ranges",
- set: rangeset{{100, 200}, {300, 400}, {500, 600}, {700, 800}, {900, 1000}},
- add: i64range{300, 850},
- want: rangeset{{100, 200}, {300, 850}, {900, 1000}},
+ set: rangeset[int64]{{100, 200}, {300, 400}, {500, 600}, {700, 800}, {900, 1000}},
+ add: i64range[int64]{300, 850},
+ want: rangeset[int64]{{100, 200}, {300, 850}, {900, 1000}},
}} {
test := test
t.Run(test.desc, func(t *testing.T) {
@@ -125,59 +125,59 @@
func TestRangesetSub(t *testing.T) {
for _, test := range []struct {
desc string
- set rangeset
- sub i64range
- want rangeset
+ set rangeset[int64]
+ sub i64range[int64]
+ want rangeset[int64]
}{{
desc: "subtract from empty set",
- set: rangeset{},
- sub: i64range{0, 100},
- want: rangeset{},
+ set: rangeset[int64]{},
+ sub: i64range[int64]{0, 100},
+ want: rangeset[int64]{},
}, {
desc: "subtract empty range",
- set: rangeset{{0, 100}},
- sub: i64range{0, 0},
- want: rangeset{{0, 100}},
+ set: rangeset[int64]{{0, 100}},
+ sub: i64range[int64]{0, 0},
+ want: rangeset[int64]{{0, 100}},
}, {
desc: "subtract not present in set",
- set: rangeset{{0, 100}, {200, 300}},
- sub: i64range{100, 200},
- want: rangeset{{0, 100}, {200, 300}},
+ set: rangeset[int64]{{0, 100}, {200, 300}},
+ sub: i64range[int64]{100, 200},
+ want: rangeset[int64]{{0, 100}, {200, 300}},
}, {
desc: "subtract prefix",
- set: rangeset{{100, 200}},
- sub: i64range{0, 150},
- want: rangeset{{150, 200}},
+ set: rangeset[int64]{{100, 200}},
+ sub: i64range[int64]{0, 150},
+ want: rangeset[int64]{{150, 200}},
}, {
desc: "subtract suffix",
- set: rangeset{{100, 200}},
- sub: i64range{150, 300},
- want: rangeset{{100, 150}},
+ set: rangeset[int64]{{100, 200}},
+ sub: i64range[int64]{150, 300},
+ want: rangeset[int64]{{100, 150}},
}, {
desc: "subtract middle",
- set: rangeset{{0, 100}},
- sub: i64range{40, 60},
- want: rangeset{{0, 40}, {60, 100}},
+ set: rangeset[int64]{{0, 100}},
+ sub: i64range[int64]{40, 60},
+ want: rangeset[int64]{{0, 40}, {60, 100}},
}, {
desc: "subtract from two ranges",
- set: rangeset{{0, 100}, {200, 300}},
- sub: i64range{50, 250},
- want: rangeset{{0, 50}, {250, 300}},
+ set: rangeset[int64]{{0, 100}, {200, 300}},
+ sub: i64range[int64]{50, 250},
+ want: rangeset[int64]{{0, 50}, {250, 300}},
}, {
desc: "subtract removes range",
- set: rangeset{{0, 100}, {200, 300}, {400, 500}},
- sub: i64range{200, 300},
- want: rangeset{{0, 100}, {400, 500}},
+ set: rangeset[int64]{{0, 100}, {200, 300}, {400, 500}},
+ sub: i64range[int64]{200, 300},
+ want: rangeset[int64]{{0, 100}, {400, 500}},
}, {
desc: "subtract removes multiple ranges",
- set: rangeset{{0, 100}, {200, 300}, {400, 500}, {600, 700}},
- sub: i64range{50, 650},
- want: rangeset{{0, 50}, {650, 700}},
+ set: rangeset[int64]{{0, 100}, {200, 300}, {400, 500}, {600, 700}},
+ sub: i64range[int64]{50, 650},
+ want: rangeset[int64]{{0, 50}, {650, 700}},
}, {
desc: "subtract only range",
- set: rangeset{{0, 100}},
- sub: i64range{0, 100},
- want: rangeset{},
+ set: rangeset[int64]{{0, 100}},
+ sub: i64range[int64]{0, 100},
+ want: rangeset[int64]{},
}} {
test := test
t.Run(test.desc, func(t *testing.T) {
@@ -193,7 +193,7 @@
}
func TestRangesetContains(t *testing.T) {
- var s rangeset
+ var s rangeset[int64]
s.add(10, 20)
s.add(30, 40)
for i := int64(0); i < 50; i++ {
@@ -205,23 +205,23 @@
}
func TestRangesetRangeContaining(t *testing.T) {
- var s rangeset
+ var s rangeset[int64]
s.add(10, 20)
s.add(30, 40)
for _, test := range []struct {
v int64
- want i64range
+ want i64range[int64]
}{
- {0, i64range{0, 0}},
- {9, i64range{0, 0}},
- {10, i64range{10, 20}},
- {15, i64range{10, 20}},
- {19, i64range{10, 20}},
- {20, i64range{0, 0}},
- {29, i64range{0, 0}},
- {30, i64range{30, 40}},
- {39, i64range{30, 40}},
- {40, i64range{0, 0}},
+ {0, i64range[int64]{0, 0}},
+ {9, i64range[int64]{0, 0}},
+ {10, i64range[int64]{10, 20}},
+ {15, i64range[int64]{10, 20}},
+ {19, i64range[int64]{10, 20}},
+ {20, i64range[int64]{0, 0}},
+ {29, i64range[int64]{0, 0}},
+ {30, i64range[int64]{30, 40}},
+ {39, i64range[int64]{30, 40}},
+ {40, i64range[int64]{0, 0}},
} {
got := s.rangeContaining(test.v)
if got != test.want {
@@ -232,22 +232,22 @@
func TestRangesetLimits(t *testing.T) {
for _, test := range []struct {
- s rangeset
+ s rangeset[int64]
wantMin int64
wantMax int64
wantEnd int64
}{{
- s: rangeset{},
+ s: rangeset[int64]{},
wantMin: 0,
wantMax: 0,
wantEnd: 0,
}, {
- s: rangeset{{10, 20}},
+ s: rangeset[int64]{{10, 20}},
wantMin: 10,
wantMax: 19,
wantEnd: 20,
}, {
- s: rangeset{{10, 20}, {30, 40}, {50, 60}},
+ s: rangeset[int64]{{10, 20}, {30, 40}, {50, 60}},
wantMin: 10,
wantMax: 59,
wantEnd: 60,
@@ -266,28 +266,28 @@
func TestRangesetIsRange(t *testing.T) {
for _, test := range []struct {
- s rangeset
- r i64range
+ s rangeset[int64]
+ r i64range[int64]
want bool
}{{
- s: rangeset{{0, 100}},
- r: i64range{0, 100},
+ s: rangeset[int64]{{0, 100}},
+ r: i64range[int64]{0, 100},
want: true,
}, {
- s: rangeset{{0, 100}},
- r: i64range{0, 101},
+ s: rangeset[int64]{{0, 100}},
+ r: i64range[int64]{0, 101},
want: false,
}, {
- s: rangeset{{0, 10}, {11, 100}},
- r: i64range{0, 100},
+ s: rangeset[int64]{{0, 10}, {11, 100}},
+ r: i64range[int64]{0, 100},
want: false,
}, {
- s: rangeset{},
- r: i64range{0, 0},
+ s: rangeset[int64]{},
+ r: i64range[int64]{0, 0},
want: true,
}, {
- s: rangeset{},
- r: i64range{0, 1},
+ s: rangeset[int64]{},
+ r: i64range[int64]{0, 1},
want: false,
}} {
if got := test.s.isrange(test.r.start, test.r.end); got != test.want {
diff --git a/internal/quic/sent_packet_test.go b/internal/quic/sent_packet_test.go
index c01a2fb..c0b04e6 100644
--- a/internal/quic/sent_packet_test.go
+++ b/internal/quic/sent_packet_test.go
@@ -13,7 +13,7 @@
byte(frameTypePing),
byte(frameTypeStreamBase),
uint64(1),
- i64range{1 << 20, 1<<20 + 1024},
+ i64range[int64]{1 << 20, 1<<20 + 1024},
}
// Record sent frames.
sent := newSentPacket()
@@ -23,7 +23,7 @@
sent.appendAckElicitingFrame(f)
case uint64:
sent.appendInt(f)
- case i64range:
+ case i64range[int64]:
sent.appendOffAndSize(f.start, int(f.size()))
}
}
@@ -41,7 +41,7 @@
if got := sent.nextInt(); got != want {
t.Fatalf("%v: sent.nextInt() = %v, want %v", i, got, want)
}
- case i64range:
+ case i64range[int64]:
if start, end := sent.nextRange(); start != want.start || end != want.end {
t.Fatalf("%v: sent.nextRange() = [%v,%v), want %v", i, start, end, want)
}
