Class: IPAdmin::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/tree.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options) ⇒ Tree

  • Arguments:

    • Hash with the following fields:

      - :Version -- IP version - Integer

Example:

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



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/tree.rb', line 39

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

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

        if ( @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)



21
22
23
 
# File 'lib/tree.rb', line 21

def version
  @version
end

Instance Method Details

#add(object) ⇒ Object

Add an IPAdmin::CIDR object to the tree.

  • Arguments:

    • CIDR object

  • Returns:

    • nothing

Example:

tree.add(cidr)



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/tree.rb', line 87

def add(object)

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

    if ( 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:

    • Tree object

Example:

new_tree = tree.collapse()



162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
# File 'lib/tree.rb', line 162

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]
            network = IPAdmin.unpack_ip_addr(:Integer => net_struct.network,
                                             :Version => @version)
            netmask = IPAdmin.unpack_ip_netmask(:Integer => net_struct.netmask,
                                                :Version => @version)
            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()



199
200
201
202
203
204
205
206
207
208
209
210
211
 
# File 'lib/tree.rb', line 199

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:

    • CIDR object

  • Returns:

    • true or false

Example:

added = tree.exists?(cidr)

Returns:

  • (Boolean) 


233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
 
# File 'lib/tree.rb', line 233

def exists?(object)

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

    if ( !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:

    • CIDR object

  • Returns:

    • CIDR object, or nil

Example:

longest_match = tree.find(ip)



283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
 
# File 'lib/tree.rb', line 283

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

    if ( 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 - Integer (optional)
- :Limit -- Maximum entries to return - Integer (optional)
- :Subnet -- Netmask (in bits) of space to find - Integer (optional)

  • Returns:

    • Array of CIDR objects

  • Notes:

    * :Subnet always takes precedence over :IPCount.

Example:

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



330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
 
# File 'lib/tree.rb', line 330

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

    # validate options
    if (!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) )
        subnet_size = IPAdmin.minimum_size(:IPCount =>options[:IPCount],
                                           :Version => @version)
    end
    
    if ( options.has_key?(:Subnet) )
        subnet_size = options[:Subnet]
    end

    # set subnet_size if not already
    if (!subnet_size)
        if (@version == 4)
            subnet_size = 32
        else
            subnet_size = 128
        end
    end
    
    # check that subnet_size is a valid size
    if ( (subnet_size < 1) || (subnet_size > @max_bits) )
            raise "#{subnet_size} is out of range for an " +
                  "IP version #{@version} Tree."
    end

    # search
    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:

    • CIDR object

  • Returns:

    • true or false

Example:

did_prune = tree.prune(ip)



413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
 
# File 'lib/tree.rb', line 413

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

    if (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 CIDR object from the tree.

  • Arguments:

    • CIDR object

  • Returns:

    • true or false

Example:

did_remove = tree.remove(ip)



461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
 
# File 'lib/tree.rb', line 461

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

    if (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()



520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
 
# File 'lib/tree.rb', line 520

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

    list.each do |entry|
        net_struct = entry[:NetStruct]
        depth = entry[:Depth]
        network = IPAdmin.unpack_ip_addr(:Integer => net_struct.network,
                                         :Version => @version)
        netmask = IPAdmin.unpack_ip_netmask(:Integer => net_struct.netmask,
                                            :Version => @version)
        network = IPAdmin.shorten(network) if (@version == 6)

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

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

    return(printed)
end