Codebase list libnet-iptrie-perl / HEAD
HEAD

Tree @HEAD (Download .tar.gz) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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    <-- 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    <-- 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) Carlos Vicente <cvicente@cpan.org>. All rights reserved.

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

Commit History @HEAD