我需要能够输出不在给定IP地址范围列表中的所有IP地址范围。
我可以使用某种算法来完成这种任务,我可以将其转换为工作代码吗?
我认为简单解决方案的关键是要记住IP地址可以被视为多个类型的长,因此可以对它们进行排序。
我假设排除的范围以“漂亮”的方式给出,意味着没有重叠,没有与全局范围的部分重叠等等。您当然可以在以后添加此类输入检查。
在这个例子中,我将所有网络范围(全局,包含,排除)作为NetworkRange
类的实例。
以下是NetworkRange
的实施。注意方法splitByExcludedRange
和includes
。
public class NetworkRange {
private long startAddress;
private long endAddress;
public NetworkRange(String start, String end) {
startAddress = addressRepresentationToAddress(start);
endAddress = addressRepresentationToAddress(end);
}
public NetworkRange(long start, long end) {
startAddress = start;
endAddress = end;
}
public String getStartAddress() {
return addressToAddressRepresentation(startAddress);
}
public String getEndAddress() {
return addressToAddressRepresentation(endAddress);
}
static String addressToAddressRepresentation(long address) {
String result = String.valueOf(address % 256);
for (int i = 1; i < 4; i++) {
address = address / 256;
result = String.valueOf(address % 256) + "." + result;
}
return result;
}
static long addressRepresentationToAddress(String addressRep) {
long result = 0L;
String[] tokens = addressRep.split("\\.");
for (int i = 0; i < 4; i++) {
result += Math.pow(256, i) * Long.parseLong(tokens[3-i]);
}
return result;
}
public List<NetworkRange> splitByExcludedRange(NetworkRange excludedRange) {
if (this.startAddress == excludedRange.startAddress && this.endAddress == excludedRange.endAddress)
return Arrays.asList();
if (this.startAddress == excludedRange.startAddress)
return Arrays.asList(new NetworkRange(excludedRange.endAddress+1, this.endAddress));
if (this.endAddress == excludedRange.endAddress)
return Arrays.asList(new NetworkRange(this.startAddress, excludedRange.startAddress-1));
return Arrays.asList(new NetworkRange(this.startAddress, excludedRange.startAddress-1),
new NetworkRange(excludedRange.endAddress+1, this.endAddress));
}
public boolean includes(NetworkRange excludedRange) {
return this.startAddress <= excludedRange.startAddress && this.endAddress >= excludedRange.endAddress;
}
public String toString() {
return "[" + getStartAddress() + "-" + getEndAddress() + "]";
}
}
现在来自计算包含的网络范围的类。它接受构造函数中的全局范围。
public class RangeProducer {
private NetworkRange global;
public RangeProducer(NetworkRange global) {
this.global = global;
}
public List<NetworkRange> computeEffectiveRanges(List<NetworkRange> excludedRanges) {
List<NetworkRange> effectiveRanges = new ArrayList<>();
effectiveRanges.add(global);
List<NetworkRange> effectiveRangesSplitted = new ArrayList<>();
for (NetworkRange excludedRange : excludedRanges) {
for (NetworkRange effectiveRange : effectiveRanges) {
if (effectiveRange.includes(excludedRange)) {
effectiveRangesSplitted.addAll(effectiveRange.splitByExcludedRange(excludedRange));
} else {
effectiveRangesSplitted.add(effectiveRange);
}
}
effectiveRanges = effectiveRangesSplitted;
effectiveRangesSplitted = new ArrayList<>();
}
return effectiveRanges;
}
}
您可以运行以下示例:
public static void main(String[] args) {
NetworkRange global = new NetworkRange("10.0.0.0", "10.255.255.255");
NetworkRange ex1 = new NetworkRange("10.0.0.0", "10.0.1.255");
NetworkRange ex2 = new NetworkRange("10.1.0.0", "10.1.1.255");
NetworkRange ex3 = new NetworkRange("10.6.1.0", "10.6.2.255");
List<NetworkRange> excluded = Arrays.asList(ex1, ex2, ex3);
RangeProducer producer = new RangeProducer(global);
for (NetworkRange effective : producer.computeEffectiveRanges(excluded)) {
System.out.println(effective);
}
}
输出应该是:
[10.0.2.0-10.0.255.255]
[10.1.2.0-10.6.0.255]
[10.6.3.0-10.255.255.255]
首先,我假设你的意思是你得到一个或多个不相交的CIDR范围作为输入,并且需要产生所有CIDR范围的列表,不包括任何给定的输入。为方便起见,我们进一步假设输入不包括整个IP地址空间:即0.0.0.0/0
。 (这可以通过一个特殊情况来适应,但不是很有意义。)
我之前编写的代码类似于此,虽然我不能自由地共享代码,但我可以描述这种方法。它本质上是一种二进制搜索算法,其中您重复平分整个地址空间,直到您隔离了您感兴趣的一个范围。
将IP地址空间视为二叉树:根部是完整的IPv4地址空间0.0.0.0/0
。它的孩子每个代表地址空间的一半:0.0.0.0/1
和128.0.0.0/1.
反过来,这些可以被细分为分别创建儿童0.0.0.0/2
/ 64.0.0.0/2
和128.0.0.0/2
/ 192.0.0.0/2,
。继续这一直向下,你最终得到2**32
叶子,每个叶子代表一个/32
(即一个地址)。
现在,将此树视为从输入列表中排除的地址空间的一部分。因此,您的任务是遍历此树,从树中的输入列表中查找每个范围,并删除输入中树的所有部分,留下地址空间的其余部分。
幸运的是,您无需实际创建所有2**32
叶子。 CIDR N
的每个节点都可以假设包含CIDR N+1
及以上的所有节点,如果没有为它创建子节点(你需要一个标志来记住它已被细分 - 即不再是一片叶子 - 见下面的原因)。
因此,首先,整个地址空间存在于树中,但都可以由单个叶节点表示。调用树excluded,
并使用单个节点0.0.0.0/0.
对其进行初始化
现在,考虑第一个输入范围 - 我们称之为trial
(我将使用14.27.34.0/24
作为初始trial
值,仅为演示提供具体值)。任务是从trial
中删除excluded
,留下其余的地址空间。
首先将current
节点指针设置为excluded
根节点。
开始:
比较trial
CIDR和current
。如果它是相同的,那么你已经完成了(但是如果你的输入范围是不相交的并且你已经从输入中排除了0.0.0.0/0
,那么这绝不应该发生)。
否则,如果current
是叶节点(尚未细分,意味着它代表此CIDR级别及以下的整个地址空间),请设置其细分标志,并为其创建两个子节点:指向上半部分的left
指针它的地址空间,以及指向后半部分的right
指针。适当地标记每一个(对于根节点的子节点,将是0.0.0.0/1
和128.0.0.0/1
)。
确定trial
CIDR是否属于current
的左侧或右侧。对于我们的初始trial
值,它在左边。现在,如果那边的指针已经是NULL
,那么你又完成了(尽管如果你的输入范围是不相交的,那么“不会发生”)。
如果trial
CIDR完全等同于那一侧节点中的CIDR,那么只需释放节点(以及它可能拥有的任何子节点,如果只有不相交的输入那么它也应该是无),将指针设置为那边NULL
你完成了你刚刚通过从树上切下那片叶子来排除整个范围。
如果试验值不完全等于该侧节点中的CIDR,则将current
设置为该侧并重新开始(即跳转到上面的开始标签)。
因此,在14.27.34.0/24
的初始输入范围内,您将首先将0.0.0.0/0
拆分为0.0.0.0/1
和128.0.0.0/1
。然后你将在左侧下降并将0.0.0.0/1
分成0.0.0.0/2
和64.0.0.0/2.
然后你将再次向左下方创建0.0.0.0/3
和32.0.0.0/3.
等等,直到23次分裂后,你将把14.27.34.0/23
分成14.27.34.0/24
和14.27.35.0/24.
你将然后删除左侧的14.27.34.0/24
子节点并将其指针设置为NULL
,留下另一个。
这将为您留下一个包含24个叶子节点的稀疏树(在您删除目标节点之后)。剩余的叶节点标有*:
(ROOT)
0.0.0.0/0
/ \
0.0.0.0/1 128.0.0.0/1*
/ \
0.0.0.0/2 64.0.0.0/2*
/ \
0.0.0.0/3 32.0.0.0.0/3*
/ \
0.0.0.0/4 16.0.0.0/4*
/ \
*0.0.0.0/5 8.0.0.0/5
/ \
*8.0.0.0/6 12.0.0.0/6
/ \
*12.0.0.0/7 14.0.0.0/7
/ \
14.0.0.0/8 15.0.0.0/8*
/ \
...
/ \
*14.27.32.0/23 14.27.34.0/23
/ \
(null) 14.27.35.0/24*
(14.27.34.0/24)
对于每个剩余的输入范围,您将再次遍历树,在必要时将叶节点平分,通常会产生更多叶子,但总是会切掉地址空间的某些部分。
最后,您只需以任何方便的顺序遍历生成的树,收集剩余叶子的CIDR。请注意,在此阶段中,您必须排除先前已细分的那些。例如,在上面的树中,如果你下一个处理输入范围14.27.35.0/24
,你会留下没有子节点的14.27.34.0/23
,但是它的两半都是单独剪切的,它不应该包含在输出中。 (有了一些额外的复杂功能,你当然可以折叠它上面的节点以适应这种情况,但是在每个节点中保留一个标志会更容易。)
首先,您描述的内容可以简化为:
我建议使用interval tree,每个节点存储一个间隔,你可以有效地插入和删除节点;并查询给定点(= IP地址)的重叠。
如果你可以保证没有重叠,你可以使用一个简单的TreeSet<String>
,但你必须保证(正确排序)所有字符串都使用xxx.xxx.xxx.xxx-yyy.yyy.yyy.yyy
零填充格式。
一旦您的间隔在树中,您就可以生成所需的输出,假设没有间隔重叠,通过执行树的深度优先预先遍历遍历,并将每个访问节点的开始和结束存储在列表中。鉴于此列表,
请注意,0.0.0.0和255.255.255.255实际上并不是有效的,可路由的IP。如果您确实需要输出真实感知的IP,则应阅读相关的RFC。