collapse_address_list is too slow

ipaddr.py

Index: ipaddr.py
===================================================================
--- ipaddr.py	(revision 71)
+++ ipaddr.py	(working copy)
@@ -129,6 +129,65 @@
                      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.
 
@@ -189,8 +248,22 @@
         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
@@ -591,6 +664,7 @@
         """
         BaseIP.__init__(self)
         self._version = 4
+        self._max_prefixlen = 32
 
         # Efficient constructor from integer.
         if isinstance(ipaddr, int) or isinstance(ipaddr, long):
@@ -780,6 +854,10 @@
         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)
@@ -937,6 +1015,7 @@
         """
         BaseIP.__init__(self)
         self._version = 6
+        self._max_prefixlen = 128
 
         # Efficient constructor from integer.
         if isinstance(ipaddr, long) or isinstance(ipaddr, int):
@@ -1140,6 +1219,10 @@
         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))