cpython: 8867874a2b7d (original) (raw)

Mercurial > cpython

changeset 90717:8867874a2b7d

Issue #20826: Optimize ipaddress.collapse_addresses(). [#20826]

Antoine Pitrou solipsis@pitrou.net
date	Thu, 15 May 2014 20:40:53 +0200
parents	2711677cf874
children	dbf728f9a2f0
files	Lib/ipaddress.py Misc/NEWS
diffstat	2 files changed, 28 insertions(+), 27 deletions(-)[+] [-] Lib/ipaddress.py 53 Misc/NEWS 2

line wrap: on

line diff

--- a/Lib/ipaddress.py +++ b/Lib/ipaddress.py @@ -253,7 +253,7 @@ def summarize_address_range(first, last) break -def _collapse_addresses_recursive(addresses): +def _collapse_addresses_internal(addresses): """Loops through the addresses, collapsing concurrent netblocks. Example: @@ -263,7 +263,7 @@ def _collapse_addresses_recursive(addres ip3 = IPv4Network('192.0.2.128/26') ip4 = IPv4Network('192.0.2.192/26')

   _collapse_addresses_recursive([ip1, ip2, ip3, ip4]) ->[](#l1.16)

   _collapse_addresses_internal([ip1, ip2, ip3, ip4]) ->[](#l1.17)
     [IPv4Network('192.0.2.0/24')][](#l1.18)

This shouldn't be called directly; it is called via @@ -277,28 +277,29 @@ def _collapse_addresses_recursive(addres passed. """

while True:
```
   last_addr = None[](#l1.26)
```
```
   ret_array = [][](#l1.27)
```
```
   optimized = False[](#l1.28)
```

```
   for cur_addr in addresses:[](#l1.30)
```
```
       if not ret_array:[](#l1.31)
```

           last_addr = cur_addr[](#l1.32)

           ret_array.append(cur_addr)[](#l1.33)

       elif (cur_addr.network_address >= last_addr.network_address and[](#l1.34)

           cur_addr.broadcast_address <= last_addr.broadcast_address):[](#l1.35)

```
           optimized = True[](#l1.36)
```

       elif cur_addr == list(last_addr.supernet().subnets())[1]:[](#l1.37)

           ret_array[-1] = last_addr = last_addr.supernet()[](#l1.38)

```
           optimized = True[](#l1.39)
```
```
       else:[](#l1.40)
```

           last_addr = cur_addr[](#l1.41)

           ret_array.append(cur_addr)[](#l1.42)

```
   addresses = ret_array[](#l1.44)
```
```
   if not optimized:[](#l1.45)
```
```
       return addresses[](#l1.46)
```

First merge
to_merge = list(addresses)
subnets = {}
while to_merge:
```
   net = to_merge.pop()[](#l1.51)
```
```
   supernet = net.supernet()[](#l1.52)
```

   existing = subnets.get(supernet)[](#l1.53)

```
   if existing is None:[](#l1.54)
```

       subnets[supernet] = net[](#l1.55)

```
   elif existing != net:[](#l1.56)
```

       # Merge consecutive subnets[](#l1.57)

```
       del subnets[supernet][](#l1.58)
```

       to_merge.append(supernet)[](#l1.59)

Then iterate over resulting networks, skipping subsumed subnets
last = None
for net in sorted(subnets.values()):
```
   if last is not None:[](#l1.63)
```

       # Since they are sorted, last.network_address <= net.network_address[](#l1.64)

```
       # is a given.[](#l1.65)
```

       if last.broadcast_address >= net.broadcast_address:[](#l1.66)

```
           continue[](#l1.67)
```
```
   yield net[](#l1.68)
```
```
   last = net[](#l1.69)
```

def collapse_addresses(addresses): @@ -347,15 +348,13 @@ def collapse_addresses(addresses): # sort and dedup ips = sorted(set(ips))

nets = sorted(set(nets))

while i < len(ips): (first, last) = _find_address_range(ips[i:]) i = ips.index(last) + 1 addrs.extend(summarize_address_range(first, last))

return iter(_collapse_addresses_recursive(sorted(

   addrs + nets, key=_BaseNetwork._get_networks_key)))[](#l1.85)

return _collapse_addresses_internal(addrs + nets)

def get_mixed_type_key(obj):

--- a/Misc/NEWS +++ b/Misc/NEWS @@ -84,6 +84,8 @@ Core and Builtins Library ------- +- Issue #20826: Optimize ipaddress.collapse_addresses(). +

Issue #21487: Optimize ipaddress.summarize_address_range() and ipaddress.{IPv4Network,IPv6Network}.subnets().

cpython: 8867874a2b7d (original) (raw)

Mercurial > cpython

changeset 90717:8867874a2b7d

First merge

Then iterate over resulting networks, skipping subsumed subnets