From Linuxnetworks
IP tree structure with prefix based operations
If you need to accumulate IP traffic stats or have to find values attached to IP addresses, using a tree structure is the most efficient way. The C++ IPPrefTree template is a generic data structure for working with IPv4 or IPv6 related content of any kind. It provides very fast lookups for values attached to a single IP address or to the parent subnet if the address isn't available and enables you to retrieve all values in parent nodes added to the tree before as well.
[edit] Code and documenation
[edit] Example
#include <stdio>
IPPrefTree<int> ipv4; // stored values are integers
IPPrefTreeIterator<int> node;
unsigned char addr1[4] = { 192, 168, 1, 1 };
unsigned char addr2[4] = { 192, 168, 1, 2 };
unsigned char net[4] = { 255, 255, 255, 255 };
/* add value "1" to the node for "192.168.1" */
ipv4.add( addr1, 24, 4, 1 );
/* add value "2" to the node for "192.168.1.2" */
ipv4.add( addr2, net, 4, 2 );
/* find the best matching node */
if( ( node = lookup( addr1, net, 4, false ) ) != ipv4.end() )
{
// points to the node for "192.168.1" and will print "1"
std::cout << *node;
}
/* find the exact node
will point to the node for "192.168.1.2" */
node = lookup( addr2, 32, 4, true );
/* this will print 2 and 1 because the IP of addr2
is part of the subnet defined by addr1 */
while( node != ipv4.end() )
{
std::cout << *node;
node++;
}
[edit] License
The IPPrefTree code is freely available and distributeable under the terms of the GPLv2 license. It is based on the idea of Mark Bergsma who implemented a similar data structure for the GEO backend available for the PowerDNS server.
