Class: IPAdmin::Tree

Inherits:

Object

• Object
• IPAdmin::Tree

Defined in:

lib/ip_admin.rb

Overview

A class & series of methods for creating and manipulating IP-based

heirarchical trees. Both IPv4 and IPv6 are supported.

Tree's are useful for creating mini 'routing tables' of CIDR address space.
Using a tree, you can quickly determine the 'route' of another CIDR via
the standard longest-match algorithm.

Tree's are not dynamic, in that if you modify any of the CIDR objects
contained within, the Tree will not automatically adjust itself accordingly.
For example if you have a tree like the following:

   192.168.0.0/24
       192.168.0.0/26
   192.168.1.0/24

You decide to resize 192.168.0.0/24 to 192.168.0.0/23. The tree will now
be incorrect:

   192.168.0.0/23
       192.168.0.0/26
   192.168.1.0/24

You would need to remove and re-add the CIDR 192.168.0.0/23 in order for the
tree to rebuild itself properly.

Instance Attribute Summary

• #version ⇒ Object readonly

  IP version for this tree (4 or 6).

Instance Method Summary

• #add(object) ⇒ Object

  Add an IPAdmin::CIDR object to the tree.

• #collapse ⇒ Object

  Collapse (supernet) all subnets of the tree, and return a new tree.

• #dump ⇒ Object

  Dump the contents of this tree.

• #exists?(object) ⇒ Boolean

  Has an IPAdmin::CIDR object already been added to the tree?.

• #find(object) ⇒ Object

  Find the longest matching branch of our tree to which an IPAdmin::CIDR object belongs.

• #find_space(options) ⇒ Object

  Find Tree entries that can hold a subnet of size X.

• #initialize(options) ⇒ Tree constructor

  • Arguments: * Hash with the following fields: - :Version – IP version for this tree (4 or 6).

• #prune(object) ⇒ Object

  Remove an IPAdmin::CIDR object, and all child objects from the tree.

• #remove(object) ⇒ Object

  Remove a single IPAdmin::CIDR object from the tree.

• #show ⇒ Object

  Print the tree in a nicely formatted string.

Constructor Details

#initialize(options) ⇒ Tree

• Arguments:

  • Hash with the following fields:

    - :Version -- IP version for this tree (4 or 6)
    

Example:

table = IPAdmin::CIDRTable.new(:Version => 4)

# File 'lib/ip_admin.rb', line 2953

def initialize(options)
    unless (options.kind_of? Hash)
        raise ArgumentError, "Expected Hash, but #{options.class} provided."
    end

    if ( options.has_key?(:Version) )
        @version =  options[:Version]

        unless ( @version == 4 || @version == 6 )
            raise "IP version should be either 4 or 6."
        end
    else
        raise ArgumentError, "Missing argument: Version."
    end

    if (@version == 4)
        @max_bits = 32
        @all_f = 2**@max_bits - 1
    else
        @max_bits = 128
        @all_f = 2**@max_bits - 1
    end

    # root of our ordered IP tree
    @root = []

end

Instance Attribute Details

#version ⇒ Object (readonly)

IP version for this tree (4 or 6)

# File 'lib/ip_admin.rb', line 2935

def version
  @version
end

Instance Method Details

#add(object) ⇒ Object

Add an IPAdmin::CIDR object to the tree.

• Arguments:

  • IPAdmin::CIDR object

• Returns:

  • nothing

Example:

tree.add(cidr)

# File 'lib/ip_admin.rb', line 3001

def add(object)

    # validate object
    unless ( object.kind_of?(IPAdmin::CIDR) )
        raise ArgumentError, "IPAdmin::CIDR object " +
                             "required but #{object.class} provided."
    end

    unless (object.version == @version )
        raise "IP version #{object.version} is incompatible with " +
              "Tree IP version #{@version}."
    end

    net_struct = IPAdmin.create_net_struct(object)

    # search tree for it's home branch
    search_results = find_home(net_struct, @root)
    home_struct = search_results[0] if (search_results)
    home_branch = home_struct.subnets if (search_results)
    home_branch = @root if (!home_branch)

    # make sure we dont have a duplicate
    if (home_struct)
        if ( (net_struct.network == home_struct.network) && 
             (net_struct.netmask == home_struct.netmask) )
            raise "Attempted to add #{object.desc()} multiple times."
        end
    end

    # now that we have our branch location, check that other entries
    # of this branch are not subnets of our new object. if they are
    # then make them a branch of our new object
    home_branch.each do |entry|
        is_contained = contains(net_struct, entry)

        if (is_contained)
            net_struct.subnets.push(entry)
        end
    end

    net_struct.subnets.each do |entry|
        home_branch.delete(entry)
    end

    # add new object as an ordered entry to home_branch
    add_to_branch(net_struct,home_branch)

    return(nil)
end

#collapse ⇒ Object

Collapse (supernet) all subnets of the tree, and return a new tree. The supernetting of subnets will only occur in situations where the newly created supernet will not result in the ‘creation’ of additional space. For example the following blocks (192.168.0.0/24, 192.168.1.0/24, and 192.168.2.0/24) would merge into 192.168.0.0/23 and 192.168.2.0/24 rather than into 192.168.0.0/22.

• Arguments:

  • none

• Returns:

  • IPAdmin::Tree object

Example:

new_tree = tree.collapse()

# File 'lib/ip_admin.rb', line 3117

def collapse()
        tree = IPAdmin::Tree.new(:Version => @version)
        branch = IPAdmin.merge(:List => @root, :NetStruct => 1)
        dumped = dump_branch(branch)
        dumped.each do |entry|
            net_struct = entry[:NetStruct]

            if (@version == 4)
                network = IPAdmin.unpack_ipv4_addr(net_struct.network)
                netmask = IPAdmin.unpack_ipv4_netmask(net_struct.netmask)
            else
                network = IPAdmin.unpack_ipv6_addr(net_struct.network)
                netmask = IPAdmin.unpack_ipv6_netmask(net_struct.netmask)
            end
            cidr = IPAdmin::CIDR.new(:CIDR => "#{network}/#{netmask}")
            tree.add(cidr)
        end
    return(tree)
end

#dump ⇒ Object

Dump the contents of this tree.

• Arguments:

  • none

• Returns:

  • ordered array of hashes with the following fields:

    - :Object => CIDR object
    - :Depth => (depth level in tree)
    

Example:

dumped = tree.dump()

# File 'lib/ip_admin.rb', line 3210

def dump()
    list = []
    dumped = dump_branch(@root)

    dumped.each do |entry|
        depth = entry[:Depth]
        net_struct = entry[:NetStruct]
        object = net_struct.object
        list.push({:Depth => depth, :Object => object})
    end

    return(list)
end

#exists?(object) ⇒ Boolean

Has an IPAdmin::CIDR object already been added to the tree?

• Arguments:

  • IPAdmin::CIDR object

• Returns:

  • true or false

Example:

added = tree.exists?(cidr)

Returns:

• (Boolean)

# File 'lib/ip_admin.rb', line 3281

def exists?(object)

    # validate object
    unless ( object.kind_of?(IPAdmin::CIDR) )
        raise ArgumentError, "IPAdmin::CIDR object " +
                             "required but #{object.class} provided."
    end

    unless (object.version == @version )
        raise "IP version #{object.version} is incompatible with " +
              "Tree IP version #{@version}."
    end

    net_struct = IPAdmin.create_net_struct(object)
    home_struct,home_branch = find_home(net_struct, @root)

    # check for match
    found = false
    if (home_struct)  
        if ( (net_struct.network == home_struct.network) && 
             (net_struct.netmask == home_struct.netmask) )
            found = true
        end
    end


    return(found)
end

#find(object) ⇒ Object

Find the longest matching branch of our tree to which an IPAdmin::CIDR object belongs. Useful for performing ‘routing table’ lookups.

• Arguments:

  • IPAdmin::CIDR object

• Returns:

  • IPAdmin::CIDR object, or nil if not found

Example:

longest_match = tree.find(ip)

# File 'lib/ip_admin.rb', line 3331

def find(object)
    unless ( object.kind_of?(IPAdmin::CIDR) )
        raise ArgumentError, "IPAdmin::CIDR object " +
                             "required but #{object.class} provided."
    end

    unless (object.version == @version )
        raise "IP version #{object.version} is incompatible with " +
              "Tree IP version #{@version}."
    end

    net_struct = IPAdmin.create_net_struct(object)
    home_struct,home_branch = find_home(net_struct, @root)
    found_obj = home_struct.object if (home_struct)

    return(found_obj)
end

#find_space(options) ⇒ Object

Find Tree entries that can hold a subnet of size X. Returns only the smallest matching subnets of each supernet. If neither IPCount or Subnet or provided, then method returns all entries that can fit a single IP.

• Arguments:

  • Hash with the following fields:

    - :IPCount -- Minimum number of IP's that should fit within subnet (optional)
    - :Limit -- Maximum entries to return (optional)
    - :Subnet -- Netmask (in bits) of space to find(optional)
    

• Returns:

  • ordered array of IPAdmin::CIDR objects

Note:

:Subnet always takes precedence over :IPCount.

Example:

list = tree.find_space(:Subnet => 27)
list = tree.find_space(:IPCount => 33, :Limit => 2)

# File 'lib/ip_admin.rb', line 3426

def find_space(options)
    limit = nil
    list = []

    # validate options
    unless (options.kind_of? Hash)
        raise ArgumentError, "Expected Hash, but #{options.class} provided."
    end

    if ( options.has_key?(:Limit) )
        limit = options[:Limit]
    end
    
    if ( options.has_key?(:IPCount) )
        num_ips = options[:IPCount]
        bits_needed = 0
        until (2**bits_needed >= num_ips)
            bits_needed += 1
        end
        subnet_size = @max_bits - bits_needed
    end
    
    if ( options.has_key?(:Subnet) )
        subnet_size = options[:Subnet]
    end

    # check that subnet_size is a valid size
    if (@version == 4)
        subnet_size = 32 if (!subnet_size)
        unless ( (subnet_size > 0) && (subnet_size < 33) )
            raise "#{subnet_size} is out of range for an " +
                  "IP version #{@version} Tree."
        end

    else
        subnet_size = 128 if (!subnet_size)
        unless ( (subnet_size > 0) && (subnet_size < 129) )
            raise "#{subnet_size} is out of range for an " +
                  "IP version #{@version} Tree."
        end
    end

    search_list = dump_branch(@root)

    search_list.each do |entry|
        depth = entry[:Depth]
        net_struct = entry[:NetStruct]

        # we only want leaf nodes of type IPAdmin::CIDR
        if ( (net_struct.subnets.length == 0) &&
             (net_struct.object.kind_of?(IPAdmin::CIDR)) )

             if (subnet_size >= net_struct.object.bits)
                list.push(net_struct.object)
             end
        end

        if (limit && (list.length >= limit) )
            break
        end

    end

    return(list)

end

#prune(object) ⇒ Object

Remove an IPAdmin::CIDR object, and all child objects from the tree.

• Arguments:

  • IPAdmin::CIDR object

• Returns:

  • true on success, or false

Example:

did_prune = tree.prune(ip)

# File 'lib/ip_admin.rb', line 3514

def prune(object)
    unless ( object.kind_of?(IPAdmin::CIDR) )
        raise ArgumentError, "IPAdmin::CIDR object " +
                             "required but #{object.class} provided."
    end

    unless (object.version == @version )
        raise "IP version #{object.version} is incompatible with " +
              "Tree IP version #{@version}."
    end

    net_struct = IPAdmin.create_net_struct(object)
    home_struct,home_branch = find_home(net_struct, @root)

    if(!home_struct)
        raise "#{object.desc} could not be found."
    end
    
    # remove if home_struct.object = object
    pruned = false
    if (home_struct.object = object)
        home_branch.delete(home_struct)
        pruned = true
    end

    return(pruned)
end

#remove(object) ⇒ Object

Remove a single IPAdmin::CIDR object from the tree.

• Arguments:

  • IPAdmin::CIDR object

• Returns:

  • true on success, or false

Example:

did_remove = tree.remove(ip)

# File 'lib/ip_admin.rb', line 3562

def remove(object)
    unless ( object.kind_of?(IPAdmin::CIDR) )
        raise ArgumentError, "IPAdmin::CIDR object " +
                             "required but #{object.class} provided."
    end

    unless (object.version == @version )
        raise "IP version #{object.version} is incompatible with " +
              "Tree IP version #{@version}."
    end

    net_struct = IPAdmin.create_net_struct(object)
    home_struct,home_branch = find_home(net_struct, @root)

    # remove if home_struct.object = object
    removed = false
    if (home_struct.object = object)

        # if we have children subnets, move them up one level
        if (home_struct.subnets.length > 0)
            home_struct.subnets.each do |entry|
                index = 0
                home_branch.each do
                    if(entry.network < (home_branch[index]).network)
                        break
                    end
                    index += 1
                end
                home_branch.insert(index, entry)
            end
        end

        home_branch.delete(home_struct)
        removed = true
    end

    return(removed)
end

#show ⇒ Object

Print the tree in a nicely formatted string.

• Arguments:

  • none

• Returns:

  • String representing the contents of the tree

Example:

puts tree.show()

# File 'lib/ip_admin.rb', line 3621

def show()
    printed = ""
    list = dump_branch(@root)

    list.each do |entry|
        net_struct = entry[:NetStruct]
        depth = entry[:Depth]

        if (@version == 4)
            network = IPAdmin.unpack_ipv4_addr(net_struct.network)
            netmask = IPAdmin.unpack_ipv4_netmask(net_struct.netmask)

        else
            network = IPAdmin.unpack_ipv6_addr(net_struct.network)
            netmask = IPAdmin.unpack_ipv6_netmask(net_struct.netmask)
            network = IPAdmin.shorten(network)
        end

        if (depth == 0)
            indent = ""
        else
            indent = " " * (depth*3)
        end

        printed << "#{indent}#{network}/#{netmask}\n"
    end

    return(printed)
end