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 # IPv6 support:
24 $pt = new Net::Patricia AF_INET6;
25 $pt->add_string('2001:db8::/32');
26 $pt->add_string('2001:db8:0:dead::/64');
27 $pt->add_string('2001:db8:0:beef::/64');
28 $pt->climb(sub { print "climbing at node $_[0]\n" });
29 print $pt->match_string('2001:db8:0:dead::1'), "\n";
30 # IPv4-mapped IPv6 addresses:
32 $pt->add_string('::ffff:0:0/96');
33 for my $cidr (qw( 192.0.2.0/24 192.0.2.0/25 192.0.2.128/25 )) {
34 my($ip, $len) = split(m|/|, $cidr);
35 $pt->add_string("::ffff:$ip/" .
36 (96+(defined($len)? $len : 32)), $cidr);
37 }
38 $pt->climb(sub { print "climbing at node $_[0]\n" });
39 print $pt->match_string("::ffff:" . "192.0.2.129"), "\n";
40
42 This module uses a Patricia Trie data structure to quickly perform IP
43 address prefix matching for applications such as IP subnet, network or
44 routing table lookups. The data structure is based on a radix tree
45 using a radix of two, so sometimes you see patricia implementations
46 called "radix" as well. The term "Trie" is derived from the word
47 "retrieval" but is pronounced like "try". Patricia stands for
48 "Practical Algorithm to Retrieve Information Coded as Alphanumeric",
49 and was first suggested for routing table lookups by Van Jacobsen.
50 Patricia Trie performance characteristics are well-known as it has been
51 employed for routing table lookups within the BSD kernel since the 4.3
52 Reno release.
53 The BSD radix code is thoroughly described in "TCP/IP Illustrated,
55 Volume 2" by Wright and Stevens and in the paper ``A Tree-Based Packet
56 Routing Table for Berkeley Unix'' by Keith Sklower.
57
59 new - create a new Net::Patricia object
60 $pt = new Net::Patricia;
61 This is the class' constructor - it returns a "Net::Patricia"
63 object upon success or undef on failure. The constructor takes an
64 optional argument (of AF_INET or AF_INET6, defaulting to the
65 former), and creates a tree with address and mask values of that
66 type as keys.
67 The "Net::Patricia" object will be destroyed automatically when
69 there are no longer any references to it.
70 add_string
72 $pt->add_string(key_string[,user_data]);
73 The first argument, key_string, is a network or subnet
75 specification in canonical form, e.g. "10.0.0.0/8", where the
76 number after the slash represents the number of bits in the
77 netmask. If no mask width is specified, the longest possible mask
78 is assumed, i.e. 32 bits for AF_INET addresses.
79 The second argument, user_data, is optional. If supplied, it
81 should be a SCALAR value (which may be a perl reference) specifying
82 the user data that will be stored in the Patricia Trie node.
83 Subsequently, this value will be returned by the match methods
84 described below to indicate a successful search. Remember that
85 perl references and objects are represented as SCALAR values and
86 therefore the user data can be complicated data objects.
87 If no second argument is passed, the key_string will be stored as
89 the user data and therfore will likewise be returned by the match
90 functions.
91 On success, this method returns the user_data passed as the second
93 argument or key_string if no user data was specified. It returns
94 undef on failure.
95 match_string
97 $pt->match_string(key_string);
98 This method searches the Patricia Trie to find a matching node,
100 according to normal subnetting rules for the address and mask
101 specified.
102 The key_string argument is a network or subnet specification in
104 canonical form, e.g. "10.0.0.0/8", where the number after the slash
105 represents the number of bits in the netmask. If no mask width
106 value is specified, the longest mask is assumed, i.e. 32 bits for
107 AF_INET addresses.
108 If a matching node is found in the Patricia Trie, this method
110 returns the user data for the node. This method returns undef on
111 failure.
112 match_exact_string
114 $pt->match_exact_string(key_string);
115 This method searches the Patricia Trie to find a matching node.
117 Its semantics are exactly the same as those described for
118 "match_string" except that the key must match a node exactly. I.e.
119 it is not sufficient that the address and mask specified merely
120 falls within the subnet specified by a particular node.
121 match_integer
123 $pt->match_integer(integer[,mask_bits]);
124 This method searches the Patricia Trie to find a matching node,
126 according to normal subnetting rules for the address and mask
127 specified. Its semantics are similar to those described for
128 "match_string" except that the key is specified using an integer
129 (i.e. SCALAR), such as that returned by perl's "unpack" function
130 for values converted using the "N" (network-ordered long). Note
131 that this argument is not a packed network-ordered long.
132 Just to be completely clear, the integer argument should be a value
134 of the sort produced by this code:
135 use Socket;
137 $integer = unpack("N", inet_aton("10.0.0.0"));
138 match_exact_integer
140 $pt->match_exact_integer(integer[,mask_bits]);
141 This method searches the Patricia Trie to find a matching node.
143 Its semantics are exactly the same as "match_integer" except that
144 the key must match a node exactly. I.e. it is not sufficient that
145 the address and mask specified merely falls within the subnet
146 specified by a particular node.
147 remove_string
149 $pt->remove_string(key_string);
150 This method removes the node which exactly matches the the address
152 and mask specified from the Patricia Trie.
153 If the matching node is found in the Patricia Trie, it is removed,
155 and this method returns the user data for the node. This method
156 returns undef on failure.
157 climb
159 $pt->climb([CODEREF]);
160 This method climbs the Patricia Trie, visiting each node as it does
162 so. It performs a non-recursive, "preorder" traversal.
163 The CODEREF argument is optional. It is a perl code reference used
165 to specify a user-defined subroutine to be called when visiting
166 each node. The node's user data will be passed as the sole
167 argument to that subroutine.
168 This method returns the number of nodes successfully visited while
170 climbing the Trie. That is, without a CODEREF argument, it simply
171 counts the number of nodes in the Patricia Trie.
172 Note that currently the return value from your CODEREF subroutine
174 is ignored. In the future the climb method may return the number
175 of times your subroutine returned non-zero, as it is called once
176 per node. So, if you are currently relying on the climb return
177 value to accurately report a count of the number of nodes in the
178 Patricia Trie, it would be prudent to have your subroutine return a
179 non-zero value.
180 This method is called climb() rather than walk() because climbing
182 trees (and therfore tries) is a more popular pass-time than walking
183 them.
184 climb_inorder
186 $pt->climb_inorder([CODEREF]);
187 This method climbs the Patricia Trie, visiting each node in order
189 as it does so. That is, it performs an "inorder" traversal.
190 The CODEREF argument is optional. It is a perl code reference used
192 to specify a user-defined subroutine to be called when visiting
193 each node. The node's user data will be passed as the sole
194 argument to that subroutine.
195 This method returns the number of nodes successfully visited while
197 climbing the Trie. That is, without a CODEREF argument, it simply
198 counts the number of nodes in the Patricia Trie.
199 Note that currently the return value from your CODEREF subroutine
201 is ignored. In the future the climb method may return the number
202 of times your subroutine returned non-zero, as it is called once
203 per node. So, if you are currently relying on the climb return
204 value to accurately report a count of the number of nodes in the
205 Patricia Trie, it would be prudent to have your subroutine return a
206 non-zero value.
207 This method is called climb() rather than walk() because climbing
209 trees (and therfore tries) is a more popular pass-time than walking
210 them.
211 Serialization
213 Net::Patricia trees, unlike many classes with XS-level data, can be
214 frozen and thawed using Storable.
215
217 When passing a CODEREF argument to the climb method, the return value
218 from your CODEREF subroutine is currently ignored. In the future the
219 climb method may return the number of times your subroutine returned
220 non-zero, as it is called once per node. So, if you are currently
221 relying on the climb return value to accurately report a count of the
222 number of nodes in the Patricia Trie, it would be prudent to have your
223 subroutine return a non-zero value.
224
226 Dave Plonka <plonka@doit.wisc.edu> Philip Prindeville
227 <philipp@redfish-solutions.com> Anton Berezin <tobez@tobez.org>
228 Copyright (C) 2000-2005 Dave Plonka. Copyright (C) 2009 Dave Plonka
230 & Philip Prindeville. This program is free software; you can
231 redistribute it and/or modify it under the terms of the GNU General
232 Public License as published by the Free Software Foundation; either
233 version 2 of the License, or (at your option) any later version.
234 This product includes software developed by the University of Michigan,
236 Merit Network, Inc., and their contributors. See the copyright file in
237 the patricialib sub-directory of the distribution for details.
238 patricialib, the C library used by this perl extension, is an extracted
240 version of MRT's patricia code from radix.[ch], which was worked on by
241 Masaki Hirabaru and Craig Labovitz. For more info on MRT see:
242 http://www.mrtd.net/
244 The MRT patricia code owes some heritage to GateD's radix code, which
246 in turn owes something to the BSD kernel.
247
249 perl(1), Socket, Net::Netmask, Text::Trie, Tree::Trie.
250 Tree::Radix and Net::RoutingTable are modules by Daniel Hagerty
252 <hag@linnaean.org> written entirely in perl, unlike this module. At
253 the time of this writing, they are works-in-progress but may be
254 available at:
255 http://www.linnaean.org/~hag/
257perl v5.34.0 2022-01-21 Patricia(3)