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 "Practi‐
30 cal Algorithm to Retrieve Information Coded as Alphanumeric", and was
31 first suggested for routing table lookups by Van Jacobsen. Patricia
32 Trie performance characteristics are well-known as it has been employed
33 for routing table lookups within the BSD kernel since the 4.3 Reno
34 release.
35 The BSD radix code is thoroughly described in "TCP/IP Illustrated, Vol‐
37 ume 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. For now, the constructor
46 takes no arguments, and defaults to creating a tree which uses
47 AF_INET IPv4 address and mask values as keys. In the future it
48 will probably take one argument such as AF_INET or AF_INET6 to
49 specify whether or not you are use 32-bit IP addresses as keys or
50 128-bit IPv6 addresses.
51 The "Net::Patricia" object will be destroyed automatically when
53 there are no longer any references to it.
54 add_string
56 $pt->add_string(key_string[,user_data]);
57 The first argument, key_string, is a network or subnet specifica‐
59 tion in canonical form, e.g. "10.0.0.0/8", where the number after
60 the slash represents the number of bits in the netmask. If no mask
61 width is specified, the longest possible mask is assumed, i.e. 32
62 bits for AF_INET addresses.
63 The second argument, user_data, is optional. If supplied, it
65 should be a SCALAR value (which may be a perl reference) specifying
66 the user data that will be stored in the Patricia Trie node. Sub‐
67 sequently, this value will be returned by the match methods
68 described below to indicate a successful search. Remember that
69 perl references and objects are represented as SCALAR values and
70 therefore the user data can be complicated data objects.
71 If no second argument is passed, the key_string will be stored as
73 the user data and therfore will likewise be returned by the match
74 functions.
75 On success, this method returns the user_data passed as the second
77 argument or key_string if no user data was specified. It returns
78 undef on failure.
79 match_string
81 $pt->match_string(key_string);
82 This method searches the Patricia Trie to find a matching node,
84 according to normal subnetting rules for the address and mask spec‐
85 ified.
86 The key_string argument is a network or subnet specification in
88 canonical form, e.g. "10.0.0.0/8", where the number after the slash
89 represents the number of bits in the netmask. If no mask width
90 value is specified, the longest mask is assumed, i.e. 32 bits for
91 AF_INET addresses.
92 If a matching node is found in the Patricia Trie, this method
94 returns the user data for the node. This method returns undef on
95 failure.
96 match_exact_string
98 $pt->match_exact_string(key_string);
99 This method searches the Patricia Trie to find a matching node.
101 Its semantics are exactly the same as those described for
102 "match_string" except that the key must match a node exactly. I.e.
103 it is not sufficient that the address and mask specified merely
104 falls within the subnet specified by a particular node.
105 match_integer
107 $pt->match_integer(integer[,mask_bits]);
108 This method searches the Patricia Trie to find a matching node,
110 according to normal subnetting rules for the address and mask spec‐
111 ified. Its semantics are similar to those described for
112 "match_string" except that the key is specified using an integer
113 (i.e. SCALAR), such as that returned by perl's "unpack" function
114 for values converted using the "N" (network-ordered long). Note
115 that this argument is not a packed network-ordered long.
116 Just to be completely clear, the integer argument should be a value
118 of the sort produced by this code:
119 use Socket;
121 $integer = unpack("N", inet_aton("10.0.0.0"));
122 match_exact_integer
124 $pt->match_exact_integer(integer[,mask_bits]);
125 This method searches the Patricia Trie to find a matching node.
127 Its semantics are exactly the same as "match_integer" except that
128 the key must match a node exactly. I.e. it is not sufficient that
129 the address and mask specified merely falls within the subnet spec‐
130 ified by a particular node.
131 remove_string
133 $pt->remove_string(key_string);
134 This method removes the node which exactly matches the the address
136 and mask specified from the Patricia Trie.
137 If the matching node is found in the Patricia Trie, it is removed,
139 and this method returns the user data for the node. This method
140 returns undef on failure.
141 climb
143 $pt->climb([CODEREF]);
144 This method climbs the Patricia Trie, visiting each node as it does
146 so. It performs a non-recursive, "preorder" traversal.
147 The CODEREF argument is optional. It is a perl code reference used
149 to specify a user-defined subroutine to be called when visiting
150 each node. The node's user data will be passed as the sole argu‐
151 ment to that subroutine.
152 This method returns the number of nodes successfully visited while
154 climbing the Trie. That is, without a CODEREF argument, it simply
155 counts the number of nodes in the Patricia Trie.
156 Note that currently the return value from your CODEREF subroutine
158 is ignored. In the future the climb method may return the number
159 of times your subroutine returned non-zero, as it is called once
160 per node. So, if you are currently relying on the climb return
161 value to accurately report a count of the number of nodes in the
162 Patricia Trie, it would be prudent to have your subroutine return a
163 non-zero value.
164 This method is called climb() rather than walk() because climbing
166 trees (and therfore tries) is a more popular pass-time than walking
167 them.
168 climb_inorder
170 $pt->climb_inorder([CODEREF]);
171 This method climbs the Patricia Trie, visiting each node in order
173 as it does so. That is, it performs an "inorder" traversal.
174 The CODEREF argument is optional. It is a perl code reference used
176 to specify a user-defined subroutine to be called when visiting
177 each node. The node's user data will be passed as the sole argu‐
178 ment to that subroutine.
179 This method returns the number of nodes successfully visited while
181 climbing the Trie. That is, without a CODEREF argument, it simply
182 counts the number of nodes in the Patricia Trie.
183 Note that currently the return value from your CODEREF subroutine
185 is ignored. In the future the climb method may return the number
186 of times your subroutine returned non-zero, as it is called once
187 per node. So, if you are currently relying on the climb return
188 value to accurately report a count of the number of nodes in the
189 Patricia Trie, it would be prudent to have your subroutine return a
190 non-zero value.
191 This method is called climb() rather than walk() because climbing
193 trees (and therfore tries) is a more popular pass-time than walking
194 them.
195
197 The match_string method ignores the mask bits/width, if specified, in
198 its argument. So, if you add two prefixes with the same base address
199 but different mask widths, this module will match the most-specific
200 prefix even if that prefix doesn't wholly cotain the prefix specified
201 by the match argument. For example:
202 use Net::Patricia;
204 my $pt = new Net::Patricia;
205 $pt->add_string('192.168.0.0/25');
206 $pt->add_string('192.168.0.0/16');
207 print $pt->match_string('192.168.0.0/24'), "\n";
208 prints "192.168.0.0/25", just as if you had called:
210 print $pt->match_string('192.168.0.0'), "\n";
212 This issue was reported to me by John Payne, who also provided a candi‐
214 date patch, but I have not applied it since I hesitate to change this
215 behavior which was inherited from MRT. Consequently, this module might
216 seem to violate the principle of least surprise if you specific the
217 mask bits when trying to find the best match.
218 Methods to add or remove nodes using integer arguments are yet to be
220 implemented. This was a lower priority since it is less necessary to
221 avoid the overhead involved in translation from a string representation
222 since add and remove operations are usually performed less frequently
223 than matching operations.
224 This modules does not yet support AF_INET6 (IP version 6) 128 bit
226 addresses, although the underlying patricialib C code does.
227 When passing a CODEREF argument to the climb method, the return value
229 from your CODEREF subroutine is currently ignored. In the future the
230 climb method may return the number of times your subroutine returned
231 non-zero, as it is called once per node. So, if you are currently
232 relying on the climb return value to accurately report a count of the
233 number of nodes in the Patricia Trie, it would be prudent to have your
234 subroutine return a non-zero value.
235
237 Dave Plonka <plonka@doit.wisc.edu>
238 Copyright (C) 2000-2005 Dave Plonka. This program is free software;
240 you can redistribute it and/or modify it under the terms of the GNU
241 General Public License as published by the Free Software Foundation;
242 either version 2 of the License, or (at your option) any later version.
243 This product includes software developed by the University of Michigan,
245 Merit Network, Inc., and their contributors. See the copyright file in
246 the patricialib sub-directory of the distribution for details.
247 patricialib, the C library used by this perl extension, is an extracted
249 version of MRT's patricia code from radix.[ch], which was worked on by
250 Masaki Hirabaru and Craig Labovitz. For more info on MRT see:
251 http://www.mrtd.net/
253 The MRT patricia code owes some heritage to GateD's radix code, which
255 in turn owes something to the BSD kernel.
256
258 perl(1), Socket, Net::Netmask, Text::Trie, Tree::Trie.
259 Tree::Radix and Net::RoutingTable are modules by Daniel Hagerty
261 <hag@linnaean.org> written entirely in perl, unlike this module. At
262 the time of this writing, they are works-in-progress but may be avail‐
263 able at:
264 http://www.linnaean.org/~hag/
266perl v5.8.8 2005-12-08 Patricia(3)