1Patricia(3) User Contributed Perl Documentation Patricia(3)
2
6 Net::Patricia - Patricia Trie perl module for fast IP address lookups
7
9 use Net::Patricia;
10 my $pt = new Net::Patricia;
12 $pt->add_string('127.0.0.0/8', \$user_data);
14 $pt->match_string('127.0.0.1');
15 $pt->match_exact_string('127.0.0.0');
16 $pt->match_integer(2130706433); # 127.0.0.1
17 $pt->match_exact_integer(2130706432, 8); # 127.0.0.0
18 $pt->remove_string('127.0.0.0/8');
19 $pt->climb(sub { print "climbing at node $_[0]\n" });
20 undef $pt; # automatically destroys the Patricia Trie
22
24 This module uses a Patricia Trie data structure to quickly perform IP
25 address prefix matching for applications such as IP subnet, network or
26 routing table lookups. The data structure is based on a radix tree
27 using a radix of two, so sometimes you see patricia implementations
28 called "radix" as well. The term "Trie" is derived from the word
29 "retrieval" but is pronounced like "try". Patricia stands for
30 "Practical Algorithm to Retrieve Information Coded as Alphanumeric",
31 and was first suggested for routing table lookups by Van Jacobsen.
32 Patricia Trie performance characteristics are well-known as it has been
33 employed for routing table lookups within the BSD kernel since the 4.3
34 Reno release.
35 The BSD radix code is thoroughly described in "TCP/IP Illustrated,
37 Volume 2" by Wright and Stevens and in the paper ``A Tree-Based Packet
38 Routing Table for Berkeley Unix'' by Keith Sklower.
39
41 new - create a new Net::Patricia object
42 $pt = new Net::Patricia;
43 This is the class' constructor - it returns a "Net::Patricia"
45 object upon success or undef on failure. The constructor takes an
46 optional argument (of AF_INET or AF_INET6, defaulting to the
47 former), and creates a tree with address and mask values of that
48 type as keys.
49 The "Net::Patricia" object will be destroyed automatically when
51 there are no longer any references to it.
52 add_string
54 $pt->add_string(key_string[,user_data]);
55 The first argument, key_string, is a network or subnet
57 specification in canonical form, e.g. "10.0.0.0/8", where the
58 number after the slash represents the number of bits in the
59 netmask. If no mask width is specified, the longest possible mask
60 is assumed, i.e. 32 bits for AF_INET addresses.
61 The second argument, user_data, is optional. If supplied, it
63 should be a SCALAR value (which may be a perl reference) specifying
64 the user data that will be stored in the Patricia Trie node.
65 Subsequently, this value will be returned by the match methods
66 described below to indicate a successful search. Remember that
67 perl references and objects are represented as SCALAR values and
68 therefore the user data can be complicated data objects.
69 If no second argument is passed, the key_string will be stored as
71 the user data and therfore will likewise be returned by the match
72 functions.
73 On success, this method returns the user_data passed as the second
75 argument or key_string if no user data was specified. It returns
76 undef on failure.
77 match_string
79 $pt->match_string(key_string);
80 This method searches the Patricia Trie to find a matching node,
82 according to normal subnetting rules for the address and mask
83 specified.
84 The key_string argument is a network or subnet specification in
86 canonical form, e.g. "10.0.0.0/8", where the number after the slash
87 represents the number of bits in the netmask. If no mask width
88 value is specified, the longest mask is assumed, i.e. 32 bits for
89 AF_INET addresses.
90 If a matching node is found in the Patricia Trie, this method
92 returns the user data for the node. This method returns undef on
93 failure.
94 match_exact_string
96 $pt->match_exact_string(key_string);
97 This method searches the Patricia Trie to find a matching node.
99 Its semantics are exactly the same as those described for
100 "match_string" except that the key must match a node exactly. I.e.
101 it is not sufficient that the address and mask specified merely
102 falls within the subnet specified by a particular node.
103 match_integer
105 $pt->match_integer(integer[,mask_bits]);
106 This method searches the Patricia Trie to find a matching node,
108 according to normal subnetting rules for the address and mask
109 specified. Its semantics are similar to those described for
110 "match_string" except that the key is specified using an integer
111 (i.e. SCALAR), such as that returned by perl's "unpack" function
112 for values converted using the "N" (network-ordered long). Note
113 that this argument is not a packed network-ordered long.
114 Just to be completely clear, the integer argument should be a value
116 of the sort produced by this code:
117 use Socket;
119 $integer = unpack("N", inet_aton("10.0.0.0"));
120 match_exact_integer
122 $pt->match_exact_integer(integer[,mask_bits]);
123 This method searches the Patricia Trie to find a matching node.
125 Its semantics are exactly the same as "match_integer" except that
126 the key must match a node exactly. I.e. it is not sufficient that
127 the address and mask specified merely falls within the subnet
128 specified by a particular node.
129 remove_string
131 $pt->remove_string(key_string);
132 This method removes the node which exactly matches the the address
134 and mask specified from the Patricia Trie.
135 If the matching node is found in the Patricia Trie, it is removed,
137 and this method returns the user data for the node. This method
138 returns undef on failure.
139 climb
141 $pt->climb([CODEREF]);
142 This method climbs the Patricia Trie, visiting each node as it does
144 so. It performs a non-recursive, "preorder" traversal.
145 The CODEREF argument is optional. It is a perl code reference used
147 to specify a user-defined subroutine to be called when visiting
148 each node. The node's user data will be passed as the sole
149 argument to that subroutine.
150 This method returns the number of nodes successfully visited while
152 climbing the Trie. That is, without a CODEREF argument, it simply
153 counts the number of nodes in the Patricia Trie.
154 Note that currently the return value from your CODEREF subroutine
156 is ignored. In the future the climb method may return the number
157 of times your subroutine returned non-zero, as it is called once
158 per node. So, if you are currently relying on the climb return
159 value to accurately report a count of the number of nodes in the
160 Patricia Trie, it would be prudent to have your subroutine return a
161 non-zero value.
162 This method is called climb() rather than walk() because climbing
164 trees (and therfore tries) is a more popular pass-time than walking
165 them.
166 climb_inorder
168 $pt->climb_inorder([CODEREF]);
169 This method climbs the Patricia Trie, visiting each node in order
171 as it does so. That is, it performs an "inorder" traversal.
172 The CODEREF argument is optional. It is a perl code reference used
174 to specify a user-defined subroutine to be called when visiting
175 each node. The node's user data will be passed as the sole
176 argument to that subroutine.
177 This method returns the number of nodes successfully visited while
179 climbing the Trie. That is, without a CODEREF argument, it simply
180 counts the number of nodes in the Patricia Trie.
181 Note that currently the return value from your CODEREF subroutine
183 is ignored. In the future the climb method may return the number
184 of times your subroutine returned non-zero, as it is called once
185 per node. So, if you are currently relying on the climb return
186 value to accurately report a count of the number of nodes in the
187 Patricia Trie, it would be prudent to have your subroutine return a
188 non-zero value.
189 This method is called climb() rather than walk() because climbing
191 trees (and therfore tries) is a more popular pass-time than walking
192 them.
193
195 This modules does not yet support AF_INET6 (IP version 6) 128 bit
196 addresses, although the underlying patricialib C code does.
197 When passing a CODEREF argument to the climb method, the return value
199 from your CODEREF subroutine is currently ignored. In the future the
200 climb method may return the number of times your subroutine returned
201 non-zero, as it is called once per node. So, if you are currently
202 relying on the climb return value to accurately report a count of the
203 number of nodes in the Patricia Trie, it would be prudent to have your
204 subroutine return a non-zero value.
205
207 Dave Plonka <plonka@doit.wisc.edu> Philip Prindeville
208 <philipp@redfish-solutions.com>
209 Copyright (C) 2000-2005 Dave Plonka. Copyright (C) 2009 Dave Plonka
211 & Philip Prindeville. This program is free software; you can
212 redistribute it and/or modify it under the terms of the GNU General
213 Public License as published by the Free Software Foundation; either
214 version 2 of the License, or (at your option) any later version.
215 This product includes software developed by the University of Michigan,
217 Merit Network, Inc., and their contributors. See the copyright file in
218 the patricialib sub-directory of the distribution for details.
219 patricialib, the C library used by this perl extension, is an extracted
221 version of MRT's patricia code from radix.[ch], which was worked on by
222 Masaki Hirabaru and Craig Labovitz. For more info on MRT see:
223 http://www.mrtd.net/
225 The MRT patricia code owes some heritage to GateD's radix code, which
227 in turn owes something to the BSD kernel.
228
230 perl(1), Socket, Net::Netmask, Text::Trie, Tree::Trie.
231 Tree::Radix and Net::RoutingTable are modules by Daniel Hagerty
233 <hag@linnaean.org> written entirely in perl, unlike this module. At
234 the time of this writing, they are works-in-progress but may be
235 available at:
236 http://www.linnaean.org/~hag/
238perl v5.12.2 2010-11-14 Patricia(3)