collapse_address_list is too slow

ipaddr.py

 #!/usr/bin/python
 #
 # Copyright 2007 Google Inc.
 #  Licensed to PSF under a Contributor Agreement.
 #
 # 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
@@ skipping 111 matching lines @@
 
     try:
         return IPv6(ipaddr)
     except (IPv6IpValidationError, IPv6NetmaskValidationError):
         pass
 
     raise ValueError('%r does not appear to be an IPv4 or IPv6 address' %
                      ipaddr)
 
 
+def _find_address_range(addresses):
+    """Find a sequence of addresses."""
+    first = last = addresses[0]
+    for ip in addresses[1:]:
+        if ip.ip == last.ip + 1:
+            last = ip
+        else:
+            break
+    return (first, last)
+
+def _get_prefix_length(number1, number2, bits):
+    """Get the number of leading bits that are same for two numbers."""
+    for i in range(bits):
+        if number1 >> i == number2 >> i:
+            return bits - i
+    return 0
+
+def _count_righthand_zero_bits(integer, bits):
+    """Count the number of zero bits on the right hand side."""
+    if integer == 0:
+        return bits
+    for i in range(bits):
+        if (integer >> i) % 2:
+            return i
+
+def summarize_address_range(first, last):
+    """Summarize a network range given the first and last IP addresses."""
+
+    if first.version != last.version:
+        raise ValueError("IP addresses must be same version")
+    if first > last:
+        raise ValueError("last IP address must be greater than first")
+
+    networks = []
+
+    if first.version == 4:
+        ip = IPv4
+    elif first.version == 6:
+        ip = IPv6
+    else:
+        raise ValueError("unknown IP version")
+
+    ip_bits = first.max_prefixlen
+    while first <= last:
+        nbits = _count_righthand_zero_bits(first.ip, ip_bits)
+        current = None
+        while True:
+            addend = 2**nbits - 1
+            current = first.ip + addend
+            nbits -= 1
+            if ip(current) <= last:
+                break
+        prefix = _get_prefix_length(first.ip, current, ip_bits)
+        networks.append(ip('%s/%s' % (first.ip_ext, prefix)))
+        if current == ip._ALL_ONES:
+            break
+        first = ip(current + 1)
+    return networks
+
 def _collapse_address_list_recursive(addresses):
     """Loops through the addresses, collapsing concurrent netblocks.
 
     Example:
 
         ip1 = IPv4('1.1.0.0/24')
         ip2 = IPv4('1.1.1.0/24')
         ip3 = IPv4('1.1.2.0/24')
         ip4 = IPv4('1.1.3.0/24')
         ip5 = IPv4('1.1.4.0/24')
@@ skipping 40 matching lines @@
         collapse_address_list([IPv4('1.1.0.0/24'), IPv4('1.1.1.0/24')]) ->
           [IPv4('1.1.0.0/23')]
 
     Args:
         addresses: A list of IPv4 or IPv6 objects.
 
     Returns:
         A list of IPv4 or IPv6 objects depending on what we were passed.
 
     """
+    _addresses = []
+    i = 0
+    ip_bits = addresses[0].max_prefixlen

[Peter Moody, 2009/06/02 21:05:19]

for internal access, I usually end up using the private variable directly just
to avoid as much overhead as possible.

+    # filter out IP addresses, dedup, and sort
+    addrs = sorted(set([ip for ip in addresses if ip.prefixlen == ip_bits]),
+        key=BaseIP._get_networks_key)
+    nets = [ip for ip in addresses if ip.prefixlen < ip_bits]
+
+    while i < len(addrs):
+        (first, last) = _find_address_range(addrs[i:])
+        i = addrs.index(last) + 1
+        _addresses.extend(
+            [IP(ip) for ip in summarize_address_range(first, last)])
+
     return _collapse_address_list_recursive(
-        sorted(addresses, key=BaseIP._get_networks_key))
+        sorted(_addresses + nets, key=BaseIP._get_networks_key))
 
 # backwards compatibility
 CollapseAddrList = collapse_address_list
 
 # Test whether this Python implementation supports byte objects that
 # are not identical to str ones.
 # We need to exclude platforms where bytes == str so that we can
 # distinguish between packed representations and strings, for example
 # b'12::' (the IPv4 address 49.50.58.58) and '12::' (an IPv6 address).
 try:
@@ skipping 380 matching lines @@
               IPv4(IPv4('192.168.1.1').ip) == IPv4('192.168.1.1')
 
         Raises:
             IPv4IpValidationError: If ipaddr isn't a valid IPv4 address.
             IPv4NetmaskValidationError: If the netmask isn't valid for
               an IPv4 address.
 
         """
         BaseIP.__init__(self)
         self._version = 4
+        self._max_prefixlen = 32
 
         # Efficient constructor from integer.
         if isinstance(ipaddr, int) or isinstance(ipaddr, long):
             self.ip = ipaddr
             self._prefixlen = 32
             self.netmask = self._ALL_ONES
             if ipaddr < 0 or ipaddr > self._ALL_ONES:
                 raise IPv4IpValidationError(ipaddr)
             return
 
@@ skipping 169 matching lines @@
             A boolean, True if the address is link-local per RFC 3927.
 
         """
         return self in IPv4('169.254.0.0/16')
 
     @property
     def version(self):
         return self._version
 
     @property
+    def max_prefixlen(self):

[Peter Moody, 2009/06/02 21:05:19]

this could be a property of BaseIP

+        return self._max_prefixlen
+
+    @property
     def packed(self):
         """The binary representation of this address."""
         return struct.pack('!I', self.ip)
 
     def _is_hostmask(self, ip_str):
         """Test if the IP string is a hostmask (rather than a netmask).
 
         Args:
             ip_str: A string, the potential hostmask.
 
@@ skipping 137 matching lines @@
               IPv6(IPv6('2001:4860::').ip) == IPv6('2001:4860::')
 
         Raises:
             IPv6IpValidationError: If ipaddr isn't a valid IPv6 address.
             IPv6NetmaskValidationError: If the netmask isn't valid for
               an IPv6 address.
 
         """
         BaseIP.__init__(self)
         self._version = 6
+        self._max_prefixlen = 128
 
         # Efficient constructor from integer.
         if isinstance(ipaddr, long) or isinstance(ipaddr, int):
             self.ip = ipaddr
             self._prefixlen = 128
             self.netmask = self._ALL_ONES
             if ipaddr < 0 or ipaddr > self._ALL_ONES:
                 raise IPv6IpValidationError(ipaddr)
             return
 
@@ skipping 183 matching lines @@
             A boolean, True if the address is reserved per RFC 4193.
 
         """
         return self in IPv6('fc00::/7')
 
     @property
     def version(self):
         return self._version
 
     @property
+    def max_prefixlen(self):
+        return self._max_prefixlen
+
+    @property
     def packed(self):
         """The binary representation of this address."""
         return struct.pack('!QQ', self.ip >> 64, self.ip & (2**64 - 1))
 
     def _is_shorthand_ip(self, ip_str=None):
         """Determine if the address is shortened.
 
         Args:
             ip_str: A string, the IPv6 address.
 
@@ skipping 224 matching lines @@
 
         Returns:
             An integer.
 
         """
         return self.prefixlen
 
     # backwards compatibility
     Subnet = subnet
     Supernet = supernet