#NEWLINE# def range_usage( ip_start , ip_end , ip_type , get_objects = False ) : #NEWLINE# #INDENT# "\n    :param ip_start: Start ip\n    :type ip_start: str\n    :param ip_end: End ip\n    :type ip_end: str\n    :param ip_type: ip type\n    :type ip_end: str ('4' or '6')\n\n    Returns ip usage statistics about the range starting at ip_start and\n    ending at ip_end.\n\n    Given an inclusive contiguous range of positive integers (IP addresses)\n    between `a` and `b` and a list of lists where each sublist contains\n    integers (IP addresses) that are within the range, how many integers\n    between `a` and `b` do not exist in any of the lists; this is what this\n    function calculates.\n\n    For example:\n\n    ```\n    Start = 0\n    End = 9\n    Lists = [[1,2,3], [2,3,4]]\n    ```\n\n    The integers that do not occur in `Lists` are `0`, `5`, `6`, `7`, `8`, and\n    `9`, so there are 6 integers that do not exist in Lists that satisfy `Start\n    <= n <= End`.\n\n    Start can be small and End can be very large (the range may be\n    larger than you would want to itterate over). Due to the size of IPv6\n    ranges, we should not use recursion.\n\n    There are three types of objects (that we care about) that have IP's\n    associated with them: AddressRecord, PTR, StaticInterface. Because we get\n    objects back as Queryset's that are hard to merge, we have to do this\n    algorithm while retaining all three lists. The gist of the algoritm is as\n    follows::\n\n        # Assume the lists are sorted\n        while lists:\n            note the start number (ip)\n            lowest =: of the things in list (PTR, A, INTR), find the lowest\n            difference =: start - lowest.ip\n            total_free +=: difference\n            start =: lowest.ip + 1\n\n            if any PTR, A, or INTR has the same IP as lowest:\n                remove those items from their lists\n    " #NEWLINE# ( istart , iend , ipf_q ) = start_end_filter ( ip_start , ip_end , ip_type ) #NEWLINE# def get_ip( rec ) : #NEWLINE# #INDENT# return two_to_one ( rec . ip_upper , rec . ip_lower ) #NEWLINE# #UNINDENT# lists = [ sorted ( AddressRecord . objects . filter ( ipf_q ) , key = get_ip ) , sorted ( PTR . objects . filter ( ipf_q ) , key = get_ip ) , sorted ( StaticInterface . objects . filter ( ipf_q ) , key = get_ip ) ] #NEWLINE# free_ranges = [ ] #NEWLINE# def cmp_ip_upper_lower( a , b ) : #NEWLINE# #INDENT# if ( a . ip_upper > b . ip_upper ) : #NEWLINE# #INDENT# return a #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( a . ip_upper < b . ip_upper ) : #NEWLINE# #INDENT# return b #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( a . ip_lower > b . ip_lower ) : #NEWLINE# #INDENT# return a #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( a . ip_lower < b . ip_lower ) : #NEWLINE# #INDENT# return b #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# return a #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# unused = 0 #NEWLINE# minimum_i = 0 #NEWLINE# rel_start = int ( istart ) #NEWLINE# end = int ( iend ) #NEWLINE# while True : #NEWLINE# #INDENT# if ( rel_start > end ) : #NEWLINE# #INDENT# break #NEWLINE# #UNINDENT# lists = [ l for l in lists if l ] #NEWLINE# if ( not lists ) : #NEWLINE# #INDENT# free_ranges . append ( ( rel_start , end ) ) #NEWLINE# unused += ( ( end - rel_start ) + 1 ) #NEWLINE# break #NEWLINE# #UNINDENT# min_list = min ( lists , key = ( lambda x : two_to_one ( x [ 0 ] . ip_upper , x [ 0 ] . ip_lower ) ) ) #NEWLINE# minimum = min_list [ 0 ] #NEWLINE# minimum_i = two_to_one ( minimum . ip_upper , minimum . ip_lower ) #NEWLINE# unused += ( minimum_i - rel_start ) #NEWLINE# if ( minimum_i != rel_start ) : #NEWLINE# #INDENT# free_ranges . append ( ( rel_start , ( minimum_i - 1 ) ) ) #NEWLINE# #UNINDENT# if get_objects : #NEWLINE# #INDENT# objects = [ 'objects' ] #NEWLINE# #UNINDENT# for l in lists : #NEWLINE# #INDENT# while ( l and ( l [ 0 ] . ip_upper == minimum . ip_upper ) and ( l [ 0 ] . ip_lower == minimum . ip_lower ) ) : #NEWLINE# #INDENT# if get_objects : #NEWLINE# #INDENT# objects . append ( l . pop ( 0 ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# l . pop ( 0 ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# if get_objects : #NEWLINE# #INDENT# free_ranges . append ( objects ) #NEWLINE# #UNINDENT# rel_start = ( minimum_i + 1 ) #NEWLINE# #UNINDENT# range_usage = { #NEWLINE# #INDENT# 'unused' : unused , #NEWLINE# 'used' : ( ( ( int ( iend ) - int ( istart ) ) - unused ) + 1 ) , #NEWLINE# 'free_ranges' : free_ranges , #NEWLINE# #UNINDENT# } #NEWLINE# return range_usage