-
Notifications
You must be signed in to change notification settings - Fork 9
/
ipseqrange.go
1246 lines (1148 loc) · 44.4 KB
/
ipseqrange.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//
// Copyright 2020-2022 Sean C Foley
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
package ipaddr
import (
"fmt"
"math/big"
"math/bits"
"net"
"net/netip"
"sort"
"strings"
"unsafe"
)
// DefaultSeqRangeSeparator is the low to high value separator used when creating strings for IP ranges.
const DefaultSeqRangeSeparator = " -> "
type rangeCache struct {
cachedCount *big.Int
}
// SequentialRangeConstraint is the generic type constraint for an IP address sequential range.
type SequentialRangeConstraint[T any] interface {
AddressType // cannot use IPAddressType here because ToAddressString() results in a circular dependency, SequentialRangeConstraint -> IPAddressType -> IPAddressString -> SequentialRange -> SequentialRangeConstraint
IPAddressRange
comparable
ToIP() *IPAddress
PrefixedConstraint[T]
Increment(int64) T
GetLower() T
GetUpper() T
CoverWithPrefixBlockTo(T) T
SpanWithPrefixBlocksTo(T) []T
SpanWithSequentialBlocksTo(T) []T
SpanWithPrefixBlocks() []T
IncludesZeroHostLen(BitCount) bool
IncludesMaxHostLen(BitCount) bool
Format(state fmt.State, verb rune)
rangeIterator(upper T,
valsAreMultiple bool,
prefixLen PrefixLen,
segProducer func(addr *IPAddress, index int) *IPAddressSegment,
segmentIteratorProducer func(seg *IPAddressSegment, index int) Iterator[*IPAddressSegment],
segValueComparator func(seg1, seg2 *IPAddress, index int) bool,
networkSegmentIndex,
hostSegmentIndex int,
prefixedSegIteratorProducer func(seg *IPAddressSegment, index int) Iterator[*IPAddressSegment],
) Iterator[T]
toKey() RangeBoundaryKey[T]
equalsSameVersion(AddressType) bool
getLowestHighestAddrs() (lower, upper T)
getAddrType() addrType
}
var (
_ SequentialRange[*IPAddress]
_ SequentialRange[*IPv4Address]
_ SequentialRange[*IPv6Address]
)
// SequentialRange represents an arbitrary range of consecutive IP addresses, from a lower address to an upper address, inclusive.
//
// For the generic type T you can choose *IPAddress, *IPv4Address, or *IPv6Address.
//
// This type allows the representation of any sequential address range, including those that cannot be represented by [IPAddress] or [IPAddressString].
//
// [IPAddress] and [IPAddressString] allow you to specify a range of values for each segment, allowing
// for single addresses, any address CIDR prefix subnet (for example, "1.2.0.0/16" or "1:2:3:4::/64") or any subnet that can be represented with segment ranges (for example, "1.2.0-255.*" or "1:2:3:4:*").
// See [IPAddressString] for details.
// [IPAddressString] and [IPAddress] cover all potential subnets and addresses that can be represented by a single address string of 4 or less segments for IPv4, and 8 or less segments for IPv6.
// In contrast, this type covers any sequential address range.
//
// String representations of this type include the full address for both the lower and upper bounds of the range.
//
// The zero value is a range from the zero-valued [IPAddress] to itself.
//
// For a range of type SequentialRange[*IPAddress], the range spans from an IPv4 address to another IPv4 address,
// or from an IPv6 address to another IPv6 address. A sequential range cannot include both IPv4 and IPv6 addresses.
type SequentialRange[T SequentialRangeConstraint[T]] struct {
lower,
upper T
isMultiple bool // set on construction, even for zero values
cache *rangeCache
}
func nilConvert[T SequentialRangeConstraint[T]]() (t T) {
anyt := any(t)
if _, ok := anyt.(*IPv6Address); ok {
t = any(zeroIPv6).(T)
} else if _, ok := anyt.(*IPv4Address); ok {
t = any(zeroIPv4).(T)
} else if _, ok := anyt.(*IPAddress); ok {
t = any(zeroIPAddr).(T)
}
return
}
func (rng *SequentialRange[T]) init() *SequentialRange[T] {
var t T
if rng.lower == t { // nil for pointers
t = nilConvert[T]()
zeroSeqRange := newSequRange(t, t)
return zeroSeqRange
}
return rng
}
// GetIPVersion returns the IP version of this IP address sequential range
func (rng *SequentialRange[T]) GetIPVersion() IPVersion {
return rng.init().lower.GetIPVersion()
}
func (rng *SequentialRange[T]) getCachedCount(copy bool) (res *big.Int) {
cache := rng.cache
count := (*big.Int)(atomicLoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cache.cachedCount))))
if count == nil {
if !rng.IsMultiple() {
count = bigOne()
} else {
lower := rng.lower
upper := rng.upper
if ipv4Lower, ok := any(lower).(*IPv4Address); ok {
ipv4Upper := any(upper).(*IPv4Address)
val := int64(ipv4Upper.Uint32Value()) - int64(ipv4Lower.Uint32Value()) + 1
count = new(big.Int).SetInt64(val)
} else {
count = upper.GetValue()
res = lower.GetValue()
count.Sub(count, res).Add(count, bigOneConst())
res.Set(count)
}
}
dataLoc := (*unsafe.Pointer)(unsafe.Pointer(&cache.cachedCount))
atomicStorePointer(dataLoc, unsafe.Pointer(count))
}
if res == nil {
if copy {
res = new(big.Int).Set(count)
} else {
res = count
}
}
return
}
// GetPrefixCountLen returns the count of the number of distinct values within the prefix part of the range of addresses.
func (rng *SequentialRange[T]) GetPrefixCountLen(prefixLen BitCount) *big.Int {
if !rng.IsMultiple() { // also checks for zero-ranges
return bigOne()
}
bitCount := rng.lower.GetBitCount()
if prefixLen <= 0 {
return bigOne()
} else if prefixLen >= bitCount {
return rng.GetCount()
}
shiftAdjustment := bitCount - prefixLen
lower := rng.lower
if ipv4Lower, ok := any(lower).(*IPv4Address); ok {
ipv4Upper := any(rng.upper).(*IPv4Address)
upperAdjusted := ipv4Upper.Uint32Value() >> uint(shiftAdjustment)
lowerAdjusted := ipv4Lower.Uint32Value() >> uint(shiftAdjustment)
result := int64(upperAdjusted) - int64(lowerAdjusted) + 1
return new(big.Int).SetInt64(result)
}
upperVal := rng.upper.GetValue()
ushiftAdjustment := uint(shiftAdjustment)
upperVal.Rsh(upperVal, ushiftAdjustment)
lowerVal := lower.GetValue()
lowerVal.Rsh(lowerVal, ushiftAdjustment)
upperVal.Sub(upperVal, lowerVal).Add(upperVal, bigOneConst())
return upperVal
}
// IsSequential returns whether the address or subnet represents a range of values that are sequential.
//
// IP address sequential ranges are sequential by definition, so this returns true.
func (rng *SequentialRange[T]) IsSequential() bool {
return true
}
// ContainsPrefixBlock returns whether the range contains the block of addresses for the given prefix length.
//
// Unlike ContainsSinglePrefixBlock, whether there are multiple prefix values for the given prefix length makes no difference.
//
// Use GetMinPrefixLenForBlock to determine whether there is a prefix length for which this method returns true.
func (rng *SequentialRange[T]) ContainsPrefixBlock(prefixLen BitCount) bool {
lower := rng.lower
upper := rng.upper
if lower == upper { // also handles zero-value case nil lower and upper
return true
}
prefixLen = checkSubnet(lower, prefixLen)
divCount := lower.GetDivisionCount()
bitsPerSegment := lower.GetBitsPerSegment()
i := getHostSegmentIndex(prefixLen, lower.GetBytesPerSegment(), bitsPerSegment)
if i < divCount {
div := lower.GetGenericSegment(i)
upperDiv := upper.GetGenericSegment(i)
segmentPrefixLength := getPrefixedSegmentPrefixLength(bitsPerSegment, prefixLen, i)
if !isPrefixBlockVals(DivInt(div.GetSegmentValue()), DivInt(upperDiv.GetSegmentValue()), segmentPrefixLength.bitCount(), div.GetBitCount()) {
return false
}
for i++; i < divCount; i++ {
div = lower.GetGenericSegment(i)
upperDiv = upper.GetGenericSegment(i)
//is full range?
if !div.IncludesZero() || !upperDiv.IncludesMax() {
return false
}
}
}
return true
}
// ContainsSinglePrefixBlock returns whether this address range contains a single prefix block for the given prefix length.
//
// This means there is only one prefix value for the given prefix length, and it also contains the full prefix block for that prefix, all addresses with that prefix.
//
// Use GetPrefixLenForSingleBlock to determine whether there is a prefix length for which this method returns true.
func (rng *SequentialRange[T]) ContainsSinglePrefixBlock(prefixLen BitCount) bool {
lower := rng.lower
upper := rng.upper
if lower == upper { // also handles zero-value case nil lower and upper
return true
}
prefixLen = checkSubnet(lower, prefixLen)
var prevBitCount BitCount
divCount := lower.GetDivisionCount()
for i := 0; i < divCount; i++ {
div := lower.GetGenericSegment(i)
upperDiv := upper.GetGenericSegment(i)
bitCount := div.GetBitCount()
totalBitCount := bitCount + prevBitCount
if prefixLen >= totalBitCount {
if !segValSame(div.GetSegmentValue(), upperDiv.GetSegmentValue()) {
return false
}
} else {
divPrefixLen := prefixLen - prevBitCount
if !isPrefixBlockVals(DivInt(div.GetSegmentValue()), DivInt(upperDiv.GetSegmentValue()), divPrefixLen, div.GetBitCount()) {
return false
}
for i++; i < divCount; i++ {
div = lower.GetGenericSegment(i)
upperDiv = upper.GetGenericSegment(i)
if !div.IncludesZero() || !upperDiv.IncludesMax() {
return false
}
}
return true
}
prevBitCount = totalBitCount
}
return true
}
// GetPrefixLenForSingleBlock returns a prefix length for which there is only one prefix in this range,
// and the range of values in this range matches the block of all values for that prefix.
//
// If the range can be described this way, then this method returns the same value as GetMinPrefixLenForBlock.
//
// If no such prefix length exists, returns nil.
//
// If this item represents a single value, this returns the bit count.
func (rng *SequentialRange[T]) GetPrefixLenForSingleBlock() PrefixLen {
rng = rng.init()
lower := rng.lower
upper := rng.upper
count := lower.GetSegmentCount()
segBitCount := lower.GetBitsPerSegment()
maxSegValue := ^(^SegInt(0) << uint(segBitCount))
totalPrefix := BitCount(0)
for i := 0; i < count; i++ {
lowerSeg := lower.GetGenericSegment(i)
upperSeg := upper.GetGenericSegment(i)
segPrefix := getPrefixLenForSingleBlock(DivInt(lowerSeg.GetSegmentValue()), DivInt(upperSeg.GetSegmentValue()), segBitCount)
if segPrefix == nil {
return nil
}
dabits := segPrefix.bitCount()
totalPrefix += dabits
if dabits < segBitCount {
//remaining segments must be full range or we return nil
for i++; i < count; i++ {
lowerSeg = lower.GetGenericSegment(i)
upperSeg = upper.GetGenericSegment(i)
if lowerSeg.GetSegmentValue() != 0 {
return nil
} else if upperSeg.GetSegmentValue() != maxSegValue {
return nil
}
}
}
}
return cacheBitCount(totalPrefix)
}
// GetMinPrefixLenForBlock returns the smallest prefix length such that this includes the block of addresses for that prefix length.
//
// If the entire range can be described this way, then this method returns the same value as GetPrefixLenForSingleBlock.
//
// There may be a single prefix, or multiple possible prefix values in this item for the returned prefix length.
// Use GetPrefixLenForSingleBlock to avoid the case of multiple prefix values.
func (rng *SequentialRange[T]) GetMinPrefixLenForBlock() BitCount {
rng = rng.init()
lower := rng.lower
upper := rng.upper
count := lower.GetSegmentCount()
totalPrefix := lower.GetBitCount()
segBitCount := lower.GetBitsPerSegment()
for i := count - 1; i >= 0; i-- {
lowerSeg := lower.GetGenericSegment(i)
upperSeg := upper.GetGenericSegment(i)
segPrefix := getMinPrefixLenForBlock(DivInt(lowerSeg.GetSegmentValue()), DivInt(upperSeg.GetSegmentValue()), segBitCount)
if segPrefix == segBitCount {
break
} else {
totalPrefix -= segBitCount
if segPrefix != 0 {
totalPrefix += segPrefix
break
}
}
}
return totalPrefix
}
// IsZero returns whether this sequential range spans from the zero address to itself.
func (rng *SequentialRange[T]) IsZero() bool {
return rng.IncludesZero() && !rng.IsMultiple()
}
// IncludesZero returns whether this sequential range's lower value is the zero address.
func (rng *SequentialRange[T]) IncludesZero() bool {
return rng.init().lower.IsZero()
}
// IsMax returns whether this sequential range spans from the max address, the address whose bits are all ones, to itself.
func (rng *SequentialRange[T]) IsMax() bool {
return rng.IncludesMax() && !rng.IsMultiple()
}
// IncludesMax returns whether this sequential range's upper value is the max value, the value whose bits are all ones.
func (rng *SequentialRange[T]) IncludesMax() bool {
return rng.init().upper.IsMax()
}
// IsFullRange returns whether this address range covers the entire address space of this IP address version.
//
// This is true if and only if both IncludesZero and IncludesMax return true.
func (rng *SequentialRange[T]) IsFullRange() bool {
return rng.IncludesZero() && rng.IncludesMax()
}
// GetCount returns the count of addresses that this sequential range spans.
//
// Use IsMultiple if you simply want to know if the count is greater than 1.
func (rng *SequentialRange[T]) GetCount() *big.Int {
if rng == nil {
return bigZero()
}
return rng.init().getCachedCount(true)
}
// IsMultiple returns whether this range represents a range of multiple addresses.
func (rng *SequentialRange[T]) IsMultiple() bool {
return rng != nil && rng.isMultiple
}
// String implements the [fmt.Stringer] interface,
// returning the lower address canonical string, followed by the default separator " -> ",
// followed by the upper address canonical string.
// It returns "<nil>" if the receiver is a nil pointer.
func (rng *SequentialRange[T]) String() string {
if rng == nil {
return nilString()
}
return rng.ToString(T.String, DefaultSeqRangeSeparator, T.String)
}
// Format implements [fmt.Formatter] interface.
//
// It prints the string as "lower -> upper" where lower and upper are the formatted strings for the lowest and highest addresses in the range, given by GetLower and GetUpper.
// The formats, flags, and other specifications supported are those supported by Format in IPAddress.
func (rng SequentialRange[T]) Format(state fmt.State, verb rune) {
rngPtr := rng.init()
rngPtr.lower.Format(state, verb)
_, _ = state.Write([]byte(DefaultSeqRangeSeparator))
rngPtr.upper.Format(state, verb)
}
// ToString produces a customized string for the address range.
func (rng *SequentialRange[T]) ToString(lowerStringer func(T) string, separator string, upperStringer func(T) string) string {
if rng == nil {
return nilString()
}
rng = rng.init()
builder := strings.Builder{}
str1, str2, str3 := lowerStringer(rng.lower), separator, upperStringer(rng.upper)
builder.Grow(len(str1) + len(str2) + len(str3))
builder.WriteString(str1)
builder.WriteString(str2)
builder.WriteString(str3)
return builder.String()
}
// ToNormalizedString produces a normalized string for the address range.
// It has the format "lower -> upper" where lower and upper are the normalized strings for the lowest and highest addresses in the range, given by GetLower and GetUpper.
func (rng *SequentialRange[T]) ToNormalizedString() string {
return rng.ToString(T.ToNormalizedString, DefaultSeqRangeSeparator, T.ToNormalizedString)
}
// ToCanonicalString produces a canonical string for the address range.
// It has the format "lower -> upper" where lower and upper are the canonical strings for the lowest and highest addresses in the range, given by GetLower and GetUpper.
func (rng *SequentialRange[T]) ToCanonicalString() string {
return rng.ToString(T.ToCanonicalString, DefaultSeqRangeSeparator, T.ToCanonicalString)
}
// GetLowerIPAddress satisfies the IPAddressRange interface, returning the lower address in the range, same as GetLower.
func (rng *SequentialRange[T]) GetLowerIPAddress() *IPAddress {
return rng.GetLower().ToIP()
}
// GetUpperIPAddress satisfies the IPAddressRange interface, returning the upper address in the range, same as GetUpper.
func (rng *SequentialRange[T]) GetUpperIPAddress() *IPAddress {
return rng.GetUpper().ToIP()
}
// GetLower returns the lowest address in the range, the one with the lowest numeric value.
func (rng *SequentialRange[T]) GetLower() T {
return rng.init().lower
}
// GetUpper returns the highest address in the range, the one with the highest numeric value.
func (rng *SequentialRange[T]) GetUpper() T {
return rng.init().upper
}
// GetBitCount returns the number of bits in each address in the range.
func (rng *SequentialRange[T]) GetBitCount() BitCount {
return rng.GetLower().GetBitCount()
}
// GetByteCount returns the number of bytes in each address in the range.
func (rng *SequentialRange[T]) GetByteCount() int {
return rng.GetLower().GetByteCount()
}
// GetNetIP returns the lower IP address in the range as a net.IP.
func (rng *SequentialRange[T]) GetNetIP() net.IP {
return rng.GetLower().GetNetIP()
}
// GetUpperNetIP returns the upper IP address in the range as a net.IP.
func (rng *SequentialRange[T]) GetUpperNetIP() net.IP {
return rng.GetUpper().GetUpperNetIP()
}
// GetNetNetIPAddr returns the lowest address in this address range as a netip.Addr.
func (rng *SequentialRange[T]) GetNetNetIPAddr() netip.Addr {
return rng.GetLower().GetNetNetIPAddr()
}
// GetUpperNetNetIPAddr returns the highest address in this address range as a netip.Addr.
func (rng *SequentialRange[T]) GetUpperNetNetIPAddr() netip.Addr {
return rng.GetUpper().GetUpperNetNetIPAddr()
}
// CopyNetIP copies the value of the lower IP address in the range into a net.IP.
//
// If the value can fit in the given net.IP slice, the value is copied into that slice and a length-adjusted sub-slice is returned.
// Otherwise, a new slice is created and returned with the value.
func (rng *SequentialRange[T]) CopyNetIP(bytes net.IP) net.IP {
return rng.GetLower().CopyNetIP(bytes) // this changes the arg to 4 bytes if 16 bytes and ipv4
}
// CopyUpperNetIP copies the upper IP address in the range into a net.IP.
//
// If the value can fit in the given net.IP slice, the value is copied into that slice and a length-adjusted sub-slice is returned.
// Otherwise, a new slice is created and returned with the value.
func (rng *SequentialRange[T]) CopyUpperNetIP(bytes net.IP) net.IP {
return rng.GetUpper().CopyUpperNetIP(bytes) // this changes the arg to 4 bytes if 16 bytes and ipv4
}
// Bytes returns the lowest address in the range, the one with the lowest numeric value, as a byte slice.
func (rng *SequentialRange[T]) Bytes() []byte {
return rng.GetLower().Bytes()
}
// CopyBytes copies the value of the lowest address in the range into a byte slice.
//
// If the value can fit in the given slice, the value is copied into that slice and a length-adjusted sub-slice is returned.
// Otherwise, a new slice is created and returned with the value.
func (rng *SequentialRange[T]) CopyBytes(bytes []byte) []byte {
return rng.GetLower().CopyBytes(bytes)
}
// UpperBytes returns the highest address in the range, the one with the highest numeric value, as a byte slice.
func (rng *SequentialRange[T]) UpperBytes() []byte {
return rng.GetUpper().UpperBytes()
}
// CopyUpperBytes copies the value of the highest address in the range into a byte slice.
//
// If the value can fit in the given slice, the value is copied into that slice and a length-adjusted sub-slice is returned.
// Otherwise, a new slice is created and returned with the value.
func (rng *SequentialRange[T]) CopyUpperBytes(bytes []byte) []byte {
return rng.GetUpper().CopyUpperBytes(bytes)
}
// Contains returns whether this range contains all addresses in the given address or subnet.
func (rng *SequentialRange[T]) Contains(other IPAddressType) bool {
if rng == nil {
return other == nil || other.ToAddressBase() == nil
} else if other == nil {
return true
}
otherAddr := other.ToIP()
if otherAddr == nil {
return true
}
rng = rng.init()
return compareLowIPAddressValues(otherAddr.GetLower(), rng.lower) >= 0 &&
compareLowIPAddressValues(otherAddr.GetUpper(), rng.upper) <= 0
}
// ContainsRange returns whether all the addresses in the given sequential range are also contained in this sequential range.
func (rng *SequentialRange[T]) ContainsRange(other IPAddressSeqRangeType) bool {
if rng == nil {
return other == nil || other.ToIP() == nil
} else if other == nil {
return true
}
rng = rng.init()
otherRange := other.ToIP()
if otherRange == nil {
return true
}
return compareLowIPAddressValues(otherRange.GetLower(), rng.lower) >= 0 &&
compareLowIPAddressValues(otherRange.GetUpper(), rng.upper) <= 0
}
// Equal returns whether the given sequential address range is equal to this sequential address range.
// Two sequential address ranges are equal if their lower and upper range boundaries are equal.
func (rng *SequentialRange[T]) Equal(other IPAddressSeqRangeType) bool {
if rng == nil {
return other == nil || other.ToIP() == nil
} else if other == nil {
return false
}
rng = rng.init()
otherRange := other.ToIP()
if otherRange == nil {
return false
}
return rng.lower.Equal(otherRange.GetLower()) && rng.upper.Equal(otherRange.GetUpper())
}
// Compare returns a negative integer, zero, or a positive integer if this sequential address range is less than, equal, or greater than the given item.
// Any address item is comparable to any other. All address items use CountComparator to compare.
func (rng *SequentialRange[T]) Compare(item AddressItem) int {
if rng != nil {
rng = rng.init()
}
return CountComparator.Compare(rng, item)
}
// CompareSize compares the counts of two address ranges or items, the number of individual addresses or items within each.
//
// Rather than calculating counts with GetCount, there can be more efficient ways of determining whether this range spans more individual addresses than another item.
//
// CompareSize returns a positive integer if this range has a larger count than the item given, zero if they are the same, or a negative integer if the other has a larger count.
func (rng *SequentialRange[T]) CompareSize(other AddressItem) int {
if rng == nil {
if isNilItem(other) {
return 0
}
// we have size 0, other has size >= 1
return -1
}
return compareCount(rng, other)
}
// GetValue returns the lowest address in the range, the one with the lowest numeric value, as an integer.
func (rng *SequentialRange[T]) GetValue() *big.Int {
return rng.GetLower().GetValue()
}
// GetUpperValue returns the highest address in the range, the one with the highest numeric value, as an integer.
func (rng *SequentialRange[T]) GetUpperValue() *big.Int {
return rng.GetUpper().GetValue()
}
// Iterator provides an iterator to iterate through the individual addresses of this address range.
//
// Call GetCount for the count.
func (rng *SequentialRange[T]) Iterator() Iterator[T] {
if rng == nil {
return nilIterator[T]()
}
rng = rng.init()
lower := rng.lower
if !rng.isMultiple {
return &singleIterator[T]{original: lower}
}
divCount := lower.GetSegmentCount()
return lower.rangeIterator(
rng.upper,
false,
nil,
(*IPAddress).GetSegment,
func(seg *IPAddressSegment, index int) Iterator[*IPAddressSegment] {
return seg.Iterator()
},
func(addr1, addr2 *IPAddress, index int) bool {
return addr1.getSegment(index).getSegmentValue() == addr2.getSegment(index).getSegmentValue()
},
divCount-1,
divCount,
nil)
}
type segPrefData struct {
prefLen PrefixLen
shift BitCount
}
// PrefixBlockIterator provides an iterator to iterate through the individual prefix blocks of the given prefix length,
// one for each prefix of that length in the address range.
func (rng *SequentialRange[T]) PrefixBlockIterator(prefLength BitCount) Iterator[T] {
rng = rng.init()
lower := rng.lower
if !rng.isMultiple {
return &singleIterator[T]{original: lower.ToPrefixBlockLen(prefLength)}
}
prefLength = checkSubnet(lower, prefLength)
bitsPerSegment := lower.GetBitsPerSegment()
bytesPerSegment := lower.GetBytesPerSegment()
segCount := lower.GetSegmentCount()
segPrefs := make([]segPrefData, segCount)
networkSegIndex := getNetworkSegmentIndex(prefLength, bytesPerSegment, bitsPerSegment)
for i := networkSegIndex; i < segCount; i++ {
segPrefLength := getPrefixedSegmentPrefixLength(bitsPerSegment, prefLength, i)
segPrefs[i] = segPrefData{segPrefLength, bitsPerSegment - segPrefLength.bitCount()}
}
hostSegIndex := getHostSegmentIndex(prefLength, bytesPerSegment, bitsPerSegment)
return lower.rangeIterator(
rng.upper,
true,
cacheBitCount(prefLength),
(*IPAddress).GetSegment,
func(seg *IPAddressSegment, index int) Iterator[*IPAddressSegment] {
return seg.Iterator()
},
func(addr1, addr2 *IPAddress, index int) bool {
segPref := segPrefs[index]
if segPref.prefLen == nil {
return addr1.GetSegment(index).GetSegmentValue() == addr2.GetSegment(index).GetSegmentValue()
}
shift := segPref.shift
return addr1.GetSegment(index).GetSegmentValue()>>uint(shift) == addr2.GetSegment(index).GetSegmentValue()>>uint(shift)
},
networkSegIndex,
hostSegIndex,
func(seg *IPAddressSegment, index int) Iterator[*IPAddressSegment] {
segPref := segPrefs[index]
segPrefLen := segPref.prefLen
if segPrefLen == nil {
return seg.Iterator()
}
return seg.PrefixedBlockIterator(segPrefLen.bitCount())
},
)
}
// PrefixIterator provides an iterator to iterate through the individual prefixes of the given prefix length in this address range,
// each iterated element spanning the range of values for its prefix.
//
// It is similar to the prefix block iterator, except for possibly the first and last iterated elements, which might not be prefix blocks,
// instead constraining themselves to values from this range.
//
// Since a range between two arbitrary addresses cannot always be represented with a single IPAddress instance,
// the returned iterator iterates through SequentialRange instances.
//
// For instance, if iterating from "1.2.3.4" to "1.2.4.5" with prefix 8, the range shares the same prefix of value 1,
// but the range cannot be represented by the address "1.2.3-4.4-5" which does not include "1.2.3.255" or "1.2.4.0" both of which are in the original range.
// Nor can the range be represented by "1.2.3-4.0-255" which includes "1.2.4.6" and "1.2.3.3", both of which were not in the original range.
// A SequentialRange is thus required to represent that prefixed range.
func (rng *SequentialRange[T]) PrefixIterator(prefLength BitCount) Iterator[*SequentialRange[T]] {
rng = rng.init()
lower := rng.lower
if !rng.isMultiple {
return &singleIterator[*SequentialRange[T]]{original: rng}
}
prefLength = checkSubnet(lower, prefLength)
return &sequRangeIterator[T]{
rng: rng,
creator: newSequRange[T],
prefixBlockIterator: rng.PrefixBlockIterator(prefLength),
prefixLength: prefLength,
}
}
// Overlaps returns true if this sequential range overlaps with the given sequential range.
func (rng *SequentialRange[T]) Overlaps(other *SequentialRange[T]) bool {
rng = rng.init()
return compareLowIPAddressValues(other.GetLower(), rng.upper) <= 0 &&
compareLowIPAddressValues(other.GetUpper(), rng.lower) >= 0
}
// Intersect returns the intersection of this range with the given range, a range which includes those addresses found in both.
func (rng *SequentialRange[T]) Intersect(other *SequentialRange[T]) *SequentialRange[T] {
rng = rng.init()
other = other.init()
otherLower, otherUpper := other.GetLower(), other.GetUpper()
lower, upper := rng.lower, rng.upper
if compareLowIPAddressValues(lower, otherLower) <= 0 {
if compareLowIPAddressValues(upper, otherUpper) >= 0 { // l, ol, ou, u
return other
}
comp := compareLowIPAddressValues(upper, otherLower)
if comp < 0 { // l, u, ol, ou
return nil
}
return newSequRangeUnchecked(otherLower, upper, comp != 0) // l, ol, u, ou
} else if compareLowIPAddressValues(otherUpper, upper) >= 0 {
return rng
}
comp := compareLowIPAddressValues(otherUpper, lower)
if comp < 0 {
return nil
}
return newSequRangeUnchecked(lower, otherUpper, comp != 0)
}
// CoverWithPrefixBlock returns the minimal-size prefix block that covers all the addresses in this range.
// The resulting block will have a larger count than this, unless this range already directly corresponds to a prefix block.
func (rng *SequentialRange[T]) CoverWithPrefixBlock() T {
return rng.GetLower().CoverWithPrefixBlockTo(rng.GetUpper())
}
// SpanWithPrefixBlocks returns an array of prefix blocks that spans the same set of addresses as this range.
func (rng *SequentialRange[T]) SpanWithPrefixBlocks() []T {
return rng.GetLower().SpanWithPrefixBlocksTo(rng.GetUpper())
}
// SpanWithSequentialBlocks produces the smallest slice of sequential blocks that cover the same set of addresses as this range.
// This slice can be shorter than that produced by SpanWithPrefixBlocks and is never longer.
func (rng *SequentialRange[T]) SpanWithSequentialBlocks() []T {
res := rng.GetLower().SpanWithSequentialBlocksTo(rng.GetUpper())
return res
}
// Join joins the receiver with the given ranges into the fewest number of ranges.
// The returned array will be sorted by ascending lowest range value.
// Nil ranges are tolerated, and ignored.
func (rng *SequentialRange[T]) Join(ranges ...*SequentialRange[T]) []*SequentialRange[T] {
ranges = append(append(make([]*SequentialRange[T], 0, len(ranges)+1), ranges...), rng)
return joinRanges(ranges)
}
// JoinTo joins this range to the other if they are contiguous. If this range overlaps with the given range,
// or if the highest value of the lower range is one below the lowest value of the higher range,
// then the two are joined into a new larger range that is returned.
// Otherwise, nil is returned.
func (rng *SequentialRange[T]) JoinTo(other *SequentialRange[T]) *SequentialRange[T] {
rng = rng.init()
other = other.init()
otherLower, otherUpper := other.GetLower(), other.GetUpper()
lower, upper := rng.lower, rng.upper
lowerComp := compareLowIPAddressValues(lower, otherLower)
if !rng.Overlaps(other) {
if lowerComp >= 0 {
if otherUpper.Increment(1).Equal(lower) {
return newSequRangeUnchecked[T](otherLower, upper, true)
}
} else {
if upper.Increment(1).Equal(otherLower) {
return newSequRangeUnchecked[T](lower, otherUpper, true)
}
}
return nil
}
upperComp := compareLowIPAddressValues(upper, otherUpper)
var lowestLower, highestUpper T
if lowerComp >= 0 {
if lowerComp == 0 && upperComp == 0 {
return rng
}
lowestLower = otherLower
} else {
lowestLower = lower
}
if upperComp >= 0 {
highestUpper = upper
} else {
highestUpper = otherUpper
}
return newSequRangeUnchecked(lowestLower, highestUpper, true)
}
// Extend extends this sequential range to include all address in the given range.
// If the argument has a different IP version than this, nil is returned.
// Otherwise, this method returns the range that includes this range, the given range, and all addresses in-between.
func (rng *SequentialRange[T]) Extend(other *SequentialRange[T]) *SequentialRange[T] {
rng = rng.init()
other = other.init()
if !rng.lower.GetIPVersion().Equal(other.lower.GetIPVersion()) {
return nil
}
otherLower, otherUpper := other.GetLower(), other.GetUpper()
lower, upper := rng.lower, rng.upper
lowerComp := compareLowIPAddressValues(lower, otherLower)
upperComp := compareLowIPAddressValues(upper, otherUpper)
if lowerComp > 0 { //
if upperComp <= 0 { // ol l u ou
return other
}
// ol l ou u or ol ou l u
return newSequRangeUnchecked(otherLower, upper, true)
}
// lowerComp <= 0
if upperComp >= 0 { // l ol ou u
return rng
}
return newSequRangeUnchecked(lower, otherUpper, true) // l ol u ou or l u ol ou
}
// Subtract subtracts the given range from the receiver range, to produce either zero, one, or two address ranges that contain the addresses in the receiver range and not in the given range.
// If the result has length 2, the two ranges are ordered by ascending lowest range value.
func (rng *SequentialRange[T]) Subtract(other *SequentialRange[T]) []*SequentialRange[T] {
rng = rng.init()
other = other.init()
otherLower, otherUpper := other.GetLower(), other.GetUpper()
lower, upper := rng.lower, rng.upper
if compareLowIPAddressValues(lower, otherLower) < 0 {
if compareLowIPAddressValues(upper, otherUpper) > 0 { // l ol ou u
return []*SequentialRange[T]{
newSequRangeCheckSize(lower, otherLower.Increment(-1)),
newSequRangeCheckSize(otherUpper.Increment(1), upper),
}
} else {
comp := compareLowIPAddressValues(upper, otherLower)
if comp < 0 { // l u ol ou
return []*SequentialRange[T]{rng}
} else if comp == 0 { // l u == ol ou
return []*SequentialRange[T]{newSequRangeCheckSize(lower, upper.Increment(-1))}
}
return []*SequentialRange[T]{newSequRangeCheckSize(lower, otherLower.Increment(-1))} // l ol u ou
}
} else if compareLowIPAddressValues(otherUpper, upper) >= 0 { // ol l u ou
return make([]*SequentialRange[T], 0, 0)
} else {
comp := compareLowIPAddressValues(otherUpper, lower)
if comp < 0 {
return []*SequentialRange[T]{rng} // ol ou l u
} else if comp == 0 {
return []*SequentialRange[T]{newSequRangeCheckSize(lower.Increment(1), upper)} // ol ou == l u
}
return []*SequentialRange[T]{newSequRangeCheckSize(otherUpper.Increment(1), upper)} // ol l ou u
}
}
// ToKey creates the associated address range key.
// While address ranges can be compared with the Compare or Equal methods as well as various provided instances of AddressComparator,
// they are not comparable with Go operators.
// However, SequentialRangeKey instances are comparable with Go operators, and thus can be used as map keys.
func (rng *SequentialRange[T]) ToKey() SequentialRangeKey[T] {
rng = rng.init()
return SequentialRangeKey[T]{
lowerKey: rng.lower.toKey(),
upperKey: rng.upper.toKey(),
}
}
// IsIPv4 returns true if this sequential address range is an IPv4 sequential address range. If so, use ToIPv4 to convert to the IPv4-specific type.
func (rng *SequentialRange[T]) IsIPv4() bool { // returns false when lower is nil
if rng != nil {
t := any(rng.GetLower())
if _, ok := t.(*IPv4Address); ok {
return true
} else if addr, ok := t.(*IPAddress); ok {
return addr.IsIPv4()
}
}
return false
}
// IsIPv6 returns true if this sequential address range is an IPv6 sequential address range. If so, use ToIPv6 to convert to the IPv6-specific type.
func (rng *SequentialRange[T]) IsIPv6() bool { // returns false when lower is nil
if rng != nil {
t := any(rng.GetLower())
if _, ok := t.(*IPv6Address); ok {
return true
} else if addr, ok := t.(*IPAddress); ok {
return addr.IsIPv6()
}
}
return false
}
// ToIPv4 converts to a SequentialRange[*IPv4Address] if this address range is an IPv4 address range.
// If not, ToIPv4 returns nil.
//
// ToIPv4 can be called with a nil receiver, enabling you to chain this method with methods that might return a nil pointer.
func (rng *SequentialRange[T]) ToIPv4() *SequentialRange[*IPv4Address] {
if rng != nil {
if ipv4, ok := any(rng).(*SequentialRange[*IPv4Address]); ok {
return ipv4
} else {
t := any(rng.GetLower())
if addr, ok := t.(*IPAddress); ok && addr.IsIPv4() {
t = any(rng.GetUpper())
return newSequRangeUnchecked(addr.ToIPv4(), t.(*IPAddress).ToIPv4(), rng.isMultiple)
}
}
}
return nil
}
// ToIPv6 converts to a SequentialRange[*IPv6Address] if this address range is an IPv6 address range.
// If not, ToIPv6 returns nil.
//
// ToIPv6 can be called with a nil receiver, enabling you to chain this method with methods that might return a nil pointer.
func (rng *SequentialRange[T]) ToIPv6() *SequentialRange[*IPv6Address] {
if rng != nil {
if ipv6, ok := any(rng).(*SequentialRange[*IPv6Address]); ok {
return ipv6
} else {
t := any(rng.GetLower())
if addr, ok := t.(*IPAddress); ok && addr.IsIPv6() {
t = any(rng.GetUpper())
return newSequRangeUnchecked(addr.ToIPv6(), t.(*IPAddress).ToIPv6(), rng.isMultiple)
}
}
}
return nil
}
// ToIP converts to a SequentialRange[*IPAddress], a polymorphic type usable with all IP address sequential ranges.
//
// ToIP can be called with a nil receiver, enabling you to chain this method with methods that might return a nil pointer.
func (rng *SequentialRange[T]) ToIP() *SequentialRange[*IPAddress] {
if rng != nil {
if ip, ok := any(rng).(*SequentialRange[*IPAddress]); ok {
return ip
}
return newSequRangeUnchecked(rng.GetLower().ToIP(), rng.GetUpper().ToIP(), rng.isMultiple)
}
return nil
}
func newSequRangeUnchecked[T SequentialRangeConstraint[T]](lower, upper T, isMult bool) *SequentialRange[T] {
return &SequentialRange[T]{
lower: lower,
upper: upper,
isMultiple: isMult,
cache: &rangeCache{},
}
}
func newSequRangeCheckSize[T SequentialRangeConstraint[T]](lower, upper T) *SequentialRange[T] {
return newSequRangeUnchecked(lower, upper, !lower.equalsSameVersion(upper))
}
func newSequRange[T SequentialRangeConstraint[T]](first, other T) *SequentialRange[T] {
var lower, upper T
var isMult bool
if f := first.Contains(other); f || other.Contains(first) {