<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">Net::IPTrie

############################################################################
INSTALLATION
############################################################################

You have two options:

perl Build.PL
./Build
./Build test
./Build install

or (if you have GNU make):
perl Makefile.PL
make
make test
make install


############################################################################
BACKGROUND: 
############################################################################
A trie structure is based on a radix tree using a radix of two.  
This is commonly used in routing engines, which need to quickly find the best 
match for a given address against a list of prefixes.
The term "Trie" is derived from the word "retrieval".
For more information on digital trees, see:
   * Algorithms in C, Robert Sedgewick

How it works:
A digital tree is built by performing a binary comparison on each bit of 
the number (in this case, the IP address) sequentially, starting from the 
most significant bit.  

Examples:

 Given these two IP addresses:
                 bit 31                                0
                     |                                 |
   10.0.0.0/8      : 00001010.00000000.00000000.00000000/8
   10.128.0.0/32   : 00001010.10000000.00000000.00000000/32

 Insert the first one in the trie and look up the second one.

 Starting with the first address:

 bit     tree position
 -------------------------------------------------------------------
 31             0
 30           0
 29         0
 28       0
 27         1
 26       0
 25         1
 24       0    &lt;-- Prefix position (size - prefix).  Stop and save object


 Continuing with the second address:

 bit     tree position
 -------------------------------------------------------------------
 31             0
 30           0
 29         0
 28       0
 27         1
 26       0
 25         1
 24       0    &lt;-- 10.0.0.0/8 exists here
 23          1  
 22     0

 ...continued until bit 0

Since there are no more objects to process, it is determined
that the "parent" of the second adddress is the first address.


############################################################################
COPYRIGHT AND LICENCE
############################################################################

Copyright (c) 2007-2010, Carlos Vicente &lt;cvicente@cpan.org&gt;. All rights reserved.

This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.

</pre></body></html>