1Patricia(3)           User Contributed Perl Documentation          Patricia(3)
2
3
4

NAME

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

SYNOPSIS

9         use Net::Patricia;
10
11         my $pt = new Net::Patricia;
12
13         $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
21         undef $pt; # automatically destroys the Patricia Trie
22
23         # 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
31         # 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

DESCRIPTION

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
54       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

METHODS

59       new - create a new Net::Patricia object
60              $pt = new Net::Patricia;
61
62           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
68           The "Net::Patricia" object will be destroyed automatically when
69           there are no longer any references to it.
70
71       add_string
72             $pt->add_string(key_string[,user_data]);
73
74           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
80           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
88           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
92           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
96       match_string
97             $pt->match_string(key_string);
98
99           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
103           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
109           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
113       match_exact_string
114             $pt->match_exact_string(key_string);
115
116           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
122       match_integer
123             $pt->match_integer(integer[,mask_bits]);
124
125           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
133           Just to be completely clear, the integer argument should be a value
134           of the sort produced by this code:
135
136              use Socket;
137              $integer = unpack("N", inet_aton("10.0.0.0"));
138
139       match_exact_integer
140             $pt->match_exact_integer(integer[,mask_bits]);
141
142           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
148       remove_string
149             $pt->remove_string(key_string);
150
151           This method removes the node which exactly matches the the address
152           and mask specified from the Patricia Trie.
153
154           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
158       climb
159              $pt->climb([CODEREF]);
160
161           This method climbs the Patricia Trie, visiting each node as it does
162           so.  It performs a non-recursive, "preorder" traversal.
163
164           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
169           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
173           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
181           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
185       climb_inorder
186              $pt->climb_inorder([CODEREF]);
187
188           This method climbs the Patricia Trie, visiting each node in order
189           as it does so.  That is, it performs an "inorder" traversal.
190
191           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
196           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
200           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
208           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
212   Serialization
213       Net::Patricia trees, unlike many classes with XS-level data, can be
214       frozen and thawed using Storable.
215

BUGS

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

AUTHOR

226       Dave Plonka <plonka@doit.wisc.edu> Philip Prindeville
227       <philipp@redfish-solutions.com> Anton Berezin <tobez@tobez.org>
228
229       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
235       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
239       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
243          http://www.mrtd.net/
244
245       The MRT patricia code owes some heritage to GateD's radix code, which
246       in turn owes something to the BSD kernel.
247

SEE ALSO

249       perl(1), Socket, Net::Netmask, Text::Trie, Tree::Trie.
250
251       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
256          http://www.linnaean.org/~hag/
257
258
259
260perl v5.34.0                      2022-01-21                       Patricia(3)
Impressum