Author image Karl Gaissmaier
and 1 contributors

NAME

Net::IPAM::Tree - A CIDR/Block tree library for fast IP lookup with longest-prefix-match.

DESCRIPTION

A module for fast IP-routing-table lookups and IP-ACLs (Access Control Lists).

It is NOT a standard patricia-trie implementation. This isn't possible for general blocks not represented by bitmasks. Every tree item is a Net::IPAM::Block or a subclass of it.

SYNOPSIS

  use Net::IPAM::Tree;

  my ($t, $dups) = Net::IPAM::Tree->new(@blocks);
  if (@$dups) {
    warn("items are duplicate: " . join("\n", @$dups));
  }

  my $block = $t->lookup($ip_or_block)
    && printf( "longest-prefix-match in tree for %s is %s\n", $ip_or_block, $block );

  my $superset = $t->superset($ip_or_block)
    && printf( "superset in tree for ip or block %s is %s\n", $ip_or_block, $superset );

  say $t->to_string;

  ▼
  ├─ ::/8
  ├─ 100::/8
  ├─ 2000::/3
  │  ├─ 2000::/4
  │  └─ 3000::/4
  ├─ 4000::/3
  ...

METHODS

new(@blocks)

Create Net::IPAM::Tree object.

  my ($t, $dups) = Net::IPAM::Tree->new(@blocks);

In scalar context just returns the tree object, duplicate items produce a warning.

In list context returns the tree object and the arrayref of duplicate items, if any.

superset($thing)

Returns the outermost block if the given $thing (Net::IPAM::IP or Net::IPAM::Block) is contained in the tree or undef.

lookup($thing)

Returns Net::IPAM::Block with longest prefix match for $thing (Net::IPAM::IP or Net::IPAM::Block) in the tree, undef if not found.

This can be used for ACL or fast routing table lookups.

  # make blocks
  my @priv = map { Net::IPAM::Block->new($_) } qw(10.0.0.0/8 172.16.0.0/12 192.168.0.0 fc00::/7);

  # make tree
  my $priv = Net::IPAM::Tree->new(@priv);

  my $b = Net::IPAM::Block->new('fdcd:aa59:8bce::/48') or die;

  my $lpm = $priv->lookup($b)
    && say "longest-prefix-match for $b is $lpm";

to_string

Returns the tree as ordered graph or undef on empty trees.

  $t->to_string($callback);

The optional callback is called on every block. Returns the decorated string for block.

  $t->to_string( sub { my $block = shift; return decorate($block) } );

example (without callback):

  ▼
  ├─ ::/8
  ├─ 100::/8
  ├─ 2000::/3
  │  ├─ 2000::/4
  │  └─ 3000::/4
  ├─ 6000::/3

possible example (with callback):

  ▼
  ├─ ::/8.................   "Reserved by IETF     [RFC3513][RFC4291]"
  ├─ 100::/8..............   "Reserved by IETF     [RFC3513][RFC4291]"
  ├─ 2000::/3.............   "Global Unicast       [RFC3513][RFC4291]"
  │  ├─ 2000::/4.............  "Test"
  │  └─ 3000::/4.............  "FREE"
  ├─ 6000::/3.............   "Reserved by IETF     [RFC3513][RFC4291]"

walk($walk_func)

Walks the ordered tree, see to_string().

  my $err_string = $t->walk($walk_func);

For every item the walk_func function is called with the following hash-ref:

    my $err = $walk_func->(
      {
        depth  => $i,           # starts at 0
        item   => $item,        # current block
        parent => $parent,      # parent block, undef for root items
        childs => [@childs],    # child blocks, empty for leaf items
      }
    );

The current depth is counting from 0.

On error, the walk is stopped and the error is returned to the caller. The walk_func MUST return undef if there is no error!

len

Returns the number of blocks in the tree.

AUTHOR

Karl Gaissmaier, <karl.gaissmaier(at)uni-ulm.de>

SUPPORT

You can find documentation for this module with the perldoc command.

    perldoc Net::IPAM::Tree

You can also look for information at:

  • on github

    TODO

SEE ALSO

Net::IPAM::IP Net::IPAM::Block

LICENSE AND COPYRIGHT

This software is copyright (c) 2020-2022 by Karl Gaissmaier.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.