NAME¶

Net::Patricia - Patricia Trie perl module for fast IP address lookups

SYNOPSIS¶

  use Net::Patricia;
  my $pt = new Net::Patricia;
  $pt->add_string('127.0.0.0/8', \$user_data);
  $pt->match_string('127.0.0.1');
  $pt->match_exact_string('127.0.0.0');
  $pt->match_integer(2130706433); # 127.0.0.1
  $pt->match_exact_integer(2130706432, 8); # 127.0.0.0
  $pt->remove_string('127.0.0.0/8');
  $pt->climb(sub { print "climbing at node $_[0]\n" });
  undef $pt; # automatically destroys the Patricia Trie
  # IPv6 support:
  $pt = new Net::Patricia AF_INET6;
  $pt->add_string('2001:db8::/32');
  $pt->add_string('2001:db8:0:dead::/64');
  $pt->add_string('2001:db8:0:beef::/64');
  $pt->climb(sub { print "climbing at node $_[0]\n" });
  print $pt->match_string('2001:db8:0:dead::1'), "\n";
  # IPv4-mapped IPv6 addresses:
  $pt->add_string('::ffff:0:0/96');
  for my $cidr (qw( 192.0.2.0/24 192.0.2.0/25 192.0.2.128/25 )) {
    my($ip, $len) = split(m|/|, $cidr);
    $pt->add_string("::ffff:$ip/" .
            (96+(defined($len)? $len : 32)), $cidr);
  }
  $pt->climb(sub { print "climbing at node $_[0]\n" });
  print $pt->match_string("::ffff:" . "192.0.2.129"), "\n";

DESCRIPTION¶

This module uses a Patricia Trie data structure to quicklyperform IP address prefix matching for applications such as IP subnet,network or routing table lookups. The data structure is based on aradix tree using a radix of two, so sometimes you see patriciaimplementations called "radix" as well. The term "Trie" is derivedfrom the word "retrieval" but is pronounced like "try". Patriciastands for "Practical Algorithm to Retrieve Information Coded asAlphanumeric", and was first suggested for routing table lookups by VanJacobsen. Patricia Trie performance characteristics are well-known asit has been employed for routing table lookups within the BSD kernelsince the 4.3 Reno release.

The BSD radix code is thoroughly described in "TCP/IP Illustrated,Volume 2" by Wright and Stevens and in the paper ``A Tree-Based PacketRouting Table for Berkeley Unix'' by Keith Sklower.

METHODS¶

new - create a new Net::Patricia object

   $pt = new Net::Patricia;
    

This is the class' constructor - it returns a "Net::Patricia" object upon success or undef on failure. The constructor takes an optional argument (of AF_INET or AF_INET6, defaulting to the former), and creates a tree with address and mask values of that type as keys.

The "Net::Patricia" object will be destroyed automatically when there are no longer any references to it.

add_string

  $pt->add_string(key_string[,user_data]);
    

The first argument, key_string, is a network or subnet specification incanonical form, e.g. "10.0.0.0/8", where the number after the slashrepresents the number of bits in the netmask. If no mask width isspecified, the longest possible mask is assumed, i.e. 32 bits forAF_INET addresses.

The second argument, user_data, is optional. If supplied, it should bea SCALAR value (which may be a perl reference) specifying the user datathat will be stored in the Patricia Trie node. Subsequently, thisvalue will be returned by the match methods described below to indicatea successful search. Remember that perl references and objects arerepresented as SCALAR values and therefore the user data can becomplicated data objects.

If no second argument is passed, the key_string will be stored as theuser data and therfore will likewise be returned by the matchfunctions.

On success, this method returns the user_data passed as the secondargument or key_string if no user data was specified. It returns undefon failure.

match_string

  $pt->match_string(key_string);
    

This method searches the Patricia Trie to find a matching node,according to normal subnetting rules for the address and maskspecified.

The key_string argument is a network or subnet specification incanonical form, e.g. "10.0.0.0/8", where the number after the slashrepresents the number of bits in the netmask. If no mask width valueis specified, the longest mask is assumed, i.e. 32 bits for AF_INETaddresses.

If a matching node is found in the Patricia Trie, this method returnsthe user data for the node. This method returns undef on failure.

match_exact_string

  $pt->match_exact_string(key_string);
    

This method searches the Patricia Trie to find a matching node. Itssemantics are exactly the same as those described for "match_string" except that the key must match a node exactly. I.e. it is not sufficient that the address and mask specified merely falls within the subnet specified by a particular node.

match_integer

  $pt->match_integer(integer[,mask_bits]);
    

This method searches the Patricia Trie to find a matching node,according to normal subnetting rules for the address and maskspecified. Its semantics are similar to those described for"match_string" except that the key is specified using an integer (i.e. SCALAR), such as that returned by perl's "unpack" function for values converted using the "N" (network-ordered long). Note that this argument is not a packed network-ordered long.

Just to be completely clear, the integer argument should be a value ofthe sort produced by this code:

   use Socket;
   $integer = unpack("N", inet_aton("10.0.0.0"));
    

match_exact_integer

  $pt->match_exact_integer(integer[,mask_bits]);
    

This method searches the Patricia Trie to find a matching node. Itssemantics are exactly the same as "match_integer" except that the key must match a node exactly. I.e. it is not sufficient that the address and mask specified merely falls within the subnet specified by a particular node.

remove_string

  $pt->remove_string(key_string);
    

This method removes the node which exactly matches the the address andmask specified from the Patricia Trie.

If the matching node is found in the Patricia Trie, it is removed, andthis method returns the user data for the node. This method returnsundef on failure.

climb

   $pt->climb([CODEREF]);
    

This method climbs the Patricia Trie, visiting each node as it doesso. It performs a non-recursive, "preorder" traversal.

The CODEREF argument is optional. It is a perl code reference used tospecify a user-defined subroutine to be called when visiting eachnode. The node's user data will be passed as the sole argument to thatsubroutine.

This method returns the number of nodes successfully visited whileclimbing the Trie. That is, without a CODEREF argument, it simplycounts the number of nodes in the Patricia Trie.

Note that currently the return value from your CODEREF subroutine isignored. In the future the climb method may return the number of timesyour subroutine returned non-zero, as it is called once per node. So,if you are currently relying on the climb return value to accuratelyreport a count of the number of nodes in the Patricia Trie, it would beprudent to have your subroutine return a non-zero value.

This method is called climb() rather than walk() because climbing trees (and therfore tries) is a more popular pass-time than walking them.

climb_inorder

   $pt->climb_inorder([CODEREF]);
    

This method climbs the Patricia Trie, visiting each node in order as itdoes so. That is, it performs an "inorder" traversal.

The CODEREF argument is optional. It is a perl code reference used tospecify a user-defined subroutine to be called when visiting eachnode. The node's user data will be passed as the sole argument to thatsubroutine.

This method returns the number of nodes successfully visited whileclimbing the Trie. That is, without a CODEREF argument, it simplycounts the number of nodes in the Patricia Trie.

Note that currently the return value from your CODEREF subroutine isignored. In the future the climb method may return the number of timesyour subroutine returned non-zero, as it is called once per node. So,if you are currently relying on the climb return value to accuratelyreport a count of the number of nodes in the Patricia Trie, it would beprudent to have your subroutine return a non-zero value.

This method is called climb() rather than walk() because climbing trees (and therfore tries) is a more popular pass-time than walking them.

BUGS¶

When passing a CODEREF argument to the climb method, the return valuefrom your CODEREF subroutine is currently ignored. In the future theclimb method may return the number of times your subroutine returnednon-zero, as it is called once per node. So, if you are currentlyrelying on the climb return value to accurately report a count of thenumber of nodes in the Patricia Trie, it would be prudent to have yoursubroutine return a non-zero value.

AUTHOR¶

Dave Plonka <plonka@doit.wisc.edu>Philip Prindeville <philipp@redfish-solutions.com>Anton Berezin <tobez@tobez.org>

Copyright (C) 2000-2005 Dave Plonka. Copyright (C) 2009 Dave Plonka& Philip Prindeville. This program is free software; youcan redistribute it and/or modify it under the terms of the GNU GeneralPublic License as published by the Free Software Foundation; eitherversion 2 of the License, or (at your option) any later version.

This product includes software developed by the University of Michigan,Merit Network, Inc., and their contributors. See the copyright file inthe patricialib sub-directory of the distribution for details.

patricialib, the C library used by this perl extension, is an extractedversion of MRT's patricia code from radix.[ch], which was worked on byMasaki Hirabaru and Craig Labovitz. For more info on MRT see:

   http://www.mrtd.net/

The MRT patricia code owes some heritage to GateD's radix code, whichin turn owes something to the BSD kernel.

SEE ALSO¶

perl(1), Socket, Net::Netmask, Text::Trie, Tree::Trie.

Tree::Radix and Net::RoutingTable are modules by Daniel Hagerty<hag@linnaean.org> written entirely in perl, unlike this module. Atthe time of this writing, they are works-in-progress but may beavailable at:

   http://www.linnaean.org/~hag/