line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
#!/usr/bin/perl |
2
|
|
|
|
|
|
|
|
3
|
|
|
|
|
|
|
# |
4
|
|
|
|
|
|
|
# Copyright (C) 2016 Joel C. Maslak |
5
|
|
|
|
|
|
|
# All Rights Reserved - See License |
6
|
|
|
|
|
|
|
# |
7
|
|
|
|
|
|
|
|
8
|
|
|
|
|
|
|
package Range::Merge v0.01.00; |
9
|
|
|
|
|
|
|
$Range::Merge::VERSION = '1.002'; |
10
|
4
|
|
|
4
|
|
2546
|
use Range::Merge::Boilerplate 'script'; |
|
4
|
|
|
|
|
5
|
|
|
4
|
|
|
|
|
23
|
|
11
|
|
|
|
|
|
|
|
12
|
|
|
|
|
|
|
require Exporter; |
13
|
|
|
|
|
|
|
our @ISA = qw(Exporter); |
14
|
|
|
|
|
|
|
our @EXPORT_OK = qw(merge merge_ipv4); |
15
|
|
|
|
|
|
|
|
16
|
4
|
|
|
4
|
|
3630
|
use List::Util qw(max); |
|
4
|
|
|
|
|
5
|
|
|
4
|
|
|
|
|
196
|
|
17
|
4
|
|
|
4
|
|
1859
|
use Net::CIDR; |
|
4
|
|
|
|
|
14907
|
|
|
4
|
|
|
|
|
170
|
|
18
|
4
|
|
|
4
|
|
1896
|
use Socket; |
|
4
|
|
|
|
|
10283
|
|
|
4
|
|
|
|
|
6275
|
|
19
|
|
|
|
|
|
|
|
20
|
|
|
|
|
|
|
# ABSTRACT: Merges ranges of data including subset/superset ranges |
21
|
|
|
|
|
|
|
|
22
|
|
|
|
|
|
|
|
23
|
|
|
|
|
|
|
|
24
|
14
|
50
|
|
14
|
1
|
174
|
sub merge($ranges) { |
|
14
|
50
|
|
|
|
25
|
|
|
14
|
|
|
|
|
15
|
|
|
14
|
|
|
|
|
10
|
|
25
|
14
|
|
|
|
|
27
|
my $sorted = _sort($ranges); |
26
|
14
|
|
|
|
|
18
|
my $split = []; |
27
|
14
|
|
|
|
|
27
|
_split($ranges, $split); |
28
|
14
|
|
|
|
|
25
|
return _combine($split); |
29
|
|
|
|
|
|
|
} |
30
|
|
|
|
|
|
|
|
31
|
|
|
|
|
|
|
|
32
|
12
|
50
|
|
12
|
1
|
104975
|
sub merge_ipv4($cidr) { |
|
12
|
50
|
|
|
|
26
|
|
|
12
|
|
|
|
|
11
|
|
|
12
|
|
|
|
|
10
|
|
33
|
12
|
|
|
|
|
11
|
my $ranges = []; |
34
|
12
|
|
|
|
|
114
|
@$ranges = map { _cidr2range($_) } @$cidr; |
|
66123
|
|
|
|
|
59413
|
|
35
|
12
|
|
|
|
|
1384
|
my $combined = merge($ranges); |
36
|
12
|
|
|
|
|
22
|
return _range2cidr($combined); |
37
|
|
|
|
|
|
|
} |
38
|
|
|
|
|
|
|
|
39
|
66123
|
50
|
|
66123
|
|
91694
|
sub _cidr2range($cidr) { |
|
66123
|
50
|
|
|
|
70874
|
|
|
66123
|
|
|
|
|
47407
|
|
|
66123
|
|
|
|
|
36004
|
|
40
|
66123
|
|
|
|
|
64920
|
my ($ip, @a) = @$cidr; |
41
|
66123
|
|
|
|
|
76093
|
my ($range) = Net::CIDR::cidr2range($ip); |
42
|
66123
|
|
|
|
|
3665019
|
my (@parts) = map { unpack('N', inet_aton($_)) } split(/-/, $range); |
|
132246
|
|
|
|
|
247710
|
|
43
|
|
|
|
|
|
|
|
44
|
66123
|
|
|
|
|
105859
|
return [ @parts, @a ]; |
45
|
|
|
|
|
|
|
} |
46
|
|
|
|
|
|
|
|
47
|
12
|
50
|
|
12
|
|
19
|
sub _range2cidr($ranges) { |
|
12
|
50
|
|
|
|
20
|
|
|
12
|
|
|
|
|
25
|
|
|
12
|
|
|
|
|
8
|
|
48
|
12
|
|
|
|
|
7
|
my @output; |
49
|
12
|
|
|
|
|
16
|
foreach my $range (@$ranges) { |
50
|
24
|
|
|
|
|
30
|
my ($start, $end, @other) = @$range; |
51
|
24
|
|
|
|
|
115
|
$start = inet_ntoa(pack('N', $start)); |
52
|
24
|
|
|
|
|
58
|
$end = inet_ntoa(pack('N', $end )); |
53
|
24
|
|
|
|
|
64
|
foreach my $cidr (Net::CIDR::range2cidr("$start-$end")) { |
54
|
32
|
|
|
|
|
2549
|
push @output, [ $cidr, @other ]; |
55
|
|
|
|
|
|
|
} |
56
|
|
|
|
|
|
|
} |
57
|
12
|
|
|
|
|
6089
|
return \@output; |
58
|
|
|
|
|
|
|
} |
59
|
|
|
|
|
|
|
|
60
|
|
|
|
|
|
|
# Sorts by starting address and then by reverse (less specific to more |
61
|
|
|
|
|
|
|
# specific) |
62
|
14
|
50
|
|
14
|
|
25
|
sub _sort($ranges) { |
|
14
|
50
|
|
|
|
20
|
|
|
14
|
|
|
|
|
13
|
|
|
14
|
|
|
|
|
8
|
|
63
|
14
|
50
|
|
|
|
364
|
my (@output) = sort { ($a->[0] <=> $b->[0]) || ($b->[1] <=> $a->[0]) } @$ranges; |
|
66139
|
|
|
|
|
75578
|
|
64
|
14
|
|
|
|
|
25
|
return \@output; |
65
|
|
|
|
|
|
|
} |
66
|
|
|
|
|
|
|
|
67
|
0
|
0
|
|
0
|
|
0
|
sub _merge($ranges) { |
|
0
|
0
|
|
|
|
0
|
|
|
0
|
|
|
|
|
0
|
|
|
0
|
|
|
|
|
0
|
|
68
|
0
|
|
|
|
|
0
|
my $split = []; |
69
|
0
|
|
|
|
|
0
|
_split($ranges, $split); |
70
|
0
|
|
|
|
|
0
|
return _combine($split); |
71
|
|
|
|
|
|
|
} |
72
|
|
|
|
|
|
|
|
73
|
14
|
50
|
|
14
|
|
26
|
sub _combine($ranges) { |
|
14
|
50
|
|
|
|
30
|
|
|
14
|
|
|
|
|
10
|
|
|
14
|
|
|
|
|
13
|
|
74
|
14
|
|
|
|
|
11
|
my @output; |
75
|
|
|
|
|
|
|
|
76
|
|
|
|
|
|
|
my $last; |
77
|
14
|
|
|
|
|
18
|
foreach my $range (@$ranges) { |
78
|
66133
|
100
|
|
|
|
65943
|
if (!defined($last)) { |
79
|
14
|
|
|
|
|
21
|
$last = [ @$range ]; |
80
|
14
|
|
|
|
|
17
|
next; |
81
|
|
|
|
|
|
|
} |
82
|
66119
|
100
|
66
|
|
|
139947
|
if (($last->[1] == $range->[0] - 1) && (scalar(@$last) == scalar(@$range))) { |
83
|
66105
|
|
|
|
|
35909
|
my $nomatch; |
84
|
66105
|
|
|
|
|
76295
|
for (my $i=2; $i
|
85
|
3
|
100
|
|
|
|
8
|
if ($last->[$i] ne $range->[$i]) { |
86
|
2
|
|
|
|
|
1
|
$nomatch = 1; |
87
|
2
|
|
|
|
|
2
|
last; |
88
|
|
|
|
|
|
|
} |
89
|
|
|
|
|
|
|
} |
90
|
66105
|
100
|
|
|
|
51533
|
if ($nomatch) { |
91
|
2
|
|
|
|
|
2
|
push @output, $last; |
92
|
2
|
|
|
|
|
4
|
$last = [ @$range ]; |
93
|
|
|
|
|
|
|
} else { |
94
|
66103
|
|
|
|
|
54927
|
$last->[1] = $range->[1]; |
95
|
|
|
|
|
|
|
} |
96
|
|
|
|
|
|
|
} else { |
97
|
14
|
|
|
|
|
12
|
push @output, $last; |
98
|
14
|
|
|
|
|
21
|
$last = [ @$range ]; |
99
|
|
|
|
|
|
|
} |
100
|
|
|
|
|
|
|
} |
101
|
14
|
50
|
|
|
|
29
|
if (defined($last)) { push @output, $last } |
|
14
|
|
|
|
|
15
|
|
102
|
|
|
|
|
|
|
|
103
|
14
|
|
|
|
|
3221
|
return \@output; |
104
|
|
|
|
|
|
|
} |
105
|
|
|
|
|
|
|
|
106
|
14
|
50
|
|
14
|
|
29
|
sub _split($ranges, $output, $stack = []) { |
|
14
|
50
|
|
|
|
21
|
|
|
14
|
50
|
|
|
|
12
|
|
|
14
|
|
|
|
|
17
|
|
|
14
|
|
|
|
|
27
|
|
|
14
|
|
|
|
|
15
|
|
107
|
|
|
|
|
|
|
# Termination condition |
108
|
14
|
50
|
|
|
|
31
|
if (scalar($ranges->@*) == 0) { return undef; } |
|
0
|
|
|
|
|
0
|
|
109
|
|
|
|
|
|
|
|
110
|
|
|
|
|
|
|
# We just repeatedly call _add_to_stack |
111
|
14
|
|
|
|
|
20
|
foreach my $range ($ranges->@*) { |
112
|
66131
|
|
|
|
|
59287
|
_add_to_stack($range, $stack, $output); |
113
|
|
|
|
|
|
|
} |
114
|
|
|
|
|
|
|
|
115
|
|
|
|
|
|
|
# Return stack |
116
|
14
|
50
|
|
|
|
23
|
if (scalar($stack->@*)) { |
117
|
14
|
|
|
|
|
18
|
push $output->@*, $stack->@*; |
118
|
|
|
|
|
|
|
} |
119
|
|
|
|
|
|
|
|
120
|
14
|
|
|
|
|
15
|
return undef; |
121
|
|
|
|
|
|
|
} |
122
|
|
|
|
|
|
|
|
123
|
66131
|
50
|
|
66131
|
|
74760
|
sub _add_to_stack($range, $stack, $output) { |
|
66131
|
50
|
|
|
|
66722
|
|
|
66131
|
|
|
|
|
40819
|
|
|
66131
|
|
|
|
|
36010
|
|
|
66131
|
|
|
|
|
36771
|
|
|
66131
|
|
|
|
|
34785
|
|
124
|
66131
|
100
|
|
|
|
66746
|
if (!scalar($stack->@*)) { |
125
|
|
|
|
|
|
|
# Empty stack |
126
|
14
|
|
|
|
|
18
|
push $stack->@*, $range; |
127
|
14
|
|
|
|
|
24
|
return undef; |
128
|
|
|
|
|
|
|
} |
129
|
|
|
|
|
|
|
|
130
|
|
|
|
|
|
|
# We know the following: |
131
|
|
|
|
|
|
|
# |
132
|
|
|
|
|
|
|
# 1. The stack is sorted |
133
|
|
|
|
|
|
|
# 2. There are no overlapping elements |
134
|
|
|
|
|
|
|
# 2a. Thus we only have to split 1 element max |
135
|
|
|
|
|
|
|
# 3. The stack has at least one element |
136
|
|
|
|
|
|
|
|
137
|
66117
|
|
|
|
|
47287
|
my (@lstack) = grep { $_->[1] < $range->[0]} @$stack; |
|
66121
|
|
|
|
|
83119
|
|
138
|
66117
|
|
|
|
|
44529
|
my (@rstack) = grep { $_->[0] > $range->[1]} @$stack; |
|
66121
|
|
|
|
|
65258
|
|
139
|
66117
|
100
|
|
|
|
43932
|
my (@mid ) = grep { ($_->[0] <= $range->[1]) && ($_->[1] >= $range->[0])} @$stack; |
|
66121
|
|
|
|
|
158381
|
|
140
|
|
|
|
|
|
|
|
141
|
|
|
|
|
|
|
# Clear stack |
142
|
66117
|
|
|
|
|
46612
|
@$stack = (); |
143
|
|
|
|
|
|
|
|
144
|
|
|
|
|
|
|
# Output the stuff completely to the left of the new range |
145
|
66117
|
|
|
|
|
46011
|
push @$output, @lstack; |
146
|
|
|
|
|
|
|
|
147
|
|
|
|
|
|
|
# Option 1 -> No middle element, so just add the range (and the |
148
|
|
|
|
|
|
|
# right stack) to the stack |
149
|
66117
|
100
|
|
|
|
71681
|
if (!scalar(@mid)) { |
150
|
66112
|
|
|
|
|
41164
|
push @$stack, $range, @rstack; |
151
|
66112
|
|
|
|
|
65604
|
return undef; |
152
|
|
|
|
|
|
|
} |
153
|
|
|
|
|
|
|
|
154
|
|
|
|
|
|
|
# We start with the left and right parts of the element that might |
155
|
|
|
|
|
|
|
# need to be split. |
156
|
5
|
|
|
|
|
8
|
my (@left) = $mid[0]->@*; |
157
|
5
|
|
|
|
|
7
|
my (@right) = $mid[0]->@*; |
158
|
|
|
|
|
|
|
|
159
|
|
|
|
|
|
|
# Does the ele needing split start before the range? If so, add the piece |
160
|
|
|
|
|
|
|
# needed to the output |
161
|
5
|
50
|
|
|
|
15
|
if ($left[0] < $range->[0]) { |
162
|
5
|
|
|
|
|
11
|
@left[1] = $range->[0] - 1; |
163
|
5
|
50
|
|
|
|
10
|
if ($left[0] <= $left[1]) { |
164
|
5
|
|
|
|
|
7
|
push @$output, \@left; |
165
|
|
|
|
|
|
|
} |
166
|
|
|
|
|
|
|
} |
167
|
|
|
|
|
|
|
|
168
|
|
|
|
|
|
|
# We need to add the range to the stack |
169
|
5
|
|
|
|
|
5
|
push @$stack, $range; |
170
|
|
|
|
|
|
|
|
171
|
|
|
|
|
|
|
# Does the ele needing split end after the range? If so, add the |
172
|
|
|
|
|
|
|
# piece to the stack |
173
|
5
|
100
|
|
|
|
10
|
if ($right[1] > $range->[1]) { |
174
|
2
|
|
|
|
|
4
|
@right[0] = $range->[1] + 1; |
175
|
2
|
50
|
|
|
|
4
|
if ($right[0] <= $right[1]) { |
176
|
2
|
|
|
|
|
4
|
push @$stack, \@right; |
177
|
|
|
|
|
|
|
} |
178
|
|
|
|
|
|
|
} |
179
|
|
|
|
|
|
|
|
180
|
5
|
|
|
|
|
5
|
push @$stack, @rstack; |
181
|
|
|
|
|
|
|
|
182
|
5
|
|
|
|
|
10
|
return undef; |
183
|
|
|
|
|
|
|
} |
184
|
|
|
|
|
|
|
|
185
|
|
|
|
|
|
|
# Main element in the algorithm |
186
|
|
|
|
|
|
|
# sub _merge($ranges, $output, $stack) { |
187
|
|
|
|
|
|
|
# if (!scalar($stack->@*)) { |
188
|
|
|
|
|
|
|
# # Stack is empty |
189
|
|
|
|
|
|
|
# |
190
|
|
|
|
|
|
|
# if (!scalar($ranges->@*)) { |
191
|
|
|
|
|
|
|
# return undef; # No ranges, no stack |
192
|
|
|
|
|
|
|
# } |
193
|
|
|
|
|
|
|
# |
194
|
|
|
|
|
|
|
# push $stack->@*, unshift($ranges->@*); |
195
|
|
|
|
|
|
|
# } |
196
|
|
|
|
|
|
|
# |
197
|
|
|
|
|
|
|
# _output_stack($output, $stack); |
198
|
|
|
|
|
|
|
# } |
199
|
|
|
|
|
|
|
|
200
|
|
|
|
|
|
|
1; |
201
|
|
|
|
|
|
|
|
202
|
|
|
|
|
|
|
__END__ |