Code Library/IPPrefTree
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.
Code and documenation
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++;
}
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.
